通过联合粒度拓扑保持实现无训练的图压缩

《Neurocomputing》：Training-free graph condensation via joint-granularity topology preservation

　　

摘要

图压缩（GC）通过合成紧凑的图来缓解图神经网络的瓶颈问题。然而，现有方法存在内存溢出的风险或忽视了全局结构连续性。我们提出联合粒度拓扑保持（JGTP），一个高效的免训练框架。JGTP利用密度峰值偏序机制锚定全局宏观主干，同时通过局部最优传输并结合融合Gromov-Wasserstein（FGW）距离来强制微观拓扑对齐。这一双重方法可扩展地保持联合特征-结构分布。在七个数据集上的大量实验验证了JGTP相比最先进基线的优越分类准确率。严格的理论证明验证了所提出的框架，而统计检验确认了这些改进的显著性。代码可在https://github.com/kjwwwwww/JGTP获取。

引言

图神经网络（GNN）在非欧几里得数据的节点分类和链接预测中取得了显著成功[1]。然而，现实网络的快速增长——通常包含数百万节点——在GNN训练过程中造成了严重的内存瓶颈和计算延迟[2]，[3]。为了缓解这一可扩展性挑战并使GNN能够在资源受限的环境中部署，图压缩（GC）作为一种高效的数据中心范式应运而生[4]，[5]，[6]。通过将宏观原图合成为微观、信息密集的对等图，GC使模型能够在大幅降低训练开销和存储足迹的同时保持有竞争力的预测性能。

然而，现有GC方法难以保持固有的拓扑层次和联合粒度动态，导致两个关键局限性。首先，它们存在结构偏序丧失的问题。例如，连续优化范式（如GCond [7]、SFGC [8]）依赖端到端梯度匹配，这实际上将联合粒度图扁平化为单一连续空间。这种方法损害了结构透明性，并通过合成密集、不可解释的图无意中加剧了边复杂性。其次，它们表现出明显的局部结构偏差。具体而言，近期免训练的离散采样方法（如Bonsai [9]）基于静态选择指标贪婪地聚合高分节点，将GC简化为孤立的子集提取问题。正如GNN结构瓶颈研究[10]所揭示的，忽视全局拓扑流形从根本上忽略了图生成过程中施加于全局网络的动态结构扰动，从而限制了信息流（表1）。

为了应对这些挑战，本文提出联合粒度拓扑保持（JGTP），这是一个新颖的拓扑感知动态GC框架，协同整合了粗粒度宏观拓扑提取与细粒度微观拓扑对齐。所提方法有效保持了原图的固有层次特征——这一结构必要性被广泛认为是稳健图表示学习的关键[17]——同时在离散拓扑生长过程中保持严格的数学偏序。在宏观层面，我们引入了基于密度峰值的偏序机制[18]，以建立结构枢纽的严格层次，有效锚定原图主干并防止结构崩溃。在微观层面，我们提出将融合Gromov-Wasserstein（FGW）距离[19]集成为局部动态拓扑评估器，在任何节点正式挂载到压缩图上之前，严格量化并最小化联合结构-特征信息损失。

我们的贡献可以总结如下：

• •
  我们提出基于密度峰值偏序机制的宏观拓扑提取模块。通过自适应锚定高密度结构枢纽，该模块建立了节点重要性的严格层次，有效规避了静态启发式采样固有的局部拓扑短视。
• •
  我们通过由FGW距离驱动的局部动态评估机制实现了细粒度微观拓扑对齐。这种可处理的最优传输（OT）适应性保证了显式的联合特征-结构正则化，克服了局部特征过平滑问题，同时保持线性时间、免训练的效率。
• •
  进行了多级系统分析以验证JGTP的有效性：1）严格的理论推导为其性能优势提供坚实的理论支持；2）在七个代表性图数据集的节点分类任务中取得了极具竞争力的性能；3）通过成对检验验证了性能改进的统计显著性，确认所观察到的增益并非随机波动所致。

章节摘要

相关工作

在本节中，我们回顾了GC的相关工作，重点关注GNN在不同结构粒度上的可扩展性挑战、连续优化与离散采样范式之间的二分性，以及OT理论在联合粒度图学习中的应用。

所提方法

在本节中，我们提出了所提的免训练GC框架，称为JGTP。不同于将图结构扁平化为单一连续或离散空间的现有范式，我们的框架将GC刻画为受严格结构偏序支配的联合粒度拓扑演化过程。我们建立了基于密度峰值的偏序层次作为宏观结构锚点以保留全局主干，同时部署FGW距离作为细粒度的

实验

在本节中，我们介绍了用于评估所提JGTP框架的数据集、对比基线和实验设置。然后我们对节点分类性能进行了全面评估，证明JGTP取得了极具竞争力的结果，并相对于现有连续和离散基线有了实质性改进。此外，我们提供了深入的可视化分析——包括t-SNE和特征相似度热力图——以定性验证结构保真度

结论

在本文中，我们介绍了JGTP，一个新颖的免训练图压缩框架，将离散子集选择公式化为一个数学上有界的、部分有序的拓扑生长过程。JGTP有效整合了两个核心组件：一个基于密度峰值的偏序，在宏观层面显式锚定全局结构主干；以及一个局部FGW对齐，在微观层面动态强制执行严格的联合特征-结构正则化。

CRediT作者贡献声明

Kang Jiawei：撰写—初稿，可视化，验证，软件，方法论，调查，形式化分析，数据整理。Liu Shijie：撰写—审阅与编辑，验证，调查。Yu Shenao：撰写—审阅与编辑，验证，数据整理。Xu Ji：撰写—审阅与编辑，监督，资源，项目管理，资金获取，概念化。Wang Dexian：撰写—审阅与编辑，监督，资源，项目管理，资金

利益冲突声明

作者声明他们没有已知的可能影响本文所报告工作的竞争性经济利益或个人关系。

Kang Jiawei于2025年获得中国贵州大学计算机科学与技术学院计算机科学与技术学士学位。目前是贵州大学公共大数据国家重点实验室的研究生。他当前的研究兴趣包括机器学习和粒度计算。

Kang Jiawei|Liu Shijie|Yu Shenao|Xu Ji|Wang Dexian|Li Tianrui

贵州大学公共大数据国家重点实验室，中国贵阳，550025