Pith. sign in

REVIEW 5 major objections 3 minor 54 references

Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification

T0 review · 5 major / 3 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read GOKU rewires graphs to reduce over-squashing bottlenecks while keeping the Laplacian spectrum nearly unchanged, by first densifying through inverse spectral sparsification and then sparsifying back to the original edge density.

desk verdict GOKU's densification-sparsification idea is fresh and the experiments are strong, but the spectrum-preservation guarantee rests on an unproved transitivity step and a pointwise-only bound. read the letter →

arxiv 2506.16110 v1 pith:HX47B2U3 submitted 2025-06-19 cs.LG

Langzhang Liang , Fanchen Bu , Zixing Song , Zenglin Xu , Shirui Pan , Kijung Shin This is my paper · ORCID
classification cs.LG MSC 05C5068R10
keywords over-squashinggraphrewiringspectralsparsificationneuralnetworksLaplacianspectrumeffectiveresistancedensification-sparsificationheterophily
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

This paper argues that graph rewiring for over-squashing does not have to sacrifice the graph's spectral fingerprint. It proposes a densification-then-sparsification paradigm (DSR): first add edges that an inverse sparsification process would identify as missing, then prune the densified graph with spectral sparsification. The paper's method, GOKU, claims the output graph is spectrally similar to the input because both are spectral sparsifiers of the same latent graph, while effective resistance between nodes drops and edge density stays equal. Experimental results on ten datasets are presented as evidence that this balance improves node and graph classification accuracy, especially on heterophilic graphs.

What carries the argument

The central object is the Laplacian quadratic form x^T L x together with the (1±ε)-spectral similarity relation. The argument runs through two sampling-based sparsification algorithms: USS (Algorithm 1) assigns low sampling probability to edges that are crucial for connectivity, identified through the Fiedler vector, and ISS (Algorithm 2) samples edges with probability proportional to (1 + feature cosine similarity) × effective resistance. The transitivity statement Go ≈ Gl ≈ G is what carries the spectrum-preservation guarantee, and the same sparsification machinery defines the maximum-likelihood inverse problem solved to construct Gl.

What would settle it

Compute, on a graph rewired by GOKU, the ratio |x^T L_{G_o} x − x^T L_G x| / x^T L_G x over many random vectors x, or the ordered eigenvalue differences, and check whether the values stay within the claimed (1±ε)^2 window; a consistent violation would refute the spectrum-preservation claim.

Watch

Extended reading notes

Core claim

GOKU treats the input graph G as the observed output of an unimportance-based spectral sparsification applied to an unknown latent graph Gl, reconstructs Gl by maximum-likelihood estimation, then applies importance-based spectral sparsification to Gl to obtain the output graph Go. By transitivity of spectral similarity, Go ≈ Gl ≈ G, so the spectrum is explicitly preserved from G to Go. At the same time, densification adds edges with high topological significance (low Fiedler-vector difference and low degree), which lowers effective resistance, and sparsification removes edges with low effective resistance and low feature similarity, so Go is no denser than G.

Load-bearing premise

The load-bearing claim is that the input graph G can be treated as a spectral sparsifier of the reconstructed latent graph Gl, but the actual Gl is built with heuristic approximations and this spectral similarity is never verified.

Editorial extensions

If this is right

  • Graph rewiring no longer has to trade spectral fidelity for connectivity; the same graph can get both, because the output stays spectrally close while effective resistance drops.
  • Heterophilic node-classification datasets (Texas, Cornell, Wisconsin) show the largest gains, suggesting that spectrum-preserving rewiring helps exactly where topology is easily damaged.
  • Training cost stays close to the original because Go has at most as many edges as G, so message passing on the rewired graph is not denser.
  • The densification-sparsification recipe is general: any inverse-sparsification model of an observed graph can seed a rewiring method, not only the Fiedler-vector heuristic used here.

Reading between the lines

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

  • A direct test would measure actual spectral distance between G and Go across all ten datasets; the paper mostly visualizes spectra on a few graphs, so the reader cannot yet confirm the claimed (1±ε)^2 bound empirically.
  • The transitivity guarantee depends on G being a spectral sparsifier of Gl, which is asserted rather than verified; checking that link empirically, for example by comparing quadratic forms on random test vectors, would confirm or break the argument.
  • The Fiedler-vector/degree heuristic for identifying missing edges could be replaced by a learned or curvature-based importance model; the DSR loop is agnostic to that choice.
  • If real graphs are not of the 'sparsified latent graph' form, the recovered edges may optimize the proxy objective without corresponding to genuine missing structure, which would weaken the claim that rewiring recovers the true bottlenecks.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

5 major / 3 minor

Summary. The paper proposes GOKU, a graph rewiring method for mitigating over-squashing in GNNs. GOKU instantiates a densification-sparsification rewiring (DSR) paradigm: it treats the input graph G as a spectral sparsifier of a latent graph Gl, reconstructs Gl by an inverse-sparsification maximum-likelihood procedure, and then applies an effective-resistance-based spectral sparsifier to obtain a sparse output graph Go. The central theoretical claim is that the composition preserves the Laplacian spectrum: since both G and Go are spectral sparsifiers of Gl, transitivity gives Go ≈ Gl ≈ G. The paper reports experiments on ten datasets for node and graph classification, comparisons against six rewiring baselines with GCN, GIN, and GCNII backbones, spectral visualizations, ablations, and complexity analysis. The authors also provide code and claims near-linear-time operation.

Significance. If the central claims were established, this would be a noteworthy contribution: DSR appears to be a novel paradigm that explicitly targets the tension between connectivity improvement, sparsity, and spectral fidelity, and the experimental evaluation is broad and carefully reported. The paper has clear strengths: extensive experiments with multiple backbones and baselines, reproducible code, ablation studies, spectral visualizations, and a transparent discussion of hyperparameter sensitivity. However, the central spectrum-preservation guarantee is not currently supported: the key transitivity step relies on an unverified assumption, and the main theorem proved for densification is only a pointwise statement for a fixed vector. The empirical results may still be valuable, but the theoretical framing overstates what is established.

major comments (5)
  1. [Section 3.1 (Combination)] The central transitivity argument Go ≈ Gl and Gl ≈ G → Go ≈ G rests on the sentence 'Since G is a spectral sparsifier of Gl', which is asserted as fact immediately after Gl is defined as the maximum-likelihood solution. The actual Gl constructed in Section 4.1 is obtained from a heuristic candidate-set construction (2j nodes by Fiedler magnitude and 2j by degree), uniform edge weights, an approximate independent-edge MLE objective (Eq. 3), and an edge-count estimate from Eq. (12). No step verifies that G is a (1±ε)-spectral sparsifier of the Gl that is actually built. Without this premise, the transitivity argument loses its left leg and the spectrum-preservation guarantee collapses. The authors should either prove that the constructed Gl is spectrally similar to G, verify it numerically for their datasets, or explicitly weaken the claimed guarantee.
  2. [Appendix D.1 / Theorem 4.1] Theorem 4.1 does not prove that Algorithm 1 yields spectral sparsifiers. The proof bounds |x^T L̃x - x^T Lx| for a single fixed vector x, with probability at least 3/4 and with the required number q depending on κ(x) for that specific vector. Spectral similarity as defined in Definition 2.1 requires the inequality to hold uniformly for all x ∈ R^n. No epsilon-net argument or union bound is supplied, so the uniform statement is not established. Moreover, κ(x) can be unbounded as p_min → 0, and the probability 3/4 is not a high-probability guarantee. This is a load-bearing gap for the claim that densification 'provably produces spectral sparsifiers'.
  3. [Appendix D.2, Eq. (9)] The inequality in Eq. (9) has the incorrect direction. With p_e ∝ (1+S_e)R_e and S_e ∈ [0,1], the correct bound is p_e ≥ R_e / (2(n−1)), not p_e ≤ R_e / (2(n−1)). The subsequent proof uses the lower bound on p_e to upper-bound ||y||₂; with the printed inequality, the bound ||y||₂ ≤ √(2(n−1)) does not follow. This is likely a typo rather than a fatal error, because the norm bound in the proof uses the correct direction, but it must be fixed for the proof of Theorem 4.2 to be valid.
  4. [Section 4.2 / Algorithms 2 and 3] There is a mismatch between the theorem and the practical algorithm regarding the stopping rule. Section 4.2 states that 'We sample edges until β|E| distinct edges are selected', and the hyperparameter description repeats this ('we keep sampling until β|E| distinct edges are sampled'). However, Algorithm 2 and Algorithm 3 sample exactly q edges with replacement, and Theorem 4.2 guarantees spectral approximation for this fixed-q with-replacement procedure. Adaptive sampling until a fixed number of distinct edges is a stopping rule that changes the sampling distribution, and no argument is provided that it preserves the guarantees of Theorem 4.2. The algorithm, theorem, and implementation description should be aligned.
  5. [Section 4.1 / Appendix E] The derivation of |El|, the number of edges in the latent graph, is inconsistent with the USS sampling distribution. Eq. (12) determines |El| by assuming a uniform edge sampling model, x(1 − (1 − 1/x)^q) = |E|, but Algorithm 1 samples edges nonuniformly with p_e ∝ (deg(u)+deg(v)+1)/|f_u − f_v|. Consequently, the claim in Section 3.2 that the number of added edges is 'derived from a well-established theoretical result rather than being a heuristically chosen value' is not supported as stated. Additionally, the p_e values in Eq. (3) are defined over the latent graph Gd, which is unknown; the practical computation appears to substitute quantities from G without justification. These approximations should be acknowledged explicitly or replaced by a consistent derivation.
minor comments (3)
  1. [Algorithm 1] The sampling probability p_e ∝ (deg(u)+deg(v)+1)/|f_u − f_v| can have a zero denominator when f_u = f_v, and the Fiedler vector is not uniquely defined when the graph is disconnected. The paper does not discuss how these cases are handled.
  2. [Section 4.2] The text says '0.5 < β ≤ 1' in one place and 'β ∈ [0.5, 1.0]' in the hyperparameter description; these are inconsistent.
  3. [Table 5 / Figure 3] The caption and table labels describe the graph scales as '20 edges', '245 edges', and '80352 edges', while the text refers to graphs with 20, 200, and 2000 nodes; the relationship between the node count and the edge-count labels should be clarified.

Circularity Check

2 steps flagged · score 6.0 of 10

The spectral-preservation guarantee inherits its G≈Gl premise from the densification constraint in Eq. (2), so Go≈G is partly by construction; the practical heuristic never verifies that constraint.

  1. self definitional [Section 3.1, Definition 3.1 (Eq. 2), and the 'Combination' paragraph]
    "'Since G is a spectral sparsifier of Gl, Gl is expected to effectively preserve the spectrum of G while improving connectivity. ... both G and Go are spectral sparsifiers of Gl. Therefore, the spectrum is explicitly preserved from G to Go: Go ≈ Gl; Gl ≈ G implies Go ≈ G. ... Gl = argmax ... subject to ... Gd_{1±ϵ}≈G.'"

    The premise 'G is a spectral sparsifier of Gl' is not derived; it is the constraint Gd_{1±ϵ}≈G imposed in the MLE problem (Eq. 2) that defines Gl. The transitivity argument therefore carries the desired spectral match in as an input: if the optimization were solved exactly, Go≈G follows from the constraint plus Theorem 4.2, while if not, Section 4.1 never verifies that the heuristic Gl actually satisfies the constraint. Either way, the spectrum-preservation conclusion is built into the definition of Gl rather than predicted from the sparsification process.

  2. fitted input called prediction [Section 4.1 (Determining |El|) and Section 1 Contributions]
    "'The choice of ϵ ensures that a sufficient number of new edges can be added to E′, specifically requiring |E′|=|El|−|E| to exceed a predefined threshold α.' ... 'the number of added edges |E′| is derived from a well-established theoretical result (see Theorem 4.1) rather than being a heuristically chosen value.'"

    The paper presents the edge-addition count |E′| as theoretically derived, but the implemented rule overrides the formula: ε is iteratively increased until |E′|>α, where α is a tuned hyperparameter (α∈{5,10,15,20,25,30}). Thus the edge count is effectively fit to a validation-set hyperparameter, not predicted by the cited theory. Moreover, Eq. (12) estimates |El| under a uniform edge-sampling model, while Algorithm 1 samples with probabilities pe∝(deg(u)+deg(v)+1)/|fu−fv|, so the 'theoretical' count does not match the actual sampler.

full rationale

The central circular step is in the theoretical transitivity. The paper asserts 'Since G is a spectral sparsifier of Gl' immediately after defining Gl as the maximizer of an MLE problem whose constraint is Gd_{1±ϵ}≈G. That constraint is exactly the spectral-similarity premise used to conclude Go≈G, so the claim that the spectrum is 'explicitly preserved' from G to Go is partly an input of the construction rather than an independent consequence. The practical algorithm in Section 4.1 never checks that its heuristic Gl—built from Fiedler-magnitude and degree candidate sets, uniform edge weights, and an approximate independent-edge likelihood—actually satisfies the constraint, so the guarantee is either tautological (if the constraint were enforced) or unsupported (as implemented). A separate fitted-input issue is the claimed theoretical derivation of the number of added edges: Section 4.1 defines |E′| through ε but then requires |E′| to exceed the tuned threshold α, increasing ε until that happens, and Eq. (12)'s uniform-sampling estimate is inconsistent with Algorithm 1's nonuniform sampling probabilities. The pointwise bound in Theorem 4.1 is an additional correctness concern—it does not by itself establish the uniform-over-all-x inequality required by Definition 2.1—but that is a proof gap rather than circularity. There is no load-bearing self-citation chain or imported uniqueness theorem; the sparsification side (Theorem 4.2) is an independent adaptation of Spielman-Srivastava. On balance, the derivation's spectrum-preservation conclusion is partially circular because its G≈Gl leg is imposed by the optimization constraint, yielding a score of 6.

Assumptions & free parameters 4 free parameters · 4 assumptions · 1 invented entities

The central claim rests on the latent-graph assumption G ≈ Gl, which is asserted but not verified, plus two validation-tuned hyperparameters (alpha and beta) and two hand-fixed approximation errors (epsilon and delta). The theoretical guarantees additionally depend on concentration arguments whose uniformity over all vectors is not established.

free parameters (4)
  • alpha (densification threshold) = tuned per dataset from {5, 10, 15, 20, 25, 30}
    Controls the minimum number of edges added during densification; selected on the validation set for each dataset.
  • beta (sparsification budget) = tuned in [0.5, 1.0]
    Scales the output graph size relative to the input graph; selected on the validation set.
  • epsilon (spectral approximation error) = 0.1
    Hand-fixed; determines q = kappa^2 / (2 epsilon^2) log 8 and indirectly the number of edges added.
  • delta (effective resistance approximation error) = 0.1
    Hand-fixed approximation error for the effective-resistance estimator used in the sparsification step.
assumptions (4)
  • ad hoc to paper Input graph G is a spectral sparsifier of the reconstructed latent graph Gl.
    Used in Section 3.1 (Combination) to conclude Go ≈ G by transitivity. The actual Gl built in Section 4.1 uses a heuristic candidate-set and uniform-weights approximation; spectral similarity between G and Gl is never verified. If this fails, the spectrum-preservation guarantee collapses.
  • ad hoc to paper The concentration argument in Theorem 4.1 covers all vectors x simultaneously.
    Appendix D.1 bounds |x^T L̃x - x^T Lx| for a single fixed x using Hoeffding; no epsilon-net or union bound over x is provided, so Definition 2.1's 'for all x' does not follow.
  • ad hoc to paper Adaptive stopping after beta|E| distinct edges preserves the sampling distribution of Theorem 4.2.
    Section 4.2 samples until beta|E| distinct edges, while Theorem 4.2 analyzes q independent samples with replacement; the stopping rule changes the distribution and is not covered by the theorem.
  • standard math Standard spectral sparsification guarantees hold for the ER-based sampler with feature-similarity weighting.
    Theorem 4.2 builds on Spielman and Srivastava (2008); accepted background, though the adaptation has an inequality typo in Eq. (9).
invented entities (1)
  • Latent graph Gl and its missing-edge set E'
    purpose: Postulated denser graph from which the input G is assumed to be a spectral sparsifier; the missing edges are recovered to improve connectivity.
    Gl is an unobserved construct. The paper provides no falsifiable handle on Gl outside the algorithm; the entire densification step is defined by this assumption.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification." pith.science (2026). https://pith.science/paper/HX47B2U3

@misc{pith2026250616110,
  author       = {Pith},
  title        = {Pith review of: Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HX47B2U3}},
  note         = {Machine review of arXiv:2506.16110}
}
read the original abstract

The message-passing paradigm of Graph Neural Networks often struggles with exchanging information across distant nodes typically due to structural bottlenecks in certain graph regions, a limitation known as \textit{over-squashing}. To reduce such bottlenecks, \textit{graph rewiring}, which modifies graph topology, has been widely used. However, existing graph rewiring techniques often overlook the need to preserve critical properties of the original graph, e.g., \textit{spectral properties}. Moreover, many approaches rely on increasing edge count to improve connectivity, which introduces significant computational overhead and exacerbates the risk of over-smoothing. In this paper, we propose a novel graph rewiring method that leverages \textit{spectrum-preserving} graph \textit{sparsification}, for mitigating over-squashing. Our method generates graphs with enhanced connectivity while maintaining sparsity and largely preserving the original graph spectrum, effectively balancing structural bottleneck reduction and graph property preservation. Experimental results validate the effectiveness of our approach, demonstrating its superiority over strong baseline methods in classification accuracy and retention of the Laplacian spectrum.

Figures

Figures reproduced from arXiv: 2506.16110 by the authors.

Figure 1
Figure 1. Overview of the proposed densification-sparsification rewiring (DSR) framework. The framework starts by densifying the [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 3
Figure 3. Effective resistance (ER) distribution of all node pairs in [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figure 4
Figure 4. Hyperparameter sensitivity analysis on real-world datasets. [PITH_FULL_IMAGE:figures/full_fig_p017_4.png] view at source ↗
Figures from the paper (2 more)
Figure 5
Figure 5. Figure 5: Trade-off between preserving spectrum and reducing ER. [PITH_FULL_IMAGE:figures/full_fig_p018_5.png]
Figure 6
Figure 6. Figure 6: More randomly selected graph spectra visualization results from Mutag, Imdb, and Proteins datasets. [PITH_FULL_IMAGE:figures/full_fig_p020_6.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

54 extracted references · 43 canonical work pages

  1. [1]

    and Yahav, E

    Alon, U. and Yahav, E. On the bottleneck of graph neural networks and its practical implications. In ICLR, 2021

    2021

  2. [2]

    Delaunay graph: Addressing over-squashing and over-smoothing using delaunay triangulation

    Attali, H., Buscaldi, D., and Pernelle, N. Delaunay graph: Addressing over-squashing and over-smoothing using delaunay triangulation. In ICML, 2024

    work page 2024

  3. [3]

    M., and Giovanni, F

    Barbero, F., Velingker, A., Saberi, A., Bronstein, M. M., and Giovanni, F. D. Locality-aware graph rewiring in gnns. In ICLR, 2024

    work page 2024

  4. [4]

    W., Hamrick, J

    Battaglia, P. W., Hamrick, J. B., Bapst, V., Sanchez - Gonzalez, A., Zambaldi, V., Malinowski, M., Tacchetti, A., Raposo, D., Santoro, A., Faulkner, R., Gulcehre, C., Menick, H., Pascanu, R., Botvinick, M., Vinyals, O., and Li, Y. Relational inductive biases, deep learning, and graph networks. Nature, 575: 0 515--518, 2018

    work page 2018

  5. [5]

    Bencz \' u r, A. A. and Karger, D. R. Approximating s-t minimum cuts in \ O (n\( ^ 2 \)) time. In STOC, 1996

    work page 1996

  6. [6]

    Understanding oversquashing in gnns through the lens of effective resistance

    Black, M., Wan, Z., Nayyeri, A., and Wang, Y. Understanding oversquashing in gnns through the lens of effective resistance. In ICML, 2023

    work page 2023

  7. [7]

    \" U ber ein paradoxon aus der verkehrsplanung

    Braess, D. \" U ber ein paradoxon aus der verkehrsplanung. Unternehmensforschung, 12 0 (1): 0 258--268, 1968

    work page 1968

  8. [8]

    Measuring and relieving the over-smoothing problem for graph neural networks from the topological view

    Chen, D., Lin, Y., Li, W., Li, P., Zhou, J., and Sun, X. Measuring and relieving the over-smoothing problem for graph neural networks from the topological view. In AAAI, 2020 a

    work page 2020

Show all 54 references
  1. [9]

    Simple and deep graph convolutional networks

    Chen, M., Wei, Z., Huang, Z., Ding, B., and Li, Y. Simple and deep graph convolutional networks. In ICML, 2020 b

    2020

  2. [10]

    PANDA: expanded width-aware message passing beyond rewiring

    Choi, J., Park, S., Wi, H., Cho, S., and Park, N. PANDA: expanded width-aware message passing beyond rewiring. In ICML, 2024

    2024

  3. [11]

    and He, Y

    Christie, T. and He, Y. Higher-order expander graph propagation. CoRR, abs/2311.07966, 2023

    2023 arXiv

  4. [12]

    Chung, F. R. Spectral graph theory. CBMS Regional Conference Series in Mathematics, 1997

    1997

  5. [13]

    Expander graph propagation

    Deac, A., Lackenby, M., and Velickovic, P. Expander graph propagation. In LoG, 2022

    2022

  6. [14]

    Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics

    Diestel, R. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012

    2012

  7. [15]

    Doyle, P. G. and Snell, J. L. Random walks and electric networks. 1984

    1984

  8. [16]

    and Weber, M

    Fesser, L. and Weber, M. Mitigating over-smoothing and over-squashing using augmentations of forman-ricci curvature. In LoG, 2023

    2023

  9. [17]

    Algebraic connectivity of graphs

    Fiedler, M. Algebraic connectivity of graphs. In Czechoslovak Mathematical Journal, volume 23, pp.\ 298--305, 1973

    1973

  10. [18]

    M., and Ceylan, \.I

    Finkelshtein, B., Huang, X., Bronstein, M. M., and Ceylan, \.I . \.I . Cooperative graph neural networks. In ICML, 2024

    2024

  11. [19]

    S., Riley, P

    Gilmer, J., Schoenholz, S. S., Riley, P. F., Vinyals, O., and Dahl, G. E. Neural message passing for quantum chemistry. In ICML, 2017

    2017

  12. [20]

    D., Giusti, L., Barbero, F., Luise, G., Lio, P., and Bronstein, M

    Giovanni, F. D., Giusti, L., Barbero, F., Luise, G., Lio, P., and Bronstein, M. M. On over-squashing in message passing neural networks: The impact of width, depth, and topology. In ICML, 2023

    2023

  13. [21]

    Graph Theory

    Harary, F. Graph Theory. Addison-Wesley, 1969

    1969

  14. [22]

    Spectral graph pruning against over-squashing and over-smoothing

    Jamadandi, A., Rubio - Madrigal, C., and Burkholz, R. Spectral graph pruning against over-squashing and over-smoothing. CoRR, abs/2404.04612, 2024

    2024 arXiv

  15. [23]

    K., and Mont \' u far, G

    Karhadkar, K., Banerjee, P. K., and Mont \' u far, G. Fosr: First-order spectral rewiring for addressing oversquashing in gnns. In ICLR, 2023

    2023

  16. [24]

    Kipf, T. N. and Welling, M. Semi-supervised classification with graph convolutional networks. In ICLR, 2017

    2017

  17. [25]

    Y., Nguyen, A

    Koh, H. Y., Nguyen, A. T. N., Pan, S., May, L. T., and Webb, G. I. Physicochemical graph neural network for learning protein-ligand interaction fingerprints from sequence data. Nat. Mac. Intell., 2024

    2024

  18. [26]

    L., and Peng, R

    Koutis, I., Miller, G. L., and Peng, R. Approaching optimality for solving SDD linear systems. SIAM J. Comput. , 43 0 (1): 0 337--354, 2014

    2014

  19. [27]

    L., L \' e tourneau, V., and Tossou, P

    Kreuzer, D., Beaini, D., Hamilton, W. L., L \' e tourneau, V., and Tossou, P. Rethinking graph transformers with spectral attention. In NeurIPS, 2021

    2021

  20. [28]

    Crafting papers on machine learning

    Langley, P. Crafting papers on machine learning. In ICML, pp.\ 1207--1216, 2000

    2000

  21. [29]

    Deeper insights into graph convolutional networks for semi-supervised learning

    Li, Q., Han, Z., and Wu, X.-M. Deeper insights into graph convolutional networks for semi-supervised learning. In AAAI, 2018

    2018

  22. [30]

    Predicting global label relationship matrix for graph neural networks under heterophily

    Liang, L., Hu, X., Xu, Z., Song, Z., and King, I. Predicting global label relationship matrix for graph neural networks under heterophily. NeurIPS, 2023 a

    2023

  23. [31]

    Tackling long-tailed distribution issue in graph neural networks via normalization

    Liang, L., Xu, Z., Song, Z., King, I., Qi, Y., and Ye, J. Tackling long-tailed distribution issue in graph neural networks via normalization. IEEE Transactions on Knowledge and Data Engineering, 36 0 (5): 0 2213--2223, 2023 b

    2023

  24. [32]

    Sign is not a remedy: Multiset-to-multiset message passing for learning on heterophilic graphs

    Liang, L., Kim, S., Shin, K., Xu, Z., Pan, S., and Qi, Y. Sign is not a remedy: Multiset-to-multiset message passing for learning on heterophilic graphs. ICML, 2024

    2024

  25. [33]

    Revisiting heterophily for graph neural networks

    Luan, S., Hua, C., Lu, Q., Zhu, J., Zhao, M., Zhang, S., Chang, X.-W., and Precup, D. Revisiting heterophily for graph neural networks. NeurIPS, 2022

    2022

  26. [34]

    Learning to drop: Robust graph neural network via topological denoising

    Luo, D., Cheng, W., Yu, W., Zong, B., Ni, J., Chen, H., and Zhang, X. Learning to drop: Robust graph neural network via topological denoising. In WSDM, 2021

    2021

  27. [35]

    L., Lenssen, J

    Morris, C., Ritzert, M., Fey, M., Hamilton, W. L., Lenssen, J. E., Rattan, G., and Grohe, M. Weisfeiler and leman go neural: Higher-order graph neural networks. In NeurIPS, 2019

    2019

  28. [36]

    M., Nguyen, V

    Nguyen, K., Hieu, N. M., Nguyen, V. D., Ho, N., Osher, S. J., and Nguyen, T. M. Revisiting over-smoothing and over-squashing using ollivier-ricci curvature. In ICML, 2023

    2023

  29. [37]

    C., Lei, Y., and Yang, B

    Pei, H., Wei, B., Chang, K. C., Lei, Y., and Yang, B. Geom-gcn: Geometric graph convolutional networks. In ICLR, 2020

    2020

  30. [38]

    Local algorithms for estimating effective resistance

    Peng, P., Lopatta, D., Yoshida, Y., and Goranci, G. Local algorithms for estimating effective resistance. In KDD, 2021

    2021

  31. [39]

    V., Niepert, M., and Morris, C

    Qian, C., Manolache, A., Ahmed, K., Zeng, Z., den Broeck, G. V., Niepert, M., and Morris, C. Probabilistically rewired message-passing neural networks. In ICLR, 2024

    2024

  32. [40]

    Multi-scale attributed node embedding

    Rozemberczki, B., Allen, C., and Sarkar, R. Multi-scale attributed node embedding. J. Complex Networks, 9 0 (2), 2021

    2021

  33. [41]

    T., Merel, J., Riedmiller, M., Hadsell, R., and Battaglia, P

    Sanchez - Gonzalez, A., Heess, N., Springenberg, J. T., Merel, J., Riedmiller, M., Hadsell, R., and Battaglia, P. W. Graph networks as learnable physics engines for inference and control. In NeurIPS, 2018

    2018

  34. [42]

    C., Hagenbuchner, M., and Monfardini, G

    Scarselli, F., Gori, M., Tsoi, A. C., Hagenbuchner, M., and Monfardini, G. The graph neural network model. IEEE Trans. Neural Networks , 20 0 (1): 0 61--80, 2009

    2009

  35. [43]

    I., Narang, S

    Shuman, D. I., Narang, S. K., Frossard, P., Ortega, A., and Vandergheynst, P. The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains. CoRR, abs/1307.5675, 2013

    2013 arXiv

  36. [44]

    Spielman, D. A. and Srivastava, N. Graph sparsification by effective resistances. In STOC, 2008

    2008

  37. [45]

    Spielman, D. A. and Teng, S. Spectral sparsification of graphs. SIAM J. Comput. , 40 0 (4): 0 981--1025, 2011

    2011

  38. [46]

    D., Chamberlain, B

    Topping, J., Giovanni, F. D., Chamberlain, B. P., Dong, X., and Bronstein, M. M. Understanding over-squashing and bottlenecks on graphs via curvature. In ICLR, 2022

    2022

  39. [47]

    and Micheli, A

    Tortorella, D. and Micheli, A. Leave graphs alone: Addressing over-squashing without rewiring. CoRR, abs/2212.06538, 2022

    2022 arXiv

  40. [48]

    N., and Welling, M

    van den Berg, R., Kipf, T. N., and Welling, M. Graph convolutional matrix completion. In RecSys, 2017

    2017

  41. [49]

    Graph attention networks

    Velickovic, P., Cucurull, G., Casanova, A., Romero, A., Li \` o , P., and Bengio, Y. Graph attention networks. In ICLR, 2018

    2018

  42. [50]

    How powerful are graph neural networks? In ICLR, 2019

    Xu, K., Hu, W., Leskovec, J., and Jegelka, S. How powerful are graph neural networks? In ICLR, 2019

    2019

  43. [51]

    W., and Salakhutdinov, R

    Yang, Z., Cohen, W. W., and Salakhutdinov, R. Revisiting semi-supervised learning with graph embeddings. In ICML, 2016

    2016

  44. [52]

    Do transformers really perform badly for graph representation? In NeurIPS, 2021

    Ying, C., Cai, T., Luo, S., Zheng, S., Ke, G., He, D., Shen, Y., and Liu, T. Do transformers really perform badly for graph representation? In NeurIPS, 2021

    2021

  45. [53]

    Beyond homophily in graph neural networks: Current limitations and effective designs

    Zhu, J., Yan, Y., Zhao, L., Heimann, M., Akoglu, L., and Koutra, D. Beyond homophily in graph neural networks: Current limitations and effective designs. NeurIPS, 2020

    2020

  46. [54]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 gl...

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.