WWW-2019-SEAL

Reading time ~3 minutes

Contents

Semi-Supervised Graph Classification: A Hierarchical Graph Perspective

image-20201211112621071

研究问题

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

image-20201211113824573

解决方案

两个挑战

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

方案思路

  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机制

image-20201211144101351
  • 增加了损失项 \(\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预测结果的子集来减小分歧损失。

image-20201212104007432

在\(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\)个示例。

    image-20201211162412773

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

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

  2. SEAL-AI

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

    image-20201211162334603

    其中 \(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论文中的实验设置相同)比较,准确率如下:

image-20201212105323885

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

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

    image-20201212111847476

    为什么SEAL-AL优于SEAL-CL?(随着迭代次数增加,SEAL-CL引入的新标签中不准确的增加)

    image-20201212112013812

SHAP源码之GradientExplainer

Published on January 01, 2022

可解释方法LIME和SHAP代码实战

Published on November 29, 2021