Question

1. 图是 pairwise relationship 的universal representation。许多现实世界的数据自然而然地以 graph 的形式展现，如社交网络、基因表达网络、知识图谱。为了提高 graph-based 学习任务的性能，最近人们努力将已有的网络架构（包括 RNN 和 CNN）推广到 graph 数据。

   虽然学习 graph 的 feature representation 是一个重要主题，但是这里我们重点关注节点的 feature representation 。在这方面，《Semi-supervised classification with graph convolutional networks》提出的 GCN 是最接近 CNN 架构的工作。借助针对图片像素的卷积滤波器的概念，或者信号的 linear array 的概念，GCN 使用图的连通性结构connectivity structure 作为滤波器进行邻域混合 neighborhood mixing 。该架构可以用总结为：

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

   其中：

   • $\hat{\mathbf{A}}$$ \hat{\mathbf A} $ 是图的某个归一化邻接矩阵。
   • ${\mathbf{H}}^{(l)}$$ \mathbf H^{(l)} $ 为图的所有节点在网络第$l$$ l $ 层 embedding 组成的 embedding 矩阵（按行）。
   • ${\mathbf{W}}^{(l)}$$ \mathbf W^{(l)} $ 为网络第$l$$ l $ 层的参数矩阵。
   • $\sigma$$ \sigma $ 为非线性函数。

   与许多图算法一样，邻接矩阵编码了训练数据和测试数据中的 pairwise relationship 。模型的学习和 embedding 是同时在训练数据和测试数据上进行的，至少根据作者的建议而言。然而，对于许多应用程序而言，测试数据可能并不容易获得，因为图可能会不断扩展新的节点（如，社交网络的新成员、推荐系统的新产品、以及用于功能测试的新药物）。这样的场景需要一个归纳式的方案inductive scheme ，该方案仅从训练数据中学习模型并且可以很好地泛化到测试数据。

   因为 GCN 是 transductive 的，因此需要在训练期间就知道测试数据，并同时针对测试数据进行训练。

   GCN 面临的一个更严峻的挑战是：跨层的邻域递归扩展会在 batched training 中产生昂贵的计算。尤其是对于稠密图dense graph和幂率图powerlaw graph，单个节点的邻域扩展会迅速填满图的大部分。然后，即使是一个很小的 batch size ，每个 mini-batch 训练都涉及到大量数据。因此，GCN 难以推广到大型稠密图。

   为解决这两个挑战，《FASTGCN: FAST LEARNING WITH GRAPH CONVOLUTIONAL NETWORKS VIA IMPORTANCE SAMPLING》 从另一个角度考察图卷积，并将图卷积解释为概率测度下 embedding 函数的积分变换。这种观点为归纳式学习inductive learning提供了一种从损失函数的公式到梯度的随机版本的原则性的机制principled mechanism。

   具体来讲，论文将图节点解释为某种概率分布的独立同分布 iid 样本，并将损失函数以及每个卷积层视为节点 embedding 函数的积分。然后通过对积分进行蒙特卡洛模拟来求解，从而得到损失函数和梯度（损失函数和梯度中包含了 embedding 函数的积分）。也可以进一步改变蒙特卡洛模拟中的采样分布（如，重要性采样）来减少积分近似的方差。

   论文所提出的方法称作 FastGCN ，该方法不仅是 inductive 的，并且每个 batch 的计算成本可控。在撰写该论文时，作者注意到新发表的作品 GraphSAGE，其中 GraphSAGE 提出使用采样来减少 GCN 的计算代价。相比而言，FastGCN 的方法代价更低。实验表明，FastGCN 的每个batch 计算速度比 GraphSAGE 快一个量级以上，并且分类准确性相差无几。

2. 相关工作：在过去的几年中，出现了几种graph-based的卷积网络模型，它们用于解决图结构数据的应用，如分子的 representation （《Convolutional networks on graphs for learning molecular fingerprints》）。

   • 一个重要的工作方向是建立在谱图理论上的。它们受到傅里叶变换的启发，在谱域中定义了参数化的滤波器。这些方法学习整个图的 feature representation，并可用于图分类。

   • 另一个工作方向是学习 graph vertex 的 embedding 。《Graph embedding techniques, applications, and performance: A survey》 是最近的一项综述，全面涵盖了几类方法。

     • 一个主要的类别包括基于分解的算法，这些算法通过矩阵分解来产生 embedding 。这些方法共同学习训练数据和测试数据的 representation 。
     • 另一类方法基于随机游走，通过探索邻域来计算 node representation 。LINE 就是这样的一种技术，它的动机是保留一阶邻近性和二阶邻近性。
     • 同时，也出现了一些深度神经网络架构，它们可以更好地捕获图中的非线性，如 SDNE。

     如前所述，我们的工作是基于GCN 模型的。

   与我们工作最相关的工作是 GraphSAGE，它通过聚合邻域信息来学习 node representation。作者还承认所提出的聚合器之一采用了 GCN 架构。作者还承认 GCN 的内存瓶颈，因此提出了一种临时采样方案ad hoc sampling scheme 来限制邻域大小。我们的采样方法基于一个不同的、更有原则的公式。主要区别是我们采样节点而不是邻域。

12.1 模型

1. GCN 和许多标准神经网络架构之间的一个显著区别是：样本损失之间缺乏独立性。诸如随机梯度下降 SGD 以及它的 batch 版本等训练算法是基于损失函数相对于独立数据样本的可加性来设计的。另一方面，对于图，每个节点都与它的所有邻居进行卷积，因此定义一个计算计算高效的样本梯度非常简单。

2. 具体而言，考虑标准的随机梯度下降 SGD ，其中损失函数是某个函数$g$$ g $ 对数据分布$D$$ D $ 的期望，其中$g$$ g $ 为单个样本的损失：

   $$\mathcal{L}={\mathbb{E}}_{\overrightarrow{\mathbf{x}}\sim D}[g(\mathbf{W};\overrightarrow{\mathbf{x}})]$$

   其中$\overrightarrow{\mathbf{x}}$$ \mathbf{\vec x} $ 为单个样本特征，$\mathbf{W}$$ \mathbf W $ 为待学习的模型参数。

   通常数据分布$D$$ D $ 是未知的，因此我们可以用经验损失函数（来代替上述损失函数，即：

   $${\mathcal{L}}_{\text{emp}}=\frac{1}{n}\sum _{i=1}^{n}g(\mathbf{W};{\overrightarrow{\mathbf{x}}}_i),\mathrm{\forall }i,{\overrightarrow{\mathbf{x}}}_i\sim D$$

   其中${\overrightarrow{\mathbf{x}}}_i$$ \mathbf{\vec x}_i $ 为$n$$ n $ 个从分布$D$$ D $ 中采样的 iid 样本。

   在 SGD 的每一步中，梯度近似为$\mathrm{\nabla }g(\mathbf{W};{\overrightarrow{\mathbf{x}}}_i)$$ \nabla g(\mathbf W; \mathbf{\vec x}_i) $ ，它是$\mathrm{\nabla }\mathcal{L}$$ \nabla\mathcal L $ 的一个无偏估计。人们可以解释为：每个梯度的 step 都会朝向着样本损失$g(\mathbf{W};{\overrightarrow{\mathbf{x}}}_i)$$ g(\mathbf W; \mathbf{\vec x}_i) $ 增加的方向（因此，负梯度是最小化的方向）。这里，样本损失和样本梯度仅涉及单个样本${\overrightarrow{\mathbf{x}}}_i$$ \mathbf{\vec x}_i $ 。

3. 对于图，利用样本独立性并通过递归地丢弃邻域节点及其邻域信息来计算样本梯度$\mathrm{\nabla }g(\mathbf{W};{\overrightarrow{\mathbf{x}}}_i)$$ \nabla g(\mathbf W; \mathbf{\vec x}_i) $ ，这是不可行的。因此，我们寻求另一个替代公式。为了在相同的采样框架下解决学习问题，我们假设存在一个（可能无限大）的图$G^{\prime }$$ G^\prime $ ，它包含节点集合$V^{\prime }$$ V^\prime $ 。这个图定义了一个概率空间$(V^{\prime },F,P)$$ (V^\prime, F, P) $ ，其中：

   • $V^{\prime }$$ V^\prime $ 为样本空间。
   • $F$$ F $ 为事件空间。如$F=2^{V^{\prime }}$$ F=2^{V^\prime} $ 表示$V^{\prime }$$ V^\prime $ 中的每个节点是否被选中。
   • $P$$ P $ 为概率测度，它定义了一个采样分布。

   对于给定的图$G$$ G $ ，我们假设$G$$ G $ 为$G^{\prime }$$ G^\prime $ 的诱导子图：$G$$ G $ 的节点是根据概率测度$P$$ P $ 在节点集合$V^{\prime }$$ V^\prime $ 上采样的独立同分布 iid 样本。

   为解决图卷积的损失函数缺乏独立性问题，我们将卷积层定义为节点的 embedding 的函数，不同节点关联了相同的概率测度，但是节点之间相互独立。

   注意，这里每个节点代表一个随机变量。

   具体而言，考虑 GCN 体系架构：

   $$\begin{array}{c}{\tilde{\mathbf{H}}}^{(l+1)}=\hat{\mathbf{A}}{\mathbf{H}}^{(l)}{\mathbf{W}}^{(l)},{\mathbf{H}}^{(l+1)}=\sigma \left({\tilde{\mathbf{H}}}^{(l+1)}\right),l=0,\cdots ,L-1\\ \mathcal{L}=\frac{1}{n}\sum _{i=1}^{n}g\left({\overrightarrow{\mathbf{h}}}_i^{(L)}\right)\end{array}$$

   从函数泛化的角度，我们改写为：

   $$\begin{array}{c}{\widetilde{\overrightarrow{\mathbf{h}}}}^{(l+1)}(v)=\int \hat{A}(v,u){({\overrightarrow{\mathbf{h}}}^{(l)}(u))}^{\mathrm{\top }}{\mathbf{W}}^{(l)}dP(u),{\overrightarrow{\mathbf{h}}}^{(l+1)}(v)=\sigma ({\widetilde{\overrightarrow{\mathbf{h}}}}^{(l+1)}(v)),l=0,\cdots ,L-1\\ \mathcal{L}={\mathbb{E}}_{v\sim P}\left[g({\overrightarrow{\mathbf{h}}}^{(L)}(v))\right]=\int g({\overrightarrow{\mathbf{h}}}^{(L)}(v))dP(v)\end{array}$$

   第一个积分是对邻域聚合的替代，第二个积分是对损失函数求均值的替代。

   其中：

   • $u,v$$ u,v $ 为独立的随机变量，它们都有相同的概率测度$P$$ P $ 。

   • 函数${\overrightarrow{\mathbf{h}}}^{(l)}$$ \mathbf{\vec h}^{(l)} $ 为第$l$$ l $ 层的 embedding 函数。第$l+1$$ l+1 $ 层 embedding 为第$l$$ l $ 层 embedding 的卷积，并通过积分变换来公式化卷积。其中卷积核$\hat{A}(v,u)$$ \hat A(v,u) $ 对应于矩阵$\hat{\mathbf{A}}$$ \hat{\mathbf A} $ 的位置$(v,u)$$ (v,u) $ 的元素。

     注意：积分不是通常的 Riemann–Stieltjes 积分，因为随机变量$u,v$$ u,v $ 为图上的节点。但是这种区别只是形式上的区别而已。

   • ${\mathbf{H}}^{(l)}$$ \mathbf H^{(l)} $ 为第$l$$ l $ 层的 embedding 矩阵，每个节点占据一行。${\overrightarrow{\mathbf{h}}}^{(l)}(v)$$ \mathbf{\vec h}^{(l)}(v) $ 表示${\mathbf{H}}^{(l)}$$ \mathbf H^{(l)} $ 中节点$v$$ v $ 对应的向量。而$({)}^{\mathrm{\top }}$$ ()^\top $ 将列向量转换为行向量。

   • 最终的损失函数是对$g\left({\overrightarrow{\mathbf{h}}}^{(L)}\right)$$ g\left(\mathbf{\vec h}^{(L)}\right) $ 的期望。

4. 我们通过蒙特卡洛模拟来求解上述积分，从而得到 batch 训练算法，并很自然地得到 inductive learning 。

   对于第$l$$ l $ 层，假设我们随机采样得到$t_l$$ t_l $ 个独立同分布的节点$u_1^{(l)},\cdots ,u_{t_l}^{(l)}\sim P$$ u_1^{(l)},\cdots,u_{t_l}^{(l)}\sim P $ ，则得到：

   $$\begin{array}{c}{\widetilde{\overrightarrow{\mathbf{h}}}}_{\ast }^{(l+1)}(v)=\frac{1}{t_l}\sum _{j=1}^{t_l}\hat{A}(v,u_j^{(l)}){\left({\overrightarrow{\mathbf{h}}}_{\ast }^{(l)}\left(u_j^{(l)}\right)\right)}^{\mathrm{\top }}{\mathbf{W}}^{(l)}\\ {\overrightarrow{\mathbf{h}}}_{\ast }^{(l+1)}(v)=\sigma ({\widetilde{\overrightarrow{\mathbf{h}}}}_{\ast }^{(l+1)}(v))\end{array}$$

   其中${\overrightarrow{\mathbf{h}}}_{\ast }^{(l)}(\cdot )$$ \mathbf{\vec h}_* ^{(l)}(\cdot) $ 表示根据蒙特卡洛模拟近似的 embeding 函数。

   最终的损失函数估计为：

   $${\mathcal{L}}_{\ast }=\frac{1}{t_L}\sum _{i=1}^{t_L}g\left({\overrightarrow{\mathbf{h}}}_{\ast }^{(L)}\left(u_i^{(L)}\right)\right)$$

   原理是以蒙特卡洛模拟来执行 “期望公式 -- 积分” 之间的替代，即：“原始公式（期望视角） --> 积分 --> 新公式（期望视角）”。

   要保证结果正确的核心是：大数定理。例如，样本邻域不能太稀疏，否则计算${\widetilde{\overrightarrow{\mathbf{h}}}}_{\ast }^{(l+1)}(v)$$ \tilde{\mathbf{\vec h}}_*^{(l+1)}(v) $ 时可能一个邻居都没有采样到，最终导致模型效果较差。

5. 定理：如果$g(\cdot )$$ g(\cdot) $ 和$\sigma (\cdot )$$ \sigma(\cdot) $ 是连续函数，则$\underset{t_0,\cdots ,t_L\to \mathrm{\infty }}{lim}{\mathcal{L}}_{\ast }$$ \lim_{t_0,\cdots,t_L\rightarrow \infty} \mathcal L_{*} $ 以概率 1 收敛到$\mathcal{L}$$ \mathcal L $ 。

   证明见原始论文，其中依赖于大数定律、连续函数理论（要求激活函数$\sigma (\cdot )$$ \sigma(\cdot) $ 是连续的）。

6. 实际应用中，给定一个图$G$$ G $ ，图的节点被假设为从$V^{\prime }$$ V^\prime $ 中采样的样本。因此我们的蒙特卡洛模拟采样过程中需要 bootstrap 采样从而获得一致的估计。

   给定一个 batch，我们从图$G$$ G $ 中随机采样$t_L$$ t_L $ 个节点。我们在网络每一层进行有放回的采样从而得到样本节点$u_i^{(l)},i=1,\cdots ,t_l;l=0,\cdots ,L-1$$ u_i^{(l)}, i =1,\cdots,t_l; l=0,\cdots,L-1 $ 。该过程等价于在每一层对${\mathbf{H}}^{(l)}$$ \mathbf H^{(l)} $ 的列进行均匀采样。

   注意：在第$L$$ L $ 层的时候我们不需要进行采样，因为第$L$$ L $ 层的${\mathbf{H}}^{(L)}$$ \mathbf H^{(L)} $ 是输出结果。我们将${\mathbf{H}}^{(L)}$$ \mathbf H^{(L)} $ 划分为若干个 batch （注意：这里是划分，而不是采样）。我们使用节点$u_1^{(L)},\cdots ,u_{t_L}^{(L)}$$ u_1^{(L)},\cdots,u_{t_L}^{(L)} $ 来描述一个 batch 的节点，因此得到 batch loss：

   $${\mathcal{L}}_{\text{batch}}=\frac{1}{t_L}\sum _{i=1}^{t_L}g\left({\overrightarrow{\mathbf{h}}}^{(L)}\left(u_i^{(L)}\right)\right)$$

   其中：

   $${\overrightarrow{\mathbf{h}}}^{(l+1)}(v)=\sigma \left(\frac{n}{t_l}\sum _{j=1}^{t_l}\hat{A}(v,u_j^{(l)}){\left({\overrightarrow{\mathbf{h}}}^{(l)}\left(u_j^{(l)}\right)\right)}^{\mathrm{\top }}{\mathbf{W}}^{(l)}\right),l=0,\cdots ,L-1$$

   该公式可以理解为：基于采样的消息传播机制。其中，消息为${\left({\overrightarrow{\mathbf{h}}}^{(l)}\left(u_j^{(l)}\right)\right)}^{\mathrm{\top }}{\mathbf{W}}^{(l)}$$ \left( \mathbf {\vec h}^{(l)}\left(u_j^{(l)}\right)\right)^\top \mathbf W^{(l)} $ ，聚合权重由$\hat{A}(v,u)$$ \hat A(v,u) $ 给出。由于均匀采样，所以采样概率为$1/n$$ 1/n $ ，因此需要除以采样概率从而恢复原始的期望值。

   注意：这里激活函数$\sigma (\cdot )$$ \sigma(\cdot) $ 内部的$n$$ n $ 为图中节点数量，用于解决 GCN 原始的矩阵形式和我们的 embedding 积分形式之间的归一化差异。

   可以通过在每个${\mathbf{H}}^{(l)}$$ \mathbf H^{(l)} $ 上应用链式法则来直接获取相应的 batch 梯度，最终我们得到了 batch 损失以及 batch 梯度。

   理论上讲，如果跨 batch 共享，那么训练速度会更快，但是效果可能会更差。论文这里选择 batch 之间独立地采样，即，不共享。

7. 下图给出了 GCN 的两种观点。

   • 左图：图卷积的观点。每个圆圈表示图中的一个节点。在连续的两行上，如果图中两个节点存在连接，则对应的圆圈以灰线相连（其中部分灰线被橙线覆盖）。卷积层利用图的连接性来融合图的节点特征或者 embedding 。
   • 右图：积分变换的观点。下一层 embedding 函数为前一层 embedding 函数的积分变换，用橙色扇形表示。

   在 FastGCN 中，所有积分（包括损失函数）都是通过蒙特卡洛模拟采样进行评估的。对应于图中，FastGCN 从每一层进行有放回的节点采样从而近似卷积。采样部分由蓝色实体圆圈，以及橙线来表示。例如：

   • 输出层（第二层）的一个 batch 包含三个节点
   • 第一层有放回地随机采样三个节点，通过这三个节点来求解输出层的 embedding
   • 第零层有放回地随机采样三个节点，通过这三个节点来求解第一层三个节点的 embedding

   每个 batch 采样的节点集合（即，输出节点）不同、相同 batch 每一层采样的节点集合不同。

   

8. FastGCN 的 batch 训练算法（一个 epoch）：

   • 输入：

     • 图$G(V,E)$$ G(V,E) $ ，以及图的邻接矩阵$\hat{\mathbf{A}}$$ \hat{\mathbf A} $
     • 学习率$\eta$$ \eta $

   • 输出：更新后的参数${\left\{{\mathbf{W}}^{(l)}\right\}}_{l=0}^{L-1}$$ \left\{\mathbf W^{(l)}\right\}_{l=0}^{L-1} $

   • 算法步骤：

     迭代每个 batch，迭代过程：

     • 对每一层$l$$ l $ ，均匀随机采样$t_l$$ t_l $ 个节点：$u_1^{(l)},\cdots ,u_{t_l}^{(l)}$$ u_1^{(l)},\cdots,u_{t_l}^{(l)} $ 。

     • 对每一层$l$$ l $ ，如果节点$v$$ v $ 在第$l+1$$ l+1 $ 层被采样到，则计算：

       $$\mathrm{\nabla }\widetilde{\overrightarrow{\mathbf{h}}}(v)\leftarrow \frac{n}{t_l}\sum _{j=1}^{t_l}\hat{A}(v,u_j^{(l)})\mathrm{\nabla }\left\{{\left({\overrightarrow{\mathbf{h}}}^{(l)}\left(u_j^{(l)}\right)\right)}^{\mathrm{\top }}{\mathbf{W}}^{(l)}\right\}$$

     • 参数更新：$\mathbf{W}\leftarrow \mathbf{W}-\eta \mathrm{\nabla }{\mathcal{L}}_{batch}$$ \mathbf W\leftarrow \mathbf W-\eta \nabla \mathcal L_{batch} $ 。

12.2 重要性采样

1. 根据前文所述，${\mathcal{L}}_{\ast }$$ \mathcal L_{*} $ 是$\mathcal{L}$$ \mathcal L $ 的一个一致的估计量。现在我们关心这个估计量的方差，期望得到较小的方差。但是，由于网络架构非线性的影响，评估${\mathcal{L}}_{\ast }$$ \mathcal L_{*} $ 的方差非常具有挑战性。因此这里我们考虑每一层的非线性之前 embedding 函数的方差。

   考虑第$l$$ l $ 层，函数${\widetilde{\overrightarrow{\mathbf{h}}}}_{\ast }^{(l+1)}(v)$$ \tilde{\mathbf{\vec h}}_*^{(l+1)}(v) $ 是卷积$\int \hat{A}(v,u){({\overrightarrow{\mathbf{h}}}^{(l)}(u))}^{\mathrm{\top }}{\mathbf{W}}^{(l)}dP(u)$$ \int \hat A(v,u) \left(\mathbf{\vec h}^{(l)}(u) \right)^\top\mathbf W^{(l)} dP(u) $ 的近似。当考虑$t_{l+1}$$ t_{l+1} $ 个样本$v=u_1^{(l+1)},\cdots ,u_{t_{l+1}}^{(l+1)}$$ v=u_1^{(l+1)},\cdots,u_{t_{l+1}}^{(l+1)} $ 时，这些样本的${\widetilde{\overrightarrow{\mathbf{h}}}}_{\ast }^{(l+1)}\left(u_j^{(l+1)}\right)$$ \tilde{\mathbf{\vec h}}_*^{(l+1)}\left(u_j^{(l+1)}\right) $ 的均值存在一个方差，该方差捕获了第$l$$ l $ 层对最终损失函数估计量偏离的贡献。因此，我们现在希望改善这个方差。

   • 这里我们并未考虑单个函数${\widetilde{\overrightarrow{\mathbf{h}}}}_{\ast }^{(l+1)}\left(u_j^{(l+1)}\right)$$ \tilde{\mathbf{\vec h}}_*^{(l+1)}\left(u_j^{(l+1)}\right) $ ，因为我们的目标是整个第$l$$ l $ 层的方差。
   • 我们考虑的是非线性之前的embedding 函数${\widetilde{\overrightarrow{\mathbf{h}}}}_{\ast }^{(l+1)}(v)$$ \tilde{\mathbf{\vec h}}_*^{(l+1)}(v) $ ，而不是非线性之后的 embedding 函数${\overrightarrow{\mathbf{h}}}_{\ast }^{(l+1)}(v)$$ \mathbf{\vec h} _*^{(l+1)}(v) $ 。

2. 为表述方便，我们修改某些符号。

   • 对于第$l$$ l $ 层的随机变量记作$u$$ u $ ，采样的节点$u_j^{(l)}$$ u_j^{(l)} $ 记作$u_j$$ u_j $ ，采样数量$t_l$$ t_l $ 记作$t$$ t $ ，${({\overrightarrow{\mathbf{h}}}^{(l)}(u))}^{\mathrm{\top }}{\mathbf{W}}^{(l)}$$ \left(\mathbf{\vec h}^{(l)}(u) \right)^\top\mathbf W^{(l)} $ 记作$\overrightarrow{\mathbf{x}}(u)$$ \mathbf{\vec x}(u) $ 。
   • 对于第$l+1$$ l+1 $ 层的随机变量记作$v$$ v $ ，采样的节点$u_i^{(l+1)}$$ u_i^{(l+1)} $ 记作$v_i$$ v_i $ ，采样数量$t_{l+1}$$ t_{ l+1} $ 记作$s$$ s $ ，${\widetilde{\overrightarrow{\mathbf{h}}}}_{\ast }^{(l+1)}(v)$$ \tilde{\mathbf{\vec h}}_*^{(l+1)}(v) $ 记作$\overrightarrow{\mathbf{y}}(v)$$ \mathbf{\vec y}(v) $ 。

   在随机变量$v,u$$ v,u $ 的联合分布下，上述$t_{l+1}$$ t_{l+1} $ 个样本的${\widetilde{\overrightarrow{\mathbf{h}}}}_{\ast }^{(l+1)}\left(u_j^{(l+1)}\right)$$ \tilde{\mathbf{\vec h}}_*^{(l+1)}\left(u_j^{(l+1)}\right) $ 的均值为：

   $$\overrightarrow{\mathbf{g}}=\frac{1}{s}\sum _{i=1}^s\overrightarrow{\mathbf{y}}(v_i)=\frac{1}{s}\sum _{i=1}^s(\frac{1}{t}\sum _{j=1}^t\hat{A}(v_i,u_j)\overrightarrow{\mathbf{x}}(u_j))$$

3. 推论：$\overrightarrow{\mathbf{g}}$$ \mathbf{\vec g} $ 的方差为：

   $$\text{var}(\overrightarrow{\mathbf{g}})=\overrightarrow{\mathbf{r}}+\frac{1}{st}\int \int \hat{A}(v,u{)}^2\overrightarrow{\mathbf{x}}(u{)}^{2}dP(u)dP(v)$$

   其中：

   $$\begin{array}{c}\overrightarrow{\mathbf{r}}=\frac{1}{s}(1-\frac{1}{t})\int \overrightarrow{\mathbf{e}}(v{)}^{2}dP(v)-\frac{1}{s}{(\int \overrightarrow{\mathbf{e}}(v)dP(v))}^2\\ \overrightarrow{\mathbf{e}}(v)=\int \hat{A}(v,u)\overrightarrow{\mathbf{x}}(u)dP(u)\end{array}$$

   其中向量的平方$(\cdot {)}^2$$ (\cdot)^2 $ 为向量逐元素的平方。

   证明见原始论文。

   可以看到，$\overrightarrow{\mathbf{g}}$$ \mathbf{\vec g} $ 的方差由两部分组成：

   • 第一部分$\overrightarrow{\mathbf{r}}$$ \mathbf{\vec r} $ 几乎没有改善的余地，因为$v$$ v $ 变量空间的采样并未在第$l$$ l $ 层完成，第$l$$ l $ 层执行的是对$u$$ u $ 变量空间的采样。
   • 第二部分（双重积分）取决于$u$$ u $ 变量空间的节点采样方式。

   当前结果是使用概率测度$P$$ P $ 对$u_j$$ u_j $ 进行采样得到。我们可以执行 importance sampling 重要性采样，从而改变采样分布来减少$\overrightarrow{\mathbf{g}}$$ \mathbf{\vec g} $ 的方差。

   具体而言，我们使用新的概率测度$Q(u)$$ Q(u) $ 来对$u_j$$ u_j $ 进行采样。因此我们定义样本均值新的近似。定义：

   $${\overrightarrow{\mathbf{y}}}_Q(v)=\frac{1}{t}\sum _{j=1}^t\hat{A}(v,u_j)\overrightarrow{\mathbf{x}}(u_j)\left(\frac{dP(u)}{dQ(u)}{|}_{u_j}\right),u_1,\cdots ,u_t\sim Q$$

   以及新的均值：

   $${\overrightarrow{\mathbf{g}}}_Q=\frac{1}{s}\sum _{i=1}^s{\overrightarrow{\mathbf{y}}}_Q(v_i)$$

   当然，无论新的测度$Q$$ Q $ 如何，$\mathbb{E}[{\overrightarrow{\mathbf{g}}}_Q]=\mathbb{E}[\overrightarrow{\mathbf{g}}]$$ \mathbb E[\mathbf{\vec g}_Q] = \mathbb E[\mathbf{\vec g} ] $ 。因为：

   $$\mathbb{E}[{\overrightarrow{\mathbf{g}}}_Q]=\mathbb{E}[\frac{1}{s}\sum _{i=1}^s{\overrightarrow{\mathbf{y}}}_Q(v_i)]=\mathbb{E}[{\overrightarrow{\mathbf{y}}}_Q(v)\mid v]=\int \hat{A}(v,u)\overrightarrow{\mathbf{x}}(u)dP(u)=\mathbb{E}[\overrightarrow{\mathbf{g}}]$$

4. 定理：如果：

   $$dQ(u)=\frac{b(u)|\overrightarrow{\mathbf{x}}(u)|dP(u)}{\int b(u)|\overrightarrow{\mathbf{x}}(u)|dP(u)}$$

   其中$b(u)={[\int \hat{A}(v,u{)}^{2}dP(v)]}^{1/2}$$ b(u) = \left[\int \hat A(v,u)^2 dP(v)\right]^{1/2} $ ，则${\overrightarrow{\mathbf{g}}}_Q$$ \mathbf{\vec g}_Q $ 的方差为：

   $$\text{var}[{\overrightarrow{\mathbf{g}}}_Q]=\overrightarrow{\mathbf{r}}+\frac{1}{st}{[\int b(u)|\overrightarrow{\mathbf{x}}(u)|dP(u)]}^2$$

   则该方差为所有可选分布$Q$$ Q $ 中最小的方差。

   其中$|\cdot |$$ |\cdot| $ 表示向量的长度。

   证明见原始论文。

   $b(u)$$ b(u) $ 的物理意义为：基于邻接向量$\hat{\mathbf{A}}$$ \hat{\mathbf A} $ 的、节点$u$$ u $ 的邻接向量的$L_2$$ L_2 $ 范数。

5. 考虑$dQ(u)=\frac{b(u)|\overrightarrow{\mathbf{x}}(u)|dP(u)}{\int b(u)|\overrightarrow{\mathbf{x}}(u)|dP(u)}$$ dQ(u) = \frac{b(u)| \mathbf{\vec x}(u)| dP(u)}{\int b(u)| \mathbf{\vec x}(u)| dP(u)} $ ，这种方式定义的采样分布$Q$$ Q $ 存在一个缺点：它涉及$|\overrightarrow{\mathbf{x}}(u)|$$ | \mathbf{\vec x}(u)| $ ，而$\overrightarrow{\mathbf{x}}(u)$$ \mathbf{\vec x}(u) $ 在训练期间不断变化，因为权重矩阵${\mathbf{W}}^{(l)}$$ \mathbf W^{(l)} $ 在训练期间不断更新。另外它还涉及到 embedding 矩阵${\mathbf{H}}^{(l)}$$ \mathbf H^{(l)} $ 和${\mathbf{W}}^{(l)}$$ \mathbf W^{(l)} $ 的矩阵乘法，计算代价太高。

   作为折衷方案，我们考虑$Q$$ Q $ 的另一种选择，它仅涉及$b(u)$$ b(u) $ 。对于新的$Q$$ Q $ ，$\text{var}({\overrightarrow{\mathbf{g}}}_Q)$$ \text{var}(\mathbf{\vec g}_Q) $ 可能会也可能不会小于$\text{var}(\overrightarrow{\mathbf{g}})$$ \text{var}(\mathbf{\vec g}) $ ，但是实践中我们发现它几乎总是有益的。

   推论：如果$dQ(u)=\frac{b(u{)}^{2}dP(u)}{\int b(u{)}^{2}dP(u)}$$ dQ(u) = \frac{b(u)^2 dP(u)}{\int b(u)^2 dP(u)} $ ，则${\overrightarrow{\mathbf{g}}}_Q$$ \mathbf{\vec g}_Q $ 的方差为：

   $$\text{var}({\overrightarrow{\mathbf{g}}}_Q)=\overrightarrow{\mathbf{r}}+\frac{1}{st}\int b(u{)}^{2}dP(u)\int \overrightarrow{\mathbf{x}}(u{)}^{2}dP(u)$$

   证明见原始论文。

   $dQ(u)$$ dQ(u) $ 的物理意义为：给定邻接向量$\hat{\mathbf{A}}$$ \hat{\mathbf A} $ ，节点$u$$ u $ 的邻接向量长度的平方，占所有节点邻接向量长度平方之和的比例。

6. 使用$dQ(u)=\frac{b(u{)}^{2}dP(u)}{\int b(u{)}^{2}dP(u)}$$ dQ(u) = \frac{b(u)^2 dP(u)}{\int b(u)^2 dP(u)} $ 之后，$dQ(u)/dP(u)$$ dQ(u)/dP(u) $ 正比于$b(u{)}^2=\int \hat{A}(v,u{)}^{2}dP(v)$$ b(u)^2 = \int \hat A(v,u)^2 dP(v) $ 。这只是简单地将$\hat{A}(v,u{)}^2$$ \hat A(v,u)^2 $ 对$v$$ v $ 的积分。

   实际应用过程中，我们为图中所有节点定义了概率质量函数：

   $$q(u)=\frac{{\Vert \overrightarrow{\mathbf{a}}(u)\Vert }^2}{\sum _{u^{\prime }\in V}{\Vert \overrightarrow{\mathbf{a}}(u^{\prime })\Vert }^2},u\in V$$

   其中$\overrightarrow{\mathbf{a}}(u)={(\hat{A}(v_1,u),\cdots ,\hat{A}(v_n,u))}^{\mathrm{\top }}$$ \mathbf{\vec a}(u) = \left(\hat A(v_1,u),\cdots,\hat A(v_n,u)\right)^\top $ ，为矩阵$\hat{\mathbf{A}}$$ \hat {\mathbf A} $ 第$u$$ u $ 列组成的向量，即节点$u$$ u $ 的邻接向量。

   然后我们根据这个概率分布来采样$t$$ t $ 个节点：$\{u_1,\cdots ,u_t\}$$ \{u_1,\cdots,u_t\} $ 。

   即，根据邻域连接强度的平方之和为概率来采样。因此，degree 较高的节点更有可能被采样。

   从$q(u)$$ q(u) $ 表达式中我们发现：$q(u)$$ q(u) $ 和$l$$ l $ 不相关。因此所有层的节点采样分布都相同。

   使用$q(u)$$ q(u) $ 之后，batch 损失${\mathcal{L}}_{\text{batch}}$$ \mathcal L_\text{batch} $ 为：

   $${\mathcal{L}}_{\text{batch}}=\frac{1}{t_L}\sum _{i=1}^{t_L}g\left({\overrightarrow{\mathbf{h}}}^{(L)}\left(u_i^{(L)}\right)\right)$$

   其中：

   $${\overrightarrow{\mathbf{h}}}^{(l+1)}(v)=\sigma \left(\frac{1}{t_l}\sum _{j=1}^{t_l}\frac{\hat{A}(v,u_j^{(l)}){\left({\overrightarrow{\mathbf{h}}}^{(l)}\left(u_j^{(l)}\right)\right)}^{\mathrm{\top }}{\mathbf{W}}^{(l)}}{q\left(u_j^{(l)}\right)}\right),u_j^{(l)}\sim q,,l=0,\cdots ,L-1$$

   它和前述${\overrightarrow{\mathbf{h}}}^{(l+1)}(v)=\sigma \left(\frac{n}{t_l}\sum _{j=1}^{t_l}\hat{A}(v,u_j^{(l)}){({\overrightarrow{\mathbf{h}}}^{(l)}(u_j^{(l)}))}^{\mathrm{\top }}{\mathbf{W}}^{(l)}\right)$$ \mathbf {\vec h}^{(l+1)}(v) = \sigma\left(\frac{n}{t_l}\sum_{j=1}^{t_l}\hat A\left(v,u_j^{(l)}\right)\left( \mathbf {\vec h}^{(l)}(u_j^{(l)})\right)^\top \mathbf W^{(l)}\right) $ 的主要区别在于：

   • 新的${\overrightarrow{\mathbf{h}}}^{(l+1)}(v)$$ \mathbf {\vec h}^{(l+1)}(v) $ 根据$q$$ q $ 来采样，因此缩放比例为$1/q\left(u_j^{(l)}\right)$$ {1}/{q\left(u_j^{(l)}\right)} $ 。
   • 旧的${\overrightarrow{\mathbf{h}}}^{(l+1)}(v)$$ \mathbf {\vec h}^{(l+1)}(v) $ 均匀采样，因此缩放比例为$1/n$$ 1/n $ 。

   可以通过在每个${\mathbf{H}}^{(l)}$$ \mathbf H^{(l)} $ 上应用链式法则来直接获取相应的 batch 梯度，最终我们得到了 batch 损失以及 batch 梯度。

   为什么选择这样的$Q(u)$$ Q(u) $ 和$q(u)$$ q(u) $ ，没有理论的依据。论文是根据邻域连接强度的平方和作为采样概率，也可以选择$k$$ k $ 次方，$k$$ k $ 为超参数。

7. 基于重要性采样的 FastGCN batch 训练算法（一个 epoch ）：

   • 输入：

     • 图$G(V,E)$$ G(V,E) $ ，以及图的邻接矩阵$\hat{\mathbf{A}}$$ \hat{\mathbf A} $
     • 学习率$\eta$$ \eta $

   • 输出：更新后的参数${\left\{{\mathbf{W}}^{(l)}\right\}}_{l=0}^{L-1}$$ \left\{\mathbf W^{(l)}\right\}_{l=0}^{L-1} $

   • 算法步骤：

     对每个节点$u$$ u $ ，计算采样概率$q(u)\propto {\Vert \overrightarrow{\mathbf{a}}(u)\Vert }^2$$ q(u) \propto \left\|\mathbf{\vec a}(u)\right\|^2 $ 。

     迭代每个 batch，迭代过程：

     • 对每一层$l$$ l $ ，根据概率$q(u)$$ q(u) $ 随机采样$t_l$$ t_l $ 个节点：$u_1^{(l)},\cdots ,u_{t_l}^{(l)}$$ u_1^{(l)},\cdots,u_{t_l}^{(l)} $ 。

       这里根据邻域连接强度的平方和作为概率，而不是均匀采样。

     • 对每一层$l$$ l $ ，如果节点$v$$ v $ 在第$l+1$$ l+1 $ 层被采样到，则计算：

       $$\mathrm{\nabla }\widetilde{\overrightarrow{\mathbf{h}}}(v)\leftarrow \frac{1}{t_l}\sum _{j=1}^{t_l}\frac{\hat{A}(v,u_j^{(l)})}{q\left(u_j^{(l)}\right)}\mathrm{\nabla }\left\{{\left({\overrightarrow{\mathbf{h}}}^{(l)}\left(u_j^{(l)}\right)\right)}^{\mathrm{\top }}{\mathbf{W}}^{(l)}\right\}$$

     • 参数更新：$\mathbf{W}\leftarrow \mathbf{W}-\eta \mathrm{\nabla }{\mathcal{L}}_{\text{batch}}$$ \mathbf W\leftarrow \mathbf W-\eta \nabla \mathcal L_\text{batch} $ 。

   这里虽然使用了邻接矩阵$\hat{\mathbf{A}}$$ \hat{\mathbf A} $ ，但是主要依赖于连接的强度$\hat{A}(v,u)$$ \hat A(v,u) $ ，因此整个算法是 inductive 的。

12.3 讨论

1. inference：前述的采样方法清晰地将训练数据和测试数据分开，因此这种方法是 inductive 的，而不是 transductive 。本质是将图的节点集合转换为独立同分布的 iid 样本，以便学习算法可以使用损失函数的一致估计量的梯度来执行参数更新。

   在测试过程中，可以使用完整的 GCN 架构来计算新节点的 embedding ，也可以使用在训练过程中通过采样来近似的方法。通常，使用完整 GCN 来 inference 更容易实现。

2. 与 GraphSAGE的比较：GraphSAGE 通过聚合邻域信息来生成节点 embedding。由于递归邻域扩展，它和 GCN 一样都存在内存瓶颈。为减少计算量，作者建议限制每一层的直接邻域大小。

   • 在 GraphSAGE 中，如果在第$l$$ l $ 层每个节点采样了$t_l$$ t_l $ 个邻居，那么扩展的邻域大小为$\prod _{l=1}^L{t}_l$$ \prod_{l =1}^L t_{l } $ 。
   • 而在 FastGCN 中，在每一层中，我们对节点进行采样，而不是对每个节点的邻居进行采样，因此涉及的节点数量为$\sum _{l=1}^L{t}_l$$ \sum_{l=1}^L t_l $ ，远小于 GraphSAGE 。实验表明，FastGCN 这种方式可以大幅度提高训练速度。

   事实上 FastGCN 训练算法（包括重要性采样的训练算法）并不完全遵循 SGD 的现有理论，因为尽管梯度的估计量是一致的，但是这个估计量是有偏的。论文证明了即使梯度估计量是有偏的，学习算法仍然是收敛的。

   FastGCN 主要聚焦于提升邻域采样方法的效率，这种做法也可以应用到 GraphSAGE 等方法。方法实现很简单，但是作者这里给了理论上的说明。

12.4 实验

1. 数据集：

   • Cora 引文数据集：数据集包含以文档（具有稀疏 BOW 特征向量）作为节点，文档之间的引文链接作为边。共包含2708 个节点、5429 条边、7 个类别，每个节点 1433 维特征。
   • Pubmed 学术论文数据集：数据集包含以文档（具有稀疏 BOW 特征向量）作为节点，文档之间的引文链接作为边。共包含19717 个节点、44338 条边、3 个类别，每个节点 500 维特征。
   • Reddit 数据集：包含2014 年 9 月Reddit 上发布帖子的一个大型图数据集，节点标签为帖子所属的社区。

   我们调整了 Cora, Pubmed 的训练集、验证集、测试集划分，从而与监督学习的场景相一致。具体而言，训练集中所有标签都用于训练，而不是半监督学习使用训练集中非常少量的标签。这种方式与 GraphSage 工作中使用的Reddit 一致。

   这里没有给出平均 degree 信息，读者猜测：FastGCN 对于 degree 较小的长尾节点不利。

   

2. Baseline 方法：

   • GCN：《Semi-supervised classification with graph convolutional networks》提出的 GCN 方法。原始的 GCN 无法在非常大的图上（例如 Reddit），因此我们只需要在 FastGCN 中移除采样即可将其修改为 batch 版本。如，我们在每个 batch 使用所有节点，而不是在每个 batch 中在每一层随机采样一些节点。

     对于较小的图（如 Cora 和 Pubmed），我们还将batch 版本的 GCN 和原始 GCN 进行比较。

   • GraphSAGE ：为比较训练时间，我们使用 GraphSAGE-GCN，它使用 GCN 作为聚合器，这也是所有聚合器中最快的版本。

     为进行准确性比较，我们还将它与 GraphSAGE-mean 进行比较。

3. 实验配置：

   • 所有模型的学习率在 {0.01, 0.001, 0.0001} 中选择。

   • 所有模型都采用两层网络（包括 FastGCN, GCN, GraphSAGE）。

     • 对于 GraphSAGE，这两层的邻域采样大小分别为 S1=25, S2=10 ，隐层维度为 128。
     • 对于 FastGCN， Reddit 数据集的隐层维度为 128，其它两个数据集的隐层维度为 16 。

   • 对于 batch 训练的模型(FastGCN, GCN-batch, GraphSAGE) ，Reddit, Cora 数据集的 batch size = 256，Pubmed 数据集的 batch size = 1024 。

   • GraphSAGE, GCN 的代码是从原作者的网站上下载，使用原始论文的实现。

   • FastGCN 的 inference 是通过完整的 GCN 网络来完成。

   • FastGCN 使用 Adam 优化器。

   • FastGCN 在Cora, Pubmed, Reddit 三个数据集上采样的节点数量数量分别为 400, 100, 400 。

   • 硬件配置：4 核 2.5GHz Intel Core i7， 16G Ram 。

12.4.1 超参数研究

1. 首先我们观察不同采样规模对 FastGCN 的影响。下表左侧（Sampling 列）给出了随着采样数量增加，对应的训练时间（单位 s/epoch）、分类准确性（以 F1 衡量）的变化。该数据集为 Pubmed 数据集，batch size = 1024 。

   为便于说明，我们将网络两层的采样数量都设为同一个值。可以看到：随着采样数量的增加，每个 epoch 训练时间也会增加，但是准确性也会提高。

   我们观察到一个有趣的事实：在给定输入特征${\mathbf{H}}^{(0)}$$ \mathbf H^{(0)} $ 的情况下，底层的乘积$\hat{\mathbf{A}}{\mathbf{H}}^{(0)}$$ \hat{ \mathbf A} \mathbf H^{(0)} $ 不变。这意味着相对于${\mathbf{W}}^{(0)}$$ \mathbf W^{(0)} $ 的梯度链式扩展的最后一步在整个训练过程中都是恒定的。因此可以预计算这个矩阵乘积，而不是对该层采样从而获得效率提升。

   我们给出预计算的结果（右侧Precompute 列），可以看到：使用预计算后，训练时间大幅降低，但是预测准确性却相当。因此后续实验我们都使用预计算。

   

2. 然后我们考察 FastGCN 中均匀采样和重要性采样的区别。三个图依次为 Cora, Pubmed, Reddit 数据集的结果。可以看到：基于重要性采样的 FastGCN 始终比基于均匀采样的 FastGCN 效果更好。

   我们这里使用的是折衷的重要性采样$dQ(u)=\frac{b(u{)}^{2}dP(u)}{\int b(u{)}^{2}dP(u)}$$ dQ(u) = \frac{b(u)^2 dP(u)}{\int b(u)^2 dP(u)} $ ，而不是最佳的重要性采样$dQ(u)=\frac{b(u)|\overrightarrow{\mathbf{x}}(u)|dP(u)}{\int b(u)|\overrightarrow{\mathbf{x}}(u)|dP(u)}$$ dQ(u) = \frac{b(u)| \mathbf{\vec x}(u)| dP(u)}{\int b(u)| \mathbf{\vec x}(u)| dP(u)} $ 。结果表明我们折衷的重要性采样比均匀采样更接近最佳的重要性采样。

   因此，后续实验将使用重要性采样。

   

12.4.2 Baseline 比较

1. 最后我们对比了 FastGCN 和 Baseline 方法的训练速度和分类效果。左图以对数坐标给出了每个 batch 的训练时间，单位为 s 。

   注意：在训练速度比较中，GraphSAGE 指的是 GraphSAGE-GCN ，它和其它聚合器（如 GraphSAGE-mean ）是差不多的。GCN 指的是 GCN-batched 版本，而不是 GCN-original 版本。GCN-original 在大的图(如 Reddit ) 上内存溢出。

   可以看到：

   • GraphSAGE 在大型和稠密的图（Reddit ）上训练速度比 GCN 快得多，但是在小数据集上(Cora, Pubmed) 要比 GCN 更慢。
   • FastGCN 训练速度最快，比第二名（除 Cora 之外）至少提高了一个量级，比最慢的提高了大约两个量级。
   • 除了训练速度优势之外，FastGCN 的准确性和其它两种方法相比相差无几。

   

2. 上面比较了单个 batch 的训练速度。实际上总的训练时间除了受到 batch 训练速度的影响之外，还受到收敛性的影响（决定了需要训练多少个 batch）。这里我们给出总的训练时间，单位为秒。注意：收敛性受到学习率、batch size、sample size 等因素的影响。

   可以看到：尽管收敛速度使得FastGCN 拖慢了最终训练速度（整体训练速度的提升比例低于单个 batch 的提升比例），但是 FastGCN 整体训练速度仍然保持巨大优势。

   注意：即使GCN-original 的训练速度比 GCN-batched 更快，但是由于内存限制导致GCN-original 无法扩展。因此这里我们仅比较了 GCN-batched 版本。

   

   我们还给出了随着训练的进行，预测准确性的变化。下图从左到右依次为 Cora,Pubmed,Reddit 数据集。

   

3. 在讨论期间，GraphSAGE 的作者提供了时间优化的版本，并提醒说 GraphSAGE 更适合于大图。原因是：对于小图，采样大小（它等于各层样本数量的乘积）和图的大小相差无几，因此改善的程度很小。

   此外，采样的开销可能会对训练时间有不利影响。为公平比较，GraphSAGE 的作者保留了采样策略，但是通过消除对采样节点的冗余计算，改进了原始代码的实现。

   可以看到：GraphSAGE 现在在小图 Cora 上的训练速度快得多。注意，这种实现方式不会影响大图（Reddit） ，并且我们的 FastGCN 仍然比它快一个量级。

   

4. 在前面评估过程中，我们增加了 Cora,Pubmed 数据集中训练标签数量，从而与 Reddit 监督学习的训练集比例保持一致。作为参考，这里我们给出使用原始数据集拆分，从而使用更少的训练标签的结果。

   此外我们还给出FastGCN 的 transductive 版本，它同时使用训练节点、测试节点学习，这个过程中仅使用少量训练节点的标签信息（而不使用任何测试节点的标签信息）。

   可以看到：

   • GCN 的结果和 《Semi-supervised classification with graph convolutional networks》 报告的结果一致。由于训练标记数据稀疏，GCN 训练速度非常快。FastGCN 仅在 Pubmed 数据集上超越 GCN 的训练速度。
   • 由于训练标记数据稀疏，FastGCN 的准确性也比 GCN 更差。
   • transductive 版本的 FastGCN 和 GCN 的准确性相差无几，比 inductive 的 FastGCN 更好。但是其训练时间也更长（训练节点更多）。
   • GraphSAGE 的结果有些奇怪，其F1 值非常低。我们怀疑模型严重过拟合，因为它的训练准确性为 1.0，非常完美。
   • 注意到这里的 GCN-original 要比前面报告给出的 GCN-original 更慢。这时因为我们这里使用和 《Semi-supervised classification with graph convolutional networks》 工作中相同的超参数，而前面给出的 GCN-original 使用调参之后的学习率（因为数据集拆分发生变化，所以需要调参）。

   下表中的Time 单位为 s/batch 。