【综述专栏】全面详述图监督图结构等图学习技术进展

马上科普尚尚

发布于 2023-08-29 14:38:07

7690

地址：https://arxiv.org/abs/2304.05055

图表示学习旨在将高维稀疏的图结构数据有效编码为低维稠密的向量，是机器学习、数据挖掘等众多领域的一项基础任务。经典的图嵌入方法遵循图中互联节点的嵌入向量仍然可以保持相对近距离的基本思想，从而保留图中节点之间的结构信息。然而，这是次优的，因为: (i)传统方法的模型容量有限，限制了学习性能; (ii)现有技术通常依赖于无监督学习策略，无法与最新的学习范式耦合; (iii)表示学习和下游任务相互依赖，需要共同加强。随着深度学习的显著成功，深度图表示学习比浅层(传统)方法显示出了巨大的潜力和优势，近十年来提出了大量的深度图表示学习技术，尤其是图神经网络。对当前的深度图表示学习算法进行了全面的调研，提出了一个现有的最先进文献的新分类法。系统地总结了图表示学习的基本组成部分，并通过图神经网络架构和最新的先进学习范式对现有方法进行了分类。此外，本文还提供了深度图表示学习的实际和有前景的应用。最后，本文阐述了新的观点，并提出了具有挑战性的方向，值得未来进一步研究。

1 引言

近年来，图成为表示各种结构化和复杂数据的有力工具，包括社交网络、交通网络、信息系统、知识图谱、蛋白质相互作用网络和物理相互作用网络等。作为一种通用的数据组织形式，图结构能够自然地表达这些数据的内在关系，因此可以表征大量在各种学科和领域中至关重要的非欧几里得结构，因为它们具有灵活的适应性。例如，将社交网络编码为图，用图上的节点来表示个体用户，用边来表示两个个体之间的关系，比如朋友。在生物学领域，节点可以用来表示蛋白质，边可以用来表示各种蛋白质之间的生物相互作用，比如蛋白质之间的动态相互作用。因此，通过对图结构数据的分析和挖掘，我们可以了解隐藏在数据背后的深层含义，进一步发现有价值的知识，从而造福社会和人类。

在过去的十年中，针对图结构数据学习，已经开发出了各种各样的机器学习算法。其中，传统的图核方法[107,177,314,316]通常将图分解为不同的原子子结构，然后使用核函数来衡量它们所有对之间的相似性。虽然图核可以提供一个建模图拓扑的视角，但这些方法往往根据给定的手工制定的标准生成子结构或特征表示。这些规则相当具有启发式，容易受到高计算复杂度的影响，因此可扩展性较弱，性能欠佳。

过去几年不断涌现的图嵌入算法[2,123,276,343,344,359]，试图对图的结构信息(通常是高维稀疏矩阵)进行编码，并将其映射为低维稠密的向量嵌入，以尽可能保留嵌入空间中的拓扑信息和属性信息，使学习到的图嵌入可以自然地融入传统的机器学习算法中。与之前在预处理阶段使用特征工程来提取图结构特征的工作相比，目前的图嵌入算法是以数据驱动的方式利用机器学习算法(如神经网络)来编码图的结构信息。具体来说，现有的图嵌入方法可以分为以下主要组: (i)基于矩阵分解的方法[2,36,268]，对矩阵进行分解以学习保留图属性的节点嵌入; (ii)应用专为图结构数据设计的深度学习技术的基于深度学习的方法[123,276,344,359]; (iii)要么最大化边缘重建概率，要么最小化边缘重建损失的基于边缘重建的方法[229,253,343]。一般来说，这些方法通常依赖于浅层架构，并未能利用深度神经网络的潜力和能力，导致次优的表示质量和学习性能。

受最近深度神经网络显著成功的启发，一系列用于图结构数据学习的深度学习算法被开发出来。这些方法的核心是使用图神经网络(GNNs)生成有效的节点和图表示，其次是面向目标的学习范式。通过这种方式，派生出的表示可以自适应各种下游任务和应用程序。遵循这一思路，本文提出了一种新的分类法，对现有的图表示学习算法进行分类，即图神经网络架构、学习范式和各种有前途的应用，如图1所示。具体来说，对于图神经网络的架构，我们调查了图卷积、图核神经网络、图池化和图transformer的研究。对于学习范式，我们探索了三种高级类型，即图上的监督/半监督学习，图自监督学习和图结构学习。为了证明学习到的图表示的有效性，我们提供了几个有希望的应用程序，以在表示学习和下游任务之间建立紧密的联系，如社会分析、分子属性预测和生成、推荐系统和流量分析。最后但并非最不重要的是，我们提出了一些思考的视角，并提出了值得在未来进一步研究的具有挑战性的方向。

本调查与现有调查的差异。到目前为止，还存在一些其他的综述论文，侧重于图表示学习的不同视角[12,40,43,47,179,387,390,446,463,464]，这些论文与我们的研究密切相关。然而，很少有全面的综述从不同的GNN架构和相应的最新学习范式的角度同时总结了深度图表示学习。因此，我们在这里明确说明它们与我们调查的区别如下。已经有一些关于经典图嵌入的调查[32,119]，这些工作根据不同的训练目标对图嵌入方法进行了分类。Wang等人[366]更进一步，对现有的异构图嵌入方法进行了全面的回顾。随着深度学习的快速发展，出现了一些沿着这条路线的调查。例如，Wu et al.[387]和Zhang et al.[446]主要关注几种经典和代表性的GNN架构，而没有从图自监督学习和图结构学习等最新的高级学习范式的角度探索深度图表示学习。Xia et al.[390]和Chami et al.[40]共同总结了图嵌入和gnn的研究。Zhou等人[463]探索了GNNs不同类型的计算模块。最近的一项综述[179]对来自静态图和动态图的图表示学习的现有工作进行了分类。然而，这些分类强调了基本的GNN方法，但对学习范式关注不足，并且很少讨论最有前途的应用，如推荐系统和分子性质的预测和生成。据我们所知，正式发表的最相关的调查是[464]，它介绍了GNN架构的综述，并粗略地讨论了相应的应用。尽管如此，这项调查仅涵盖了截至2020年的方法，错过了过去两年的最新发展。

因此，非常希望将具有代表性的GNN方法、最新的先进学习范式和有前途的应用总结到一个统一和全面的框架中。此外，我们强烈相信，这项具有新的文献分类法和400多项研究的调查将加强未来对深度图表示学习的研究。

本综述的贡献。本综述的目标是系统地回顾关于深度图表示学习进展的文献，并讨论进一步的方向。旨在帮助对该领域感兴趣的研究人员和从业人员，并支持他们了解全景图和深度图表示学习的最新进展。本次调研的主要贡献总结如下:

系统分类法。我们提出了一个系统的分类法来组织现有的深度图表示学习方法，基于GNN架构的方式和最新的先进学习范式，通过提供一些代表性的分类法。此外，还提出了几个有前途的应用，以说明图表示学习的优越性和潜力。
全面综述。对于本综述的每个分支，我们回顾了基本组成部分并提供了代表性算法的详细描述，并系统地总结了特点以进行概述比较。
未来的方向。基于现有的深度图表示学习算法的属性，讨论了当前方法的局限性和挑战，并提出了值得未来研究的潜力和有前途的研究方向。

2. 图卷积

图卷积已经成为最近开发的许多深度图表示学习算法和图神经网络的基本构建模块。在本节中，我们对图卷积进行了全面的回顾，图卷积一般分为两类: 谱图卷积和空间图卷积。基于图信号处理(GSP)的坚实数学基础[129,303,320]，谱图卷积寻求在频域捕获图的模式。另一方面，空间图卷积继承了循环图神经网络(RecGNNs)的消息传递思想，它们通过聚合其邻居的特征来计算节点特征。因此，一个节点的计算图是从其周围的局部图结构中派生出来的，图拓扑结构自然地纳入到节点特征的计算方式中。在本节中，我们首先介绍谱图卷积，然后介绍空间图卷积，然后做一个简要的总结。在表1中，我们总结了近年来提出的一些图卷积。

技术。图卷积主要分为两种类型，即谱图卷积和空间图卷积。谱图卷积具有坚实的图信号处理数学基础，因此其操作具有理论解释。空间图卷积受到循环图神经网络的启发，其计算简单直接，因为其计算图来源于局部图结构。一般来说，空间图卷积在应用中更常见。
挑战和局限性。尽管图卷积取得了巨大的成功，但在更复杂的应用中，其性能并不令人满意。一方面，图卷积的性能严重依赖于图的构造。不同的图构造可能会导致不同的图卷积性能。另一方面，在构建非常深的神经网络时，图卷积容易出现过平滑。
未来工作。在未来，我们希望开发更强大的图卷积来缓解过度平滑的问题，我们也希望图结构学习(GSL)中的技术和方法可以帮助学习更有意义的图结构，从而有利于图卷积的性能。

3. 图核神经网络

图核(GKs)是历史上在图分析和表示任务中使用最广泛的技术[107,313,463]。然而，传统的图核在特定任务上依赖于手工设计的模式或领域知识[194,316]。多年来，人们对图核神经网络(GKNNs)进行了大量的研究，取得了很好的结果。研究人员已经探索了GKNN的各个方面，包括其理论基础、算法设计和实际应用。这些努力导致了广泛的基于GKNN的模型和方法的发展，这些模型和方法可用于图分析和表示任务，如节点分类、链接预测和图聚类[44,237,238]。GKNNs的成功可以归因于它们能够利用图核和神经网络的优势。通过使用核函数来度量图之间的相似性，GKNNs可以捕获图的结构属性，而神经网络的使用使其能够学习到图的更复杂和抽象的表示。这种技术的组合使GKNNs在广泛的图相关任务上实现最先进的性能。在本节中，我们首先介绍最具代表性的传统图核。然后总结了结合GNN和图核的基本框架; 最后，对流行的图核神经网络进行分类，并比较它们的差异。

技术。图核神经网络(GKNNs)是最近流行的研究领域，它结合了图核和GNNs的优势来学习更有效的图表示。研究人员从理论基础、算法设计和实际应用等各个方面对GKNNs进行了研究。因此，广泛的基于GKNN的模型和方法被开发出来用于图分析和表示任务，包括节点分类、链接预测和图聚类。
挑战和限制。尽管gknn在图相关任务中显示出了巨大的潜力，但它们也有一些需要解决的局限性。可扩展性是一个重大挑战，特别是在处理大规模图和网络时。随着图的规模增加，GKNNs的计算成本呈指数级增长，这可能会限制它们处理大型和复杂的现实世界应用程序的能力。
未来工作。对于未来的工作，我们希望GKNNs可以将更多特定领域的知识集成到设计的核中。特定领域的知识已经被证明可以显著提高许多应用的性能，例如药物发现、基于知识图谱的信息检索系统和分子分析[90,360]。将特定领域知识纳入GKNNs可以增强其处理复杂和多样化数据结构的能力，从而产生更准确和可解释的模型。

4. 图池化

当涉及到图级别的任务时，如图分类和图回归，图池化是从学习到的节点嵌入生成整个图表示的一个重要组件。为了确保同构图具有相同的表示，图池化操作应与节点的排列无关。在本节中，系统地回顾了现有的图池化算法，并将其分为两类:全局池化算法和层次池化算法。全局池化算法直接将节点嵌入聚合为最终的图表示，而层次池化算法减小图规模并逐步生成即时表示，以捕获输入图的层次结构和特征。表3提供了一个总结。

技术。图池化方法通过聚合节点嵌入在生成整个图表示中发挥着至关重要的作用。图池化方法主要有两类:全局池化方法和层次池化方法。全局池化方法直接一步聚合节点嵌入，层次池化方法基于TopK选择、聚类方法或混合方法逐步粗化图以捕获图的层次结构特征。

挑战和限制。尽管图池化方法在学习整个图表示方面取得了巨大的成功，但仍然存在一些未解决的挑战和限制:

1)对于层次池化，大多数基于簇的方法都涉及到密集的分配矩阵，这限制了它们的应用于大型图，而基于topk的方法在捕捉图的结构信息方面不太好，可能会因为节点丢弃而丢失信息。

2)大多数图池化方法是为简单属性图设计的，而为其他类型的图(如动态图和异构图)量身定制的池化算法在很大程度上还没有得到充分的探索。

未来工作。在未来，我们预计可以研究更多的混合或其他池化方法，以充分捕获图结构信息，并对大型图高效。在现实场景中，有各种类型的图，涉及动态、异构或时空信息。专门针对这些图设计图池化方法是很有希望的，这可以有利于更真实的应用，如流量分析和推荐系统。

5. 图 Transformer

尽管基于消息传递范式的gnn在多个众所周知的任务[115,205,363,403]上取得了令人印象深刻的性能，但它们仍然面临一些内在问题，迭代邻居聚合操作。之前的许多工作已经证明了消息传递GNN的两个主要缺陷，即所谓的过平滑和长距离建模问题。而且也有很多解释性的工作试图从这两个问题中挖掘见解。过平滑问题可以解释为各种只关注低频信息[23]的GNN，混合不同类型节点之间的信息破坏模型性能[45]，GCN相当于拉普拉斯平滑[213]，邻居之间的各向同性聚集导致与随机游走相同的影响分布[404]等。无法对GNN的长距离依赖关系进行建模，部分原因是过度平滑问题，因为在传统的邻居聚合GNN的背景下，节点信息只能通过多个GNN层进行长距离传递。最近，Alon et al.[6]发现这个问题也可能是由过度挤压(over- squeeashing)引起的，这意味着随着距离的增加，计算路径呈指数增长。虽然这两个基本的性能瓶颈可以通过精心设计的消息传递和聚合策略来解决，但GNN的表征能力本质上受到Weisfeiler-Lehman同构层次结构的限制[264]。更糟糕的是，大多数GNN[115, 182, 351]都受到最简单的一阶Weisfeiler-Lehman检验(1-WL)的限制。一些努力致力于打破这一限制，如基于超图的[93,149]，基于路径的[31,415]和基于k- wl的[15,264]方法。

在解决这些基本问题的许多尝试中，一个重要的尝试是将Transformer[350]用于图表示学习。transformer，无论是vanilla版本还是几个变体，都已经在包括NLP [70, 350]， CV[38, 469]等各种深度学习领域被采用，并取得了令人印象深刻的结果。最近，Transformer也在许多研究中显示出强大的图建模能力[46,81,193,386,415]。而广泛的经验结果表明，在基于transformer的方法中，传统gnn中的一些慢性缺点可以很容易地克服。本节概述了这类方法的当前进展。

注意力操作的核心是基于源与待更新目标之间的相似度来完成信息迁移。这与全连接图上的消息传递过程非常相似。然而，将这种架构直接应用到任意图上并不能利用结构信息，因此在图拓扑很重要的时候可能会导致性能不佳。另一方面，在图中定义位置编码并不是一个微不足道的问题，因为图节点的顺序或坐标是欠定义的。

根据这两个挑战，基于transformer的图表示学习方法可以分为两大类，一类是在注意力过程中考虑图结构，另一类是将图的拓扑信息编码为初始节点特征。我们将第一种命名为注意力修正，第二种命名为编码增强。表4提供了一个总结。在接下来的讨论中，如果在一篇论文中同时使用了两种方法，我们将在不同的小节中列出，我们将忽略注意力操作中的多头技巧。

本节介绍了基于transformer的图表示学习方法，总结如下:

技术。图Transformer方法修改了Transformer中的两项基本技术，注意力操作和位置编码，以增强其编码图数据的能力。通常，它们引入全连接注意力来建模长距离关系，利用最短路径和拉普拉斯特征向量来打破1-WL瓶颈，并将属于不同类别的点和边分开以避免过度混合问题。
挑战和限制。尽管图transformer取得了令人鼓舞的性能，但它们仍然面临两个主要挑战。第一个挑战是二次注意力机制和最短路径计算的计算成本。这些操作需要大量的计算资源，可能成为瓶颈，特别是对于大型图。其次是基于transformer的模型对大量数据的依赖，以获得稳定的性能。它在处理缺乏足够数据的问题时提出了挑战，特别是在少样本和零样本设置时。
未来的工作。我们期望进一步探索Graph Transformer的效率提升。此外，有一些工作使用预训练和微调框架来平衡下游任务中的性能和复杂性[415]，这可能是解决上述两个挑战的有希望的解决方案。

6. 图半监督学习

我们研究了图神经网络的各种架构，其中的参数应该由学习目标调整。最流行的优化方法是图数据上的监督学习。由于标签scarify的存在，半监督学习在数据挖掘界引起了越来越多的关注。在细节上，这些方法试图将图表示学习与当前包括伪标记、一致性学习、知识蒸馏和主动学习在内的半监督技术相结合。这些工作可以进一步细分为节点级表示学习和图级表示学习。我们将分别在第7.1节和第7.2节中详细介绍这两部分。表5给出了一个总结。

本节介绍用于图表示学习的半监督学习，我们提供如下摘要:

技术。经典节点分类旨在对访问未标记数据的图进行直推式学习，这是一个自然的半监督问题。半监督图分类旨在缓解对大量标记图的需求。在这里，人们提出了多种半监督方法，以在标签稀缺的情况下实现更好的性能。通常，他们试图将主动学习、伪标记、一致性学习和一致性学习等半监督技术与图表示学习相结合。
挑战和限制。尽管取得了巨大的成功，但这些方法的性能仍然不令人满意，特别是在图级表示学习方面。例如，DSGC在二分类数据集REDDIT-BINARY中只能达到57%的准确率。更糟糕的是，标签稀缺往往伴随着不平衡的数据集和潜在的域偏移，这为现实世界的应用提供了更多的挑战。
未来工作。在未来，我们期望这些方法可以应用于不同的问题，如分子性质预测。还有一些工作可以扩展图表示学习的应用场景，如少样本学习[41,249]。对于更先进、更有效的半监督技术，总是期待更高的精度。

7. 图自监督学习

除了监督或半监督方法之外，近年来自监督学习(SSL)在数据挖掘和表示嵌入方面也显示出强大的能力。在本节中，我们研究了基于SSL的图神经网络，并对几个典型的模型进行了详细介绍。图SSL方法通常有一个统一的管道，包括前置任务和下游任务。前置任务帮助模型编码器学习更好的表示，这是在下游任务中表现更好的前提。因此，精致的前置任务设计对于Graph SSL至关重要。我们将首先在8.1节介绍Graph SSL的整体框架，然后在8.2节和8.3节分别介绍两种前置任务设计，基于生成的方法和基于对比的方法。表6提供了一个总结。

本节介绍图的自监督学习，总结如下:

* 技术。与经典的监督学习和半监督学习不同，自监督学习提高了模型泛化能力和鲁棒性，同时降低了对标签的依赖。Graph SSL利用前置任务来提取表示分布中的固有信息。典型的Graph SSL方法可以分为基于生成的和基于对比的两种。基于生成的方法学习一个编码器，该编码器具有尽可能精确地重建图的能力，由自动编码器驱动。基于对比的方法最近引起了极大的兴趣，它们学习一个编码器，以最小化相关实例之间的互信息和最大化不相关实例之间的互信息。

挑战和局限。尽管graph SSL在许多任务中取得了卓越的性能，但它的理论基础并不那么坚实。许多众所周知的方法只是通过实验进行验证，而没有解释理论或提出数学证明。为graph SSL建立一个强大的理论基础是势在必行的。
未来的工作。未来，我们期待更多基本上通过理论证明设计的graph ssl方法，而不是通过直觉专门设计的增强过程或伪装任务。这将给我们带来更明确的数学属性和更少模糊的经验意义。此外，图是跨不同领域的数据表示的一种普遍形式，然而获得手工标签可能非常昂贵。将graph SSL的应用扩展到更广泛的领域是未来研究的一个有希望的途径。

8. 图结构学习

图结构决定了节点特征如何相互传播和影响，在图表示学习中起着至关重要的作用。在某些场景中，提供的图是不完整的、有噪声的，甚至根本没有结构信息。最近的研究还发现，图的对抗攻击(即修改少量节点特征或边)可以显著降低学习到的表示。这些问题激发了图结构学习(GSL)，它旨在学习一种新的图结构以产生最优的图表示。根据边连接的建模方式，GSL中有三种不同的方法，即基于度量的方法、基于模型的方法和直接的方法。除了边建模，正则化也是一种常用的技巧，可以使学习到的图满足一些期望的属性。我们首先介绍了基本框架和分别在9.1节和9.2节中介绍GSL的正则化方法，然后在9.3节、9.4节和9.5节中介绍GSL的不同类别。我们在表7中总结了GSL的方法

本节和我们提供的总结如下:

技术。GSL旨在学习一个优化的图结构以获得更好的图表示。它还用于对抗对抗攻击的更鲁棒的图表示。根据边缘建模的方式，我们将GSL分为三组:基于度量的方法、基于模型的方法和直接方法。正则化也是一种常用的原理，使学习到的图结构满足包括稀疏性、低秩性和平滑性在内的特定属性。
挑战和限制。由于没有办法访问groundtruth或最佳图结构作为训练数据，GSL的学习目标要么是间接的(例如，在下游任务上的性能)，要么是手动设计的(例如，稀疏性和平滑性)。因此，GSL的优化是困难的，性能并不令人满意。此外，许多GSL方法都是基于同质性假设，即相似的节点更容易相互连接。然而，现实世界中存在着许多其他类型的连接，这给GSL带来了巨大的挑战。
未来的工作。在未来，我们期望更高效和可泛化的GSL方法被应用于大规模和异构图。大多数现有的GSL方法专注于成对节点相似性，因此难以扩展到大型图。此外，它们通常学习同质的图结构，但在许多场景中图是异构的。

9 结论

在本综述中，我们对深度图表示学习进行了全面和最新的概述。提出了现有算法的一种新的分类法，分为GNN架构、学习范式和应用。技术上，我们首先总结了GNN架构的方法，即图卷积、图核神经网络、图池化和图transformer。基于不同的训练目标，我们提出了三种最新的高级学习范式，即:图上的监督/半监督学习，图自监督学习和图结构学习。然后，我们提供了几个有希望的应用，以证明深度图表示学习的有效性。最后但同样重要的是，我们讨论了深度图表示学习中具有潜在机会的未来方向。

本文目的在于学术交流，并不代表本公众号赞同其观点或对其内容真实性负责，版权归原作者所有，如有侵权请告知删除。

“综述专栏”历史文章