ICLR 2017。图卷积中谱图领域理论上很重要的一篇论文，提升了图卷积的性能，使用切比雪夫多项式的1阶近似完成了高效的图卷积架构。原文链接：Semi-Supervised Classification with Graph Convolutional Networks. Kipf & Welling 2017
摘要
我们提出了一种在图结构数据上的半监督可扩展学习方法，基于高效的图卷积变体。契机是通过一个谱图卷积的局部一阶近似得到的我们的图卷积结构。我们的模型与图的边数呈线性关系，学习到的隐藏层可以对图的顶点和局部图结构同时进行编码。在引文网络和一个知识图谱数据集上的大量实验结果表明我们的方法比相关方法好很多。
引言
$$\tag{1} \mathcal{L} = \mathcal{L\_0} + \lambda \mathcal{L\_{reg}}, \rm with \ \mathcal{L\_{reg}} = \sum\_{i.j}A\_{ij} \Vert f(X\_i) - f(X\_j) \Vert^2 = f(X)^T \Delta f(X)$$其中，$\mathcal{L_0}$表示对于图的标签部分的监督损失，$f(\cdot)$可以是一个神经网络类的可微分函数，$\lambda$是权重向量，$X$是定点特征向量$X_i$的矩阵。$N$个顶点$v_i \in \mathcal{V}$，边$(v_i, v_j) \in \varepsilon$，邻接矩阵$A \in \mathbb{R}^{N \times N}$（二值的或者带权重的），还有一个度矩阵$D_{ii} = \sum_jA_{ij}$。式1依赖于“图中相连的顶点更有可能具有相同的标记”这一假设。然而，这个假设，可能会限制模型的能力，因为图的边并不是必须要编码成相似的，而是要包含更多的信息。 在我们的研究中，我们将图结构直接通过一个神经网络模型$f(X, A)$进行编码，并且在监督的目标$\mathcal{L_0}$下对所有有标记的顶点进行训练，因此避免了损失函数中刻意的对图进行正则化。在图的邻接矩阵上使用$f(\cdot)$可以使模型从监督损失$\mathcal{L_0}$中分布梯度信息，并且能够从有标记和没有标记的顶点上学习到他们的表示。 我们的贡献有两点，首先，我们引入了一个简单的，表现很好的针对神经网络的对层传播规则，其中，这个神经网络是直接应用到图上的，并且展示了这个规则是如何通过谱图卷积的一阶近似启发得到的。其次，我们展示了这种形式的基于图的神经网络可以用于对图中的顶点进行更快更可扩展的半监督分类任务。在大量数据集上的实验表明我们的模型在分类精度和效率上比当前在半监督学习中的先进算法要好。
图上的快速近似卷积
$$\tag{2} H^{(l+1)} = \sigma(\tilde{D}^{-\frac{1}{2}} \tilde{A} \tilde{D}^{-\frac{1}{2}} H^{(l)} W^{(l)})$$其中，$\tilde{A} = A + I_N$是无向图$\mathcal{G}$加了自连接的邻接矩阵。$I_N$是单位阵，$\tilde{D}_{ii} = \sum_j \tilde{A}_{ij}$，$W^{(l)}$是一个针对层训练的权重矩阵。$\sigma(\cdot)$表示一个激活函数，比如$\rm ReLU(\cdot) = \rm max(0, \cdot)$，$H^{(l)} \in \mathbb{R}^{N \times D}$是第$l$层的激活矩阵；$H^{(0)} = X$。接下来我们将展示通过图上的一阶近似局部谱滤波器(Hammond et al., 2011; Defferrard et al., 2016)的传播过程。
谱图卷积 spectral graph convolutions
$$\tag{3} g\_\theta \ast x = U g\_\theta U^T x$$$$\tag{4} g\_\theta' \approx \sum^K\_{k=0} \theta'\_k T\_k(\tilde{\Lambda})$$$$\tag{5} g\_\theta' \ast x \approx \sum^K\_{k=0} \theta'\_k T\_k(\tilde{L}) x$$其中，$\tilde{L} = \frac{2}{\lambda x_{max}} L - I_N$；注意$(U \Lambda U^T)^k = U \Lambda^k U^T$。这个表达式目前是$K$阶局部的，因为这个表达式是拉普拉斯矩阵的$K$阶多项式，也就是说从中心节点向外最多走$K$步，$K$阶邻居。式5的时间复杂度是$O(\vert \varepsilon \vert)$，也就是和边数呈线性关系。Defferrard et al.(2016)使用这个$K$阶局部卷积定义了在图上的卷积神经网络。
按层的线性模型 layer-wise linear model
$$\tag{6} g\_\theta' \ast x \approx \theta'\_0x + \theta'\_1 (L - I\_N)x = \theta'\_0x - \theta'\_1 D^{-\frac{1}{2}} A D^{-\frac{1}{2}} x$$$$\tag{7} g\_\theta \ast x \approx \theta(I\_N + D^{-\frac{1}{2}} A D^{-\frac{1}{2}}) x$$$$\tag{8} Z = \tilde{D}^{-\frac{1}{2}} \tilde{A} \tilde{D}^{-\frac{1}{2}} X \Theta$$其中$\Theta \in \mathbb{R}^{C \times F}$是一个滤波器的参数矩阵，$Z \in \mathbb{R}^{N \times F}$是卷积的信号矩阵。卷积操作的时间复杂度是$O(\vert \varepsilon \vert F C)$，因为$\tilde{A} X$可以被实现成一个稀疏矩阵和一个稠密矩阵的乘积。
半监督顶点分类
介绍过这个简单、灵活的可以在图上传播信息的模型$f(X, A)$后，我们回到半监督顶点分类的问题上。如介绍里面所说的，我们可以减轻在基于图的半监督学习任务中的假设，通过在图结构上的数据$X$和邻接矩阵$A$上使用模型$f(X, A)$。我们期望这个设置可以在邻接矩阵表达出数据$X$没有的信息的这种情况时表现的很好，比如引文网络中，引用的关系或是知识图谱中的关系。整个模型是一个多层的GCN，如图1所示。
例子
$$\tag{9} Z = f(X, A) = \rm softmax( \hat{A} \ \rm ReLU( \hat{A}XW^{(0)})W^{(1)})$$$$\tag{10} \mathcal{L} = - \sum\_{l \in \mathcal{Y}\_L} \sum^F\_{f = 1} Y\_{lf} \ln(Z\_{lf})$$其中，$\mathcal{Y}_L$是有标签的顶点的下标集合。 神经网络权重$W^{(0)}$和$W^{(1)}$使用梯度下降训练。我们每次训练的时候都是用全部的训练集来做梯度下降，只要数据集能放到内存中。对$A$进行稀疏矩阵的表示，内存的使用量是$O(\vert \varepsilon \vert)$。训练过程中使用了dropout增加随机性。我们将在未来的工作使用mini-batch随机梯度下降。
实现
我们使用Tensorflow实现了基于GPU的，稀疏稠密矩阵乘法形式。式9的时间复杂度是$O(\vert \varepsilon \vert C H F)$。