Question

1. 当前图神经网络GNN的一个明显挑战是可扩展性。在 GCN 中计算图卷积需要跨层递归扩张邻域，这在计算上是不现实的，并且需要占用大量内存。即使对于单个节点，当图是稠密的或者满足幂律powerlaw 分布时，由于邻域的逐层扩张，这将迅速覆盖图的很大一部分。传统的 mini-batch 训练无法加快图卷积的计算速度，因为每个batch 都将涉及大量节点，即使 mini-batch 本身很小。

   为缓解过度扩张over-expansion 的问题，一些工作通过控制采样邻域的大小来加速GCN 的训练。有几种基于采样的方法用于图上进行快速的 representation learning：

   • GraphSAGE 通过对每个节点的邻域进行采样（node-wise 采样），然后执行特定的聚合器以进行信息融合来计算节点的 representation。
   • FastGCN 模型将图卷积解释为 embedding 函数的积分变换，并独立采样每一层中的节点（layer-wise 采样）。
   • VRGCN 是control-variate-based 方法 ，这种采样方法也是 node-wise，并且需要节点的历史激活值。

   论文 《Adaptive Sampling Towards Fast Graph Representation Learning》 提出了一种新的layer-wise 采样方法：按照自上而下的方式逐层构建网络，其中下层的节点是根据上层的节点有条件采样而来。这种层级采样layer-wise sampling在两个技术方面是有效的：

   • 首先，由于较低层中的节点是可见的visible ，并且由于它们在较高层中的不同父节点之间共享，因此我们可以复用采样邻域的信息（即低层节点）。
   • 其次，很容易固定fix每一层的大小，从而避免邻域的过度扩张，因为较低层的节点是整体采样的。

   和基于节点采样的 GraphSAGE 相比，论文的方法基于层级采样，因为所有邻域都被一起采样，因此可以实现邻域共享；和独立构造每一层的 FastGCN 相比，论文的方法可以捕获跨层连接。因为较低的层根据上层的条件进行采样。

   论文方法的核心是为 layer-wise 采样定义合适的采样器。通常，设计采样器的目标是使得结果的方差最小化。不幸的是，由于在论文的网络中自上而下的采样和自下而上的传播的不一致，使得方差最小化的最佳采样器是无法计算的uncomputable 。为解决这个问题，作者通过使用自依赖函数代替不可计算的部分，然后将方差添加到损失函数，从而逼近最佳采样器。结果，通过共同训练模型参数和采样器 ，方差得到显著降低，这反过来又促进了模型的训练。

   此外，论文还探索了如何使得有效的消息跨远程节点distant node 来传递。有些方法通过随机游走以生成各个step 的邻域，然后对 multi-hop 邻域进行整合。相反，本文通过在第$(l+1)$$ (l+1) $ 层和第$(l-1)$$ (l-1) $ 层之间添加skip-connection 从而提出了一种新的机制。这种跳跃连接将第$(l-1)$$ (l-1) $ 层的节点复用为第$(l+1)$$ (l+1) $ 层节点的 2-hop 邻域，因此它自然地保持了二阶邻近性，而无需进行额外的计算。

   总之本文做出了以下贡献：

   • 开发了一种新的 layer-wise 采样方法来加速 GCN 模型，该模型共享层间信息，并可控制采样节点的规模。
   • 用于 layer-wise 采样的采样器是自适应的，并通过训练阶段显式降低方差来确定。
   • 提出了一种简单而有效的方法，即通过在两层之间指定 skip-connection 来保留二阶邻近性。

   最后，论文在节点分类的四个流行benchmark 上评估了新方法的性能，包括 Cora, Citeseer, Pubmed, Reddit。大量实验证明了新方法在分类准确率和收敛速度方面的有效性。

2. 相关工作：

   • 如何设计高效的图卷积网络已成为一个热门研究课题。图卷积方法通常被分为谱域卷积和空域卷积两类：

     • 谱域卷积方法首先由 《Spectral networks and locally connected networks on graphs》提出，并在傅里叶域定义卷积操作。

       后来，《Deep convolutional networks on graph-structured data》通过应用高效的频滤波器实现了局部滤波。

       《Convolutional neural networks on graphs with fast localized spectral filtering》采用图拉普拉斯矩阵的 Chebyshev 多项式来避免特征分解 eigen-decomposition 。

       最近，《Semi-supervised classification with graph convolutional networks》提出了GCN，它用一阶近似和重参数化技巧 re-parameterization trick 简化了以前的方法。

     • 空域卷积方法通过直接使用空间连接来定义图的卷积。例如：

       《Convolutional networks on graphs for learning molecular fingerprints》为每个 node degree 学习一个权重矩阵。

       《Diffusion-convolutional neural networks》通过使用转移矩阵transition matrix 的一系列幂次来定义 multiple-hop 邻域。

       《Learning convolutional neural networks for graphs》提取了包含固定数量节点的规范化的邻域。

   • 最近的一个研究方向是通过利用 patch 操作和自注意力来泛化卷积。与 GCN 相比，这些方法隐含地为邻域中的节点分配不同的重要性，从而实现了模型容量的飞跃。具体而言：

     • 《Geometric deep learning on graphs and manifolds using mixture model cnns》 提出了 mixture model CNN ，使用 patch 操作在图上建立 CNN 架构。
     • 《Graph attention networks》 通过 attend 中心节点的每个邻居，按照自注意力策略计算中心节点的 hidden representation 。

   • 最近有两种基于采样的方法（即，GraphSAGE 和 FastGCN 被开发出来），用于图上的 fast representation learning 。具体而言：

     • GraphSAGE 通过对每个节点的邻域进行采样，然后执行特定的信息融合聚合器来计算节点的representation（node-wise 采样）。
     • FastGCN 模型将图的卷积解释为 embedding 函数的积分变换，并对每一层的节点独立采样（layer-wise 采样）。

     虽然我们的方法与这些方法密切相关，但我们在本文中开发了一个不同的采样策略：

     • 与 GraphSAGE 以节点为单位的方法相比，我们的方法是基于 layer-wise 采样的，因为所有的邻域都是整体采样的，因此可以允许邻域共享。
     • 与独立构建每一层的 FastGCN 相比，我们的模型能够捕捉到层与层之间的联系，因为下层是以上层为条件进行采样的。

     另一项相关工作是 《Fastgcn: Fast learning with graph convolutional networks via importance sampling》的基于控制变量的方法。然而，这种方法的采样过程是 node-wise 的，需要节点的历史激活 historical activation 。

33.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}\} $ 为边集合。

   • 邻接矩阵$\mathbf{A}\in {\mathbb{R}}^{n\times n}$$ \mathbf A\in \mathbb R^{n\times n} $ ，其中$A_{i,j}$$ A_{i,j} $ 表示节点$(v_i,v_j)$$ (v_i,v_j) $ 之间是否存在边以及边的权重。$\mathbf{D}$$ \mathbf D $ 为degree 矩阵，它是一个对角矩阵，$D_{i,i}=\sum _j{A}_{i,j}$$ D_{i,i} = \sum_j A_{i,j} $ 。
   • 归一化的邻接矩阵定义为$\hat{\mathbf{A}}={\mathbf{D}}^{-1/2}\mathbf{A}{\mathbf{D}}^{-1/2}$$ \hat{\mathbf A} = \mathbf D^{-1/2}\mathbf A\mathbf D^{-1/2} $ 。
   • 每个节点$v_i\in \mathcal{V}$$ v_i\in \mathcal V $ 关联一个输入特征向量${\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} $ 。

2. GCN 是用于图representation learning 的最成功的卷积网络之一。为区分不同层的节点，我们将第$l$$ l $ 层的节点记作$\{u_j\}$$ \{u_j\} $ ，将第$l+1$$ l+1 $ 层的节点记作$\{v_i\}$$ \{v_i\} $ 。实际上它们都是相同的节点集合$\mathcal{V}$$ \mathcal V $ ，只是为了表述的方便而进行区分。

   GCN 的前向传播公式为：

   $${\overrightarrow{\mathbf{h}}}_i^{(l+1)}=\sigma \left(\sum _{j=1}^n{\hat{A}}_{i,j}{\mathbf{W}}^{(l)}{\overrightarrow{\mathbf{h}}}_j^{(l)}\right)$$

   其中：

   • ${\overrightarrow{\mathbf{h}}}_i^{(l+1)}$$ \mathbf{\vec h}_i^{(l+1)} $ 是第$l+1$$ l+1 $ 层节点$v_i$$ v_i $ 的representation ，${\overrightarrow{\mathbf{h}}}_j^{(l)}$$ \mathbf{\vec h}_j^{(l)} $ 是第$l$$ l $ 层节点$u_j$$ u_j $ 的representation 。
   • $\hat{\mathbf{A}}\in {\mathbb{R}}^{n\times n}$$ \hat{\mathbf A} \in \mathbb R^{n\times n} $ 为归一化的邻接矩阵，${\hat{A}}_{i,j}$$ \hat A_{i,j} $ 为$\hat{\mathbf{A}}$$ \hat{\mathbf A} $ 的元素。
   • $\sigma (\cdot )$$ \sigma(\cdot) $ 为非线性激活函数。
   • ${\mathbf{W}}^{(l)}\in {\mathbb{R}}^{d_{l+1}\times d_l}$$ \mathbf W^{(l)}\in \mathbb R^{d_{l+1}\times d_l} $ 为第$l$$ l $ 层的权重，$d_l$$ d_l $ 为第$l$$ l $ 层 representation 的维度。

3. GCN 的前向传播公式表明：GCN 要求邻域的完整扩张full expansion 才能对每个节点进行前向计算。这使得在包含数十万个节点的大规模图上的学习变得计算量大而且消耗内存。

   为解决这个问题，本文通过自适应采样adaptive sampling 来加快前向传播。我们提出的采样器是自适应的，并且可以减少方差。

   • 我们首先将 GCN 公式重写为期望的形式，并相应地引入 node-wise 采样。然后我们将 node-wise 采样推广为一个更有效的框架，称为 layer-wise 采样。
   • 为了使得采样方差最小化，我们进一步提出通过显式执行方差缩减variance reduction 来学习layer-wise 采样器。

   最后，我们介绍了skip-connection 的概念，通过应用skip-connection 来实现前向传播的二阶邻近性second-order proximity 。

33.1.1 自适应采样

1. node-wise 采样：我们首先观察到 GCN 前向传播公式可以重写为期望的形式，即：

   $${\overrightarrow{\mathbf{h}}}_i^{(l+1)}=\sigma \left(\sum _{j=1}^n{\hat{A}}_{i,j}{\mathbf{W}}^{(l)}{\overrightarrow{\mathbf{h}}}_j^{(l)}\right)={\sigma }_{{\mathbf{W}}^{(l)}}(d_i\times {\mathbb{E}}_{p(u_j\mid v_i)}\left[{\overrightarrow{\mathbf{h}}}_j^{(l)}\right])$$

   其中：

   • ${\sigma }_{{\mathbf{W}}^{(l)}}$$ \sigma_{\mathbf W^{(l)}} $ 包含了权重矩阵${\mathbf{W}}^{(l)}$$ \mathbf W^{(l)} $ 的非线性函数，这是为了简单起见。
   • $d_i$$ d_i $ 为节点$v_i$$ v_i $ 的 degree ：$d_i=\sum _{j=1}^n{\hat{A}}_{i,j}$$ d_i=\sum_{j=1}^n \hat A_{i,j} $ 。
   • $p(u_j\mid v_i)={\hat{A}}_{i,j}/d_i$$ p(u_j\mid v_i) = \hat A_{i,j}/d_i $ 为给定$v_i$$ v_i $ 的条件下采样到节点$u_j$$ u_j $ 的概率。
   • ${\mathbb{E}}_{p(u_j\mid v_i)}\left[{\overrightarrow{\mathbf{h}}}_j^{(l)}\right]=\sum _{j=1}^{n}p(u_j\mid v_i)\times {\overrightarrow{\mathbf{h}}}_j^{(l)}$$ \mathbb E_{p(u_j\mid v_i)}\left[\mathbf{\vec h}^{(l)}_j\right]=\sum_{j=1}^n p(u_j\mid v_i)\times \mathbf{\vec h}^{(l)}_j $ 为${\overrightarrow{\mathbf{h}}}_j^{(l)}$$ \mathbf{\vec h}^{(l)}_j $ 的期望。

   加快上式的一个自然想法是通过蒙特卡洛采样Monte-Carlo sampling 来近似期望的计算。具体而言，我们通过${\hat{\overrightarrow{\mu }}}_p(v_i)$$ \hat{\vec \mu}_{p}(v_i) $ 来估计期望${\overrightarrow{\mu }}_p(v_i)={\mathbb{E}}_{p(u_j\mid v_i)}\left[{\overrightarrow{\mathbf{h}}}_j^{(l)}\right]$$ \vec\mu_{p}(v_i) =\mathbb E_{p(u_j\mid v_i)}\left[\mathbf{\vec h}^{(l)}_j\right] $ ：

   $${\hat{\overrightarrow{\mu }}}_p(v_i)=\frac{1}{\hat{n}}\sum _{u_j\in \{{\hat{u}}_1,\cdots ,{\hat{u}}_{\hat{n}}\}}{\overrightarrow{\mathbf{h}}}_j^{(l)},{\hat{u}}_j\sim p(u_j\mid v_i)$$

   其中$\hat{n}\ll n$$ \hat n \ll n $ 为采样的节点数量，$\{{\hat{u}}_1,\cdots ,{\hat{u}}_{\hat{n}}\}$$ \{\hat u_1,\cdots,\hat u_{\hat n}\} $ 为采样的节点集合，采样分布为$p(u_j\mid v_i)$$ p(u_j\mid v_i) $ 。

   使用蒙特卡洛采样之后，GCN 前向传播公式的计算复杂度从$O(|\mathcal{E}|\times d_l\times d_{l-1})$$ O(|\mathcal E| \times d_l\times d_{l-1}) $ 降低到$O({\hat{n}}^2\times d_l\times d_{l-1})$$ O(\hat n^2\times d_l\times d_{l-1}) $ 。

   然后我们以自顶向下的方式构造网络结构：递归地对当前层中每个节点的邻居进行采样，如下图所示。这里实线表示采样到的节点，虚线表示为未采样到的节点，红色节点表示至少有两个父节点的节点。

   

   虽然node-wise 采样能够降低单层的计算复杂度，但是对于深度网络而言，这样的 node-wise 采样在计算上仍然昂贵，因为要采样的节点数量随着层数呈指数增长。假设网络有$L$$ L $ 层，则输入层中的采样节点数量将增加到$O({\hat{n}}^L)$$ O(\hat n^L) $ 。对于较深的网络（即$L$$ L $ 较大），则会导致较大的计算负担。

   通常 graph 是稀疏的，因此节点邻域的规模远远小于$n$$ n $ ，绝大多数${\hat{A}}_{i,j}=0$$ \hat A_{i,j}=0 $ 。因此，上面的$\sum _{j=1}^n$$ \sum_{j=1}^n $ 可以降低到$\sum _{j=1}^{d_i}$$ \sum_{j=1}^{d_i} $ ，其中$d_i$$ d_i $ 为父节点$v_i$$ v_i $ 的 degree 。

2. layer-wise 采样：通过应用重要性采样，我们进一步地将 GCN 前向传播公式重写为以下形式：

   $${\overrightarrow{\mathbf{h}}}_i^{(l+1)}={\sigma }_{{\mathbf{W}}^{(l)}}(d_i\times {\mathbb{E}}_{p(u_j\mid v_i)}\left[{\overrightarrow{\mathbf{h}}}_j^{(l)}\right])={\sigma }_{{\mathbf{W}}^{(l)}}(d_i\times {\mathbb{E}}_{q(u_j\mid v_1,\cdots ,v_{\hat{n}})}\left[\frac{p(u_j\mid v_i)}{q(u_j\mid v_1,\cdots ,v_{\hat{n}})}{\overrightarrow{\mathbf{h}}}_j^{(l)}\right])$$

   其中$q(u_j\mid v_1,\cdots ,v_{\hat{n}})$$ q(u_j\mid v_1,\cdots,v_\hat n) $ 表示给定第$(l+1)$$ (l+1) $ 层所有节点（如$v_1,\cdots ,v_{\hat{n}}$$ v_1,\cdots,v_\hat n $ ）的条件下，采样到第$l$$ l $ 层节点$u_j$$ u_j $ 的概率。

   类似地，我们通过蒙特卡洛Monte-Carlo 方法来估计这个期望值从而加速计算：

   $${\hat{\overrightarrow{\mu }}}_q(v_i)=\frac{1}{\hat{n}}\sum _{u_j\in \{{\hat{u}}_1,\cdots ,{\hat{u}}_{\hat{n}}\}}\frac{p(u_j\mid v_i)}{q(u_j\mid v_1,\cdots ,v_{\hat{n}})}{\overrightarrow{\mathbf{h}}}_j^{(l)},{\hat{u}}_j\sim q(u_j\mid v_1,\cdots ,v_{\hat{n}})$$

   我们这种方法称作 layer-wise 采样策略。

3. layer-wise 采样和 node-wise 采样方法不同：

   • 在 node-wise 采样方法中，每个父节点$v_i$$ v_i $ （位于第$l+1$$ l+1 $ 层）分别独立地采样子节点（位于第$l$$ l $ 层）$\{{\hat{u}}_j{\}}_{j=1}^{\hat{n}}$$ \{\hat u_j\}_{j=1}^{\hat n} $ ，每个采样的分布都不相同（$p(u_j\mid v_i)$$ p(u_j\mid v_i) $ 依赖于父节点$v_i$$ v_i $ ） 。

     并且每个父节点的邻域（子节点集合）对于其它父节点是不可见的。

     另外采样节点数量随着网络深度指数增长。

   • 在 layer-wise 采样方法中，所有父节点$\{v_1,\cdots ,v_{\hat{n}}\}$$ \{v_1,\cdots,v_{\hat n}\} $ 共同采样，只需要采样一轮，使用的是同一个采样分布。

     并且采样到的子节点集合$\{{\hat{u}}_j{\}}_{j=1}^{\hat{n}}$$ \{\hat u_j\}_{j=1}^{\hat n} $ 由所有父节点共享。这种共享的特性能够最大程度地强化消息传递。

     更重要的是，每层的大小固定为$\hat{n}$$ \hat n $ ，使得采样节点数量仅随网络深度线性增长。

33.1.2 显式方差缩减

1. layer-wise 采样剩下的问题是如何定义采样器$q(u_j\mid v_1,\cdots ,v_{\hat{n}})$$ q(u_j\mid v_1,\cdots,v_{\hat n}) $ 的准确形式。确实，一个好的采样器应该减少由于采样过程引起的方差，因为高方差可能会阻碍模型的有效训练。

   为简单起见，我们将分布$q(u_j\mid v_1,\cdots ,v_{\hat{n}})$$ q(u_j\mid v_1,\cdots,v_{\hat n}) $ 简单地表示为下面的$q(u_j)$$ q(u_j) $ 。根据《Monte Carlo theory, methods and examples》 中重要性抽样的推导，我们得出结论：

   命题：estimator${\hat{\overrightarrow{\mu }}}_q(v_i)$$ \hat{\vec\mu}_q(v_i) $ 的方差为：

   $${\text{Var}}_q({\hat{\overrightarrow{\mu }}}_q(v_i))=\frac{1}{\hat{n}}{\mathbb{E}}_{q(u_j)}\left[\frac{{(p(u_j\mid v_i)\Vert {\overrightarrow{\mathbf{h}}}_j^{(l)}\Vert -\Vert {\overrightarrow{\mu }}_q(v_i)\Vert q(u_j))}^2}{q^2(u_j)}\right]$$

   最小化上式中方差${\text{Var}}_q({\hat{\overrightarrow{\mu }}}_q(v_i))$$ \text{Var}_q\left(\hat{\vec \mu}_q(v_i)\right) $ 的最优采样器为：

   $$q^{\ast }(u_j)=\frac{p(u_j\mid v_i)\Vert {\overrightarrow{\mathbf{h}}}_j^{(l)}\Vert }{\sum _{k=1}^{n}p(u_k\mid v_i)\Vert {\overrightarrow{\mathbf{h}}}_k^{(l)}\Vert }$$

   不幸的是，这里得到的最优采样器是不可行的。根据定义，采样器$q^{\ast }(u_j)$$ q^*(u_j) $ 基于 hidden feature${\overrightarrow{\mathbf{h}}}_j^{(l)}$$ \mathbf{\vec h}^{(l)}_j $ 来计算，而后者是根据节点$u_j$$ u_j $ 在第$l-1$$ l-1 $ 层的邻域聚合而成的。但是在我们自上而下的采样框架下，除非通过采样完全构建了网络，否则在采样第$l$$ l $ 层的节点时，更低层（如第$l-1$$ l-1 $ 层）的采样节点是未知的。

2. 为缓解这个 “鸡和蛋” 的困境，我们学习了每个节点的自依赖函数self-dependent function，从而确定每个节点对于采样的重要性。

   令${\overrightarrow{\mathbf{g}}}_j=g\left({\overrightarrow{\mathbf{x}}}_j\right)$$ \mathbf{\vec g}_j = g\left(\mathbf{\vec x}_j\right) $ 表示基于节点$u_j$$ u_j $ 的特征向量${\overrightarrow{\mathbf{x}}}_j$$ \mathbf{\vec x}_j $ 计算得到的自依赖函数，我们将其替换掉上式中的 hidden feature，则得到：

   $$q^{\ast }(u_j)=\frac{p(u_j\mid v_i)\Vert {\overrightarrow{\mathbf{g}}}_j\Vert }{\sum _{k=1}^{n}p(u_k\mid v_i)\Vert {\overrightarrow{\mathbf{g}}}_k\Vert }$$

   在本文中，我们定义$g(\cdot )$$ g(\cdot) $ 为一个线性函数：

   $$g\left({\overrightarrow{\mathbf{x}}}_j\right)={\mathbf{W}}_g{\overrightarrow{\mathbf{x}}}_j$$

   其中${\mathbf{W}}_g\in {\mathbb{R}}^{d\times d_f}$$ \mathbf W_g\in \mathbb R^{d\times d_f} $ 为待学习的参数，$d_f$$ d_f $ 为输入特征向量的维度，$d$$ d $ 为 hidden feature 的维度。

3. 现在我们得到了 node-wise 采样器，并且对于不同的$v_i$$ v_i $ 有所不同。为了使其适用于 layer-wise 采样，我们汇总了所有节点$\{v_i{\}}_{i=1}^{\hat{n}}$$ \{v_i\}_{i=1}^{\hat n} $ 上的计算，因此得到：

   $$q^{\ast }(u_j)=\frac{\sum _{i=1}^{\hat{n}}p(u_j\mid v_i)\Vert {\overrightarrow{\mathbf{g}}}_j\Vert }{\sum _{k=1}^n\sum _{i=1}^{\hat{n}}p(u_k\mid v_i)\Vert {\overrightarrow{\mathbf{g}}}_k\Vert }$$

   这里定义的采样器是高效的，因为$p(u_j\mid v_i)$$ p(u_j\mid v_i) $ 根据邻接矩阵来计算、自依赖函数${\overrightarrow{\mathbf{g}}}_j$$ \mathbf{\vec g}_j $ 根据节点输入特征${\overrightarrow{\mathbf{x}}}_j$$ \mathbf{\vec x}_j $ 来计算，二者计算速度很快。

   $p(u_j\mid v_i)$$ p(u_j\mid v_i) $ 就是从节点$v_i$$ v_i $ 转移到$u_j$$ u_j $ 的概率，可以在预处理中快速处理，且仅需要处理一次即可。

4. 注意，通过$q^{\ast }(u_j)$$ q^*(u_j) $ 定义的采样器不一定会导致最小的方差，因为我们还有一个参数${\mathbf{W}}_g$$ \mathbf W_g $ 待学习。为了实现方差缩减，我们将方差添加到损失函数中，并通过模型训练显式最小化方差。

   假设有一个mini-batch 的数据pair 对${\{(v_i,y_i)\}}_{i=1}^{\hat{n}}$$ \left\{(v_i,y_i)\right\}_{i=1}^{\hat n} $ ，其中$v_i$$ v_i $ 是目标节点，$y_i$$ y_i $ 是对应的 ground-truth label。

   • 通过 layer-wise 采样，给定$\{v_i{\}}_{i=1}^{\hat{n}}$$ \{v_i\}_{i=1}^{\hat n} $ 的情况下对前一层的节点进行采样，然后逐层递归地调用采样过程，直到达到输入层。
   • 然后执行自下而上的传播以计算 hidden feature 并获得节点$v_i$$ v_i $ 的估计的激活值，即${\hat{\overrightarrow{\mu }}}_q(v_i)$$ \hat {\vec \mu}_q(v_i) $ 。
   • 然后将某些非线性函数和 softmax 函数进一步添加到${\hat{\overrightarrow{\mu }}}_q(v_i)$$ \hat {\vec \mu}_q(v_i) $ 上，则生成了预测${\hat{y}}_i$$ \hat y_i $ 。

   考虑分类损失和采样方差，我们将混合损失定义为：

   $$\mathcal{L}=\frac{1}{\hat{n}}\sum _{i=1}^{\hat{n}}{\mathcal{L}}_c(y_i,{\hat{y}}_i)+\lambda {\text{Var}}_q({\hat{\overrightarrow{\mu }}}_q(v_i))$$

   其中：

   • ${\mathcal{L}}_c$$ \mathcal L_c $ 为分类损失（如交叉熵）。
   • $\lambda$$ \lambda $ 为trade-off 超参数，在我们的实验中固定为 0.5 。

   注意：这里的方差实际上是节点$v_i$$ v_i $ 最后一层 embedding 向量的各维度方差的和（方差是跨多个采样之间来计算）。另外这里只考虑最后一层 embedding 的方差，并未考虑中间层embedding 的方差。

   为了计算最后一项（方差项），需要对每个 batch 执行多次采样，从而对同一个父节点的多个估计激活值计算方差。

   在损失函数中我们仅对最后一层的embedding 的方差进行惩罚以进行有效的计算，并发现它足以在我们的实验中提供有效的性能。

5. 为了使得混合损失最小化，我们需要对混合损失进行梯度计算。

   • 对于网络参数，如${\mathbf{W}}^{(l)}$$ \mathbf W^{(l)} $ ，梯度计算非常简单，可以通过自动微分工具（如 Tensorflow）轻松得到。
   • 对于采样器参数，如${\mathbf{W}}_g$$ \mathbf W_g $ ，由于采样过程是不可微的，因此计算得到的梯度是无意义的。

   幸运的是，我们证明了分类损失相对于采样器的梯度为零。我们还推导出有关采样器方差项相对于采样器的梯度。详细内容在原始论文的补充材料给出。

33.1.3 Skip Connection

1. GCN 的更新方程仅聚合来自 1-hop 邻域的消息。为了使网络更好地利用远处节点上的信息，我们可以用类似于随机游走的方式来采样multi-hop 邻域，从而用于 GCN 更新。然而，随机游走需要额外的采样来获得远处的节点，这对于稠密图而言计算代价太高。

   本文中我们提出通过 skip connection 来传播远处节点的信息。skip connection 的关键思想是重用第$(l-1)$$ (l-1) $ 层的节点来保留二阶邻近性。对于第$(l+1)$$ (l+1) $ 层，第$(l-1)$$ (l-1) $ 层的节点实际上是 2-hop 邻域。如果我们进一步从$(l-1)$$ (l-1) $ 层到第$(l+1)$$ (l+1) $ 层添加一个 skip connection，则聚合将涉及 1-hop 邻域和 2-hop 邻域。

   具体而言，skip connection 的更新方程为：

   $${\overrightarrow{\mathbf{h}}}_{\text{skip}}^{(l+1)}(v_i)=\sum _{j=1}^{\hat{n}}{\hat{A}}_{\text{skip}}(v_i,s_j){\mathbf{W}}_{\text{skip}}^{(l-1)}{\overrightarrow{\mathbf{h}}}^{(l-1)}(s_j),i=1,\cdots ,\hat{n}$$

   其中：

   • $\mathcal{S}=\{s_j{\}}_{j=1}^{\hat{n}}$$ \mathcal S=\{s_j\}_{j=1}^{\hat n} $ 为第$(l-1)$$ (l-1) $ 层的节点。

   • 由于$v_i$$ v_i $ 和$s_j$$ s_j $ 之间隔了两跳，因此系数${\hat{A}}_{\text{skip}}(v_i,s_j)$$ \hat A_\text{skip}(v_i,s_j) $ 是${\hat{\mathbf{A}}}^2$$ \hat {\mathbf A}^2 $ 的元素。为避免直接计算${\hat{\mathbf{A}}}^2$$ \hat {\mathbf A}^2 $ ，我们通过第$l$$ l $ 层采样的节点来估计这个权重：

     $${\hat{A}}_{\text{skip}}(v_i,s_j)\simeq \sum _{k=1}^{\hat{n}}\hat{A}(v_i,u_k)\hat{A}(u_k,s_j)$$

     虽然论文实验表明显式计算${\hat{\mathbf{A}}}^2$$ \hat{\mathbf A} ^2 $ 的 skip connection 能提高模型效果，但是这里的近似计算带来的噪音使得最终没有效果提升。

   • 我们并未学习一个额外的参数${\mathbf{W}}_{\text{skip}}^{(l-1)}$$ \mathbf W_\text{skip}^{(l-1)} $ ，而是将其分解为：

     $${\mathbf{W}}_{\text{skip}}^{(l-1)}={\mathbf{W}}^{(l)}{\mathbf{W}}^{(l-1)}$$

     其中${\mathbf{W}}^{(l)}$$ \mathbf W^{(l)} $ 为第$l$$ l $ 层的网络参数。

   skip connection 的输出可以加到 GCN layer，在非线性层之前。

   考虑到 skip connection 的更新方程为：

   $${\overrightarrow{\mathbf{h}}}_i^{(l+1)}=\sigma ({\overrightarrow{\mathbf{h}}}_{\text{skip}}^{(l+1)}(v_i)+\sum _{j=1}^{\hat{n}}\frac{p(u_j\mid v_i)}{q^{\ast }(u_j)}{\mathbf{W}}^{(l)}{\overrightarrow{\mathbf{h}}}_j^{(l)})$$

2. 通过skip connection，无需额外的 2-hop 采样即可保持二阶邻近性。此外，skip connection 允许信息在两个远距离的层之间传递，从而实现了更有效的反向传播和模型训练。

   尽管设计相似，但是我们使用 skip-connection 的动机和 ResNet 中的残差函数不同：

   • 在ResNet 中，使用 skip connection 的目的是通过增加网络深度来获得更好的准确率。
   • 在我们这里，使用skip connection 用于保留二阶邻近性second-order proximity 。

   另外和 ResNet 中使用恒等映射相反，我们模型中沿着 skip connection 的计算更加复杂，如${\overrightarrow{\mathbf{h}}}_{\text{skip}}^{(l+1)}(v_i)=\sum _{j=1}^{\hat{n}}{\hat{A}}_{\text{skip}}(v_i,s_j){\mathbf{W}}_{\text{skip}}^{(l-1)}{\overrightarrow{\mathbf{h}}}^{(l-1)}(s_j)$$ \mathbf{\vec h}_\text{skip}^{(l+1)}(v_i) = \sum_{j=1}^{\hat n} \hat A_\text{skip}(v_i,s_j) \mathbf W_\text{skip}^{(l-1)}\mathbf{\vec h}^{(l-1)}(s_j) $ 。

3. 如下图所示，使用不同采样方法来构建网络：(a) 表示 node-wise 采样方法；(b) 表示 layer-wise 方法；(c) 表示考虑 skip-connection 的采样方法。

   实线表示采样节点，虚线表示未采样节点，红色圆圈表示该节点在上层至少有两个父节点。

   • 在 node-wise 采样中，每个父节点的邻域都不会被其它父节点看到，因此父节点邻域和其它父节点之间的连接未被复用。
   • 相反，在 layer-wise 采样中，所有邻域被上层所有父节点所共享，因此利用了所有的层间连接。

   

33.1.4 讨论

1. 和其它采样方法的联系：我们的方法和 GraphSAGE、FastGCN 等方法的区别如下：

   • 我们提出的 layer-wise 采样方法是新颖的。

     • GrphSAGE 对每个节点随机采样固定大小的邻域，是 node-wise 采样的。
     • FastGCN 虽然是 layer-wise 采样的，但是采样的分布对于每一层都是相同的。
     • 我们的 layer-wise 方法，较低层的节点是在较高层节点的条件下进行采样的，这能够捕获层之间的相关性。

   • 我们的框架是更通用的。GraphSAGE 和 FastGCN 都可以归类为我们框架的特定变体，具体而言：

     • 如果将${\hat{\overrightarrow{\mu }}}_p(v_i)=\frac{1}{\hat{n}}\sum _{u_j\in \{{\hat{u}}_1,\cdots ,{\hat{u}}_{\hat{n}}\}}{\overrightarrow{\mathbf{h}}}_j^{(l)},{\hat{u}}_j\sim p(u_j\mid v_i)$$ \hat{\vec\mu}_{p}(v_i) = \frac {1}{\hat n}\sum_{u_j\in \{\hat u_1,\cdots,\hat u_{\hat n}\}}\mathbf{\vec h}^{(l)}_{j},\quad \hat u_j\sim p(u_j\mid v_i) $ 中的$p(u_j\mid v_i)$$ p(u_j\mid v_i) $ 定义为均匀分布，则 GraphSAGE 被视为一个 node-wise 采样器。
     • 如果将${\hat{\overrightarrow{\mu }}}_q(v_i)=\frac{1}{\hat{n}}\sum _{u_j\in \{{\hat{u}}_1,\cdots ,{\hat{u}}_{\hat{n}}\}}\frac{p(u_j\mid v_i)}{q(u_j\mid v_1,\cdots ,v_{\hat{n}})}{\overrightarrow{\mathbf{h}}}_j^{(l)},{\hat{u}}_j\sim q(u_j\mid v_1,\cdots ,v_{\hat{n}})$$ \hat{\vec\mu}_q(v_i) = \frac{1}{\hat n}\sum_{u_j\in \{\hat u_1,\cdots,\hat u_{\hat n}\}}\frac{p( u_j\mid v_i)}{q(u_j\mid v_1,\cdots,v_\hat n)}\mathbf{\vec h}^{(l)}_j,\quad \hat u_j\sim q( u_j\mid v_1,\cdots,v_{\hat n}) $ 中的$q(u_j\mid v_1,\cdots ,v_{\hat{n}})$$ q(u_j\mid v_1,\cdots,v_{\hat n}) $ 独立于节点$\{v_i{\}}_{i=1}^{\hat{n}}$$ \{v_i\}_{i=1}^{\hat n} $ ，则FastGCN 可以视为一个特殊的 layer-wise 方法。

   • 我们的采样器是参数化的，并且可以训练来显式减少方差。

     • GraphSAGE 和 FastGCN 的采样器不包含任何参数，并且没有自适应来最小化方差。
     • 相反，我们的采样器通过自依赖函数来调整最优重要性采样分布optimal importance sampling distribution 。通过对网络和采样器进行微调，可以显著减少结果的方差。

2. 考虑 attention 机制：GAT 将 self-attention 机制应用于图representation learning 。简而言之，它使用特定的 attention 值来取代 GCN 中的归一化邻接矩阵，即：

   $${\overrightarrow{\mathbf{h}}}_i^{(l+1)}=\sigma \left(\sum _{j=1}^{n}a({\overrightarrow{\mathbf{h}}}_i^{(l)},{\overrightarrow{\mathbf{h}}}_j^{(l)}){\mathbf{W}}^{(l)}{\overrightarrow{\mathbf{h}}}_j^{(l)}\right)$$

   其中$a({\overrightarrow{\mathbf{h}}}_i^{(l)},{\overrightarrow{\mathbf{h}}}_j^{(l)})$$ a\left(\mathbf{\vec h}_i^{(l )},\mathbf{\vec h}_j^{(l )}\right) $ 衡量了$v_i$$ v_i $ 和$u_j$$ u_j $ 的 hiden feature 之间的attention value 。它通常计算为：

   $$a({\overrightarrow{\mathbf{h}}}_i^{(l)},{\overrightarrow{\mathbf{h}}}_j^{(l)})=\text{softmax}\left(\text{LeakyRelu}({\mathbf{W}}_1{\overrightarrow{\mathbf{h}}}_i^{(l)},{\mathbf{W}}_2{\overrightarrow{\mathbf{h}}}_j^{(l)})\right)$$

   其中${\mathbf{W}}_1,{\mathbf{W}}_2$$ \mathbf W_1, \mathbf W_2 $ 为两个待学习的参数。

   直接在我们的框架中应用类似于 GAT 的注意力机制是不可行的，因为概率$p(u_j\mid v_i)$$ p(u_j\mid v_i) $ 和 attention 值$a({\overrightarrow{\mathbf{h}}}_i^{(l)},{\overrightarrow{\mathbf{h}}}_j^{(l)})$$ a\left(\mathbf{\vec h}_i^{(l )},\mathbf{\vec h}_j^{(l )}\right) $ 相关，而$a({\overrightarrow{\mathbf{h}}}_i^{(l)},{\overrightarrow{\mathbf{h}}}_j^{(l)})$$ a\left(\mathbf{\vec h}_i^{(l )},\mathbf{\vec h}_j^{(l )}\right) $ 需要由第$l$$ l $ 层的 hidden feature 来决定。如前所述，除非在采样后已经建立了网络，否则就不可能计算出较低层的 hidden feature。

   为解决这个问题，我们通过应用类似于自依赖函数开发了一种新的注意力机制：

   $$a({\overrightarrow{\mathbf{x}}}_i,{\overrightarrow{\mathbf{x}}}_j)=\frac{1}{\hat{n}}\times \text{relu}({\overrightarrow{\mathbf{w}}}_1\cdot {\overrightarrow{\mathbf{g}}}_i+{\overrightarrow{\mathbf{w}}}_2\cdot {\overrightarrow{\mathbf{g}}}_j)$$

   其中：${\overrightarrow{\mathbf{w}}}_1,{\overrightarrow{\mathbf{w}}}_2$$ \mathbf {\vec w}_1, \mathbf {\vec w}_2 $ 为待学习的参数；${\overrightarrow{\mathbf{g}}}_j=g\left({\overrightarrow{\mathbf{x}}}_j\right)$$ \mathbf{\vec g}_j = g\left(\mathbf{\vec x}_j\right) $ 表示基于节点$u_j$$ u_j $ 的特征向量${\overrightarrow{\mathbf{x}}}_j$$ \mathbf{\vec x}_j $ 计算得到的自依赖函数。

33.2 实验

1. 数据集：

   • 引文网络数据集Cora,Citeseer,Pubmed：目标是对学术论文进行分类。
   • Reddit 数据集：目标是预测不同的帖子属于哪个社区 community 。

   这些图的规模从小到大都有所不同。具体而言：Cora,Citeseer 的节点数量为$O({10}^3)$$ O(10^3) $ ；Pubmed 数据集包含超过${10}^4$$ 10^4 $ 个节点；Reddit 数据集包含超过${10}^5$$ 10^5 $ 个节点。

   下表给出了这些数据集的统计量。

   

2. 实验配置：

   • 根据 FastGCN 中的监督学习场景，我们使用训练样本的所有标签进行训练。
   • 我们的采样框架是 inductive learning 的。和提供了所有节点的 transductive learning 不同，我们的方法聚合来自每个节点的邻域信息，从而学到可以泛化到未见过节点的结构属性。
   • 为了进行测试，可以使用全部邻域来计算新节点的 embedding，也可以像模型训练中那样通过采样进行近似。这里我们使用完整的邻域，因为它更直接、更容易实现。
   • 对于所有数据集，我们使用具有两个隐层的网络。对于引文网络数据集，隐层维度为 16 ；对于Reddit 数据集，隐层维度为 256 。
   • 对于 Reddit 数据集，我们固定底层的权重，并且预计算$\hat{\mathbf{A}}{\mathbf{H}}^{(0)}$$ \hat{\mathbf A} \mathbf H^{(0)} $ 来作为输入特征从而提高效率。其中${\mathbf{H}}^{(0)}=\mathbf{X}$$ \mathbf H^{(0)}=\mathbf X $ 。
   • 对于所有数据集，顶层的 layer-wise采样数量为 256，非顶层的 layer-wise 采样数量为：Cora, Citeseer 数据集 128、Pubmed 数据集 256、Reddit 数据集 512 。
   • 使用 Adam 优化器，初始学习率为：对于 Cora,Citeseer,Pubmed 设置为 0.001、对于 Reddit 为 0.01。
   • 所有数据集的权重衰减设置为 0.0004 。
   • 所有数据集采用 ReLU 激活函数，并且没有 dropout。
   • 训练期间使用窗口为 30 的早停来训练所有模型，并选择最佳验证准确率的模型用于测试。
   • 所有实验是在单个 Tesla P40 GPU 上进行。

3. baseline 方法：由于 GraphSAGE 和 FastGCN 它们作者提供的代码不一致，这里我们根据我们的框架重新实现它们，从而进行更公平的比较。

   • 我们通过对$p(u_j\mid v_i)$$ p(u_j\mid v_i) $ 使用均匀的采样器来应用 node-wise 采样，从而实现 GraphSAGE 方法。其中每个节点的邻域采样大小为 5 。这种重新实现命名为 Node-Wise。
   • 我们使用《Fast learning with graph convolutional networks via importance sampling》 中提出的独立同分布采样器来实现$q(u_j\mid v_1,\cdots ,v_{\hat{n}})$$ q(u_j\mid v_1,\cdots,v_{\hat n}) $ ，其中每一层采样的节点数量和我们的方法相同。这种重新实现命名为 IID。
   • 我们还将 Full GCN 体系架构作为强大的 baseline 。

   所有比较的方法共享相同的网络结构和训练设置，以进行公平的比较。

   我们还对所有方法进行了前述介绍的注意力机制。

4. 不同采样方法的比较：这里我们固定随机数种子，并且不进行任何早停实验。下图报告了Cora,Citeseer, Reddit 训练期间所有采样方法的收敛行为。曲线代表测试数据上的准确率曲线accuracy curve。这里一个 training epoch 意味着对所有训练样本进行一次完整的遍历。

   另外，为证明方差缩减的重要性，我们通过设置$\lambda =0$$ \lambda=0 $ 来得到我们模型的变体，称作 Adapt(no vr) 。其中自依赖函数的参数被随机初始化，并且不进行训练。

   可以看到：

   • 我们的方法（称作 Adapt） 在所有三个数据集上的收敛速度都比其它采样方法更快。

   • 有趣的是，我们的方法甚至优于 Cora,Reddit 上的 Full 模型。

   • 和我们的方法类似，IID 采样也是 layer-wise 的，但是它独立地构造了每一层。和IID 采样相比，由于有条件采样，我们的方法获得了更稳定的收敛曲线。

     事实证明，考虑层间信息有助于提高模型训练的稳定性stability 和准确性accuracy 。

   • 移除方差缩减的损失项确实会降低我们的方法在 Cora 和 Reddit 上的准确率。对于 Citeseer 而言，移除方差缩减的损失项的效果不是很明显。我们推测这是因为 Citeseer 的平均 degree （1.4）小于 Cora （2.0）和 Reddit（492），并且由于邻域的多样性有限，因此对方差的惩罚并没有那么重要。

   

   此外我们还给出了Pubmed 和 Reddit 数据集的训练时间，单位：second/epoch 。可以看到：

   • 所有方法的训练速度都比完整模型更快。

   • 和 node-wise 方法相比，我们的方法具有更紧凑的体系结构，因此具有更快的训练速度。

     为了说明这一点，假设顶层的节点数量为$\hat{n}$$ \hat n $ ，那么node-wise 方法的输入层、隐层、顶层的大小分别为$25\hat{n},5\hat{n},\hat{n}$$ 25\hat n,5\hat n,\hat n $ （每个节点的邻域采样大小固定为 5 ）。而我们模型中所有层的节点数量为$\hat{n}$$ \hat n $ 。即使使用更少的采样节点，我们的模型仍然超越了 node-wise 方法。

   

5. 和其它 state-of-the-art 方法的比较：我们使用 graph kernel 方法 KLED 和 Diffusion Convolutional Network:DCN 对比了我们方法的性能。

   • 我们使用 Cora 和 Pubmed 在《Diffusion-convolutional neural networks》 中报道的 KLED 和 DCN 的结果。
   • 我们还通过其原始实现总结了 GraphSAGE 和 FastGCN 的结果。对于 GraphSAGE，我们报告了具有默认参数的均值聚合结果。对于 FastGCN，我们直接使用 《Diffusion-convolutional neural networks》 提供的结果。

   对于 baseline 和我们的方法，我们使用随机数种子进行 20多个随机实验，并记录了测试集的平均准确率和标准差。所有结果如下表所示，可以看到：

   • 我们的方法在所有数据集中都实现了最佳性能。
   • 移除方差缩减将降低我们方法的性能，尤其是在 Cora 和 Reddit 上。

   另外，仅对顶层进行方差缩减就能够提升性能。事实上，在我们的方法中对所有层进行方差缩减也是方便的，例如将它们都添加到损失函数中。为说明这一点，我们通过最小化第一层和顶层隐层的方差来对 Cora 进行实验，其中实验配置和下表相同。结果为 0.8780 +- 0.0014，这比下表中的 0.8744 +- 0.0034 要更好。

   

6. 我们使用公开的代码重新运行了 FastGCN 实验。四个数据集的 FastGCN 的平均准确率为 0.840 +- 0.005、0.774 +- 0.004、0.881 +- 0.002、0.920 +- 0.005 。显然，我们的方法仍然超越了 FastGCN。

   这里重新运行的 FastGCN 和上表给出的结果（来自于各自的原始论文）不一致。

   我们观察到 GraphSAGE和 FastGCN 的官方实现之间的不一致之处，包括邻接矩阵的构造、隐层维度、mini-batch size、最大训练 epoch 数量、以及其它在论文中未提及的工程技巧。

   

7. 我们评估在 Cora 数据集上 skip-connection 的有效性。我们进一步在输入层和顶层之间添加了 skip-connection。下图显式了原始 Adapt 方法以及带skip-connection 变体的收敛曲线。其中随机种子是共享的，并且没有使用早停。

   可以看到：尽管就最终准确率而言，我们的 skip-connection 带来的提升并不大，但是确实可以显著增加收敛速度。添加 skip-connection 可以将收敛 epoch 数量从 150 降低到 100 。

   

   我们在 20 个实验中使用不同的随机数种子进行实验，并在下表报告了使用早停获得的平均结果。可以看到，使用 skip-connection 可以稍微改善性能。

   

   另外，通过将归一化的邻接矩阵$\hat{\mathbf{A}}$$ \hat{\mathbf A} $ 替换为$\hat{\mathbf{A}}+{\hat{\mathbf{A}}}^2$$ \hat{\mathbf A} + \hat{\mathbf A}^2 $ ，我们显式地将 2-hop 邻域采样包含在我们的方法中（直接计算归一化矩阵的二次幂）。如上表所示，显式 2-hop 邻域采样进一步提高了分类准确率。尽管skip-connection 要比显式 2-hop 采样略差一点，但是它避免了${\hat{\mathbf{A}}}^2$$ \hat{\mathbf A}^2 $ 的计算，这对于大型图和稠密度带来了更多的计算优势。

8. 最后，我们评估了 Citeseer,Pubmed 数据集上 skip-connection 的有效性。

   • 对于 Citeseer 数据集，skip-connection 有助于更快地收敛。
   • 对于 Pubmed 数据集，添加 skip-connection 仅在训练的早期才有效果。