WWW-2019-SEAL

Contents

• Semi-Supervised Graph Classification: A Hierarchical Graph Perspective
  • 研究问题
  • 解决方案
    • 两个挑战
    • 方案思路
    • 损失函数
  • 分类器设计
    • IC: 生成Embedding
    • HC: 传统的节点分类任务
  • 迭代模型
    • 复杂度分析
  • 实验评估
    • 图嵌入算法（SAGE）
    • SEAL-C/AI模型

Semi-Supervised Graph Classification: A Hierarchical Graph Perspective

研究问题

层次图上的半监督（图）节点分类。以下图为例，社交网络表示为一个“层次图”，其上的节点（用户组A,B,C,D）也是“图实例”；在每个表示用户组的图实例中，各节点表示一个用户，具有年龄、性别等属性；在（层次图、图实例）结构一定，已知部分（用户组）节点标签的情况下，对未知节点（C,D）进行分类。

解决方案

两个挑战

• 层次图对于分类器而言是一种复杂的输入结构
• 在真实数据中标签往往是稀缺的

方案思路

1. 两个分类器（定义disagreement loss保证两个分类器结果的一致性）

   • IC: instance-level，生成每个instance的 graph embedding、属于各类别的概率
   • HC: hierarchical graph level，每个instance属于各类别的概率

2. 半监督学习SEmi-supervised grAph cLassification（迭代的算法架构，轮流更新IC/HC）

   两种迭代更新方法

   • SEAL-CI: Cautious Iteration，每一轮HC预测后选出预测标签置信度较高的子集扩充训练集
   • SEAL-AI: Active-learning，每次迭代时选出最具信息量的图实例做人工标注

损失函数

$$min\zeta(G_l)+\xi(G_u)$$

• 减小有监督(labeled)样本的分类损失：IC和HC的交叉熵之和

  $$\zeta(G_l)=\sum_{g_l\in{G_l}}(L(y_i,\psi_i)+L(y_i,\gamma_i))$$

• 减小无监督(ublabeled)样本两个分类器之间的判别距离：KL散度 $D_{KL}(P\vert\vert Q)=\sum_jP_jlog(\frac{P_j}{Q_j})$

  $$\xi(G_u)=\sum_{g_l\in{G_l}}D_{KL}(\gamma_i \vert \vert\psi_i)$$

分类器设计

IC: 生成Embedding

self-attetion graph embedding (SAGE)：两层图卷积+（graph-level readout）attention机制

• 增加了损失项 $\vert\vert SS^T-I_r \vert\vert _F^2$，惩罚attention矩阵将各节点视为类似重要的情况。其中 $\vert\vert \cdot \vert\vert _F$ 表示矩阵的佛罗贝尼乌斯范数（Frobenius norm），即各元素的平方和开根号。

HC: 传统的节点分类任务

将每个图实例视为节点，输入邻接矩阵、节点特征（embedding）。使用两层GCN。

迭代模型

损失函数包含组合项和连续项；其中，有监督损失中的HC分类器损失依赖于IC的embedding结果；使得该优化问题非凸。因此使用迭代算法交替减小IC和HC分类器的有监督损失，通过在下轮迭代时信任HC预测结果的子集来减小分歧损失。

在$t$轮迭代时，IC生成所有节点的embedding $E^t$，喂入HC，得到预测结果 $\Gamma^t$，利用 $\Gamma^t$ 更新IC的参数，生成 $E^{t+1}$…

Q: 如何利用$\Gamma^t$ ？【算法Line 6】

1. SEAL-CI

   在$t$轮迭代时，从未标注样本中选择$t\lambda$个最”自信”的预测结果加入labeled样本，直到所有未标注样本被用完；

   $h(\lambda,\Gamma)=top(max_{\gamma\in{\Gamma}}\gamma, \lambda)$，其中函数$top(\cdot, \lambda)$表示选取前$\lambda$个示例。

   

   为了提升效率，使用微调（fine-tune, not re-train）的方法更新IC.

   没用到disagreement loss？？？还有循环中t未更新= =

2. SEAL-AI

   $G_{tmp}$为一个使disagreement loss下降最快的样本集合。

   

   其中 $B$ 表示标注样本的预算开销。

复杂度分析

以SEAL-CI模型的一轮迭代为例，复杂度$O(E_1\phi(L+U)+E_2rv)$。与图实例的个数、边数，层次图的边数呈线性关系。

• 更新IC：所有图实例的GCN卷积，$O(E_1\phi(L+U))$
• 更新HC：层次图的GCN卷积，$O(E_2rv)$
• 候补图实例选择：未标注图实例预测结果的比较，$O(L+U)$ ???

实验评估

图嵌入算法（SAGE）

在PROTEINS和D&D数据集（判断蛋白质是不是酶）上，与6个baseline（前四种核方法与PSCN论文中的实验设置相同）比较，准确率如下：

SEAL-C/AI模型

1. 合成数据集：层次图结构来自Cora数据集，是包含2708个（论文）节点的引用网络；该数据集有7个类别的节点，每类使用不同的图生成算法来生成图实例。

   7个图生成算法：Watts-Strogatz [32], Tree graph, Erdős-Rényi [8], Barbell [13], Bipartite graph, Baraba´siAlbert graph [2] and Path graph

   

2. QQ：37,836个用户组，共18,422,331个用户，每个用户有7个属性（注册天数，过去90天最活跃地区的代码，好友数，过去30天的活跃天数、登录次数、发送消息的条数、在用户组内发送消息的条数）；用户组中，有1,773个标记为“game”，剩余为“non-game”。

   

   为什么SEAL-AL优于SEAL-CL？（随着迭代次数增加，SEAL-CL引入的新标签中不准确的增加）