Question

1. 众所周知训练深度神经网络通常需要大量的标记数据。由于获得标记样本的成本较高，因此在很多情况下无法大量标记数据的需求无法满足。为了降低模型训练所需的标记数据量，最近很多研究集中在fewshot learning 上：学习一个分类模型，其中每个类别只有很少的标记数据。和 fewshot learning 密切相关的是半监督学习，其中大量未标记数据来辅助训练少量的标记数据。很多研究表明：如果使用得当，在训练中使用未标记数据可以显著提升模型的预测能力。

   关键问题是如何最大程度地有效利用未标记数据的结构信息和特征信息。目前已有一些基于神经网络的半监督学习模型取得成功，包括 ladder network, semi-supervised embedding, planetoid, graph convolutional network 。

   最近的图卷积神经网络 graph convolutional neural networks: GCNN 成功地推广了CNN 来处理图结构数据。《Semisupervised classification with graph convolutional networks》 提出了一种简化的 GCNN模型，称作图卷积网络 GCN ，并将其应用于半监督分类中。GCN 模型很自然地融合了图结构信息和节点特征信息，并在某些 benchmark 上明显优于许多 state-of-the-art 的方法。

   但是，GCN 模型面临很多其它神经网络模型类似的问题：

   • 用于半监督学习的 GCN 模型的工作机制尚不清楚。
   • 虽然 GCN 只需要少量的标记数据用于训练，但是GCN 仍然需要大量标记数据作为验证集从而用于超参数调优和模型选择。这违背了半监督学习的目的。

   论文 《Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning》 深入洞察 GCN 模型，并提出：GCN 模型的图卷积只是拉普拉斯平滑的一种特殊形式，这种平滑混合了节点及其周围邻域的特征。平滑操作使得同一个簇 cluster 中节点的特征相似，从而大大简化了分类任务，这是 GCN 表现出色的关键原因。

   但是，这也会带来过度平滑 over-smoothing 的潜在风险。如果 GCN 有很多层的卷积层，则最终输出的特征可能过于平滑，使得来自不同 cluster 之间的节点变得难以区分。如下图所示为 karate club 数据集分别使用 1、2、3、4、5 层 GCN 训练的节点 embedding 可视化的结果，不同颜色表示不同的类别。可以看到，随着卷积层数量的增加，过度平滑很快发生。除此之外，使用很多层的卷积层也使得训练变得更加困难。

   

   但是卷积层数量太少也会有问题。在半监督学习中标记数据太少，这使得浅层 GCN 无法将标签信息有效地传播到整个图。这就是卷积滤波器局部性带来的困扰。如下图所示（Cora 数据集），随着训练的标签数据的减少，GCN 性能迅速下降。即使采用了额外的 500 个标记样本作为验证集（图中的 GCN with validation 曲线），GCN 的性能也是迅速下降。

   

   为了克服 GCN 模型的缺陷并实现模型的全部潜力，论文提出了一种共同训练Co-Training 方法和一种自训练 Self-Training 方法来训练 GCN。

   • 通过将 GCN 和随机游走模型共同训练，从而利用随机游走模型补充 GCN 在探索全局图拓扑结构方面的不足。
   • 通过自训练，从而利用 GCN 的特征抽取能力来克服卷积滤波器的局部性。

   通过将 Co-Training 和 Self-Training 相结合，可以大大改善带少量标记数据的半监督学习的 GCN 模型，并使得它不需要额外的标记数据进行验证。如上图所示，论文提出的方法（红色曲线）在很大程度上超越了 GCN 的表现。

   论文贡献：

   • 对半监督 GCN 模型提供了新的洞察和分析。
   • 提出了改进半监督 GCN 模型的解决方案。

1.1 基本原理和相关工作

1. 给定图$\mathcal{G}=(\mathcal{V},\mathcal{E},\mathbf{X})$$ \mathcal G=(\mathcal V, \mathcal E,\mathbf X) $ ，其中$\mathcal{V}=\{v_1,\cdots ,v_n\}$$ \mathcal V=\{v_1,\cdots,v_n\} $ 为节点集合，$\mathcal{E}$$ \mathcal E $ 为边集合，$\mathbf{X}=[{\overrightarrow{\mathbf{x}}}_1,{\overrightarrow{\mathbf{x}}}_2,\cdots ,{\overrightarrow{\mathbf{x}}}_n{]}^{\mathrm{\top }}\in {\mathbb{R}}^{n\times d_f}$$ \mathbf X = [\mathbf{\vec x}_1,\mathbf{\vec x}_2,\cdots,\mathbf{\vec x}_n]^\top\in \mathbb R^{n\times d_f} $ 为节点的特征矩阵，${\overrightarrow{\mathbf{x}}}_i\in {\mathbb{R}}^{d_f}$$ \mathbf{\vec x}_i\in \mathbb R^{d_f} $ 为节点$v_i$$ v_i $ 的特征向量，$d_f$$ d_f $ 为特征维度。注意，为简单起见，这里我们仅讨论无向图。

   定义非负的邻接矩阵$\mathbf{A}=[a_{i,j}]\in {\mathbb{R}}^{n\times n}$$ \mathbf A = [a_{i,j}]\in \mathbb R^{n\times n} $ ；定义度矩阵$\mathbf{D}=\text{diag}(d_1,\cdots ,d_n),d_i=\sum _j{a}_{i,j}$$ \mathbf D = \text{diag}(d_1,\cdots,d_n), d_i=\sum_{j} a_{i,j} $ ；定义图拉普拉斯矩阵$\mathbf{L}=\mathbf{D}-\mathbf{A}$$ \mathbf L = \mathbf D - \mathbf A $ 。定义归一化的图拉普拉斯矩阵为：对称版本为${\mathbf{L}}_{\text{sym}}={\mathbf{D}}^{-1/2}\mathbf{L}{\mathbf{D}}^{-1/2}$$ \mathbf L_{\text{sym}} = \mathbf D^{-1/2}\mathbf L \mathbf D^{-1/2} $ 、非对称版本为${\mathbf{L}}_{\text{rw}}={\mathbf{D}}^{-1}\mathbf{L}$$ \mathbf L_{\text{rw}} = \mathbf D^{-1}\mathbf L $ 。

   这里我们只考虑图上的半监督分类问题。假设标记节点集合为${\mathcal{V}}_l$$ \mathcal V_l $ ，剩余的未标记节点集合为${\mathcal{V}}_u=\mathcal{V}-{\mathcal{V}}_l$$ \mathcal V_u = \mathcal V - \mathcal V_l $ 。其中${\mathcal{V}}_u$$ \mathcal V_u $ 就是我们需要预测标签的节点集合。

1.1.1 基于图的半监督学习

1. 基于图的半监督学习利用数据的拓扑结构从而可以通过很少的标签进行学习。很多基于图的半监督学习方法都采用聚类假设 cluster assumption：假设图上距离相近的节点倾向于共享相同的标签。采用这种假设的方法包括：最小割min-cuts 、随机最小割randomized min-cuts、spectral graph transducer、标签传播 label propagation 及其变体、modified adsorption、iterative classification algorithm 。

   但是图仅仅代表拓扑结构信息，在很多应用场景中，数据还带有属性信息。如引文网络中，文档可以表示为描述其内容的 bag-of-words 向量。许多半监督学习方法试图联合建模图结构和特征属性。一个常见的想法是用一些正则器对supervised learner 进行正则化。例如：

   • LapSVM 使用流形正则化manifold regularization 从而通过拉普拉斯正则化器来正则化支持向量机。
   • deep semi-supervised embedding 用基于embedding 的正则器对深度神经网络进行正则化。
   • Planetoid 也通过联合预测一个节点的类别标签和上下文来正则化神经网络。

1.1.2 GCN

1. Graph convolutional neural networks: GCNN 将传统的卷积神经网络推广到图数据。GCNN 主要有两种类型：空间 GCNN、谱域 GCNN 。

   • 空间 GCNN 将卷积视为 patch operator ，它基于节点邻域信息为每个节点构建一个新的 representation 向量。

   • 谱域 GCNN 通过谱域分解图信号$\overrightarrow{\mathbf{s}}\in {\mathbb{R}}^n$$ \mathbf{\vec s}\in \mathbb R^n $ ，然后在谱分量 spectral component上应用谱域滤波器$g_{\theta }$$ g_\theta $ ：

     $$\begin{array}{c}\overrightarrow{\mathbf{y}}=\mathbf{U}\mathbf{K}{\mathbf{U}}^{\mathrm{\top }}\overrightarrow{\mathbf{s}}\\ {\theta }_i=g_{\theta }({\lambda }_i),\mathbf{K}=\left[\begin{array}{cccc}{\theta }_1& 0& \cdots & 0\\ 0& {\theta }_2& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & {\theta }_n\end{array}\right]\end{array}$$

     其中：图信号$\overrightarrow{\mathbf{s}}$$ \mathbf{\vec s} $ 每个原始对应于每个节点上的一个标量值；谱域滤波器$g_{\theta }$$ g_\theta $ 是${\mathbf{L}}_{\text{sym}}$$ \mathbf L_{\text{sym}} $ 特征值的函数；$\mathbf{K}$$ \mathbf K $ 为卷积核；$\mathbf{U}$$ \mathbf U $ 为拉普拉斯矩阵特征向量 eigenvector 组成的矩阵。

2. 谱域GCNN 需要显式计算图的拉普拉斯特征向量 eigenvector ，这对于很多实际的大图来讲是难以实现的。解决该问题的一种方法是对谱域滤波器进$g_{\theta }$$ g_\theta $ 进行$K$$ K $ 阶切比雪夫多项式近似：

   $$\begin{array}{c}{\tilde{\mathbf{L}}}_{\text{sym}}=\frac{2}{{\lambda }_{max}}{\mathbf{L}}_{\text{sym}}-\mathbf{I}\\ \overrightarrow{\mathbf{y}}=\mathbf{U}\mathbf{K}{\mathbf{U}}^{\mathrm{\top }}\overrightarrow{\mathbf{s}}\simeq \sum _{k=0}^K{\beta }_k{T}_k({\tilde{\mathbf{L}}}_{\text{sym}})\overrightarrow{\mathbf{s}}\end{array}$$

   其中：${\beta }_k$$ \beta_k $ 为$k$$ k $ 阶切比雪夫多项式的系数，$T_k(\cdot )$$ T_k(\cdot) $ 为$k$$ k $ 阶切比雪夫多项式。

   《Semisupervised classification with graph convolutional networks》 通过限定$K=1$$ K=1 $ 来简化该模型，从而得到：

   $${\mathbf{H}}^{(l+1)}=\sigma \left({\tilde{\mathbf{D}}}^{-1/2}\tilde{\mathbf{A}}{\tilde{\mathbf{D}}}^{-1/2}{\mathbf{H}}^{(l)}{\mathbf{W}}^{(l)}\right)$$

   其中：$\tilde{\mathbf{A}}=\mathbf{A}+\mathbf{I}$$ \tilde{\mathbf A} = \mathbf A + \mathbf I $ ，$\tilde{\mathbf{D}}$$ \tilde{\mathbf D} $ 为$\tilde{\mathbf{A}}$$ \tilde{\mathbf A} $ 的度矩阵；${\mathbf{H}}^{(l)}$$ \mathbf H^{(l)} $ 为第$l$$ l $ 层的 hidden representation，${\mathbf{H}}^{(0)}=\mathbf{X}$$ \mathbf H^{(0)} = \mathbf X $ ；${\mathbf{W}}^{(l)}$$ \mathbf W^{(l)} $ 为第$l$$ l $ 层的参数矩阵；$\sigma (\cdot )$$ \sigma(\cdot) $ 为激活函数。

   这个简化的模型被称作 GCN。

1.1.3 采用 GCN 的半监督分类

1. 在 《Semisupervised classification with graph convolutional networks》 论文中，GCN 模型用于半监督分类。模型采用两层卷积层，并使用 softmax 分类器：

   $$\mathbf{Z}=\text{softmax}\left(\hat{\mathbf{A}}\text{ReLU}\left(\hat{\mathbf{A}}\mathbf{X}{\mathbf{W}}^{(0)}\right){\mathbf{W}}^{(1)}\right)$$

   其中：$\hat{\mathbf{A}}={\tilde{\mathbf{D}}}^{-1/2}\tilde{\mathbf{A}}{\tilde{\mathbf{D}}}^{-1/2}$$ \hat{\mathbf A} = \tilde{\mathbf D}^{-1/2}\tilde{\mathbf A} \tilde{\mathbf D}^{-1/2} $ ； ReLU(.) 为 ReLU 激活函数。

   损失函数为在所有标记数据上的交叉熵损失：

   $$\mathcal{L}=\sum _{v_i\in {\mathcal{V}}_l}\sum _{c=1}^C{y}_{i,c}\log z_{i,c}$$

   其中：

   • ${\mathcal{V}}_l$$ \mathcal V_l $ 为标记的训练集，$C$$ C $ 为类别数量。

   • ${\overrightarrow{\mathbf{y}}}_i$$ \mathbf{\vec y}_i $ 为节点$v_i$$ v_i $ 的类别标记的 one-hot 向量。$y_{i,c}\in \{0,1\}$$ y_{i,c}\in \{0,1\} $ 为${\overrightarrow{\mathbf{y}}}_i$$ \mathbf{\vec y}_i $ 的第$c$$ c $ 个元素，表示节点$v_i$$ v_i $ 是否属于类别$c$$ c $ 。它满足：

     $$\begin{array}{c}\sum _{c=1}^C{y}_{i,c}=1\\ y_{i,c}\in \{0,1\}\end{array}$$

   • ${\overrightarrow{\mathbf{z}}}_i$$ \mathbf{\vec z}_i $ 为节点$v_i$$ v_i $ 预测属于各类别的概率。$z_{i,c}$$ z_{i,c} $ 为${\overrightarrow{\mathbf{z}}}_i$$ \mathbf{\vec z}_i $ 的第$c$$ c $ 个元素，表示节点$v_i$$ v_i $ 属于类别$c$$ c $ 的概率。它满足：

     $$\begin{array}{c}\sum _{c=1}^C{z}_{i,c}=1.0\\ 0.0\le z_{i,c}\le 1.0\end{array}$$

   GCN 模型很自然地在卷积中结合了图拓扑结构和节点属性，其中未标记节点的属性和附近的标记节点的属性混合，并通过多层 GCN 传播到图上。实验表明，在某些 benchmark 上（如引文网络），GCN 性能明显优于很多 state-of-the-art 方法。

   这里的半监督学习仅考虑监督损失，而并未考虑无监督损失。还有一些工作会同时考虑监督损失和无监督损失。

1.2 分析

1. 尽管 GCN 效果很好，但是我们还不清楚它的机制。这里我们仔细研究 GCN 模型，分析其原理并指出其局限性。

1.2.1 为什么 GCN 有效

1. 为分析 GCN 工作良好的原因，我们将其与最简单的全连接网络 fully-connected networks:FCN 进行比较，其中layer-wise 传播规则为：

   $${\mathbf{H}}^{(l+1)}=\sigma \left({\mathbf{H}}^{(l)}{\mathbf{W}}^{(l)}\right)$$

   可以看到 GCN 和 FCN 的区别在于：GCN 在 FCN 的左边乘以一个图卷积矩阵 graph convolution matrix$\hat{\mathbf{A}}={\tilde{\mathbf{D}}}^{-1/2}\tilde{\mathbf{A}}{\tilde{\mathbf{D}}}^{-1/2}$$ \hat{\mathbf A} = \tilde{\mathbf D}^{-1/2}\tilde{\mathbf A} \tilde{\mathbf D}^{-1/2} $ 。

   为分析图卷积矩阵的影响，我们在 Cora 引文网络上对比了 GCN 和 FCN 在半监督分类上的性能，其中每个类别有 20 个标记数据。对比结果如下表所示，可以看到：即使只有一层，GCN 也要比 FCN 效果好得多。

   

   首先我们考虑单层的 GCN 网络，它包含两步：

   • 通过对节点特征矩阵$\mathbf{X}$$ \mathbf X $ 应用图卷积，从而生成一个新的 representation 矩阵$\mathbf{H}$$ \mathbf H $ ：

     $$\mathbf{H}={\tilde{\mathbf{D}}}^{-1/2}\tilde{\mathbf{A}}{\tilde{\mathbf{D}}}^{-1/2}\mathbf{X}$$

   • 然后将新的 representation 矩阵$\mathbf{H}$$ \mathbf H $ 馈入一个全连接层。

   显然，图卷积是GCN 相对于 FCN 获得巨大性能提升的关键。

2. 拉普拉斯平滑：假设我们向图中每个节点添加一个自连接 self-connection ，则新的邻接矩阵为$\tilde{\mathbf{A}}=\mathbf{A}+\mathbf{I}$$ \tilde{\mathbf A} = \mathbf A + \mathbf I $ 。

   在输入特征每个维度上的拉普拉斯平滑 Laplacian Smoothing 定义为：

   $$h_i=(1-\gamma )x_i+\gamma \times \sum _{j=1}^n(\frac{{\tilde{a}}_{i,j}}{{\tilde{d}}_i}\times x_j),1\le i\le n$$

   其中：

   • $x_i$$ x_i $ 为节点$v_i$$ v_i $ 在某个维度上的取值（标量）。
   • $h_i$$ h_i $ 为节点$v_i$$ v_i $ 在该维度上拉普拉斯平滑结果（标量）。
   • $0<\gamma \le 1$$ 0\lt \gamma \le 1 $ 为平滑参数，它控制当前节点$v_i$$ v_i $ 在该维度上取值及其邻域取值之间的权重。
   • ${\tilde{a}}_{i,j}$$ \tilde a_{i,j} $ 为$\tilde{\mathbf{A}}$$ \tilde{\mathbf A} $ 的第$i$$ i $ 行、$j$$ j $ 列元素；${\tilde{d}}_i=\sum _j{\tilde{a}}_{i,j}$$ \tilde d_i=\sum_{j}\tilde a_{i,j} $ 为节点$v_i$$ v_i $ 在新的邻接矩阵上的 degree 。

   我们以矩阵的形式重写拉普拉斯平滑：

   $$\mathbf{H}=\mathbf{X}-\gamma {\tilde{\mathbf{D}}}^{-1}\tilde{\mathbf{L}}\mathbf{X}=(\mathbf{I}-\gamma {\tilde{\mathbf{D}}}^{-1}\tilde{\mathbf{L}})\mathbf{X}$$

   其中$\tilde{\mathbf{L}}=\tilde{\mathbf{D}}-\tilde{\mathbf{A}}$$ \tilde{\mathbf L} =\tilde{\mathbf D} - \tilde{\mathbf A} $ 。

   令$\gamma =1$$ \gamma = 1 $ 即仅使用邻域特征，则拉普拉斯平滑退化为：

   $$\mathbf{H}={\tilde{\mathbf{D}}}^{-1}\tilde{\mathbf{A}}\mathbf{X}={\tilde{\mathbf{D}}}^{-1/2}\tilde{\mathbf{A}}{\tilde{\mathbf{D}}}^{-1/2}\mathbf{X}$$

   这刚好就是图卷积公式。因此，我们将图卷积视为拉普拉斯平滑的一种特殊形式，称作对称拉普拉斯平滑 Symmetric Laplacian Smoothing 。注意：虽然$\gamma =1$$ \gamma=1 $ 表示仅使用邻域特征，这里的平滑过程仍然包含当前节点的特征。因为每个节点都有一个自连接，所以每个节点都是自己的邻居。

   拉普拉斯平滑将节点的 representation 计算为自身以及邻域特征的加权平均。由于同一个 cluster 中的节点倾向于紧密连接 densely connected，因此平滑处理使得它们的 representation 彼此相似，这有助于后续的分类过程。从下图（ Cora 引文网络）可以看到，仅使用一次拉普拉斯平滑操作就能够带来巨大的性能提升。

   

3. 多层架构：从上图中我们也看到，虽然两层 FCN 相对于一层 FCN 有少许提升，但是两层 GCN 比一层 GCN 提升很大。这是因为在第一层 representation 上再次应用平滑会使得同一个 cluster 中节点的输出 representation 更为相似，进一步提升分类性能。

1.2.2 为什么失败

1. 我们已经表明：图卷积本质上是一种拉普拉斯平滑。一个自然的问题是，GCN 中应该包含多少卷积层？显然层数不是越多越好。一方面，深层 GCN 非常难以训练；另一方面，反复应用拉普拉斯平滑可能会混合来自不同 cluster 的节点的信息，使得它们无法区分。

   我们用 karate club 数据集为例。该数据集包含 34 个节点、78 条边、两种节点类型。我们将隐层维度设为 16，输出层维度为 2。每个节点的特征向量为节点的 one-hot 向量。可以观察到拉普拉斯平滑对该数据集的影响。

   • 在进行一次平滑之后，不同类型节点之间的区分不明显。
   • 在进行两次平滑之后，不同类型节点之间的区分相当明显。
   • 在进行更多次平滑之后，不同类型节点被混合 mixing。

   由于这是一个很小的数据集，而且两种类别节点之间存在很多连接，因此混合很快发生。

   

2. 我们即将证明：通过多次重复应用拉普拉斯平滑，图的每个连通分量 connected component 内的节点 representation 将收敛到相同的值。对于对称拉普拉斯平滑，它们将收敛到与节点的 degree 的平方根成正比。

   连通分量：任意两点之间都存在路径来访问。

   假设图$\mathcal{G}$$ \mathcal G $ 有$k$$ k $ 个连通分量$\{{\mathcal{C}}_i{\}}_{i=1}^k$$ \{\mathcal C_i\}_{i=1}^k $ ，对于第$i$$ i $ 个连通分量定义一个示性向量${\overrightarrow{\mathbf{q}}}^{(i)}\in {\mathbb{R}}^n$$ \mathbf{\vec q}^{(i)}\in \mathbb R^n $ ，其定义为：

   $$\begin{array}{c}{q}_j^{(i)}=\{\begin{array}{ll}1,& v_j\in {\mathcal{C}}_i\\ 0,& \text{else}\end{array}\end{array}$$

   因此${\overrightarrow{\mathbf{q}}}^{(i)}$$ \mathbf{\vec q}^{(i)} $ 向量中元素为 1 的项对应于属于第$i$$ i $ 个连通分量的节点。

   定理：如果一个图没有bipartite components，则对于任意信号$\overrightarrow{\mathbf{s}}\in {\mathbb{R}}^n$$ \mathbf{\vec s}\in \mathbb R^n $ 以及$\alpha \in (0,1]$$ \alpha \in (0,1] $ ，都有：

   $$\begin{array}{c}\underset{m\to +\mathrm{\infty }}{lim}{(\mathbf{I}-\alpha {\mathbf{L}}_{\text{rw}})}^m\overrightarrow{\mathbf{s}}=[{\overrightarrow{\mathbf{q}}}^{(1)},\cdots ,{\overrightarrow{\mathbf{q}}}^{(k)}]{\overrightarrow{\mathbf{w}}}_1\\ \underset{m\to +\mathrm{\infty }}{lim}{(\mathbf{I}-\alpha {\mathbf{L}}_{\text{sym}})}^m\overrightarrow{\mathbf{s}}={\mathbf{D}}^{-1/2}[{\overrightarrow{\mathbf{q}}}^{(1)},\cdots ,{\overrightarrow{\mathbf{q}}}^{(k)}]{\overrightarrow{\mathbf{w}}}_2\end{array}$$

   其中${\overrightarrow{\mathbf{w}}}_1\in {\mathbb{R}}^k,{\overrightarrow{\mathbf{w}}}_2\in {\mathbb{R}}^k$$ \mathbf{\vec w}_1\in \mathbb R^k, \mathbf{\vec w}_2\in \mathbb R^k $ 。即它们分别收敛到${\left\{{\overrightarrow{\mathbf{q}}}^{(i)}\right\}}_{i=1}^k$$ \left\{\mathbf{\vec q}^{(i)}\right\}_{i=1}^k $ 以及${\left\{{\mathbf{D}}^{-1/2}{\overrightarrow{\mathbf{q}}}^{(i)}\right\}}_{i=1}^k$$ \left\{\mathbf D^{-1/2} \mathbf{\vec q}^{(i)}\right\}_{i=1}^k $ 的线性组合。

   证明：${\mathbf{L}}_{\text{rw}}$$ \mathbf L_{\text{rw}} $ 和${\mathbf{L}}_{\text{sym}}$$ \mathbf L_{\text{sym}} $ 有相同的$n$$ n $ 个特征值 eigenvalues，但是有不同的特征向量 eigenvectors 。如果图没有 bipartite components，则所有特征值都位于 [0,2) 之间。 则${\mathbf{L}}_{\text{rw}}$$ \mathbf L_{\text{rw}} $ 和${\mathbf{L}}_{\text{sym}}$$ \mathbf L_{\text{sym}} $ 对应于特征值 0 的特征空间 eigenspaces 分别由${\left\{{\overrightarrow{\mathbf{q}}}^{(i)}\right\}}_{i=1}^k$$ \left\{\mathbf{\vec q}^{(i)}\right\}_{i=1}^k $ 以及${\left\{{\mathbf{D}}^{-1/2}{\overrightarrow{\mathbf{q}}}^{(i)}\right\}}_{i=1}^k$$ \left\{\mathbf D^{-1/2} \mathbf{\vec q}^{(i)}\right\}_{i=1}^k $ 派生（即这些向量构成的线性空间）。

   对于$\alpha \in (0,1]$$ \alpha \in (0,1] $ ，则$(\mathbf{I}-\alpha {\mathbf{L}}_{\text{rw}})$$ \left(\mathbf I - \alpha \mathbf L_{\text{rw}}\right) $ 以及$(\mathbf{I}-\alpha {\mathbf{L}}_{\text{sym}})$$ \left(\mathbf I - \alpha \mathbf L_{\text{sym}}\right) $ 的特征值都落在区间 (-1,1] 。因此特征值 1 对应的特征空间分别由${\left\{{\overrightarrow{\mathbf{q}}}^{(i)}\right\}}_{i=1}^k$$ \left\{\mathbf{\vec q}^{(i)}\right\}_{i=1}^k $ 以及${\left\{{\mathbf{D}}^{-1/2}{\overrightarrow{\mathbf{q}}}^{(i)}\right\}}_{i=1}^k$$ \left\{\mathbf D^{-1/2} \mathbf{\vec q}^{(i)}\right\}_{i=1}^k $ 派生。

   由于$(\mathbf{I}-\alpha {\mathbf{L}}_{\text{rw}})$$ \left(\mathbf I - \alpha \mathbf L_{\text{rw}}\right) $ 以及$(\mathbf{I}-\alpha {\mathbf{L}}_{\text{sym}})$$ \left(\mathbf I - \alpha \mathbf L_{\text{sym}}\right) $ 的所有特征值的绝对值都小于等于 1，所以经过多次反复相乘之后，它们的结果收敛到特征值 1 对应的特征向量的线性组合，即${\left\{{\overrightarrow{\mathbf{q}}}^{(i)}\right\}}_{i=1}^k$$ \left\{\mathbf{\vec q}^{(i)}\right\}_{i=1}^k $ 以及${\left\{{\mathbf{D}}^{-1/2}{\overrightarrow{\mathbf{q}}}^{(i)}\right\}}_{i=1}^k$$ \left\{\mathbf D^{-1/2} \mathbf{\vec q}^{(i)}\right\}_{i=1}^k $ 的线性组合。

3. 注意，由于每个节点都添加了额外的自连接，因此图中没有 bipartite component 。根据上述结论，过度平滑 over-smoothing 将使得节点之间特征难以区分从而有损于分类性能。

4. 上述分析总结了堆叠多层卷积层导致 GCN 过度平滑的问题，此外深层的 GCN 也难以训练。因此 《Semisupervised classification with graph convolutional networks》 使用的 GCN 采用两层卷积层。

   但是，由于图卷积是局部滤波器，即邻域节点的特征向量的线性组合，因此浅层 GCN 无法将标签信息充分传播到整个图上。如下图所示（Cora 数据集），随机训练标记数据的减少，GCN 算法的性能迅速下降。可以看到 GCN 准确率随着标记数据规模减少而下降的速度，要比 label propagation 下降速度快得多。由于标签传播label propagation 算法仅使用图结构，而 GCN 同时使用图结构和节点特征，因此这反应了 GCN 模型无法探索全局图结构。

   

5. GCN 的另一个问题是，它需要额外的验证集来实现早停，这本质上是需要额外的标记数据作为验证集来执行模型选择。如果我们不使用验证集来训练 GCN，则其性能会大大降低。如上图所示，不带验证集的 GCN 性能（GCN without validation）要比带验证集的 GCN 性能（GCN with validation）差得多。

   《Semisupervised classification with graph convolutional networks》 使用了额外 500 个标记数据作为验证集，这远多于训练标记数据。这是不可取的，因为这违反了半监督学习的目的。此外，这也使得 GCN 和其它方法的比较不公平，因为其它方法（如标签传播）可能根本不需要验证集。

1.3 解决方案

1. 我们总结了 GCN 模型的优缺点：

   • 优点：

     • 图卷积（拉普拉斯平滑）有助于分类问题。
     • 多层神经网络是功能强大的特征抽取器。

   • 缺点：

     • 图卷积是一个局部滤波器，在标记数据很少的情况下效果不理想。
     • 神经网络需要大量的标记数据作为验证集，从而进行模型选择。

     注：读者认为还有一个缺点是容易过度平滑。

   我们希望在克服缺点的同时充分利用 GCN 模型的优点。因此我们提出了 Co-Training、Self-Training 等思想。

1.3.1 Co-Training

1. 我们提出将 GCN 和随机游走模型一起共同训练，因为后者可以探索全局图结构，从而解决卷积局部性的问题。

   具体而言，我们首先使用随机游走模型找到最置信 confidence 的节点（即，每个标记节点的最近邻居），然后将它们添加到标记数据集合从而训练 GCN 。

   和 《Semisupervised classification with graph convolutional networks》 不同，我们直接在训练集上优化 GCN ，无需任何其它标记数据来作为验证集。

2. 我们使用 partially absorbing random walks:ParWalks 算法作为我们的随机游走模型。ParWalks 是一个二阶马尔科夫链，它在每个状态下都有部分吸收 partial absorption 。

   考虑下图的简单扩散过程：

   • 首先将单位能量（蓝色）注入到指定的节点。

   • 第一步，某些能量（红色）“存储” 在当前节点，剩余能量（蓝色）传播到邻居中。

   • 每当能量通过节点时，一部分能量就会保留在当前节点、剩余能量继续传播。

     随着该过程的持续，每个节点中存储的能量将累积，并且图中流动的能量越来越少。经过一定数量的step 后，几乎没有剩余能量流动，并且存储的能量总和几乎为 1 。

   

   正式地，考虑一个离散时间的随机过程$X=\{X_t:t\ge 0\}$$ X = \{X_t:t\ge 0\} $ ，状态空间为$N=\{1,2,\cdots ,n\}$$ N=\{1,2,\cdots,n\} $ ，其中初始状态$X_0=i$$ X_0 =i $ 是给定的。则下一个状态$X_1$$ X_1 $ 是由转移概率$P(X_1=j\mid X_0=i)=p_{i,j}$$ P(X_1=j\mid X_0 = i) = p_{i,j} $ 来决定：

   $$\begin{array}{c}P(X_{t+2}=j\mid X_{t+1}=i,X_t=k)=\{\begin{array}{ll}1,& i=j,i=k\\ 0,& i\ne j,i=k,\\ P(X_{t+2}=j\mid X_{t+1}=i)=p_{i,j},& i\ne k\end{array}\end{array}$$

   即：如果前一个状态和当前状态是相同的，则下一个状态也永远保持不变；否则下一个状态和前一个状态无关、仅和当前状态有关（类似于普通的随机游走）。

   对于图$\mathcal{G}$$ \mathcal G $ ，定义图上的 ParWalks 转移概率为：

   $$\begin{array}{c}{p}_{i,j}=\{\begin{array}{ll}\frac{{\lambda }_i}{{\lambda }_i+d_i},& i=j\\ \frac{a_{i,j}}{{\lambda }_i+d_i},& i\ne j\end{array}\end{array}$$

   其中：

   • ${\lambda }_i\ge 0$$ \lambda_i\ge 0 $ 为任意参数。当${\lambda }_i>0$$ \lambda_i\gt0 $ 时我们说状态$i$$ i $ （或者说节点$v_i$$ v_i $ ）是一个吸收状态 absorbing state；当${\lambda }_i=0$$ \lambda_i =0 $ 时我们说状态$i$$ i $ （或者说节点$v_i$$ v_i $ ）是一个transient state 。
   • $a_{i,j}$$ a_{i,j} $ 为节点$v_i,v_j$$ v_i,v_j $ 之间边的权重，$d_i$$ d_i $ 为节点$v_i$$ v_i $ 的 degree 。

   定义$\mathbf{\Lambda }=\text{diag}({\lambda }_1,\cdots ,{\lambda }_n)$$ \mathbf \Lambda = \text{diag}(\lambda_1,\cdots,\lambda_n) $ ，则$\mathbf{\Lambda }$$ \mathbf\Lambda $ 类似于一个正则化器，它控制每个节点的吸收状态，${\lambda }_i$$ \lambda_i $ 越大则$p_{i,i}$$ p_{i,i} $ 越大（意味着节点停留在原地的概率越大）。因此，我们称$\mathbf{\Lambda }$$ \mathbf\Lambda $ 为正则器矩阵 regularizer matrix。

   我们关心的是从节点$v_i$$ v_i $ 开始的随机游走被节点$v_j$$ v_j $ 吸收的概率$r_{i,j}$$ r_{i,j} $ 。令$\mathbf{R}=[r_{i,j}]\in {\mathbb{R}}^{n\times n}$$ \mathbf R = [r_{i,j}]\in \mathbb R^{n\times n} $ 为吸收概率矩阵，则可以证明：如果对于某个$i$$ i $ 有${\lambda }_i>0$$ \lambda_i\gt 0 $ ，则有$\mathbf{R}=(\mathbf{\Lambda }+\mathbf{L}{)}^{-1}\mathbf{\Lambda }$$ \mathbf R = (\mathbf\Lambda + \mathbf L)^{-1} \mathbf\Lambda $ 。

   我们可以求解$\mathbf{R}$$ \mathbf R $ 来得到每个标记数据的最近邻节点，但是涉及到矩阵的求逆。为降低计算复杂度，我们采用随机游走采样来快速逼近。

3. ParWalks 算法：

   • 输入：

     • 图拉普拉斯矩阵$\mathbf{L}$$ \mathbf L $
     • 正则化器矩阵$\mathbf{\Lambda }$$ \mathbf\Lambda $

   • 输出：新的标记节点集合

   • 算法步骤：

     • 计算吸收概率矩阵$\mathbf{R}=(\mathbf{\Lambda }+\mathbf{L}{)}^{-1}\mathbf{\Lambda }$$ \mathbf R = (\mathbf\Lambda + \mathbf L)^{-1} \mathbf\Lambda $ 。

     • 对于每个类别$k$$ k $ ，假设${\mathcal{S}}_c$$ \mathcal S_c $ 为类别$c$$ c $ 的标记节点集合，计算：

       $$p_i=\sum _{j\in {\mathcal{S}}_c}{r}_{i,j},\overrightarrow{\mathbf{p}}=(p_1,\cdots ,p_n{)}^{\mathrm{\top }}\in {\mathbb{R}}^n$$

       即计算每个节点$v_i$$ v_i $ 距离${\mathcal{S}}_c$$ \mathcal S_c $ 中标记节点的吸收概率之和$p_i$$ p_i $ ，即每个节点隶属于类别$c$$ c $ 的置信度。$\overrightarrow{\mathbf{p}}$$ \mathbf{\vec p} $ 为置信度向量 confidence vector 。

       然后从$\{p_1,\cdots ,p_n\}$$ \{p_1,\cdots,p_n\} $ 中挑选 top - t 个节点，并将这些节点添加到标签$c$$ c $ 对应的训练标记数据。

       用随机游走来描述就是：观察哪些节点开始的随机游走序列最容易被类别为$c$$ c $ 的节点所吸收，那么就将这些节点视为类别$c$$ c $ 。

1.3.2 Self-Training

1. 让 GCN “看到” 更多标记数据的另一个方法是对 GCN 进行 self-train 。具体而言，我们首先通过给定的标记数据来训练 GCN，然后通过比较 softmax 得分为每个类别选择最置信的未标记数据，然后将这些未标记数据添加到对应的类别的标记数据集合中。然后，我们使用扩展的标记数据集合来训练 GCN，并使用预先训练好的 GCN 来作为初始化。

   GCN 发现的最置信的样本应该和标记数据共享相似（但不相同）的 representation，将它们添加到标记数据集合有助于训练更强大和准确的分类器。此外，它还在以下场景补充了 Co-Training 方法：当图具有很多孤立的、小的连通分量时，此时无法通过随机游走来传播标签。

   Co-Training 和 Self-Training 本质都是寻找最置信的未标记数据，从而将它们加入到标记数据中来扩充标记数据集。

   • Co-Training 是通过图结构来寻找最置信的节点，方法是基于随机游走寻找最近邻节点，无需模型参与。
   • Self-Training 是通过图结构和节点特征来寻找最置信的节点，方法是基于 GCN 模型寻找最相似节点。

2. Self-Training 算法：

   • 输入：训练好的 GCN 模型、图$\mathcal{G}$$ \mathcal G $

   • 输出：新的标记节点集合

   • 算法步骤：

     • 计算所有节点的预测输出：$\mathbf{Z}=\text{GCN}(\mathbf{X})\in {\mathbb{R}}^{n\times C}$$ \mathbf Z = \text{GCN}(\mathbf X)\in \mathbb R^{n\times C} $
     • 对每个类别$c$$ c $ ，从$\{z_{i,c}{\}}_{i=1}^n$$ \{z_{i,c}\}_{i=1}^n $ 中找到 top - t 个节点，并将这些节点添加到标签$c$$ c $ 对应的训练标记数据。

3. 为提升标签多样性 diversity 并训练更鲁棒的分类器，我们提出联合 Co-Training 和 Self-Training 。具体而言：

   • 使用Co-Training 、Self-Training 分别挖掘出各自最置信的未标记节点。
   • 使用二者未标记节点的并集来扩充标记数据集合，并继续训练 GCN，这称为 Union。其中使用预先训练好的 GCN 来作为二次训练的初始化。
   • 使用二者未标记节点的交集来扩充标记数据集合，并继续训练 GCN，这称为 Intersection。其中使用预先训练好的 GCN 来作为二次训练的初始化。

   注意：我们在扩展的标记数据上训练 GCN，无需任何额外其它验证数据。只要扩展的标记数据包含足够多的正确的标记数据，则我们的方法就有希望训练出良好的 GCN 分类器。

4. 但是，训练一个 GCN 分类器需要多少标记数据？假设 GCN 层数为$\tau$$ \tau $ ，图的平均 degree 为$\hat{d}$$ \hat d $ ，则我们提出通过求解${\left(\hat{d}\right)}^{\tau }\times \eta \simeq n$$ \left(\hat d\right)^\tau \times \eta \simeq n $ 来得到标记样本数量$\eta$$ \eta $ 的下界（根据定义有$|{\mathcal{V}}_l|=\eta$$ |\mathcal V_l| = \eta $ ）。背后的思想是：估计一个$\tau$$ \tau $ 层的 GCN 需要多少标记数据可以传播到整个图。

1.4 实验

1. 数据集：我们在三种常用的引文网络上进行实验：CiteSeer, Cora, PubMed。每个数据集上，文档采用 bag-of-word 特征向量，文档之间的引文链接通过 0/1 值的邻接矩阵来描述。

   这些数据集的统计信息如下表所示。

   

2. baseline 方法：

   我们和几种 state-of-the-art 方法比较，包括：带验证集的 GCN:GCN+V、不带验证集的 GCN:GCN-V、使用切比雪夫滤波器的 GCN(Cheby)、使用 ParWalks 的标记传播算法 label propagation:LP、 Planetoid 算法、DeepWalk 算法、流形正则化 manifold regularization:ManiReg、半监督嵌入semi-supervised embedding:SemiEmb 、iterative classification algorithm:ICA。

   我们对比了我们提出的 Co-Training、Self-Training、Union、Intersection 等方法。

3. 参数设置：

   • 对于 ParWalks，我们设置$\mathbf{\Lambda }=\alpha \mathbf{I}$$ \mathbf \Lambda = \alpha \mathbf I $ ，且$\alpha ={10}^{-6}$$ \alpha = 10^{-6} $ 。

   • 对于 GCN，我们使用和 《Semisupervised classification with graph convolutional networks》 相同的超参数，这些超参数是模型在 Cora 数据集上验证好的：学习率 0.01、最多 200 轮 epoch、$L_2$$ L_2 $ 正则化系数为$5\times {10}^{-4}$$ 5\times 10^{-4} $ 、2层卷积层、隐层维度16 。

   • 对于 GCN(Cheby)，我们选择多项式的阶数为$K=2$$ K=2 $ 。

   • 每次执行时，我们随机拆分标记数据，随机选择其中一小部分标记数据作为训练集，然后随机选择 1000 个标记数据作为测试集。

     • 对于 GCN +V ，我们还选择额外的 500个标记数据作为验证集。

     • 对于 GCN -V，我们仅简单地优化 GCN 的训练 accuracy 。

     • 对于所有方法，我们分别评估不同规模的训练标记数据的效果：

       • 在 Cora,CiteSeer 数据集上，训练标记数据规模分别为 0.5%, 1%, 2%, 3%, 4%, 5% 。
       • 在 PubMed 数据集上，训练标记数据规模为 0.03%, 0.05%, 0.1%, 0.3% 。

       我们选择这些比例是为了方便和 《Semisupervised classification with graph convolutional networks》 的实验结果进行比较。

     对于 Cora,CiteSeer 数据集，每种方法执行 50 轮并报告平均的 accuracy；对于 PubMed 数据集，每种方法执行 10 轮并报告平均的 accuracy 。

4. 不同方法在各数据集上的效果如下表所示，其中每列测试准确率最高的方法以粗体突出显示，top 3 方法以下划线显示。

   结论：

   • 在每个数据集上，我们的方法大多数情况下都要比其它方法好得多。

   • 如果数据具有很强的流形结构（如 PubMed），则 Co-Training 效果更好；否则 Self-Training 效果更好。Self-Training 在 PubMed 上表现较差，因为它未能充分利用图结构。

   • 当训练标记数据规模较大时，Intersection 效果更好，因为它会过滤很多扩展的、但是无效的标记数据；大多数情况下，Union 表现最佳，因为它为训练集添加了更多种多样的标签数据。

   • 当训练标记数据规模较小时，我们所有的方法都远远超越 GCN-V、并在大多数情况下超越了 GCN +V 。

     这验证了我们的分析，即 GCN 模型无法在标记数据较少时有效地将标签信息传播到整个图。

   • 随着训练标记数据规模的增加，大多数情况下我们的方法仍然优于 GCN +V ，这表明我们方法的有效性。

   • 当训练标记数据规模足够大时，我们方法和 GCN 表现差不多，这表明当标记数据充足时已经可以训练一个良好的 GCN 分类器。

   • Cheby 在大多数情况下表现不佳，这可能是由于过拟合造成的。

   

   

   

5. 我们将我们的方法和其它 state-of-the-art 方法比较，比较结果如下表所示。实验配置和前面的相同，除了对于每个数据集我们对每个类别采样 20 个训练标记数据，这对应于 CiteSeer 训练集大小 3.6%、Cora 的 5.1%、PubMed 的 0.3% 。

   其它 baseline 直接拷贝自 《Semisupervised classification with graph convolutional networks》。

   结论：我们方法的效果和 GCN 类似，并明显优于其它 baseline 方法。

   

6. 我们方法一个常用的超参数是新添加标记数据的数量：添加太多标记数据会引入噪声，添加太少标记数据则无法训练出良好的 GCN 分类器。

   如前文所述，我们估计训练 GCN 所需要的总的标记数据量$\eta$$ \eta $ 的下界为：

   $${\left(\hat{d}\right)}^{\tau }\times \eta \simeq n$$

   我们在实验中选择$3\eta$$ 3\eta $ 。实际上我们发现选择$2\eta ,3\eta ,4\eta$$ 2\eta, 3\eta,4\eta $ 的效果差不多。

7. 我们遵循 《Semisupervised classification with graph convolutional networks》 将卷积层数量设为 2 。我们观察到 2 层 GCN 表现最好。当卷积层数量增加时，分类准确率急剧下降，这可能是因为过度平滑。

8. 计算代价：

   • 对于 Co-Training，额外的计算开销是随机游走模型，这需要求解$\mathbf{R}=(\mathbf{\Lambda }+\mathbf{L}{)}^{-1}\mathbf{\Lambda }$$ \mathbf R = (\mathbf \Lambda + \mathbf L)^{-1} \mathbf \Lambda $ 。在我们的实验中，由于 Cora/CiteSeer 只有数千个节点，因此计算时间几乎可以忽略不记；而 PubMed 在 Matlab R2015b 上花的时间也不到 0.38 秒。

     我们可以使用基于节点的 graph engine 进一步加速计算速度，因此我们方法的可扩展性不是问题。

   • 对于 Self-Training，我们只需要训练 GCN 几个额外的 epoch，它建立在预先训练好的 GCN 之上，因此收敛速度很快。因此 Self-Training 训练时间和 GCN 相当。