《图简化(Graph Reduction)》最新综述

许多现实世界的数据集可以自然地表示为图，涵盖了广泛的领域。然而，图数据集的日益增长的复杂性和大小为分析和计算带来了显著挑战。作为回应，图简化技术因其在简化大型图的同时保留关键属性而获得了重要地位。在这篇综述中，我们旨在提供对图简化方法的全面理解，包括图稀疏化、图粗化和图凝聚。具体来说，我们为这些方法建立了统一的定义，并引入了一个层次化的分类法来归类它们解决的挑战。我们的综述然后系统地回顾了这些方法的技术细节，并强调了它们在不同场景中的实际应用。此外，我们概述了确保图简化技术持续有效性的关键研究方向，并在https://github.com/ChandlerBang/awesome-graph-reduction上提供了一份全面的论文列表。我们希望这篇综述能够填补文献空缺，并推动这一有希望的领域的进步。

图结构数据在各个领域已变得无处不在，从社交网络和生物系统到推荐系统和知识图谱[Fan et al., 2019; Wu et al., 2022b, 2018; Shi and Weninger, 2017; Wang et al., 2021]。图数据的内在关系结构使其成为模拟复杂交互和依赖关系的强大表示。此外，随着图机器学习技术的兴起，特别是图神经网络（GNNs）[Kipf and Welling, 2016; Wu et al., 2020]，图数据集的利用见证了前所未有的增长，推动了节点分类、链接预测、图分类和图生成等任务的进展[Zhou et al., 2020; Ma and Tang, 2021]。 近年来，图数据集的大小和复杂性呈指数级增长。大规模网络，如社交图和引文网络[Hu et al., 2021]，挑战了现有算法的可扩展性和效率，并要求为高效模型训练提供创新解决方案。尽管最近努力设计了可以伴随大型图扩展的GNNs [Jia et al., 2020; Zeng et al., 2021; Song et al., 2023; Liu et al., 2021]，另一种方法专注于减小图数据集的大小，包括图、节点和边的数量，我们将之称为图简化[Jin et al., 2022b; Huang et al., 2021]。在本文中，我们将图简化定义为寻找一个更小尺寸的图数据集的过程，同时保留其关键信息。具体来说，这一定义要求一个算法接受原始图数据集作为输入并产生一个更小的数据集。如图1所示，图简化旨在通过保持其结构和语义特性来从庞大的图数据集中提取关键信息。除了加速图算法外，图简化还提供了一系列优势。首先，减少后的图显示出与各种下游模型架构的兼容性[Jin et al., 2022b]。其次，图简化可能有助于隐私保护，因为它改变了原始结构或节点属性，使它们难以恢复[Dong et al., 2022]。第三，与其较大的对应物相比，减少后的图显著更小，更易于人类理解，这有助于图可视化[Imre et al., 2020]。

鉴于图简化的重要性，已经开发了众多算法，这些算法分为三种不同策略：图稀疏化[Althofer et al., 1993; Batson et al., 2009]、图粗化[Loukas and Vandergheynst, 2018; Dorfler and Bullo, 2012]，以及更近期的图凝聚[Jin et al., 2022b,a; Xu et al., 2023; Liu et al., 2022]。图稀疏化围绕通过仅保留一部分边和重要节点来近似图的概念展开。与之相反，图粗化并未消除任何节点，而是将节点分组并合并成超级节点，使用指定的聚合算法将原始组间边聚合成超级边。与前两种策略不同，图凝聚最近被引入作为一种在保持GNNs性能的同时，通过合成更小的图来凝聚图的方法。尽管这些方法已经广泛传播，但它们通常是孤立研究的，留下了它们之间的联系和区别有些模糊。因此，提供这些现有算法的系统概览，以增强我们对图简化技术的理解，既必要又及时。

贡献。在这项工作中，我们旨在提供一份全面且最新的综述，聚焦于图简化技术及其在解决图相关挑战中的多样化应用。我们希望这份综述能够成为初学者研究人员和对探索该领域感兴趣的从业者的宝贵资源，同时也催化未来研究努力。我们的贡献可以总结如下：(a) 我们提供了第一个全面的图简化方法综述，包括图稀疏化、图粗化和图凝聚。 (b) 我们为现有的图简化方法开发了一个统一的视角，在第2节中根据它们的特征进行区分，并在第3节提供代表性算法的详细回顾。 (c) 我们在第4节讨论了图简化方法的实际应用，阐明了这些技术证明有价值的现实世界场景。 (d) 在第5节，我们识别关键挑战和有希望的未来研究方向，指导图简化技术的持续进步。

与现有综述的联系。与之前关于图简化的综述[Liu et al., 2018; Interdonato et al., 2020; Shabani et al., 2023; Chen et al., 2022]相比，我们的研究提供了图凝聚这一新兴领域的全面概述，并提出了一个统一框架，将图凝聚与传统的图简化技术联系起来。此外，我们的综述探索了图简化和GNNs之间的协同作用，这是现有综述中很少涉及的一个方面。同时，一些以数据为中心的图学习综述[Zha et al., 2023; Zheng et al., 2023a]包括了对图简化的讨论，但我们提供了更详细、更彻底的简化技术审查。此外，我们的工作与最近关于数据集蒸馏的综述[Geng et al., 2023; Sachdeva and McAuley, 2023]有所联系，虽然它们主要关注应用于图像数据的凝聚方法。 在图2中，我们提供了上述类别中现有图简化方法的详细分类，并将在接下来的部分中详细阐述。此外，表2提供了前面提到的三种图简化策略的定性比较。

方法论

在本节中，我们将介绍上述三种图简化策略的代表性算法。对于每种策略，我们根据它们的学习目标对方法进行分类，并在表3中总结了流行的方法。 图稀疏化 图稀疏化作为图简化的直观方法，涉及基于特定标准选择关键边或节点。传统方法通常侧重于保留特定图属性，如谱和中心性。随着GNNs日益流行，旨在维持节点表示质量的方法越来越多。因此，我们根据它们的保留目标将现有技术分为两组：一组专注于保留图属性的，另一组致力于维持模型性能的。 图粗化 在稀疏化方法中选择节点或边不可避免地会丢失一些信息。为了确保保留足够量的信息，开发了粗化技术，涉及对节点进行分组并聚合它们。这一过程可以迭代进行，产生原始图的层次视图。现有的粗化方法可以根据是否存在重构目标分为两组：基于重构的方法和无需重构的方法，将在后续进一步阐述。 图凝聚 尽管稀疏化和粗化方法在减小图数据的大小方面已被证明是有效的，但它们存在内在的局限性。由于这些方法中的许多优先保留特定的图属性，它们没有利用下游任务信息，可能导致模型性能不佳。此外，这些技术依赖于原始图中存在代表性节点或边的假设，这在原始数据集中可能并不总是成立。为了解决这些问题，图凝聚首次由[Jin et al., 2022b]引入，开始发挥作用。

结论

在本文中，我们提供了一个结构化且具有前瞻性的图简化综述。我们首先建立了图简化的正式定义，然后开发了一个详细的层次分类法，系统地组织了这一领域内的多样化方法论。我们的综述将图简化技术划分为三个主要类别：稀疏化、粗化和凝聚。每个类别代表了一种独特的方法来减少图复杂性，同时保留关键属性。在每个类别中，我们系统地深入探讨了突出方法的技术细节，并突出显示了它们在各种现实世界场景中的实际应用。此外，我们阐明了该领域内存在的挑战，并指出了未来研究努力的潜在方向。我们的目标是激励和指导即将进行的研究，为图简化方法论的持续发展和进步做出贡献。