最新综述| A Survey on Graph Condensation 如何有效将大图压缩为小图?

Houye

发布于 2024-02-26 20:30:22

1940

发布于 2024-02-26 20:30:22

大规模图的分析对计算效率和资源需求提出了重大挑战。最近，图缩合(Graph Condensation)作为一种解决方案出现，以解决图数据量不断增加所带来的挑战。GC的动机是将大图的规模缩小到较小的图，同时为下游任务保留必要的信息。为了更好地理解GC并将其与其他相关主题区分开来，浙江大学与伦斯勒理工大学联合发布了该领域的权威综述

综述题目：A Survey on Graph Condensation
PDF 链接: https://arxiv.org/pdf/2402.02000.pdf
Github 仓库: https://github.com/Frostland12138/Awesome-Graph-Condensation

研究目标与挑战

图数据表示实体之间的关系和交互，在包括社交网络、生物系统和推荐系统在内的各个领域中无处不在。这些场景中的信息和模式已经被建模为节点和边缘，并且在大规模图数据挖掘和模式识别技术等方面拥有重大进展。然而，分析和处理大规模图形对计算效率和资源需求提出了重大挑战。在计算机视觉方面，数据集蒸馏技术得到了广泛的研究与关注。传统的数据集蒸馏依赖的思想是：在由类标签定义的类别中，同一类的实例具有相似的关键特征，例如视觉数据集中的形状模式。这意味着存在“原型”或“聚类中心”，因此同一类的实例之间存在大量冗余信息。同样，在图数据集中，例如在节点分类任务中，同一类内节点的特征和拓扑结构是相似的，图中可能存在大量重复和相似的子图结构。因此，一个自然的问题是：我们如何有效地从大规模图中浓缩有用的信息到小规模图中，以促进各种图数据挖掘任务的效率？以此为研究目标，图缩合方法提出将大规模图提炼成更小但信息量更大的新图。缩合后的新图，在有限计算资源的约束下更易于管理，从而为图数据挖掘任务和应用提供更好的支持，如图持续学习，网络架构搜索和联邦学习等。

虽然图缩合概念与图数据的数据蒸馏（data distillaion）是一致的，但沿用数据蒸馏的定义会导致：

缺乏能够突出图数据特性的问题定义；
该领域的丰富方法被归为数据蒸馏在图数据上的一个应用

主要贡献和定义

为了增强对GC的理解，我们首先提出了一个精炼的定义，阐明了GC相较于已有大量研究主题独特之处，并强调了与普通数据集蒸馏的区别。在我们的定义下，由于共同的研究目标，即通过减少图数据量来促进图数据分析，部分相关主题的方法也被包含在我们的讨论中。我们的贡献如下：

我们提出了GC的正式定义，并系统地将现有的GC方法根据优化目标分为三种类型:图导向、模型导向和混合，并将将缩合图的生成方式分为修饰法（对原图进行聚合、删减）和合成法（从初始化的参数开始合成全新的图）；
我们提供了基本数据集的摘要，并对评估指标和方法应用进行了分析；
我们从更广阔的角度深入研究了GC方法的局限性和挑战，提出了未来的方向，从而启发了GC的未来工作。

由于图数据集的丰富性，图缩合算法的研究涉及单图和多图的场景。考虑

\mathcal{S}=\{\mathcal{G}_1, \cdots, \mathcal{G}_{\eta}\}

表示

\eta

张图的数据集，其中

\eta\in \mathbb{N}

\mathcal{G}=\{\mathcal{V},\mathcal{E}, {\bf A}, {\bf X}\}

\mathcal{V}

和

\mathcal{E}

表示顶点(节点)和边的集合,

{\bf A} \in \mathbb{R}^{N \times N}

为邻接矩阵,

{\bf X} \in \mathbb{R}^{N \times d}

为特征矩阵。

{\bf L}_{\mathcal{G}}

则是图

\mathcal{G}

对应的拉普拉斯矩阵。

\mathcal{Y}\in \{ 1,\cdots, C \}^M

表示

\eta=1

时节点或者边的标签；当

\eta>1

时，

[\mathcal{Y}] \in \mathbb{N}^{M \times 1}

为标签的向量表示。

假设缩合数据集为

\mathcal{S}_c=\{{\mathcal{G}_c}_1, \cdots, {\mathcal{G}_c}_{\mu}\}

\mu \leq \eta

，我们对GC的定义如下：

在定义中，GC特指一类旨在将大规模图缩放为更小但信息丰富的新的图数据集的方法，这里的“新”意味着原始数据集中不存在的部分，包括新的节点和边。

由于广泛的研究围绕单个图的数据缩合展开，为了更直观展示缩合过程的信息变化，我们有以下公式表示其优化过程：

其中：

缩合目标

\mathcal{O}

描述图信息的损失，通过函数

\phi

进行量化；

{\bf W}

通过最小化

\mathcal{O}

进行优化；

公式函数

f()

描述了我们如何公式化缩合图，由

{\bf {W}}

进行参数化。

形成缩合图的三个步骤对应于GC工作流中的三个步骤，如上图（c）所示。根据我们的定义，对于图中需要保留信息的指定至关重要，因为主要目标是在保留足够信息的同时减少图数据的规模。我们根据图缩合对象分类对已有研究进行介绍，并在论文中列出了该领域中现有算法的优化方式。

方法介绍与分类

数据对象分类

根据GC定义中缩合对象的不同，我们把方法分为三种类型：保留图的某些属性(图指导)，保留GNN对下游任务的能力(模型指导)，或同时完成两者(混合方法)。

图指导

该类型方法主要是以原始数据集为导向，提取得到类似属性的缩合图，其中对于图属性的定义和相似性评估是该类方法的关键。根据图信息所属域的不同，我们将该类目标进一步分为图数据的谱域和空间域方法。

谱域中拉普拉斯算子是用来定义图的谱性质，这一类GC方法通过最小化原始图集和缩合图集的谱域距离，或者直接使用拉普拉斯特征值和特征向量进行相似度靠近优化来获得缩合图集。
空间域是指图的原始拓扑和节点特征，最小化拓扑信息如使用图密度、节点平均度、节点度方差、评分函数排序等指标和冗余结构识别等方法进行优化。特征则可以使用同态性、特征重构等方法进行优化。

模型指导

我们假设

\operatorname{GNN}(;{\theta}_{\mathcal{S}}): \mathcal{S}\rightarrow\mathcal{Y}

表示用

{\theta}_{\mathcal{S}}

参数化的GNN在数据集

\{\mathcal{S},\mathcal{Y}\}

上训练。由于GC的最终目标是通过在较小的图集上训练模型 (包括但不限于GNN) 来获得和原始数据集相似的性能，因此使用原始图训练的神经网络模型上的信息是有意义且可用的。因此，许多方法以模型为中介来获得缩合数据集，优化目标为为：

\min _{\mathcal{G}_c} \mathcal{L}\left(\mathrm{Model}(S;{\boldsymbol{\theta}_{\mathcal{G}_c}}), \mathcal{Y}\right) \\ \text { s.t } \quad \boldsymbol{\theta}_{\mathcal{G}_c}=\underset{\boldsymbol{\theta}}{\arg \min } \mathcal{L}\left(\mathrm{Model}\left(\mathcal{G}_c; {\boldsymbol{\theta}}\right), \mathcal{Y}^{\prime}\right),

其中

\mathcal{L}

是特定于任务的损失函数，优化属性为

\phi(\{\mathcal{G},\mathcal{Y}\})=\phi(\mathrm{Model}(;{\boldsymbol{\theta}_{\mathcal{G}}}))

，优化目标是

\mathcal{O}=D(\phi(\mathrm{Model}(;{\boldsymbol{\theta}_{\mathcal{G}_c}})),\phi(\mathrm{Model}(;{\boldsymbol{\theta}_{\mathcal{G}}})))

为距离函数。

现有研究捕获的模型属性信息包括：梯度、模型损失值、嵌入和logits预测等。

混合方法

值得注意的是，上述两类优化目标并不是相互冲突的。因此，我们把同时结合了图属性和模型信息作为凝聚过程中的指导的方法称为混合方法。

目标比较

三种类型的目标，即图指导、模型指导和混合方法，对应其优点和缺点的讨论如下：

图指导：为了产生“相似”的缩合图，图指导目标侧重于保留原始图的属性。这适用于需要保留原始图中的模式的应用程序。然而，它们不受下游任务的指导，因此可能不是最优解决方案。
模型指导：目标旨在通过优化缩合图来保持模型的性能。这些方法是由动机导向的优化驱动的，因此在预定义的场景中表现得非常好。然而，它可能会导致过拟合，降低缩合图对其他模型或任务的适应性。
混合方法：结合了图引导方法和模型引导方法的优点，旨在保留模型性能的同时，为同时重视图属性和模型性能的场景保留图属性。然而，平衡这两个目标并优化它们可能具有挑战性。

综上所述，图指导更适用于强调图结构的任务，模型指导适用于强调模型性能的场景，混合方法寻求两者之间的平衡。考虑到任务的目标和图的特点，在实际应用中选择最合适的方法需要仔细考虑。

优化方法分类

对于原始数据集的优化，我们提出公式表述：

\{\mathcal{G}_c,\mathcal{Y}^{\prime}\} = \{\{{\bf A}^{\prime}, {\bf X}^{\prime}\},\mathcal{Y}^{\prime}\}

。因此,

f(G)

优化过程包括三个部分分别对应缩合图的拓扑，特征和标签，对应表示为：

{\bf A}^{\prime} = f_{\bf A}(G; {\bf W})

{\bf X}^{\prime} = f_{\bf X}(G; {\bf W})

, 和

\mathcal{Y}^{\prime}=f_{\mathcal{Y}}(G; {\bf W})

。进一步，我们把得到缩合图的具体过程分为修饰法和合成法。

修饰法

修饰法包括节点聚合和删除等操作，其中缩合图是修改原始图的产物。这类公式可以统一形式化为从原始图

\mathcal{G}

到缩合图

\mathcal{G}_c

的节点聚合操作。假设缩合图节点

v^{\prime}_i\in V^{\prime}

是由原始图中

个节点聚合而来，其中

k\in \mathbb{N}

，我们总结形式化过程如下：

f_{\bf A}(\mathcal{G}; {\bf P}) = {\bf P^{T}AP} \text{ },\text{ } f_{\bf X}(\mathcal{G}; {\bf P}) = {\bf P^{+}X},\\ f_{\bf \mathcal{Y}}(\mathcal{G}; {\bf P}) = \arg \max {\bf P^{+}}{[\mathcal{Y}]}

其中

\top,+

表示矩阵的转置和伪逆运算，

P \in \mathbb{R}^{N\times N^{\prime}}

被定义为映射矩阵，表示原始图

\mathcal{G}

中的节点

\mathcal{V}_{(i)}

聚合成为缩合图

\mathcal{G}_c

中的超级节点

v^{\prime}_i

。在一般定义中，映射矩阵

的每一行可能包含不确定数量的非零条目，从none（节点被认为是丢弃的）到一个(节点聚合一次)甚至多个(社区存在重叠问题)。目前还没有论文深入讨论这一领域的社区重叠，然而，这种情况也可以包括在我们的构想中。

合成法

合成法将缩合图作为参数，通过最小化特定目标函数来直接优化。我们进一步将此公式分为三种策略:预定义、联合优化和顺序优化。

预定义：预定义缩合图的拓扑

和标签

Y '

；

联合优化：将缩合图(拓扑

和节点特征

)视为优化目标的参数，并且通常通过采样原始标签

来预定义节点标签

Y '

；

顺序优化：可以视为联合优化挑战中的一种妥协（如果将包含拓扑

和节点特征

的完整缩合图作为优化参数，则参数空间的维数会显著上升，从而导致难以收敛），采用对缩合图的部分属性信息进行优化，然后根据信息之间的关系构造或学习其余信息。

方法比较

尽管合成法中顺序优化必须依赖于其他属性的中间结果，但以上提到的每种优化方式都有其独特的方法(或尚未发明但可以实现的方法)来分别生成

A ', X ', Y '

。综上所述，修饰法表现出最强的计算效率和可解释性，但其适用性有限，因为每个等待凝结的图都需要重新校准投影矩阵。联合优化合成法是最简单的方法，可以直接定义目标并进行优化，但也是最具挑战性的方法，参数搜索空间可能太大而难以收敛。为了解决这个问题，顺序优化合成是一个两步方案，结合了易于实现和面向目标的优点。预定义的合成法产生直观的结果，并且在特定设计的场景中有效。

多图缩合方法

以上方法的分类与讨论都是针对单个图的缩合算法，而有些例如生物数据集中的分子图中，一个分子就是一个图网络，因此对于多图数据集的缩合方法我们也做出分类如下：

一对一缩合：每个图都是独立缩合的，即缩合图集和原始图集中图的数量保持不变；
联合缩合：与单图联合优化类似，该策略将多个图作为优化目标，即缩合图集中图的个数远远小于原始图集。

数据集和评价指标

数据集

我们系统地组织和总结了所讨论方法中使用的数据集，将它们分为两种主要类型:具有单个大图的数据集和包含多个图的数据集。前者通常用于节点分类和边缘预测等任务，后者用于图分类。我们给出了数据集的关键属性，包括节点数量、边数量、特征和类等细节，以及具有单个大图的数据集的图类型(例如，社交网络或分子网络)。此外，对于包含多个子图的数据集，我们根据子图的数量、节点的平均数量、边的平均数量、标签的数量和图的类型提供组织。这些数据集的详细统计可以在我们的在线资源中找到。

有效性和效率度量

GC旨在创建一个更小的图数据集，同时保留足够的信息，因此评估这些信息保留了多少是至关重要的。与传统GNN的直接性能评估相比，GC方法由于其信息的复杂和方法的多样，从而难以进行较为客观的评价。从整体的角度来看，我们将整个GC过程的评价归纳为两个方面：有效性和效率度量。有效性评估GC保留原始信息的程度，而效率包括冷凝过程和下游任务效率。详情如下：

有效性

从输入和输出的角度来看，GC方法将原始图作为输入，将缩合图作为输出。为了验证缩合图的信息量，从以下三个方面来评估GC的有效性:

评估原始图和缩合图在光谱和空间特征等领域的相似性；
缩合图集在下游任务中的性能与传统GNN的评价非常接近，但具有可比性的性能可以被认为是成功地为下游任务保留了有价值的信息；
缩合图本身的属性，例如，将GC作为一个组件集成到现有系统中的适用性，以及与目标系统(如图嵌入和图持续学习)相一致的评估指标；具有公平性、通用性等能力的度量。

效率

GC的基本动机是高效地促进大规模原始图上的图挖掘任务。因此，评估GC在缩合图挖掘中节省的资源或者说效率提升是有必要的。我们主要针对GC算法本身的效率和得到的缩合图集用于下游任务的效率提升进行讨论。

GC算法效率：算法本身的时间复杂度和空间复杂度，得到缩合图集所用的时间和内存占用等；
缩合图下游任务：使用缩合图集训练一个新的GNN相较于原始图集的效率提升一般可由缩合比间接表示出，但对应的时间和内存等分析可以为缩合比和性能的权衡提供指导。

挑战与未来方向

局限性与挑战

性能差距：在我们的分析中，有一个明显的性能差距：合成缩合图的规模比修改策略的规模小得多。不同的策略有各自的优势，但是在同一度量标准上进行评估时，可能存在显著的性能差距。即合适的方法的选择是多种多样的，取决于应用场景的实际需求，目前很难有一个统一的策略。
应用的效率：如果GC的最终目标是在缩放数据集上有效地训练GNNs，则可能需要确保GC投入的时间和资源不会超过在较小的图上训练所节省的时间。然而，由于GC过程是一次性的，只要下游任务持续足够长的时间或经常重复，这个需求仍然可以满足。因此，下游任务场景必须作为效率评估方案的一部分。
综合效能指标：现有方法主要基于下游任务中缩合图的性能来评估GC有效性。然而，传统的性能指标，如准确性ACC，可能无法解决关键问题。其他如缩合图集的公平性，鲁棒性等都需要进一步的关注与研究。
潜在能力探索：GC方法得到了一个新的数据集，而对于新概念的引入可能会带来许多潜在的能力提供给我们进行探索。我们认为一下方面可以提供指导：(1)各种GNN架构的性能; (2)模型收敛性; (3)极端缩合比和(4)多重下游任务等。

未来方向

可解释性：与计算机视觉领域数据集蒸馏的结果所带来的天然可解释性不同，缩合图的输出需要在现实世界中进一步探索可解释性。在我们的定义中，GC的关键识别是缩合图中的节点或边可能是新生成的。虽然这些新元素可能为图挖掘提供了足够的信息，但它们在现实世界中的语义含义可能很难直接获得。
更复杂的图数据：尽管GC已经成功地在各种图中开发，但大多数现有方法主要集中在无向、同构、静态图上。然而，现实场景中的图通常更复杂，例如动态图(例如;如交通流图)、异构图(如用户-项目图)等。
优化对象的关系：在我们的分类法下，每个GC目标都可以根据要保存的特定信息分为两组--图指导和模型指导。这两类目标并非内在冲突，但它们之间的相互关系尚未得到最终调查。例如，尚不确定是否存在理论上的保证，即保留某些图属性足以保持GNN性能，或者相反。
性能与效率权衡：在应用程序的探索中，我们不可避免地面临一个关键而微妙的问题：如何确定缩合图的规模以满足GC的预定义目的？虽然一些现有的方法已经认识到有效性和效率之间的权衡，但我们认为有效性和效率都应该全面地包括在权衡框架中。这对于指定GC的效用并将其应用范围扩展到更实际的场景至关重要。通过考虑这两个方面，我们可以更好地理解GC技术的优点和局限性，并对它们在实际环境中的适用性做出明智的决策。

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2024-02-09，如有侵权请联系 cloudcommunity@tencent.com 删除

优化