论文笔记 – Semi-Supervised Classification with Graph Convolutional Network

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(·)$ 来实现的。

这篇文章有两方面贡献:

  1. 设计了一个简单的层级网络传播规则,并说明这个设计是怎么从谱图卷积理论得到启发的
  2. 展示 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 图的半监督学习

之前有两类方法:

  1. 带拉普拉斯正则项的:标签传递?流形正则化项?深度半监督嵌入?
  2. 基于图嵌入的:deepwalk 从自己向邻居随机游走。

基于图拉普拉斯正则项的,会被其前提假设(边只代表节点之间的相似度)限制;基于 skip-gram 的,都是 pipeline 方法,不好优化;GCN 克服了这俩限制。

4.2 图神经网络

一开始有人用 RNN 做;然后有人用 CNN 的想法,但要学习每个顶点都不一样的参数,规模大就完蛋。本文的方法用了卷积的想法、每个顶点参数都一样,比他们都强。这里我明白了这篇文章的意义:以前人用谱域卷积的想法做图卷积,都是挨个点有各自的函数,GCN 非常优雅,格局很大,是一个全局的函数(我又在胡说什么)。

在图节点分类问题上,有人是把图节点转化为序列,再 CNN 分类,复杂度 $O(N^2)$,还得提前规定节点的顺序。我们这个又快又好。

5 实验结果

  1. GCN 性能 SOTA,最快。
  2. GCN 的这个层级传播规则,上面推导过程中的每次近似(或者说简化),都对性能有帮助。
  3. 时间复杂度和边数线性相关。

6 讨论

限制

  1. 现在是 full-batch,对内存要求高,以后要改成 mini-batch。
  2. 现在只能适用于无向图,以后得适配有向图。
  3. 现在 $\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] GNN 教程:漫谈谱图理论和GCN的起源

9 TODO

  1. graphsage、[6] [7]
  2. 切比雪夫多项式为什么能 localized?跟切比雪夫滤波器有什么关系?

[mathjax]

Leave a Comment

电子邮件地址不会被公开。