「论文阅读（简）」Semi-Supervised Classification with Graph Convolutional Network

论文名称：Semi-Supervised Classification with Graph Convolutional Network

作者：Kipf, Thomas N., Max Welling

时间：2017年

期刊或会议：ICLR

代码：https://github.com/dragen1860/GCN-PyTorch

原文摘要

We present a scalable approach for semi-supervised learning on graph-structured data that is based on an effificient variant of convolutional neural networks which operate directly on graphs. We motivate the choice of our convolutional architecture via a localized fifirst-order approximation of spectral graph convolutions. Our model scales linearly in the number of graph edges and learns hidden layer representations that encode both local graph structure and features of nodes. In a number of experiments on citation networks and on a knowledge graph dataset we demonstrate that our approach outperforms related methods by a signifificant margin.

理论基础

标签只适用于一小部分的节点子集这个问题可以通过构建一个基于图的半监督学习，这使得标签可以通过使用一些形式的显式的图正则化，比如在损失函数中加入图拉普拉斯正则化项：
$公式1：\mathcal{L}=\mathcal{L}_{0}+\lambda \mathcal{L}_{\mathrm{reg}}, \quad \text { with } \quad \mathcal{L}_{\mathrm{reg}}=\sum_{i, j} A_{i j}\left\|f\left(X_{i}\right)-f\left(X_{j}\right)\right\|^{2}=f(X)^{\top} \Delta f(X)$
其中 $L_0$ 表示图中有标签部分的监督损失， $f(\cdot)$ 是类似神经网络的可微函数， $\lambda$ 是权重因子， $X$ 是节点特征向量 $X_{i}$ 的矩阵。 $\Delta=D-A$ 表示无向图 $\mathcal{G}=(\mathcal{V}, \mathcal{E})$ （其有N个节点 $v_{i} \in \mathcal{V}$ ，边 $\left(v_{i}, v_{j}\right) \in \mathcal{E}$ ，邻接矩阵 $A \in \mathbb{R}^{N \times N}$ ，度矩阵 $D_{i i}=\sum_{j} A_{i j}$ ）的非标准化图拉普拉斯矩阵。

任务与存在的问题

在图上的节点分类任务（知识图谱中的文档分类）存在问题：标签只适用于一小部分的节点子集。
在公式1中依赖一个假设：图上连接的节点是共享相同标签的。但这个假设可能会限制建模能力，因为图的边不需要编码节点的相似性，但可能包含额外的信息。

主要工作

提出了一个在图结构数据上的用于半监督学习的可伸缩的方法，其是卷积神经网络的一个有效变体，可以直接在图上操作。通过谱图卷积的局部一阶近邻来激发卷积体系结构的选择。

创新点

针对直接作用于图的神经网络模型，引入了一种简单且行为良好的分层传播规则，展示如何从谱卷积的一阶近似中激发他。
展示了这种形式的基于图的神经网络如何用于图中节点的快速和可拓展的半监督分类。

在图上的快速近似图卷积

多层GCN可以根据下面的分层传播规则计算：

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

其中 $\tilde{A}=A+I_{N}$ 是添加了自环的无向图 $\mathcal{G}$ 的邻接矩阵。 $I_{N}$ 是单位矩阵， $\tilde{D}_{i i}=\sum_{j} \tilde{A}_{i j}$ 和 $W^{(L)}$ 是特定层中可以被训练的权重矩阵。 $\sigma(\cdot)$ 表示激活函数。 $\operatorname{ReLU}(\cdot)=\max (0, \cdot) . H^{(l)} \in \mathbb{R}^{N \times D}$ 是在第l层激活后的矩阵。 $H^{(0)}=X$ 。

谱图卷积

本文将在图上的谱图卷积当做在傅里叶域中，使用通过 $\theta \in \mathbb{R}^{N}$ 参数化过的滤波器 $g_{\theta}=\operatorname{diag}(\theta)$ 和一个信号 $x \in \mathbb{R}^{N}$ （每个节点的标量）的矩阵乘法，可以用下面的公式表示：

$公式3：g_{\theta} \star x=U g_{\theta} U^{\top} x$

其中 $U$ 是归一化的图拉普拉斯矩阵 $L=I_{N}-D^{-\frac{1}{2}} A D^{-\frac{1}{2}}=U \Lambda U^{\top}$ 的特征向量矩阵，这个图拉普拉斯矩阵有一个特征值为 $\Lambda$ 的对角矩阵， $U^{\top} x$ 是 $x$ 的图傅里叶变化。可以将 $g_{\theta}$ 理解为 $L$ 的特征值的一个函数，比如 $g_{\theta}(\Lambda)$ 。由于特征向量矩阵 $U$ 的乘法运算是 $O(N^2)$ 的，因此在大型图中计算 $L$ 的特征分解代价很大。为了解决这个问题， $g_{\theta}(\Lambda)$ 可以用切比雪夫多项式 $T_{k}(x)$ 的阶段展开来近似代替：

$公式4：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} \in \mathbb{R}^{K}$ 是切比雪夫系数的一个向量。q切比雪夫多项式的递归定义为： $T_{k}(x)=2 x T_{k-1}(x)-T_{k-2}(x)$

因此公式3可以根据公式4近似表示为

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

其中 $\tilde{L}=\frac{2}{\lambda_{\max }} L-I_{N}$ ， $\left(U \Lambda U^{\top}\right)^{k}=U \Lambda^{k} U^{\top}$ ，这个表达式现在是K-localized的，因为他是拉普拉斯行列式中的第一个K阶多项式。比如，他只依赖于距离中心节点(K阶邻域)最大K阶的节点。

分层线性模型

在GCN的线性公式中，进一步近似 $\lambda_{max} \approx 2$ ，在这个近似下，公式5可以简化为：

$公式6：g_{\theta^{\prime} \star} \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_{0}^{\prime}$ 和 $\theta_{1}^{\prime}$ 是两个自由的参数，滤波器参数可以在整张图上共享。

实际上进一步约束参数量对解决过拟合问题和最小化每一层的操作数量是有益的，于是又了下面的式子：

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

其中参数 $\theta=\theta_{0}^{\prime}=-\theta_{1}^{\prime}$ ，注意 $I_{N}+D^{-\frac{1}{2}} A D^{-\frac{1}{2}}$ 现在有在 $[0,2]$ 之间的特征值。重复使用这个操作会是使得深度神经网络模型参数不稳定，梯度爆炸和梯度消失。为了减轻这个问题，使用了renormalization技巧： $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}$ , $\tilde{D}_{i i}=\sum_{j} \tilde{A}_{i j}$ 。

于是可以形成对于一个有 $C$ 个输入通道(每个节点又C维的特征向量)和 $F$ 利波器或特征映射的信号 $X \in \mathbb{R}^{N \times C}$ 的定义如下：

$公式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}$ 是卷积信号矩阵。

半监督节点分类

引入以简单灵活的模型 $f(X,A)$ ，用于在图上有效地传播信息。对于半监督节点分类问题，可以通过将模型 $f(X,A)$ 对数据X和底层图结构的邻接矩阵A进行调整，拉放松基于图的半监督学习中所做的某些假设。期望这种方法在邻接矩阵包含数据X中不存在的信息的场景中有强大的表现。整个模型是一个用于半监督学习的多层GCN，如下图所示：

使用对称邻接矩阵A在图上使用一个两层的GCN进行半监督图节点分类。首先，在预处理步骤中计算 $\hat{A}=\tilde{D}^{-\frac{1}{2}} \tilde{A} \tilde{D}^{-\frac{1}{2}}$ ，然后，前向模型可以用下面的公式表示：

$公式9：Z=f(X, A)=\operatorname{softmax}\left(\hat{A} \operatorname{ReLU}\left(\hat{A} X W^{(0)}\right) W^{(1)}\right)$

其中 $W^{(0)} \in \mathbb{R}^{C \times H}$ 具有H特征映射的隐藏层的input-to-hidden权重矩阵。 $W^{(1)} \in \mathbb{R}^{H \times F}$ 是hidden-to-output的权重矩阵。softmax的计算公式为： $\operatorname{softmax}\left(x_{i}\right)=\frac{1}{\mathcal{Z}} \exp \left(x_{i}\right)$ 其中 $\mathcal{Z}=\sum_{i} \exp \left(x_{i}\right)$ 。对于半监督多类别分类任务，会在所有标记的样本上的交叉熵误差进行评估：