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. Sparsity：考虑到现实世界的图一般都是稀疏的，我们会要求得到的邻接矩阵是比较稀疏的，直观地，我们可以利用 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 算法的未来发展。

更多阅读

#投 稿 通 道#

 让你的文字被更多人看到 

如何才能让更多的优质内容以更短路径到达读者群体，缩短读者寻找优质内容的成本呢？答案就是：你不认识的人。

总有一些你不认识的人，知道你想知道的东西。PaperWeekly 或许可以成为一座桥梁，促使不同背景、不同方向的学者和学术灵感相互碰撞，迸发出更多的可能性。 

PaperWeekly 鼓励高校实验室或个人，在我们的平台上分享各类优质内容，可以是最新论文解读，也可以是学术热点剖析、科研心得或竞赛经验讲解等。我们的目的只有一个，让知识真正流动起来。

📝 稿件基本要求：

• 文章确系个人原创作品，未曾在公开渠道发表，如为其他平台已发表或待发表的文章，请明确标注 

• 稿件建议以 markdown 格式撰写，文中配图以附件形式发送，要求图片清晰，无版权问题

• PaperWeekly 尊重原作者署名权，并将为每篇被采纳的原创首发稿件，提供业内具有竞争力稿酬，具体依据文章阅读量和文章质量阶梯制结算

📬 投稿通道：

• 投稿邮箱：[e-mail] 

• 来稿请备注即时联系方式（微信），以便我们在稿件选用的第一时间联系作者

• 您也可以直接添加小编微信（pwbot02）快速投稿，备注：姓名-投稿

△长按添加PaperWeekly小编

🔍

现在，在「知乎」也能找到我们了

进入知乎首页搜索「PaperWeekly」

点击「关注」订阅我们的专栏吧

·

·