图在表示关系数据(如化合物、蛋白质和社交网络)方面具有卓越的能力。因此，图级学习以一组图作为输入，已应用于许多任务，包括比较、回归、分类等。传统的图学习方法往往依赖于手工设计的特征，如子结构。但是，虽然这些方法受益于良好的可解释性，但它们往往遭受计算瓶颈，因为它们不能绕过图同构问题。相反，深度学习通过自动提取特征并将图解码为低维表示，帮助图级学习适应不断增长的图规模。因此，这些深度图学习方法取得了许多成功。然而，没有一个全面的调研来回顾从传统学习到深度学习方法的图级学习。本文填补了这一空白，并将具有代表性的算法框架化为一个系统的分类，包括传统学习、图级深度神经网络、图级图神经网络和图池化。为了确保一个彻底的全面的综述，从四个不同的分支的开发方法之间的演变，交互和交流也被检查。接下来简要回顾基准数据集、评估指标和常见的下游应用。该调研总结了13个必要研究的未来方向，这些研究将有助于克服这一蓬勃发展的领域面临的挑战。
1. 引言
对图结构数据的研究始于18世纪的哥尼斯堡桥问题，即:“我们如何在哥尼斯堡市的7座桥中设计一条每座桥只穿过一次的路径?”1741年，Euler将7座桥梁建模成一个图，并证明在没有重复路径[1]的情况下，该图是不能完全遍历的。在图中，节点表示桥梁之间的连接点，而边表示桥梁本身。从那时起，图结构数据已经成为建模和探索世界不可或缺的一部分。在大量与图相关的文献中，图级学习引起了相当大的关注。图级学习是对由图组成的数据集的分析。例如，图同构问题，即两个成对图是否同构的问题，自1942年首次提出以来吸引了大量的研究[2]-[4][5]。进一步，在2016年[6]提出一个拟多项式时间解之前，图同构被认为是NP-immediate的候选对象。还研究了其他有重要价值的应用。例如，Wang et al.[7]采用分子图，其中节点表示原子，边表示化学键，并执行图回归作为预测分子特性的一种方法，以帮助发现更经济的晶体。在另一项研究中，基于一系列蛋白质图的图生成任务用于生成具有特定功能的蛋白质图，以支持药物发现[8]。同样，基于脑图的图分类具有将神经系统疾病的脑结构与健康个体[9]的脑结构区分开来的潜力。
传统的图级学习主要依赖手工设计的特征来区分图。然而，尽管手工特征赋予了传统方法良好的可解释性，但它们通常具有较高的计算复杂度，这是阻碍其部署的主要障碍。该方法的复杂性在于:(1)大规模图数据中手工特征通常过于稀疏;(2)大多数依赖于这些手工特征的图级学习算法通常涉及图同构问题。例如，一些传统的图分类方法是根据从图数据集中分解出的一系列子结构对图进行分类的，其主要问题是判断是否存在同构子结构。然而，深度学习技术已经开启了图级学习的新时代。通过这些方法，可以以端到端的方式自动学习图的非线性和特定任务的特征，这为最先进的性能带来了新的基准。此外，深度神经网络学习的高维表示可以支持不断增长的图数据规模。美中不足的是，深度学习的黑箱性质导致可信性下降，因此一个新的趋势是通过传统技术开发可靠的神经网络。
此外，要理解跨越传统和深度学习的各种图级学习技术，需要全面回顾大量的图级学习文献。有一些关于学习图结构数据的调研。然而，这些评论有两个主要缺点。首先，现有的研究大多集中在探索单个图中的节点/边/子结构的文章，如网络嵌入[10]、社区检测[11]、[12]、异常检测[13]和图神经网络[14]、[15];图级学习被视为占用分段或更少部分的副产品。图1说明了单个图上的图学习和图级别学习之间的差异。其次，仅从单一角度研究图级学习，如图核[16]或图池[17]。因此，这些调研并不全面，因为它们忽略了不同图级学习技术之间的相互作用。据我们所知，这是对图级学习的第一次全面调查，涵盖了传统方法和基于深度学习的技术。详尽地描述了图级学习不同时期的主流技术(见图2)，并进一步讨论了它们之间的演变、相互作用和交流。因此，本调研的贡献包括:
全面的分类法:本文提出了图级学习技术的全面分类法。具体来说，该分类涵盖了通过传统和深度学习方法进行的图级学习。
深度回顾:总结了四类具有代表性的算法，进行了比较，并讨论了现有方法的贡献和局限性。
丰富的资源:这份调研为读者提供了丰富的图级学习资源，包括最先进算法的信息，不同领域的基准数据集，不同图级学习任务的公平评估指标，以及实际的下游应用。本文的存储库可在https://github.com/ZhenyuYangMQ/Awesome-GraphLevel-Learning上找到。
未来方向:本文确定了图级学习领域的13个重要未来方向。
图2:四种主流技术下的图级学习时间线。
本节提供图级学习技术的分类。它的类别包括传统学习，图级深度神经网络(GL-DNNs)，图级图神经网络(GL-GNNs)和图池化。图3中的分类树描述了图级学习的这四个分支，并突出了所选算法。接下来简要介绍每一类。
A. 传统的学习:
在深度学习技术取得巨大成功之前，传统的学习形式曾经是图级学习的主流。传统的学习方法大多依赖手工特征来描述图，如随机游走序列[16]。给定确定性的图描述，使用现成的机器学习模型以非端到端的方式执行下游任务，如图分类。即使在今天，传统方法也比深度学习技术具有一些优势，例如更好的可解释性和更好的建模不规则结构的能力。出于这些原因，传统方法仍然为图级学习社区提供了有价值的见解。
B.图级深度神经网络(GL-DNNs):
传统方法不仅仅包括经典方法。它们还包括对深度学习技术的初步探索，如RNN、CNN和CapsNet。这三种类型的深度神经网络最初并不是为了学习像图这样的非欧氏数据而设计的。因此，GL-DNNs的一个重要问题是如何使这些深度神经网络学习大小不一且邻域结构不规则的图结构数据。
C.图级图神经网络(GL-GNNs):
GL-GNNs使用专门为图结构数据提出的图卷积操作作为执行图级学习的主干。大多数GL-GNN使用图卷积MPNNs框架，因为它们简单，易于理解，并且具有线性复杂度。GL-GNNs凝聚了图级学习最丰富的成果。此外，一些从业者将基于MPNN的GL-GNN的优势与其他技术，特别是传统学习技术相结合，以提高图级学习。
D .图池化:
图池化是一种缩小图规模的技术，通过将一系列节点压缩为一个超级节点来产生图的紧凑表示。例如，图池化可以通过求和或平均操作将图的所有节点嵌入全局聚合到一个最终超级节点中。同时，图池化可以逐层减小图的大小。这种多层缩小过程倾向于在每一层聚集同一层次结构(例如，社区)中的节点。
想要了解更多资讯，请扫描下方二维码，关注机器学习研究会
转自：专知
