REVIEW 2 major objections 5 minor 32 references
Does Graph Compression Preserve Signal Propagation?
T0 review · 2 major / 5 minor · reviewed 2026-07-31 · deepseek-v4-flash
Pith's one-line read Under graph compression, preserving signal diversity and preserving propagation fidelity are empirically at odds: sparsification keeps signals diverse but drifts off-course, while coarsening stays faithful but over-smooths.
desk verdict Useful empirical lens, but the coarsening rank-collapse claim is partly baked into the lifting, so the central tension needs a revision before it fully holds. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The argument rests on comparing three signal-level metrics over propagation depth: the Dirichlet energy ratio $R(k)$ (smoothness relative to initial energy), the relative Frobenius deviation $\Delta k$ between compressed and original propagated signals, and the numeric rank of the signal matrix (effective signal dimensionality). Signals are propagated by repeated application of the symmetric normalized adjacency with self-loops, $Y(k) = \tilde{A}^k X$; coarsened signals are lifted back to the original node space via the transpose of the cluster-assignment matrix so that all metrics are computed on a common node set.
What would settle it
Run the same three metrics while matching compression by effective graph size or by spectral change instead of by rate r; if coarsening and sparsification no longer show opposite behavior, the claimed tension is an artifact of the ratio-matching premise.
Extended reading notes
Core claim
The paper claims that coarsening and sparsification fail in opposite, complementary ways when judged by how they propagate node features. Repeated application of the normalized adjacency operator on a coarsened graph (nodes merged into supernodes) closely reproduces the original signal trajectory, but at the cost of faster energy decay and lower numeric rank — i.e., stronger oversmoothing. On a sparsified graph (edges pruned), signals retain higher rank and higher Dirichlet energy relative to baseline, resisting oversmoothing, but the propagated signals deviate from the original trajectory increasingly with depth. Because both effects appear consistently across methods within each paradigm,
Load-bearing premise
The comparison assumes that pruning r percent of edges and merging r percent of nodes are comparable compression budgets, and that lifting coarsened signals via the transpose of the cluster-assignment matrix gives a fair rank comparison; the paper concedes the first point explicitly.
Editorial extensions
If this is right
- Applications that need the compressed graph to reproduce the original mixing of information should favor coarsening, provided the graph is sufficiently connected and clusters stay balanced.
- Applications that need diverse node representations should favor sparsification, accepting that the trajectory diverges from the original graph.
- Evaluation protocols that assess compression quality only through oversmoothing metrics (e.g., Dirichlet energy) can be misleading: a method that looks good on energy may be far from the original propagation, and vice versa.
- High-rate coarsening on dense graphs can reverse the fidelity advantage, so coarse cluster balance is a necessary condition, not a detail.
- Unstructured sparsification can inflate rank metrics through disconnection rather than genuine signal diversity, so rank results should be read alongside connectivity statistics.
Reading between the lines
- A direct test of the paper's premise: re-run the comparison matching compression by effective graph size or spectral change rather than equal rates; if the tension weakens, the claimed duality may be an artifact of ratio matching.
- The C^T lifting of coarsened signals makes some rank collapse unavoidable; a lift that projects onto the coarse signal subspace might yield different rank conclusions and is worth testing.
- A hybrid strategy — mild sparsification to retain diversity plus balanced coarsening to retain fidelity — is a natural next step the paper does not explore.
- The findings imply that compression research should report both a trajectory-fidelity metric and a diversity metric; single-number benchmarks on downstream tasks likely hide the trade-off.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper empirically compares two graph-compression paradigms—coarsening (NOPE, Heavy Edge Matching, Variation Neighborhoods) and sparsification (TEDDY, Local Degree, Random Edge)—across five datasets, three compression rates, and five propagation depths. Using three metrics (Dirichlet energy ratio, relative Frobenius deviation, and numeric rank), it claims a consistent dual failure mode: sparsification better preserves signal diversity and mitigates oversmoothing but increasingly diverges from the original propagation trajectory, while coarsening more faithfully follows the original trajectory but causes stronger smoothing and rank collapse. The authors argue that signal-diversity preservation and propagation fidelity are distinct, competing evaluation objectives under compression. The paper is transparent about caveats, including Pubmed/Heavy Edge reversal, Random Edge disconnection artifacts, and the unequal meaning of the compression rate r across families.
Significance. If the central claim holds, the paper provides a useful empirical map of a previously underexplored trade-off in graph compression evaluation. Its strengths include a clear experimental protocol, open code and results, multiple datasets and methods, and a willingness to report exceptions rather than smoothing them over. The claim that oversmoothing-oriented metrics and trajectory-fidelity metrics can rank compression methods differently is potentially impactful for how graph compression is evaluated. However, the central tension rests on two load-bearing methodological choices—the C^T lifting for coarsened rank and the cross-family meaning of r—and the rank evidence is partly structurally forced.
major comments (2)
- [§III-D3, Eq. (7) with Eq. (2)] The rank-collapse evidence for coarsening is partly guaranteed by the lifting construction. Since Y_m^{(k)} = C^T Y_c^{(k)} and C^T is an N×N' matrix of rank N'=(1-r)N, rank(Y_m^{(k)}) ≤ N' for every depth k. At r=0.7, for datasets where d>N' (Cora, Citeseer, DBLP, Amazon), the coarsened rank is numerically capped below the baseline even at k=0; thus 'rank falls below baseline at all depths' does not solely measure propagation-induced oversmoothing. The paper neither reports k=0 rank nor normalizes rank by N' (or by baseline rank), so the 'rank collapse' half of the central tension is not yet established. Please quantify the contribution of the lifting cap, report k=0 values, and demonstrate that the depth-dependent decay beyond k=0 is significant after accounting for this representational reduction.
- [§IV-C, §III-E] The cross-family comparison defines r as fraction of nodes merged (coarsening) versus fraction of edges pruned (sparsification). The paper concedes these are 'matched budgets rather than equivalent structural changes,' but the abstract's general conclusion ('coarsening ... rank collapse; sparsification ... higher diversity') depends on this specific calibration. On dense graphs, r=0.7 removes 70% of nodes in one family and only 70% of edges in the other, leaving very different effective graph sizes; the observed rank or deviation gaps could reflect graph-size disparity rather than paradigm differences. Please add at least one alternative matching—for example, equal remaining node/edge counts, equal spectral change, or equal effective size—to show the diversity–fidelity tension is robust to the budget definition.
minor comments (5)
- [§III-D1, Eq. (5)] Clarify whether E(0) for compressed signals is the compressed signal's own initial energy or the baseline's initial energy. This affects whether DE ratios are comparable across coarsening and sparsification, and the current text is ambiguous.
- [Fig. 2 / §IV-A] The DE ratio exceeding 1 (e.g., Heavy Edge Matching on Pubmed at r=0.7) is statistically surprising: propagation increases Dirichlet energy. A short explanation of this amplification mechanism and whether it is specific to HE's cluster-size imbalance would improve readability.
- [§II, §IV-A] Reference inconsistency: the text labels 'Heavy Edge Matching [5]' in the experimental setup and 'Variation Neighborhoods [5]', but Heavy Edge Matching is originally [18] (Karypis & Kumar). Please correct the in-text citations to match the bibliography.
- [§IV-A, §IV-B] Use decimal notation consistently: 'r=70%' should be 'r=0.7' as defined in §III-E; the mixed notation is confusing when comparing rates.
- [§IV-B] The Random Edge caveat (8,980 singletons on Pubmed at r=0.7) is disclosed, but the category-level claim 'sparsification preserves higher rank' still includes this partly artifactual result. Consider reporting the rank analysis restricted to the largest connected component as a robustness check, so the diversity claim does not rely on disconnection artifacts.
Circularity Check
Coarsening's rank-collapse result is partially forced by the C^T lifting: Eq. (2) caps NumRank at N'=(1-r)N before any propagation.
-
self definitional
[Eq. (2) in Sec. III.C.1; Eq. (7) in Sec. III.D.3; claim in Sec. IV.A]
"Since the coarsened graph operates in a reduced node space, direct comparison with the original baseline is not straightforward. We therefore map the coarse signal back to the original node space by applying the transpose of C: Y_m^(k) = C^T Y_c^(k). (2) ... NumRank = ||Y_cmp^(k)||_F^2 / ||Y_cmp^(k)||_2^2, Y_cmp = ... Y_m coarsening (7) ... For coarsening-based methods, both metrics are measured in the original node space after lifting through C^T, making them directly comparable across compression categories."
By Eq. (2), the coarsened signal compared in the original node space is Y_m^(k) = C^T Y_c^(k), where C^T is N x N' with N'=(1-r)N. Therefore rank(Y_m^(k)) <= N' for every depth k, independently of propagation dynamics. Eq. (7) then feeds exactly this lifted matrix into NumRank, so the measured coarsened rank is capped by the reduced node count before any message passing occurs. In settings where the baseline NumRank exceeds N' (e.g., Cora and Citeseer at r=0.7), the reported finding 'the numeric rank fall below the baseline at all depths and rates' is guaranteed by the lifting construction at k=0, not discovered through propagation. The paper does not report k=0 rank or rank normalized by the cap, and its assertion that lifting 'mak[es] them directly comparable across compression categorie
full rationale
This is an empirical measurement study rather than a fitted-parameter prediction, so there is no fitting-a-prediction circularity. The paper's citations are external prior works, not load-bearing self-citations. The main construction-level issue is the coarsened rank metric: Eq. (2) defines the comparison signal as Y_m = C^T Y_c, and Eq. (7) measures NumRank on that lifted matrix. Since C^T has rank at most N'=(1-r)N, the coarsened rank is bounded by the supernode count before propagation, making at least part of the observed rank collapse a representational artifact rather than an empirical discovery. This weakens the abstract's claim that coarsening suffers 'rank collapse' as a propagation cost, because the collapse is partly baked into the lifting step. The other two metrics (Dirichlet energy ratio and deviation) are not similarly forced: they are computed from actual propagated signals and retain independent empirical content, and the paper explicitly acknowledges a related artifact for sparsification ('its apparent rank advantage can be partly considered an artifact of disconnection'). The cross-family budget comparison is also explicitly conceded as 'matched budgets rather than equivalent structural changes,' which is a limitation but not a hidden circular step. Overall, the central diversity-fidelity tension has substantial independent evidence, but one load-bearing pillar—coarsening-induced rank collapse—is partially circular by construction, warranting a score of 6.
Assumptions & free parameters
assumptions (5)
- domain assumption Repeated application of the symmetric normalized adjacency matrix with self-loops (Eq. 1) is an adequate model of signal propagation.
- domain assumption Dirichlet energy ratio R(k) is a meaningful measure of oversmoothing under compression.
- domain assumption Numeric rank (NumRank) is a meaningful measure of signal diversity independent of scale.
- ad hoc to paper Upsampling coarsened signals by C^T (Eq. 2) yields a fair comparison with the original node-space signal.
- ad hoc to paper Compression rate r is comparable across coarsening and sparsification for the cross-family comparison.
Cite this review
Pith. "Pith review of Does Graph Compression Preserve Signal Propagation?." pith.science (2026). https://pith.science/paper/BRDWNM6W
@misc{pith2026260723338,
author = {Pith},
title = {Pith review of: Does Graph Compression Preserve Signal Propagation?},
year = {2026},
howpublished = {\url{https://pith.science/paper/BRDWNM6W}},
note = {Machine review of arXiv:2607.23338}
}
read the original abstract
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
Figures
Reference graph
Works this paper leans on
-
[1]
A unifying framework for spectrum-preserving graph sparsification and coarsening,
G. Bravo Hermsdorff and L. Gunderson, “A unifying framework for spectrum-preserving graph sparsification and coarsening,”Advances in Neural Information Processing Systems, vol. 32, 2019
2019
-
[2]
A comprehensive study on large-scale graph training: Bench- marking and rethinking,
K. Duan, Z. Liu, P. Wang, W. Zheng, K. Zhou, T. Chen, X. Hu, and Z. Wang, “A comprehensive study on large-scale graph training: Bench- marking and rethinking,”Advances in Neural Information Processing Systems, vol. 35, pp. 5376–5389, 2022
2022
-
[3]
DSpar: An embarrassingly simple strategy for efficient GNN training and inference via degree-based sparsification,
Z. Liu, K. Zhou, Z. Jiang, L. Li, R. Chen, S.-H. Choi, and X. Hu, “DSpar: An embarrassingly simple strategy for efficient GNN training and inference via degree-based sparsification,”Transactions on Machine Learning Research, 2023
2023
-
[4]
Learning to reduce the scale of large graphs: A comprehensive survey,
H. Xu, L. Zhang, Y . Ma, S. Zhou, Z. Zheng, and J. Bu, “Learning to reduce the scale of large graphs: A comprehensive survey,”ACM Transactions on Knowledge Discovery from Data, vol. 19, no. 5, pp. 1–25, 2025
2025
-
[5]
Graph reduction with spectral and cut guarantees,
A. Loukas, “Graph reduction with spectral and cut guarantees,”Journal of Machine Learning Research, vol. 20, no. 116, pp. 1–42, 2019
2019
-
[6]
Spectrally approximating large graphs with smaller graphs,
A. Loukas and P. Vandergheynst, “Spectrally approximating large graphs with smaller graphs,” inProceedings of the International Conference on Machine Learning. PMLR, 2018, pp. 3237–3246
2018
-
[7]
Graph sparsification via mixture of graphs,
G. Zhang, X. Sun, Y . Yue, C. Jiang, K. Wang, T. Chen, and S. Pan, “Graph sparsification via mixture of graphs,” inInternational Conference on Learning Representations, vol. 2025, 2025, pp. 92 735–92 763
2025
-
[8]
Structure-preserving sparsification of social networks,
G. Lindner, C. L. Staudt, M. Hamann, H. Meyerhenke, and D. Wagner, “Structure-preserving sparsification of social networks,” inProceedings of the 2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining 2015, 2015, pp. 448–454
2015
Show all 32 references
-
[9]
Does graph distillation see like vision dataset counterpart?
B. Yang, K. Wang, Q. Sun, C. Ji, X. Fu, H. Tang, Y . You, and J. Li, “Does graph distillation see like vision dataset counterpart?”Advances in Neural Information Processing Systems, vol. 36, pp. 53 201–53 226, 2023
2023
-
[10]
GC4NC: A benchmark framework for graph condensation on node classification with new insights,
S. Gong, J. Ni, N. Sachdeva, C. Yang, and W. Jin, “GC4NC: A benchmark framework for graph condensation on node classification with new insights,”Advances in Neural Information Processing Systems, vol. 38, 2026
2026
-
[11]
UGC: Universal graph coarsening,
M. Kataria, S. Kumaret al., “UGC: Universal graph coarsening,”Ad- vances in Neural Information Processing Systems, vol. 37, pp. 63 057– 63 081, 2024
2024
-
[12]
Semi-supervised classification with graph convolutional networks,
T. N. Kipf and M. Welling, “Semi-supervised classification with graph convolutional networks,” inProceedings of The International Conference on Learning Representations, 2017
2017
-
[13]
Graph coarsening with message-passing guar- antees,
A. Joly and N. Keriven, “Graph coarsening with message-passing guar- antees,”Advances in Neural Information Processing Systems, vol. 37, pp. 114 902–114 927, 2024
2024
-
[14]
A note on over-smoothing for graph neural networks,
C. Cai and Y . Wang, “A note on over-smoothing for graph neural networks,” inProceedings of The 37th International Conference on Machine Learning. PMLR, 2020
2020
-
[15]
Graph neural networks exponentially lose expressive power for node classification,
K. Oono and T. Suzuki, “Graph neural networks exponentially lose expressive power for node classification,” inInternational Conference on Learning Representations, 2020
2020
-
[16]
A survey on oversmooth- ing in graph neural networks,
T. K. Rusch, M. M. Bronstein, and S. Mishra, “A survey on oversmooth- ing in graph neural networks,”arXiv preprint arXiv:2303.10993, 2023
2023 arXiv
-
[17]
A comprehensive survey on graph reduction: Sparsification, coarsening, and condensation,
M. Hashemi, S. Gong, J. Ni, W. Fan, B. A. Prakash, and W. Jin, “A comprehensive survey on graph reduction: Sparsification, coarsening, and condensation,” inProceedings of the Thirty-Third International Joint Conference on Artificial Intelligence, 2024, pp. 8058–8066
2024
-
[18]
A fast and high quality multilevel scheme for partitioning irregular graphs,
G. Karypis and V . Kumar, “A fast and high quality multilevel scheme for partitioning irregular graphs,”SIAM Journal on Scientific Computing, vol. 20, no. 1, pp. 359–392, 1998
1998
-
[19]
Rethinking efficient graph coarsening via a non-selfishness principle,
X. Bai, B. Lu, K. Zhang, S. Chen, X. Wang, C. Zhou, and M. Jin, “Rethinking efficient graph coarsening via a non-selfishness principle,” inProceedings of The International Conference on Machine Learning. PMLR, 2026
2026
-
[20]
A general framework for graph sparsification,
W. S. Fung, R. Hariharan, N. J. Harvey, and D. Panigrahi, “A general framework for graph sparsification,” inProceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, 2011, pp. 71–80
2011
-
[21]
Spectral sparsification of graphs,
D. A. Spielman and S.-H. Teng, “Spectral sparsification of graphs,” SIAM Journal on Computing, vol. 40, no. 4, pp. 981–1025, 2011
2011
-
[22]
Local graph sparsification for scalable clustering,
V . Satuluri, S. Parthasarathy, and Y . Ruan, “Local graph sparsification for scalable clustering,” inProceedings of the 2011 ACM SIGMOD International Conference on Management of Data, 2011, pp. 721–732
2011
-
[23]
TEDDY: Trimming edges with degree- based discrimination strategy,
H. Seo, J. Yun, and E. Yang, “TEDDY: Trimming edges with degree- based discrimination strategy,” inProceedings of The Twelfth Interna- tional Conference on Learning Representations, 2024
2024
-
[24]
Deeper insights into graph convolutional networks for semi-supervised learning,
Q. Li, Z. Han, and X.-M. Wu, “Deeper insights into graph convolutional networks for semi-supervised learning,” inProceedings of the AAAI Conference on Artificial Intelligence, vol. 32, no. 1, 2018
2018
-
[25]
Demystifying over- smoothing in attention-based graph neural networks,
X. Wu, A. Ajorlou, Z. Wu, and A. Jadbabaie, “Demystifying over- smoothing in attention-based graph neural networks,”Advances in Neural Information Processing Systems, vol. 36, pp. 35 084–35 106, 2023
2023
-
[26]
Are we measuring oversmoothing in graph neural networks correctly?
K. Zhang, P. Deidda, D. J. Higham, and F. Tudisco, “Are we measuring oversmoothing in graph neural networks correctly?” inProceedings of the International Conference on Learning Representations, 2026
2026
-
[27]
Dirichlet energy constrained learning for deep graph neural networks,
K. Zhou, X. Huang, D. Zha, R. Chen, L. Li, S.-H. Choi, and X. Hu, “Dirichlet energy constrained learning for deep graph neural networks,” Advances in Neural Information Processing Systems, vol. 34, pp. 21 834–21 846, 2021
2021
-
[28]
TINED: GNNs-to-MLPs by teacher injection and dirichlet energy distillation,
Z. Zhou, Z. Ding, J. Shi, L. Qing, and S. Shen, “TINED: GNNs-to-MLPs by teacher injection and dirichlet energy distillation,” inInternational Conference on Machine Learning. PMLR, 2025, pp. 78 616–78 632
2025
-
[29]
Sampling from large matrices: An approach through geometric functional analysis,
M. Rudelson and R. Vershynin, “Sampling from large matrices: An approach through geometric functional analysis,”Journal of the ACM (JACM), vol. 54, no. 4, pp. 21–es, 2007
2007
-
[30]
Revisiting semi-supervised learning with graph embeddings,
Z. Yang, W. Cohen, and R. Salakhudinov, “Revisiting semi-supervised learning with graph embeddings,” inProceedings of The International Conference on Machine Learning. PMLR, 2016, pp. 40–48
2016
-
[31]
Deep gaussian embedding of graphs: Unsupervised inductive learning via ranking,
A. Bojchevski and S. G ¨unnemann, “Deep gaussian embedding of graphs: Unsupervised inductive learning via ranking,” inInternational Conference on Learning Representations, 2018
2018
-
[32]
Pitfalls of graph neural network evaluation,
O. Shchur, M. Mumme, A. Bojchevski, and S. G ¨unnemann, “Pitfalls of graph neural network evaluation,”arXiv preprint arXiv:1811.05868, 2018
2018 arXiv
Reviewed July 31, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.