十九、LDS-GNN [2019]

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

关系学习relational learning 同时利用了样本自身的属性以及样本之间的关系。例如：患者诊断不仅需要考虑患者本身的信息，还需要考虑患者亲属的信息。因此，关系学习不会假设数据点之间的独立性，而是显式建模它们之间的依赖关系。图是表示关系信息relational information的自然的方式，并且已经有很多利用图结构的方法，如图神经网络GNN 。
虽然图结构在某些领域可用（如社交网络），但是在另一些领域中我们必须构造图结构。
- 一种常用的人工构造图结构的方法是：基于样本之间的某种相似性来构建 kNN 图。这种方法被很多算法采用（如 LLE,IsoMap），但是它存在不足：模型效果取决于 $k$ $ k $ 值的选择，也取决于相似性度量的选择。
  另外在这种方法中，图的构建和 GNN 参数的学习是相互独立的，图的构建需要启发式方法并反复实验。
- 另一种方法是简单地使用核矩阵 kernel matrix 来隐式建模样本之间的相似性，但是得到了稠密的相似性矩阵（对应于全连接图）维代价。
论文 《Learning Discrete Structures for Graph Neural Networks》 提出了不同的方法同时学习了图的构建和 GNN 参数，即 LDS-GNN 。简单而言，论文提出了学习图生成概率模型，其中节点来自于训练集和测试集，边被建模为随机变量，其参数视为 bilevel 学习框架中的超参数。论文在最小化内层目标函数（GCN 训练误差）的同时对图结构进行迭代式采样，并通过最小化外层目标函数（GCN 验证误差）来优化边的分布参数。
两层优化：内层在训练集上优化训练损失，外层在验证集上优化验证损失。该方法仅用于小型图，计算量很大并且不能保证收敛性。
据作者所知，这是针对半监督分类问题中，同时学习图结构和 GNN 参数的第一种方法。此外，论文使用基于梯度的超参数优化来处理不连续的超参数（边是否存在）。通过一系列实验，结果证明了论文的方法比现有方法的优势，同时验证了图生成模型具有有意义的边概率（即：边是否存在的概率）。
相关工作：
- 半监督学习 Semi-supervised Learning：基于图的半监督学习的早期工作使用图拉普拉斯正则化graph Laplacian regularization ，包括标签传播 label propagation: LP、流形正则化 manifold regularization: ManiReg、半监督嵌入 semi-supervised embedding: SemiEmb。这些方法假设给定一个图，其中边代表节点之间的某种相似性。
  - 后来，《Revisiting semi-supervised learning with graph embeddings》 提出了一种方法，该方法不使用图进行正则化，而是通过联合classification 和 graph context prediction 这两个任务来学习 embedding 。
  - 《Semi-supervised classification with graph convolutional networks》 提出了第一个用于半监督学习的 GCN。
  现在有许多 GCN 变体，所有这些变体都假设给定了图结构。与所有现有的 graph-based 半监督学习相反，LDS 即使在图不完整或图缺失的情况下也能工作。
- 图合成和生成 graph synthesis and generation：LDS 学习图的概率生成模型。
  - 最早的图概率生成模型是 《On the evolution of random graphs》 提出的随机图模型，其中边概率被建模为独立同分布的伯努利随机变量。
  - 人们已经提出了几种网络模型来建模特定的图属性，如 degree 分布（《Graphs overtime: densification laws, shrinking diameters and possible explanations》）、网络直径（《Collective dynamics of small-world networks》）。
  - 《Kronecker graphs: An approach to modeling networks》 提出了一种基于 Kronecker 乘积的生成模型，该模型将真实图作为输入并生成具有相似属性的图。
  - 最近，人们已经提出了基于深度学习的图生成方法。
  然而，这些方法的目标是学习一个复杂的生成模型 generative model，该模型反映了训练图的属性。另一方面，LDS 学习图生成模型，并将其作为分类问题的一种良好的手段，并且LDS 的输入不是图的集合。
  最近的工作提出了一种无监督模型，该模型学习推断实体之间的交互，同时学习物理系统（如弹簧系统）的动力学（《Neural relational inference for interacting systems》)。与 LDS 不同，该方法特定于动态交互系统，是无监督的，并且使用变分自编码器。
  最后，我们注意到 《Learning graphical state transitions》 提出了一个完全可微的神经模型，能够在 input/representation/output level 处理和生成图结构。然而，训练模型需要根据 ground truth graph 进行监督。
- 链接预测：链接预测是一个几十年前的问题。有几篇综述论文涵盖了从社交网络到知识图谱中的链接预测的大量工作。虽然大多数方法都是基于 node pair 之间的某种相似性度量，但是也有许多基于神经网络的方法（《Link prediction based on graph neural networks》）。
  我们在本文中研究的问题与链接预测有关，因为我们也想学习learn或扩张extend一个图。然而，现有的链接预测方法不会同时学习一个 GNN node classifier。统计关系学习 statistical relational learning: SRL 模型通常通过二元或一元谓词的存在来执行链接预测和节点分类。然而，SRL 模型本质上是难以处理的，并且网络结构和模型参数学习步骤是独立的。
- 离散随机变量的梯度估计：由于两个 bilevel objective的难以处理的特性，LDS 需要通过随机计算图 stochastic computational graph 来估计超梯度hypergradient。使用得分函数估计器（也称作 REINFORCE）会将外层目标视为黑盒函数，并且不会利用 $F$ $ F $ 相对于采样的邻接矩阵和内部优化动态 inner optimization dynamics 是可微的。相反，路径估计器 path-wise estimator 并不容易使用，因为随机变量是离散的。
  LDS 借鉴了之前提出的解决方案（《Estimating or propagating gradients through stochastic neurons for conditional computation》），但是代价是估计有偏。

19.1 模型

19.1.1 背景知识

给定图 $G = (V, E, A)$ $ G=(V,E, \mathbf A) $ ，其中：
- $V = {v_{1}, \dots, v_{n}}$ $ V=\{v_1,\cdots,v_n\} $ 为节点集合， $E \subseteq V \times V$ $ E\sube V\times V $ 为边集合。
- 邻接矩阵 $A \in R^{n \times n}$ $ \mathbf A \in \mathbb R^{n\times n} $ 为：
  $\begin{matrix} A_{i, j} = {\begin{cases} 1, & (v_{i}, v_{j}) \in E \\ 0, & (v_{i}, v_{j}) \notin E \end{cases} \end{matrix}$
- 图拉普拉斯矩阵为 $L = D - A$ $ \mathbf L = \mathbf D - \mathbf A $ ，其中 $D = diag (D_{i}) \in R^{n \times n}$ $ \mathbf D=\text{diag}(D_{i})\in \mathbb R^{n\times n} $ 为度矩阵， $D_{i} = \sum_{j} A_{i, j}$ $ D_{i } =\sum_{j} A_{i,j} $ 。
- 每个节点 $v_{i}$ $ v_i $ 关联一个特征向量 ${\vec{x}}_{i} \in R^{d_{f}}$ $ \mathbf{\vec x}_i\in \mathbb R^{d_f} $ ，其中 $d_{f}$ $ d_f $ 为特征向量的维度。
  所有节点的输入特征向量拼接为特征矩阵 $X \in R^{n \times d_{f}}$ $ \mathbf X\in \mathbb R^{n\times d_f} $ ，其中第 $i$ $ i $ 行为 ${\vec{x}}_{i}$ $ \mathbf{\vec x}_i $ 。
- 每个节点 $v_{i}$ $ v_i $ 关联一个 label $y_{i}$ $ y_i $ ，将其展开为one-hot 向量为 ${\vec{y}}_{i} \in R^{K}$ $ \mathbf{\vec y}_i\in \mathbb R^K $ ，其中 $K$ $ K $ 为类别数量。
  所有节点的label 向量拼接为label 矩阵 $Y \in R^{n \times K}$ $ \mathbf Y\in \mathbb R^{n\times K} $ ，其中第 $i$ $ i $ 行为 ${\vec{y}}_{i}$ $ \mathbf{\vec y}_i $ 。
定义所有的邻接矩阵的取值空间为 $A_{n} \subseteq R^{n \times n}$ $ \mathcal A_n\sube \mathbb R^{n\times n} $ ，定义所有特征矩阵的取值空间为 $X_{n} \subseteq R^{n \times d_{f}}$ $ \mathcal X_n\sube \mathbb R^{n\times d_f} $ ，定义label 矩阵的取值空间为 $Y_{n} \subseteq R^{n \times K}$ $ \mathcal Y_n\sube \mathbb R^{n\times K} $ 。
则图神经网络的目标是学习函数：
$f_{\vec{w}} : X_{n} \times A_{n} \to Y_{n}$
其中 $\vec{w} \in R^{d_{w}}$ $ \mathbf{\vec w}\in \mathbb R^{d_w} $ 为网络的参数，它将所有参数展平为一维向量。
为学习目标函数，我们在训练集上最小化经验损失:
$L (\vec{w}, A) = \sum_{v \in V_{train}} l (f_{\vec{w}} (X, A)_{v}, y_{v}) + Ω (\vec{w})$
其中：
- $f_{\vec{w}} (X, A)_{v}$ $ f_{ \mathbf{\vec w}}(\mathbf X, \mathbf A)_v $ 为 $f_{\vec{w}}$ $ f_{ \mathbf{\vec w}} $ 针对节点 $v$ $ v $ 的输出。
- $l (\cdot, \cdot)$ $ l(\cdot,\cdot) $ 为point-wise 损失函数。
- $Ω (\cdot)$ $ \Omega(\cdot) $ 为正则化函数。
在 GCN 中，一个典型的 $f_{\vec{w}}$ $ f_ \mathbf{\vec w} $ 为：
$f_{\vec{w}} (X, A) = softmax (\hat{A} relu (\hat{A} X W_{1}) W_{2})$
其中：
- $\hat{A} = {\tilde{D}}^{- 1 / 2} (A + I) {\tilde{D}}^{- 1 / 2}$ $ \hat{\mathbf A} = \tilde{\mathbf D}^{-1/2} (\mathbf A + \mathbf I) \tilde{\mathbf D}^{-1/2} $ 为归一化的邻接矩阵。 $\tilde{D} = diag ({\tilde{D}}_{i}), {\tilde{D}}_{i} = 1 + \sum_{j} A_{i, j}$ $ \tilde{\mathbf D}=\text{diag}(\tilde D_i) ,\tilde{D}_i = 1 + \sum_{j}A_{i,j} $ 为归一化的度矩阵。
- 网络为两层网络，参数 $\vec{w}$ $ \mathbf{\vec w} $ 为 $(W_{1}, W_{2})$ $ (\mathbf W_1,\mathbf W_2) $ 展平为一维向量的形式。
Bilevel program 是一种优化问题，其中目标函数中出现的一组变量被约束为另一个优化问题的最优解。Bilevel program 出现在很多常见下，比如超参数调优、多任务学习、meta-learning 学习等。
给定外层目标函数 outer objective $F$ $ \mathcal F $ 和内层目标函数 inner objective $L$ $ \mathcal L $ ，给定外层变量outer variable $\vec{θ} \in R^{d_{m}}$ $ \vec\theta\in \mathbb R^{d_m} $ 和内层变量 inner variable $\vec{w} \in R^{d_{w}}$ $ \mathbf{\vec w}\in \mathbb R^{d_w} $ ，则一个bilevel program 定义为：
$min_{\vec{θ}, {\vec{w}}_{\vec{θ}}} F ({\vec{w}}_{\vec{θ}}, \vec{θ}) s . t . {\vec{w}}_{\vec{θ}} \in \arg min_{\vec{w}} L (\vec{w}, \vec{θ})$
直接求解上式非常困难，因为内层问题inner problem 通常没有闭式解。一种标准的求解方式是：利用迭代式的动态优化过程 $Φ$ $ \Phi $ （如随机梯度下降）的重复执行，从而代替直接求解 $L$ $ \mathcal L $ 的最小值。
令 ${\vec{w}}_{\vec{θ}, T}$ $ \mathbf{\vec w}_{\vec \theta,T} $ 为内层变量在经过 $T$ $ T $ 次迭代之后的结果，即：
${\vec{w}}_{\vec{θ}, T} = Φ ({\vec{w}}_{\vec{θ}, T - 1}, \vec{θ}) = Φ (Φ ({\vec{w}}_{\vec{θ}, T - 2}, \vec{θ}), \vec{θ}) = \dots$
假设 $\vec{θ}$ $ \vec\theta $ 和 $\vec{w}$ $ \mathbf{\vec w} $ 都是实数，且目标函数 $F, L$ $ \mathcal F,\mathcal L $ 和动态优化函数 $Φ$ $ \Phi $ 都是光滑的，则我们可以计算外层目标函数 $F$ $ \mathcal F $ 关于外层变量 $\vec{θ}$ $ \vec\theta $ 的梯度为：
$\nabla_{\vec{θ}} F ({\vec{w}}_{\vec{θ}, T}, \vec{θ}) = \frac{\partial F ({\vec{w}}_{\vec{θ}, T}, \vec{θ})}{\partial \vec{w}} \nabla_{\vec{θ}} {\vec{w}}_{\vec{θ}, T} + \frac{\partial F ({\vec{w}}_{\vec{θ}, T}, \vec{θ})}{\partial \vec{θ}}$
我们称其为超梯度hypergradient 。其中 $\nabla_{\vec{θ}} {\vec{w}}_{\vec{θ}, T}$ $ \nabla_\vec \theta \mathbf{\vec w}_{\vec \theta,T} $ 可以通过展开计算图并利用链式法则来在 $O (T (d_{w} + d_{m}))$ $ O(T(d_w + d_m)) $ 时间内高效地计算。
这种技术允许我们同时调优多个超参数，其调优数量比经典的超参数优化技术大几个量级。
但是这种方法需要执行更多的 $Φ$ $ \Phi $ ，计算量剧烈增长。

19.1.2 LDS

在现实世界中，经常会出现带噪音的图（noisy graph）、结构残缺的图（incomplete graph ）、甚至完全没有图结构（ missing graph）。为解决这些问题，我们必须在训练 GCN 网络参数的同时，还需要学习图结构。
我们将这个问题构造为一个 Bilevel program 问题，其中外层变量为图生成概率模型的参数，内层变量为 GCN 模型的参数。我们的方法同时优化了 GCN 模型参数以及图生成概率模型的参数。下图给出了我们方法的示意图：
假设真实邻接矩阵 $A$ $ \mathbf A $ 因为种种原因不可用（如 nosisy, incomplete, missing），我们的目标是寻找最小泛化误差的模型。给定验证集 $V_{val}$ $ V_{\text{val}} $ ，我们假设验证集的误差就代表者泛化误差。因此我们的目标是寻找使得以下函数最小的邻接矩阵 $A \in A_{n}$ $ \mathbf A\in \mathcal A_n $ ：
$F ({\vec{w}}_{A}, A) = \sum_{v \in V_{val}} l (f_{{\vec{w}}_{A}} (X, A)_{v}, y_{v})$
其中 ${\vec{w}}_{A}$ $ \mathbf{\vec w}_\mathbf A $ 为固定邻接矩阵 $A$ $ \mathbf A $ 时，损失函数 $L$ $ \mathcal L $ 最小的 $\vec{w}$ $ \mathbf {\vec w} $ （假设存在且唯一）。
因此：
- 我们将 $L (\vec{w}, A) = \sum_{v \in V_{train}} l (f_{\vec{w}} (X, A)_{v}, y_{v}) + Ω (\vec{w})$ $ \mathcal L( \mathbf{\vec w},\mathbf A) = \sum_{v\in V_{\text{train}}} \mathcal l \left(f_{ \mathbf{\vec w}}(\mathbf X, \mathbf A)_v, y_v\right) + \Omega( \mathbf{\vec w}) $ 设为内层目标函数，其目标是求解给定图结构的 GCN 的最佳参数。
- 我们将 $F ({\vec{w}}_{A}, A) = \sum_{v \in V_{val}} l (f_{{\vec{w}}_{A}} (X, A)_{v}, y_{v})$ $ \mathcal F(\mathbf{\vec w}_\mathbf A,\mathbf A) = \sum_{v\in V_{\text{val}}} \mathcal l(f_{\mathbf{\vec w}_\mathbf A}(\mathbf X, \mathbf A)_v, y_v) $ 设为外层目标函数，其目标是求解最佳的图结构。
  注意， $L$ $ \mathcal L $ 是在训练集 $V_{train}$ $ V_\text{train} $ 上评估， $F$ $ \mathcal F $ 是在验证集 $V_{val}$ $ V_\text{val} $ 上评估。
即使是很小的图，bilevel 问题也难以直接求解。另外，上述模型包含连续变量（GCN 参数）和离散变量（网络结构），这使得我们无法直接求解梯度（离散型变量无法求导）。
一种可能的解决方案是对离散型变量构造连续性松弛 continuous relaxation；另一种方案是对离散型变量使用概率分布。这里我们采用第二种方案。
我们利用二元伯努利随机变量对图的每条边进行建模，并假设每条边是否存在是相互独立的，则我们可以采样一个图 $A \in Ber (\vec{θ})$ $ \mathbf A \in \text{Ber}\left(\vec\theta\right) $ 。其中 $\vec{θ}$ $ \vec\theta $ 代表每条边是否存在的概率， $θ_{i, j} \in (0, 1)$ $ \theta_{i,j}\in (0,1) $ 。
这种边的独立性假设可能并不成立。假设 $v_{1}$ $ v_1 $ 和 $v_{2}$ $ v_2 $ 之间存在边、 $v_{2}$ $ v_2 $ 和 $v_{3}$ $ v_3 $ 之间存在边，那么 $v_{1}$ $ v_1 $ 和 $v_{3}$ $ v_3 $ 之间存在边的可能性较大。也就是边的存在不是独立的。
我们基于图结构的生成模型来重写 bilevel 问题为：
$min_{\vec{θ}, {\vec{w}}_{\vec{θ}}} E_{A \sim Ber (\vec{θ})} [F ({\vec{w}}_{\vec{θ}}, A)] s . t . {\vec{w}}_{\vec{θ}} \in \arg min_{\vec{w}} E_{A \sim Ber (\vec{θ})} [L (\vec{w}, A)]$
利用期望，现在内层目标函数和外层目标函数都是伯努利分布的参数的连续函数。
上式给出的 bilevel 问题仍然难以有效求解，这是因为内层目标函数对于 GCN 而言没有闭式解（目标函数非凸）。因此有效的算法仅能找到近似的解。
在给出近似解之前，我们先关注于GCN 模型的输出。对于具有 $n$ $ n $ 个节点的图 $G$ $ G $ ，给定边的分布概率 $P_{\vec{θ}}$ $ P_\vec\theta $ （其中 $\vec{θ}$ $ \vec\theta $ 为每条边的存在的概率），则 GCN 的期望输出为：
$f_{\vec{w}}^{exp} (X) = E_{A \sim P_{\vec{θ}}} [f_{\vec{w}} (X, A)] = \sum_{A} P_{\vec{θ}} (A) f_{\vec{w}} (X, A)$
不幸的是，即使对于很小的图，计算这个期望值也非常困难。于是我们可以计算期望输出的经验估计：
${\hat{f}}_{\vec{w}} (X) = \frac{1}{S} \sum_{s = 1}^{S} f_{\vec{w}} (X, A_{s})$
其中 $S > 0$ $ S\gt 0 $ 为图生成模型的采样数量， $A_{s}$ $ \mathbf A_s $ 为通过 $P_{\vec{θ}} (A)$ $ P_{\vec\theta}(\mathbf A) $ 采样的第 $s$ $ s $ 个图的邻接矩阵。
注意：
- ${\hat{f}}_{\vec{w}} (X)$ $ \hat f_{\mathbf {\vec w}} (\mathbf X) $ 是 $f_{\vec{w}}^{exp} (X)$ $ f_{\mathbf{\vec w}}^{\text{exp}}(\mathbf X) $ 的一个无偏估计。因此，为了使用 bilevel 中学到的 GCN $f_{\vec{w}}$ $ f_{\mathbf{\vec w}} $ 来进行预测，我们需要从 $P_{\vec{θ}}$ $ P_\vec\theta $ 中采样 $S$ $ S $ 个图，并计算 $f_{\vec{w}}$ $ f_{\mathbf{\vec w}} $ 的均值作为预测结果。
- 由于 $f_{\vec{w}}$ $ f_{\mathbf{\vec w}} $ 通常都是非线性函数，因此有： $E [f_{\vec{w}} (X, A)] \neq f_{\vec{w}} (X, E [A]) = f_{\vec{w}} (X, \vec{θ})$ $ \mathbb E[f_{\mathbf{\vec w}}(\mathbf X,\mathbf A)]\ne f_{\mathbf{\vec w}}(\mathbf X,\mathbb E[\mathbf A]) = f_{\mathbf{\vec w}}\left(\mathbf X, \vec \theta\right) $ 。最后一个等式成立是因为对于伯努利随机变量的期望等于其概率。
给定具有伯努利随机变量的图生成模型（边的概率分布 $P_{\vec{θ}} \in Ber (\vec{θ})$ $ P_\vec\theta \in \text{Ber}\left(\vec\theta\right) $ ），则可以在 $O (n^{2})$ $ O(n^2) $ 时间内采样一个新的图。由于不同边对应的随机变量是相互独立的，因此从大量伯努利随机变量进行采样是高效的、可并行化的，并且能够以百万每秒的速度执行。
- 如果将伯努利参数直接作为 GCN 的邻接矩阵，则这相当于一个全连接图，图中每条边的权重就是边存在的概率。此时计算GCN 输出的计算复杂度为 $O (n^{2} d_{w})$ $ O(n^2d_w) $ 。
- 如果采样 $S$ $ S $ 个图并计算其 GCN 的平均输出，由于每个采样的图都是稀疏图，则总的计算复杂度为 $O (S n_{e} d_{w})$ $ O(Sn_ed_w) $ ，其中 $n_{e} = \sum_{i, j} θ_{i, j}$ $ n_e=\sum_{i,j}\theta_{i,j} $ 为期望的边的数量。因此相比于前一种方式，这种计算输出的方式的效率更高。
  另外，使用图生成模型的另一个优势是：我们能够在概率上解释它。而学习稠密的邻接矩阵则无法做到。
  对于具有百万级别以上的大型图， $O (n^{2})$ $ O(n^2) $ 时间复杂度的图采样过程完全是不可行的。因此该方法仅适用于小型图。
现在我们考虑 bilevel 问题的近似解。
我们基于图结构的生成模型来重写 bilevel 问题为：
$min_{\vec{θ}, {\vec{w}}_{\vec{θ}}} E_{A \sim Ber (\vec{θ})} [F ({\vec{w}}_{\vec{θ}}, A)] s . t . {\vec{w}}_{\vec{θ}} \in \arg min_{\vec{w}} E_{A \sim Ber (\vec{θ})} [L (\vec{w}, A)]$
其中图生成模型的参数 $\vec{θ}$ $ \vec\theta $ 为外层变量，GCN 模型参数 $\vec{w}$ $ \mathbf{\vec w} $ 为内层变量。
- 对于内层问题，我们考虑期望 $E_{A \sim Ber (\vec{θ})} [L (\vec{w}, A)]$ $ \mathbb E_{\mathbf A\sim \text{Ber}\left(\vec\theta\right)}\left[\mathcal L\left( \mathbf{\vec w},\mathbf A\right)\right] $ 是由 $2^{n^{2}}$ $ 2^{n^2} $ 项求和而来（一共 $n^{2}$ $ n^2 $ 个伯努利随机变量，每个变量取值为 0 或 1 ）。因此即使对于很小的图，其计算复杂度也非常高。但是，换个角度来看，我们可以利用迭代式的动态优化过程 $Φ$ $ \Phi $ （如随机梯度下降）的重复执行，从而代替直接求解 $L$ $ \mathcal L $ 的最小值：
  ${\vec{w}}_{\vec{θ}, t + 1} = Φ ({\vec{w}}_{\vec{θ}, t}, A_{t}) = {\vec{w}}_{\vec{θ}, t} - γ_{t} \nabla L ({\vec{w}}_{\vec{θ}, t}, A_{t})$
  其中 $γ_{t}$ $ \gamma_t $ 为学习率， $A_{t} \sim Ber (\vec{θ})$ $ \mathbf A_t\sim \text{Ber}\left(\vec\theta\right) $ 为每轮迭代中采样到的图的邻接矩阵。
  在合适的假设下，当 $t \to \infty$ $ t\rightarrow \infty $ 时，SGD 收敛到权重向量 ${\vec{w}}_{\vec{θ}}$ $ \mathbf{\vec w}_\vec\theta $ ，并且该向量仅取决于边的概率分布 $P_{\vec{θ}}$ $ P_\vec\theta $ 。
  这种方法就是标准的随机梯度下降，其中邻接矩阵 $A_{t}$ $ \mathbf A_t $ 在每个 step 发生改变。但是，这种方式是否保证能够收敛到最小值？论文并未证明。直觉上看，难以保证收敛，因为在梯度下降过程中 $A_{t}$ $ \mathbf A_t $ 不断在变化，这导致 GCN 所应用的图在不断变化。
- 对于外层问题，令 ${\vec{w}}_{\vec{θ}, T}$ $ \mathbf{\vec w}_{\vec\theta,T} $ 为 $E [L]$ $ \mathbb E[\mathcal L] $ 的近似极小点（ $T$ $ T $ 可能依赖于 $\vec{θ}$ $ \vec\theta $ ），现在我们需要计算超梯度期望 $\nabla_{\vec{θ}} E_{A \sim Ber (\vec{θ})} [F]$ $ \nabla_{\vec\theta}\mathbb E_{\mathbf A\sim \text{Ber}\left(\vec\theta\right)}[\mathcal F] $ 的近似估计。
  根据：
  $\nabla_{\vec{θ}} F ({\vec{w}}_{\vec{θ}, T}, \vec{θ}) = \frac{\partial F ({\vec{w}}_{\vec{θ}, T}, \vec{θ})}{\partial \vec{w}} \nabla_{\vec{θ}} {\vec{w}}_{\vec{θ}, T} + \frac{\partial F ({\vec{w}}_{\vec{θ}, T}, \vec{θ})}{\partial \vec{θ}}$
  我们有：
  $\nabla_{\vec{θ}} E [F ({\vec{w}}_{\vec{θ}, T}, A)] = E [\nabla_{\vec{θ}} F ({\vec{w}}_{\vec{θ}, T}, A)] = E [\frac{\partial F ({\vec{w}}_{\vec{θ}, T}, A)}{\partial \vec{w}} \nabla_{\vec{θ}} {\vec{w}}_{\vec{θ}, T} + \frac{\partial F ({\vec{w}}_{\vec{θ}, T}, A)}{\partial A} \nabla_{\vec{θ}} A]$
  我们使用所谓的 straight-through 估计，并令 $\nabla_{\vec{θ}} A = I$ $ \nabla_\vec\theta \mathbf A = \mathbf I $ （因为 $A$ $ \mathbf A $ 是由二元伯努利变量生成，对应的参数为 $\vec{θ}$ $ \vec\theta $ ）。
最后，我们对上式采用单个样本的蒙特卡洛估计来更新参数 $\vec{θ}$ $ \vec\theta $ ，更新时采用梯度投影并将 $\vec{θ}$ $ \vec\theta $ 在单位立方体上截断（因为每个 $θ_{i, j}$ $ \theta_{i,j} $ 都在 0 到 1 之间）。
在计算外层问题的超梯度时，需要对 $Φ$ $ \Phi $ 进行展开。因为计算 $\nabla_{\vec{θ}} {\vec{w}}_{\vec{θ}, T}$ $ \nabla_\vec \theta \mathbf{\vec w}_{\vec \theta,T} $ 时需要考虑到：
${\vec{w}}_{\vec{θ}, T} = Φ ({\vec{w}}_{\vec{θ}, T - 1}, \vec{θ}) = Φ (Φ ({\vec{w}}_{\vec{θ}, T - 2}, \vec{θ}), \vec{θ}) = \dots$
这在时间和空间上都代价太大。
此外，我们依赖于梯度的有偏估计，因此并不期望从完整的计算中获得太多收益。因此我们建议截断计算，并在每 $τ$ $ \tau $ 次迭代中估计超梯度，其中 $τ$ $ \tau $ 为算法的超参数。这本质上是截断的反向传播算法，可以看作是一个 short-horizon 优化过程，其中带有对 $\vec{w}$ $ \mathbf {\vec w} $ 的热重启 warm restart 。
LDS 算法：
- 输入：
  - 特征矩阵 $X$ $ \mathbf X $
  - 标签矩阵 $Y$ $ \mathbf Y $
  - 可能有（也可能没有）邻接矩阵 $A$ $ \mathbf A $
  - 学习率 $η$ $ \eta $
  - 超梯度截断步长 $τ$ $ \tau $
  - 可能有（也可能没有）用于计算 kNN 的 $k$ $ k $ 值
- 输出：最佳的权重 $\vec{w}$ $ \mathbf {\vec w} $ 和最佳的概率分布 $P_{\vec{θ}}$ $ P_\vec\theta $
- 算法步骤：
  - 如果没有邻接矩阵 $A$ $ \mathbf A $ ，则通过 kNN 来初始化邻接矩阵 $A \leftarrow kNN (X, k)$ $ \mathbf A\leftarrow \text{kNN}(\mathbf X,k) $
  - 通过 $A$ $ \mathbf A $ 来初始化 $\vec{θ}$ $ \vec\theta $ ： $θ \leftarrow A$ $ \theta\leftarrow \mathbf A $
  - 外层迭代，当停止条件未满足时（基于验证集）：
    - $t \leftarrow 0$ $ t\leftarrow 0 $
    - 内层迭代，当内层目标函数还在下降时（基于训练集）：
      - 采样一个新的图： $A_{t} \sim Ber (\vec{θ})$ $ \mathbf A_t\sim \text{Ber}\left(\vec\theta\right) $
      - 优化内层目标函数： ${\vec{w}}_{\vec{θ}, t + 1} \leftarrow Φ_{t} ({\vec{w}}_{\vec{θ}, t}, A_{t})$ $ \mathbf{\vec w}_{\vec \theta,t+1} \leftarrow \Phi_t(\mathbf{\vec w}_{\vec \theta,t},\mathbf A_t) $
      - $t \leftarrow t + 1$ $ t\leftarrow t+1 $
      - 如果 $τ = 0$ $ \tau =0 $ 或者 $t mod τ = 0$ $ t \text{ mod } \tau = 0 $ ，则：
        采样一个新的图： $A_{t} \sim Ber (\vec{θ})$ $ \mathbf A_t\sim \text{Ber} \left(\vec\theta\right) $
        计算 $\vec{q} = \frac{\partial F ({\vec{w}}_{\vec{θ}, t}, A)}{\partial \vec{w}}$ $ \mathbf{\vec q} =\frac{\partial \mathcal F\left( \mathbf{\vec w}_{\vec \theta,t},\mathbf A\right)}{\partial \mathbf{\vec w}} $
        $G \leftarrow \frac{\partial F ({\vec{w}}_{\vec{θ}, t}, A)}{\partial A}$ $ \mathbf G \leftarrow\frac{\partial \mathcal F\left( \mathbf{\vec w}_{\vec \theta,t},\mathbf A\right)}{\partial \mathbf A} $
        迭代 $s = t - 1, \dots, t - τ$ $ s=t-1,\cdots, t-\tau $ ：
        采样一个结构： $A_{s} \sim Ber (\vec{θ})$ $ \mathbf A_s\sim \text{Ber} \left(\vec\theta\right) $
        计算 $\vec{p} \leftarrow D_{s} ({\vec{w}}_{\vec{θ}, s}, A_{s}) \vec{p}$ $ \mathbf{\vec p} \leftarrow \mathbf D_s (\mathbf{\vec w}_{\vec \theta,s},\mathbf A_s)\mathbf{\vec p} $ ，其中 $D_{s} ({\vec{w}}_{\vec{θ}, s}, A_{s}) = \frac{\partial Φ ({\vec{w}}_{\vec{θ}, s}, A_{s})}{\partial \vec{w}}$ $ \mathbf D_s (\mathbf{\vec w}_{\vec \theta,s},\mathbf A_s)= \frac{ \partial \Phi (\mathbf{\vec w}_{\vec \theta,s},\mathbf A_s)}{\partial\mathbf{\vec w}} $ 为雅可比矩阵
        计算 $G \leftarrow G + E_{s} ({\vec{w}}_{\vec{θ}, s}, A_{s}) \vec{p}$ $ \mathbf G\leftarrow \mathbf G + \mathbf E_s (\mathbf{\vec w}_{\vec \theta,s},\mathbf A_s)\mathbf{\vec p} $ ，其中 $E_{s} ({\vec{w}}_{\vec{θ}, s}, A_{s}) = \frac{\partial Φ ({\vec{w}}_{\vec{θ}, s}, A_{s})}{\partial A_{s}} \frac{\partial A_{s}}{\partial \vec{θ}} = \frac{\partial Φ ({\vec{w}}_{\vec{θ}, s}, A_{s})}{\partial A_{s}}$ $ \mathbf E_s (\mathbf{\vec w}_{\vec \theta,s},\mathbf A_s)= \frac{ \partial \Phi (\mathbf{\vec w}_{\vec \theta,s},\mathbf A_s)}{\partial\mathbf A_s}\frac{\partial \mathbf A_s}{\partial \vec\theta} = \frac{ \partial \Phi (\mathbf{\vec w}_{\vec \theta,s},\mathbf A_s)}{\partial\mathbf A_s} $
        优化外层目标函数： $\vec{θ} \leftarrow \vec{θ} - η G$ $ \vec \theta \leftarrow \vec\theta- \eta \mathbf G $ ，并将 $\vec{θ}$ $ \vec\theta $ 投影到单位立方体
  - 返回最佳的权重 $\vec{w}$ $ \mathbf {\vec w} $ 和最佳的概率分布 $P_{\vec{θ}}$ $ P_\vec\theta $
LDS 算法包含外层停止条件和内层停止条件。
- 对于内层停止条件，我们发现以内层目标函数的下降作为内层停止条件非常有效。
  我们持续优化 $L$ $ \mathcal L $ 直到 $L ({\vec{w}}_{t - 1, \vec{θ}}, A) (1 + ϵ) \geq L ({\vec{w}}_{t, θ}, A)$ $ \mathcal L(\mathbf{\vec w}_{t-1,\vec\theta},\mathbf A) (1+\epsilon) \ge \mathcal L(\mathbf{\vec w}_{t,\theta},\mathbf A) $ ，其中 $ϵ > 0$ $ \epsilon \gt 0 $ ，在实验中我们选择 $ϵ = 10^{- 3}$ $ \epsilon = 10^{-3} $ 。由于 $L$ $ \mathcal L $ 是非凸的，因此我们选择一个 patience 窗口为 $p$ $ p $ 个迭代步。
- 对于外层停止条件，我们发现使用早停策略非常有效。
  我们选择一部分验证集 $V_{valid}$ $ V_{\text{valid}} $ ，并通过期望输出 ${\hat{f}}_{\vec{w}} (X) = \frac{1}{S} \sum_{s = 1}^{S} f_{\vec{w}} (X, A_{s})$ $ \hat f_{\mathbf {\vec w}} (\mathbf X) = \frac{1}{S}\sum_{s=1}^S f_ \mathbf{\vec w}(\mathbf X, \mathbf A_s) $ 来评估验证准确性。如果外层循环连续几次迭代都没有得到改善则提前停止优化过程。这有助于避免外层目标函数过拟合。
  但是当需要优化的参数数量太多、验证集规模太小时，可能会存在验证集的过拟合。
每次外层迭代中，对超梯度的估计都存在偏差。偏差即来自于 straig-through 估计，也来自于超梯度的截断。尽管如此，我们从实验中发现该算法能够取得良好的效果，并能够在边的分布空间中找到适合于当前任务的参数。
LDS 借鉴了之前提出的启发式方案，但是代价是超梯度估计是有偏的。
给定一个函数 $h (z)$ $ h(z) $ ，其中 $z$ $ z $ 是一个伯努利分布的离散型随机变量，其分布依赖于 $θ$ $ \theta $ 。作为示例，我们考虑非常简单的情况：假设 $h (z) = (a z - b)^{2} / 2$ $ h(z) = (az-b)^2/2 $ ， $a, b$ $ a,b $ 都为标量， $z \sim Ber (θ), θ \in [0, 1]$ $ z\sim \text{Ber}(\theta),\theta\in [0,1] $ 。
- $E [h]$ $ \mathbb E[h] $ 对 $θ$ $ \theta $ 的梯度可以简单计算得到：
  $\frac{\partial}{\partial θ} E_{z \sim Ber (θ)} [h (z)] = \frac{\partial}{\partial θ} [θ \frac{(a - b)^{2}}{2} + (1 - θ) \frac{b^{2}}{2}] = \frac{a^{2}}{2} - a b$
- $E [h]$ $ \mathbb E[h] $ 对 $θ$ $ \theta $ 的梯度对应的 straight-through 估计量为：
  $\hat{g} (z) = \frac{\partial h (z)}{\partial z} = (a z - b) a, z \sim Ber (θ)$
  则有：
  $E_{z \sim Ber (θ)} [\hat{g} (z)] = θ (a - b) a + (1 - θ) (- a b) = θ a^{2} - a b$
  通常 $θ \neq 1 / 2$ $ \theta\ne 1/2 $ ，因此 $\hat{g}$ $ \hat g $ 是一个有偏的估计。
LDS 算法有两个缺陷：
- 计算复杂度太高，导致无法扩展到大图。
- 仅限于 transductive learning，无法扩展到未见过的节点。对于新的、未见过的节点，需要从头开始重新训练模型。

19.2 实验

我们针对三个目标进行了一系列实验：
- 首先，我们在节点分类问题上评估 LDS，其中图结构虽然可用但是缺失了一定比例的边。这里我们将 LDS 和包括普通 GCN 在内的基于图的学习算法进行比较。
- 其次，我们想验证我们的假设，即 LDS 可以在没有图的半监督分类问题上取得有竞争力的结果。这里我们将 LDS 和许多现有的半监督分类算法进行比较。
  此外，我们对比了一些图算法，图是通过在数据集上创建的 kNN 近邻图。
- 最后，我们分析了学到的图生成模型，从而了解LDS 如何学到有意义的边的概率分布。
数据集：
- 图数据集：Cora, Citeseer 是图的两个基准数据集，输入特征是 bag of word，任务是节点分类。我们遵循之前的工作，执行相同的数据集拆分和实验配置。
  为评估残缺图上 LDS 的鲁棒性，我们通过随机采样 25%, 50%, 75% 的边来构造残缺图。
- 非图数据集：我们使用 scikit-learn 中的基准数据集，如 Wine, Breast Cancer(Cancer), Digits, 20 NewsGroup(20News) 等数据集，这些数据集都不是图结构。我们用这些非图数据集来评估 LDS。
  对于20 NewsGroup 数据集，我们从中挑选出 10 个类别，然后使用词频超过 5% 的单词的 TF-IDF 作为特征。
- FMA 数据集：该数据集从 7994 个音乐曲目中提取了 140 个音频特征，任务是音乐风格分类。
所有这些数据集的统计信息如下：
baseline 方法：
- 对于图算法，我们对比了以下方法：普通 GCN、GCN-RND、标签传播算法label propagation: LP、流形正则化算法manifold regularization: ManiReg、半监督 embedding 算法semi-supervised embedding: SemiEmb 。其中 ManiReg, SemiEmb 将一个 kNN 图作为拉普拉斯正则化的输入。
  GCN-RND 是在普通 GCN 的每个优化step 中添加随机采样的边。通过这种方法，我们打算证明：仅将随机边添加到 GCN 中不足以提高模型的泛化能力。
- 对于非图算法，我们对比了以下方法：GC、逻辑回归logistic regression: LogReg、支持向量机 support vector machines: Linear and RBF SVM、随机森林random forests: RF 、前馈神经网络 feed-forward neural networks:FFNN 。
- 当没有图结构时，GCN 退化为前馈神经网络，此时我们通过下列的手段来构造图结构：
  - 随机创建一个稀疏的图结构，记作 Sparse-GCN 。
  - 以相等的边概率构建一个稠密图，记作 Dense-GCN。
  - 基于输入特征构建一个 RBF 核的稠密图，记作 RBF-GCN。
  - 基于输入特征构建一个kNN 近邻图的稀疏图，记作 kNN-GCN 。
  对于 LDS，我们使用 KNN 近邻图作为初始的边概率，即 kNN-LDS 。另外，我们进一步比较了 LDS 的稠密版本，此时我们学习一个稠密的相似度矩阵，记作 kNN-LDS(dense) 。
当需要用到 kNN 时，需要考虑两个超参数：k 值的选择、度量函数的选择。我们从 $k \in {2, 3, \dots, 20}$ $ k\in \{2,3,\cdots,20\} $ ，以及度量函数为欧拉距离、cosine 距离，然后通过验证集的准确性来调优这两个超参数。
对于 kNN-LDS， $k \in {10, 20}$ $ k\in \{10,20\} $ 。
GCN 和 LDS 配置：
- 对于所有用到 GCN 的网络，我们使用两层 GCN 网络，隐层维度为 16，采用 ReLU 激活函数。
- 我们使用 0.5 的 dropout rate 来执行 dropout，从而执行额外的正则化。
- 我们使用 Adam 优化器，学习率从 ${0.005, 0.01, 0.02}$ $ \{0.005,0.01,0.02\} $ 中选择
- SemiEmb 核 FFNN 使用相同数量的隐层维度、相同的激活函数。
- 我们使用带正则化的交叉熵损失函数：
  $L (\vec{w}, A) = - \sum_{v \in V_{train}} {\vec{y}}_{v} \circ \log [f_{\vec{w}} (X, A)_{v}] + ρ {‖ \vec{w} ‖}^{2}$
  其中 ${\vec{y}}_{v}$ $ \mathbf{\vec y}_v $ 为第 $v$ $ v $ 各节点的标签的 one-hot 向量， $\circ$ $ \circ $ 为逐元素乘积， $ρ$ $ \rho $ 为非负的正则化系数。
- 对于 LDS，除了已知的边或者 kNN 构造的边我们设置为 $θ_{i, j} = 1$ $ \theta_{i,j} = 1 $ 之外，其它的 $θ_{i, j} = 0$ $ \theta_{i,j} = 0 $ 。
- 我们将验证集平均划分为验证集 (A) 和早停集(B)。对于外层目标，我们使用 (A) 上的不带正则化的交叉熵损失，并通过随机梯度下降对其进行优化。
- 我们通过超参数调优来优化外层循环的步长 $η$ $ \eta $ ，即超梯度截断的更新次数 $τ$ $ \tau $ 。
- 最后我们采样 $S = 16$ $ S=16 $ 个样本来计算输出的预测。
- 对于 LDS 和 GCN，我们以 20 步的窗口大小来应用早停。
其它方法的实现来自于 skicit-learn 或者原始论文。所有方法的超参数都是通过验证集的 accuracy 来调优。

19.2.1 图数据集

我们比较了在图数据集（Cora 左图、Citeseer 中间图）的残缺图上的结果。我们给出边的每个保留比例，以及对应的验证集准确率（虚线，用于早停）和测试集准确率（实线），阴影表示标准差。所有结果都随机执行5 次并取均值。
可以看到：
- LDS 在所有情况下都具有竞争性优势，准确率提升了 7% 。最终 Cora 和 Citeseer 的准确率分别为 84.1% 和 75.0%，超越了所有的 state-of-the-art 模型。
- 当保留所有的边（100%）时，LDS 还可以通过学习其它额外的、有用的边来提高 GCN 模型的泛化准确率。
- 从 GCN 和 GCN-RND 对比中可以看到，随机添加边并不能减少泛化误差，这对于模型没有任何帮助。
右图给出超梯度截断的更新次数 $τ$ $ \tau $ 对 LDS 的影响。 $τ = 0$ $ \tau=0 $ 对应于内层、外层交替优化。可以看到：
- $τ > 0$ $ \tau\gt 0 $ （即：内层多步优化）的效果要远远超过交替优化
- $τ$ $ \tau $ 进一步提升到 20 并不会带来明显提升，同时会增加计算成本
上述实验更详细的结果如下表所示，其中（+- 表示标准差）。
我们考虑 LDS 在 Cora,Citeseer 数据集上期望的边的数量，从而分析学到的图生成器采样的图的属性。
- LDS 期望的边的数量高于原始图的边的数量，这是可以预期的，因为 LDS 具有比普通 GCN 更高的准确率。
- 尽管如此，LDS 学到的图仍然是非常稀疏的，如，对于 Cora 而言平均只有不到 0.2% 的边。这有助于 LDS 的内层循环中有效学习 GCN 。

19.2.2 半监督学习

我们考察 LDS 在所有数据集上的半监督学习效果。每个实验随机执行 5 次并报告平均的测试准确率和标准差（以 +- 表示）。有竞争力的结果以粗体展示。
结论：
- 非图算法在某些数据集上效果很好（如 Wine,Cancer,FMA），但是在 Digits,Citeseer,Cora,20news 等其它数据集上效果较差。
- LP, ManiReg, SemiEmb 只能改善 Digits,20news 数据集的效果。
- 和非图算法相比，kNN-GCN 效果很好，并提供了具有竞争力的结果。
- kNN-LDS 是所有数据集中最具竞争力的方法之一，并且在图数据集上获得最高的收益。
- kNN-LDS 的性能略优于其 dense 模型，并且其稀疏图可以扩展到更大的数据集。

19.2.3 图生成模型

我们给出LDS （ $τ = 5$ $ \tau = 5 $ ）在Cora 数据集（保留 25% 的边）学习过程中，三种类型的节点（训练集、验证集、测试集,对应于下图的从左到右）的平均的边概率的演变，每种类型一个节点。对于每个样本节点，所有其它节点被划分为四个分组：底层真实图中相邻的节点（True link）、相同类别的节点（Same class）、不同类别的节点（Different classes）、未知类别的节点（Unknown classes）。图中灰色竖线指示内层优化何时重启。纵坐标以 log 10 来表示。
- 平均而言，LDS 将相同类别标签样本之间存在边的概率提高了 10 到 100 倍。
- LDS 能够为真实相邻的边赋予一个较高的概率。
我们给出LDS （ $τ = 5$ $ \tau = 5 $ ）在Cora 数据集（保留 25% 的边）学习完成之后，三种类型的节点（训练集、验证集、测试集,对应于下图的从左到右）的边的概率的归一化直方图，每种类型一个节点。对于每个样本节点，所有其它节点被划分为两个分组：相同类别的节点（Same class）、不同类别或未知类别的节点（Different/Unknown classes）。直方图统计按照 log 10 分为六个桶。
可以看到：LDS 学到边的高度非均匀的概率分布能够反应节点的类别。
我们给出LDS （ $τ = 5$ $ \tau = 5 $ ）在Citeseer 数据集（保留 25% 的边）学习完成之后，被 kNN-GCN 误分类但是被 kNN-LDS 正确分类的测试集的三个节点的边的概率的归一化直方图。。对于每个样本节点，所有其它节点被划分为两个分组：相同类别的节点（Same class）、不同类别或未知类别的节点（Different/Unknown classes）。直方图统计按照 log 10 分为六个桶。
可以看到：
- LDS 学到边的高度非均匀的概率分布能够反应节点的类别，这和前面的结论相同。
- 可能更重要的是捕获有效的边的分布（即相同类别之间存在边的概率更高），而不是选择正确的连接。
我们用 t-SNE 进一步可视化了 GCN 和 LDS 学到的 embedding。下图给出了 Citeseer 数据集上使用 Dense-GCN（左）、kNN-GCN（中）、kNN-LDS（右）学到的 embedding 的的 t-SNE 可视化。该 embedding 是最后一层卷积层的输出。
可以看到：kNN-LDS 学到的 embedding 在所有不同类别之间提供了最佳分隔。