Pith. sign in

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 →

arxiv 2607.23338 v1 pith:BRDWNM6W submitted 2026-07-25 cs.LG

classification cs.LG
keywords graphcompressioncoarseningsparsificationoversmoothingsignalpropagationDirichletenergyrankcollapselearning
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper argues that graph compression cannot be judged by a single propagation-centric objective. Across five datasets, it shows that two objectives — preserving signal diversity (resisting oversmoothing) and preserving propagation fidelity (matching the original graph's signal trajectory) — pull in opposite directions depending on whether nodes are merged (coarsening) or edges are pruned (sparsification). Coarsening tracks the original propagation closely but collapses representation rank; sparsification keeps representations diverse but its propagated signals diverge from the original as depth grows. If right, this means evaluation of compressed graphs should jointly measure both dimensions, not just oversmoothing metrics.

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.

Watch

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

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

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)
  1. [§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.
  2. [§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)
  1. [§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.
  2. [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.
  3. [§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.
  4. [§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.
  5. [§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

1 steps flagged · score 6.0 of 10

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.

  1. 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 0 free parameters · 5 assumptions · 0 invented entities

No free parameters are fitted to produce the reported trends; compression rates are experimental settings. The paper relies on standard metrics and on two assumptions specific to its comparison protocol: the C^T lifting for coarsening and the comparability of r across paradigms. No new entities are introduced.

assumptions (5)
  • domain assumption Repeated application of the symmetric normalized adjacency matrix with self-loops (Eq. 1) is an adequate model of signal propagation.
    Adopted from [12]; it is a standard but specific propagation model and not justified from first principles in this paper.
  • domain assumption Dirichlet energy ratio R(k) is a meaningful measure of oversmoothing under compression.
    Follows [14], [27], [28]; accepted in the oversmoothing literature but not validated for compressed graphs here.
  • domain assumption Numeric rank (NumRank) is a meaningful measure of signal diversity independent of scale.
    Follows [29]; the paper uses it to compare compressed and uncompressed signals, but for coarsening the value is bounded by the lifting construction.
  • ad hoc to paper Upsampling coarsened signals by C^T (Eq. 2) yields a fair comparison with the original node-space signal.
    This lifting assigns identical features to all nodes in a supernode; it is necessary for comparison but is not justified and mechanically caps the rank of the coarsened signal.
  • ad hoc to paper Compression rate r is comparable across coarsening and sparsification for the cross-family comparison.
    The paper explicitly concedes in Section IV-C that matched ratios are matched budgets, not equivalent structural changes, yet the central tension is stated across the two families at the same numeric r.

how reviews work

0 comments
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

Figures reproduced from arXiv: 2607.23338 by the authors.

Figure 1
Figure 1. Deviation from baseline comparison across compression methods, compression ratios, and datasets. [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Dirichlet energy ratio comparison across compression methods, compression ratios, and datasets. [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Numeric rank comparison across compression methods, compression ratios, and datasets. [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

32 extracted references · 2 linked inside Pith

  1. [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

  2. [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

  3. [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

  4. [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

  5. [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

  6. [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

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

  8. [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

Show all 32 references
  1. [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

  2. [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

  3. [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

  4. [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

  5. [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

  6. [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

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

  8. [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

  9. [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

  10. [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

  11. [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

  12. [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

  13. [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

  14. [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

  15. [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

  16. [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

  17. [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

  18. [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

  19. [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

  20. [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

  21. [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

  22. [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

  23. [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

  24. [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

Pith tools

Reviewed July 31, 2026 · model on record in the stance chip above.