基于图卷积网络的半监督分类

摘要

一种基于图上的卷积神经网络的半监督学习方法. 谱图卷积的一阶近似. 模型的规模 (csales) 关于图边数线性增长, 学习将局部图结构和结点特征编码的隐藏层表示. 在引用网络 (citation network) 和知识图谱数据集 (knowledge graph dataset) 上实验效果好.

介绍

图上的结点分类问题 (如引用网络中的文档分类), 仅有很少的结点有标签. 可归为半监督学习的框架, 标签信息通过一些形式的基于图的正则化项在图上平滑(smoothed over the graph) (Zhu et al., 2003; Zhou et al., 2004; Belkin et al., 2006; Weston et al., 2012). 例: 在损失函数中使用图的拉普拉斯正则化项:

$$\mathcal { L } = \mathcal { L } _ { 0 } + \lambda \mathcal { L } _ { \text {reg }},$$ $$\mathcal { L } _ { \mathrm { reg } } = \sum _ { i , j } A _ { i j } \left\| f \left( X _ { i } \right) - f \left( X _ { j } \right) \right\| ^ { 2 } = f ( X ) ^ { \top } \Delta f ( X ).\tag{1}$$

其中$\mathcal { L } _ { 0 }$是监督损失, $f ( \cdot )$神经网络状 (nn-like) 的可微函数, $\lambda$是权重因子, $X$是结点特征矩阵, 由结点特征向量$X_i$组成. $\Delta = D - A$是图$\mathcal { G } = ( \mathcal { V } , \mathcal { E } )$的为规范化的拉普拉斯矩阵. 邻接矩阵$A \in \mathbb { R } ^ { N \times N }$为二值或有权重. $(1)$需要假设图中相邻结点倾向于共享同一标签. 这一假设可能会限制模型的表示能力 (因为图的边不需要结点编码相似), 但可以包含更多的附加信息.

在这篇文章中, 直接使用神经网络模型$f ( X , A )$将图结构编码, 并在所有有标签的结点上有监督地训练目标$\mathcal { L } _ { 0 }$, 从而避免了显式的基于图的正则化项. 在邻接矩阵上训练 (condition) $f(\cdot)$使模型能够从监督损失$\mathcal { L } _ { 0 }$中给出 (distribute) 梯度信息.

本文的贡献为两部分. 首先, 对神经网络模型引入一个简单而有用的 (well-behaved) 逐层传播方式, 它直接作用在图上, 并且我们会说明它如何从谱图卷积的一阶近似(Hammond et al., 2011)中受到启发. 其次, 说明了这种形式的基于图的神经网络如何用于快速可扩展的半监督图结点分类. 实验说明在速度和准确度上都比现在的最先进的半监督方法好.

图上的快速近似卷积

本节给出本文使用的基于图的神经网络模型的理论依据. 考虑多层GCN, 按以下方式传播:

$$H ^ { ( l + 1 ) } = \sigma \left( \tilde { D } ^ { - \frac { 1 } { 2 } } \tilde { A } \tilde { D } ^ { - \frac { 1 } { 2 } } H ^ { ( l ) } W ^ { ( l ) } \right). \tag{2}$$

其中$\tilde{A}=A+I_N$是无向图$\mathcal{G}$的邻接矩阵加上自联系 (self-connection), $\tilde { D } _ { i i } = \sum _ { j } \tilde { A } _ { i j }$, $W ^ { ( l ) }$是层的可训练权重矩阵. $H ^ { ( l ) } \in \mathbb { R } ^ { N \times D }$是第l层的激活值 (activations) 矩阵, $H ^ { ( 0 ) } = X$.
以下给出这种传播规则如何受通过图上的局部谱过滤器 (localized spectral filters) (Hammond et al., 2011), (Defferrard et al., 2016) 的一阶近似启发.

谱图卷积

图上的谱卷积定义为图信号$x \in \mathbb { R } ^ { N }$ (每个结点对应一个标量) 与参数化滤波器$g _ { \theta } = \operatorname { diag } ( \theta )$在傅立叶域内的乘积, 即:

$$g _ { \theta } \star x = U g _ { \theta } U ^ { \top } x \tag{3}$$

其中$U$是规范化图拉普拉斯算子$L = I _ { N } - D ^ { - \frac { 1 } { 2 } } A D ^ { - \frac { 1 } { 2 } } =U \Lambda U ^ { \top }$的特征向量矩阵, 对角阵$\Lambda$是特征值矩阵, $U^\top x$是$x$的傅立叶变换. $g_\theta$视为特征值的函数: $g _ { \theta } ( \Lambda )$. 计算(3)复杂度: $\mathcal{O}(N^2)$, 同时特征分解也很难算. 为了规避之, Hammond et al. (2011) 认为$g _ { \theta } ( \Lambda )$可以通过切比雪夫多项式$T _ { k } ( x )$的截断展开逼近到K阶:

$$g _ { \theta ^ { \prime } } ( \Lambda ) \approx \sum _ { k = 0 } ^ { K } \theta _ { k } ^ { \prime } T _ { k } ( \tilde { \Lambda } ) ,$$

其中$\tilde { \Lambda } = \frac { 2 } { \lambda _ { \text {max } } } \Lambda - I _ { N }$. $\lambda_{\max}$是$L$的最大特征值. $\theta ^ { \prime } \in \mathbb { R } ^ { K }$在这里是切比雪夫系数. 切比雪夫多项式递归给出: $T _ { 0 } ( x ) = 1,\ T _ { 1 } ( x ) = x,\ T _ { k } ( x ) =2 x T _ { k - 1 } ( x ) - T _ { k - 2 } ( x ).$
在这一表示下, 信号$x$关于滤波器$g _ { \theta ^ { \prime } }$的卷积为:

$$g _ { \theta ^ { \prime } } \star x \approx \sum _ { k = 0 } ^ { K } \theta _ { k } ^ { \prime } T _ { k } ( \tilde { L } ) x, \tag{5}$$

注意到$\left( U \Lambda U ^ { \top } \right) ^ { k } = U \Lambda ^ { k } U ^ { \top }$, 从而有$\tilde { L } = \frac { 2 } { \lambda _ { \max } } L - I _ { N }$. 注意到这一表达式时K-局部的 (K-localized), 因为表达式中只有拉普拉斯算子的K次幂, 因此最多依赖于与中心结点距离为k的结点. 计算$(5)$的复杂度为$\mathcal { O } ( | \mathcal { E } | )$, 即关于边数线性. Defferrard et al. (2016) 使用K-局部卷积定义图上的CNN.

逐层的线性模型

可通过堆叠$(5)$中的卷积层来搭建神经网络模型. 在每层限制$K=1,$ 得到一个关于$L$的线性函数, 从而也使图的拉普拉斯矩阵的谱的线性函数.

按这种方式可以通过对点很多这样的层恢复一大类卷积滤波器, 但是我们不会将参数仅由切比雪夫多项式给出. 直观上我们希望这样的模型可以对度很大的图减轻在局部邻居结构上过拟合的问题, 如社交网络, 引用网络, 知识图谱许多现实中的数据集. 同时这种方法使得我们在算力有限的情况下可以搭建更深层的网络.

进一步假设$\lambda _ { \max } \approx 2$, 我们预期这一变化会在训练中实现. 在这一假设下, $(5)$可以简化为:

$$g _ { \theta ^ { \prime } } \star x \approx \theta _ { 0 } ^ { \prime } x + \theta _ { 1 } ^ { \prime } \left( L - I _ { N } \right) x = \theta _ { 0 } ^ { \prime } x - \theta _ { 1 } ^ { \prime } D ^ { - \frac { 1 } { 2 } } A D ^ { - \frac { 1 } { 2 } } x,$$

有两个自由的参数$\theta _ { 0 } ^ { \prime }$和$\theta _ { 1 } ^ { \prime }$, 这两个过滤器变量在整个网络中共享. 后续应用这种形式的滤波可以高效地对一个结点的k阶邻居做卷积, 这里k是后续卷积的操作数或神经网络的卷积层数.

若进一步降低参数的数量到一个 (以解决过拟合问题和减少操作 (如矩阵乘法)), 有:

$$g _ { \theta } \star x \approx \theta \left( I _ { N } + D ^ { - \frac { 1 } { 2 } } A D ^ { - \frac { 1 } { 2 } } \right) x ,$$

其中$\theta = \theta _ { 0 } ^ { \prime } = - \theta _ { 1 } ^ { \prime }$. 注意到$I _ { N } + D ^ { - \frac { 1 } { 2 } } A D ^ { - \frac { 1 } { 2 } }$的特征值在$[0, 2]$范围内 (由于$L$的最大特征值$\lambda_{\max}\approx2$), 重复使用这一算子会导致数值不稳定及梯度爆炸 (或消失). 为此, 引入再规范化技巧 (renormalization trick):

$$I _ { N } + D ^ { - \frac { 1 } { 2 } } A D ^ { - \frac { 1 } { 2 } } \rightarrow \tilde { D } ^ { - \frac { 1 } { 2 } } \tilde { A } \tilde { D } ^ { - \frac { 1 } { 2 } },$$

其中$\tilde { A } = A + I _ { N },\ \tilde { D } _ { i i } = \sum _ { j } \tilde { A } _ { i j }$ (给$D$每个元素加1?).

将这一定义推广到信号$X \in \mathbb { R } ^ { N \times C }$上(每个结点有C个通道, 对应一个C维向量, 和F个滤波器 (?)), 结果如下:

$$Z = \tilde { D } ^ { - \frac { 1 } { 2 } } \tilde { A } \tilde { D } ^ { - \frac { 1 } { 2 } } X \Theta, \tag{8}$$

其中$\Theta \in \mathbb { R } C \times F$是滤波参数矩阵, $Z \in \mathbb { R } ^ { N \times F }$是卷积后的信号. 滤波操作的复杂度是$\mathcal { O } ( | \mathcal { E } | F C )$, 因为计算$\tilde { A } X$时对稀疏矩阵和非稀疏矩阵乘积运算可以很高效.

半监督结点分类

引入图上的信息传播模型$f(X,\ A)$后, 回到半监督节点分类问题. 我们期望当邻接矩阵包含没有在特征矩阵$X$中表达的信息 (如引用网络, 或知识图谱中的关联) 时, 我们的假设会起很大的作用. 整体模型见图1.

例

考虑两层GCN, 可以预先计算$\hat { A } = \tilde { D } ^ { - \frac { 1 } { 2 } } \tilde { A } \tilde { D } ^ { - \frac { 1 } { 2 } }$, 从而前向传播模型形式为:

$$Z = f ( X , A ) = \operatorname { softmax } \left( \hat { A } \operatorname { ReLU } \left( \hat { A } X W ^ { ( 0 ) } \right) W ^ { ( 1 ) } \right)\tag{9}$$

其中$W ^ { ( 0 ) } \in \mathbb { R } ^ { C \times H }$是输入到隐藏层的权重矩阵, 有$H$个特征映射; $W ^ { ( 1 ) } \in \mathbb { R } ^ { H \times F }$是隐藏层到输出层的权重矩阵. softmax 激活函数定义为: $\operatorname { softmax } \left( x _ { i } \right) = \frac { 1 } {\mathcal { Z }} \exp \left( x _ { i } \right),$ 其中$\mathcal { Z } = \sum _ { i } \exp \left( x _ { i } \right)$. 多分类问题的损失函数定义为交叉熵:

$$\mathcal { L } = - \sum _ { l \in \mathcal { Y } _ { L } } \sum _ { f = 1 } ^ { F } Y _ { l f } \ln Z _ { l f } \tag{10}$$

其中$\mathcal { Y } _ { L }$是有标签的结点的指标集; 1到F是最后的类, 最后的$Z_{lf}$是分到第f类的概率.

使用梯度下降训练权重$W ^ { ( 0 ) }$和$W ^ { ( 1 ) }$. 本文中使用批梯度下降 (SGD, 每次使用全部数据做梯度下降, 随机梯度下降留给以后的工作(?)). 对$A$采用稀疏表示. 内存占用为$\mathcal { O } ( | \mathcal { E } | )$. 通过 dropout (Srivastava et al., 2014) 引入随机性.

实施

使用TensorFlow (Abadi et al., 2015) 计算$(9)$, 复杂度$\mathcal { O } ( | \mathcal { E } | C H F )$

相关工作

基于图的半监督学习

近年来的研究粗略分为两类: 使用某些显式图拉普拉斯矩阵正则化形式的方法和图嵌入的方法 (Zhu et al., 2003),