SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKS

论文链接：SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKS

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 笔记

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

本文的两个贡献：

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

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

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

推导过程如下：

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

$$g_\theta * x = U g_\theta U^T x$$

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

$$L = U \Lambda U^T \qquad L = D^{-{1\over2}} (D-A) D^{-{1\over2}} = I_N - D^{-{1\over2}} A D^{-{1\over2}}$$

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

$$g_\theta = g_\theta(\Lambda)$$

$g_\theta(\Lambda)$可以用Chebyshev多项式$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{\max } } \Lambda-I{N}$，$\lambda_{\max }$是$L$的最大特征值，$\theta^{\prime}$是Chebyshev系数向量。

回到卷积定义中，有：

$$g_{\theta^{\prime}} \star x \approx \sum_{k=0}^{K} \theta_{k}^{\prime} T_{k}(\tilde{L}) x$$

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

将$\lambda_{max}$近似为2，简化为：

$$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=\theta{0}^{\prime}=-\theta{1}^{\prime}$，则只剩一个参数$\theta$：

$$g_{\theta} \star x \approx \theta\left(I_{N}+D^{-\frac{1}{2}} A D^{-\frac{1}{2}}\right) x$$

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

$$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} \text { and } \tilde{D}_{i i}=\sum_{j} \tilde{A}_{i j}$$

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

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

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

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

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

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

原文中相同参数下(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模型能够同时对图结构和节点特征进行编码，有助于半监督分类。在这种情况下，我们的模型在计算效率方面显著优于最近提出的几种方法。

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