Semi-Supervised Classification with Graph Convolutional Networks

用图卷积网络做半监督分类（Semi-Supervised Classification with Graph Convolutional Networks）

Thomas N. Kipf Affiliation: University of Amsterdam Email: T.N.Kipf@uva.nl    Max Welling Affiliation: University of Amsterdam Affiliation: Canadian Institute for Advanced Research (CIFAR) Email: M.Welling@uva.nl

Thomas N. Kipf
所属机构：阿姆斯特丹大学
电子邮箱：T.N.Kipf@uva.nl

Max Welling
所属机构：阿姆斯特丹大学；加拿大高级研究院（CIFAR）
电子邮箱：M.Welling@uva.nl

Abstract

摘要

We present a scalable approach for semi-supervised learning on graph-structured data that is based on an efficient variant of convolutional neural networks which operate directly on graphs. We motivate the choice of our convolutional architecture via a localized first-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 significant margin.

我们提出一种可扩展的图结构数据半监督学习方法，其核心是直接在图上运算的卷积神经网络的高效变体。卷积结构的选择由谱图卷积的局部一阶近似所启发。模型复杂度随图边数线性增长，学到的隐层表示同时编码局部图结构与节点特征。在若干引用网络与一个知识图谱数据集上的实验表明，该方法以显著优势超过相关方法。

1 Introduction

1 引言

We consider the problem of classifying nodes (such as documents) in a graph (such as a citation network), where labels are only available for a small subset of nodes. This problem can be framed as graph-based semi-supervised learning, where label information is smoothed over the graph via some form of explicit graph-based regularization (Zhu et al. 2003; Zhou et al. 2004; Belkin et al. 2006; Weston et al. 2012), e.g. by using a graph Laplacian regularization term in the loss function:

我们考虑对图中（例如引文网络）中的节点（例如文档）进行分类的问题，其中标签仅适用于一小部分节点。 这个问题可以被描述为基于图的半监督学习，其中标签信息通过某种形式的显式基于图的正则化在图上进行平滑（Zhu et al. 2003; Zhou et al. 2004; Belkin et al. 2006; Weston et al. 2012），例如 通过在损失函数中使用图拉普拉斯正则化项：

$$\mathcal{L}=\mathcal{L}_{0}+\lambda\mathcal{L}_{\text{reg}}\,,\quad\text{with}\quad\mathcal{L}_{\text{reg}}=\sum_{i,j}A_{ij}\|f(X_{i})-f(X_{j})\|^{2}=f(X)^{\top}\Delta f(X)\,. \tag{1}$$

Here, $\mathcal{L}_{0}$ denotes the supervised loss w.r.t. the labeled part of the graph, $f(\cdot)$ can be a neural network-like differentiable function, $\lambda$ is a weighing factor and $X$ is a matrix of node feature vectors $X_{i}$. $\Delta=D-A$ denotes the unnormalized graph Laplacian of an undirected graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ with $N$ nodes $v_{i}\in\mathcal{V}$, edges $(v_{i},v_{j})\in\mathcal{E}$, an adjacency matrix $A\in\mathbb{R}^{N\times N}$ (binary or weighted) and a degree matrix $D_{ii}=\sum_{j}A_{ij}$. The formulation of Eq. 1 relies on the assumption that connected nodes in the graph are likely to share the same label. This assumption, however, might restrict modeling capacity, as graph edges need not necessarily encode node similarity, but could contain additional information.

这里，$\mathcal{L}_{0}$ 表示监督损失 w.r.t. 图中的标记部分，$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\mathbb{R}^{N\times N}$（二进制或加权）和度矩阵$D_{ii}=\sum_{j}A_{ij}$。 方程式的制定 1 依赖于这样的假设：图中的连接节点可能共享相同的标签。 然而，这种假设可能会限制建模能力，因为图边不一定需要对节点相似性进行编码，但可能包含附加信息。

In this work, we encode the graph structure directly using a neural network model $f(X,A)$ and train on a supervised target $\mathcal{L}_{0}$ for all nodes with labels, thereby avoiding explicit graph-based regularization in the loss function. Conditioning $f(\cdot)$ on the adjacency matrix of the graph will allow the model to distribute gradient information from the supervised loss $\mathcal{L}_{0}$ and will enable it to learn representations of nodes both with and without labels.

在本工作中，我们用神经网络模型 $f(X,A)$ 直接编码图结构，并在所有带标签节点上对监督目标 $\mathcal{L}_{0}$ 训练，从而避免显式的基于图的正则。条件依赖于 $A$ 使模型能够在图的有标签与无标签节点之间分配梯度信息。

Our contributions are two-fold. Firstly, we introduce a simple and well-behaved layer-wise propagation rule for neural network models which operate directly on graphs and show how it can be motivated from a first-order approximation of spectral graph convolutions (Hammond et al. 2011). Secondly, we demonstrate how this form of a graph-based neural network model can be used for fast and scalable semi-supervised classification of nodes in a graph. Experiments on a number of datasets demonstrate that our model compares favorably both in classification accuracy and efficiency (measured in wall-clock time) against state-of-the-art methods for semi-supervised learning.

我们的贡献是双重的。 首先，我们为神经网络模型引入了一种简单且表现良好的分层传播规则，该规则直接在图上运行，并展示了如何从谱图卷积的一阶近似中激发它（Hammond 等人，2011）。 其次，我们演示了如何使用这种形式的基于图的神经网络模型对图中的节点进行快速且可扩展的半监督分类。 对多个数据集的实验表明，我们的模型在分类准确性和效率（以挂钟时间测量）方面与最先进的半监督学习方法相比都具有优势。

2 Fast Approximate Convolutions on Graphs

2 图上的快速近似卷积

In this section, we provide theoretical motivation for a specific graph-based neural network model $f(X,A)$ that we will use in the rest of this paper. We consider a multi-layer Graph Convolutional Network (GCN) with the following layer-wise propagation rule:

本节给出我们将在全文使用的图神经网络模型 $f(X,A)$ 的理论动机。考虑多层图卷积网络（GCN），其层间传播规则为：

$$\textstyle H^{(l+1)}=\sigma\!\left(\tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}H^{(l)}W^{(l)}\right)\,. \tag{2}$$

Here, $\tilde{A}=A+I_{N}$ is the adjacency matrix of the undirected graph $\mathcal{G}$ with added self-connections. $I_{N}$ is the identity matrix, $\tilde{D}_{ii}=\sum_{j}\tilde{A}_{ij}$ and $W^{(l)}$ is a layer-specific trainable weight matrix. $\sigma(\cdot)$ denotes an activation function, such as the $\mathrm{ReLU}(\cdot)=\max(0,\cdot)$. $H^{(l)}\in\mathbb{R}^{N\times D}$ is the matrix of activations in the $l^{\text{th}}$ layer; $H^{(0)}=X$. In the following, we show that the form of this propagation rule can be motivated[^1] via a first-order approximation of localized spectral filters on graphs (Hammond et al. 2011; Defferrard et al. 2016).

此处 $\tilde{A}=A+I_{N}$ 是带自环的无向图 $\mathcal{G}$ 的邻接矩阵。$I_{N}$ 为单位阵，$\tilde{D}_{ii}=\sum_{j}\tilde{A}_{ij}$，$W^{(l)}$ 为第 $l$ 层可训练权重矩阵，$\sigma(\cdot)$ 为激活函数，如 ReLU。$H^{(0)}=X$。

2.1 Spectral Graph Convolutions

2.1 谱图卷积

We consider spectral convolutions on graphs defined as the multiplication of a signal $x\in\mathbb{R}^{N}$ (a scalar for every node) with a filter $g_{\theta}=\text{diag}(\theta)$ parameterized by $\theta\in\mathbb{R}^{N}$ in the Fourier domain, i.e.:

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

$$g_{\theta}\star x=Ug_{\theta}U^{\top}x\,, \tag{3}$$

where $U$ is the matrix of eigenvectors of the normalized graph Laplacian $L=I_{N}-D^{-\frac{1}{2}}AD^{-\frac{1}{2}}=U\Lambda U^{\top}$, with a diagonal matrix of its eigenvalues $\Lambda$ and $U^{\top}x$ being the graph Fourier transform of $x$. We can understand $g_{\theta}$ as a function of the eigenvalues of $L$, i.e. $g_{\theta}(\Lambda)$. Evaluating Eq. 3 is computationally expensive, as multiplication with the eigenvector matrix $U$ is $\mathcal{O}(N^{2})$. Furthermore, computing the eigendecomposition of $L$ in the first place might be prohibitively expensive for large graphs. To circumvent this problem, it was suggested in Hammond et al. 2011 that $g_{\theta}(\Lambda)$ can be well-approximated by a truncated expansion in terms of Chebyshev polynomials $T_{k}(x)$ up to $K^{\text{th}}$ order:

其中$U$是归一化图拉普拉斯$L=I_{N}-D^{-\frac{1}{2}}AD^{-\frac{1}{2}}=U\Lambda U^{\top}$的特征向量矩阵，其特征值$\Lambda$和$U^{\top}x$的对角矩阵是$x$的图傅立叶变换。 我们可以将$g_{\theta}$理解为$L$特征值的函数，即$g_{\theta}(\Lambda)$。 评估方程 3 的计算成本很高，因为与特征向量矩阵$U$的乘法是$\mathcal{O}(N^{2})$。 此外，对于大型图来说，首先计算$L$的特征分解可能会非常昂贵。 为了规避这个问题，Hammond 等人提出了建议。 2011 年，$g_{\theta}(\Lambda)$ 可以通过切比雪夫多项式$T_{k}(x)$到$K^{\text{th}}$阶数的截断展开来很好地近似：

$$g_{\theta^{\prime}}(\Lambda)\approx\sum_{k=0}^{K}\theta_{k}^{\prime}T_{k}(\tilde{\Lambda})\,, \tag{4}$$

with a rescaled $\tilde{\Lambda}=\frac{2}{\lambda_{\text{max}}}\Lambda-I_{N}$. $\lambda_{\text{max}}$ denotes the largest eigenvalue of $L$. $\theta^{\prime}\in\mathbb{R}^{K}$ is now a vector of Chebyshev coefficients. The Chebyshev polynomials are recursively defined as $T_{k}(x)=2xT_{k-1}(x)-T_{k-2}(x)$, with $T_{0}(x)=1$ and $T_{1}(x)=x$. The reader is referred to Hammond et al. 2011 for an in-depth discussion of this approximation.

重新调整后的$\tilde{\Lambda}=\frac{2}{\lambda_{\text{max}}}\Lambda-I_{N}$。$\lambda_{\text{max}}$表示$L$的最大特征值。$\theta^{\prime}\in\mathbb{R}^{K}$现在是切比雪夫系数的向量。 切比雪夫多项式递归定义为$T_{k}(x)=2xT_{k-1}(x)-T_{k-2}(x)$、$T_{0}(x)=1$和$T_{1}(x)=x$。 读者可参考 Hammond 等人。 2011 年对这种近似进行了深入讨论。

Going back to our definition of a convolution of a signal $x$ with a filter $g_{\theta^{\prime}}$, we now have:

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

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

with $\tilde{L}=\frac{2}{\lambda_{\text{max}}}L-I_{N}$; as can easily be verified by noticing that $(U\Lambda U^{\top})^{k}=U\Lambda^{k}U^{\top}$. Note that this expression is now $K$-localized since it is a $K^{\text{th}}$-order polynomial in the Laplacian, i.e. it depends only on nodes that are at maximum $K$ steps away from the central node ($K^{\text{th}}$-order neighborhood). The complexity of evaluating Eq. 5 is $\mathcal{O}(|\mathcal{E}|)$, i.e. linear in the number of edges. Defferrard et al. 2016 use this $K$-localized convolution to define a convolutional neural network on graphs.

与$\tilde{L}=\frac{2}{\lambda_{\text{max}}}L-I_{N}$； 通过注意到$(U\Lambda U^{\top})^{k}=U\Lambda^{k}U^{\top}$可以轻松验证这一点。 请注意，此表达式现在是$K$局部化的，因为它是拉普拉斯中的$K^{\text{th}}$阶多项式，即它仅取决于距中心节点最大$K$步的节点（$K^{\text{th}}$阶邻域）。 评估方程的复杂性。 5 是$\mathcal{O}(|\mathcal{E}|)$，即边数呈线性。 德弗拉德等人。 2016 年使用这个$K$局部卷积来定义图上的卷积神经网络。

2.2 Layer-Wise Linear Model

2.2 层式线性模型

A neural network model based on graph convolutions can therefore be built by stacking multiple convolutional layers of the form of Eq. 5, each layer followed by a point-wise non-linearity. Now, imagine we limited the layer-wise convolution operation to $K=1$ (see Eq. 5), i.e. a function that is linear w.r.t. $L$ and therefore a linear function on the graph Laplacian spectrum.

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

In this way, we can still recover a rich class of convolutional filter functions by stacking multiple such layers, but we are not limited to the explicit parameterization given by, e.g., the Chebyshev polynomials. We intuitively expect that such a model can alleviate the problem of overfitting on local neighborhood structures for graphs with very wide node degree distributions, such as social networks, citation networks, knowledge graphs and many other real-world graph datasets. Additionally, for a fixed computational budget, this layer-wise linear formulation allows us to build deeper models, a practice that is known to improve modeling capacity on a number of domains (He et al. 2016).

通过这种方式，我们仍然可以通过堆叠多个此类层来恢复丰富的卷积滤波器函数类别，但我们不限于由切比雪夫多项式等给出的显式参数化。 我们直观地期望这样的模型可以缓解节点度分布非常宽的图（例如社交网络、引用网络、知识图和许多其他现实世界图数据集）的局部邻域结构过度拟合的问题。 此外，对于固定的计算预算，这种逐层线性公式允许我们构建更深的模型，这种做法众所周知可以提高多个领域的建模能力（He et al. 2016）。

In this linear formulation of a GCN we further approximate $\lambda_{\text{max}}\approx 2$, as we can expect that neural network parameters will adapt to this change in scale during training. Under these approximations Eq. 5 simplifies to:

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

$$g_{\theta^{\prime}}\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}}AD^{-\frac{1}{2}}x\,, \tag{6}$$

with two free parameters $\theta_{0}^{\prime}$ and $\theta_{1}^{\prime}$. The filter parameters can be shared over the whole graph. Successive application of filters of this form then effectively convolve the $k^{\text{th}}$-order neighborhood of a node, where $k$ is the number of successive filtering operations or convolutional layers in the neural network model.

有两个自由参数$\theta_{0}^{\prime}$和$\theta_{1}^{\prime}$。 过滤器参数可以在整个图表上共享。 这种形式的过滤器的连续应用然后有效地对节点的$k^{\text{th}}$阶邻域进行卷积，其中$k$是神经网络模型中连续过滤操作或卷积层的数量。

In practice, it can be beneficial to constrain the number of parameters further to address overfitting and to minimize the number of operations (such as matrix multiplications) per layer. This leaves us with the following expression:

在实践中，进一步限制参数数量以解决过度拟合并最大限度地减少每层的操作（例如矩阵乘法）数量可能是有益的。 这给我们留下了以下表达式：

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

with a single parameter $\theta=\theta_{0}^{\prime}=-\theta_{1}^{\prime}$. Note that $I_{N}+D^{-\frac{1}{2}}AD^{-\frac{1}{2}}$ now has eigenvalues in the range $[0,2]$. Repeated application of this operator can therefore lead to numerical instabilities and exploding/vanishing gradients when used in a deep neural network model. To alleviate this problem, we introduce the following renormalization trick: $I_{N}+D^{-\frac{1}{2}}AD^{-\frac{1}{2}}\rightarrow\tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}$, with $\tilde{A}=A+I_{N}$ and $\tilde{D}_{ii}=\sum_{j}\tilde{A}_{ij}$.

使用单个参数$\theta=\theta_{0}^{\prime}=-\theta_{1}^{\prime}$。 请注意，$I_{N}+D^{-\frac{1}{2}}AD^{-\frac{1}{2}}$现在的特征值在$[0,2]$范围内。 因此，当在深度神经网络模型中使用时，重复应用该算子可能会导致数值不稳定和梯度爆炸/消失。 为了缓解这个问题，我们引入了以下重整化技巧：$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}$。

We can generalize this definition to a signal $X\in\mathbb{R}^{N\times C}$ with $C$ input channels (i.e. a $C$-dimensional feature vector for every node) and $F$ filters or feature maps as follows:

我们可以将此定义推广到具有$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\,, \tag{8}$$

where $\Theta\in\mathbb{R}^{C\times F}$ is now a matrix of filter parameters and $Z\in\mathbb{R}^{N\times F}$ is the convolved signal matrix. This filtering operation has complexity $\mathcal{O}(|\mathcal{E}|FC)$, as $\tilde{A}X$ can be efficiently implemented as a product of a sparse matrix with a dense matrix.

其中$\Theta\in\mathbb{R}^{C\times F}$现在是滤波器参数矩阵，$Z\in\mathbb{R}^{N\times F}$ 是卷积信号矩阵。 此过滤操作的复杂度为$\mathcal{O}(|\mathcal{E}|FC)$，因为$\tilde{A}X$可以有效地实现为稀疏矩阵与稠密矩阵的乘积。

3 Semi-Supervised Node Classification

3 半监督节点分类

Having introduced a simple, yet flexible model $f(X,A)$ for efficient information propagation on graphs, we can return to the problem of semi-supervised node classification. As outlined in the introduction, we can relax certain assumptions typically made in graph-based semi-supervised learning by conditioning our model $f(X,A)$ both on the data $X$ and on the adjacency matrix $A$ of the underlying graph structure. We expect this setting to be especially powerful in scenarios where the adjacency matrix contains information not present in the data $X$, such as citation links between documents in a citation network or relations in a knowledge graph. The overall model, a multi-layer GCN for semi-supervised learning, is schematically depicted in Figure 1.

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

(a) Graph Convolutional Network

(a) 图卷积网络

3.1 Example

3.1 示例

In the following, we consider a two-layer GCN for semi-supervised node classification on a graph with a symmetric adjacency matrix $A$ (binary or weighted). We first calculate $\hat{A}=\tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}$ in a pre-processing step. Our forward model then takes the simple form:

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

$$Z=f(X,A)=\mathrm{softmax}\!\left(\hat{A}\,\,\mathrm{ReLU}\!\left(\hat{A}XW^{(0)}\right)W^{(1)}\right)\,. \tag{9}$$

Here, $W^{(0)}\in\mathbb{R}^{C\times H}$ is an input-to-hidden weight matrix for a hidden layer with $H$ feature maps. $W^{(1)}\in\mathbb{R}^{H\times F}$ is a hidden-to-output weight matrix. The softmax activation function, defined as $\mathrm{softmax}(x_{i})=\frac{1}{\mathcal{Z}}\exp(x_{i})$ with $\mathcal{Z}=\sum_{i}\exp(x_{i})$, is applied row-wise. For semi-supervised multi-class classification, we then evaluate the cross-entropy error over all labeled examples:

这里，$W^{(0)}\in\mathbb{R}^{C\times H}$ 是具有$H$特征图的隐藏层的输入到隐藏权重矩阵。$W^{(1)}\in\mathbb{R}^{H\times F}$是隐藏到输出的权重矩阵。 softmax 激活函数（定义为$\mathrm{softmax}(x_{i})=\frac{1}{\mathcal{Z}}\exp(x_{i})$和$\mathcal{Z}=\sum_{i}\exp(x_{i})$）按行应用。 对于半监督多类分类，我们评估所有标记示例的交叉熵误差：

$$\mathcal{L}=-\sum_{l\in\mathcal{Y}_{L}}\sum_{f=1}^{F}Y_{lf}\ln Z_{lf}\,, \tag{10}$$

where $\mathcal{Y}_{L}$ is the set of node indices that have labels.

其中$\mathcal{Y}_{L}$是具有标签的节点索引集。

The neural network weights $W^{(0)}$ and $W^{(1)}$ are trained using gradient descent. In this work, we perform batch gradient descent using the full dataset for every training iteration, which is a viable option as long as datasets fit in memory. Using a sparse representation for $A$, memory requirement is $\mathcal{O}(|\mathcal{E}|)$, i.e. linear in the number of edges. Stochasticity in the training process is introduced via dropout (Srivastava et al. 2014). We leave memory-efficient extensions with mini-batch stochastic gradient descent for future work.

神经网络权重$W^{(0)}$和$W^{(1)}$使用梯度下降进行训练。 在这项工作中，我们在每次训练迭代中使用完整数据集实现批量梯度下降，只要数据集适合内存，这就是一个可行的选择。 使用$A$的稀疏表示，内存需求为$\mathcal{O}(|\mathcal{E}|)$，即边数呈线性。 训练过程中的随机性是通过 dropout 引入的（Srivastava et al. 2014）。 我们将小批量随机梯度下降的内存高效扩展留给未来的工作。

3.2 Implementation

3.2 实现

In practice, we make use of TensorFlow (Abadi et al. 2015) for an efficient GPU-based implementation[^2] of Eq. 9 using sparse-dense matrix multiplications. The computational complexity of evaluating Eq. 9 is then $\mathcal{O}(|\mathcal{E}|CHF)$, i.e. linear in the number of graph edges.

在实践中，我们利用 TensorFlow（Abadi 等人，2015）对等式进行基于 GPU 的高效实现[^2]。 9 使用稀疏密集矩阵乘法。 评估方程的计算复杂度。 9 则为$\mathcal{O}(|\mathcal{E}|CHF)$，即图边数呈线性。

4 Related Work

4 相关工作

Our model draws inspiration both from the field of graph-based semi-supervised learning and from recent work on neural networks that operate on graphs. In what follows, we provide a brief overview on related work in both fields.

我们的模型从基于图的半监督学习领域和最近在图上运行的神经网络的工作中汲取了灵感。 接下来，我们将简要概述这两个领域的相关工作。

4.1 Graph-Based Semi-Supervised Learning

4.1 基于图的半监督学习

A large number of approaches for semi-supervised learning using graph representations have been proposed in recent years, most of which fall into two broad categories: methods that use some form of explicit graph Laplacian regularization and graph embedding-based approaches. Prominent examples for graph Laplacian regularization include label propagation (Zhu et al. 2003), manifold regularization (Belkin et al. 2006) and deep semi-supervised embedding (Weston et al. 2012).

近年来，人们提出了大量使用图表示的半监督学习方法，其中大多数分为两大类：使用某种形式的显式图拉普拉斯正则化的方法和基于图嵌入的方法。 图拉普拉斯正则化的突出例子包括标签传播（Zhu et al. 2003）、流形正则化（Belkin et al. 2006）和深度半监督嵌入（Weston et al. 2012）。

Recently, attention has shifted to models that learn graph embeddings with methods inspired by the skip-gram model (Mikolov et al. 2013). DeepWalk (Perozzi et al. 2014) learns embeddings via the prediction of the local neighborhood of nodes, sampled from random walks on the graph. LINE (Tang et al. 2015) and node2vec (Grover & Leskovec 2016) extend DeepWalk with more sophisticated random walk or breadth-first search schemes. For all these methods, however, a multi-step pipeline including random walk generation and semi-supervised training is required where each step has to be optimized separately. Planetoid (Yang et al. 2016) alleviates this by injecting label information in the process of learning embeddings.

最近，人们的注意力已经转移到使用受skip-gram模型启发的方法来学习图嵌入的模型（Mikolov et al. 2013）。 DeepWalk（Perozzi et al. 2014）通过预测节点的局部邻域（从图上的随机游走中采样）来学习嵌入。 LINE (Tang et al. 2015) 和 node2vec (Grover & Leskovec 2016) 通过更复杂的随机游走或广度优先搜索方案扩展了 DeepWalk。 然而，对于所有这些方法，都需要包括随机游走生成和半监督训练的多步骤管道，其中每个步骤都必须单独优化。 Planetoid（Yang et al. 2016）通过在学习嵌入的过程中注入标签信息来缓解这一问题。

4.2 Neural Networks on Graphs

4.2 图上的神经网络

Neural networks that operate on graphs have previously been introduced in Gori et al. 2005; Scarselli et al. 2009 as a form of recurrent neural network. Their framework requires the repeated application of contraction maps as propagation functions until node representations reach a stable fixed point. This restriction was later alleviated in Li et al. 2016 by introducing modern practices for recurrent neural network training to the original graph neural network framework. Duvenaud et al. 2015 introduced a convolution-like propagation rule on graphs and methods for graph-level classification. Their approach requires to learn node degree-specific weight matrices which does not scale to large graphs with wide node degree distributions. Our model instead uses a single weight matrix per layer and deals with varying node degrees through an appropriate normalization of the adjacency matrix (see Section 3.1).

Gori 等人之前已经介绍过在图上运行的神经网络。 2005年； 斯卡塞利等人。 2009 年作为循环神经网络的一种形式。 他们的框架需要重复应用收缩图作为传播函数，直到节点表示达到稳定的固定点。 后来 Li 等人放宽了这一限制。 2016 年，将循环神经网络训练的现代实践引入到原始的图神经网络框架中。 杜维诺等人。 2015 年引入了图上的类卷积传播规则和图级分类方法。 他们的方法需要学习特定于节点度的权重矩阵，该矩阵不能扩展到具有宽节点度分布的大图。 相反，我们的模型每层使用一个权重矩阵，并通过邻接矩阵的适当归一化来处理不同的节点度（参见第 3.1 节）。

A related approach to node classification with a graph-based neural network was recently introduced in Atwood & Towsley 2016. They report $\mathcal{O}(N^{2})$ complexity, limiting the range of possible applications. In a different yet related model, Niepert et al. 2016 convert graphs locally into sequences that are fed into a conventional 1D convolutional neural network, which requires the definition of a node ordering in a pre-processing step.

最近在 Atwood & Towsley 2016 中引入了一种使用基于图的神经网络进行节点分类的相关方法。他们报告了$\mathcal{O}(N^{2})$复杂性，限制了可能的应用范围。 在一个不同但相关的模型中，Niepert 等人。 2016 将图本地转换为序列，然后输入传统的一维卷积神经网络，这需要在预处理步骤中定义节点排序。

Our method is based on spectral graph convolutional neural networks, introduced in Bruna et al. 2014 and later extended by Defferrard et al. 2016 with fast localized convolutions. In contrast to these works, we consider here the task of transductive node classification within networks of significantly larger scale. We show that in this setting, a number of simplifications (see Section 2.2) can be introduced to the original frameworks of Bruna et al. 2014 and Defferrard et al. 2016 that improve scalability and classification performance in large-scale networks.

我们的方法基于 Bruna 等人介绍的谱图卷积神经网络。 2014年，后来由Defferrard等人扩展。 2016 年，快速局部卷积。 与这些工作相反，我们在这里考虑在规模明显更大的网络中进行传导节点分类的任务。 我们表明，在这种情况下，可以将许多简化（参见第 2.2 节）引入到 Bruna 等人的原始框架中。 2014 年和德弗拉德等人。 2016 年，提高了大规模网络的可扩展性和分类性能。

5 Experiments

5 实验

We test our model in a number of experiments: semi-supervised document classification in citation networks, semi-supervised entity classification in a bipartite graph extracted from a knowledge graph, an evaluation of various graph propagation models and a run-time analysis on random graphs.

我们在许多实验中测试了我们的模型：引文网络中的半监督文档分类、从知识图谱中提取的二分图中的半监督实体分类、各种图传播模型的评估以及随机图的运行时分析。

5.1 Datasets

5.1 数据集

We closely follow the experimental setup in Yang et al. 2016. Dataset statistics are summarized in Table 1. In the citation network datasets—Citeseer, Cora and Pubmed (Sen et al. 2008)—nodes are documents and edges are citation links. Label rate denotes the number of labeled nodes that are used for training divided by the total number of nodes in each dataset. NELL (Carlson et al. 2010; Yang et al. 2016) is a bipartite graph dataset extracted from a knowledge graph with 55,864 relation nodes and 9,891 entity nodes.

我们密切关注 Yang 等人的实验设置。 2016。表 1 总结了数据集统计数据。在引文网络数据集中——Citeseer、Cora 和 Pubmed（Sen 等人，2008）——节点是文档，边是引文链接。 标签率表示用于训练的标记节点数除以每个数据集中的节点总数。 NELL（Carlson et al. 2010；Yang et al. 2016）是从知识图谱中提取的二部图数据集，有 55,864 个关系节点和 9,891 个实体节点。

Dataset	Type	Nodes	Edges	Classes	Features	Label rate
Citeseer	Citation network	3,327	4,732	$6$	3,703	$0.036$
Cora	Citation network	2,708	5,429	$7$	1,433	$0.052$
Pubmed	Citation network	19,717	44,338	$3$	500	$0.003$
NELL	Knowledge graph	65,755	266,144	$210$	5,414	$0.001$

Table 1: Dataset statistics, as reported in Yang et al. 2016.

数据集	类型	节点	边缘	课程	特征	标签率
西特西尔	引文网	3,327	4,732	$6$	3,703	$0.036$
科拉	引文网	2,708	5,429	$7$	1,433	$0.052$
考研	引文网	19,717	44,338	$3$	500	$0.003$
内尔	知识图谱	65,755	266,144	$210$	5,414	$0.001$

表 1：数据集统计数据，如 Yang 等人报告的那样。 2016年。

Citation networks

We consider three citation network datasets: Citeseer, Cora and Pubmed (Sen et al. 2008). The datasets contain sparse bag-of-words feature vectors for each document and a list of citation links between documents. We treat the citation links as (undirected) edges and construct a binary, symmetric adjacency matrix $A$. Each document has a class label. For training, we only use 20 labels per class, but all feature vectors.

引文网络

我们考虑三个引文网络数据集：Citeseer、Cora 和 Pubmed（Sen 等人，2008 年）。 数据集包含每个文档的稀疏词袋特征向量以及文档之间的引用链接列表。 我们将引用链接视为（无向）边并构造一个二元对称邻接矩阵$A$。 每个文档都有一个类标签。 对于训练，我们每个类仅使用 20 个标签，但全部是特征向量。

NELL

NELL is a dataset extracted from the knowledge graph introduced in (Carlson et al. 2010). A knowledge graph is a set of entities connected with directed, labeled edges (relations). We follow the pre-processing scheme as described in Yang et al. 2016. We assign separate relation nodes $r_{1}$ and $r_{2}$ for each entity pair $(e_{1},r,e_{2})$ as $(e_{1},r_{1})$ and $(e_{2},r_{2})$. Entity nodes are described by sparse feature vectors. We extend the number of features in NELL by assigning a unique one-hot representation for every relation node, effectively resulting in a 61,278-dim sparse feature vector per node. The semi-supervised task here considers the extreme case of only a single labeled example per class in the training set. We construct a binary, symmetric adjacency matrix from this graph by setting entries $A_{ij}=1$, if one or more edges are present between nodes $i$ and $j$.

内尔

NELL 是从（Carlson et al. 2010）中引入的知识图谱中提取的数据集。 知识图是一组通过有向、标记的边（关系）连接的实体。 我们遵循 Yang 等人中描述的预处理方案。 2016。我们为每个实体对$(e_{1},r,e_{2})$分配单独的关系节点$r_{1}$和$r_{2}$作为$(e_{1},r_{1})$和$(e_{2},r_{2})$。 实体节点由稀疏特征向量描述。 我们通过为每个关系节点分配唯一的 one-hot 表示来扩展 NELL 中的特征数量，从而有效地为每个节点生成 61,278 维的稀疏特征向量。 这里的半监督任务考虑了训练集中每个类只有一个标记示例的极端情况。 如果节点$i$和$j$之间存在一条或多条边，我们通过设置条目$A_{ij}=1$从此图构建二元对称邻接矩阵。

Random graphs

We simulate random graph datasets of various sizes for experiments where we measure training time per epoch. For a dataset with $N$ nodes we create a random graph assigning $2N$ edges uniformly at random. We take the identity matrix $I_{N}$ as input feature matrix $X$, thereby implicitly taking a featureless approach where the model is only informed about the identity of each node, specified by a unique one-hot vector. We add dummy labels $Y_{i}=1$ for every node.

随机图

我们模拟各种大小的随机图数据集进行实验，测量每个时期的训练时间。 对于具有$N$节点的数据集，我们创建一个随机图，随机均匀分配$2N$边。 我们将单位矩阵$I_{N}$作为输入特征矩阵$X$，从而隐式地采用一种无特征方法，其中模型仅了解由唯一的 one-hot 向量指定的每个节点的身份。 我们为每个节点添加虚拟标签 $Y_{i}=1$。

5.2 Experimental Set-Up

5.2 实验设置

Unless otherwise noted, we train a two-layer GCN as described in Section 3.1 and evaluate prediction accuracy on a test set of 1,000 labeled examples. We provide additional experiments using deeper models with up to 10 layers in Appendix B. We choose the same dataset splits as in Yang et al. 2016 with an additional validation set of 500 labeled examples for hyperparameter optimization (dropout rate for all layers, L2 regularization factor for the first GCN layer and number of hidden units). We do not use the validation set labels for training.

除非另有说明，我们按照 3.1 节中的描述训练一个两层 GCN，并在 1,000 个标记示例的测试集上评估预测准确性。 我们在附录 B 中提供了使用最多 10 层的更深模型的额外实验。我们选择与 Yang 等人相同的数据集分割。 2016 年，额外的验证集包含 500 个用于超参数优化的标记示例（所有层的丢弃率、第一个 GCN 层的 L2 正则化因子以及隐藏单元的数量）。 我们不使用验证集标签进行训练。

For the citation network datasets, we optimize hyperparameters on Cora only and use the same set of parameters for Citeseer and Pubmed. We train all models for a maximum of 200 epochs (training iterations) using Adam (Kingma & Ba 2015) with a learning rate of $0.01$ and early stopping with a window size of $10$, i.e. we stop training if the validation loss does not decrease for 10 consecutive epochs. We initialize weights using the initialization described in Glorot & Bengio 2010 and accordingly (row-)normalize input feature vectors. On the random graph datasets, we use a hidden layer size of 32 units and omit regularization (i.e. neither dropout nor L2 regularization).

对于引文网络数据集，我们仅在 Cora 上优化超参数，并为 Citeseer 和 Pubmed 使用相同的参数集。 我们使用 Adam (Kingma & Ba 2015) 训练所有模型，学习率为$0.01$，并以$10$的窗口大小提前停止，即如果验证损失在 10 个连续的 epoch 内没有减少，我们将停止训练。 我们使用 Glorot & Bengio 2010 中描述的初始化来初始化权重，并相应地对输入特征向量进行（行）归一化。 在随机图数据集上，我们使用 32 个单位的隐藏层大小并省略正则化（即既不丢失也不进行 L2 正则化）。

5.3 Baselines

5.3 基线

We compare against the same baseline methods as in Yang et al. 2016, i.e. label propagation (LP) (Zhu et al. 2003), semi-supervised embedding (SemiEmb) (Weston et al. 2012), manifold regularization (ManiReg) (Belkin et al. 2006) and skip-gram based graph embeddings (DeepWalk) (Perozzi et al. 2014). We omit TSVM (Joachims 1999), as it does not scale to the large number of classes in one of our datasets.

我们与 Yang 等人的相同基线方法进行比较。 2016，即标签传播（LP）（Zhu et al. 2003）、半监督嵌入（SemiEmb）（Weston et al. 2012）、流形正则化（ManiReg）（Belkin et al. 2006）和基于skip-gram的图嵌入（DeepWalk）（Perozzi et al. 2014）。 我们省略了 TSVM (Joachims 1999)，因为它无法扩展到我们的数据集中的大量类。

We further compare against the iterative classification algorithm (ICA) proposed in Lu & Getoor 2003 in conjunction with two logistic regression classifiers, one for local node features alone and one for relational classification using local features and an aggregation operator as described in Sen et al. 2008. We first train the local classifier using all labeled training set nodes and use it to bootstrap class labels of unlabeled nodes for relational classifier training. We run iterative classification (relational classifier) with a random node ordering for 10 iterations on all unlabeled nodes (bootstrapped using the local classifier). L2 regularization parameter and aggregation operator (count vs. prop, see Sen et al. 2008) are chosen based on validation set performance for each dataset separately.

我们进一步将 Lu & Getoor 2003 中提出的迭代分类算法 (ICA) 与两种逻辑回归分类器相结合进行比较，一种仅用于局部节点特征，另一种用于使用局部特征和聚合算子的关系分类，如 Sen 等人所述。 2008年。我们首先使用所有标记的训练集节点来训练局部分类器，并使用它来引导未标记节点的类标签以进行关系分类器训练。 我们使用随机节点排序运行迭代分类（关系分类器），在所有未标记节点上进行 10 次迭代（使用本地分类器引导）。 L2 正则化参数和聚合运算符（count 与 prop，参见 Sen 等人，2008）是根据每个数据集的验证集性能分别选择的。

Lastly, we compare against Planetoid (Yang et al. 2016), where we always choose their best-performing model variant (transductive vs. inductive) as a baseline.

最后，我们与 Planetoid 进行比较（Yang et al. 2016），我们总是选择他们表现最好的模型变体（传导与感应）作为基线。

6 Results

6 结果

6.1 Semi-Supervised Node Classification

6.1 半监督节点分类

Results are summarized in Table 2. Reported numbers denote classification accuracy in percent. For ICA, we report the mean accuracy of 100 runs with random node orderings. Results for all other baseline methods are taken from the Planetoid paper (Yang et al. 2016). Planetoid* denotes the best model for the respective dataset out of the variants presented in their paper.

结果总结于表 2 中。报告的数字表示分类准确度（以百分比表示）。 对于 ICA，我们报告了 100 次随机节点排序运行的平均准确度。 所有其他基线方法的结果均取自 Planetoid 论文（Yang 等人，2016 年）。 Planetoid* 表示论文中提出的变体中各个数据集的最佳模型。

Method	Citeseer	Cora	Pubmed	NELL
ManiReg [[3]]	$60.1$	$59.5$	$70.7$	$21.8$
SemiEmb [[28]]	$59.6$	$59.0$	$71.1$	$26.7$
LP [[32]]	$45.3$	$68.0$	$63.0$	$26.5$
DeepWalk [[22]]	$43.2$	$67.2$	$65.3$	$58.1$
ICA [[18]]	$69.1$	$75.1$	$73.9$	$23.1$
Planetoid* [[29]]	$64.7$ (26s)	$75.7$ (13s)	$77.2$ (25s)	$61.9$ (185s)
GCN (this paper)	$\mathbf{70.3}$ (7s)	$\mathbf{81.5}$ (4s)	$\mathbf{79.0}$ (38s)	$\mathbf{66.0}$ (48s)
GCN (rand. splits)	$67.9\pm 0.5$	$80.1\pm 0.5$	$78.9\pm 0.7$	$58.4\pm 1.7$

Table 2: Summary of results in terms of classification accuracy (in percent).

方法	Citeseer	Cora	Pubmed	NELL
ManiReg [[3]]	$60.1$	$59.5$	$70.7$	$21.8$
SemiEmb [[28]]	$59.6$	$59.0$	$71.1$	$26.7$
LP [[32]]	$45.3$	$68.0$	$63.0$	$26.5$
DeepWalk [[22]]	$43.2$	$67.2$	$65.3$	$58.1$
ICA [[18]]	$69.1$	$75.1$	$73.9$	$23.1$
Planetoid* [[29]]	$64.7$ (26s)	$75.7$ (13s)	$77.2$ (25s)	$61.9$ (185s)
GCN（本文）	$\mathbf{70.3}$ (7s)	$\mathbf{81.5}$ (4s)	$\mathbf{79.0}$ (38s)	$\mathbf{66.0}$ (48s)
GCN（随机划分）	$67.9\pm 0.5$	$80.1\pm 0.5$	$78.9\pm 0.7$	$58.4\pm 1.7$

表 2：分类准确率（百分比）汇总。

We further report wall-clock training time in seconds until convergence (in brackets) for our method (incl. evaluation of validation error) and for Planetoid. For the latter, we used an implementation provided by the authors[^3] and trained on the same hardware (with GPU) as our GCN model. We trained and tested our model on the same dataset splits as in Yang et al. 2016 and report mean accuracy of 100 runs with random weight initializations. We used the following sets of hyperparameters for Citeseer, Cora and Pubmed: 0.5 (dropout rate), $5\cdot 10^{-4}$ (L2 regularization) and $16$ (number of hidden units); and for NELL: 0.1 (dropout rate), $1\cdot 10^{-5}$ (L2 regularization) and $64$ (number of hidden units).

我们进一步报告了我们的方法（包括验证错误的评估）和 Planetoid 的收敛（括号中）之前的挂钟训练时间（以秒为单位）。 对于后者，我们使用了作者 [^3] 提供的实现，并在与我们的 GCN 模型相同的硬件（带有 GPU）上进行训练。 我们在与 Yang 等人相同的数据集分割上训练和测试了我们的模型。 2016 年并报告了随机权重初始化的 100 次运行的平均准确度。 我们为 Citeseer、Cora 和 Pubmed 使用了以下超参数集：0.5（丢失率）、$5\cdot 10^{-4}$（L2 正则化）和 $16$（隐藏单元数量）； 对于 NELL：0.1（丢失率）、$1\cdot 10^{-5}$（L2 正则化）和 $64$（隐藏单元数）。

In addition, we report performance of our model on 10 randomly drawn dataset splits of the same size as in Yang et al. 2016, denoted by GCN (rand. splits). Here, we report mean and standard error of prediction accuracy on the test set split in percent.

此外，我们报告了我们的模型在 10 个随机抽取的数据集分割上的性能，这些分割的大小与 Yang 等人的大小相同。 2016，用 GCN（rand. splits）表示。 在这里，我们以百分比报告测试集预测准确性的平均值和标准误差。

6.2 Evaluation of Propagation Model

6.2 评估传播模型

We compare different variants of our proposed per-layer propagation model on the citation network datasets. We follow the experimental set-up described in the previous section. Results are summarized in Table 3. The propagation model of our original GCN model is denoted by renormalization trick (in bold). In all other cases, the propagation model of both neural network layers is replaced with the model specified under propagation model. Reported numbers denote mean classification accuracy for 100 repeated runs with random weight matrix initializations. In case of multiple variables $\Theta_{i}$ per layer, we impose L2 regularization on all weight matrices of the first layer.

我们在引文网络数据集上比较了我们提出的每层传播模型的不同变体。 我们遵循上一节中描述的实验设置。 结果总结在表 3 中。我们原始 GCN 模型的传播模型由重整化技巧（粗体）表示。 在所有其他情况下，两个神经网络层的传播模型都替换为传播模型下指定的模型。 报告的数字表示随机权重矩阵初始化的 100 次重复运行的平均分类精度。 如果每层有多个变量 $\Theta_{i}$，我们对第一层的所有权重矩阵进行 L2 正则化。

Description		Propagation model	Citeseer	Cora	Pubmed
Chebyshev filter (Eq. 5)	$K=3$	$\sum_{k=0}^{K}T_{k}(\tilde{L})X\Theta_{k}$	$69.8$	$79.5$	$74.4$
$K=2$	$69.6$	$81.2$	$73.8$
$1^{\text{st}}$-order model (Eq. 6)	$X\Theta_{0}+D^{-\frac{1}{2}}AD^{-\frac{1}{2}}X\Theta_{1}$	$68.3$	$80.0$	$77.5$
Single parameter (Eq. 7)	$(I_{N}+D^{-\frac{1}{2}}AD^{-\frac{1}{2}})X\Theta$	$69.3$	$79.2$	$77.4$
Renormalization trick (Eq. 8)	$\tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}X\Theta$	$\mathbf{70.3}$	$\mathbf{81.5}$	$\mathbf{79.0}$
$1^{\text{st}}$-order term only	$D^{-\frac{1}{2}}AD^{-\frac{1}{2}}X\Theta$	$68.7$	$80.5$	$77.8$
Multi-layer perceptron	$X\Theta$	$46.5$	$55.1$	$71.4$

Table 3: Comparison of propagation models.

描述		传播模型	Citeseer	科拉	已发表
切比雪夫滤波器（方程 5）	$K=3$	$\sum_{k=0}^{K}T_{k}(\tilde{L})X\Theta_{k}$	$69.8$	$79.5$	$74.4$
$K=2$	$69.6$	$81.2$	$73.8$
$1^{\text{st}}$ 阶模型（方程 6）	$X\Theta_{0}+D^{-\frac{1}{2}}AD^{-\frac{1}{2}}X\Theta_{1}$	$68.3$	$80.0$	$77.5$
单参数（方程 7）	$(I_{N}+D^{-\frac{1}{2}}AD^{-\frac{1}{2}})X\Theta$	$69.3$	$79.2$	$77.4$
重整化技巧（等式 8）	$\tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}X\Theta$	$\mathbf{70.3}$	$\mathbf{81.5}$	$\mathbf{79.0}$
$1^{\text{st}}$ - 仅限订单条款	$D^{-\frac{1}{2}}AD^{-\frac{1}{2}}X\Theta$	$68.7$	$80.5$	$77.8$
多层感知器	$X\Theta$	$46.5$	$55.1$	$71.4$

表 3：传播模型的比较。

6.3 Training Time per Epoch

6.3 训练时间

Figure 2: Wall-clock time per epoch for random graphs. (*) indicates out-of-memory error.

图 2：随机图每个时期的挂钟时间。 (*) 表示内存不足错误。

Here, we report results for the mean training time per epoch (forward pass, cross-entropy calculation, backward pass) for 100 epochs on simulated random graphs, measured in seconds wall-clock time. See Section 5.1 for a detailed description of the random graph dataset used in these experiments. We compare results on a GPU and on a CPU-only implementation[^4] in TensorFlow (Abadi et al. 2015). Figure 2 summarizes the results.

在这里，我们报告了模拟随机图上 100 个时期的每个时期的平均训练时间（前向传播、交叉熵计算、后向传播）的结果，以秒挂钟时间为单位。 有关这些实验中使用的随机图数据集的详细描述，请参阅第 5.1 节。 我们比较了 TensorFlow 中 GPU 和仅 CPU 实现 [^4] 的结果（Abadi 等人，2015）。 图 2 总结了结果。

7 Discussion

7 讨论

7.1 Semi-Supervised Model

7.1 半监督模型

In the experiments demonstrated here, our method for semi-supervised node classification outperforms recent related methods by a significant margin. Methods based on graph-Laplacian regularization (Zhu et al. 2003; Belkin et al. 2006; Weston et al. 2012) are most likely limited due to their assumption that edges encode mere similarity of nodes. Skip-gram based methods on the other hand are limited by the fact that they are based on a multi-step pipeline which is difficult to optimize. Our proposed model can overcome both limitations, while still comparing favorably in terms of efficiency (measured in wall-clock time) to related methods. Propagation of feature information from neighboring nodes in every layer improves classification performance in comparison to methods like ICA (Lu & Getoor 2003), where only label information is aggregated.

在这里演示的实验中，我们的半监督节点分类方法明显优于最近的相关方法。 基于图拉普拉斯正则化的方法（Zhu et al. 2003；Belkin et al. 2006；Weston et al. 2012）很可能受到限制，因为它们假设边缘仅编码节点的相似性。 另一方面，基于 Skip-gram 的方法受到以下事实的限制：它们基于难以优化的多步骤管道。 我们提出的模型可以克服这两个限制，同时在效率（以挂钟时间测量）方面仍然优于相关方法。 与仅聚合标签信息的 ICA (Lu & Getoor 2003) 等方法相比，从每一层的相邻节点传播特征信息可以提高分类性能。

We have further demonstrated that the proposed renormalized propagation model (Eq. 8) offers both improved efficiency (fewer parameters and operations, such as multiplication or addition) and better predictive performance on a number of datasets compared to a naïve $1^{\text{st}}$-order model (Eq. 6) or higher-order graph convolutional models using Chebyshev polynomials (Eq. 5).

我们进一步证明，与朴素的$1^{\text{st}}$阶模型（方程 6）或使用切比雪夫多项式的高阶图卷积模型（方程 5）相比，所提出的重正化传播模型（方程 8）在多个数据集上提供了更高的效率（更少的参数和运算，例如乘法或加法）和更好的预测性能。

7.2 Limitations and Future Work

7.2 局限与未来工作

Here, we describe several limitations of our current model and outline how these might be overcome in future work.

在这里，我们描述了当前模型的一些局限性，并概述了如何在未来的工作中克服这些局限性。

Memory requirement

In the current setup with full-batch gradient descent, memory requirement grows linearly in the size of the dataset. We have shown that for large graphs that do not fit in GPU memory, training on CPU can still be a viable option. Mini-batch stochastic gradient descent can alleviate this issue. The procedure of generating mini-batches, however, should take into account the number of layers in the GCN model, as the $K^{\text{th}}$-order neighborhood for a GCN with $K$ layers has to be stored in memory for an exact procedure. For very large and densely connected graph datasets, further approximations might be necessary.

内存要求

在当前的全批量梯度下降设置中，内存需求随着数据集的大小线性增长。 我们已经证明，对于 GPU 内存无法容纳的大型图，在 CPU 上进行训练仍然是一个可行的选择。 小批量随机梯度下降可以缓解这个问题。 然而，生成小批量的过程应该考虑 GCN 模型中的层数，因为具有$K$层的 GCN 的$K^{\text{th}}$阶邻域必须存储在内存中以实现精确的过程。 对于非常大且紧密连接的图形数据集，可能需要进一步的近似。

Directed edges and edge features

Our framework currently does not naturally support edge features and is limited to undirected graphs (weighted or unweighted). Results on NELL however show that it is possible to handle both directed edges and edge features by representing the original directed graph as an undirected bipartite graph with additional nodes that represent edges in the original graph (see Section 5.1 for details).

有向边和边特征

我们的框架目前并不自然支持边缘特征，并且仅限于无向图（加权或未加权）。 然而，NELL 上的结果表明，可以通过将原始有向图表示为无向二部图，并使用表示原始图中边的附加节点来处理有向边和边特征（详细信息请参见第 5.1 节）。

Limiting assumptions

Through the approximations introduced in Section 2, we implicitly assume locality (dependence on the $K^{\text{th}}$-order neighborhood for a GCN with $K$ layers) and equal importance of self-connections vs. edges to neighboring nodes. For some datasets, however, it might be beneficial to introduce a trade-off parameter $\lambda$ in the definition of $\tilde{A}$:

限制性假设

通过第 2 节中介绍的近似，我们隐含地假设局部性（依赖于具有$K$层的 GCN 的$K^{\text{th}}$阶邻域）以及自连接与相邻节点的边的同等重要性。 然而，对于某些数据集，在$\tilde{A}$的定义中引入权衡参数$\lambda$可能会有所帮助：

$$\tilde{A}=A+\lambda I_{N}\,. \tag{11}$$

This parameter now plays a similar role as the trade-off parameter between supervised and unsupervised loss in the typical semi-supervised setting (see Eq. 1). Here, however, it can be learned via gradient descent.

该参数现在起着与典型半监督设置中监督和无监督损失之间的权衡参数类似的作用（参见方程 1）。 然而，在这里，它可以通过梯度下降来学习。

8 Conclusion

8 结论

We have introduced a novel approach for semi-supervised classification on graph-structured data. Our GCN model uses an efficient layer-wise propagation rule that is based on a first-order approximation of spectral convolutions on graphs. Experiments on a number of network datasets suggest that the proposed GCN model is capable of encoding both graph structure and node features in a way useful for semi-supervised classification. In this setting, our model outperforms several recently proposed methods by a significant margin, while being computationally efficient.

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

Acknowledgments

We would like to thank Christos Louizos, Taco Cohen, Joan Bruna, Zhilin Yang, Dave Herman, Pramod Sinha and Abdul-Saboor Sheikh for helpful discussions. This research was funded by SAP.

致谢

我们要感谢 Christos Louizos、Taco Cohen、Joan Bruna、Zhilin Yang、Dave Herman、Pramod Sinha 和 Abdul-Saboor Sheikh 进行的有益讨论。 这项研究由 SAP 资助。

References

参考文献

Abadi et al. (2015) Martín Abadi et al. TensorFlow: Large-scale machine learning on heterogeneous systems, 2015.

Atwood & Towsley (2016) James Atwood and Don Towsley. Diffusion-convolutional neural networks. In Advances in neural information processing systems (NIPS) , 2016.

Belkin et al. (2006) Mikhail Belkin, Partha Niyogi, and Vikas Sindhwani. Manifold regularization: A geometric framework for learning from labeled and unlabeled examples. Journal of machine learning research (JMLR) , 7(Nov):2399–2434, 2006.

Brandes et al. (2008) Ulrik Brandes, Daniel Delling, Marco Gaertler, Robert Gorke, Martin Hoefer, Zoran Nikoloski, and Dorothea Wagner. On modularity clustering. IEEE Transactions on Knowledge and Data Engineering , 20(2):172–188, 2008.

Bruna et al. (2014) Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. In International Conference on Learning Representations (ICLR) , 2014.

Carlson et al. (2010) Andrew Carlson, Justin Betteridge, Bryan Kisiel, Burr Settles, Estevam R. Hruschka Jr, and Tom M. Mitchell. Toward an architecture for never-ending language learning. In AAAI , volume 5, pp. 3, 2010.

Defferrard et al. (2016) Michaë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.

Douglas (2011) Brendan L. Douglas. The Weisfeiler-Lehman method and graph isomorphism testing. arXiv preprint arXiv:1101.5211 , 2011.

Duvenaud et al. (2015) David K. Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aspuru-Guzik, and Ryan P. Adams. Convolutional networks on graphs for learning molecular fingerprints. In Advances in neural information processing systems (NIPS) , pp. 2224–2232, 2015.

Glorot & Bengio (2010) Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In AISTATS , volume 9, pp. 249–256, 2010.

Gori et al. (2005) Marco Gori, Gabriele Monfardini, and Franco Scarselli. A new model for learning in graph domains. In Proceedings. 2005 IEEE International Joint Conference on Neural Networks. , volume 2, pp. 729–734. IEEE, 2005.

Grover & Leskovec (2016) Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining . ACM, 2016.

Hammond et al. (2011) David K. Hammond, Pierre Vandergheynst, and Rémi Gribonval. Wavelets on graphs via spectral graph theory. Applied and Computational Harmonic Analysis , 30(2):129–150, 2011.

He et al. (2016) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR) , 2016.

Joachims (1999) Thorsten Joachims. Transductive inference for text classification using support vector machines. In International Conference on Machine Learning (ICML) , volume 99, pp. 200–209, 1999.

Kingma & Ba (2015) Diederik P. Kingma and Jimmy Lei Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations (ICLR) , 2015.

Li et al. (2016) Yujia Li, Daniel Tarlow, Marc Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. In International Conference on Learning Representations (ICLR) , 2016.

Lu & Getoor (2003) Qing Lu and Lise Getoor. Link-based classification. In International Conference on Machine Learning (ICML) , volume 3, pp. 496–503, 2003.

Maaten & Hinton (2008) Laurens van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of Machine Learning Research (JMLR) , 9(Nov):2579–2605, 2008.

Mikolov et al. (2013) Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S. Corrado, and Jeff Dean. Distributed representations of words and phrases and their compositionality. In Advances in neural information processing systems (NIPS) , pp. 3111–3119, 2013.

Niepert et al. (2016) Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning convolutional neural networks for graphs. In International Conference on Machine Learning (ICML) , 2016.

Perozzi et al. (2014) Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining , pp. 701–710. ACM, 2014.

Scarselli et al. (2009) Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks , 20(1):61–80, 2009.

Sen et al. (2008) Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. AI magazine , 29(3):93, 2008.

Srivastava et al. (2014) Nitish Srivastava, Geoffrey E. Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: a simple way to prevent neural networks from overfitting. Journal of Machine Learning Research (JMLR) , 15(1):1929–1958, 2014.

Tang et al. (2015) Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. Line: Large-scale information network embedding. In Proceedings of the 24th International Conference on World Wide Web , pp. 1067–1077. ACM, 2015.

Weisfeiler & Lehmann (1968) Boris Weisfeiler and A. A. Lehmann. A reduction of a graph to a canonical form and an algebra arising during this reduction. Nauchno-Technicheskaya Informatsia , 2(9):12–16, 1968.

Weston et al. (2012) Jason Weston, Frédéric Ratle, Hossein Mobahi, and Ronan Collobert. Deep learning via semi-supervised embedding. In Neural Networks: Tricks of the Trade , pp. 639–655. Springer, 2012.

Yang et al. (2016) Zhilin Yang, William Cohen, and Ruslan Salakhutdinov. Revisiting semi-supervised learning with graph embeddings. In International Conference on Machine Learning (ICML) , 2016.

Zachary (1977) Wayne W. Zachary. An information flow model for conflict and fission in small groups. Journal of anthropological research , pp. 452–473, 1977.

Zhou et al. (2004) Dengyong Zhou, Olivier Bousquet, Thomas Navin Lal, Jason Weston, and Bernhard Schölkopf. Learning with local and global consistency. In Advances in neural information processing systems (NIPS) , volume 16, pp. 321–328, 2004.

Zhu et al. (2003) Xiaojin Zhu, Zoubin Ghahramani, and John Lafferty. Semi-supervised learning using gaussian fields and harmonic functions. In International Conference on Machine Learning (ICML) , volume 3, pp. 912–919, 2003.

Appendix A Relation to Weisfeiler-Lehman Algorithm

附录 A 与 Weisfeiler-Lehman 算法的关系

A neural network model for graph-structured data should ideally be able to learn representations of nodes in a graph, taking both the graph structure and feature description of nodes into account. A well-studied framework for the unique assignment of node labels given a graph and (optionally) discrete initial node labels is provided by the 1-dim Weisfeiler-Lehman (WL-1) algorithm (Weisfeiler & Lehmann 1968):

理想情况下，图结构数据的神经网络模型应该能够学习图中节点的表示，同时考虑节点的图结构和特征描述。 1-dim Weisfeiler-Lehman (WL-1) 算法提供了一个经过充分研究的框架，用于在给定图和（可选）离散初始节点标签的情况下对节点标签进行唯一分配（Weisfeiler & Lehmann 1968）：

Input: Initial node coloring $(h^{(0)}_{1},h^{(0)}_{2},...,h^{(0)}_{N})$
Output: Final node coloring $(h^{(T)}_{1},h^{(T)}_{2},...,h^{(T)}_{N})$
t $\leftarrow$ 0;
repeat
for $v_{i}\in\mathcal{V}$ do
$h^{(t+1)}_{i}\leftarrow\mathrm{hash}\left(\sum_{j\in\mathcal{N}_{i}}h^{(t)}_{j}\right)$;
$t\leftarrow t+1$;
until stable node coloring is reached;

Algorithm 1 WL-1 algorithm (Weisfeiler & Lehmann 1968)

输入： 初始节点着色 $(h^{(0)}_{1},h^{(0)}_{2},...,h^{(0)}_{N})$
输出： 最终节点着色 $(h^{(T)}_{1},h^{(T)}_{2},...,h^{(T)}_{N})$
t XX数学2XX 0；
重复
对于 $v_{i}\in\mathcal{V}$ 做
XX数学4XX；
XX数学5XX；
直到 达到稳定的节点着色；

算法 1 WL-1 算法（Weisfeiler & Lehmann 1968）

Here, $h_{i}^{(t)}$ denotes the coloring (label assignment) of node $v_{i}$ (at iteration $t$) and $\mathcal{N}_{i}$ is its set of neighboring node indices (irrespective of whether the graph includes self-connections for every node or not). $\mathrm{hash}(\cdot)$ is a hash function. For an in-depth mathematical discussion of the WL-1 algorithm see, e.g., Douglas 2011.

这里，$h_{i}^{(t)}$表示节点$v_{i}$（在迭代$t$时）的着色（标签分配），$\mathcal{N}_{i}$ 是其相邻节点索引集（无论图中是否包含每个节点的自连接）。$\mathrm{hash}(\cdot)$是一个哈希函数。 有关 WL-1 算法的深入数学讨论，请参阅 Douglas 2011。

We can replace the hash function in Algorithm 1 with a neural network layer-like differentiable function with trainable parameters as follows:

我们可以将算法 1 中的哈希函数替换为具有可训练参数的神经网络层状可微函数，如下所示：

$$h^{(l+1)}_{i}=\sigma\left(\sum_{j\in\mathcal{N}_{i}}\frac{1}{c_{ij}}h^{(l)}_{j}W^{(l)}\right)\,, \tag{12}$$

where $c_{ij}$ is an appropriately chosen normalization constant for the edge $(v_{i},v_{j})$. Further, we can take $h^{(l)}_{i}$ now to be a vector of activations of node $i$ in the $l^{\text{th}}$ neural network layer. $W^{(l)}$ is a layer-specific weight matrix and $\sigma(\cdot)$ denotes a differentiable, non-linear activation function.

其中$c_{ij}$是为边$(v_{i},v_{j})$适当选择的归一化常数。 此外，我们现在可以将$h^{(l)}_{i}$视为$l^{\text{th}}$神经网络层中节点$i$的“激活”向量。$W^{(l)}$是特定于层的权重矩阵，$\sigma(\cdot)$ 表示可微的非线性激活函数。

By choosing $c_{ij}=\sqrt{d_{i}d_{j}}$, where $d_{i}=|\mathcal{N}_{i}|$ denotes the degree of node $v_{i}$, we recover the propagation rule of our Graph Convolutional Network (GCN) model in vector form (see Eq. 2)[^5].

通过选择$c_{ij}=\sqrt{d_{i}d_{j}}$，其中$d_{i}=|\mathcal{N}_{i}|$表示节点$v_{i}$的度数，我们以向量形式恢复图卷积网络（GCN）模型的传播规则（参见方程 2）[^5]。

This—loosely speaking—allows us to interpret our GCN model as a differentiable and parameterized generalization of the 1-dim Weisfeiler-Lehman algorithm on graphs.

宽松地说，这使我们能够将 GCN 模型解释为图上 1 维 Weisfeiler-Lehman 算法的可微分和参数化泛化。

A.1 Node Embeddings with Random Weights

A.1 节点嵌入的随机初始化权重

From the analogy with the Weisfeiler-Lehman algorithm, we can understand that even an untrained GCN model with random weights can serve as a powerful feature extractor for nodes in a graph. As an example, consider the following 3-layer GCN model:

通过与 Weisfeiler-Lehman 算法的类比，我们可以理解，即使是未经训练的具有随机权重的 GCN 模型也可以作为图中节点的强大特征提取器。 作为示例，请考虑以下 3 层 GCN 模型：

$$Z=\tanh\!\left(\hat{A}\,\tanh\!\left(\hat{A}\,\tanh\!\left(\hat{A}XW^{(0)}\right)W^{(1)}\right)W^{(2)}\right)\,, \tag{13}$$

with weight matrices $W^{(l)}$ initialized at random using the initialization described in Glorot & Bengio 2010. $\hat{A}$, $X$ and $Z$ are defined as in Section 3.1.

使用 Glorot & Bengio 2010 中描述的初始化随机初始化权重矩阵 $W^{(l)}$。$\hat{A}$、$X$和$Z$的定义如第 3.1 节中所述。

We apply this model on Zachary’s karate club network (Zachary 1977). This graph contains 34 nodes, connected by 154 (undirected and unweighted) edges. Every node is labeled by one of four classes, obtained via modularity-based clustering (Brandes et al. 2008). See Figure 3(a) for an illustration.

我们将此模型应用于 Zachary 的空手道俱乐部网络（Zachary 1977）。 该图包含 34 个节点，由 154 条（无向且未加权）边连接。 每个节点都由四个类别之一进行标记，这些类别是通过基于模块化的聚类获得的（Brandes 等人，2008 年）。 参见图 3(a) 的说明。

(a) Karate club network

(a) 空手道俱乐部网络

We take a featureless approach by setting $X=I_{N}$, where $I_{N}$ is the $N$ by $N$ identity matrix. $N$ is the number of nodes in the graph. Note that nodes are randomly ordered (i.e. ordering contains no information). Furthermore, we choose a hidden layer dimensionality[^6] of $4$ and a two-dimensional output (so that the output can immediately be visualized in a 2-dim plot).

我们通过设置$X=I_{N}$来采取无特征的方法，其中$I_{N}$是$N$×$N$单位矩阵。$N$是图中的节点数。 请注意，节点是随机排序的（即排序不包含信息）。 此外，我们选择$4$的隐藏层维度 [^6] 和二维输出（以便输出可以立即在 2 维图中可视化）。

Figure 3(b) shows a representative example of node embeddings (outputs $Z$) obtained from an untrained GCN model applied to the karate club network. These results are comparable to embeddings obtained from DeepWalk (Perozzi et al. 2014), which uses a more expensive unsupervised training procedure.

图 3(b) 显示了从应用于空手道俱乐部网络的未经训练的 GCN 模型获得的节点嵌入（输出$Z$）的代表性示例。 这些结果与 DeepWalk（Perozzi 等人，2014）获得的嵌入相当，后者使用更昂贵的无监督训练程序。

A.2 Semi-Supervised Node Embeddings

A.2 半监督节点嵌入

On this simple example of a GCN applied to the karate club network it is interesting to observe how embeddings react during training on a semi-supervised classification task. Such a visualization (see Figure 4) provides insights into how the GCN model can make use of the graph structure (and of features extracted from the graph structure at later layers) to learn embeddings that are useful for a classification task.

在这个将 GCN 应用于空手道俱乐部网络的简单示例中，观察嵌入在半监督分类任务训练期间的反应非常有趣。 这种可视化（见图 4）提供了关于 GCN 模型如何利用图结构（以及从后面层的图结构中提取的特征）来学习对分类任务有用的嵌入的见解。

We consider the following semi-supervised learning setup: we add a softmax layer on top of our model (Eq. 13) and train using only a single labeled example per class (i.e. a total number of 4 labeled nodes). We train for 300 training iterations using Adam (Kingma & Ba 2015) with a learning rate of $0.01$ on a cross-entropy loss.

我们考虑以下半监督学习设置：我们在模型顶部添加一个 softmax 层（等式 13），并且每个类仅使用单个标记示例（即总共 4 个标记节点）进行训练。 我们使用 Adam (Kingma & Ba 2015) 进行 300 次训练迭代，交叉熵损失的学习率为 $0.01$。

Figure 4 shows the evolution of node embeddings over a number of training iterations. The model succeeds in linearly separating the communities based on minimal supervision and the graph structure alone. A video of the full training process can be found on our website[^7].

图 4 显示了节点嵌入在多次训练迭代中的演变。 该模型成功地基于最少的监督和图结构来线性分离社区。 完整训练过程的视频可以在我们的网站上找到[^7]。

(a) Iteration 25

(a) 迭代 25

Appendix B Experiments on Model Depth

附录 B 模型深度实验

In these experiments, we investigate the influence of model depth (number of layers) on classification performance. We report results on a 5-fold cross-validation experiment on the Cora, Citeseer and Pubmed datasets (Sen et al. 2008) using all labels. In addition to the standard GCN model (Eq. 2), we report results on a model variant where we use residual connections (He et al. 2016) between hidden layers to facilitate training of deeper models by enabling the model to carry over information from the previous layer’s input:

在这些实验中，我们研究了模型深度（层数）对分类性能的影响。 我们报告了使用所有标签对 Cora、Citeseer 和 Pubmed 数据集（Sen 等人，2008）进行 5 倍交叉验证实验的结果。 除了标准 GCN 模型（等式 2）之外，我们还报告了模型变体的结果，其中我们在隐藏层之间使用残差连接（He et al. 2016），通过使模型能够继承前一层输入的信息来促进更深层次模型的训练：

$$\textstyle H^{(l+1)}=\sigma\!\left(\tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}H^{(l)}W^{(l)}\right)+H^{(l)}\,. \tag{14}$$

On each cross-validation split, we train for 400 epochs (without early stopping) using the Adam optimizer (Kingma & Ba 2015) with a learning rate of $0.01$. Other hyperparameters are chosen as follows: 0.5 (dropout rate, first and last layer), $5\cdot 10^{-4}$ (L2 regularization, first layer), 16 (number of units for each hidden layer) and 0.01 (learning rate). Results are summarized in Figure 5.

在每个交叉验证分割中，我们使用 Adam 优化器 (Kingma & Ba 2015) 训练 400 个 epoch（没有提前停止），学习率为$0.01$。 其他超参数选择如下：0.5（丢弃率，第一层和最后一层）、$5\cdot 10^{-4}$（L2 正则化，第一层）、16（每个隐藏层的单元数）和 0.01（学习率）。 结果总结于图 5 中。

Figure 5: Influence of model depth (number of layers) on classification performance. Markers denote mean classification accuracy (training vs. testing) for 5-fold cross-validation. Shaded areas denote standard error. We show results both for a standard GCN model (dashed lines) and a model with added residual connections (He et al. 2016) between hidden layers (solid lines).

图 5：模型深度（层数）对分类性能的影响。 标记表示 5 倍交叉验证的平均分类精度（训练与测试）。 阴影区域表示标准误差。 我们展示了标准 GCN 模型（虚线）和隐藏层之间添加残差连接的模型（He et al. 2016）的结果（实线）。

For the datasets considered here, best results are obtained with a 2- or 3-layer model. We observe that for models deeper than 7 layers, training without the use of residual connections can become difficult, as the effective context size for each node increases by the size of its $K^{\text{th}}$-order neighborhood (for a model with $K$ layers) with each additional layer. Furthermore, overfitting can become an issue as the number of parameters increases with model depth.

对于此处考虑的数据集，使用 2 层或 3 层模型可以获得最佳结果。 我们观察到，对于深度超过 7 层的模型，不使用残差连接的训练可能会变得困难，因为每个节点的有效上下文大小随着每个附加层的$K^{\text{th}}$阶邻域（对于具有$K$层的模型）的大小而增加。 此外，随着参数数量随着模型深度的增加而增加，过度拟合可能成为一个问题。