Thomas N. Kipf, Max Welling, “Semi-Supervised Classification with Graph Convolutional Networks”, ICLR 2017
这篇文章是鼎鼎大名的图卷积网络。如上文所述，图上的卷积操作是从信号的卷积类比而来的。那 GCN 的卷积是什么呢？作者说 GCN 的计算复杂度和图的边数线性相关，这是通过什么 trick 达到的呢？之前也有人做谱图相关的工作，这篇文章为什么有如此巨大的影响呢？带着这些问题，我开始了 kipf 的论文 [1] 和博客 [2] 的阅读。
1 简介
图中的节点分类，其中只有部分节点有标注，这就是图的半监督学习问题。之前的人通过带有图拉普拉斯正则化项的损失函数进行优化：$$\mathcal{L} = \mathcal{L}_0 + \lambda\mathcal{L}_{reg}$$ $$\mathcal{L}_{reg} = \sum_{i,j}A_{ij}\|f(X_i) – f(X_j)\|^2 = f(X)^T\triangle f(X)$$
其中，$\mathcal{L}_0$ 是监督学习的损失函数，$f(·)$ 就是神经网络那种可微的函数，$\lambda$ 是平衡两部分的参数，$X$ 是节点特征的矩阵，$\triangle = D-A$ 是拉普拉斯矩阵。设计 $\mathcal{L}_reg$ 的假设是，边权越大的两个节点，其内容相似度也就越大。但是这就限制了模型，因为图的结构不仅包含了相邻节点的相似度，还可能包含了其他信息。
这篇文章的工作就避免了图拉普拉斯正则项，只使用一个 $f(X,A)$ 这种神经网络，用 $\mathcal{L}_0$ 进行训练。图结构是通过改变 $f(·)$ 来实现的。
这篇文章有两方面贡献：
- 设计了一个简单的层级网络传播规则，并说明这个设计是怎么从谱图卷积理论得到启发的
- 展示 GCN 怎么用来半监督学习
2 图卷积的快速近似
GCN 的层级传播规则如下：$$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$ 是图加上自连接的邻接矩阵，$\tilde{D}$ 就是对应的度矩阵，$W$ 是神经网络参数（或者说，卷积核的参数），$\sigma(·)$ 是激活函数，$H^{(l)}\in\mathbb{R}^{N\times D}$ 是第 $l$ 层网络的，节点图信号的特征表示，$H^0 = X$。下面就详细论述这个式子是怎么推导出来的。
2.1 谱图卷积
图的谱域卷积为：$$g_{\theta}\star x = Ug_{\theta}U^Tx$$
其中 $U$ 是归一化拉普拉斯矩阵 $L = I_n – D^{-\frac{1}{2}} A D^{-\frac{1}{2}} = U\Lambda U^T$ 的特征向量矩阵。$U^Tx$ 表示将原始信号 $x$ 变换到谱域，$g_\theta U^T x$ 表示在谱域过一个卷积核，$Ug_{\theta}U^Tx$ 表示再进行反变换，回到空间域，如下图所示（图源：[5] ）。这里的卷积核 $g_\theta$ 可以被理解为 $L$ 的特征值的函数，比如 $g_\theta(\Lambda)$。
这个式子的计算复杂度很大，矩阵相乘就有 $O(N^2)$ 的计算复杂度，特征分解更是 $O(N^3)$ 复杂度。于是 [6] 提出，可以用切比雪夫多项式的前几项，来近似替代 $g_\theta(\Lambda)$：$$g_{\theta’}(\Lambda)\approx\sum_{k=0}^K\theta’_kT_k(\tilde{\Lambda})$$
其中 $\tilde{\Lambda} = \frac{2}{\lambda_{max}}\Lambda – I_N$，$\lambda_{max}$ 表示 $L$ 的最大特征值。$\theta’\in\mathbb{R}^K$ 是切比雪夫多项式的系数。切比雪夫多项式是递归定义的：$T_k(x) = 2xT_{k-1}(x)-T_{k-2}(x),T_0(x) = 1, T_1(x) = x$。于是谱域卷积表达式可近似为：$$g_{\theta’}\star x\approx \sum_{k=0}^K\theta’_kT_k(\tilde{L})x$$
其中 $\tilde{L} = \frac{2}{\lambda_{max}}L – I_N = U\tilde{\Lambda}U^T$。现在这个表达式是 localized 了，因为这是前 $k$ 项的切比雪夫多项式，相当于节点只跟与他距离 $\le k$ 的节点发生关系，或者说进行“平滑”。（这里我并不明白，唉，DSP 学艺不精啊 #TODO2）[7] 就是直接用这个 $k$-localized 定义的图卷积神经网络。
2.2 多层神经网络
于是，图卷积网络就可用多层用上面式子表达的卷积层堆叠在一起构成。我们只取切比雪夫多项式的前两项，且估计 $\lambda_{max}\approx 2$，这样就得到：$$g_{\theta’}\star x\approx \theta’_0x + \theta’_1(L-I_N)x = \theta’_0x-\theta’_1D^{-\frac{1}{2}}AD^{-\frac{1}{2}}x$$
这时还是有两个参数 $\theta’_0,\theta’_1$，再简化一下，把这俩都简化成 $\theta$：$$g_{\theta’}\star x\approx \theta(I_N + D^{-\frac{1}{2}}AD^{-\frac{1}{2}})x$$
这里 $\theta = \theta’_0 = -\theta’_1$。注意，这里 $I_N + D^{-\frac{1}{2}}AD^{-\frac{1}{2}}$ 不方便计算，可以用这样一个 trick：$I_N + D^{-\frac{1}{2}}AD^{-\frac{1}{2}} \rightarrow \tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}$，其中 $\tilde{A} = A+I_N, \tilde{D}_{ii} = \sum_j\tilde{A}_{ij}$
这样一来，我们就得到了最终的表达式：一个信号 $X\in\mathbb{R}^{N\times C}$（$N$ 个顶点，每个顶点是 $C$ 维向量）通过 $F$ 个卷积窗口的信号：$$Z = \tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}} X\Theta$$
其中 $\Theta\in\mathbb{R}^{C\times F}$ 是所有卷积窗口参数的矩阵。这个式子的卷积操作的复杂度仅为 $O(|\mathcal{E}|FC)$。
3 半监督顶点分类
多层 GCN 的结构如图所示：
先计算 $\hat{A} = \tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}$，前递网络形式为：$$Z = f(X,A) = \text{softmax}(\hat{A} \text{ ReLU}(\hat{A}XW^{(0)})W^{(1)})$$
其中 $W^{(0)}\in\mathbb{R}^{C\times H}$ 是从输入到隐层的参数矩阵（$N$ 个顶点，每个顶点是 $C$ 维向量，$H$ 个卷积核），$W^{(1)}\in\mathbb{R}^{H\times F}$ 是从隐层到输出层的参数矩阵。对半监督分类任务，损失函数就设计成交叉熵：$$\mathcal{L} = -\sum_{l\in\mathcal{Y}_L}\sum_{f=1}^FY_{lf}\ln Z_{lf}$$
其中 $\mathcal{Y}_L$ 是有标签的顶点集合。优化使用 SGD。
总结一下，优化过程是把每个顶点的 feature 当做 sample，训练图的函数。而为了用上图的结构信息，作者定义了一个统一的谱域变换卷积的过程（谱域变换就考虑了邻接矩阵嘛）。
4 相关工作
4.1 图的半监督学习
之前有两类方法：
- 带拉普拉斯正则项的：标签传递？流形正则化项？深度半监督嵌入？
- 基于图嵌入的：deepwalk 从自己向邻居随机游走。
基于图拉普拉斯正则项的，会被其前提假设（边只代表节点之间的相似度）限制；基于 skip-gram 的，都是 pipeline 方法，不好优化；GCN 克服了这俩限制。
4.2 图神经网络
一开始有人用 RNN 做；然后有人用 CNN 的想法，但要学习每个顶点都不一样的参数，规模大就完蛋。本文的方法用了卷积的想法、每个顶点参数都一样，比他们都强。这里我明白了这篇文章的意义：以前人用谱域卷积的想法做图卷积，都是挨个点有各自的函数，GCN 非常优雅，格局很大，是一个全局的函数（我又在胡说什么）。
在图节点分类问题上，有人是把图节点转化为序列，再 CNN 分类，复杂度 $O(N^2)$，还得提前规定节点的顺序。我们这个又快又好。
5 实验结果
- GCN 性能 SOTA，最快。
- GCN 的这个层级传播规则，上面推导过程中的每次近似（或者说简化），都对性能有帮助。
- 时间复杂度和边数线性相关。
6 讨论
限制
- 现在是 full-batch，对内存要求高，以后要改成 mini-batch。
- 现在只能适用于无向图，以后得适配有向图。
- 现在 $\tilde{A} = A+I_N$，应该加个 trade-off: $\tilde{A} = A+\lambda I_N$
[3] 把 GCN 与 CNN 类比，认为 GCN 过于简陋。
7 附录
7.1 关于 WL 算法
关于 WL-test，详见 [8]。作者就把 GCN 类比成一维 WL-test。那么三层 GCN，其实就是传播三次，做个平滑。因此即使随机初始化参数，直接套 GCN 不训练，也能得到很好的顶点特征表示。
7.2 关于半监督
只给每类一个标注的节点，300 次迭代之后竟然全分开了。
7.3 关于模型的层数
两三层是最好的；大于 7 层的话，没有残差链接，就训练不了啦。过拟合是一个待解决的问题！
8 引用和拓展阅读
[1] Thomas N. Kipf, Max Welling, “Semi-Supervised Classification with Graph Convolutional Networks”, ICLR 2017 GCN 的原始论文
[2] GRAPH CONVOLUTIONAL NETWORKS kipf 写的博客，写出了他设计 GCN 的 motivation
[3] How powerful are Graph Convolutions? (review of Kipf & Welling, 2016)
[4] 如何理解 Graph Convolutional Network（GCN）？ – Johnny Richards的回答 – 知乎
[5] 图神经网络在线研讨会 沈华伟老师部分 bilibili 必看！讲得太好了！男神！
[6] David K. Hammond, Pierre Vandergheynst, and Re ́mi Gribonval. Wavelets on graphs via spectral graph theory. Applied and Computational Harmonic Analysis, 30(2):129–150, 2011.
[7] Michae ̈l Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Advances in neural information processing systems (NIPS), 2016.
[8] 什么是Weisfeiler-Lehman(WL)算法和WL Test？ – 苘郁蓁的文章 – 知乎
9 TODO
- graphsage、[6] [7]
- 切比雪夫多项式为什么能 localized？跟切比雪夫滤波器有什么关系？
[mathjax]