Question

1. CNN 在很多领域已经获得巨大成功，如图像领域、NLP 领域。这些领域背后的一个共同点是数据可以由网格结构表示，这使得可以在输入的每个位置上应用卷积算子。但是在很多实际应用中数据是图结构，如社交网络、引文网络、生物网络。网格结构是图结构的特殊情况，因此将图像领域的深度学习模型（尤其是 CNN）推广到图结构数据很有吸引力。

   但是，在图结构数据上应用常规卷积算子面临两个主要挑战。这些挑战来自于这样一个事实：常规卷积算子要求每个节点的邻域节点数量不变，并且这些邻域节点是有序的。论文 《Large-Scale Learnable Graph Convolutional Networks》 为解决这些挑战提出了优雅的解决方案。

   两个挑战：图数据中，不同节点的邻域节点数量不同，并且邻域节点没有排序信息。

   最近的一些研究试图将卷积算子推广到通用图结构：

   • GCN 提出使用类似卷积的运算来聚合每个节点的所有邻域节点的特征，然后进行线性变换来生成给定节点的新的 representation 。可以将其视为类似于卷积的运算，但是它在两个方面和常规的卷积算子有本质的不同：

     • 首先，它不使用相同的局部滤波器来扫描每个节点。即，邻域数量不同的节点具有不同尺寸size 和权重的滤波器。

     • 其次，对于感受野receptive field中所有的邻域节点，滤波器中的权重均相同，权重为$\frac{1}{|{\mathcal{N}}_i|}$$ \frac {1}{|\mathcal N_i|} $ ，其中${\mathcal{N}}_i$$ \mathcal N_i $ 为中心节点$v_i$$ v_i $ 的邻域。因此滤波器的权重是不可训练的。

       相比之下，CNN 滤波器的权重是可训练的。

   • GAT 采用注意力机制，通过衡量邻域节点的特征向量和中心节点的特征向量之间的相关性，从而获得邻域节点的不同、且可训练的权重。

     但是，graph attention 操作仍然不同于常规卷积，后者直接学习局部滤波器的权重。此外，注意力机制需要根据成对的特征向量进行额外的计算，从而在实践中导致过多的内存和计算资源需求。

   和这些方法不同，论文《Large-Scale Learnable Graph Convolutional Networks》 为在通用图结构数据上应用 CNN 做出了两个主要贡献：

   • 首先，论文提出可学习的图卷积层learnable graph convolutional layer: LGCL ，以便能够在图上使用常规的卷积运算。

     注意：之前的研究修改了原始卷积运算来适配图数据。相比之下， LGCL 修改了图数据来适配卷积运算。LGCL 为每个特征维度根据取值的排名自动选择固定数量的邻域节点，以便将graph 数据转换为 1-D 格式的网格结构，从而可以在通用的 graph 上应用卷积运算。

     实验结果表明，基于 LGCL 的模型在 transductive learning 和 inductive learning 的节点分类任务上均表现出更好的性能。

   • 其次，论文观察到现有方法的另一个局限性，即：现有的训练过程将整个图的邻接矩阵作为输入。当图包含大量节点时，这需要过多的内存和计算资源。

     为克服这一局限性，论文提出了一种子图训练方法sub-graph training method 。该方法是一种简单而有效的方法，可以对大规模图数据进行训练。子图训练方法可以显著减少所需的内存和计算资源，而在模型性能方面的损失可以忽略不计。

31.1 模型

31.1.1 背景和相关工作

1. 给定图$\mathcal{G}=(\mathcal{V},\mathcal{E})$$ \mathcal G=(\mathcal V,\mathcal E) $ ，其中$\mathcal{V}=\{v_1,\cdots ,v_n\}$$ \mathcal V=\{v_1,\cdots,v_n\} $ 为节点集合，$\mathcal{E}=\{e_{i,j}\}$$ \mathcal E=\{e_{i,j}\} $ 为边集合。

   • 每个节点$v_i$$ v_i $ 关联一个特征向量${\overrightarrow{\mathbf{x}}}_i\in {\mathbb{R}}^{d_f}$$ \mathbf{\vec x}_i\in \mathbb R^{d_f} $ ，所有节点的特征向量组成特征矩阵$\mathbf{X}\in {\mathbb{R}}^{n\times d_f}$$ \mathbf X\in \mathbb R^{n\times d_f} $ 。
   • 令$\mathbf{A}$$ \mathbf A $ 为邻接矩阵，$\mathbf{D}$$ \mathbf D $ 为degree度矩阵。$\hat{\mathbf{A}}=\mathbf{A}+\mathbf{I}$$ \hat{\mathbf A}=\mathbf A +\mathbf I $ 为带自环的邻接矩阵。$\hat{\mathbf{D}}$$ \hat{\mathbf D} $ 为对应的 degree 矩阵。

2. GCN 模型中，每一层的操作可以表示为：

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

   其中：

   • ${\mathbf{H}}^{(l)}\in {\mathbb{R}}^{n\times d_l}$$ \mathbf H^{(l)}\in \mathbb R^{n\times d_l} $ 为第$l$$ l $ 层所有节点的 embedding 矩阵，${\mathbf{H}}^{(0)}=\mathbf{X}$$ \mathbf H^{(0)}=\mathbf X $ 。
   • ${\mathbf{W}}^{(l)}\in {\mathbb{R}}^{d_l\times d_{l+1}}$$ \mathbf W^{(l)}\in \mathbb R^{d_l\times d_{l+1}} $ 为第$l$$ l $ 层可训练的权重矩阵。
   • $\sigma (\cdot )$$ \sigma(\cdot) $ 为非线性激活函数，如 ReLU 函数。

   可以看到该操作类似于卷积运算：每个节点的感受野由其本身和邻域节点组成，然后在感受野上应用一个局部滤波器。但是这种运算和 CNN 中的常规卷积运算有两点区别：

   • 通常图数据中不同节点具有不同数量的邻域节点，这使得不同节点的感受野大小有所不同，从而导致不同的局部滤波器。这是和常规卷积运算的主要区别，在常规卷积运算中，网格数据的每个输入位置都使用相同的滤波器。
   • 此外，即使对图数据使用大小不同的局部滤波器似乎是合理的，但是值得注意的是${\hat{\mathbf{D}}}^{-1/2}\hat{\mathbf{A}}{\hat{\mathbf{D}}}^{-1/2}$$ \hat{\mathbf D}^{-1/2}\hat{\mathbf A}\hat{\mathbf D}^{-1/2} $ 中没有可训练的参数。即，每个邻域节点在加权和中的权重是相同的，即简单的取平均。这和常规卷积运算也有所区别，在常规卷积运算中，每个位置的权重是可训练的参数。

   因此，GCN 中这种不可训练的聚合操作限制了 CNN 在通用图数据上的能力。

   两点区别：GCN 中每个节点采用不同的滤波器（滤波器不会跨节点共享，且滤波器的尺寸不固定），且滤波器是不可训练的。

3. GAT 试图通过注意力机制来聚合邻域特征向量，从而使得学习聚合权重成为可能。

   像 GCN 一样，GAT 中每个节点仍然具有局部滤波器，其感受野包含节点本身及其邻域。当执行特征向量的加权和时，每个邻居节点都通过衡量它与中心节点之间的相关性来接收不同的权重。

   正式地，在第$l$$ l $ 层对于节点$v_i$$ v_i $ 及其邻域节点$v_j$$ v_j $ ，其相关性计算为：

   $$\begin{array}{c}{e}_{i,j}^{(l)}=a^{(l)}({\mathbf{W}}^{(l)}{\overrightarrow{\mathbf{h}}}_i^{(l)},{\mathbf{W}}^{(l)}{\overrightarrow{\mathbf{h}}}_j^{(l)})\in \mathbb{R}\\ {\alpha }_{i,j}^{(l)}={\text{softmax}}_j(e_{i,j}^{(l)})=\frac{\exp (e_{i,j}^{(l)})}{\sum _{k\in {\mathcal{N}}_i}\exp (e_{i,k}^{(l)})}\end{array}$$

   其中：

   • $a^{(l)}(\cdot ,\cdot )$$ a^{(l)}(\cdot,\cdot) $ 为一个单层前馈神经网络，可以选择为：

     $$a^{(l)}({\mathbf{W}}^{(l)}{\overrightarrow{\mathbf{h}}}_i^{(l)},{\mathbf{W}}^{(l)}{\overrightarrow{\mathbf{h}}}_j^{(l)})={\overrightarrow{\mathbf{a}}}^{(l)}\cdot [{\mathbf{W}}^{(l)}{\overrightarrow{\mathbf{h}}}_i^{(l)},{\mathbf{W}}^{(l)}{\overrightarrow{\mathbf{h}}}_j^{(l)}]$$

     ${\overrightarrow{\mathbf{a}}}^{(l)}$$ \mathbf{\vec a}^{(l)} $ 为第$l$$ l $ 层的 attention 向量。

   • ${\mathbf{W}}^{(l)}$$ \mathbf W^{(l)} $ 为第$l$$ l $ 层的权重矩阵，它在所有节点上共享。

   • ${\alpha }_{i,j}^{(l)}$$ \alpha_{i,j}^{(l)} $ 为节点$v_j$$ v_j $ 对于中心节点$v_i$$ v_i $ 的 attention 权重。

   • ${\mathcal{N}}_i$$ \mathcal N_i $ 为节点$v_i$$ v_i $ 的邻域集合。注意这里${\mathcal{N}}_i$$ \mathcal N_i $ 包含节点$v_i$$ v_i $ 本身。

   尽管通过这种方式 GAT 向不同的邻域节点提供了不同、且可训练的权重，但学习权重的过程和常规 CNN 的学习过程不同。在常规 CNN 中，直接学习局部滤波器的权重。

   另外，注意力机制需要在中心节点和所有邻域节点之间进行额外的计算，这在实践中会引起内存和计算资源的问题。

4. 和现有的这些修改常规卷积运算使得其适合通用的图数据不同，我们提出将图转换为类似网格的数据来直接应用 CNN。这个想法以前在 《Learning convolutional neural networks for graphs》 中有所探讨，但是该论文中的变换是在预处理过程中实现的。而我们的方法在模型中包含转换。

   此外，我们的工作还提出了一种子图训练方法，这是一种允许大规模图的训练的简单而有效的方法。

31.1.2 LGCL

1. 这里我们介绍通用图数据的可学习图卷积层learnable graph convolutional layer:LGCL 。

   LGCL 的传播规则为：

   $$\begin{array}{c}{\tilde{\mathbf{H}}}^{(l)}=g({\mathbf{H}}^{(l)},\mathbf{A},k)\in {\mathbb{R}}^{n\times (k+1)\times d_l}\\ {\mathbf{H}}^{(l+1)}=c\left({\tilde{\mathbf{H}}}^{(l)}\right)\in {\mathbb{R}}^{n\times d_{l+1}}\end{array}$$

   其中：

   • $\mathbf{A}$$ \mathbf A $ 为邻接矩阵。${\mathbf{H}}^{(l)}\in {\mathbb{R}}^{n\times d_l}$$ \mathbf H^{(l)}\in \mathbb R^{n\times d_l} $ 为第$l$$ l $ 层所有节点的 embedding 矩阵，${\mathbf{H}}^{(0)}=\mathbf{X}$$ \mathbf H^{(0)}=\mathbf X $ 。
   • $g(\cdot )$$ g(\cdot) $ 为选择 k-largest 节点并将通用图结构转换为网格数据的操作。
   • $c(\cdot )$$ c(\cdot) $ 为常规的 1-D CNN 来聚合邻域信息并为每个节点输出新的 representation 向量。

   下面我们分别讨论$g(\cdot )$$ g(\cdot) $ 和$c(\cdot )$$ c(\cdot) $ 。

2. k-largest node selection$g(\cdot )$$ g(\cdot) $ ：我们提出一种称之为 k-largest node selection 的新颖方法，从而实现从图数据到网格数据的转换，其中$k$$ k $ 为 LGCL 的超参数。

   执行该操作后，每个节点将聚合来自邻域的信息，并表示为具有$(k+1)$$ (k+1) $ 个位置的一维网格。然后我们将转换后的数据馈入1D-CNN 来更新representation 向量。

   假设${\mathbf{H}}^{(l)}\in {\mathbb{R}}^{n\times d_l}$$ \mathbf H^{(l)}\in \mathbb R^{n\times d_l} $ ，第$i$$ i $ 行${\overrightarrow{\mathbf{h}}}_i^{(l)}\in {\mathbb{R}}^{d_l}$$ \mathbf{\vec h}_i^{(l)}\in \mathbb R^{d_l} $ 表示节点$v_i$$ v_i $ 在第$l$$ l $ 层的representation 。$d_l$$ d_l $ 为第$l$$ l $ 层representation 的维度。

   给定邻接矩阵$\mathbf{A}\in {\mathbb{R}}^{n\times n}$$ \mathbf A\in \mathbb R^{n\times n} $ 以及固定的大小$k$$ k $ ，现在考虑节点$v_i$$ v_i $ 及其邻域。假设邻域节点分别为${\mathcal{N}}_i=\{v_{i_1},\cdots ,v_{i_m}\}$$ \mathcal N_i=\{v_{i_1},\cdots,v_{i_m}\} $ ，其中$m$$ m $ 为节点$v_i$$ v_i $ 邻域节点数量。我们将这些邻域节点的 representation 向量拼接为矩阵：

   $$\begin{array}{c}{\mathbf{M}}_i^{(l)}=\left[\begin{array}{c}{\left({\overrightarrow{\mathbf{h}}}_{i_1}^{(l)}\right)}^{\mathrm{\top }}\\ ⋮\\ {\left({\overrightarrow{\mathbf{h}}}_{i_m}^{(l)}\right)}^{\mathrm{\top }}\end{array}\right]\in {\mathbb{R}}^{m\times d_l}\end{array}$$

   不失一般性假设$m\ge k$$ m\ge k $ ，如果$m<k$$ m\lt k $ 则我们将${\mathbf{M}}_i^{(l)}$$ \mathbf M^{(l)}_i $ 填充全为零的行。

   k-largest 节点选择是在${\mathbf{M}}_i^{(l)}$$ \mathbf M_i^{(l)} $ 上进行的。在每一列上，我们对$m$$ m $ 行的数据进行排序，并选择最大的$k$$ k $ 个值。因此我们得到一个${\mathbb{R}}^{k\times d_l}$$ \mathbb R^{k\times d_{l}} $ 的输出矩阵。由于${\mathbf{M}}_i^{(l)}$$ \mathbf M_i^{(l)} $ 中的列代表特征，因此该操作等效于为每个特征选择 k-largest 个节点。

   注意，这里是对每一列单独进行排序，而不是根据维度取值来对节点进行排序。此外，这里不仅仅是选择了最大的$k$$ k $ 个值，而且还进行了排序。固定数量的邻域、且邻域节点有序，这运行 CNN 卷积的要求。

   这里的核心的两个操作是：如何 select、如何 sort 。除了论文里提到的这种维度独立的选择和排序，还可以选择样本独立的选择和排序：从第一个维度到最后一个维度，依次选择$k/d_l$$ k/d_l $ 个该维度取值最大的节点，然后依次拼接起来。

   最后，我们将${\overrightarrow{\mathbf{h}}}_i^{(l)}$$ \mathbf{\vec h}_i^{(l)} $ 插入到输出矩阵的第一行，得到最终的输出矩阵${\tilde{\mathbf{M}}}_i^{(l)}\in {\mathbb{R}}^{(k+1)\times d_l}$$ \tilde{\mathbf M}^{(l)}_i\in \mathbb R^{(k+1)\times d_l} $ 。这一过程如下图所示。下图给出了$k=4$$ k=4 $ 的 k-largest node selection 过程：中心节点具有6 个邻居；对于每个特征，根据特征取值从邻域中选择四个最大的值；最后将中心节点自己的特征拼接起来得到$(k+1)$$ (k+1) $ 个特征向量。

   通过在每个节点上应用这一过程，$g(\cdot )$$ g(\cdot) $ 将${\mathbf{H}}^{(l)}$$ \mathbf H^{(l)} $ 转换为${\tilde{\mathbf{H}}}^{(l)}\in {\mathbb{R}}^{n\times (k+1)\times d_l}$$ \tilde{\mathbf H}^{(l)}\in \mathbb R^{n\times (k+1)\times d_l} $ 。${\tilde{\mathbf{H}}}^{(l)}$$ \tilde{\mathbf H}^{(l)} $ 可以视为一个 1D 网格数据，其中$n$$ n $ 为batch size、$k+1$$ k+1 $ 为空间尺寸、$d_l$$ d_l $ 为通道数。因此，k-largest node selection 函数$g(\cdot )$$ g(\cdot) $ 成功地实现了从通用图数据到网格数据的转换。

   k-largest node selection 操作利用了实数之间的自然排名信息，并强制每个节点具有固定数量的有序邻居。

   

3. 1D-CNN$c(\cdot )$$ c(\cdot) $ ：如前所述，常规卷积运算可以直接应用于网格数据。由于${\tilde{\mathbf{H}}}^{(l)}$$ \tilde{\mathbf H}^{(l)} $ 可以视为一个 1D 网格数据，因此我们采用1-D CNN 模型$c(\cdot )$$ c(\cdot) $ 。

   LGCL 的基本功能是聚合邻域信息并更新每个节点的 representation，因此 1-D CNN$c(\cdot )$$ c(\cdot) $ 将${\tilde{\mathbf{H}}}^{(l)}\in {\mathbb{R}}^{n\times (k+1)\times d_l}$$ \tilde{\mathbf H}^{(l)}\in \mathbb R^{n\times (k+1)\times d_l} $ 作为输入、将${\mathbf{H}}^{(l+1)}\in {\mathbb{R}}^{n\times d_{l+1}}$$ \mathbf H^{(l+1)}\in \mathbb R^{n\times d_{l+1}} $ 作为输出。其中$c(\cdot )$$ c(\cdot) $ 将空间维度从$(k+1)$$ (k+1) $ 缩减为 1 。

   • $n$$ n $ 被视为 batch size，它和$c(\cdot )$$ c(\cdot) $ 的设计无关。因此我们只关注于单个数据样本，即图中的一个节点。

   • 考虑节点$v_i$$ v_i $ ，经过k-largest node selection转换的输出为${\tilde{\mathbf{M}}}_i^{(l)}\in {\mathbb{R}}^{(k+1)\times d_l}$$ \tilde{\mathbf M}^{(l)}_i\in \mathbb R^{(k+1)\times d_l} $ ，它将被作为$c(\cdot )$$ c(\cdot) $ 的输入。

     由于任何常规卷积算子（滤波器尺寸大于 1 并且没有填充）都会减小空间尺寸，因此最简单的$c(\cdot )$$ c(\cdot) $ 仅具有一个卷积层，滤波器大小为$(k+1)$$ (k+1) $ 、没有填充、输入通道数为$d_l$$ d_l $ 、输出通道数为$d_{l+1}$$ d_{l+1} $ 。

     同时，也可以使用任何多层 CNN，只要其最终输出的尺寸为$1\times d_{l+1}$$ 1\times d_{l+1} $ 。

   • 同样地，对所有$n$$ n $ 个节点应用$c(\cdot )$$ c(\cdot) $ 会输出${\mathbf{H}}^{(l+1)}\in {\mathbb{R}}^{n\times d_{l+1}}$$ \mathbf H^{(l+1)}\in \mathbb R^{n\times d_{l+1}} $ 。

   总之，我们的 LGCL 使用 k-largest node selection 方法将通用的图数据转换为网格数据，并应用标准的1-D CNN 进行特征聚合从而为每个节点更新 representation。

4. 下图为 LGCL 的一个例子。考虑具有6个邻域节点的中心节点（橙色表示），每个节点具有3维特征（特征由三个分量的特征向量来表示）。LGCL 选择邻近的$k=4$$ k=4 $ 个节点来生成网格数据，并应用 1-D CNN 来更新中心节点的 representation 。

   • 左侧描述了从邻域中为每个特征选择 k-largest 节点的过程。
   • 右侧给出了通过 1-D CNN 作用于生成的网格数据并得到中心节点的 representation 。输出为 5 维特征（输出通道数为 5 ）。

   这里1-D CNN 的输入通道数和输出通道数都不相同，并且 1-D CNN 可以为任何 CNN 模型。

   这里采用了两层的 1-D 卷积：第一层输入通道数为 3、输出通道数为 4；第二层输入通道数为 4、输出通道数为 5 。

   

31.1.3 LGCN

1. 众所周知更深的网络通常会产生更好的性能，但是之前 GCN 之类的图模型通常只有两层，因为它们层数加深时会受到性能损失。但是在我们的 LGCL 中可以采用更深的层，从而为图节点分类提供可学习的图卷积网络 learnable graph convolutional networks: LGCNs 。

   我们基于 densely connected convolutional networks:DCNNs 体系架构来构建 LGCN，因为 DCNNs 在 ImageNet 分类挑战中获得了 state-of-the-art 性能。

   • 在 LGCN 中，我们首先应用一个 graph embedding layer 来生成节点的低维representation。因为某些图数据集中，原始输入通常是很高维度的特征向量。

     第一层中的 graph embedding layer 实际上是一个线性变换，即：

     $${\mathbf{H}}^{(1)}=\mathbf{X}{\mathbf{W}}^{(0)}$$

     其中：

     • $\mathbf{X}\in {\mathbb{R}}^{n\times d_f}$$ \mathbf X\in \mathbb R^{n\times d_f} $ 为输入特征矩阵。
     • ${\mathbf{W}}^{(0)}\in {\mathbb{R}}^{d_f\times d_1}$$ \mathbf W^{(0)}\in \mathbb R^{d_f\times d_1} $ 将特征空间维度从$d_f$$ d_f $ 转换到$d_1$$ d_1 $ ，其中$d_1<d_f$$ d_1\lt d_f $ 。

     也可以使用一个 GCN layer 作为 graph embedding layer。

   • 在 graph embedding layer 之后，根据图数据的复杂性，我们堆叠了多个 LGCL 。由于每个 LGCL 仅聚合来自于一阶邻域的信息，因此多个 LGCL 可以收集到更大感受野中的信息。

     为了提高模型性能并简化训练过程，我们应用了 skip-connection 来连接 LGCL 的输入和输出。

   • 最后，我们在softmax 输出层之前采用一个全连接层。

2. 遵循 LGCNs 的设计原理，$k$$ k $ 以及 LGCL 堆叠层数是最重要的超参数。

   • 图中节点的平均 degree 可以作为选择$k$$ k $ 的良好参考。
   • LGCL 层的数量取决于任务的复杂性，如类别数量、图中节点数量等。通常更复杂的任务需要更深度的模型。

3. LGCN 的一个例子如下图所示。在这个例子中，输入的节点具有两维特征。

   • 首先，我们使用 graph embedding layer 将输入特征向量转换为低维 representation 。

   • 然后，我们使用两个 LGCL 层，每个 LGCL 层和 skip-connection 堆叠在一起。

     注意：LGCL 层和 skip-connection 输出是拼接起来，而不是相加。

   • 最后，使用一个全连接层和 softmax 输出层用于节点分类。这里有三个不同的类别。

   

31.1.4 子图训练

1. 通常而言，在训练期间，图模型的输入是所有节点的特征向量及整个图的邻接矩阵。这些模型可以在小规模图上正常工作。但是对于大规模图，这些方法通常会导致过多的内存和计算资源需求，从而限制了这些模型的实际应用。

   对于其它类型的数据（如网格数据）的深度神经网络，也会遇到类似的问题。如，在处理大尺寸图像时，模型通常使用随机裁剪的 patch 。受到该策略的启发，我们打算随机 “裁剪” graph 从而获得较小的graph来进行训练。

   但是，图像的矩形 patch 自然地保持了像素之间的相邻信息，而如何处理图中的节点之间的不规则连接仍然具有挑战性。这里我们提出了一种子图选择算法来解决大规模图数据上的内存和计算资源问题。

   具体而言，给定一个图：

   • 我们首先对一些初始节点进行采样。
   • 从这些节点开始，我们使用广度优先搜索BFS 算法将相邻节点迭代地扩展到子图中。
   • 通过多次迭代，我们得到了初始节点和它们的高阶邻域节点。

2. Sub-Graph Selection Algorithm：

   • 输入：

     • 邻接矩阵$\mathbf{A}$$ \mathbf A $
     • 所有节点数量$n$$ n $
     • 子图大小$n_s$$ n_s $
     • 初始的节点数量$n_{\text{init}}$$ n_{\text{init}} $
     • 每轮迭代扩展的最大节点数量$n_m$$ n_m $ （即，每轮广度搜索时，最多添加多少个节点进来）

   • 输出：子图的节点集合$\mathcal{S}$$ \mathcal S $

   • 算法步骤：

     • 初始化$\mathcal{S}$$ \mathcal S $ 为空：$\mathcal{S}=\varphi$$ \mathcal S = \phi $ 。

     • 从$n$$ n $ 个节点中随机采样$n_{\text{init}}$$ n_{\text{init}} $ 个初始节点，这些节点集合记作${\mathcal{V}}_{\text{init}}$$ \mathcal V_{\text{init}} $ 。

     • 更新$\mathcal{S}=\mathcal{S}\cup {\mathcal{V}}_{\text{init}}$$ \mathcal S = \mathcal S\cup \mathcal V_{\text{init}} $ 。

     • 记${\mathcal{V}}_{\text{newadd}}={\mathcal{V}}_{\text{init}}$$ \mathcal V_{\text{newadd}} = \mathcal V_{\text{init}} $ 。

     • 当$|\mathcal{S}|<n_s$$ |\mathcal S|\lt n_s $ 且$|{\mathcal{V}}_{\text{newadd}}|\ne 0$$ |\mathcal V_{\text{newadd}} |\ne 0 $ ，则迭代。迭代步骤为：

       • 候选节点集合为${\mathcal{V}}_{\text{candidate}}=\text{BFS}({\mathcal{V}}_{\text{newadd}},\mathbf{A})$$ \mathcal V_\text{candidate} = \text{BFS}(\mathcal V_{\text{newadd}},\mathbf A) $ 。即获取${\mathcal{V}}_{\text{newadd}}$$ \mathcal V_{\text{newadd}} $ 中所有节点的一阶邻居。

       • 更新${\mathcal{V}}_{\text{newadd}}={\mathcal{V}}_{\text{candidate}}-\mathcal{S}$$ \mathcal V_{\text{newadd}}= \mathcal V_\text{candidate} - \mathcal S $ ，即二者的差集。然后调整${\mathcal{V}}_{\text{newadd}}$$ \mathcal V_\text{newadd} $ 的规模：

         • 如果$|{\mathcal{V}}_{\text{newadd}}|>n_m$$ |\mathcal V_{\text{newadd}}|\gt n_m $ ，则从${\mathcal{V}}_{\text{newadd}}$$ \mathcal V_{\text{newadd}} $ 中随机采样$n_m$$ n_m $ 个节点来作为新的${\mathcal{V}}_{\text{newadd}}$$ \mathcal V_{\text{newadd}} $ 。否则不用随机采样。
         • 如果$|{\mathcal{V}}_{\text{newadd}}|+|\mathcal{S}|>n_s$$ |\mathcal V_{\text{newadd}}|+|\mathcal S|\gt n_s $ ，则从${\mathcal{V}}_{\text{newadd}}$$ \mathcal V_{\text{newadd}} $ 中随机采样$n_s-|\mathcal{S}|$$ n_s - |\mathcal S| $ 个节点来作为新的${\mathcal{V}}_{\text{newadd}}$$ \mathcal V_{\text{newadd}} $ 。否则不用随机采样。

       • 更新$\mathcal{S}=\mathcal{S}\cup {\mathcal{V}}_{\text{newadd}}$$ \mathcal S = \mathcal S\cup \mathcal V_{\text{newadd}} $ 。

   注：为简单期间这里我们使用单个参数$n_m$$ n_m $ 。实际上我们可以为每次迭代选择不同的$n_m$$ n_m $ 值。

3. 下图是一个子图选择过程的示例。我们从$n_{\text{init}}=3$$ n_{\text{init}} = 3 $ 个随机采样的节点开始，最终得到$n_s=15$$ n_s=15 $ 个节点的子图。

   • 在第一次迭代中，我们使用 BFS 查找 3 个初始节点（橙色）中的所有一阶相邻节点（不包括它们自己）。在这些节点中，我们随机选择$|{\mathcal{V}}_{\text{newadd}}|=5$$ |\mathcal V_\text{newadd}|=5 $ 个节点（蓝色）。
   • 在下一次迭代中，我们从蓝色节点的邻居中选择$|{\mathcal{V}}_{\text{newadd}}|=7$$ |\mathcal V_\text{newadd}|=7 $ 个节点（绿色）。

   经过两次迭代，我们选择了 3+5+7=15 个节点并获得了所需的子图。这些节点以及相应的邻接矩阵将在训练迭代期间作为 LGCN 的输入。

   

4. 有了这样的随机 “裁剪” 子图，我们就能够在大规模图上训练深度模型。

   此外，我们可以利用 mini-batch 训练策略来加速学习过程。在每次训练迭代中，我们可以使用提出的子图选择算法来采样若干个子图，然后将这些子图放到 mini-batch 中。相应的特征向量和邻接矩阵构成了网络的输入。

   子图采样也可以作为 GNN 的通用策略从而帮助 GNN 的 mini-batch 训练。

31.1.5 未来方向

1. 我们的方法主要解决节点分类问题，实践中有些任务需要对图进行分类，即图分类问题。

   但是目前的图卷积方法（包括我们的方法）无法对图进行降采样（类似于图像数据的池化操作），我们需要一个layer 来有效地减少节点数，这是图分类所必须的。

2. 另外，我们的方法主要应用于通用图数据，如引文网络。对于其它数据，如文本，我们的方法也可能会有所帮助，因为我们可以将文本数据视为图。

31.2 实验

1. 我们评估在 transductive learning 和 inductive learning 环境下 LGCN 在大规模图的节点分类任务上的表现。

   另外，除了和 state-of-the-art 模型进行比较之外，我们还进行了一些性能研究，从而研究如何选择超参数。

   最终实验结果表明，LGCN 可以提高性能，并且子图训练比全图训练更有效。

2. 数据集：

   • transduction Learning：在 transductive learning 环境下，未标记的测试节点可以在训练期间访问到，包括测试节点的特征和连接。这意味着训练期间知道包含测试节点的图结构。

     我们使用三个标准的 benchmark 数据集：Cora, Citeseer, Pubmed。这三个数据集是引文网络数据集，节点代表文档、边代表引用关系。每个节点的特征向量是文档的bag-of-word 表示。对于这三个数据集，我们采用和 GCN 中相同的实验设置：对于每个类别，我们选择 20 个节点进行训练、500 个节点进行验证、1000 个节点用于测试。

   • inductive Learning：在 inductive learning 环境下，未标记的测试节点可以在训练期间不可用。这意味着训练期间不知道测试图的结构。

     在 inductive learning 环境下，我们通常具有不同的训练图、验证图、测试图。在训练期间模型仅使用训练图、而无法访问验证图和测试图。

     我们使用 protein-protein interaction: PPI 数据集，其中包含 20 个训练图、2 个验证图、2 个测试图。由于验证图和测试图是独立的，因此训练过程中不会使用它们。平均每个图包含 2372 个节点，每个节点包含 50 个特征。每个节点都有来自 121 个类别的多个标签。

   下表给出这些数据集的统计量。degree 属性是每个数据集的平均节点 degree，这有助于选择 LGCL 中的超参数$k$$ k $ 。

   

3. 实验配置：

   • transduction Learning：

     • 由于 transductive learning 数据集使用高维的bag-of-word 作为特征向量，因此输入经过 graph embedding layer 来减小维度。

       这里我们使用 GCN layer 来作为 graph embedding layer，embedding 的输出维度为 32。

     • 然后我们使用 LGCL，每个 LGCL 使用$k=8$$ k=8 $ 并产生维度为 8 的特征向量。对于 Cora/Citesser/Pubmed，我们分别堆叠了 2/1/1 个 LGCL。

       另外，我们在 skip-connection 中使用拼接操作。

     • 最后，将全连接层用作分类器以进行预测。在全连接层之前，我们执行一个简单的sum 操作来聚合邻域节点的特征向量。

     • 在每一层的输入特征向量和邻接矩阵上都应用 dropout，dropout 比例分别为 0.16 和 0.999 。

     • 所有 LGCN 模型都使用子图训练策略，子图大小设置为 2000 。

   • inductive Learning：除了某些超参数之外，使用和 transductive learning 相同的配置。

     • 对于 graph embedding layer，输出特征向量维度为 128。
     • 我们堆叠两层 LGCL，$k=64$$ k=64 $ 。
     • 我们还使用子图训练策略，子图初始节点大小等于 500 和 200 。
     • 在每一层应用dropout，dropout 比例为 0.9 。

   • 对于 transductive learning 和 inductive learning ，LGCN 模型共享以下配置：

     • 对于所有层仅使用线性激活函数，这意味着网络中不涉及非线性。
     • 为了避免过拟合，使用$\lambda =0.0005$$ \lambda=0.0005 $ 的 L2 正则化。
     • 训练期间，使用学习率为 0.1 的 Adam 优化器。
     • LGCN 中的权重使用 Glorot 方法初始化。
     • 我们根据验证集准确率来执行早停策略，最多训练 1000 个 epoch 。

4. 实验结果：

   • Transduction Learning 实验结果：我们报告了不同模型在节点分类任务上的准确率。根据结果，LGCN 模型在 Cora, Citeseer, Pubmed 数据集上的性能比 state-of-the-art 的 GCN 分别提高了 1.8%, 2.7%, 0.5% （绝对提升）。其中${\text{LGCN}}_{\text{sub}}$$ \text{LGCN}_{\text{sub}} $ 表示使用子图训练策略的 LGCN 模型。

     

   • Inductive Learning 实验结果：我们报告了不同模型的 micro-averaged F1 得分。根据结果，LGCN 模型的性能比 GraphSAGE-LSTM提高了 16%。这表明在训练期间看不到测试图的情况下，LGCN 模型仍然取得很好的泛化能力。

     

   上述实验结果表明：

   • 在通用的图数据上提出的 LGCN 模型在不同节点分类数据集上一致性地达到 state-of-the-art 性能。
   • 这些结果证明了在变换后的图数据上应用常规卷积运算的有效性。
   • 另外，通过 k-largest node selection 实现的转换方法被证明是有效的。

5. LGCL vs GCL Layer：有人认为LGCN 性能的提高仅仅是因为 LGCN 模型采用的网络体系结构比 GCN 更深。但是，已有论文提出：通过堆叠更多的层来加深 GCN 会导致性能更差。

   因此，这里我们进行另一项实验：将 LGCN 模型中所有 LGCL 替换为 GCN Layer，称之为${\text{LGCN}}_{\text{sub}}\text{-GCN}$$ \text{LGCN}_{\text{sub}}\text{-GCN} $ 模型。所有其它设置保持相同以确保比较的公平性。

   下表给出了${\text{LGCN}}_{\text{sub}}$$ \text{LGCN}_{\text{sub}} $ 和${\text{LGCN}}_{\text{sub}}\text{-GCN}$$ \text{LGCN}_{\text{sub}}\text{-GCN} $ 之间的比较结果，评估指标为测试准确率。结果表明：${\text{LGCN}}_{\text{sub}}$$ \text{LGCN}_{\text{sub}} $ 的性能优于${\text{LGCN}}_{\text{sub}}\text{-GCN}$$ \text{LGCN}_{\text{sub}}\text{-GCN} $ 。这表明 LGCL 比 GCN Layer 更为有效。

   

6. 子图训练vs 全图训练：上述实验中我们使用子图训练策略来训练 LGCN 模型，旨在节省内存和训练时间。但是，由于子图选择算法从整个图中抽取一些节点作为子图，这意味着以这种方式训练的模型在训练过程中不了解整个图的结构。同时，在 transductive learning 环境下，测试节点的信息可能会被忽略，从而增加了性能下降的风险。

   为解决这个问题，我们在 transductive learning 环境下进行实验，从而比较子图训练策略subgraph training strategy 和全图训练策略whole-graph training strategy 。通过实验，我们证明了子图训练策略的优势，同时在模型性能方面的损失可以忽略不计。

   对于子图选择过程，在 transductive learning 环境下我们仅从带有训练标签的节点中采样初始节点，以确保训练可以进行。具体而言，对于 Cora/Citeseer/Pubmed 数据集，我们分别随机采样 140/120/60 个初始节点。在迭代过程中，我们并没有设置$n_m$$ n_m $ 来限制扩展到子图中的节点数，而是设置子图的最大节点数为 2000。对于我们的 GPU 而言这是可行的大小。

   为进行比较，我们使用相同的 LGCN 模型进行实验，但使用和 GCN 相同的全图训练策略来训练它们。这意味着输入是整个图的表示。和使用子图训练策略的${\text{LGCN}}_{\text{sub}}$$ \text{LGCN}_{\text{sub}} $ 相比，我们将模型称之为${\text{LGCN}}_{\text{whole}}$$ \text{LGCN}_{\text{whole}} $ 。

   下表给出了这两种模型和 GCN 的比较结果：报告的节点数表示一次迭代训练使用了多少个节点；报告的时间是使用单个 TITAN Xp GPU 运行 100 个 epoch 的训练时间；报告的准确率是测试准确率。

   可以看到：

   • Cora/Citeseer/Pubmed 数据集的子图训练中，子图的实际节点数量分别为 644/442/354，远小于最大的子图大小 2000 。这表明这三个数据集中的节点是稀疏连接的。具体而言，从带有训练标记的几个初始节点开始，通过扩展相邻节点以形成连接的子图，只会选择一小部分节点。

     尽管通常将这些数据集视为一个大图，但是整个图实际上只是由彼此独立的几个单独的子图组成。子图训练策略利用了这一事实，并有效利用了带训练标签的节点。

     由于只有初始节点具有训练标签，并且所有这些初始节点的连接性信息都包含在所选子图中，因此子图训练中的信息丢失量降到最低，从而导致性能损失几乎可以忽略不计。

     通过对比${\text{LGCN}}_{\text{sub}}$$ \text{LGCN}_{\text{sub}} $ 和${\text{LGCN}}_{\text{whole}}$$ \text{LGCN}_{\text{whole}} $ 的节点分类准确率，可以证明这一点。根据结果，和${\text{LGCN}}_{\text{whole}}$$ \text{LGCN}_{\text{whole}} $ 相比，${\text{LGCN}}_{\text{sub}}$$ \text{LGCN}_{\text{sub}} $ 仅在 Cora 数据集上有 0.5% 的微小性能损失，而在 Citeseer 和 Pubmed 数据集上却具有相同的性能。

   • 在调查了性能损失的风险之后，我们看到子图训练策略在训练速度方面的巨大优势。通过使用子图训练策略，和全图训练策略相比，${\text{LGCN}}_{\text{sub}}$$ \text{LGCN}_{\text{sub}} $ 模型采用较少节点的子图作为输入，这有望大大提高训练效率。

     从结果可以看到，这种训练效率的提升是显著的。尽管 GCN 的计算更简单，它在 Pubmed 之类的大规模图数据集上的运行时间比 LGCN 模型要长的多。

     通常在大规模图数据上应用强大的深度学习模型，这使得子图训练策略在实践中很有用。子图训练策略可以使用更复杂的层，如LGCL，而无需担心训练时间。结果，带有子图训练策略的大型 LGCN 不仅效果好而且效率高。

   

7. 超参数$k$$ k $ 的选择：如前所述，在 LGCN 中选择超参数$k$$ k $ 时，图中的平均节点 degree 会有所帮助。这里我们进行实验来展示不同的$k$$ k $ 值如何影响 LGCN 模型的性能。

   我们在 Cora,Citeseer,Pubmed 数据集上调整$k$$ k $ 值，从而观察节点分类准确率的变化。$k$$ k $ 的值选取自 [2,4,8,16,32]，这覆盖了合理范围内的整数值。

   下图给出了不同$k$$ k $ 值下 LGCN 模型的性能变化。可以看到：

   • LGCN 模型上的所有三个数据集在$k=8$$ k=8 $ 时达到最好性能。在 Cora, Citeseer, Pubmed 数据集中，平均节点 degree 分别为 4/5/6 。这表明最佳的$k$$ k $ 通常比数据集中的平均节点 degree 稍大一点。
   • 当$k$$ k $ 太大时，LGCN 模型的性能会降低。可能的解释是：如果$k$$ k $ 比图中的平均节点 degree 大得多，那么在 k-largest node selection 过程中使用了太多的零填充，这会不利于接下来的 1-D CNN 模型的性能。
   • 对于 PPI 数据集上的 inductive learning 任务，我们也探索了不同的$k$$ k $ 值。最佳性能由$k=64$$ k=64 $ 给出，而平均节点 degree 为 31。这和我们上面讨论的结果一致。