mlsanityData to 7 Oct 2026

Scalable Topology-Preserving Graph Coarsening: Concepts and Algorithms

arXiv 2601.22943 ↗First posted 30 Jan 2026cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 28 of its 54 references that are in the map. First posted on arXiv 30 Jan 2026.

Builds on

28 of 54 references.

References · 28

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  2. 2017Inductive Representation Learning on Large Graphscited by 6,284
  3. 2018How Powerful are Graph Neural Networks?cited by 4,355
  4. 2018Predict then Propagate: Graph Neural Networks meet Personalized PageRankcited by 987
  5. 2019GraphSAINT: Graph Sampling Based Inductive Learning Methodcited by 618
  6. 2020Adaptive Universal Generalized PageRank Graph Neural Networkcited by 592
  7. 2022Long Range Graph Benchmarkcited by 258
  8. 2021Graph Condensation for Graph Neural Networkscited by 150
  9. 2021A Unified Lottery Ticket Hypothesis for Graph Neural Networkscited by 118
  10. 2021Topological Graph Neural Networkscited by 86
  11. 2021Scaling Up Graph Neural Networks Via Graph Coarseningcited by 80
  12. 2018Spectrally approximating large graphs with smaller graphscited by 56
16 more
  1. 2021Graph Coarsening with Neural Networkscited by 55
  2. 2021Link Prediction with Persistent Homology: An Interactive Viewcited by 37
  3. 2019A Unifying Framework for Spectrum-Preserving Graph Sparsification and Coarseningcited by 31
  4. 2021Topological Relational Learning on Graphscited by 27
  5. 2021Cycle Representation Learning for Inductive Relation Predictioncited by 23
  6. 2023Rethinking Graph Lottery Tickets: Graph Sparsity Matterscited by 23
  7. 2023Going beyond persistent homology using persistent homologycited by 21
  8. 2024EXGC: Bridging Efficiency and Explainability in Graph Condensationcited by 20
  9. 2022Neural Approximation of Graph Topological Featurescited by 16
  10. 2023Graph Coarsening via Convolution Matching for Scalable Graph Neural Network Trainingcited by 12
  11. 2024A Topology-aware Graph Coarsening Framework for Continual Graph Learningcited by 11
  12. 2024Graph Coarsening with Message-Passing Guaranteescited by 9
  13. 2023Cycle Invariant Positional Encoding for Graph Representation Learningcited by 8
  14. 2023Topological Node2vec: Enhanced Graph Embedding via Persistent Homologycited by 5
  15. 2015Efficient Computation of the Characteristic Polynomial of a Threshold Graphcited by 1
  16. 2022Tight basis cycle representatives for persistent homology of large data setscited by 1

Built on by

Not cited yet.