轻量级拓扑比对算法，快速分析加权图的结构差异
RTD-Lite: Scalable Topological Analysis for Comparing Weighted Graphs in Learning Tasks
- 基于辅助图的最小生成树捕捉两图拓扑差异
- 时间复杂度仅O(n²)，显著提速传统方法
- 适合需要保留图结构的神经网络训练场景
加权图的拓扑比较在各类学习任务中具有重要价值，但现有方法在大规模数据上计算效率低下。本文提出RTD-Lite，一种可扩展的算法，能够高效比较两个顶点一一对应加权图在任意尺度下的连通性或聚类结构。通过辅助图中的最小生成树，该方法实现O(n²)的时间和空间复杂度。实验表明，RTD-Lite在合成与真实数据集上均能有效识别拓扑差异，并大幅降低计算耗时。进一步地，将RTD-Lite作为神经网络训练中的损失项，可增强学习表示中拓扑结构的保持能力。代码已公开于https://github.com/ArGintum/RTD-Lite。
原文摘要 · Abstract (English)
Topological methods for comparing weighted graphs are valuable in various learning tasks but often suffer from computational inefficiency on large datasets. We introduce RTD-Lite, a scalable algorithm that efficiently compares topological features, specifically connectivity or cluster structures at arbitrary scales, of two weighted graphs with one-to-one correspondence between vertices. Using minimal spanning trees in auxiliary graphs, RTD-Lite captures topological discrepancies with $O(n^2)$ time and memory complexity. This efficiency enables its application in tasks like dimensionality reduction and neural network training. Experiments on synthetic and real-world datasets demonstrate that RTD-Lite effectively identifies topological differences while significantly reducing computation time compared to existing methods. Moreover, integrating RTD-Lite into neural network training as a loss function component enhances the preservation of topological structures in learned representations. Our code is publicly available at https://github.com/ArGintum/RTD-Lite
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。