Abstract 摘要

We present a scalable approach for semi-supervised learning on graph-structureddata that is based on an efficient variant of convolutional neural networks whichoperate directly on graphs. We motivate the choice of our convolutional archi-tecture via a localized first-order approximation of spectral graph convolutions.Our model scales linearly in the number of graph edges and learns hidden layerrepresentations that encode both local graph structure and features of nodes. In a number of experiments on citation networks and on a knowledge graph datasetwe demonstrate that our approach outperforms related methods by a significantmargin.


我们提出了一种可扩展的图结构数据半监督学习方法,该方法基于直接在图上运行的卷积神经网络的有效变体。我们通过谱图卷积的局部一阶近似来激励卷积结构的选择。我们的模型在图边的数量上线性扩展,并学习对局部图结构和节点特征进行编码的隐藏层表示。在引文网络和知识图数据集上的大量实验表明,我们的方法明显优于相关方法。

Notes 笔记

考虑一个基于图的半监督学习问题:图上的分类任务,节点中只有少部分给出了标签,标签信息经过了平滑正则(在损失函数上施加图拉普拉斯变换),即假设相邻节点的标签相似,这一假设限制了模型的表达能力,因为图中的边并不一定表示两端节点的相似性,可能包含其他信息。本文直接使用神经网络模型对图结构进行编码,并对有标签的节点进行训练,避免这种平滑正则。

本文的两个贡献:

  • 谱图卷积的一阶近似、逐层传播规则->一种图卷积神经网络;
  • 这种模型如何运用在图节点的半监督分类任务上。

首先给出逐层传播规则的终极形式:

推导过程如下:

先考虑信号$x$与滤波器$g_\theta = diag(\theta)$在傅里叶域的谱卷积:

其中$U$是对称归一化的拉普拉斯算子$L$的特征向量矩阵,即:

$g_\theta$可以看作是关于特征值矩阵$\Lambda$的函数,即:

$g_\theta(\Lambda)$可以用Chebyshev多项式$T_k(x)$的前k阶来拟合,即:

其中$\tilde{\Lambda}=\frac{2} {\lambda_{\max } } \Lambda-I_{N}$,$\lambda_{\max }$是$L$的最大特征值,$\theta^{\prime}$是Chebyshev系数向量。

回到卷积定义中,有:

之后作者提出一些简化,先令K=1,使单个卷积层关于$L$是线性函数。

将$\lambda_{max}$近似为2,简化为:

此式含有两个参数,如果进一步令$\theta=\theta_{0}^{\prime}=-\theta_{1}^{\prime}$,则只剩一个参数$\theta$:

注意到$I_{N}+D^{-\frac{1}{2}} A D^{-\frac{1}{2}}$的特征值范围是[0,2],反复使用会造成数值发散和梯度爆炸,作者采用了一个归一化技巧,使其特征值范围变成[0,1]:

其中

可以理解为给图上添加了自环。

将$x$扩充到$X \in \mathbb{R}^{N \times C}$上,有:

这样就得到了文章一开始给出的层间传播规则:

实验部分,在cora数据集上进行实验,某几次运行的结果如下:

image-20220630081030221

image-20220630081906529

原文中相同参数下(200 epoch, 0.01 lr, 0.0005 L2 regularization, 16 number of hid-den units),100次运行的平均test_acc为81.5。

Conclusion 结论

We have introduced a novel approach for semi-supervised classification on graph-structured data.Our GCN model uses an efficient layer-wise propagation rule that is based on a first-order approx-imation of spectral convolutions on graphs. Experiments on a number of network datasets suggestthat the proposed GCN model is capable of encoding both graph structure and node features in away useful for semi-supervised classification. In this setting, our model outperforms several recentlyproposed methods by a significant margin, while being computationally efficient.


我们提出了一种新的图结构数据半监督分类方法。我们的GCN模型使用了一种有效的分层传播规则,该规则基于图上谱卷积的一阶近似。在大量网络数据集上的实验表明,所提出的GCN模型能够同时对图结构和节点特征进行编码,有助于半监督分类。在这种情况下,我们的模型在计算效率方面显著优于最近提出的几种方法。

如果笔记中有错误,敬请指出;如果您有不同的理解,欢迎讨论。