提出可扩展的拓扑保持图粗化方法，提升图神经网络训练效率。
Scalable Topology-Preserving Graph Coarsening: Concepts and Algorithms
- 基于代数拓扑思想设计强收缩与边收缩算法，保留图拓扑结构。
- 在多个数据集上实现90%以上节点压缩率，且保持模型性能稳定。
- 适合大规模图神经网络训练加速，尤其适用于资源受限场景。
图粗化能在保留特定性质的前提下减小图的规模。现有方法通常仅保持谱特性或空间特性。近期研究发现，拓扑保持的粗化方法虽能维持图神经网络（GNN）在粗化图上的性能，但存在指数级时间复杂度问题。为此，本文提出可扩展的拓扑保持图粗化（STPGC），引入源自代数拓扑的图强收缩与图边收缩概念。STPGC包含三个新算法：GStrongCollapse、GEdgeCollapse 和 NeighborhoodConing，通过消除冗余节点与边，严格保持拓扑特征。我们进一步证明了STPGC能保留GNN的感受野，并开发近似算法以加速GNN训练。在多个节点分类任务中，STPGC展现出高效性与有效性，最大压缩率达90%以上，同时保证模型精度不变。
原文摘要 · Abstract (English)
Graph coarsening reduces the size of a graph while preserving certain properties. Most existing methods preserve either spectral or spatial characteristics. Recent research shows that topology-preserving coarsening methods maintain GNN performance on coarsened graphs but suffer from exponential time complexity. To address these problems, we propose Scalable Topology-Preserving Graph Coarsening (STPGC) by introducing the concepts of graph strong collapse and graph edge collapse extended from algebraic topology. STPGC comprises three new algorithms, GStrongCollapse, GEdgeCollapse, and NeighborhoodConing based on these two concepts, which eliminate dominated nodes and edges while rigorously preserving topological features. We further prove that STPGC preserves the GNN receptive field and develop approximate algorithms to accelerate GNN training. Experiments on node classification with GNNs demonstrate the efficiency and effectiveness of STPGC.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。