Semi-Supervised Classification with Graph Convolutional Networks

摘要

我们提出了一种可扩展的图结构数据上的半监督学习方法，该方法是直接操作图的卷积神经网络的高效变体。我们通过谱图卷积的局部一阶近似来给出我们选择卷积结构的原因。

我们的模型与图的边数呈线性关系，并可以学习带有图的局部结构和节点的特征信息的隐藏层表示。在引文网络和知识图数据集上的大量实验中，我们证明了我们的方法比相关方法有显著的优势。

引言

我们考虑对图（如引用网络）中的节点（如文档）进行分类的问题，其中仅一小部分节点带有标签。该问题可以被定义为基于图的半监督学习，其中通过某种显式的基于图的正则化在图上平滑标签信息，例如，通过在损失函数中使用图拉普拉斯正则化项：

\[\mathcal{L} = \mathcal{L}_{0} + \lambda \mathcal{L}_{\text{reg}} \ \text{, 其中} \ \mathcal{L}_{\text{reg}} = \sum_{i,j}A_{i,j} \Vert f(X_{i}) - f(X_{j}) \Vert^{2} = f(X)^{\top} \Delta f(X)\]

这里，\(\mathcal{L}_{0}\) 表示图的带标记部分的监督损失。\(f(\cdot)\) 可以是类似神经网络的可微函数，\(\lambda\) 是权重因子，\(X\) 是节点特征向量 \(X_{i}\) 的矩阵。\(\Delta=D-A\) 表示无向图 \(\mathcal{G} = (\mathcal{V}, \mathcal{E})\) 的非正规图拉普拉斯，该图具有 \(N\) 个节点 \(v_{i} \in \mathcal{V}\)、边 \((v_{i},v_{j}) \in \mathcal{E}\)、邻接矩阵 \(A \in \mathcal{R}^{N \times N}\)（二进制或加权）和度矩阵 \(D_{ii} = \sum_{j} A_{ij}\)。等式1的公式依赖于图中的连接节点可能共享相同标签的假设。然而，这种假设可能会限制建模能力，因为图边不一定必须带有节点相似性，但可能包含其他信息。

本工作中，我们直接使用神经网络模型 $f(X,A)$ 对图的结构进行编码，并针对带标签的所有节点在监督目标 $\mathcal{L}_{0}$ 上进行训练，从而避免了损失函数中基于图的显式正则化。在图的邻接矩阵上调节 $f(\cdot)$ 将允许模型从监督损失 \(\mathcal{L}_{0}\) 中分布梯度信息，并将使其能够学习带标签和不带标签的节点表示。

我们的贡献是双重的：

• 我们为直接作用于图的神经网络模型引入了一种简单且性能良好的分层传播规则，并展示了如何从谱卷积的一阶近似中解释该规则。
• 我们演示了这种基于图的神经网络模型如何用于图中节点的快速和可扩展半监督分类。

在大量数据集上的实验表明，我们的模型在分类精度和效率（以挂钟时间衡量）方面均优于半监督学习的最新方法。

图的快速近似卷积

本节中，我们为后面使用的基于图的神经网络模型 $f(X,A)$ 提供了理论依据。我们考虑具有以下逐层传播规则的多层图卷积网络GCN:

\(H^{(l+1)} = \sigma \Big( \tilde{D}^{-\frac{1}{2}} \tilde{A} \tilde{D}^{-\frac{1}{2}} H^{(l)} W^{(l)} \Big)\) 这里， $\tilde{A} = A + I_{N}$ 是具有附加自环的无向图 \(\mathcal{G}\) 的邻接矩阵。$I_{N}$ 是单位矩阵，\(\tilde{D}_{ii} = \sum_{j} \tilde{A}_{ij}\)， $W^{(l)}$ 是按层的可训练权重矩阵。$\sigma(\cdot)$ 表示激活函数，例如 $ReLU(\cdot)=max(0, \cdot)$。$H^{(l)} \in \mathbb{R}^{N \times D}$ 是第 $l$ 层中的激活矩阵；$H^{(0)}=X$。

下文中，我们将证表明，这种传播规则的形式可以通过图上局部谱滤波器的一阶近似来解释。

谱图卷积

考虑图上的谱卷积，其定义为信号 $x \in \mathbb{R}^{N}$（每个节点的标量）与滤波器 $g_{θ}=diag(\theta)$ 的乘积，参数 $\theta$ 在傅立叶域中 $\theta \in \mathbb{R}^{N}$ ，即：

\[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_{θ}$ 理解为 $L$ 的特征值的函数，即 $g_{\theta}(\Lambda)$。由于与特征向量矩阵 $U$ 相乘的复杂度为 $\mathcal{O}(N^{2})$，等式3的计算是很费时的。此外，在第一步就计算 $L$ 的特征分解对于大型图来说可能非常昂贵。为了避免这个问题，Hammond等人提出，$g_{\theta}(\Lambda)$ 可以通过切比雪夫多项式 $T_{k}(x)$ 的截断展开很好地逼近到 $k$ 阶：

\[g_{\theta^{'}}(\Lambda) \approx \sum_{k=0}^{K} \theta_{k}^{'}T_{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\)。

读者可参考Hammond等人的文献Wavelets on graphs via spectral graph theory对此近似进行更深入的了解。

回到我们定义的信号 $x$ 与滤波器 $g_{\theta^{‘}}$ 的卷积，有：

\(g_{\theta^{'}} \star x \approx \sum_{k=0}^{K}\theta_{k}^{'}T_{k}({\tilde{L}}) x\) 其中，$\tilde{L}=\frac{2}{\lambda_{max}} L - I_{N}$. 考虑到 $(U \Lambda U^{\top})^{k}=U \Lambda^{k} U^{\top}$，上式很容易证明。

注意该表达式现在是K-localized的，因为它是拉普拉斯多项式中的第 $K$ 阶，即它仅取决于距离中心节点（第 $K$ 阶邻域）最大 $K$ 步的节点。计算公式5的复杂度为 $\mathcal{O}(\mathcal{E})$，即与边数是线性关系。Defferard等人使用该 $K$-局部卷积定义了图上的卷积神经网络。

分层线性模型

因此，可以通过堆叠多个式5形式的卷积层来建立基于图卷积的神经网络模型，每一层之后是逐点非线性。现在，假设我们将逐层卷积运算限制为 $K=1$（见式5），即是 $L$ 的线性函数，因此是图拉普拉斯谱上的线性函数。

通过这种方式，我们仍然可以通过叠加多个此类层来恢复丰富的卷积滤波函数，但我们不限于像切比雪夫多项式等给出的显式参数化。

我们直观地认为，这种模型可以缓解具有非常广的节点度分布的图的局部邻域结构的过拟合问题，如社交网络、引用网络、知识图和许多其他真实世界的图数据集。此外，对于固定的计算能力，这种分层线性公式允许我们构建更深层次的模型，这一实践已知可以提高许多领域的建模能力。

在GCN的线性公式中，我们进一步近似 $\lambda_{max} \approx 2$，因为我们可以预期神经网络参数将适应训练期间的这种规模变化。在这些近似下，等式5简化为：

\(g_{\theta^{'}} \star x \approx \theta_{0}^{'}x + \theta_{1}^{'}(L-L_{N})x =\theta_{0}^{'}x - \theta_{1}^{'} D^{-\frac{1}{2}} A D^{-\frac{1}{2}} x\) 具有两个参数 $\theta_{0}^{‘}$ 和 $\theta_{1}^{‘}$。滤波器参数可以在整个图上共享。这种形式的滤波器的多个应用可以有效地卷积节点的第 $k$ 阶邻域，其中 $k$ 是神经网络模型中连续滤波操作或卷积层的数目。

在实践中，进一步限制参数的数量以解决过拟合问题并最小化每层的操作数量（如矩阵乘法）可能是有益的。式6进一步化简如下：

\(g_{\theta^{'}} \star x \approx \theta \Big (I_{N} + D^{-\frac{1}{2}} A D^{-\frac{1}{2}} \Big ) x\) 其中 $\theta = \theta_{0}^{‘} - \theta_{1}^{‘}$， 注意 $I_{N} + D^{-\frac{1}{2}} A D^{-\frac{1}{2}}$ 有 $[0,2]$ 之间的特征值。因此，在深度神经网络模型中重复应用该算子可能导致数值不稳定和梯度爆炸/消失。为了缓解这个问题，我们引入了以下归一化技巧：

\[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}_{ii} = \sum_{j} \tilde{A}_{ij}\)。

我们可以将此定义推广到具有 $C$ 个输入通道（即每个节点的 $C$ 维特征向量）和 $F$ 个滤波器或特征映射的信号 $X \in \mathbb{R}^{N \times C}$，如下所示：

\(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}$ 是卷积信号矩阵。这种滤波操作的复杂度为 $\mathcal{O}(\vert \mathcal{E} \vert FC)$，因为 $\tilde{A}X$ 可以有效地实现为稀疏矩阵与稠密矩阵的乘积。

半监督节点分类

已经引入了一个简单但灵活的模型 $f(X, A)$ 来实现图上的有效信息传播，我们可以回到半监督节点分类问题。如引言中所述，我们可以通过在数据 $X$ 和底层图结构的邻接矩阵 $A$ 上调节模型 $f(X, A)$，来放宽松基于图的半监督学习中通常做出的某些假设。我们预计，在邻接矩阵包含数据 $X$ 中不存在的信息的情况下，该设置尤其强大，例如引用网络中文档之间的引用链接或知识图中的关系。整体模型，一个半监督学习的多层GCN，如图1所示：

图1：左侧：用于半监督学习的多层GCN示意图，其中 $C$ 个输入通道和输出层的 $F$ 个特征映射。图结构（以黑线显示的边)在层上共享，$Y_{i}$ 表示标签。右图：用t-SNE降维算法对带5%标签的Cora数据集上训练的两层GCN的隐藏层激活进行可视化。颜色表示文档类。

例子

后面我们考虑一个两层GCN，用于对有对称邻接矩阵 $A$（二进制或加权）的图上的半监督节点分类。我们首先在预处理步骤中计算 $\hat{A} = \tilde{D}^{-\frac{1}{2}} \tilde{A} \tilde{D}^{-\frac{1}{2}}$。然后，我们的正向模型采用简单的形式：

\[Z=f(X,A)=\text{softmax} \Big( \hat{A} \ \text{ReLU} \big( \hat{A}XW^{(0)} \big) W^{(1)} \Big)\]

其中 $W^{(0)} \in \mathbb{R}^{C \times H}$ 是一个有 $H$ 个特征的隐藏层的输入层到隐藏层的权重矩阵。$W^{(1)} \in \mathbb{R}^{H \times F}$ 是一个隐藏层到输出层的权重矩阵。

定义为 $\text{softmax}(x_{i}) = \frac{1}{\mathcal{Z}} \text{exp}(x_{i})$ ，其中 $\mathcal{Z}=\sum_{i} \text{exp}(x_{i})$ 的softmax激活函数按行应用。

对于半监督分类，我们评估所有标记示例的交叉熵误差：

\(\mathcal{L}=-\sum_{l \in \mathcal{Y}_{L}} \sum_{f=1}^{F} Y_{lf} \ \text{ln} \ Z_{lf}\) 其中 $\mathcal{Y}_{L}$ 是带标签的节点的集合。

使用梯度下降法训练神经网络的权重 $W^{(0)}$ 和 $W^{(1)}$。在这项工作中，我们使用每个训练迭代的完整数据集执行批量梯度下降，这是一个可行的选择，只要数据集在内存中装的下。使用 $A$ 的稀疏表示，内存需求为 $\mathcal{O}(\mathcal{E})$，即与边数是线性关系。训练过程中通过dropout引入随机性。我们将高效内存扩展与小批量随机梯度下降作为未来的工作。

实现

在实践中，我们基于TensorFlow+GPU使用稀疏密集矩阵乘法实现等式9(实现代码)。公式9的计算复杂度为 $\mathcal{O}(\vert \mathcal{E} \vert CHF)$，即与图边数呈线性关系。

相关工作

基于图的半监督学习及最近的关于图的神经网络的工作启发了我们的模型。下文中，我们简要概述这两个领域的相关工作。

基于图的半监督学习

近年来提出了大量使用图表示的半监督学习方法，其中大多数分为两大类：

• 使用某种形式的显式图拉普拉斯正则化的方法
• 基于图嵌入的方法

图拉普拉斯正则化的突出例子包括标签传播、流形正则化和深度半监督嵌入。

最近，人们的注意力转移到了skip-gram模型启发的方法学习图嵌入的模型上。DeepWalk通过预测从图上随机游动中采样的节点的局部邻域来学习嵌入。LINE和node2vec使用更复杂的随机游动或广度优先搜索方案扩展了深度游动。然而，对于所有这些方法，需要一个包括随机游动生成和半监督训练的多步骤流水线，其中每个步骤都必须单独优化。Planetoid通过在学习嵌入的过程中注入标签信息来缓解这种情况。

图上的神经网络

Gori和Scarselli等人已经引入了对图进行操作的神经网络，作为递归神经网络的一种形式。他们的框架要求重复应用收缩映射作为传播函数，直到节点表示达到稳定的不动点。Li等人将递归神经网络训练的现代实践引入原始图形神经网络框架，缓解了这一限制。Duvenaud等人介绍了图上类似卷积的传播规则和图级分类方法。他们的方法需要学习节点度特定权重矩阵，该矩阵不适用于具有宽节点度分布的大型图。相反，我们的模型每层使用一个权重矩阵，并通过邻接矩阵的适当归一化处理不同的节点度（见第3.1节）。

Atwood&Towsley最近介绍了一种基于图的神经网络的相关节点分类方法。他们报告 $\mathcal{O}(N^{2})$ 的复杂度，限制了可能的应用范围。在一个不同但相关的模型中，Niepert等人将图形局部转换为序列，这些序列被馈送到传统的1D卷积神经网络中，这需要在预处理步骤中定义节点顺序。

我们的方法基于谱图卷积神经网络，在Bruna等人中介绍，随后由Defferard等人使用快速局部卷积进行扩展。与这些工作相反，我们在这里考虑的任务是在规模显著更大的网络中进行转换节点分类。我们表明，在这种情况下，可以在Bruna等人和Defferard等人的原始框架中引入一些简化（见第2.2节），以提高大规模网络中的可伸缩性和分类性能。

实验

结论

我们提出了图结构数据上半监督分类的一种新方法。我们的GCN模型使用了一种有效的逐层传播规则，该规则基于图谱卷积的一阶近似。在大量网络数据集上的实验表明该GCN模型能够以一种有助于半监督分类的方式对图结构和节点特征进行编码。在这种情况下，我们的模型在计算效率方面显著优于最近提出的几种方法。