# Does Graph Compression Preserve Signal Propagation?

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 21 of its 31 references that are in the map.
- First posted on arXiv 25 Jul 2026.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [Pitfalls of Graph Neural Network Evaluation](https://mlsanity.com/paper/1811.05868/) (2018)
- [Revisiting Semi-Supervised Learning with Graph Embeddings](https://mlsanity.com/paper/1603.08861/) (2016)
- [Deep Gaussian Embedding of Graphs: Unsupervised Inductive Learning via Ranking](https://mlsanity.com/paper/1707.03815/) (2017)
- [A Note on Over-Smoothing for Graph Neural Networks](https://mlsanity.com/paper/2006.13318/) (2020)
- [A Survey on Oversmoothing in Graph Neural Networks](https://mlsanity.com/paper/2303.10993/) (2023)
- [Dirichlet Energy Constrained Learning for Deep Graph Neural Networks](https://mlsanity.com/paper/2107.02392/) (2021)
- [A Comprehensive Survey on Graph Reduction: Sparsification, Coarsening, and Condensation](https://mlsanity.com/paper/2402.03358/) (2024)
- [Spectrally approximating large graphs with smaller graphs](https://mlsanity.com/paper/1802.07510/) (2018)
- [A Comprehensive Study on Large-Scale Graph Training: Benchmarking and Rethinking](https://mlsanity.com/paper/2210.07494/) (2022)
- [Does Graph Distillation See Like Vision Dataset Counterpart?](https://mlsanity.com/paper/2310.09192/) (2023)
- [A Unifying Framework for Spectrum-Preserving Graph Sparsification and Coarsening](https://mlsanity.com/paper/1902.09702/) (2019)
- [Graph Sparsification via Mixture of Graphs](https://mlsanity.com/paper/2405.14260/) (2024)
- [Graph Coarsening with Message-Passing Guarantees](https://mlsanity.com/paper/2405.18127/) (2024)
- [GC4NC: A Benchmark Framework for Graph Condensation on Node Classification with New Insights](https://mlsanity.com/paper/2406.16715/) (2024)
- [Are We Measuring Oversmoothing in Graph Neural Networks Correctly?](https://mlsanity.com/paper/2502.04591/) (2025)
- [TINED: GNNs-to-MLPs by Teacher Injection and Dirichlet Energy Distillation](https://mlsanity.com/paper/2412.11180/) (2024)
- [TEDDY: Trimming Edges with Degree-based Discrimination strategY](https://mlsanity.com/paper/2402.01261/) (2024)
- [Structure-Preserving Sparsification of Social Networks](https://mlsanity.com/paper/1505.00564/) (2015)
- [Rethinking Efficient Graph Coarsening via a Non-Selfishness Principle](https://mlsanity.com/paper/2605.13021/) (2026)

## Abstract (arXiv)

Graph compression reduces the computational cost of graph learning, but its effect on signal propagation remains largely underexplored. Existing work evaluates compression through downstream task performance or structural preservation, neither of which directly captures how propagation dynamics change after compression. We study two fundamental compression paradigms, coarsening and sparsification, and ask whether they preserve the propagation behavior of the original graph. Across five datasets, varying compression rates, and propagation depths, we measure signal behavior through three complementary metrics. Our results reveal a consistent tension between the two compression families. Sparsification retains higher signal diversity and mitigates oversmoothing, but its propagation trajectory progressively diverges from that of the original graph. Coarsening more faithfully preserves propagation behavior, but at the cost of stronger smoothing and rank collapse. These findings demonstrate that two propagation-centric objectives, preserving signal diversity and preserving propagation fidelity, are distinct and empirically at odds under graph compression, highlighting the need for evaluation protocols that jointly consider both dimensions. The code and results are available at: https://github.com/KawshikBanerjee/Compression-Propagation-Duality