Question

1. 近年来图神经网络GNN 被广泛使用，不幸的是只有图结构的数据才能使用 GNN 。很多真实世界中的数据（如社交网络）天然就是图结构数据，但是对于下游任务而言，这些天然的图结构是否对于当前任务是最优的则不一定。更重要的是，很多场景下可能没有图结构数据，因此需要从原始数据中构造图结构数据。

   • 在图信号处理领域，研究人员探索了从数据中学习图结构的各种方法，但是他们并未考虑下游任务。
   • 另外，越来越多的工作研究交互系统的动态建模从而利用隐式的交互模型，但是这些方法无法在很多噪音甚至没有图结构的情况下直接联合学习图结构和 graph representation 。
   • 最近，研究人员探索了对非图结构数据自动构建图结构并应用 GNN，但是这些方法仅优化了针对下游任务的图结构，并未利用已被证明在图信号处理中非常有用的技术。
   • 最近，论文 《Learning Discrete Structures for Graph Neural Networks》 提出了一种新的方法（即，LDS-GNN ），该方法通过近似求解一个 bilevel program 从而共同学习图结构和 GCN 参数。但是，该方法存在严重的可扩展性问题，因为它需要学习$n^2$$ n^2 $ 个伯努利随机变量（$n$$ n $ 为图中节点数量）。更重要的是，它只能应用于 transductive learning，这意味着该方法在测试期间无法应用于新的、未见过的节点。

   为解决这些限制，论文 《Deep Iterative and Adaptive Learning for Graph Neural Networks》 提出了一种用于 GNN 的深度迭代和自适应学习框架 Deep Iterative and Adaptive Learning for Graph Neural Networks: DIAL-GNN ，该框架共同学习针对具体任务的最优图结构和 GNN 网络参数。DIAL-GNN 将构建图的图学习graph learning 问题转换为数据驱动的相似性度量学习问题 similarity metric learning 。

   然后作者利用自适应图正则化来控制生成的图结构的平滑性smoothness、连接性connectivity 以及稀疏性 sparsity 。更重要的是，作者提出了一种新颖的迭代方法来搜索隐藏的图结构hidden graph structure，该隐藏的图结构将初始图结构优化到监督学习（或半监督学习）任务的最优图结构。另外，论文的方法可以同时处理transductive learning 和 inductive learning。

   最后，通过广泛的实验表明，在下游任务性能以及计算时间方面，论文提出的 DIAL-GNN 模型可以始终超越或者接近 state-of-the-art 基准模型。

20.1 模型

1. 给定$n$$ n $ 个节点的集合$\mathcal{V}=\{v_1,\cdots ,v_n\}$$ \mathcal V=\{v_1,\cdots,v_n\} $ ，每个节点$v$$ v $ 关联一个特征向量${\overrightarrow{\mathbf{x}}}_v\in {\mathbb{R}}^d$$ \mathbf{\vec x}_v\in \mathbb R^d $ 。所有节点的特征向量组成特征矩阵$\mathbf{X}\in {\mathbb{R}}^{d\times n}$$ \mathbf X\in \mathbb R^{d\times n} $ ，其中第$v$$ v $ 行对应于节点$v$$ v $ 的特征向量${\overrightarrow{\mathbf{x}}}_v$$ \mathbf{\vec x}_v $ 。

   图结构学习任务的目标是自动学习图结构$\mathcal{G}$$ \mathcal G $ ，以邻接矩阵$\mathbf{A}\in {\mathbb{R}}^{n\times n}$$ \mathbf A\in \mathbb R^{n\times n} $ 的形式，然后$\mathcal{G}$$ \mathcal G $ 被 GNN-based 模型来应用于下游的预测任务。

2. 大多数现有方法通过预处理过程来基于人工规则或特征来构造图，如 kNN 近邻图。和这些方法不同，我们提出的 DIAL-GNN 框架将问题描述为一个迭代式学习问题，该问题以端到端的方式联合学习图结构和 GNN 参数。

   DIAL-GNN 整体架构如下图所示，其中最左侧图中的虚线表示原始的图结构${\mathbf{A}}_0$$ \mathbf A_0 $ ，它来自于真实的图结构(如果存在) 或者来自于kNN 近邻图构建的图结构。

   

20.1.1 相似度量学习

1. 构建图的一个常用策略是：首先基于某种度量来计算节点pair 对之间的相似度，然后在下游任务中使用人工构建的图。和这些方法不同，我们为图结构学习设计了一个可学习的度量函数，它将与下游任务的模型一起训练。

2. Similarity Metric Learning：类似于 multi-head attention 机制，我们设计了 multi-head 余弦相似度：

   $$\begin{array}{c}{s}_{i,j}^{(k)}=\cos ({\overrightarrow{\mathbf{w}}}_k\odot {\overrightarrow{\mathbf{v}}}_i,{\overrightarrow{\mathbf{w}}}_k\odot {\overrightarrow{\mathbf{v}}}_j)\\ s_{i,j}=\frac{1}{K}\sum _{k=1}^K{s}_{i,j}^{(k)}\end{array}$$

   其中：

   • $s_{i,j}^{(k)}$$ s_{i,j}^{(k)} $ 为两个输入向量${\overrightarrow{\mathbf{v}}}_i$$ \mathbf{\vec v}_i $ 和${\overrightarrow{\mathbf{v}}}_{\mathbf{j}}$$ \mathbf{\vec v_j} $ 在第$k$$ k $ 个视图上的余弦相似度，$k=1,\cdots ,K$$ k=1,\cdots,K $ 。$K$$ K $ 为head 的数量。
   • ${\overrightarrow{\mathbf{w}}}_k$$ \mathbf{\vec w}_k $ 为第$k$$ k $ 个 head 的权重向量，它在所有节点之间共享，并代表一个视图 perspective 。每个视图捕获了节点之间的部分相似语义。
   • $\odot$$ \odot $ 为逐元素乘积。

   我们用$K$$ K $ 个权重向量独立地计算$K$$ K $ 个余弦相似度矩阵，然后将它们的均值作为最终相似度$\mathbf{S}$$ \mathbf S $ 。

   这里采用权重向量的逐元素乘积，而不是基于矩阵乘法的投影（即，${\mathbf{W}}_k{\overrightarrow{\mathbf{v}}}_i$$ \mathbf W_k\mathbf{\vec v}_i $ ）。如果采用矩阵乘法的投影，那么模型容量更大同时参数也更多（权重矩阵${\mathbf{W}}_k$$ \mathbf W_k $ vs 权重向量${\overrightarrow{\mathbf{w}}}_k$$ \mathbf{\vec w}_k $ ）。

   这里多个视图的相似性取平均，也可以考虑取最大值或者中位数？

3. Graph Sparsification：邻接矩阵应该是非负的（度量 metric 也应该是非负的），而$s_{i,j}$$ s_{i,j} $ 取值范围是 [-1,1] 。此外，很多真实的图结构都是稀疏的。进一步地，一个稠密图不仅计算代价较高，而且对于大多数场景意义不大。

   因此我们仅考虑每个节点的$ϵ-\text{neighborhood}$$ \epsilon-\text{neighborhood} $ ，从而从$\mathbf{S}$$ \mathbf S $ 中构造稀疏的邻接矩阵$\mathbf{A}$$ \mathbf A $ 。具体而言，我们丢弃了$\mathbf{S}$$ \mathbf S $ 中小于阈值$ϵ>0$$ \epsilon\gt0 $ 的元素：

   $$\begin{array}{c}{A}_{i,j}=\{\begin{array}{ll}{s}_{i,j}& ,s_{i,j}>ϵ\\ 0,& \text{else}\end{array}\end{array}$$

   .

20.1.2 图正则化

1. 在图信号处理 graph signal processing 中，对图信号广泛采用的假设是：value 在相邻节点之间平滑变化。

   给定一个加权无向图$\mathcal{G}$$ \mathcal G $ 的对称的邻接矩阵$\mathbf{A}$$ \mathbf A $ ，一组$n$$ n $ 个图信号${\overrightarrow{\mathbf{x}}}_1,\cdots ,{\overrightarrow{\mathbf{x}}}_n\in {\mathbb{R}}^d$$ \mathbf{\vec x}_1,\cdots,\mathbf{\vec x}_n\in \mathbb R^d $ 的平滑性 smoothness通常由迪利克雷能量 Dirichlet energy 来衡量：

   $$\mathrm{\Omega }(\mathbf{A},\mathbf{X})=\frac{1}{2n^2}\sum _{i,j}{A}_{i,j}{\Vert {\overrightarrow{\mathbf{x}}}_i-{\overrightarrow{\mathbf{x}}}_j\Vert }^2=\frac{1}{n^2}\text{tr}\left({\mathbf{X}}^{\mathrm{\top }}\mathbf{L}\mathbf{X}\right)$$

   其中：

   • $\mathbf{L}=\mathbf{D}-\mathbf{A}$$ \mathbf L =\mathbf D-\mathbf A $ 为图的拉普拉斯矩阵，$\mathbf{D}=\text{diag}(D_i),D_i=\sum _j{A}_{i,j}$$ \mathbf D = \text{diag}(D_{i }),D_i = \sum_j A_{i,j} $ 为图的度矩阵。
   • $\text{tr}(\cdot )$$ \text{tr}(\cdot) $ 为矩阵的迹trace 。

   可以看到：最小化$\mathrm{\Omega }(\mathbf{A},\mathbf{X})$$ \Omega(\mathbf A, \mathbf X) $ 将使得相邻节点具有相似的特征，从而在$\mathbf{A}$$ \mathbf A $ 定义的图上强化图信号的平滑性。

2. 上述平滑损失 smoothness loss 最小化存在一个平凡解 trivial solution ：$\mathbf{A}=\mathbf{0}$$ \mathbf A = \mathbf 0 $ 。另外除了平滑性，我们还希望控制图结构的稀疏性sparsity。考虑 《How to learn a graph from smooth signals》 的做法，我们对学习的图结构施加了额外的约束：

   $$f(\mathbf{A})=\frac{-\beta }{n}{\overrightarrow{\mathbf{1}}}^{\mathrm{\top }}\log \left(\mathbf{A}\overrightarrow{\mathbf{1}}\right)+\frac{\gamma }{n^2}||\mathbf{A}|{|}_F^2$$

   其中：$\beta ,\gamma$$ \beta,\gamma $ 为非负的超参数；$||\cdot |{|}_F$$ ||\cdot||_F $ 为矩阵的 F 范数。

   • 第一项通过对数的 barrier 来惩罚不连续图的形成，即连通性connectivity 。

     $${\overrightarrow{\mathbf{1}}}^{\mathrm{\top }}\log \left(\mathbf{A}\overrightarrow{\mathbf{1}}\right)=\sum _i\log \left(\sum _j{A}_{i,j}\right)$$

     当存在孤立节点$i$$ i $ 时，$\sum _j{A}_{i,j}$$ \sum_j A_{i,j} $ 等于零（不考虑$A_{i,i}$$ A_{i,i} $ ），因此$-\beta \log 0$$ -\beta\log 0 $ 趋向于正无穷，因此第一项趋近于正无穷。

   • 第二项惩罚第一项造成的较大degree，从而控制稀疏性。

     在构造邻接矩阵$\mathbf{A}$$ \mathbf A $ 时，通过对低于阈值$ϵ$$ \epsilon $ 的元素置零来人工提供稀疏性。而这里通过正则化进一步提供而稀疏性。

   图的总体正则化损失为上述损失之和，从而控制学习的图结构的平滑性、连通性、稀疏性：

   $${\mathcal{L}}_{\mathcal{G}}=\alpha \mathrm{\Omega }(\mathbf{A},\mathbf{X})+f(\mathbf{A})$$

   其中$\alpha ,\beta ,\gamma$$ \alpha,\beta,\gamma $ 都是非负的超参数。

20.1.3 迭代式图学习

a. Joint Graph Structure and Representation Learning

1. 我们期望图结构能起到两个作用：它应该遵循节点之间的语义关系；它应该适合下游预测任务的需求。

   因此，我们通过结合任务预测损失和图正则化损失来联合学习图结构和graph representation，即：

   $$\mathcal{L}={\mathcal{L}}_{\text{pred}}+{\mathcal{L}}_{\mathcal{G}}$$

   注意：我们的图学习框架与各种GNN 无关，也和预测任务无关。为方便讨论，我们采用两层 GCN，其中第一层将节点特征映射到 embedding 空间，第二层将embedding 映射到输出空间：

   $$\begin{array}{c}\mathbf{Z}=\text{relu}\left(\tilde{\mathbf{A}}\mathbf{X}{\mathbf{W}}_1\right)\\ \hat{\mathbf{Y}}=\text{output}\left(\tilde{\mathbf{A}}\mathbf{Z}{\mathbf{W}}_2\right)\\ {\mathcal{L}}_{\text{pred}}=\mathcal{l}(\hat{\mathbf{Y}},\mathbf{Y})\end{array}$$

   其中：

   • $\tilde{\mathbf{A}}$$ \tilde{\mathbf A} $ 为归一化的邻接矩阵。
   • $\text{output}(\cdot )$$ \text{output}(\cdot) $ 为具体任务的输出函数（如，sigmoid 或 softmax ）。
   • $\mathcal{l}(\cdot )$$ \mathcal l(\cdot) $ 为具体任务的损失函数。
   • $\mathbf{Y}$$ \mathbf Y $ 为节点的 label 矩阵，$\hat{\mathbf{Y}}$$ \hat{\mathbf Y} $ 为节点的预测输出矩阵。

   对于节点分类任务，$\text{output}(\cdot )$$ \text{output}(\cdot) $ 为预测节点类别概率分布的 softmax 函数，$\mathit{l}(\cdot ,\cdot )$$ \mathit l(\cdot,\cdot) $ 为预测损失的交叉熵函数。

2. 现在我们讨论如何获得归一化的邻接矩阵$\tilde{\mathbf{A}}$$ \tilde{\mathbf A} $ 。我们的初步实验表明：如果初始图结构 initial graph structure 可用，则完全丢失初始图结构是有害的。

   之前的一些工作通过执行 masked attention 从而将初始图结构注入到图结构学习中，但是这会限制图结构学习的能力。因为这种方法无法学到初始图结构中不存在、但是实际上有用的那些边。我们假设最优图结构和初始图结构的差异很小，因此我们认为最优图结构和初始图结构、度量学习学到的图结构满足以下关系：

   $$\tilde{\mathbf{A}}=\lambda {\mathbf{L}}_0+(1-\lambda )\left({\mathbf{D}}^{-1/2}\mathbf{A}{\mathbf{D}}^{-1/2}\right)$$

   其中：

   • ${\mathbf{L}}_0={\mathbf{D}}_0^{-1/2}{\mathbf{A}}_0{\mathbf{D}}_0^{-1/2}$$ \mathbf L_0 = \mathbf D_0^{-1/2} \mathbf A_0 \mathbf D_0^{-1/2} $ 为初始图结构的归一化的邻接矩阵，${\mathbf{D}}_0$$ \mathbf D_0 $ 为初始图结构的度矩阵。
   • 超参数$\lambda$$ \lambda $ 用于平衡初始图结构和度量学习学到的图结构。

   上式等价于：$\tilde{\mathbf{A}}=\lambda {\mathbf{L}}_0+(1-\lambda )\frac{A_{i,j}}{\sum _j{A}_{i,j}}$$ \tilde{\mathbf A} = \lambda \mathbf L_0 + (1-\lambda) \frac{A_{i,j}}{\sum_j A_{i,j}} $ 。

如果初始图结构${\mathbf{A}}_0$$ \mathbf A_0 $ 不可用，则我们使用余弦相似度构造 kNN 近邻图从而作为初始图结构。

“最优图结构和初始图结构的差异很小” 这是一个非常强的假设。当$\lambda =1$$ \lambda=1 $ 时模型就回退到使用初始图结构的版本。

b. Iterative Method for Graph Learning:

1. 以前的一些工作仅依靠原始节点特征并基于某些注意力机制来学习图结构。我们认为这有一些局限性，因为原始节点特征可能不包含足够的信息来学习号的图结构。我们的初步实验表明：简单地在这些原始节点特征上应用一些注意力函数无助于学习有意义的图。

   为解决上述限制，我们提出了一种用于图神经网络的深度迭代和自适应学习框架，即 Deep Iterative and Adaptive Learning framework for Graph Neural Network: DIAL-GNN 。具体而言，除了基于原始特征计算节点相似度之外，我们还引入了另一个可学习的、基于节点 embedding 计算到的相似度度量函数。这么做的目的是在 node embedding 空间上定义的度量函数能够学习拓扑信息，从而补充仅基于原始节点特征学到的拓扑信息。为了结合原始节点特征和节点 embedding 双方的优势，我们将最终学到的图结构作为它们的线性组合：

   $${\overline{\mathbf{A}}}^{(t)}=\eta {\tilde{\mathbf{A}}}^{(t)}+(1-\eta ){\tilde{\mathbf{A}}}^{(0)}$$

   其中：${\tilde{\mathbf{A}}}^{(t)}$$ \tilde{\mathbf A}^{(t)} $ 和${\tilde{\mathbf{A}}}^{(0)}$$ \tilde{\mathbf A}^{(0)} $ 为通过公式$\tilde{\mathbf{A}}=\lambda {\mathbf{L}}_0+(1-\lambda )\left({\mathbf{D}}^{-1/2}\mathbf{A}{\mathbf{D}}^{-1/2}\right)$$ \tilde{\mathbf A} = \lambda \mathbf L_0 + (1-\lambda)\left(\mathbf D^{-1/2}\mathbf A\mathbf D^{-1/2}\right) $ 得到的两个归一化的邻接矩阵，分别对应于第$t$$ t $ 轮迭代和初始迭代。

2. DIAL-GNN 算法：

   • 输入：

     • 特征矩阵$\mathbf{X}$$ \mathbf X $ ，节点label 矩阵$\mathbf{Y}$$ \mathbf Y $
     • 初始的邻接矩阵（如果有的话）${\mathbf{A}}_0$$ \mathbf A_0 $
     • 超参数$K,ϵ,\alpha ,\beta ,\gamma ,\lambda ,\delta ,T,\eta ,k$$ K, \epsilon,\alpha,\beta,\gamma,\lambda,\delta, T,\eta, k $

   • 输出：最优图结构${\tilde{\mathbf{A}}}^{(t)}$$ \tilde{\mathbf A}^{(t)} $ ，模型参数$\mathrm{\Theta }$$ \Theta $ ，预估label 矩阵$\hat{\mathbf{Y}}$$ \hat{\mathbf Y} $

   • 算法步骤：

     • 随机初始化GCN 模型参数$\mathrm{\Theta }$$ \Theta $ 。

     • 如果初始邻接矩阵${\mathbf{A}}_0$$ \mathbf A_0 $ 不可用则通过 kNN 来给出初始邻接矩阵：${\mathbf{A}}_0\leftarrow \text{kNN}(\mathbf{X},k)$$ \mathbf A_0 \leftarrow \text{kNN}(\mathbf X,k) $ ；否则直接使用${\mathbf{A}}_0$$ \mathbf A_0 $ 。

     • 根据${\mathbf{A}}_0$$ \mathbf{ A}_0 $ 和$\mathbf{X}$$ \mathbf X $ 来计算${\mathbf{A}}^{(0)}$$ \mathbf A^{(0)} $ 和${\tilde{\mathbf{A}}}^{(0)}$$ \tilde{\mathbf A}^{(0)} $ 。

       其中，${\mathbf{A}}^{(0)}={\mathbf{A}}_0$$ \mathbf A^{(0)} = \mathbf A_0 $ 。

     • 计算节点 embedding ：${\mathbf{Z}}^{(0)}=\text{relu}\left({\tilde{\mathbf{A}}}^{(0)}\mathbf{X}{\mathbf{W}}_1\right)$$ \mathbf Z^{(0)} = \text{relu}\left(\tilde{\mathbf A}^{(0)} \mathbf X \mathbf W_1\right) $ 。

     • 计算预测损失：${\mathcal{L}}_{\text{pred}}^{(0)}=\mathcal{l}(\text{output}\left({\tilde{\mathbf{A}}}^{(0)}{\mathbf{Z}}^{(0)}{\mathbf{W}}_2\right),\mathbf{Y})$$ \mathcal L_{\text{pred}}^{(0)} = \mathcal l\left(\text{output}\left(\tilde{\mathbf A }^{(0)} \mathbf Z^{(0)} \mathbf W_2\right), \mathbf Y \right) $ 。

     • 计算图正则化损失：${\mathcal{L}}_{\mathcal{G}}^{(0)}=\alpha \mathrm{\Omega }({\mathbf{A}}^{(0)},\mathbf{X})+f({\mathbf{A}}^{(0)})$$ \mathcal L_ \mathcal G^{(0)} = \alpha \Omega(\mathbf A^{(0)}, \mathbf X) + f(\mathbf A^{(0)}) $ 。

     • 计算联合损失：${\mathcal{L}}^{(0)}\leftarrow {\mathcal{L}}_{\text{pred}}^{(0)}+{\mathcal{L}}_{\mathcal{G}}^{(0)}$$ \mathcal L^{(0)}\leftarrow \mathcal L^{(0)}_{\text{pred}} + \mathcal L_\mathcal G^{(0)} $ 。

     • $t\leftarrow 0$$ t\leftarrow 0 $ 。

     • 迭代，停止条件为：$t>0$$ t \gt 0 $ 且${\Vert {\mathbf{A}}^{(t)}-{\mathbf{A}}^{(t-1)}\Vert }_F^2\le \delta {\Vert {\mathbf{A}}^{(0)}\Vert }_F^2$$ \left\|\mathbf A^{(t)} - \mathbf A^{(t-1)}\right\|_F^2 \le \delta \left\|\mathbf A^{(0)}\right\|_F^2 $ ，或者$t\ge T$$ t \ge T $ 。迭代步骤：

       • $t\leftarrow t+1$$ t\leftarrow t+1 $ 。

       • 基于${\mathbf{Z}}^{(t-1)}$$ \mathbf{ Z}^{(t-1)} $ 学习度量矩阵$\mathbf{S}$$ \mathbf S $ 。

         基于 multi-head 余弦相似度来计算。

       • 根据度量学习矩阵$\mathbf{S}$$ \mathbf S $ 计算${\mathbf{A}}^{(t)}$$ \mathbf A^{(t)} $ ，根据${\mathbf{A}}_0$$ \mathbf{ A}_0 $ 和${\mathbf{A}}^{(t)}$$ \mathbf A^{(t)} $ 计算${\tilde{\mathbf{A}}}^{(t)}$$ \tilde{\mathbf A}^{(t)} $ 。

       • 计算${\overline{\mathbf{A}}}^{(t)}=\eta {\tilde{\mathbf{A}}}^{(t)}+(1-\eta ){\tilde{\mathbf{A}}}^{(0)}$$ \bar{\mathbf A}^{(t)} = \eta\tilde{\mathbf A}^{(t)} + (1-\eta)\tilde{\mathbf A}^{(0)} $ 。

       • 计算节点 embedding ：${\mathbf{Z}}^{(t)}=\text{relu}\left({\overline{\mathbf{A}}}^{(t)}\mathbf{X}{\mathbf{W}}_1\right)$$ \mathbf Z^{(t)} = \text{relu}\left(\bar{\mathbf A}^{(t)} \mathbf X \mathbf W_1\right) $ 。

       • 计算预测损失：${\mathcal{L}}_{\text{pred}}^{(t)}=\mathcal{l}(\text{output}\left({\overline{\mathbf{A}}}^{(t)}{\mathbf{Z}}^{(t)}{\mathbf{W}}_2\right),\mathbf{Y})$$ \mathcal L_{\text{pred}}^{(t)} = \mathcal l\left(\text{output}\left(\bar{\mathbf A }^{(t)} \mathbf Z^{(t)} \mathbf W_2\right), \mathbf Y \right) $ 。

       • 计算图正则化损失：${\mathcal{L}}_{\mathcal{G}}^{(t)}=\alpha \mathrm{\Omega }({\mathbf{A}}^{(t)},\mathbf{X})+f({\mathbf{A}}^{(t)})$$ \mathcal L_ \mathcal G^{(t)} = \alpha \Omega(\mathbf A^{(t)}, \mathbf X) + f(\mathbf A^{(t)}) $ 。

       • 计算联合损失：${\mathcal{L}}^{(t)}\leftarrow {\mathcal{L}}_{\text{pred}}^{(t)}+{\mathcal{L}}_{\mathcal{G}}^{(t)}$$ \mathcal L^{(t)}\leftarrow \mathcal L^{(t)}_{\text{pred}} + \mathcal L_\mathcal G^{(t)} $ 。

     • 总的损失为：$\mathcal{L}\leftarrow {\mathcal{L}}^{(t)}+\sum _{i=1}^t{\mathcal{L}}^{(0)}/t$$ \mathcal L\leftarrow \mathcal L^{(t)} + \sum_{i=1}^t \mathcal L^{(0)} /t $

     • 如果为训练截断，则反向传播$\mathcal{L}$$ \mathcal L $ 的梯度来更新模型参数$\mathrm{\Theta }$$ \Theta $ 。

3. 从上述算法可以看到：

   • 算法使用更新后的节点 embedding${\mathbf{Z}}^{(t-1)}$$ \mathbf Z^{(t-1)} $ 来调整邻接矩阵${\tilde{\mathbf{A}}}^{(t)}$$ \tilde{\mathbf A}^{(t)} $ ，同时使用更新后的邻接矩阵${\tilde{\mathbf{A}}}^{(t)}$$ \tilde{\mathbf A}^{(t)} $ 来 调整节点 embedding${\mathbf{Z}}^{(t)}$$ \mathbf Z^{(t)} $ 。

     这个迭代过程动态停止，直到学到的邻接矩阵以指定的阈值收敛，或者最大迭代步$T$$ T $ 被达到。

   • 采用动态的阈值收敛相比固定的迭代步，在 mini-batch 训练时优势更为明显：我们可以使得mini-batch 中每个样本图exaple graph 动态停止（每个样本表示一个图）。

   • 在所有迭代之后，总的损失将通过所有之前的迭代进行反向传播，从而更新模型参数。

20.1.4 理论分析

1. 收敛性分析：理论上证明迭代式学习过程的收敛性是一个挑战，因为所涉及的学习模的任意复杂性，这里我们从概念上理解它为何在实践中有效。下图给出了迭代式学习过程中，学到的邻接矩阵$\mathbf{A}$$ \mathbf A $ 和中间 embedding$\mathbf{Z}$$ \mathbf Z $ 的信息流。为简单起见，我们省略了一些其它变量，如$\tilde{\mathbf{A}},\overline{\mathbf{A}}$$ \tilde{\mathbf A}, \bar{\mathbf A} $ 。

   可以看到：在第$t$$ t $ 次迭代中，${\mathbf{A}}^{(t)}$$ \mathbf A^{(t)} $ 是基于${\mathbf{Z}}^{(t-1)}$$ \mathbf Z^{(t-1)} $ 来计算、${\mathbf{Z}}^{(t)}$$ \mathbf Z^{(t)} $ 是基于${\tilde{\mathbf{A}}}^{(t)}$$ \tilde{\mathbf A}^{(t)} $ 来计算，而${\tilde{\mathbf{A}}}^{(t)}$$ \tilde{\mathbf A}^{(t)} $ 又基于${\mathbf{A}}^{(t)}$$ \mathbf A^{(t)} $ 来计算。

   进一步地，我们用${\delta }_{\mathbf{A}}^{(t)}$$ \delta_\mathbf A^{(t)} $ 来表示${\mathbf{A}}^{(t)}$$ \mathbf A^{(t)} $ 和${\mathbf{A}}^{(t-1)}$$ \mathbf A^{(t-1)} $ 之间的差异，用${\delta }_{\mathbf{Z}}^{(t)}$$ \delta_\mathbf Z^{(t)} $ 来表示${\mathbf{Z}}^{(t)}$$ \mathbf Z^{(t)} $ 和${\mathbf{Z}}^{(t-1)}$$ \mathbf Z^{(t-1)} $ 之间的差异。

   • 如果我们假设有${\delta }_{\mathbf{Z}}^{(1)}<{\delta }_{\mathbf{Z}}^{(0)}$$ \delta_\mathbf Z^{(1)}\lt \delta_\mathbf Z^{(0)} $ ，那么我们可以预期${\delta }_{\mathbf{A}}^{(2)}<{\delta }_{\mathbf{A}}^{(1)}$$ \delta_\mathbf A^{(2)} \lt \delta_\mathbf A^{(1)} $ 。因为假设模型参数在迭代过程中保持不变，则从概念上讲，更相似的 node embedding 矩阵（即更小的${\delta }_{\mathbf{Z}}$$ \delta_\mathbf Z $ ），将会产生更相似的邻接矩阵（即更小的${\delta }_{\mathbf{A}}$$ \delta_\mathbf A $ ） 。
   • 同样地，如果我们假设有${\delta }_{\mathbf{A}}^{(2)}<{\delta }_{\mathbf{A}}^{(1)}$$ \delta_\mathbf A^{(2)} \lt \delta_\mathbf A^{(1)} $ ，我们可以预期${\delta }_{\mathbf{Z}}^{(2)}<{\delta }_{\mathbf{Z}}^{(1)}$$ \delta_\mathbf Z^{(2)}\lt \delta_\mathbf Z^{(1)} $ 。

   根据这一推理链条，我们可以轻松地扩展到后续的迭代。

   现在讨论为什么在实践过程中${\delta }_{\mathbf{Z}}^{(1)}<{\delta }_{\mathbf{Z}}^{(0)}$$ \delta_\mathbf Z^{(1)}\lt \delta_\mathbf Z^{(0)} $ 成立。我们需要回顾一个事实，即${\delta }_{\mathbf{Z}}^{(0)}$$ \delta_{\mathbf Z}^{(0)} $ 衡量了${\mathbf{Z}}^{(0)}$$ \mathbf Z^{(0)} $ 和$\mathbf{X}$$ \mathbf X $ 之间的差异，这通常大于${\mathbf{Z}}^{(1)}$$ \mathbf Z^{(1)} $ 和${\mathbf{Z}}^{(0)}$$ \mathbf Z^{(0)} $ 之间的差异，即${\delta }_{\mathbf{Z}}^{(1)}$$ \delta_\mathbf Z^{(1)} $ 。

   我们将在实验部分经验性地检验迭代式学习过程的收敛性。

   

2. 模型复杂度：

   • 学习一个邻接矩阵的算法复杂度为$O(n^{2}h)$$ O(n^2h) $ ，其中$n$$ n $ 为节点数量，$h$$ h $ 为 embedding 维度。
   • 计算节点 embedding 矩阵的算法复杂度为$O(n^{2}d+ndh)$$ O(n^2d+ ndh) $ ，$d$$ d $ 为输入特征维度。
   • 计算输出的算法复杂度为$O(n^{2}h)$$ O(n^2h) $ 。
   • 计算总的损失函数的代价为$O(n^{2}d)$$ O(n^2d) $ 。

   假设迭代式图学习的迭代次数为$T$$ T $ ，则总的复杂度为：$O(Tn(nh+nd+hd))$$ O(Tn(nh + nd + hd)) $ 。假设有$d\simeq h$$ d\simeq h $ ，且$n\gg d$$ n\gg d $ ，则总的复杂度为$O(Td{n}^2)$$ O(Tdn^2) $ 。

20.2 实验

1. 这里我们进行一系列实验，从而验证DIAL-GNN 框架的有效性，并评估不同部分的影响。

2. 数据集：

   • 图数据集：Cora 和 Citeseer 是评估图学习算法的两个常用的基准数据集，输入的特征是 bag-of-word ，任务是节点分类。在这两个数据集中，图结构可用。
   • 非图数据集：Wine, Breast Cancel, Digits 是三个非图数据集，任务是节点分类。在这些数据集中没有图结构。
   • inductive learning 数据集：为了证明IDAL-GNN 在 inductive learning 任务上的有效性，我们分别对 20Newsgroups 数据集（20News）、movie review 数据集（MRD）进行文档分类和回归任务。我们将每个文档视为一个图，其中文档中的每个单词作为图的节点。

   对于 Cora,Citeseer，我们遵循之前工作的实验配置（GCN, GAT, LDS-GNN ）。对于 Wine, Cancer, Digits ，我们遵循LDS-GNN 的实验配置；对于 20News，我们从训练数据中随机选择 30% 样本作为验证集；对于 MRD，我们使用 60%:20%:20% 的比例将数据集拆分为训练集、验证集、测试集。

   所有实验都是采用不同的随机数种子执行 5 次的均值。

   

3. baseline 方法：

   • 在 transductive learning 中的 baseline 为 LDS-GNN。与我们的工作类似，LDS-GNN 也是共同学习图结构和 GNN 参数，但是 LDS-GNN 无法应用于 inductive-learning 。因为它旨在直接优化底层图的边上的离散概率分布，这使得它无法在测试阶段处理 unseen 的节点或图。

     LDS-GNN 论文给出了几种半监督baseline 的实验结果，这里我们直接复制结果到这里，而并没有花时间重跑这些 baseline 。

   • 对于 Cora,Cteseer 数据集，我们还将 GCN, GAT 作为 baseline。

     为评估 DIAL-GNN 在带噪音的图上的鲁棒性，我们还将 DIAL-GNN, GCN 在添加额外噪声的边、或删除已有的边的图上进行比较。

   • 对于非图数据集，我们给出了一个 kNN-GCN 作为 baseline，其中先在数据集上构建 kNN 近邻图，然后对这个图应用 GCN。

   • 对于 inductive learning，我们将 DIAL-GNN 和 BiLSTM, kNN-GCN 进行比较。

4. 实验配置：

   • 在我们所有实验中（拷贝的实验除外），除了输出层之外，我们在GCN 最后一层卷积层之后、输出层之前应用 dropout rate = 0.5 的 dropout 。

   • 在迭代式学习过程中，除了 Citeseer（无 dropout）、Digits（dropout rate = 0.3），我们也在 GCN 中间的卷积层应用 dropout rate = 0.5 的 dropout 。

   • 对于文本数据集，我们选择数据集中词频超过10 次的单词，并训练了一个 300 维的 GloVe 向量。

     对于长文本，为提高效率我们将文本长度限制为最大 1000 个单词。

     在word embedding 层和 BiLSTM 层之后，我们使用 dropout rate = 0.5 的 dropout 。

   • 我们使用 Adam 优化器，batch size = 16。

   • 对于 20News ，隐层维度为 128；对于 MRD，隐层维度为 64 。对于其它benchmark，隐层维度为 16 。

   • 对于 text benchmark，我们将学习率设为0.001 ；所有其它benchmark ，学习率为 0.01，并应用$L_2$$ L_2 $ 正则化，使用系数为 0.0005 的权重衰减。

   下图给出了benchmark 上 DIAL-GNN 相关的超参数。所有超参数都在验证集上进行了优化：

   

5. 在transductive learning 和 inductive learning 上的实验结果如下所示。其中上图为 transductive learning，评估指标为测试准确率accuracy（+- 标准差）；下图为 inductive learning，评估指标分别为测试准确率（分类问题）和测试 R2 score （回归问题） ，括号内为+- 标准差。

   结论：

   • DIAL-GNN 在 7 个 benchmark 中有6 个优于所有的 baseline 方法，这证明了 DIAL-GNN 的有效性。
   • 即使图结构可用，DIAL-GNN 也可以极大地帮助完成节点分类任务。
   • 当图结构不可用时，和 kNN-GCN 相比，DIAL-GNN 在所有数据集上始终获得更好的结果。这表明联合学习图结构和GNN 的强大能力。
   • 和 LDS 相比，DIAL-GNN 在 5 个 benchmark 上的 4 个获得了更好的性能。
   • 20News 和 MRD 上的良好表现证明了 DIAL-GNN 在 inductive learning 中的能力。

   

   

6. 我们进行消融实验从而评估DIAL-GNN 框架不同部分的影响，评估指标为测试集accuracy（+- 标准差）。其中 w/o 表示 without 。

   结论：

   • 关闭迭代式学习（w/o IL），所有数据集的性能持续下降。这证明了迭代式学习对于图结构学习问题的有效性。
   • 关闭图正则化（w/o graph reg.），所有数据集的性能也在持续下降。这证明了结合图正则化损失共同训练模型的好处。

   

7. 为评估 DIAL-GNN 在噪音图上的鲁棒性，我们对于Cora 数据集构建了随机添加边、随机删除边的图。具体而言，我们随机删除原始图中 25%, 50%, 75% 的边（上图），或者随机添加原始图中 25%, 50%, 75% 的边（下图）。评估指标为测试集accuracy（+- 标准差）。

   结论：

   • 在所有的情况下，DIAL-GNN 都比 GCN 获得更好的结果，并且对带噪音的图更鲁棒。
   • GCN 在添加噪音边的场景下完全失败，但是 DIAL-GNN 仍然能够合理地执行。我们猜测是因为等式$\tilde{\mathbf{A}}=\lambda {\mathbf{L}}_0+(1-\lambda )\left({\mathbf{D}}^{-1/2}\mathbf{A}{\mathbf{D}}^{-1/2}\right)$$ \tilde{\mathbf A} = \lambda \mathbf L_0 + (1-\lambda)\left(\mathbf D^{-1/2}\mathbf A\mathbf D^{-1/2}\right) $ 以跳跃连接的形式来表示。通过降低$\lambda$$ \lambda $ 的取值，我们强迫模型减少对包含过多加性随机噪音的初始图的依赖。

   

   

8. 我们通过测试阶段的迭代式学习过程中的迭代，展示了迭代式学习学到的邻接矩阵的演变，以及模型测试 accuracy 的演变。

   我们将迭代式学习过程中相邻矩阵之间的差定义为：

   $${\delta }_{\mathbf{A}}^{(t)}=\frac{{\Vert {\mathbf{A}}^{(t)}-{\mathbf{A}}^{(t-1)}\Vert }_F^2}{{\Vert {\mathbf{A}}^{(t)}\Vert }_F^2}$$

   其典型取值范围是 0~1 。

   结论：邻接矩阵和accuracy 都通过迭代快速收敛，这从经验上验证了我们对迭代式学习过程的收敛性做出的分析。

   

9. DIAL-GNN 迭代式学习方法的停止策略有两种：迭代固定数量的迭代步之后停止、应用某些停止条件从而动态停止。下图我们比较了两种策略的有效性，其中蓝线表示使用固定数量的迭代次数，红线表示使用动态停止条件。评估指标为 Cora 数据集的测试集上的平均accuracy。

   结论：使用停止条件从而动态停止的效果更好。

   

10. 最后，我们在各种 benchmark 中比较了 DIAL-GNN, LDS 以及其它经典GNN（如 GCN, GAT）的训练效率。

    所有实验均在 Intel i7-2700K CPU, NVIDIA Titan XP GPU 和 16GB RAM 的同一台机器上运行，并使用不同随机数种子重复执行5 次。结果见下表（单位秒）。

    结论：

    • DIAL-GNN 和 LDS 都要比 GCN,GAT 更慢。这是可以预期的，因为 GCN 和 GAT 不需要同时学习图结构。
    • DIAL-GNN 始终比 LDS 更快，但总体而言它们是差不多的水平。
    • 通过移除迭代式学习（DIAL-GNN w/o IL） 可以发现，迭代式学习的部分是 DIAL-GNN 中最耗时的。