# Scalable Topology-Preserving Graph Coarsening: Concepts and Algorithms

arXiv: https://arxiv.org/abs/2601.22943 · HTML: https://mlsanity.com/paper/2601.22943/

## Key facts

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

## Builds on (most cited first, 28 of 28)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [GraphSAINT: Graph Sampling Based Inductive Learning Method](https://mlsanity.com/paper/1907.04931/) (2019)
- [Adaptive Universal Generalized PageRank Graph Neural Network](https://mlsanity.com/paper/2006.07988/) (2020)
- [Long Range Graph Benchmark](https://mlsanity.com/paper/2206.08164/) (2022)
- [Graph Condensation for Graph Neural Networks](https://mlsanity.com/paper/2110.07580/) (2021)
- [A Unified Lottery Ticket Hypothesis for Graph Neural Networks](https://mlsanity.com/paper/2102.06790/) (2021)
- [Topological Graph Neural Networks](https://mlsanity.com/paper/2102.07835/) (2021)
- [Scaling Up Graph Neural Networks Via Graph Coarsening](https://mlsanity.com/paper/2106.05150/) (2021)
- [Spectrally approximating large graphs with smaller graphs](https://mlsanity.com/paper/1802.07510/) (2018)
- [Graph Coarsening with Neural Networks](https://mlsanity.com/paper/2102.01350/) (2021)
- [Link Prediction with Persistent Homology: An Interactive View](https://mlsanity.com/paper/2102.10255/) (2021)
- [A Unifying Framework for Spectrum-Preserving Graph Sparsification and Coarsening](https://mlsanity.com/paper/1902.09702/) (2019)
- [Topological Relational Learning on Graphs](https://mlsanity.com/paper/2110.15529/) (2021)
- [Cycle Representation Learning for Inductive Relation Prediction](https://mlsanity.com/paper/2110.02510/) (2021)
- [Rethinking Graph Lottery Tickets: Graph Sparsity Matters](https://mlsanity.com/paper/2305.02190/) (2023)
- [Going beyond persistent homology using persistent homology](https://mlsanity.com/paper/2311.06152/) (2023)
- [EXGC: Bridging Efficiency and Explainability in Graph Condensation](https://mlsanity.com/paper/2402.05962/) (2024)
- [Neural Approximation of Graph Topological Features](https://mlsanity.com/paper/2201.12032/) (2022)
- [Graph Coarsening via Convolution Matching for Scalable Graph Neural Network Training](https://mlsanity.com/paper/2312.15520/) (2023)
- [A Topology-aware Graph Coarsening Framework for Continual Graph Learning](https://mlsanity.com/paper/2401.03077/) (2024)
- [Graph Coarsening with Message-Passing Guarantees](https://mlsanity.com/paper/2405.18127/) (2024)
- [Cycle Invariant Positional Encoding for Graph Representation Learning](https://mlsanity.com/paper/2311.14333/) (2023)
- [Topological Node2vec: Enhanced Graph Embedding via Persistent Homology](https://mlsanity.com/paper/2309.08241/) (2023)
- [Efficient Computation of the Characteristic Polynomial of a Threshold Graph](https://mlsanity.com/paper/1503.00617/) (2015)
- [Tight basis cycle representatives for persistent homology of large data sets](https://mlsanity.com/paper/2206.02925/) (2022)

## 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.