改善图神经网络的鲁棒性，图结构学习最新进展如何？
论文：Deep Graph Structure Learning for Robust Representations: A Survey
作者：Yanqiao Zhu, Weizhi Xu, Jinghao Zhang et al.
图神经网络（GNNs, Graph Neural Networks）作为一种强大的工具，被广泛用于分析图结构数据。无论是在节点分类、链接预测，还是推荐系统和信息检索等，GNNs 都在跨领域的图分析任务上取得了巨大的成功。
目前大多数 GNNs 方法对图结构的质量高度敏感，通常需要一个完美的图结构来学习信息嵌入，以提高 GNN 模型的鲁棒性。
众所周知，深度神经网络容易受到噪声的干扰；甚至噪声还加剧了深度 GNN 模型所产生的表示质量，这无疑对将 GNN 应用到真实世界的愿景提出了极大的挑战，尤其是在某些风险较大、关键紧急的场景中，如医学分析（medical analysis）。
原因在于，GNNs 通过递归地聚合邻区信息来计算节点嵌入，在这种迭代机制下，很容易引发级联效应（cascading effects）。也就是说，图中的小噪声会传播到邻居节点，从而影响许多其他节点的嵌入。
以社交网络为例，其中，节点对应于用户，边代表朋友关系。一旦欺诈账户与真实账户建立虚假链接，很容易将错误信息注入到整个网络中，从而导致账户的可信度变得难以估量。
此外，最近有研究表明，图结构中不明显的、故意的扰动（又称为对抗攻击）很容易引起错误的预测。由此可见，一种用于学习信息表示的完美图结构对弥补 GNN 模型的缺陷，提高其鲁棒性来说是至关重要的。
改善 GNN 模型的鲁棒性关键点之一在于，产生用于学习表示的去噪图结构。
为了解决上述问题，许多研究围绕图结构学习（GSL, Graph Structure Learning）这一中心概念展开，旨在共同学习优化的图结构及其相应的表示形式。不幸的是，这些 GSL 技术已在不同的研究社区中被提及，但从未得到系统的审查。
近期发表的最新图结构学习综述文章 Deep Graph Structure Learning for Robust Representations: A Survey，旨在弥补这一空白：作者 Yanqiao Zhu、Weizhi Xu 和 Jinghao Zhang 等人广泛调查了 GSL 方法在学习鲁棒表示中的最新进展并给出了系统的报告：文章首先是制定 GSL 的一般范式，然后回顾按图结构建模方式分类的最新方法，根据现有工作对图结构进行建模的方式对其进行分类，并突出显示每个模型的关键优点；
其次，团队讨论了将 GSL 理念纳入其他图形任务的应用程序，如可解释性（Explainability）和图池化（Graph pooling）；最后，团队指出了当前研究中的一些问题，并讨论了未来的研究方向。
据目前所知，这是第一篇对 GSL 研究的最新进展进行全面综述的可靠文献。
GSL 的一般范式
假设用
为边集。节点特征矩阵表示为
本文主要关注修改边集来细化图结构的工作，包括添加新边、删除现有边和更改边权值（edge weights）。
考虑到目前大多数深度 GSL 工作都可看作是在学习图表示的现成 GNN 模型之上的插件模块，因此，本研究采用了一个一般范式来表征之前的研究，该范式包含三部分：结构建模（structure modeling）、消息传播（message propagation）和学习目标（learning objectives）。
下面便对这三部分展开详述：
丨结构建模：GSL 的核心是一个编码函数，可以对最优图结构 以边权值的表示形式进行建模。此外，该编码函数可以通过两两之间的距离或可学习的参数来定义边权值。在这项工作中，团队将现有的研究分为以下三类：
1) 度量学习方法，其中边权值来自于学习两两表示之间的度量函数；
2) 概率建模方法，该方法假设图是从某些分布中经过采样过程产生的，并使用可学习的参数对采样边的概率进行建模；
3) 直接优化方法，在原始邻接矩阵的基础上，结合各种图的先验对图结构进行优化。
这三组方法还可以借助可学习参数来表征，如表 1 所示。此外，一些研究考虑了额外的不可学习的后处理步骤，如硬阈值（hard thresholding），以进一步对建模的图结构进行规范化。
丨信息传播：在获得优化的图结构 之后，节点特性将会传播到改进后的邻域。使用 GNN 模型，每个节点聚合来自邻近节点的信息，并产生一个嵌入表示 。值得注意的是，由于优化图结构是个比较艰巨的任务，许多方法便采用结构建模和消息传播的迭代方式，直到满足多个停止条件为止。
丨学习目标：为了用改进的图结构训练模型，现有的工作通常定义了如下所示的包含两部分的学习目标：
公式中的第一部分
算法分类
在这部分中，团队成员将现有的工作分为三类，并对每一类的代表性 GSL 方法进行仔细检查，并且详细说明了这些工作是如何适合上述范式的。
直观地说，两个节点之间的边权值可以表示为两个端点之间的距离度量。度量学习方法通过学习一对表示的度量函数
在此类方法中，常用的更新函数有两种：插值（interpolation）和注意组合（attentive combination）。其中，前者结合了原结构 和学习的邻接矩阵
而后者采用一种通道注意机制来融合两个结构，其中 往往在多层感知器（MLPs）中实现。
另外，由于密集图不仅会带来繁重的计算负担，而且还可能包含噪声，许多方法都采用了稀疏正则化方法。因此，通常会根据边权值对边进行剪枝，作为一项后处理操作，其结果要么是 图（即每个节点最多有 个邻居节点），要么是一个
总的来说，此类方法主要在函数 和 的实际实现以及后处理步骤上有所不同。根据对 的不同认识，研究团队进一步将其分为两类方法：基于内核的方法和基于注意力的方法。表 2 总结了这些不同的度量学习方法。
基于内核的方法多采用传统的核函数作为度量 ，来建模两个节点之间的边权值。此类方法主要有：
丨 AGCN：首先计算潜在空间中每对节点之间的广义马氏距离（Mahalanobis distance）；然后使用给定距离的高斯核来建模边权值。
丨 PG-LEARN：通过利用高斯核来测量节点之间的相似性，对点云数据（point-cloud data）采用了与 AGCN 类似的方法，此外还引入了正则化器以确保特征平滑。
丨 GRCN 和 GAUGM 模型：这两种方法的边权值是通过不引入附加参数的两端节点的嵌入内积来建模的。
丨 GNN-Guard 和 AMGCN：这两种方法则是利用余弦相似度对边权值进行建模。
丨 Grale：为增强其表达力，模型融合了不同的潜在弱相似性度量，以学习信息丰富且特定于任务的图；同时，还利用了局部敏感哈希算法（LSH, Locality Sensitive Hashing）来增强可扩展性，以处理数十亿节点数据集。
基于注意力的方法通常利用注意网络或更复杂的神经网络来捕获节点之间的交互，并在此基础上生成新的图拓扑结构。
值得一提的是，尽管图注意力网络（GAT, Graph Attention Networks）未明确学习新的图结构，但它通过简单的注意网络学习边权值，可将其看作此方法中的一个特例。GAT 可以为一跳邻居分配不同的权重，而且不会在图中创建新的链接。以下为此类方法中比较有代表性的模型：
丨 GLCN：用一个单层神经网络来表示两个节点之间的成对关系。
丨 DGL：通过多头自我注意网络（Multi-head Self-attention Network）构建图，该网络具有一定的归纳能力，在添加新节点时无需再重新训练。具体来说，它利用加权余弦相似度作为每个 head 的度量标准，并将所有的注意力得分求和，以计算最终的边权值。
丨 HGSL：将 GSL 的思想扩展到了异构图。它首先通过像 IDGL 这样的多头注意力机制为每种边的类型设计了特征相似图；然后构造两个特征传播图，并将这两个图与原始图进行融合；
丨 GPNL 和 SLAPS：除了上述简单的注意力网络之外，这两种代表性的方法使用了更复杂的神经网络来参数化度量函数。其中，GPNL 使用具备非线性激活函数的 MLP 来获得边权值；SLAPS 则引入了一种新颖的自监督辅助任务来改善结构学习，该任务掩盖了某些输入特征（或添加噪声），并训练一个单独的去噪图自编码器（GAE, Graph AutoEncoder），以通过学习结构恢复掩盖的特征。这项辅助任务持有的假设是，适合预测节点特征的图结构也应该有利于预测节点标签。
区别于度量学习方法，概率建模方法并没有以这种确定性的方式修改图结构，而是假设图是通过对特定分布的采样过程生成的，并使用可学习参数对采样边的概率进行建模。考虑到图结构通常以离散矩阵的形式表示，而从离散分布中采样是不可微的。
因此，该方法的主要障碍是如何使这些采样操作可微，并使用传统梯度下降法进行优化。
受变分方法（variational method）的启发，大部分的研究采用在采样过程中借助反向传播以更新参数的技巧。相关代表性的工作如下：
丨 LDS-GNN：通过从具有可学习参数的伯努利分布（Bernoulli distribution）采样，并将 GSL 架构看作一个双层规划问题，对每对节点之间的边进行建模，提出了一种使用超梯度估计来逼近所提出的双层问题的实用算法。
丨 NeuralSparse：通过去除与任务无关的边来考虑图稀疏化任务，此方法利用深度神经网络对稀疏过程进行参数化，然后从类分布中为节点选择一个邻居。
丨 PTDNet：该方法放宽了 kNN 约束，通过对学习到的图结构施加稀疏性和低秩约束来优化稀疏化过程。
丨 GIB：该方法将 GAT 的注意力权重作为类分布或伯努利分布的参数，对利用 Gumbel-Softmax 重新参数化技巧的图结构进行采样。
丨 DGM：利用 Gumbel-Top-k 技巧从高斯核定义的概率分布中采样边，并利用强化学习，奖励参与正确分类的边，并惩罚导致错误分类的边。
丨 DenNE：与上述只考虑原始图分布的方法不同，该方法显式地在图结构上建模噪声，提出了一个带有图生成器的生成模型。
丨 BGCN：该方法提出了一种贝叶斯方法，将现有的图视为随机图的参数族样本。
丨 vGCN：依旧从贝叶斯的角度出发制定 GSL，考虑了先验伯努利分布和基于 GNN 的可能性。
最后的一组方法是将图邻接矩阵视为可学习参数，将其与 GNN 参数一起进行直接优化。图先验和优化算法是这些直接优化方法的核心。为了获得合理的图结构，该方法提出了各种图先验来对邻接矩阵进行正则化。需要注意，由于此类方法直接优化邻接矩阵，
所以，它们本质上具有转导性，无法泛化到具带有看不见节点的图上。表 3 给出了直接优化方法的总结。
丨 GCN-GT：考虑利用给定的类标签的同时，改进网络拓扑结构并学习 GNN 参数。
丨GLNN：将初始图结构、稀疏性和特征平滑性融合到混合目标中。
丨 ProGNN：该方法包含了低秩先验，该先验使用核范数
丨 GSML：该方法将 GSL 定义为一个双层优化问题，并使用元梯度（metagradients）来解决双层优化问题，其中内环代表分类，外环代表结构学习。
获得鲁棒的表示之外，还有其他改善
GSL 除了获得鲁棒的表示外，还使 GNN 模型在其他方面受益，许多基于图的模型承认了不完美的图结构，同时也固有地考虑了结构学习的问题。
在这篇文章中，作者回顾了与此相关的一些最新研究，这些研究的共性就是在其他的研究中结合了 GSL 的思想。比如说，GNN 设计中存在的过度平滑和通用性问题引起了广泛的研究兴趣，其中一些建议与 GSL 有着共同的思想。举几个最新研究工作：
丨 DropEdge：在训练过程中随机去除一部分边来以缓解过平滑问题；
丨 AdaEdge：此方法首先提出了一种 Mean Average Distance 的度量，该度量通过计算节点表示之间的平均距离来测量图的平滑度；然后，将其作为正则化器添加到训练目标中，以选择在每次迭代时删除哪些边。
丨 GRAND：根据预定义的分布多次删除节点，以获得多个扩充图；然后，鼓励这些图上传播的特征保持一致，从而得到最终的鲁棒表示。
综上所述，在这篇论文中，研究团队广泛地梳理了 GSL 在学习鲁棒表示方面的工作，但也需要强调，GSL 的发展虽然取得了令人欣喜的进展，但仍处于起步阶段，还有许多挑战有待解决。
目前研究中存在的一些关键问题和未来的研究方向主要有以下几个方向：
1) 设计不同的策略以加强异构图结构方面的学习；
2) 实现在缺乏属性特征时学习合理的图结构；
3) 提高 GSL 方法的可扩展性；
4) 探索与任务无关的结构学习。
Refenrence：
https://arxiv.org/abs/2103.03036
往期推荐