十七、VRGCN [2017]

发布于 2023-07-17 23:38:24 字数 286419 浏览 0 评论 0 收藏 0

图卷积网络 graph convolution network: GCN 将卷积神经网络CNN 推广到图结构化数据。图卷积 graph convolution 操作对节点的所有邻居应用相同的线性变换，然后是均值池化和非线性激活函数。通过堆叠多个图卷积层，GCN 可以利用来自遥远邻居的信息来学习 node representation 。GCN 及其变体已被应用于半监督节点分类、inductive node embedding 、链接预测、以及知识图谱，超越了不使用图结构的多层感知机 MLP 以及不使用节点特征的 graph embedding 方法。

然而，图卷积操作使得 GCN 难以高效地训练。考虑一个 $L$ $ L $ 层的图卷积神经网络GCN，节点的第 $l$ $ l $ 层的 hidden feature 需要递归地通过其邻域内所有节点的第 $l - 1$ $ l-1 $ 层 hidden feature 来计算。因此，如下图 (a) 所示，单个节点的感受野receptive field 的大小随网络层数呈指数型增长。
- 为解决感受野太大的问题，《Semi-supervised classification with graph convolutional networks》 提出通过 batch 算法来训练 GCN，该方法同时计算 batch 内所有节点的 representation。但是，由于 batch 算法收敛速度慢，以及需要将整个数据集放入到 GPU 中，因此无法处理大规模数据集。
- 《Inductive representation learning on large graphs》 尝试邻域采样 neighbor sampling: NS 的方法为GCN 提出随机训练算法。在 NS 算法中，他们并未考虑节点的所有邻居，而是为每个节点在第 $l$ $ l $ 层随机采样 $D^{(l)}$ $ D^{(l)} $ 个邻居，如图 (b) 所示。这可以将感受野的大小减小到 $\prod_{l} D^{(l)}$ $ \prod_l D^{(l)} $ 。他们发现对于两层的 GCN 网络，选择 $D^{(1)} = 10, D^{(2)} = 25$ $ D^{(1)}=10, D^{(2)} = 25 $ 可以实现与原始 GCN 相当的性能。
理论上当 $D^{(l)} = 1$ $ D^{(l)} = 1 $ 时（即每个节点的预测仅依靠它本身，不依赖任何其它邻域节点）计算效率最高，此时模型退化为基于节点的多层感知机 MLP 。虽然 Hamilton 的方法复杂度降低，但是仍然比 MLP 要大 $D^{(1)} \times D^{(2)} = 250$ $ D^{(1)}\times D^{(2)} = 250 $ 倍，仍然无法让人满意。

另外，使用基于邻域采样的随机训练算法能否确保模型收敛，尚无理论上的保证。

在论文 《Stochastic Training of Graph Convolutional Networks with Variance Reduction》 中，作者为 GCN 设计了新颖的基于控制变量的 control variate-based 随机逼近算法，即 GCN with Variance Reduction: VRGCN 。

VRGCN 利用节点的历史激活值（即历史hidden feature）作为控制变量control variate 。作者表明：通过邻域采样NS 策略得到的 hidden feature 的方差取决于 hidden feature 的幅度magnitude（因为 hidden feature 是一个向量），而VRGCN 得到的 hidden feature 的方差取决于 hidden feature 和它历史均值之间的差异 difference 。

另外，VRGCN 还带来了理论上的收敛性保证。VRGCN 可以给出无偏的（相比较于原始的 GCN）、零方差的预测。并且训练算法可以收敛到GCN 损失函数的局部最优值，而与采样大小 $D^{(l)}$ $ D^{(l)} $ 无关。理论分析表明：VRGCN 可以通过仅对节点采样两个邻居节点来显著降低模型的时间复杂度，同时保持模型的质量。

作者在六个 graph 数据集上对 VRGCN 进行了实验测试，并表明 VRGCN 显著降低了具有相同感受野大小的 NS 的梯度的偏差 bias 和方差 variance 。尽管仅采样 $D^{(l)} = 2$ $ D^{(l)} = 2 $ 个邻居，但是 VRGCN 在所有数据集上的可比数量的 epoch 中实现了与精确算法相同的预测性能，即，VRGCN 降低了时间复杂度同时几乎没有损失收敛速度，这是我们可以预期的最好结果。在最大的 Reddit 数据集上，VRGCN 算法的训练时间相比精确算法（《Semi-supervised classification with graph convolutional networks》）、邻域采样算法（《Inductive representation learning on large graphs》）、重要性采样算法（《Fastgcn: Fast learning with graph convolutional networks via importance sampling》）要少 7 倍。

17.1 模型

17.1.1 GCN

我们以半监督节点分类任务的 GCN 作为说明，当然我们的算法不局限于任务类型，也不局限于模型类型。我们的算法适用于任何涉及到计算邻居平均激活值的其它模型，以及其它任务。
给定图 $G = (V, E)$ $ G=(\mathcal V,\mathcal E) $ ，其中 $V = {v_{1}, \dots, v_{n}}$ $ \mathcal V=\{v_1,\cdots,v_n\} $ 为节点集合， $E = {e_{i, j}}$ $ \mathcal E=\{e_{i,j}\} $ 为所有边集合，边 $e_{i, j} = (v_{i}, v_{j})$ $ e_{i,j} = (v_i,v_j) $ 为无向边。

每个节点 $v \in V$ $ v\in \mathcal V $ 关联一个特征向量 ${\vec{x}}_{v}$ $ \mathbf{\vec x}_v $ ，以及一个label $y_{v}$ $ y_v $ 。在半监督学习场景中，我们只能观测到部分节点的 label，这部分节点的集合记作 $V_{Y}$ $ \mathcal V_Y $ 。我们的目标是预测剩余节点集合 $V_{U} = V - V_{Y}$ $ \mathcal V_U = \mathcal V- \mathcal V_Y $ 中每个节点的 label 。
定义邻接矩阵 $A \in R^{| V | \times | V |}$ $ \mathbf A\in \mathbb R^{|\mathcal V|\times |\mathcal V|} $ ，其中 $A_{i, j}$ $ A_{i,j} $ 表示节点 $v_{i}, v_{j}$ $ v_i,v_j $ 之间的链接权重，如果 $v_{i}, v_{j}$ $ v_i,v_j $ 之间不存在链接则 $A_{i, j} = 0$ $ A_{i,j} = 0 $ 。由于是无向图因此 $A$ $ \mathbf A $ 是对称矩阵。

定义传播矩阵 propagation matrix $P \in R^{| V | \times | V |}$ $ \mathbf P\in \mathbb R^{|\mathcal V|\times |\mathcal V|} $ 为归一化的邻接矩阵：
$\begin{matrix} \tilde{A} = I + A \\ \tilde{D} = diag ({\tilde{D}}_{i, i}), {\tilde{D}}_{i, i} = \sum_{j} {\tilde{A}}_{i, j} \\ P = {\tilde{D}}^{- 1 / 2} \tilde{A} {\tilde{D}}^{- 1 / 2} \end{matrix}$
其中 $\tilde{A}$ $ \tilde{\mathbf A} $ 为添加了 self-loop 的邻接矩阵。

因此一个图卷积层可以定义为（假设当前为第 $l + 1$ $ l+1 $ 层）：
$\begin{matrix} Z^{(l + 1)} = P H^{(l)} W^{(l)} \\ H^{(l + 1)} = σ (Z^{(l + 1)}) \end{matrix}$
其中：
- $H^{(l)}$ $ \mathbf H^{(l)} $ 为第 $l$ $ l $ 层的hidden feature 矩阵，也称作激活矩阵 activataion matrix。
  
  第 $v$ $ v $ 行 ${\vec{h}}_{v}^{(l)}$ $ \mathbf{\vec h}_v^{(l)} $ 表示节点 $v$ $ v $ 的 hidden feature 向量，也称作激活值 activation。
- $H^{(0)} = X$ $ \mathbf H^{(0)} = \mathbf X $ 为输入的特征矩阵，第 $v$ $ v $ 行 ${\vec{x}}_{v}$ $ \mathbf{\vec x}_v $ 表示节点 $v$ $ v $ 的特征向量。
- $W^{(l)}$ $ \mathbf W^{(l)} $ 为第 $l + 1$ $ l+1 $ 层模型待学习的权重矩阵，它在所有节点上共享。
- $σ (\cdot)$ $ \sigma(\cdot) $ 为非线性激活函数。
假设 GCN 模型有 $L$ $ L $ 层，则GCN 模型的训练损失函数为：
$J = \frac{1}{| V_{Y} |} \sum_{v \in V_{Y}} f (y_{v}, {\vec{z}}_{v}^{(L)})$
其中：
- $f (\cdot, \cdot)$ $ f(\cdot,\cdot) $ 为单个节点的损失函数。
- ${\vec{z}}_{v}^{(L)}$ $ \mathbf{\vec z}_v^{(L)} $ 为 $Z^{(L)}$ $ \mathbf Z^{(L)} $ 的第 $v$ $ v $ 行，表示节点 $v$ $ v $ 的 final representation。
卷积层通过 $P H^{(l)}$ $ \mathbf P\mathbf H^{(l)} $ 计算邻域均值，从而将邻域信息传递到当前节点。定义节点 $v$ $ v $ 的邻域集合为 $N_{v}$ $ \mathcal N_v $ ，则节点 $v$ $ v $ 的邻域均值 hidden feature 向量为：
${\vec{n}}_{v}^{(l)} = \sum_{u = 1}^{V} P_{v, u} {\vec{h}}_{u}^{(l)} = \sum_{u \in N_{v}} P_{v, u} {\vec{h}}_{u}^{(l)}$
它就是 $P H^{(l)}$ $ \mathbf P \mathbf H^{(l)} $ 的第 $v$ $ v $ 行，等于邻域hidden feature 的加权和。

定义节点 $v$ $ v $ 在第 $l$ $ l $ 层的感受野 receptive field 为：为计算 ${\vec{z}}_{v}^{(L)}$ $ \mathbf{\vec z}_v^{(L)} $ 所需要的 ${\vec{h}}_{u}^{(l)}$ $ \mathbf{\vec h}_u^{(l)} $ 的节点集合。
- 对于一个 $L$ $ L $ 层的 GCN，节点 $v$ $ v $ 的所有感受野就是它的 L-hop 邻域集合。
- 当 $P = I$ $ \mathbf P = \mathbf I $ 时，GCN 退化为一个多层感知机 MLP，其中不涉及任何图结构信息。对于多层感知机，节点 $v$ $ v $ 的感受野就是它本身 ${v}$ $ \{v\} $ 。
GCN 训练损失函数的 batch 梯度为：
$\nabla J = \frac{1}{| V_{Y} |} \sum_{v \in V_{Y}} \nabla f (y_{v}, {\vec{z}}_{v}^{(L)})$
由于每次迭代都涉及整个标记节点集合 $V_{Y}$ $ \mathcal V_Y $ ，因此计算 batch 梯度代价太大。

一个可行的方案是采用随机梯度作为 batch 梯度的近似值：
$\nabla J ≃ \frac{1}{| V_{B} |} \sum_{v \in V_{B}} \nabla f (y_{v}, {\vec{z}}_{v}^{(L)})$
其中 $V_{B} \subset V_{Y}$ $ \mathcal V_B\sub \mathcal V_Y $ 为标记节点集合的一个 mini-batch 。

但是，由于感受野太大，mini-batch 梯度的计算代价仍然很高。例如，NELL 数据集的 2-hop 邻域平均包含 1597 个节点，这意味着在一个 2 层 GCN 中，为计算单个节点的梯度需要涉及 1597/65755 = 2.4% 的全部节点。

17.1.2 GraphSAGE

为降低感受野大小，GraphSAGE 提出了邻域采样neighbor sampling: NS 策略。在第 $l$ $ l $ 层，对于每个节点 NS 策略随机采样 $D^{(l)}$ $ D^{(l)} $ 个邻居，并基于蒙特卡洛近似来给出节点 $v$ $ v $ 的邻域均值 hidden feature ${\vec{n}}_{v}^{(l)}$ $ \mathbf{\vec n}_v^{(l)} $ 的一个近似估计 ${\vec{n}}_{N S, v}^{(l)}$ $ \mathbf{\vec n}_{NS,v}^{(l)} $ ：
${\vec{n}}_{v}^{(l)} ≃ {\vec{n}}_{N S, v}^{(l)} = \frac{| N_{v} |}{D^{(l)}} \sum_{u \in {\hat{N}}_{v}^{(l)}} P_{v, u} {\vec{h}}_{u}^{(l)}$
其中 ${\hat{N}}_{v}^{(l)} \subset N_{v}$ $ \hat{\mathcal N}_v^{(l)}\sub \mathcal N_v $ 为一个大小为 $D^{(l)}$ $ D^{(l)} $ 的、邻域 $N_{v}$ $ \mathcal N_v $ 的一个随机子集。

因此 NS 策略降低了感受野大小，从 L-hop 邻域大小降低到采样后的邻域大小 $\prod_{l = 1}^{L} D^{(l)}$ $ \prod_{l=1}^L D^{(l)} $ 。

我们将 ${\vec{n}}_{N S, v}^{(l)}$ $ \mathbf{\vec n}_{NS,v}^{(l)} $ 称作 ${\vec{n}}_{v}^{(l)}$ $ \mathbf{\vec n}_v^{(l)} $ 的 NS 估计量，而 ${\vec{n}}_{v}^{(l)}$ $ \mathbf{\vec n}_v^{(l)} $ 为精确值 exact 。

上述邻域采样策略以矩阵的形式可以重写为：
$\begin{matrix} Z^{(l + 1)} = {\hat{P}}^{(l)} H^{(l)} W^{(l)} \\ H^{(l + 1)} = σ (Z^{(l + 1)}) \end{matrix}$
其中传播矩阵 $P$ $ \mathbf P $ 被替换为一个稀疏的、无偏的估计 ${\hat{P}}^{(l)}$ $ \hat{\mathbf P}^{(l)} $ ，即满足： $E [{\hat{P}}^{(l)}] = P$ $ \mathbb E\left[\hat{\mathbf P}^{(l)}\right ] = \mathbf P $ 。采样后的传播矩阵 ${\hat{P}}^{(l)}$ $ \hat{\mathbf P}^{(l)} $ 为：
$\begin{matrix} {\hat{P}}_{v, u}^{(l)} = {\begin{cases} \frac{| N_{v} |}{D^{(l)}} P_{v, u} & , u \in {\hat{N}}_{v}^{(l)} \\ 0 & , else \end{cases} \end{matrix}$
在 GraphSAGE 的随机梯度下降过程中，存在两个随机性来源：
- 选择 mini-batch $V_{B} \subset V_{Y}$ $ \mathcal V_B\sub \mathcal V_Y $ 引入的随机性。
- 选择大小为 $D^{(l)}$ $ D^{(l)} $ 的邻域集合 ${\hat{N}}_{v}^{(l)} \subset N_{v}$ $ \hat{\mathcal N}_v^{(l)}\sub \mathcal N_v $ 引入的随机性。
尽管 ${\hat{P}}^{(l)}$ $ \hat{\mathbf P}^{(l)} $ 是 $P$ $ \mathbf P $ 的无偏估计，但是由于非线性函数 $σ (\cdot)$ $ \sigma(\cdot) $ 的存在， $σ ({\hat{P}}^{(l)} H^{(l)} W^{(l)})$ $ \sigma\left(\hat{\mathbf P}^{(l)}\mathbf H^{(l)} \mathbf W^{(l)}\right) $ 并不是 $σ (P^{(l)} H^{(l)} W^{(l)})$ $ \sigma\left(\mathbf P ^{(l)}\mathbf H^{(l)} \mathbf W^{(l)}\right) $ 的无偏估计。因此，在 NS 策略中节点的 final representaion 矩阵 $Z^{(L)}$ $ \mathbf Z^{(L)} $ 以及梯度 $\nabla f (y_{v}, {\vec{z}}_{v}^{(L)})$ $ \nabla f\left(y_v,\mathbf{\vec z}_v^{(L)}\right) $ 都是有偏的。最终 NS 策略中随机梯度下降 SGD 的收敛性得不到保障，除非采样大小 $D^{(l)}$ $ D^{(l)} $ 趋向于无穷大。因为这时候计算的梯度 $\nabla f (y_{v}, {\vec{z}}_{v}^{(L)})$ $ \nabla f\left(y_v,\mathbf{\vec z}_v^{(L)}\right) $ 是有偏的，无法保证它是沿着梯度的正确方向。
在 GraphSAGE 中，由于梯度是有偏的，因此 NS 策略中的采样大小 $D^{(l)}$ $ D^{(l)} $ 必须很大，从而确保模型得到和 exact 策略相近的预测性能。

在 GraphSAGE 中Hamilton 选择 $D^{(1)} = 10, D^{(2)} = 25$ $ D^{(1)} = 10, D^{(2)} = 25 $ ，因此感受野的大小为 $D^{(1)} \times D^{(2)} = 250$ $ D^{(1)}\times D^{(2)} = 250 $ ，这远大于 MLP 的感受野（大小为 1），因此训练仍然代价较高。

17.1.3 FastGCN

FastGCN 是另一种类似于NS 的基于采样的算法。FastGCN 并没有为每个节点采样邻域，而是直接采样每一层的、所有节点共享的感受野。

对于第 $l$ $ l $ 层，FastGCN 首先采样 $D^{(l)}$ $ D^{(l)} $ 个样本的集合 $S^{(l)} = {v_{1}^{(l)}, \dots, v_{D^{(l)}}^{(l)}}$ $ \mathbb S^{(l)}=\left\{v_1^{(l)},\cdots,v_{ D^{(l) }}^{(l)}\right\} $ ，然后通过这 $D^{(l)}$ $ D^{(l)} $ 个样本来计算每个节点 $v$ $ v $ 的邻域均值 hidden feature ${\vec{n}}_{v}^{(l)}$ $ \mathbf{\vec n}_v^{(l)} $ ：
${\vec{n}}_{v}^{(l)} = \sum_{u = 1}^{V} P_{v, u} {\vec{h}}_{u}^{(l)} ≃ \frac{| V |}{D^{(l)}} \sum_{u \in S} P_{v, u} {\vec{h}}_{u}^{(l)} / q (u)$
其中重要性分布：
$q (u) \propto \sum_{v = 1}^{| V |} P_{u, v}^{2}$
我们将这种邻域均值 hidden feature 的估计称作重要性采样 importance sampling: IS 。
- 注意，IS 采样策略和 NS 采样策略的区别在于：前者为第 $l$ $ l $ 层所有节点采样 $D^{(l)}$ $ D^{(l)} $ 个节点，后者为第 $l$ $ l $ 层每个节点分别采样 $D^{(l)}$ $ D^{(l)} $ 个节点。
- 当 $D^{(l)}$ $ D^{(l)} $ 较大且选择 $q (u) \propto \sum_{(u, v) \in E} \frac{1}{| N_{v} |}$ $ q(u)\propto \sum_{(u,v)\in \mathcal E} \frac{1}{|\mathcal N_v|} $ 时，IS 可以视为 NS ，因为每个节点 $v$ $ v $ 以概率 $\frac{1}{| N_{v} |}$ $ \frac{1}{|\mathcal N_v|} $ 来选择其邻居节点 $u$ $ u $ 。因此 NS 可以看作是 IS 的一种。
尽管 IS 策略的感受野大小为 $\sum_{l} D^{(l)}$ $ \sum_l D^{(l)} $ 要小于 NS 策略的感受野大小 $\prod_{l} D^{(l)}$ $ \prod_l D^{(l)} $ ，但是 IS 仍然仅在采样大小 $D^{(l)}$ $ D^{(l)} $ 达到无穷大时才可以确保模型收敛。

从实验来看，我们发现 IS 策略的效果要比 NS 更差，这是因为：在 IS 策略中我们为所有节点采样了共同的一组节点集合，对于部分节点我们采样到了它们的很多个邻居，对于另一些节点我们没有采样到任何邻居。对于后者，这些节点的邻域均值 hidden feature ${\vec{n}}_{v}^{(l)}$ $ \mathbf{\vec n}_v^{(l)} $ 为零，从而导致 hidden feature ${\vec{h}}_{v}^{(l)}$ $ \mathbf{\vec h}_v^{(l)} $ 为零。

17.1.4 控制变量

我们提出一种新的基于控制变量control variate: CV的算法，该算法基于历史 hidden feature 来降低估计量的方差。
当计算邻域均值 hidden feature ${\vec{n}}_{v}^{(l)} = \sum_{u \in N_{v}} P_{v, u} {\vec{h}}_{u}^{(l)}$ $ \mathbf{\vec n}_v^{(l)} = \sum_{u\in \mathcal N_v} P_{v,u} \mathbf{\vec h}_u^{(l)} $ 时，由于需要递归计算，因此我们无法计算所有的 ${\vec{h}}_{u}^{(l)}$ $ \mathbf{\vec h}_u^{(l)} $ 项。我们的思想是：对于每个 ${\vec{h}}_{u}^{(l)}$ $ \mathbf{\vec h}_u^{(l)} $ ，我们维护一份历史均值 ${\bar{\vec{h}}}_{u}^{(l)}$ $ \bar{\mathbf{\vec h}}_u^{(l)} $ 作为其计算代价负担得起affordable的近似值。每次计算 ${\vec{h}}_{u}^{(l)}$ $ \mathbf{\vec h}_u^{(l)} $ 时，我们都用 ${\vec{h}}_{u}^{(l)}$ $ \mathbf{\vec h}_u^{(l)} $ 去更新 ${\bar{\vec{h}}}_{u}^{(l)}$ $ \bar{\mathbf{\vec h}}_u^{(l)} $ 。当训练期间模型的权重变化比较缓慢时，我们预期 ${\bar{\vec{h}}}_{u}^{(l)}$ $ \bar{\mathbf{\vec h}}_u^{(l)} $ 和 ${\vec{h}}_{u}^{(l)}$ $ \mathbf{\vec h}_u^{(l)} $ 是近似的。

令 $Δ {\vec{h}}_{u}^{(l)} = {\vec{h}}_{u}^{(l)} - {\bar{\vec{h}}}_{u}^{(l)}$ $ \Delta \mathbf{\vec h}_u^{(l)} = \mathbf{\vec h}_u^{(l)} - \bar{\mathbf{\vec h}}_u^{(l)} $ ，则有：
${\vec{n}}_{v}^{(l)} = \sum_{u \in N_{v}} P_{v, u} {\vec{h}}_{u}^{(l)} = \sum_{u \in N_{v}} P_{v, u} Δ {\vec{h}}_{u}^{(l)} + \sum_{u \in N_{v}} P_{v, u} {\bar{\vec{h}}}_{u}^{(l)}$
定义：
${\vec{n}}_{C V, v}^{(l)} = \frac{| N_{v} |}{D^{(l)}} \sum_{u \in {\hat{N}}_{v}^{(l)}} P_{v, u} Δ {\vec{h}}_{u}^{(l)} + \sum_{u \in N_{v}} P_{v, u} {\bar{\vec{h}}}_{u}^{(l)}$
其中 ${\hat{N}}_{v}^{(l)} \subset N_{v}$ $ \hat{\mathcal N}_v^{(l)}\sub \mathcal N_v $ 为一个大小为 $D^{(l)}$ $ D^{(l)} $ 的、邻域 $N_{v}$ $ \mathcal N_v $ 的一个随机子集。

这里的核心思想是：主要的 ${\bar{\vec{h}}}_{u}^{(l)}$ $ \bar{\mathbf{\vec h}}_u^{(l)} $ 不用递归计算，可以直接从内存中获取到；次要的 $Δ {\vec{h}}_{u}^{(l)}$ $ \Delta \mathbf{\vec h}_u^{(l)} $ 需要递归计算，但是仅对它采样一小部分的邻域。同时，这进一步促进了模型权重的缓慢变化。

因为主要部分是精确值，次要部分是近似值，因此这会大幅度降低近似计算带来的影响。

则有： ${\vec{n}}_{v}^{(l)} ≃ {\vec{n}}_{C V, v}^{(l)}$ $ \mathbf{\vec n}_{ v}^{(l)} \simeq \mathbf{\vec n}_{CV,v}^{(l)} $ 。我们称 ${\vec{n}}_{C V, v}^{(l)}$ $ \mathbf{\vec n}_{CV,v}^{(l)} $ 为节点的邻域均值 hidden feature ${\vec{n}}_{v}^{(l)}$ $ \mathbf{\vec n}_v^{(l)} $ 的 CV 估计量。写作矩阵的形式为：
$\begin{matrix} Z^{(l + 1)} = ({\hat{P}}^{(l)} (H^{(l)} - {\bar{H}}^{(l)}) + P {\bar{H}}^{(l)}) W^{(l)} \\ H^{(l + 1)} = σ (Z^{(l + 1)}) \end{matrix}$
其中 ${\bar{H}}^{(l)}$ $ \bar{\mathbf H}^{(l)} $ 的各行为 ${\bar{\vec{h}}}_{u}^{(l)}$ $ \bar{\mathbf{\vec h}}_u^{(l)} $ 拼接而成。

这里我们仅对 $Δ {\vec{h}}_{u}^{(l)}$ $ \Delta{\mathbf{\vec h}}_u^{(l)} $ 的项进行蒙特卡洛近似。对所有的 ${\bar{\vec{h}}}_{u}^{(l)}$ $ \bar{\mathbf{\vec h}}_u^{(l)} $ 取平均是可以接受的，因为它们不需要进行递归地计算。

由于我们预期 ${\bar{\vec{h}}}_{u}^{(l)}$ $ \bar{\mathbf{\vec h}}_u^{(l)} $ 和 ${\vec{h}}_{u}^{(l)}$ $ \mathbf{\vec h}_u^{(l)} $ 是近似的，因此 $Δ {\vec{h}}_{u}$ $ \Delta \mathbf{\vec h}_u $ 很小。因此 ${\vec{n}}_{C V, v}^{(l)}$ $ \mathbf{\vec n}_{CV,v}^{(l)} $ 具有比 ${\vec{n}}_{N S, v}^{(l)}$ $ \mathbf{\vec n}_{NS,v}^{(l)} $ 更小的方差。具体而言，如果模型的权重保持固定，则 ${\bar{\vec{h}}}_{u}^{(l)}$ $ \bar{\mathbf{\vec h}}_u^{(l)} $ 应该最终等于 ${\vec{h}}_{u}^{(l)}$ $ \mathbf{\vec h}_u^{(l)} $ ，因此有：
${\vec{n}}_{C V, v}^{(l)} = 0 + \sum_{u \in N_{v}} P_{v, u} {\bar{\vec{h}}}_{u}^{(l)} = \sum_{u \in N_{v}} P_{v, u} {\vec{h}}_{u}^{(l)} = {\vec{n}}_{v}^{(l)}$
即估计量的偏差和方差都为零。
我们定义控制变量 control variate 为：
${\vec{δ}}_{v}^{(l)} = {\vec{n}}_{C V, v}^{(l)} - {\vec{n}}_{N S, v}^{(l)} = \sum_{u \in N_{v}} P_{v, u} {\bar{\vec{h}}}_{u}^{(l)} - \frac{| N_{v} |}{D^{(l)}} \sum_{u \in {\hat{N}}_{v}^{(l)}} P_{v, u} {\bar{\vec{h}}}_{u}^{(l)}$
我们将控制变量 ${\vec{δ}}_{v}^{(l)}$ $ \vec \delta_v^{(l)} $ 添加到邻域采样策略 NS 的 ${\vec{n}}_{N S, v}^{(l)}$ $ \mathbf{\vec n}_{NS,v}^{(l)} $ 中，从而降低估计量的方差。

现在 ${\vec{δ}}_{v}^{(l)}$ $ \vec \delta_v^{(l)} $ 仅依赖于不需要递归计算的 ${\bar{\vec{h}}}_{u}^{(l)}$ $ \bar{\mathbf{\vec h}}_u^{(l)} $ ，因此 ${\vec{δ}}_{v}^{(l)}$ $ \vec \delta_v^{(l)} $ 也不需要递归计算。
采用 CV 估计量来训练 GCN 的方法和 NS 估计量都相同。具体而言，在 GCN 的每轮迭代中都执行以下算法。

VRGCN 迭代算法：
- 随机选择一个 mini-batch 的节点 $V_{B} \subset V_{Y}$ $ \mathcal V_B\sub \mathcal V_Y $ 。
- 构建一个计算图，其中包含当前 mini-batch 每个节点的 hidden feature 计算时需要的其它节点的 hidden feature ${\vec{h}}_{v}^{(l)}$ $ \mathbf{\vec h}_v^{(l)} $ 及其历史均值 ${\bar{\vec{h}}}_{v}^{(l)}$ $ \bar{\mathbf{\vec h}}_v^{(l)} $ 。
- 根据下面的前向传播公式进行传播：
  $\begin{matrix} Z^{(l + 1)} = ({\hat{P}}^{(l)} (H^{(l)} - {\bar{H}}^{(l)}) + P {\bar{H}}^{(l)}) W^{(l)} \\ H^{(l + 1)} = σ (Z^{(l + 1)}) \end{matrix}$
  
  这里控制变量 ${\vec{δ}}_{v}^{(l)}$ $ \vec \delta_v^{(l)} $ 的矩阵形式为： $P {\bar{H}}^{(l)} - {\hat{P}}^{(l)} {\bar{H}}^{(l)}$ $ \mathbf P\bar{\mathbf H}^{(l)} - \hat{\mathbf P}^{(l)}\bar{\mathbf H}^{(l)} $ 。
- 通过反向传播计算梯度，并更新参数。
- 更新 hidden feature 历史均值 ${\bar{\vec{h}}}_{v}^{(l)}$ $ \bar{\mathbf{\vec h}}_v^{(l)} $ 。
其中，第二步的计算图是通过每层的感受野 $R^{(l)}$ $ \mathcal R^{(l)} $ 以及对应的传播矩阵 ${\hat{P}}^{(l)}$ $ \hat {\mathbf P}^{(l)} $ 来定义。感受野 $R^{(l)}$ $ \mathcal R^{(l)} $ 定义了需要第 $l$ $ l $ 层哪些节点的 hidden feature ${\vec{h}}_{v}^{(l)}$ $ \mathbf{\vec h}_v^{(l)} $ 来计算当前的 mini-batch 。

我们自顶向下构建 $R^{(l)}$ $ \mathcal R^{(l)} $ 以及 ${\hat{P}}^{(l)}$ $ \hat {\mathbf P}^{(l)} $ ：
- 令 $R^{(L)} = V_{B}$ $ \mathcal R^{(L)} = \mathcal V_B $ 。
- 对于第 $l$ $ l $ 层，对 $R^{(l + 1)}$ $ \mathcal R^{(l+1)} $ 中的每个节点我们都从它们的邻域中各自随机选择 $D^{(l)}$ $ D^{(l)} $ 个邻居节点并加入到 $R^{(l)}$ $ \mathcal R^{(l)} $ 中。
  
  注意：我们假设 ${\vec{h}}_{v}^{(l)}$ $ \mathbf{\vec h}_v^{(l)} $ 永远都必须参与 ${\vec{h}}_{v}^{(l + 1)}$ $ \mathbf{\vec h}_v^{(l+1)} $ 的计算，即 $v$ $ v $ 每次都作为其自己的邻居一定被选中。
VRGCN 的感受野如下图 (c) 所示，其中红色节点为感受野，其 hidden feature ${\vec{h}}_{v}^{(l)}$ $ \mathbf{\vec h}_v^{(l)} $ 来计算当前的 mini-batch 。蓝色节点的历史 hidden feature 均值 ${\bar{\vec{h}}}_{v}^{(l)}$ $ \bar{\mathbf{\vec h}}_v^{(l)} $ 也用于计算当前的 mini-batch 。

17.1.5 理论分析

为便于理论分析估计量的方差，这里我们假设所有的特征都是一维的。通过分别处理每个维度，我们的分析结论可以推广到多维。
假设 ${\hat{N}}_{v}^{(l)}$ $ \hat{\mathcal N}^{(l)}_v $ 通过从 $N_{v}$ $ \mathcal N_v $ 进行无放回采样 $D^{(l)}$ $ D^{(l)} $ 个样本得到，则我们有结论：
${Var}_{{\hat{N}}_{v}^{(l)}} [\frac{| N_{v} |}{D^{(l)}} \sum_{u \in {\hat{N}}_{v}^{(l)}} x_{u}] = \frac{C_{v}^{(l)}}{2 D^{(l)}} \sum_{u_{1} \in N_{v}} \sum_{u_{2} \in N_{v}} (x_{u_{1}} - x_{u_{2}})^{2}$
其中 $C_{v}^{(l)} = 1 - (D^{(l)} - 1) / (| N_{v} | - 1)$ $ C_v^{(l)} = 1-(D^{(l)}-1)/(|\mathcal N_v| - 1) $ 。证明见原始论文的附录。

根据以上结论，对于 NS 估计量我们有：
${Var}_{{\hat{N}}_{v}^{(l)}} [n_{N S, v}^{(l)}] = \frac{C_{v}^{(l)}}{2 D^{(l)}} \sum_{u_{1} \in N_{v}} \sum_{u_{2} \in N_{v}} {(P_{v, u_{1}} h_{u_{1}}^{(l)} - P_{v, u_{2}} h_{u_{2}}^{(l)})}^{2}$
即邻域内所有邻居pair 对的加权 hidden feature 之间的距离之和。如果邻域内所有节点的 $P_{v, u} h_{u}$ $ P_{v,u}h_u $ 都相等，则该方差为零。此时，任何邻域节点都包含了整个邻域的信息。

同样地，对于 CV 估计量我们有：
${Var}_{{\hat{N}}_{v}^{(l)}} [n_{C V, v}^{(l)}] = \frac{C_{v}^{(l)}}{2 D^{(l)}} \sum_{u_{1} \in N_{v}} \sum_{u_{2} \in N_{v}} {(P_{v, u_{1}} Δ h_{u_{1}}^{(l)} - P_{v, u_{2}} Δ h_{u_{2}}^{(l)})}^{2}$
相比较于 NS 估计量，这里仅需要将 $h_{u}^{(l)}$ $ h_u^{(l)} $ 替代为 $Δ h_{u}^{(l)}$ $ \Delta h_u^{(l)} $ 。由于 $Δ h_{u}^{(l)}$ $ \Delta h_u^{(l)} $ 通常都比 $h_{u}^{(l)}$ $ h_u^{(l)} $ 更小，因此 CV 估计量通常都比 NS 估计量的方差更小。

进一步地，正如我们在下文中分析到的，由于训练期间间 $Δ h_{u}^{(l)}$ $ \Delta h_u^{(l)} $ 收敛到零，因此我们不仅降低了方差，甚至消除了方差。
除了较小的方差，CV 估计量比 NS 估计量还具有更强的理论收敛性保证。这里我们提出两个定理：
- 如果模型参数固定，则在 inference 期间，CV 会在 $L$ $ L $ （ $L$ $ L $ 为卷积层的层数）个 epoch 之后产生 exact 预测。
- 无论邻域采样大小如何，模型都会朝着局部最优解收敛。
假设算法执行多个 epoch，在每个 epoch 中我们将节点集合 $V$ $ \mathcal V $ 划分为 $I$ $ I $ 个 mini-batch： ${V_{1}, \dots, V_{I}}$ $ \{\mathcal V_1,\cdots,\mathcal V_I\} $ 。在第 $i$ $ i $ 个迭代步，我们对 mini-batch $V_{i}$ $ \mathcal V_i $ 中的节点进行前向传播和反向传播，从而更新模型参数以及节点的历史 hidden feature 均值。

注意：在每个 epoch 中我们扫描所有节点，而不仅仅是标记的训练节点，从而确保每个 epoch 中对每个节点的历史 hidden feature 均值至少进行了一次更新。

记第 $i$ $ i $ 次迭代中模型的参数为 $W_{i}$ $ \mathbf W_i $ 。在训练期间 $W_{i}$ $ \mathbf W_i $ 通过 SGD 随时间更新，在测试期间 $W = W_{T}$ $ \mathbf W = \mathbf W_T $ 被固化下来，其中 $T$ $ T $ 为迭代的总次数。

记第 $i$ $ i $ 次迭代的 exact hidden feature 为 $H_{i}^{(l)}$ $ \mathbf H ^{(l)}_i $ ，以及对应的 $Z$ $ \mathbf Z $ 为 $Z_{i}^{(l)}$ $ \mathbf Z_i ^{(l)} $ ；使用 CV 估计量的 hidden feature 为 $H_{C V, i}^{(l)}$ $ \mathbf H_{CV,i}^{(l)} $ ，以及对应的 $Z$ $ \mathbf Z $ 为 $Z_{C V, i}^{(l)}$ $ \mathbf Z_{CV,i}^{(l)} $ 。

在第 $i$ $ i $ 轮迭代，网络计算 mini-batch $V_{i}$ $ \mathcal V_i $ 的损失函数和梯度，其中：
- 对于 exact 算法，其损失函数和梯度分别为：
  $\begin{matrix} J (W_{i}) = \frac{1}{| V_{i} |} \sum_{v \in V_{i}} f (y_{v}, {\vec{z}}_{i, v}^{(L)}) \\ G_{i} (W_{i}) = \nabla J_{W} ≃ \frac{1}{| V_{i} |} \sum_{v \in V_{i}} \nabla_{W_{i}} f (y_{v}, {\vec{z}}_{i, v}^{(L)}) \end{matrix}$
  对于 exact 算法，如果 $W_{i}$ $ \mathbf W_i $ 是 constant 序列，则可以忽略下标 $i$ $ i $ 。
- 对于 CV 算法，其损失函数和梯度分别为：
  $\begin{matrix} J_{C V} (W_{i}) = \frac{1}{| V_{i} |} \sum_{v \in V_{i}} f (y_{v}, {\vec{z}}_{i, C V, v}^{(L)}) \\ G_{i, C V} (W_{i}) = \nabla J_{C V, W} ≃ \frac{1}{| V_{i} |} \sum_{v \in V_{i}} \nabla_{W_{i}} f (y_{v}, {\vec{z}}_{i, C V, v}^{(L)}) \end{matrix}$
  梯度 $G_{i, C V} (W_{i})$ $ \mathbf G_{i,CV} (\mathbf W_i) $ 有两个随机性来源：
  - 选择 mini-batch $V_{i} \subset V_{Y}$ $ \mathcal V_i\sub \mathcal V_Y $ 引入的随机性。
  - 选择大小为 $D^{(l)}$ $ D^{(l)} $ 的邻域集合 ${\hat{N}}_{v}^{(l)} \subset N_{v}$ $ \hat{\mathcal N}_v^{(l)}\sub \mathcal N_v $ 引入的随机性（由采样后的邻接矩阵 $\hat{P}$ $ \hat{\mathbf P} $ 来刻画）。
  因此我们考虑 $G_{i, C V} (W_{i})$ $ \mathbf G_{i,CV} (\mathbf W_i) $ 对 $V_{i}$ $ \mathcal V_i $ 的期望、或者对 $\hat{P}$ $ \hat{\mathbf P} $ 的期望、或者对二者的共同期望。
以下定理解释了 CV 的近似预测和 exact 预测之间的关系：

对于一个 constant sequence $W_{i} = W$ $ \mathbf W_i = \mathbf W $ ，以及任意 $i > L \times I$ $ i\gt L\times I $ （即 $L$ $ L $ 个 epoch 之后），通过 CV 估计量计算的 hidden feature 和 exact 计算的相等。即：
$\begin{matrix} H_{i, C V}^{(l)} = H_{i}^{(l)}, 1 \leq l \leq L \\ Z_{i, C V}^{(l)} = Z_{i}^{(l)}, 1 \leq l \leq L \end{matrix}$
其证明见原始论文附录。

该定理表明：在 inference 期间，我们可以使用 CV 估计量进行前向传播 $L$ $ L $ 个 epoch （通常 $L$ $ L $ 很小，比如两层的 GCN 网络中 $L = 2$ $ L=2 $ ），然后得到 exact 预测。这优于 NS 估计量，因为除非邻域大小无穷大，否则 NS 估计量无法恢复 exact 预测。

和直接进行 exact 预测的 batch 算法相比，CV 估计量可扩展性更强，因为它不需要将整个图加载到内存中。
以下定理表明，无论邻域采样大小 $D^{(l)}$ $ D^{(l)} $ 如何，采用近似梯度 $G_{i, C V} (W_{i})$ $ \mathbf G_{i,CV} (\mathbf W_i) $ 的 SGD 训练仍然收敛于局部最优。因此我们可以选择任意小的 $D^{(l)}$ $ D^{(l)} $ 而不必担心收敛性。

定理：假设：
- 激活函数 $σ (\cdot)$ $ \sigma(\cdot) $ 为 $ρ - Lipschitz$ $ \rho-\text{Lipschitz} $ 。
- 损失函数的梯度 $\nabla_{\vec{z}} f (y, \vec{z})$ $ \nabla_{\mathbf{\vec z}}f(y,\mathbf{\vec z}) $ 是 $ρ - Lipschitz$ $ \rho-\text{Lipschitz} $ 且有界的。
- 对于任意的采样 $\hat{P}$ $ \hat{\mathbf P} $ 、任意的节点子集 $\tilde{V}$ $ \tilde{\mathcal V} $ 、任意的权重矩阵，都有 $| | G (W) | |_{\infty}, | | G_{\tilde{V}, C V} (W) | |_{\infty}, | | \nabla_{W} J (W) | |_{\infty}$ $ ||\mathbf G (\mathbf W) ||_\infty, || \mathbf G_{\tilde{\mathcal V},CV} (\mathbf W )||_\infty, ||\nabla_{\mathbf W} \mathcal J(\mathbf W)||_\infty $ 都是有界的，且上界都是 $G$ $ G $ （其中 $G > 0$ $ G\gt 0 $ ）。
- 损失函数 $J (W)$ $ \mathcal J(\mathbf W) $ 是 $ρ - smooth$ $ \rho-\text{smooth} $ 的，即：对于任意 $W_{1}, W_{2}$ $ \mathbf W_1, \mathbf W_2 $ ，有：
  $| J (W_{2}) - J (W_{1}) - < \nabla J (W_{1}), W_{2} - W_{1} > | \leq \frac{ρ}{2} | | W_{2} - W_{1} | |_{F}^{2}$
  其中 $< A, B >= tr (A^{⊤} B)$ $ <\mathbf A,\mathbf B> = \text{tr}\left(\mathbf A^\top \mathbf B\right) $ 为矩阵 $A$ $ \mathbf A $ 和 $B$ $ \mathbf B $ 的内积。
则存在 $K > 0$ $ K\gt 0 $ ，使得 $\forall N > L \times I$ $ \forall N\gt L\times I $ ，当我们执行 $1 \leq R \leq N$ $ 1\le R\le N $ 次 SGD 迭代时，有：
$E_{R} | | \nabla J (W_{R}) | |_{F}^{2} \leq 2 \frac{J (W_{1}) - J (W^{*}) + K + ρ K}{\sqrt{N}}$
其中：
- $R$ $ R $ 为 [1, N] 之间均匀随机分布的变量。
- 每次迭代都使用 CV 的近似梯度 $G_{i, C V} (W_{i})$ $ \mathbf G_{i,CV} (\mathbf W_i) $ ：
  $W_{i + 1} = W_{i} - γ \times G_{i, C V} (W_{i})$
  其中步长 $γ = min {\frac{1}{ρ}, \frac{1}{\sqrt{N}}}$ $ \gamma = \min\{\frac{1}{\rho}, \frac{1}{\sqrt N}\} $ 。
从定理中我们看到： $lim_{N \to \infty} E_{R} | | \nabla J (W_{R}) | |_{F}^{2} = 0$ $ \lim_{N\rightarrow \infty} \mathbb E_R||\nabla \mathcal J(\mathbf W_R)||_F^2 = 0 $ 。因此当迭代次数 $N$ $ N $ 趋向于无穷时，我们的训练算法收敛到局部最优解（梯度为零）。完整的证明见原始论文附录。

简而言之，我们证明了近似梯度 $G_{i, C V} (W_{i})$ $ \mathbf G_{i,CV} (\mathbf W_i) $ 是 $G_{i} (W_{i})$ $ \mathbf G_{i} (\mathbf W_i) $ 的无偏估计，并且随着 $i \to \infty$ $ i\rightarrow \infty $ 这种渐进无偏的 SGD 收敛到局部最优解。

17.1.6 dropout

这里我们引入第三种随机性来源：对输入特征的随机 dropout 。

令 $D_{p} (X) = M \circ X$ $ \mathcal D_p(\mathbf X) = \mathbf M \circ \mathbf X $ 为 dropout 算子，其中 $M_{i, j} \sim B e r n (p)$ $ M_{i,j}\sim Bern(p) $ 为独立同分布 iid 的伯努利随机变量， $\circ$ $ \circ $ 是逐元素的乘积。

记 $E_{M} [\cdot]$ $ \mathbb E_\mathbf M[\cdot] $ 为针对 dropout 的期望。
引入 dropout 之后，即使在 GCN 中采用 exact 算法，hidden feature ${\vec{h}}_{v}^{(l)}$ $ \mathbf{\vec h}_v^{(l)} $ 也是随机变量，其随机性来源于 dropout 。

此时节点的邻域均值 hidden feature ${\vec{n}}_{v}^{(l)}$ $ \mathbf{\vec n}_v^{(l)} $ 也是一个随机变量，我们希望设计它的一个计算代价较低的估计量，从而使得二者具有相同的分布。但是这种估计量非常难以设计，因此我们设计了一个估计量 ${\vec{n}}_{C V D, v}^{(l)}$ $ \mathbf{\vec n}_{CVD,v}^{(l)} $ ，使得它和 ${\vec{n}}_{v}^{(l)}$ $ \mathbf{\vec n}_v^{(l)} $ 具有相同的均值和方差。即：
$\begin{matrix} E_{{\hat{N}}_{v}^{(l)}} E_{M} [{\vec{n}}_{C V D, v}^{(l)}] = E_{M} [{\vec{n}}_{v}^{(l)}] \\ {Var}_{{\hat{N}}_{v}^{(l)}} {Var}_{M} [{\vec{n}}_{C V D, v}^{(l)}] = {Var}_{M} [{\vec{n}}_{v}^{(l)}] \end{matrix}$
在 dropout 场景下， $Δ {\vec{h}}_{u}^{(l)} = {\vec{h}}_{u}^{(l)} - {\bar{\vec{h}}}_{u}^{(l)}$ $ \Delta \mathbf{\vec h}_u^{(l)} = \mathbf{\vec h}_u^{(l)} - \bar{\mathbf{\vec h}}_u^{(l)} $ 不再很小，甚至是当 ${\bar{\vec{h}}}_{u}^{(l)}$ $ \bar{\mathbf{\vec h}}_u^{(l)} $ 和 ${\vec{h}}_{u}^{(l)}$ $ \mathbf{\vec h} _u^{(l)} $ 具有相同分布的时候。为此，我们设计了另一种随机逼近算法，称作 dropout 控制变量 control variate for dropout: CVD 。

我们的方法基于权重缩放 weight scaling 技术来近似计算均值 ${\vec{μ}}_{v}^{(l)} = E_{M} [{\vec{h}}_{v}^{(l)}]$ $ \vec\mu_v^{(l)} = \mathbb E_\mathbf M\left[\mathbf{\vec h}_v^{(l)}\right] $ 。即在 dropout 模型中，我们可以运行没有 dropout 的模型的copy，从而获得均值 ${\vec{μ}}_{v}^{(l)}$ $ \vec\mu_v^{(l)} $ ，如下图 (d) 所示。
我们通过 ${\vec{μ}}_{u}^{(l)}$ $ \vec\mu_u^{(l)} $ 及其历史均值 ${\bar{\vec{μ}}}_{u}^{(l)}$ $ \bar{\vec\mu}_u^{(l)} $ 来设计 CVD 估计量。

我们将 ${\vec{n}}_{v}^{(l)}$ $ \mathbf{\vec n}_v^{(l)} $ 重写为：
${\vec{n}}_{v}^{(l)} = \sum_{u \in N_{v}} P_{v, u} {\vec{h}}_{u}^{(l)} = \sum_{u \in N_{v}} P_{v, u} ({\overset{˚}{\vec{h}}}_{u}^{(l)} + Δ {\vec{μ}}_{u}^{(l)} + {\bar{\vec{μ}}}_{u}^{(l)})$
其中：
- $Δ {\vec{μ}}_{u}^{(l)} = {\vec{μ}}_{u}^{(l)} - {\bar{\vec{μ}}}_{u}^{(l)}$ $ \Delta \vec{\mu}_u^{(l)} = \vec\mu_u^{(l)} - \bar{\vec\mu}_u^{(l)} $ 为 ${\vec{μ}}_{u}^{(l)}$ $ \vec\mu_u^{(l)} $ 及其历史均值 ${\bar{\vec{μ}}}_{u}^{(l)}$ $ \bar{\vec\mu}_u^{(l)} $ 之间的差距。因此，可以将 ${\vec{μ}}_{u}^{(l)}$ $ \vec\mu_u^{(l)} $ 视为 CV 估计量中的 ${\vec{h}}_{u}^{(l)}$ $ \mathbf{\vec h}_u^{(l)} $ 。
- ${\overset{˚}{\vec{h}}}_{u}^{(l)} = {\vec{h}}_{u}^{(l)} - {\vec{μ}}_{u}^{(l)}$ $ \mathbf{\mathring{\vec h}}_u^{(l)} = \mathbf{\vec h}_u^{(l)} - \vec\mu_u^{(l)} $ 为 ${\vec{h}}_{u}^{(l)}$ $ \mathbf{\vec h}_u^{(l)} $ （带 dropout ）和 ${\vec{μ}}_{u}^{(l)}$ $ \vec\mu_u^{(l)} $ （不带 dropout ）之间的差距。
因此定义：
${\vec{n}}_{C V D, v}^{(l)} = \sqrt{\frac{| N_{v} |}{D^{(l)}}} \sum_{u \in {\hat{N}}_{v}^{(l)}} P_{v, u} {\overset{˚}{\vec{h}}}_{u}^{(l)} + \frac{| N_{v} |}{D^{(l)}} \sum_{u \in {\hat{N}}_{v}^{(l)}} P_{v, u} Δ {\vec{μ}}_{u}^{(l)} + \sum_{u \in N_{v}} P_{v, u} {\bar{\vec{μ}}}_{u}^{(l)}$
则有： ${\vec{n}}_{v}^{(l)} ≃ {\vec{n}}_{C V D, v}^{(l)}$ $ \mathbf{\vec n}_v^{(l)}\simeq \mathbf{\vec n}_{CVD,v}^{(l)} $ 。

第一项考虑 dropout current value 和 no-dropout current value 之间的 gap，使用 $\sqrt{\cdot}$ $ \sqrt{\cdot} $ 是为了计算方差的方便。第二项考虑 no-dropout current value 和 no-dropout avg value 之间的 gap。第三项就是 no-dropout avg value 本身。

考虑第一项对于 dropout 具有零均值，即 $E_{M} [{\overset{˚}{\vec{h}}}_{u}^{(l)}] = 0$ $ \mathbb E_\mathbf M \left[\mathbf{\mathring{\vec h}}_u^{(l)}\right] = 0 $ ，因此有：
$E_{{\hat{N}}_{v}^{(l)}} E_{M} [{\vec{n}}_{C V D, v}^{(l)}] = 0 + E_{{\hat{N}}_{v}^{(l)}} E_{M} [{\vec{n}}_{C V, v}^{(l)}] = E_{M} [{\vec{n}}_{v}^{(l)}]$
第一个等式成立是因为当移除 dropout 时， CVD 估计量就退化为 CV 估计量。

因此，CVD 估计量是无偏的。下面我们即将看到，如果 ${\vec{h}}_{v}^{(l)}$ $ \mathbf{\vec h}_v^{(l)} $ 之间不相关，则 CVD 估计量具有良好的方差。
假设节点的hidden feature 之间不相关，即 $\forall v_{1} \neq v_{2}, {Cov}_{M} [{\vec{h}}_{v_{1}}^{(l)}, {\vec{h}}_{v_{2}}^{(l)}] = 0$ $ \forall v_1\ne v_2, \text{Cov}_\mathbf M\left[ \mathbf{\vec h}_{v_1}^{(l)}, \mathbf{\vec h}_{v_2}^{(l)}\right] = 0 $ ，则我们得到两个结论：
- 假设 ${\hat{N}}_{v}^{(l)}$ $ \hat{\mathcal N}^{(l)}_v $ 通过从 $N_{v}$ $ \mathcal N_v $ 进行无放回采样 $D^{(l)}$ $ D^{(l)} $ 个样本得到， $x_{1}, \dots, x_{| V |}$ $ x_1,\cdots,x_{|\mathcal V|} $ 为一维随机变量，且满足：
  $\begin{matrix} \forall v, E [x_{v}] = 0 \\ \forall v_{1} \neq v_{2}, Cov [x_{v_{1}}, x_{v_{2}}] = 0 \end{matrix}$
  则有：
  ${Var}_{{\hat{N}}_{v}^{(l)}} {Var}_{X} [\frac{| N_{v} |}{D^{(l)}} \sum_{u \in {\hat{N}}_{v}^{(l)}} x_{u}] = \frac{| N_{v} |}{D^{(l)}} \sum_{u \in N_{v}^{(l)}} Var [x_{u}]$
- 令 $X$ $ X $ 和 $Y$ $ Y $ 为两个随机变量，并且 $f (X, Y)$ $ f(X,Y) $ 和 $g (Y)$ $ g(Y) $ 为两个函数。如果 $E_{X} [f (X, Y)] = 0$ $ \mathbb E_{X}[f(X,Y)] = 0 $ ，则有：
  ${Var}_{X, Y} [f (X, Y) + g (Y)] = {Var}_{X, Y} f (X, Y) + {Var}_{Y} g (Y)$
这些结论的证明参考原始论文的附录。

通过上述结论，我们有：
$\begin{matrix} {Var}_{{\hat{N}}_{v}^{(l)}} {Var}_{M} [{\vec{n}}_{C V D, v}^{(l)}] = {Var}_{{\hat{N}}_{v}^{(l)}} {Var}_{M} [\sqrt{\frac{| N_{v} |}{D^{(l)}}} \sum_{u \in {\hat{N}}_{v}^{(l)}} P_{v, u} {\overset{˚}{\vec{h}}}_{u}^{(l)}] \\ + {Var}_{{\hat{N}}_{v}^{(l)}} [\frac{| N_{v} |}{D^{(l)}} \sum_{u \in {\hat{N}}_{v}^{(l)}} P_{v, u} Δ {\vec{μ}}_{u}^{(l)} + \sum_{u \in N_{v}} P_{v, u} {\bar{\vec{μ}}}_{u}^{(l)}] \end{matrix}$
我们将第一项视为从 dropout 中引入的方差 variance from dropout: VD，第二项视为从邻域采样中引入的方差 variance from neighbor sampling: VNS。理想情况下，VD 应该等于 ${Var}_{M} [{\vec{n}}_{v}^{(l)}]$ $ \text{Var}_{\mathbf M}\left[\mathbf{\vec n}_v^{(l)}\right] $ 、VNS 应该等于零。

和前述相同的分析，我们可以通过将 ${\vec{h}}_{v}^{(l)}$ $ \mathbf{\vec h}_v^{(l)} $ 替换为 ${\vec{μ}}_{v}^{(l)}$ $ \vec\mu_v^{(l)} $ 来分析 VNS 。令：
$\begin{matrix} {\vec{s}}_{u}^{(l)} = {Var}_{M} [{\vec{h}}_{v}^{(l)}] = {Var}_{M} [{\overset{˚}{\vec{h}}}_{u}^{(l)}] \\ {\vec{ξ}}_{v}^{(l)} = {Var}_{M} [{\vec{n}}_{v}^{(l)}] = \sum_{u \in N_{v}} P_{v, u}^{2} {\vec{s}}_{u}^{(l)} \end{matrix}$
根据这里的第一个结论，CVD 的 VD 部分为： $\sum_{u \in N_{v}} P_{v, u}^{2} {\vec{s}}_{u}^{(l)} = {\vec{ξ}}_{v}^{(l)}$ $ \sum_{u\in \mathcal N_v} P_{v,u}^2 \mathbf{\vec s}_u^{(l)} = {\vec \xi}_v^{(l)} $ ，刚好就是 exact 估计量的 VD 部分。
我们总结出所有这些估计量及其方差，推导过程参考原始论文。
- exact ： VNS 部分为零， VD 部分为 ${\vec{ξ}}_{v}^{(l)}$ $ {\vec \xi}_v^{(l)} $ 。
- NS 估计量：VNS 部分为 $\frac{C_{v}^{(l)}}{2 D^{(l)}} \sum_{u_{1} \in N_{v}} \sum_{u_{2} \in N_{v}} {(P_{v, u_{1}} {\vec{μ}}_{v_{1}}^{(l)} - P_{v, u_{2}} {\vec{μ}}_{v_{2}}^{(l)})}^{2}$ $ \frac {C_v^{(l)}}{2D^{(l)}}\sum_{u_1\in \mathcal N_v}\sum_{u_2\in \mathcal N_v}\left(P_{v,u_1}\vec\mu_{v_1}^{(l)} - P_{v,u_2}\vec\mu_{v_2}^{(l)}\right)^2 $ ， VD 部分为 $\frac{| N_{v} |}{D^{(l)}} {\vec{ξ}}_{v}^{(l)}$ $ \frac{|\mathcal N_v|}{D^{(l)}} {\vec \xi}_v^{(l)} $ 。
- CV 估计量：VNS 部分 $\frac{C_{v}^{(l)}}{2 D^{(l)}} \sum_{u_{1} \in N_{v}} \sum_{u_{2} \in N_{v}} {(P_{v, u_{1}} Δ {\vec{μ}}_{v_{1}}^{(l)} - P_{v, u_{2}} Δ {\vec{μ}}_{v_{2}}^{(l)})}^{2}$ $ \frac {C_v^{(l)}}{2D^{(l)}}\sum_{u_1\in \mathcal N_v}\sum_{u_2\in \mathcal N_v}\left(P_{v,u_1}\Delta\vec\mu_{v_1}^{(l)} - P_{v,u_2}\Delta\vec\mu_{v_2}^{(l)}\right)^2 $ ，VD 部分 $(3 + \frac{| N_{v} |}{D^{(l)}}) {\vec{ξ}}_{v}^{(l)}$ $ \left(3+\frac{|\mathcal N_v|}{D^{(l)}} \right) {\vec \xi}_v^{(l)} $ 。
- CVD 估计量：VNS 部分 $\frac{C_{v}^{(l)}}{2 D^{(l)}} \sum_{u_{1} \in N_{v}} \sum_{u_{2} \in N_{v}} {(P_{v, u_{1}} Δ {\vec{μ}}_{v_{1}}^{(l)} - P_{v, u_{2}} Δ {\vec{μ}}_{v_{2}}^{(l)})}^{2}$ $ \frac {C_v^{(l)}}{2D^{(l)}}\sum_{u_1\in \mathcal N_v}\sum_{u_2\in \mathcal N_v}\left(P_{v,u_1}\Delta\vec\mu_{v_1}^{(l)} - P_{v,u_2}\Delta\vec\mu_{v_2}^{(l)}\right)^2 $ ， VD 部分为 ${\vec{ξ}}_{v}^{(l)}$ $ {\vec \xi}_v^{(l)} $ 。
CV/CVD 的 VNS 取决于 $Δ {\vec{μ}}_{v}$ $ \Delta\vec\mu_{v} $ ，随着训练的进行 $Δ {\vec{μ}}_{v}$ $ \Delta\vec\mu_{v} $ 收敛到零；NS 的 VNS 取决于非零的 ${\vec{μ}}_{v}$ $ \vec\mu_{v} $ 。

17.1.7 预处理

有两种可能的dropout 方式：
$\begin{matrix} Z^{(l + 1)} = P D_{p} (H^{(l)}) W^{(l)} \\ Z^{(l + 1)} = D_{p} (P H^{(l)}) W^{(l)} \end{matrix}$
区别在于：第一种方式是在邻域聚合之前应用 dropout、第二种方式在邻域聚合之后应用 dropout 。《Semi-supervised classification with graph convolutional networks》 采用前者，而我们采用后者。

实验效果上，我们发现这两种方式的效果都相差无几，因此不同的方式不影响模型的效果。采用第二种方式的优势是提升训练速度：我们可以对输入进行预处理，并定义 $U^{(0)} = P H^{(0)} = P X$ $ \mathbf U^{(0)} = \mathbf P\mathbf H^{(0)} = \mathbf P\mathbf X $ ，然后将 $U^{(0)}$ $ \mathbf U^{(0)} $ 作为新的输入。采用这种方式之后，图卷积层的实际数量减少了一层。现在第一层仅是一个全连接层，而不是图卷积层。

由于大多数GCN 仅有两层卷积层，因此这种方式可以显著减少感受野大小，并加快训练速度。我们称该优化为预处理策略 preprocessing strategy 。

17.2 实验

我们在六个数据集上通过实验验证了 VRGCN 算法的方差和收敛性，其中包括来自GCN 的 Citeseer, Cora, PubMed, NeLL 四个数据集以及来自 GraphSAGE 的 PPI, Reddit 两个数据集。

对于这些数据集的统计见下表所示。最后两列给出了节点的 1-hop 邻域平均大小、2-hop 邻域平均大小。由于是无向图，因此每条边被计算两次，但是 self-loop 仅被计算一次。
- 对于每个数据集，所有模型在该数据集上采用相同的训练集/验证集/测试集拆分（而不是每个模型单独的一个拆分）。
- 对于 PPI 数据集（多标签分类数据集）我们报告测试集的 Micro-F1 指标，对于其它多分类数据集我们报告准确率 accuracy 。
- 对于Citeseer, Cora, PubMed, NELL 数据集，baseline 模型为 GCN ；对于 PPI, Reddit 数据集，baseline 模型为 GraphSAGE 。
- 对于收敛性实验，我们在 Citeseer, Cora, PubMed, NELL 数据集上重复执行 10 次，在 Reddit, PPI 数据集上重复执行 5 次。
- 所有实验都在 Titan X GPU 上完成。
首先我们评估预处理PreProcessing: PP的影响。我们比较了三种配置：
- M0：dropout 在前、计算邻域均值在后，且计算邻域的 exact 均值（未对邻域进行任何采样）
- M1：计算邻域均值在前、dropout 在后，且计算邻域的 exact 均值（未对邻域进行任何采样）
- M1 + PP：计算邻域均值在前、dropout 在后，且使用较大的邻域大小 $D^{(l)} = 20$ $ D^{(l)} = 20 $ 来对邻域采样从而计算邻域的近似均值，并且预处理 $P H^{(0)}$ $ \mathbf P\mathbf H^{(0)} $ 使得第一层邻域均值是 exact的。
实验结果如下所示。我们固定了训练的 epoch，然后给出不同配置的 GCN 在不同数据集上的测试accuracy 。我们的实现不支持 NELL 上的 M0 配置，因此未报告其结果。

可以看到：三种配置都具有相近的性能，即更换 dropout 的位置不会影响模型的预处性能。因此后续的收敛性实验中，我们以最快的 M1 + PP 配置作为 exact baseline 。
然后我们评估 VRGCN 的收敛性。我们将 M1 + PP 配置作为 exact baseline，然后对比 $D^{(l)} = 2$ $ D^{(l)} = 2 $ 的情况。我们无法配置 $D^{(l)} = 1$ $ D^{(l)} = 1 $ ，因为感受野中至少包含节点本身，如果 $D^{(l)} = 1$ $ D^{(l)}= 1 $ 则邻域聚合时不考虑任何其它节点，这退化为 MLP 。我们对四种近似策略进行比较，其中 $D^{(l)} = 2$ $ D^{(l)} = 2 $ ：
- NS ：没有使用预处理的 NS 估计量（邻域采样）。
- NS + PP：采用了预处理的 NS 估计量。
- IS + PP：采用了预处理的 IS 估计量（重要性采样）。
- CV + PP：采用了预处理的 CV 估计量。
- CVD + PP：采用了预处理的 CVD 估计量。
当 $D^{(l)} = 2$ $ D^{(l)} =2 $ 时这四种算法在每个 epoch 都具有很低的、相近的时间复杂度，相比之下 baseline M1 + PP 的 $D^{(l)} = 20$ $ D^{(l)}= 20 $ 。我们比较了这些方法和 baseline 相比，它们的收敛速度。
- 首先我们不考虑 dropout （dropout rate = 0 ），然后绘制不同方法每个 epoch 的损失函数值，如下图所示。
  
  在前 4 个数据集中，CV + PP 的损失曲线和 exact 损失曲线相重叠；部分数据集上未给出 NS 损失曲线和 IS + PP 损失曲线，因为损失太大；我们并未绘制 CVD + PP ，因为当 dropout rate = 0 时，它等价于 CV + PP 。
  
  结论：
  - CV + PP 总是可以达到和 M1 + PP 相同的训练损失。
  - NS, NS + PP, IS + PP 由于它们的梯度是有偏的，因此其训练损失更高。
  这些结果和前述定理相符。定理指数：CV 估计量的训练能够收敛到 exact 的局部最优，和 $D^{(l)}$ $ D^{(l)} $ 无关。
- 然后我们考虑使用 dropout，然后比较每个 epoch 使用不同方式训练的模型验证accuracy 。其中不管训练算法采取何种方式，inference 都采用 exact 算法来预测。结果如下图所示。注意：NS 在Reddit 数据集上收敛到 0.94、在 PPI 数据集上收敛到 0.6，由于太低所以未在图中给出。
  
  结论：
  - 当存在 dropout 时，CVD + PP 是唯一可以在所有数据集上达到和 exact 算法相近的验证准确率的算法。
  - 当存在 dropout 时，CVD + PP 的收敛速度（以 epoch 数量衡量）和 M1 + PP 相当。这意味着尽管 $D^{(l)}$ $ D^{(l)} $ 小了 10倍，但是 CVD + PP 的收敛速度几乎没有损失。
    
    这已经是我们期待的最佳结果：具有和 MLP 可比的计算复杂度，但是具有和 GCN 相近的模型质量。
  - 在 PubMed 数据集上，CVD + PP 性能比 M1 + PP 好得多，我们怀疑它找到了更加的局部最优值。
  - 对 PPI 以外的所有其它数据集，简单的 CV + PP 的准确率就可以和 M1 + PP 相媲美。
  - 在 Reddit,PPI 数据集上，IS + PP 性能比 NS + PP 更差。这可能是部分节点没有采样到任何邻居，正如我们前文所述。
  - 我们对 IS + PP 的准确率结果和 FastGCN 的报告结果相符，而他们的 GraphSAGE baseline 并未实现预处理技术。
下面给出了在最大的 Reddit 数据集上达到给定的 96% 验证准确率所需要的平均训练 epoch 和训练时间。可以看到：CVD + PP 比 exact 快 7 倍左右。这是因为 CVD + PP 的感受野大小显著降低。

另外，NS, IS + PP 无法收敛到给定的准确率（即无法收敛到 96% 验证准确率）。
我们使用相同的、由 M1 + PP 训练的模型，然后采用不同的算法进行预测，并给出预测质量。

如前所述，CV 可以达到和 exact 算法相同的测试准确率，而 NS, NS + PP 的性能要差得多。
最后，我们比较了训练期间第一层权重每一维梯度的平均 bias 和方差（对权重自身进行了归一化）。

结论：
- 对于没有 dropout 的模型，CV + PP 的梯度几乎所无偏的。
- 对于存在 dropout 的模型，CV + PP he CVD + PP 梯度的bias 和方差通常小于 NS 和 NS + PP 。