Pith. sign in

REVIEW 3 major objections 5 minor 1 cited by

Large-Scale Spectral Graph Neural Networks via Laplacian Sparsification: Technical Report

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

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

Pith's one-line read This paper claims that the K-hop propagation of spectral GNNs can be replaced by one pass of message passing on an $O(n\log n/\varepsilon^2)$-edge Laplacian sparsifier with spectral error $\varepsilon$, enabling end-to-end training on…

desk verdict Real scalability idea and strong experiments, but the proof for signed learnable filters is unsound; needs major revision before it can be a trustworthy reference. read the letter →

arxiv 2501.04570 v1 pith:SZZWL27X submitted 2025-01-08 cs.LG

Haipeng Ding , Zhewei Wei , Yuhang Ye This is my paper · ORCID
classification cs.LG
keywords spectralgraphneuralnetworksLaplaciansparsificationrandom-walkmatrixpolynomialseffectiveresistancesamplingscalabilitypolynomialfiltersnodeclassificationsemi-supervisedlearning
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 claims that the multi-hop propagation step of a spectral graph neural network — applying a polynomial filter $\sum_{k=0}^{K} w_k L^k$ to node features — can be replaced by a single round of message passing on a sparse surrogate graph built by random-walk edge sampling. The surrogate is a Laplacian sparsifier with $O(n\log n/\varepsilon^2)$ edges that the paper proves approximates the full polynomial filter to spectral error $\varepsilon$ with probability at least $1-K/n$, for fixed coefficients and for coefficients learned during training. If correct, spectral GNNs such as GPR-GNN, APPNP, and JacobiConv become trainable end-to-end on graphs with hundreds of millions of nodes and features with millions of dimensions — regimes where they currently exhaust GPU memory or are forced into the 'detach propagation from training' trick. The paper supports the claim with an error analysis of the propagated signal and with experiments reaching OGB-papers100M (111M nodes, 1.6B edges) and MAG-scholar-C (2.8M feature dimensions), where the sparsified models match or beat their exact counterparts.

What carries the argument

The load-bearing object is the random-walk matrix polynomial sparsifier produced by Algorithm 1: to approximate a single hop matrix $D(D^{-1}A)^{k}$, sample one edge uniformly, split the walk length $k$ into two parts, extend random walks of those lengths from the two endpoints, and repeat $M$ times; each sampled path becomes an edge weighted by $m/M$ times the endpoint degree-normalization ($d_u^{-1/2}d_v^{-1/2}$), with sign and norm corrections ${\rm sgn}(w_k)\lVert w\rVert_1$ for static coefficients or plain $w_k$ for learnable ones. Because a length-$k$ random-walk path has effective resistance bounded by a constant $2k$, the sampled set is an unbiased $\varepsilon$-sparsifier of that hop, and Theorem 3.2 (an extension of the random-walk polynomial sparsification theorem) certifies the $O(n\log n/\varepsilon^2)$ edge count and $1-K/n$ probability. Learnable coefficients are handled hop-by-hop so the sampled edge weights carry the gradient of each $w_k$; Theorem 4.4 then transfers the spectral guarantee to training, bounding the relative error of the APPNP-style loss $\mathcal{L}(z)=(1-\alpha)\operatorname{Tr}(z^{\top}L z)+\alpha\lVert z-x\rVert_F^2$ by $O(\varepsilon)$.

What would settle it

The decisive check is numerical: pick a small graph, fix a coefficient vector $w$ with both signs, use the paper's construction at the certified edge budget, and test the defining inequality $(1-\varepsilon)L \preceq \tilde{L} \preceq (1+\varepsilon)L$ on random signals $x$ (equivalently, compute the largest $|x^{\top}(L-\tilde{L})x|/x^{\top}L x$ over sampled $x$). If the stacked sparsifier $\tilde{L}$ violates the bound while every per-hop sparsifier satisfies its own, the stacking step in Appendix A.1 is refuted and the polynomial-level guarantee does not follow from the per-hop ones; the estimator's unbiasedness would survive, but the claimed spectral error bound would not.

Watch

Extended reading notes

Core claim

The central claim is that the entire propagation pattern of a spectral GNN — the matrix polynomial $\sum_{k=0}^{K} w_k D^{-1/2}(D^{-1}A)^{k}D^{-1/2}$, with signs absorbed into $w_k$ — admits a spectral sparsifier that can be sampled directly by random walks on the original graph, never materializing a dense hop matrix. Encoding the magnitude and sign of each coefficient into sampled edge weights, the construction yields an $\varepsilon$-sparsifier with $O(n\log n/\varepsilon^2)$ edges and success probability at least $1-K/n$, for static coefficients (SLSGC) and for learnable coefficients (GLSGC, which samples each hop independently so that gradients reach every $w_k$). A node-wise variant samples only walks starting from training nodes, making semi-supervised training compatible with mini-batching. The consequence the paper draws is that one round of message passing on the sparse graph reproduces the effect of $K$ rounds on the original graph while keeping the linear feature layers inside the training loop, so graphs that previously caused out-of-memory failures become trainable.

Load-bearing premise

The load-bearing premise, asserted in Appendix A.1, is that if each hop matrix $D(D^{-1}A)^k$ has its own sparse approximation with error $\varepsilon$, then stacking those approximations with the signed coefficients $w_k$ gives an $\varepsilon$-sparsifier of the whole polynomial $\sum_k w_k L^k$ — a step that assumes closeness under subtraction, which the underlying effective-resistance guarantee does not by itself establish.

Editorial extensions

If this is right

  • Spectral GNNs with fixed filters (APPNP) and learnable filters (GPR-GNN, JacobiConv, FavardGNN) train in a single propagation pass per epoch, with memory proportional to the mini-batch instead of the full graph, so 111M-node graphs fit on one GPU.
  • End-to-end training survives: the linear layers stay coupled to propagation, so dimensionality reduction and raw text features (2.8M dimensions on MAG-scholar-C) are handled by the model rather than by preprocessing.
  • The approximation error transfers to the optimization target: for APPNP-style models the relative error of the training loss between exact and sparsified propagation is O(epsilon), so the edge-budget hyperparameter 'ec' tunes the training bias predictably.
  • Per-epoch cost drops from K full graph propagations to one pass over O(n log n / epsilon^2) sampled edges, and the node-wise variant computes only propagation rows touching training nodes, which is what makes semi-supervised training on OGB-papers100M feasible.
  • In the reported experiments the sparsified variants match or exceed their exact counterparts across homophilous and heterophilous graphs, with the largest gain on the heterophilous network Penn94 (GPR-LS improves on GPR-GNN by +2.08 accuracy points).

Reading between the lines

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

  • The sparsified models' small but consistent gains over exact propagation, together with the paper's observation that more sampling does not always help, suggest the random-walk sampling acts as a stochastic regularizer that drops unreliable long-range paths; a testable consequence (not tested in the paper) is that this advantage should shrink when noisy links are artificially removed from the grap
  • The sampler is an anytime estimator of personalized-PageRank-style propagation matrices, so the same machinery could replace the expensive precomputation step in any algorithm that needs a PPR or polynomial-filter matrix once per query or per epoch, beyond the GNN training loop studied here.
  • GLSGC's hop-by-hop independence inflates the edge budget by a factor of K relative to SLSGC, so a joint sampling scheme that reuses walk prefixes across hops while keeping gradient flow to each w_k should close the gap; the paper's own ablation (good results at 'ec' between 1 and 10) suggests the theoretical bound is far from tight in practice.
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

3 major / 5 minor

Summary. The paper proposes SGNN-LS, a Laplacian sparsification method for approximating the propagation matrix of spectral GNNs, enabling end-to-end training without detaching the linear layers from the graph propagation. The authors claim to construct an epsilon-sparsifier of the polynomial filter sum_k w_k L^k with O(n log n / epsilon^2) edges and probability at least 1-K/n, for both static and learnable coefficients w. They validate the approach empirically on datasets ranging up to Ogbn-papers100M (111M nodes) and MAG-scholar-C (2.8M features), reporting accuracy competitive with or better than the corresponding base models.

Significance. If the theoretical guarantee were valid, this would be a valuable contribution: it would allow spectral GNNs with learnable polynomial filters to be trained end-to-end on very large graphs, avoiding the detached precomputation that limits existing scalability tricks. The empirical study is extensive, covers diverse homophilous and heterophilous datasets, and includes a code release, which are strengths. However, the central theorem for learnable signed coefficients is not established; the proof relies on an invalid combination of per-hop sparsifiers. This leaves the spectral guarantee only for nonnegative coefficient polynomials (e.g., APPNP), while the method's headline application, GPR-GNN, uses signed coefficients. The paper would need a substantially weakened claim to be correct, which changes its main contribution.

major comments (3)
  1. [Section 3.2.2 and Appendix A.1] The claim that GLSGC produces an epsilon-sparsifier of sum_k w_k D(D^{-1}A)^k for signed coefficients w is unsupported. The argument that 'a sufficient condition is that all generated K sparsifiers are eps-sparsifiers' is invalid because Loewner order is not preserved under linear combinations with mixed signs: from (1-eps)L_i <= \tilde L_i <= (1+eps)L_i for each hop i it does not follow that (1-eps) sum_i w_i L_i <= sum_i w_i \tilde L_i <= (1+eps) sum_i w_i L_i when the w_i have different signs. Moreover, the stacked object has signed edge weights and is not the Laplacian of a nonnegative-weight graph, so the effective-resistance sampling guarantee in Theorem A.1 does not apply. The proof establishes only unbiasedness of the stacked approximation, not spectral similarity, so Theorem 3.2 is not proved for learnable coefficients.
  2. [Equation (2)] The identification L^K = sum_k w_k L^k approx sum_k w_k P^k is not a valid coefficient-wise mapping because L = I - P, so L^k = sum_{j=0}^k binom(k,j)(-1)^j P^j. 'Absorbing the negative sign into the coefficients w_k' changes the coefficient vector in a way that is never specified; the new coefficients of P^j would be sums over k of w_k binom(k,j)(-1)^j, not the original w_j. This basis mismatch means the polynomial in P that is actually sparsified is not shown to be the same as the intended polynomial in L, which undermines the theoretical analysis for both static and learnable filters.
  3. [Appendix A.3] The proof of Theorem 4.4 contains algebraic steps that do not follow. From the displayed identity x^T (f + \tilde f) L \Delta x, the line x^T(f+\tilde f)L\Delta x / x^T f^T L f x = 2 x^T f L \Delta x / (x^T f L f x - x^T \Delta L \Delta x) is not justified; substituting \tilde f = f - \Delta gives (f + \tilde f) = 2f - \Delta, not an equality of denominators. In addition, the proof asserts the Loewner orderings (1-eps)(I-f) <= I - \tilde f <= (1+eps)(I-f) directly from the sparsifier condition, but it has not been shown that an epsilon-sparsifier of the random-walk polynomial D sum_k w_k (D^{-1}A)^k yields those inequalities for f(P,K) and \tilde f(P,K). The claim that the relative loss error is O(epsilon) is therefore not rigorously established.
minor comments (5)
  1. [Abstract] The phrase 'The scalability' at the start of the second sentence should be 'the scalability', and 'Spectral Graph Neural Networks' is inconsistently capitalized across the abstract and body.
  2. [Section 3.2] The expression 'our desiring matrix L_K' should read 'the desired matrix L_K'.
  3. [Figure 1 caption] The caption contains the typos 'sparsification' and 'spasified'; these should be corrected.
  4. [Algorithm 5] The self-loop (v,v) with weight w0 is added to every node, but the edge count and the unbiasedness analysis for this zero-hop term are not discussed; please clarify how this is consistent with the O(n log n / eps^2) edge bound.
  5. [Theorem 3.2] The statement 'We have extended the original theorem proposed by [8] to accommodate non-normalized polynomial coefficients w' is only true for w in the nonnegative orthant; the paper should state this limitation explicitly where the theorem is introduced.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the method adapts external spectral-sparsification results (Cheng et al.; Spielman–Srivastava) and evaluates against independently trained baselines; the signed-coefficient proof gap is a correctness issue, not a circularity.

full rationale

The paper's derivation is not circular. The central construction is explicitly built on the external random-walk matrix-polynomial sparsification theorem of Cheng et al. [8] and on effective-resistance sparsification [43, 45], rather than on a conclusion that presupposes the target result. The static-coefficient sparsifier (SLSGC) samples edges with probabilities proportional to |w_k| and reweights by sign; this is an unbiased estimator by construction, and unbiasedness is verified directly rather than imported from a fitted parameter. The learnable-coefficient variant (GLSGC) samples each hop independently and multiplies edge weights by w_k; again, no fitted input is renamed as a prediction. The loss-error bound (Theorem 4.4) is derived from the assumed epsilon-sparsifier inequalities, and even if the signed-coefficient stacking argument in Appendix A.1 is mathematically invalid, that is a correctness or soundness problem, not a circular reduction. The authors' self-citations (e.g., BernNet, ChebNetII, OptBasisGNN, GCNII) appear only as related-work context and are not load-bearing for the paper's central claim. No uniqueness theorem is imported from the authors' prior work, and no ansatz is smuggled in via citation. The empirical comparisons are self-contained against external baselines, and the approximation accuracy is checked directly against the exact polynomial-filtered matrix. Therefore the claimed derivation chain does not reduce to its own inputs, and the appropriate circularity score is 0.

Assumptions & free parameters 2 free parameters · 4 assumptions · 0 invented entities

The method imports the random-walk polynomial sparsifier machinery and adds per-dataset hyperparameters. The load-bearing ad hoc assumptions are the sign absorption in Equation (2) and the treatment of signed linear combinations as sparsifiable graphs.

free parameters (2)
  • ec (sampling multiplier) = 1 to 20 depending on dataset (Tables 12-17)
    Controls the number of sampled edges as ec * n * log n; the theory gives only Big-Oh, so ec is tuned per dataset and determines both approximation error and runtime.
  • polynomial degree K and APPNP alpha = per-dataset values in Tables 12-17, e.g., alpha 0.1 to 0.9, K 2 to 10
    Standard hyperparameters of the base spectral models; they define the filter being approximated and are chosen per dataset by validation.
assumptions (4)
  • standard math Effective-resistance sampling yields an eps-sparsifier with O(n log n / eps^2) edges, as in Theorem A.1 from Cheng et al.
    Used as the foundation for all sampling algorithms; cited from prior work and not proved in this paper.
  • ad hoc to paper A polynomial in the normalized Laplacian L can be approximated by the same polynomial in P = D^{-1/2} A D^{-1/2} by absorbing signs into coefficients.
    Equation (2) relies on this; it is only valid after re-expanding the polynomial in the new basis, which the paper does not do.
  • ad hoc to paper The sum of per-hop eps-sparsifiers is an eps-sparsifier of the signed linear combination of hops.
    Used in Appendix A.1 for GLSGC; this is generally false for signed coefficients because Loewner order is not preserved under subtraction.
  • domain assumption Sampled graphs have nonnegative edge weights so that the graph Laplacian is positive semidefinite.
    Standard for effective-resistance sparsification, but violated when sign(w_k) is negative and is applied to sampled edge weights in Algorithms 3 and 5.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Large-Scale Spectral Graph Neural Networks via Laplacian Sparsification: Technical Report." pith.science (2026). https://pith.science/paper/SZZWL27X

@misc{pith2026250104570,
  author       = {Pith},
  title        = {Pith review of: Large-Scale Spectral Graph Neural Networks via Laplacian Sparsification: Technical Report},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SZZWL27X}},
  note         = {Machine review of arXiv:2501.04570}
}
read the original abstract

Graph Neural Networks (GNNs) play a pivotal role in graph-based tasks for their proficiency in representation learning. Among the various GNN methods, spectral GNNs employing polynomial filters have shown promising performance on tasks involving both homophilous and heterophilous graph structures. However, The scalability of spectral GNNs on large graphs is limited because they learn the polynomial coefficients through multiple forward propagation executions during forward propagation. Existing works have attempted to scale up spectral GNNs by eliminating the linear layers on the input node features, a change that can disrupt end-to-end training, potentially impact performance, and become impractical with high-dimensional input features. To address the above challenges, we propose "Spectral Graph Neural Networks with Laplacian Sparsification (SGNN-LS)", a novel graph spectral sparsification method to approximate the propagation patterns of spectral GNNs. We prove that our proposed method generates Laplacian sparsifiers that can approximate both fixed and learnable polynomial filters with theoretical guarantees. Our method allows the application of linear layers on the input node features, enabling end-to-end training as well as the handling of raw text features. We conduct an extensive experimental analysis on datasets spanning various graph scales and properties to demonstrate the superior efficiency and effectiveness of our method. The results show that our method yields superior results in comparison with the corresponding approximated base models, especially on dataset Ogbn-papers100M(111M nodes, 1.6B edges) and MAG-scholar-C (2.8M features).

Figures

Figures reproduced from arXiv: 2501.04570 by the authors.

Figure 1
Figure 1. An overview of how Laplacian sparsification works. For clarity, the propagation of one single center node is illustrated. [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. The visualization of the comparison between the [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Spectral Manifold Harmonization for Graph Imbalanced Regression

    cs.LG 2025-07 reject novelty 5.0 of 10

    Spectral Manifold Harmonization generates synthetic molecular graphs by sampling graph spectra to target rare property values, but reported benefits are inconsistent and the reconstruction step is underspecified.

Reference graph

Works this paper leans on

63 extracted references · 31 canonical work pages · cited by 1 Pith paper

  1. [1]

    Batson, Daniel A

    Joshua D. Batson, Daniel A. Spielman, Nikhil Srivastava, and Shang-Hua Teng

    work page

  2. [2]

    Aleksandar Bojchevski, Johannes Klicpera, Bryan Perozzi, Amol Kapoor, Martin Blais, Benedek Rózemberczki, Michal Lukasik, and Stephan Günnemann. 2020. Scaling Graph Neural Networks with Approximate PageRank. In KDD ’20: The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Virtual Event, CA, USA, August 23-27, 2020 , Rajesh Gupta, Yan Liu...

    doi:10.1145/3394486 2020

  3. [3]

    Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin...

    2020

  4. [4]

    Julian Busch, Jiaxing Pi, and Thomas Seidl. 2020. PushNet: Efficient and Adaptive Neural Message Passing. In ECAI 2020 - 24th European Conference on Artificial Intelligence, 29 August-8 September 2020, Santiago de Compostela, Spain, August 29 - September 8, 2020 - Including 10th Conference on Prestigious Applications of Arti- ficial Intelligence (PAIS 202...

    work page 2020

  5. [5]

    Jie Chen, Tengfei Ma, and Cao Xiao. 2018. FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling. In6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings . OpenReview.net. https://openreview.net/ forum?id=rytstxWAW

    work page 2018

  6. [6]

    Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. 2020. Simple and Deep Graph Convolutional Networks. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event (Proceedings of Machine Learning Research, Vol. 119) . PMLR, 1725–1735

    work page 2020

  7. [7]

    Zhikai Chen, Haitao Mao, Hang Li, Wei Jin, Hongzhi Wen, Xiaochi Wei, Shuaiqiang Wang, Dawei Yin, Wenqi Fan, Hui Liu, and Jiliang Tang. 2023. Exploring the Potential of Large Language Models (LLMs) in Learning on Graphs. CoRR abs/2307.03393 (2023). https://doi.org/10.48550/arXiv.2307.03393 arXiv:2307.03393

    arXiv doi:10.48550/arxiv.2307.03393 2023

  8. [8]

    Dehua Cheng, Yu Cheng, Yan Liu, Richard Peng, and Shang-Hua Teng. 2015. Spec- tral Sparsification of Random-Walk Matrix Polynomials. CoRR abs/1502.03496 (2015). arXiv:1502.03496 http://arxiv.org/abs/1502.03496

    arXiv 2015

Show all 63 references
  1. [9]

    Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh

  2. [10]

    Eli Chien, Wei-Cheng Chang, Cho-Jui Hsieh, Hsiang-Fu Yu, Jiong Zhang, Olgica Milenkovic, and Inderjit S. Dhillon. 2022. Node Feature Extraction by Self- Supervised Multi-scale Neighborhood Prediction. In The Tenth International Conference on Learning Representations, ICLR 2022...

    2022

  3. [11]

    Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. 2021. Adaptive Universal Generalized PageRank Graph Neural Network. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021 . OpenReview.net

    2021

  4. [12]

    Guanyu Cui and Zhewei Wei. 2023. MGNN: Graph Neural Networks Inspired by Distance Geometry Problem. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2023, Long Beach, CA, USA, August 6-10, 2023, Ambuj K. Singh, Yizhou Sun, Leman Akog...

    2023

  5. [13]

    Zhiyong Cui, Kristian Henrickson, Ruimin Ke, and Yinhai Wang. 2020. Traffic Graph Convolutional Recurrent Neural Network: A Deep Learning Framework for Network-Scale Traffic Learning and Forecasting. IEEE Trans. Intell. Transp. Syst. 21, 11 (2020), 4883–4894. https://doi.org/1...

    2020

  6. [14]

    Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. 2016. Convo- lutional Neural Networks on Graphs with Fast Localized Spectral Filtering. In Advances in Neural Information Processing Systems 29: Annual Conference on Neu- ral Information Processing Systems 2016, Dec...

    2016

  7. [15]

    Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019. BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Associa- tion for Computational Linguistics: Hum...

    2019

  8. [16]

    Matthias Fey and Jan Eric Lenssen. 2019. Fast Graph Representation Learning with PyTorch Geometric. CoRR abs/1903.02428 (2019). arXiv:1903.02428 http: //arxiv.org/abs/1903.02428

    2019 arXiv

  9. [17]

    Matthias Fey, Jan Eric Lenssen, Frank Weichert, and Jure Leskovec. 2021. GN- NAutoScale: Scalable and Expressive Graph Neural Networks via Historical Em- beddings. In Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Even...

    2021

  10. [18]

    Yuhe Guo and Zhewei Wei. 2023. Graph Neural Networks with Learnable and Optimal Polynomial Bases. InInternational Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA (Proceedings of Machine Learning Research, Vol. 202), Andreas Krause, Emma Brunsk...

    2023

  11. [19]

    Hamilton, Zhitao Ying, and Jure Leskovec

    William L. Hamilton, Zhitao Ying, and Jure Leskovec. 2017. Inductive Represen- tation Learning on Large Graphs. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA , I...

    2017

  12. [20]

    Mingguo He, Zhewei Wei, Zengfeng Huang, and Hongteng Xu. 2021. BernNet: Learning Arbitrary Graph Spectral Filters via Bernstein Approximation. In Ad- vances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 20...

    2021

  13. [21]

    Mingguo He, Zhewei Wei, and Ji-Rong Wen. 2022. Convolutional Neural Net- works on Graphs with Chebyshev Approximation, Revisited. In NeurIPS

    2022

  14. [22]

    Horn and Charles R

    Roger A. Horn and Charles R. Johnson. 2012. Matrix Analysis (2 ed.). Cambridge University Press

    2012

  15. [23]

    Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. 2020. Open Graph Benchmark: Datasets for Machine Learning on Graphs. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Informatio...

    2020

  16. [24]

    Zengfeng Huang, Shengzhong Zhang, Chong Xi, Tang Liu, and Min Zhou. 2021. Scaling Up Graph Neural Networks Via Graph Coarsening. In KDD ’21: The 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Virtual Event, Singapore, August 14-18, 2021 , Feida Zhu, Beng Ch...

    2021

  17. [25]

    Dejun Jiang, Zhenxing Wu, Chang-Yu Hsieh, Guangyong Chen, Ben Liao, Zhe Wang, Chao Shen, Dong-Sheng Cao, Jian Wu, and Tingjun Hou. 2021. Could graph neural networks learn better molecular representation for drug discovery? A comparison study of descriptor-based and graph-based...

    2021 doi

  18. [26]

    Kipf and Max Welling

    Thomas N. Kipf and Max Welling. 2017. Semi-Supervised Classification with Graph Convolutional Networks. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net

    2017

  19. [27]

    Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. 2019. Pre- dict then Propagate: Graph Neural Networks meet Personalized PageRank. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019 . OpenReview.net

    2019

  20. [28]

    Yin Tat Lee and He Sun. 2015. Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, Venkatesan Guruswami (Ed.). IEEE Computer Society, 250–26...

    2015 doi

  21. [29]

    Derek Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao, and Ser-Nam Lim. 2021. Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods. In Advances in Neural Information Processing Systems 34: Annual Conference on ...

    2021

  22. [30]

    Junfa Lin, Siyuan Chen, and Jiahai Wang. 2022. Graph Neural Networks with Dynamic and Static Representations for Social Recommendation. In Database Systems for Advanced Applications - 27th International Conference, DASFAA 2022, Virtual Event, April 11-14, 2022, Proceedings, Pa...

    2022

  23. [31]

    Zirui Liu, Kaixiong Zhou, Zhimeng Jiang, Li Li, Rui Chen, Soo-Hyun Choi, and Xia Hu. 2023. DSpar: An Embarrassingly Simple Strategy for Efficient GNN training and inference via Degree-based Sparsification. Trans. Mach. Learn. Res. 2023 (2023). https://openreview.net/forum?id=S...

    2023

  24. [32]

    Lutzeyer, Changmin Wu, and Michalis Vazirgiannis

    Johannes F. Lutzeyer, Changmin Wu, and Michalis Vazirgiannis. 2022. Spar- sifying the Update Step in Graph Neural Networks. In Topological, Algebraic and Geometric Learning Workshops 2022, 25-22 July 2022, Virtual (Proceedings of Machine Learning Research, Vol. 196) , Alexande...

    2022

  25. [33]

    McAuley, Christopher Targett, Qinfeng Shi, and Anton van den Hengel

    Julian J. McAuley, Christopher Targett, Qinfeng Shi, and Anton van den Hengel

  26. [34]

    Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala

    Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Z. Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, ...

    2019

  27. [35]

    Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. 2020. Geom-GCN: Geometric Graph Convolutional Networks. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net

    2020

  28. [36]

    Jiezhong Qiu, Yuxiao Dong, Hao Ma, Jian Li, Chi Wang, Kuansan Wang, and Jie Tang. 2019. NetSMF: Large-Scale Network Embedding as Sparse Matrix Factorization. In The World Wide Web Conference, WWW 2019, San Francisco, CA, USA, May 13-17, 2019, Ling Liu, Ryen W. White, Amin Mant...

    2019

  29. [37]

    Bronstein, and Federico Monti

    Emanuele Rossi, Fabrizio Frasca, Ben Chamberlain, Davide Eynard, Michael M. Bronstein, and Federico Monti. 2020. SIGN: Scalable Inception Graph Neural Networks. CoRR abs/2004.11198 (2020). arXiv:2004.11198 https://arxiv.org/abs/ 2004.11198

    2020 arXiv

  30. [38]

    Aravind Sankar, Yozen Liu, Jun Yu, and Neil Shah. 2021. Graph Neural Networks for Friend Ranking in Large-scale Social Platforms. In WWW ’21: The Web Con- ference 2021, Virtual Event / Ljubljana, Slovenia, April 19-23, 2021 , Jure Leskovec, Marko Grobelnik, Marc Najork, Jie Ta...

    2021

  31. [39]

    Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Gallagher, and Tina Eliassi-Rad. 2008. Collective Classification in Network Data. AI Mag. 29, 3 (2008), 93–106. https://doi.org/10.1609/aimag.v29i3.2157

    2008 doi

  32. [40]

    Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. 2018. Pitfalls of Graph Neural Network Evaluation. CoRR abs/1811.05868 (2018). arXiv:1811.05868 http://arxiv.org/abs/1811.05868

    2018 arXiv

  33. [41]

    Zhihao Shi, Xize Liang, and Jie Wang. 2023. LMC: Fast Training of GNNs via Subgraph Sampling with Provable Convergence. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023 . OpenReview.net. https://openreview.net/forum...

    2023

  34. [42]

    Arnab Sinha, Zhihong Shen, Yang Song, Hao Ma, Darrin Eide, Bo-June Paul Hsu, and Kuansan Wang. 2015. An Overview of Microsoft Academic Service (MAS) and Applications. In Proceedings of the 24th International Conference on World Wide Web Companion, WWW 2015, Florence, Italy, Ma...

    2015

  35. [43]

    Spielman and Nikhil Srivastava

    Daniel A. Spielman and Nikhil Srivastava. 2008. Graph sparsification by effective resistances. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008 , Cynthia Dwork (Ed.). ACM, 563–568. https://doi.org/10.11...

    2008

  36. [44]

    Spielman and Shang-Hua Teng

    Daniel A. Spielman and Shang-Hua Teng. 2004. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. InProceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16, 2004, László Babai (Ed.). A...

    2004 doi

  37. [45]

    Spielman and Shang-Hua Teng

    Daniel A. Spielman and Shang-Hua Teng. 2011. Spectral Sparsification of Graphs. SIAM J. Comput. 40, 4 (2011), 981–1025. https://doi.org/10.1137/08074489X

    2011 doi

  38. [46]

    Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. 2018. Graph Attention Networks. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedi...

    2018

  39. [47]

    Xiyuan Wang and Muhan Zhang. 2022. How Powerful are Spectral Graph Neural Networks. In International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA (Proceedings of Machine Learning Research, Vol. 162), Kamalika Chaudhuri, Stefanie Jegelka,...

    2022

  40. [48]

    Souza Jr., Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Q

    Felix Wu, Amauri H. Souza Jr., Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Q. Weinberger. 2019. Simplifying Graph Convolutional Networks. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA (Pr...

    2019

  41. [49]

    Shu Wu, Yuyuan Tang, Yanqiao Zhu, Liang Wang, Xing Xie, and Tieniu Tan

  42. [50]

    Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. 2019. How Powerful are Graph Neural Networks?. In 7th International Conference on Learning Rep- resentations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019 . OpenReview.net. https://openreview.net/forum?id=ryGs6iA5Km

    2019

  43. [51]

    Rui Xue, Haoyu Han, MohamadAli Torkamani, Jian Pei, and Xiaorui Liu. 2023. LazyGNN: Large-Scale Graph Neural Networks via Lazy Propagation. In In- ternational Conference on Machine Learning, ICML 2023, 23-29 July 2023, Hon- olulu, Hawaii, USA (Proceedings of Machine Learning R...

    2023

  44. [52]

    Cohen, and Ruslan Salakhutdinov

    Zhilin Yang, William W. Cohen, and Ruslan Salakhutdinov. 2016. Revisiting Semi-Supervised Learning with Graph Embeddings. In Proceedings of the 33nd International Conference on Machine Learning, ICML 2016, New York City, NY, USA, June 19-24, 2016 (JMLR Workshop and Conference ...

    2016

  45. [53]

    Session-Based Recommendation with Graph Neural Networks. In The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019, The Thirty- First Innovative Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Advances in A...

    2019 doi

  46. [54]

    Prasanna

    Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Vik- tor K. Prasanna. 2020. GraphSAINT: Graph Sampling Based Inductive Learning Method. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020 . Open...

    2020

  47. [55]

    Mengqi Zhang, Shu Wu, Xueli Yu, Qiang Liu, and Liang Wang. 2023. Dynamic Graph Neural Networks for Sequential Recommendation. IEEE Trans. Knowl. Large-Scale Spectral Graph Neural Networks via Laplacian Sparsification: Technical Report KDD ’25, August 3–7, 2025, Toronto, ON, Ca...

    2023

  48. [56]

    Cheng Zheng, Bo Zong, Wei Cheng, Dongjin Song, Jingchao Ni, Wenchao Yu, Haifeng Chen, and Wei Wang. 2020. Robust Graph Representation Learning via Neural Sparsification. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtua...

    2020

  49. [57]

    Hamilton, and Jure Leskovec

    Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L. Hamilton, and Jure Leskovec. 2018. Graph Convolutional Neural Networks for Web-Scale Recommender Systems. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD ...

    2018

  50. [58]

    Meiqi Zhu, Xiao Wang, Chuan Shi, Houye Ji, and Peng Cui. 2021. Interpreting and Unifying Graph Neural Networks with An Optimization Framework. In WWW ’21: The Web Conference 2021, Virtual Event / Ljubljana, Slovenia, April 19-23, 2021, Jure Leskovec, Marko Grobelnik, Marc Najo...

    2021

  51. [59]

    -2L” represent the models are stacked for 2 layers, and those with suffix “-LS

    Difan Zou, Ziniu Hu, Yewen Wang, Song Jiang, Yizhou Sun, and Quanquan Gu. 2019. Layer-Dependent Importance Sampling for Training Deep and Large Graph Convolutional Networks. CoRR abs/1911.07323 (2019). arXiv:1911.07323 http://arxiv.org/abs/1911.07323 A PROOFS OF THE PROPOSED T...

    2019 arXiv

  52. [61]

    Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. 2020. Generalizing Graph Neural Networks Beyond Homophily. CoRR abs/2006.11468 (2020). arXiv:2006.11468 https://arxiv.org/abs/2006.11468

    2020 arXiv

  53. [2013]

    Spectral sparsification of graphs: theory and algorithms. Commun. ACM 56, 8 (2013), 87–94. https://doi.org/10.1145/2492007.2492029

    2013

  54. [2015]

    Image-Based Recommendations on Styles and Substitutes. In Proceedings of the 38th International ACM SIGIR Conference on Research and Development in Information Retrieval, Santiago, Chile, August 9-13, 2015 , Ricardo Baeza-Yates, Mounia Lalmas, Alistair Moffat, and Berthier A. ...

    2015

  55. [2019]

    Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 2019, Anchorage, AK, USA, August 4-8, 2019, Ankur Teredesai, Vipin Kumar, Ying...

    2019

Pith tools

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