IJCAI 2022 | 图结构学习最新综述：研究进展与未来展望

©作者 | Dream

单位 | 浙江大学

研究方向 | 图表示学习

论文标题：

A Survey on Graph Structure Learning: Progress and Opportunities

论文链接：

https://arxiv.org/pdf/2103.03036.pdf

在现实世界中存在大量的图结构数据，图神经网络已成为分析这些数据的标准范式，GNN 对图结构有较高的敏感性，不同的图结构得到的表征会很不一样。但是往往图数据中存在较多的噪声者图的不完整性都会使得 GNN 习得的表征较差，这不利于下游任务。

为了得到更好的图结构，现在有很多方法联合优化训练图结构以及图表征，这些方法统称为图结构学习（Graph Structure Learning）。在这篇综述中，总结了最近的图结构学习的方法，指出了现有的问题和对未来的展望。

该论文的组织结构如下：

在介绍图结构学习之前，我们得先对一些名词进行区分：

Please kindly note that GSL, although conceptually related, is fundamentally distinct to related problems such as graph generation that target at generating novel, diversified graphs [Du et al., 2021], or graph learning that aims to recover the Laplacian matrix of a homophilous graph corresponding to given node features.

图结构学习的流程如下图所示，这些图结构学习的方法的输入往往是带有节点特征的图（图的拓扑结构不一定会提供），通过结构建模模块不断地优化图结构，利用优化的图结构进行消息传递生成节点表征，用于下游任务，然后不断迭代更新图结构以及节点表征。

Graph construction：如果数据集没有给定图结构，或者图结构是不完整的，我们会构建一个初始的图结构，构建方法主要由两种：（1）KNN 构图，（2）阈值构图。

Graph structure modeling 是图结构学习的核心模块，不断改善图结构，现有的方法可以分类为：

1. Metric-based approaches: 利用一些度量函数（将节点对表征作为输入）来获得节点对的边权。
   
2. Neural approaches：给定节点表征，利用神经网络推理边权。
   

3. Direct approaches：将邻接矩阵看作是自由学习矩阵，通过 GNN 的参数来优化它们。
   

我们希望得到的图满足一些性质，因此在介绍这些方法之前，先回顾一下三种图正则化（规范化）方法：

1. S parsity： 考虑到现实世界的图一般都是稀疏的，我们会要求得到的邻接矩阵是比较稀疏的，直观地，我们可以利用 L0 norm： ，但是 L0 norm 是一个非凸问题（同时也是 NP-hard），通常我们会求其近似解 L1 norm，或者利用 continuous relaxation 进行求解。

2. Smoothness： 通常，我们会假设邻接节点的信号变化是平缓的，为了实现这一目的，通常最小化下面的式子：

通常带 进行联合优化。

3. Community Preservation： 不同拓扑结构的聚类更倾向于不同的标签，跨多个社区的边可以看作是噪声，邻接矩阵的秩和连通分量的数量有关，可以对邻接矩阵进行低秩约束： 。但是 rank 函数是离散的，无法进行直接优化。我们会使用 nuclear norm，也就是奇异值的和。

Structure Learnig

下面详细介绍Graph Structure Modeling：

1.1 Metric-based Approaches

这类方法会使用一些核函数用来计算节点对的相似度，并作为边权。常使用的核函数有（1）高斯核函数，（2）内积，（3）余弦相似度，（4）扩散核函数，(5) 结合多种核函数。

1.2 Neural Approaches

和 metric-based 的方法不同，这类方法会使用神经网络来预测边权。除了使用简单的神经网络，还有许多工作利用 attention 来建模边权。最近有一些利用 transformer 的工作，它们和之前 GNN 的架构不一样，之前的方法都只考虑一阶邻接，然后通过堆叠实现多跳，但是 transformer 将所有的节点都视为邻居，将结构信息编码进 graph transformer，通过 attention 给边赋权，由于图数据的特殊性，位置和结构编码十分关键。

1.3 Direct Approaches

Direct approaches 将目标图的邻接矩阵作为学习的自由变量。由于不依赖于节点表示对边进行建模，direct approaches 具有更大的灵活性，但在学习矩阵参数方面会更困难。

这类方法大都使用上面提到的正则器来优化邻接矩阵。比如 GLNN 会随机初始化一个邻接矩阵，然后给这个邻接矩阵施加一些正则作为辅助 loss，利用这个邻接矩阵进行下游任务（比如节点分类），结合下游任务的 loss 以及正则项 loss 共同来优化邻接矩阵。

还有一些 direct approaches 通过概率的方法来建模邻接矩阵，假设图结构是从某个分布中抽样得到的。LDS-GNN 通过从 learnable 伯努利分布中进行采样对边进行建模，etc.

Postprocessing Graph Structures

2.1 离散采样

从一个离散分布中采样是不可微的，我们可以利用重参数化技巧，允许梯度通过抽样操作反向传播。比较常用的是 Gumbel-Softmax，除此之外，还有 Gumbel-Max，hard concrete sampling, etc

2.2 Residual Connections

如果提供了初始的图结构（初始图结构不一定是邻接矩阵，也可以是其他形式的，比如拉普拉斯矩阵），这些结构通常会提供一些先验信息，我们可以假设优化得到的图结构是和初始结构是比较相近的，基于这一假设，一些工作利用残差连接的方式将初始图结构整合进来，这样可以加速并稳定训练。

公式化如下：

残差连接形式：

h()也可以选择其他形式。

挑战和未来展望

不止同质图：现有的方法主要聚焦在同质图的结构生成，异质图的结构生成还是under exploration。

不止同配图：现有的方法大都在同配性假设下做的，然后在现实生活中存在大量异配图，比如化学分子图。设计不同的学习策略来学习异质图结构方面还有很大的发展空间。

在缺少 rich attributes 的时候如何学习图结构：在推荐系统中于经常遇到这类问题，节点的表征可能只有不具语义信息的id，我们如何在这样的数据集下学习到比较好的图结构。

缺少可扩展性：现在的大部分工作涉及到大量的 pairwise similarity 的计算，这会限制在大图上的使用。

任务无关的结构学习：现有的工作绝大多数都需要任务相关的监督信号进行训练。但是在现实生活中，收集高质量的标签往往是耗时的，而有限的监督会恶化学习到的图结构的质量。最近有一些自监督的工作在解决这类问题，在无标签的情况下，也能学到比较好的图结构。

总结

在这篇论文中，我们回顾了现有的一些图结构学习方法。我们首先阐述了 GSL 的概念，并制定了一个通用的 pipeline。然后，我们将最近的工作分为三组：metric-based approaches、neural approaches 和 direct approaches。我们总结了每种类型的关键特性，并讨论了常见的结构建模技术。此外，我们还讨论了 GSL 在不同领域的应用。最后，我们概述了当前研究面临的挑战，并指出了进一步研究的方向。我们希望这篇综述能够帮助我们扩大对 GSL 的理解，并指导 GSL 算法的未来发展。