Pith. sign in

REVIEW 3 major objections 3 minor 79 references

On the Interplay between Graph Structure and Learning Algorithms in Graph Neural Networks

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

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

Pith's one-line read This paper derives closed-form excess-risk formulas for SGD and Ridge regression in linear graph neural networks and shows that the graph's spectral decomposition determines which learning algorithm generalizes better on a given graph, with

desk verdict Abstract describes a plausible and useful extension of excess-risk analysis to GNNs, but I can't verify the math from the copy I have; worth a referee if the actual text is clean. read the letter →

arxiv 2508.14338 v1 pith:74DTPCMP submitted 2025-08-20 cs.LG

Junwei Su , Chuan Wu This is my paper
classification cs.LG
keywords graphneuralnetworksexcessriskgeneralizationspectraltheorystochasticgradientdescentridgeregressionpower-lawgraphsover-smoothing
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 how well a graph neural network generalizes is not just a matter of network size or training iterations; the shape of the graph itself—as captured by its spectrum of eigenvalues—helps determine which learning algorithm performs best. Focusing on noisy labels rather than the noise-free interpolation regime, the authors derive excess-risk formulas for two standard trainers, stochastic gradient descent and Ridge regression, and express those formulas directly in terms of graph spectra. Comparing regular graphs with power-law graphs, they find the two graph families can favor different algorithms. Extending the analysis to multi-layer linear GNNs, they report an increasingly non-isotropic excess-risk profile with depth, which they read as a new algorithmic view of over-smoothing. Empirical measurements are said to line up with these predictions.

What carries the argument

The load-bearing object is the excess-risk profile: a closed-form expression for the average generalization error of a trained GNN under additive label noise, written as a sum over the graph's spectral modes. The graph Laplacian's eigenvalues and eigenvectors are the machinery that carries the argument—they turn a global statement about generalization into a mode-by-mode accounting that can be compared across graph families. Regular graphs and power-law graphs are the two families whose spectral profiles produce different orderings of SGD versus Ridge. For multi-layer linear GNNs, repeated application of the graph filter produces the increasing non-isotropic effect, since depth weights spect

What would settle it

Take two graphs with the same number of nodes, edges, and degree distribution but different spectra; train the same linear GNN with SGD and with Ridge under controlled label noise. If the empirical order of their excess risks does not match the order computed from the paper's spectral formulas, the central coupling claim fails.

Watch

Extended reading notes

Core claim

The central discovery is a coupling relation: the excess risk of a linear GNN trained by SGD or Ridge regression—the expected gap between error on noisy training labels and error on fresh data—is a closed-form function of the graph's spectral decomposition. From that function, the paper derives a comparative claim: regular and power-law graph families induce different orderings of the two algorithms, so neither algorithm dominates on all graphs. In multi-layer linear GNNs, the same spectral calculation shows the excess-risk profile turning increasingly non-isotropic with depth, identified as the learning-algorithm counterpart of over-smoothing. The empirical section is offered as evidence th

Load-bearing premise

The whole comparison rests on assuming the standard noisy-label linear-regression model—fixed feature distribution and additive label noise with known covariance—carries over to GNN training; if real GNN noise or feature geometry differs, the spectral ranking of algorithms may not persist.

Editorial extensions

If this is right

  • On regular graphs and on power-law graphs, the same two algorithms can be ranked differently; practitioners on these families should expect different choices of trainer to be optimal.
  • Excess risk, not convergence speed in the noise-free regime, becomes the quantity that distinguishes learning algorithms in GNNs; analyses limited to interpolation miss the graph's role.
  • The graph's full spectrum, not a coarse statistic like maximum degree, controls the generalization comparison; graphs sharing a degree statistic can still rank algorithms differently.
  • In a multi-layer linear GNN, each added layer pushes the excess-risk profile further from isotropic, giving a measurable signature of over-smoothing in the generalization error itself.

Reading between the lines

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

  • A direct testable extension: graph pairs with identical degree sequences but different spectra should show different algorithm rankings; the paper's spectral account predicts this, a degree-based account does not.
  • The depth effect suggests interventions that flatten the spectral profile—skip connections, normalization, or residual structure—should alter the excess-risk ordering, not merely stabilize training; the paper does not test this.
  • Because the derivations are for linear GNNs, they likely understate what nonlinear activations do; whether nonlinearity amplifies or blurs the spectral sensitivity is left open.
  • The regular-versus-power-law framing is probably a stand-in for a finer statement in terms of spectral moments; future work could give practitioners a direct per-graph computation of which algorithm is favored.
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 / 3 minor

Summary. The paper claims to derive excess-risk profiles for stochastic gradient descent (SGD) and Ridge regression in graph neural networks, connecting these profiles to graph structure through spectral graph theory. It further claims that regular and power-law graphs measurably change which algorithm is favored, and that multi-layer linear GNNs exhibit an increasing non-isotropic effect on the excess-risk profile linked to over-smoothing. The abstract also states that empirical results align with the theoretical predictions. However, the supplied full text is corrupted mojibake, so no equation, assumption, theorem, or experimental protocol can be inspected; only the abstract is readable.

Significance. If the derivations are correct, the paper would make a valuable contribution: a computable, algorithm-dependent relationship between the graph spectrum and generalization, with concrete comparative predictions for graph families and depth. The claimed link to over-smoothing is also potentially insightful. However, because the full text is illegible, I cannot verify any of these contributions. The paper does not, in the provided form, offer machine-checked proofs, reproducible code, or a parameter-free derivation that I can confirm. Significance is therefore conditional on receiving a readable manuscript.

major comments (3)
  1. [Full Text (all sections)] The submitted full text is corrupted mojibake; no equation, theorem statement, assumption, or experimental setting can be read. This is load-bearing: the central claims of the paper are theoretical, and without the derivations they are unverifiable. Please resupply a clean, correctly encoded manuscript with numbered equations so that the proofs and assumptions can be assessed.
  2. [Abstract] The abstract refers to extending 'conventional settings from the learning theory literature' to GNNs but does not state the label-noise model, feature covariance, or spectral regularity assumptions. Excess-risk comparisons for SGD versus Ridge are known to depend on the alignment between the target function, feature covariance eigenvectors, and noise covariance. Without these specifications, the claimed regular-versus-power-law ordering is not a well-defined graph property and cannot be checked. I am not claiming circularity, but the missing model details are essential.
  3. [Abstract (empirical claim)] The sentence 'Our empirical results align with our theoretical predictions' is the only empirical evidence visible. It reports no datasets, evaluation protocol, training details, or error bars. As the sole support for the central coupling claim, this is insufficient and must be expanded in a readable version.
minor comments (3)
  1. [Abstract] The abstract uses 'excessive risk' in the first paragraph and 'excess risk' later; the terminology should be unified.
  2. [Full Text] The supplied text contains a header 'arXiv:2508.14337v2 [quant-ph]', indicating possible file contamination. Please verify that the manuscript identity and text are correct.
  3. [Abstract] The phrase 'collectively showcasing a coupling relation among graph structure, GNNs and learning algorithms' is vague. A concrete statement of which algorithm is favored on which graph family and under which assumptions would make the contribution clearer.

Circularity Check

0 steps flagged · score 0.0 of 10

No identifiable circularity in the supplied text; the abstract describes a self-contained theoretical derivation and no specific reduction to inputs can be exhibited.

full rationale

The paper's central claim is a derivation of excess-risk profiles for SGD and Ridge regression in GNNs, connected to graph structure through spectral graph theory, followed by a comparative analysis of regular versus power-law graphs and an empirical check. The supplied full text is almost entirely mojibake-corrupted, so the equations and assumptions cannot be directly inspected. From the readable abstract, the derivation is described as extending 'conventional settings from the learning theory literature' to GNNs, and the empirical results are said to 'align with our theoretical predictions.' There is no quoted equation in which a parameter is fitted to a subset and then renamed as a prediction, no definition of a target quantity in terms of the claimed output, and no load-bearing self-citation that reduces the result to its own premise. The concern that spectral complexity measures might have been selected after observing regular-versus-power-law differences is a plausible modeling worry, but it is not a demonstrated circular step: no specific reduction is exhibited, and the rules require quoting the paper and showing the exact equivalence. Because no such reduction is available in the supplied text, the honest finding is no significant circularity. The unreadable body prevents a deeper check, but lack of evidence of circularity is not itself evidence of circularity.

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

From the abstract only, the derivation appears to rest on the standard learning-theory noise model being ported into GNNs, on spectral expressivity of the graph, and on the linear multi-layer GNN as the testbed; the regular-versus-power-law comparison is a chosen axis with no stated external anchor. No fitted constants or invented entities (new forces, mediators, dimensions) are visible in the abstract. The unreadable full text means the ledger is necessarily incomplete: hidden fitted constants or exclusions in the experiments cannot be ruled out (see red flags).

assumptions (4)
  • domain assumption The learning-theory excess-risk framework (bias-variance decomposition in the noisy regime, additive label noise with known variance) transfers to GNNs.
    The abstract says the paper 'extends the conventional settings from the learning theory literature to the context of GNNs'; the transferability of those settings is the load-bearing frame for all subsequent formulas.
  • domain assumption Graph structure can be summarized by spectral quantities (eigenvalues and eigenvectors of a graph operator such as adjacency or normalized Laplacian).
    The abstract claims profiles are 'connected to the graph structure through spectral graph theory'; this requires a spectral decomposition whose properties are assumed, and that the chosen operator captures the structure relevant to learning.
  • domain assumption Analysis of 'multi-layer linear GNNs' is representative of the phenomena claimed for GNNs, including over-smoothing.
    The abstract's over-smoothing and non-isotropy conclusions are drawn in the linear multi-layer setting; nonlinear activations are not mentioned, so generalization to practical nonlinear GNNs is assumed.
  • domain assumption Regular and power-law graph families are the right comparative axes for algorithm-selection conclusions.
    The comparative analysis chooses these two families, a standard dichotomy in network science, but the abstract gives no external justification that this dichotomy captures the structure most relevant to algorithm choice in practice.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On the Interplay between Graph Structure and Learning Algorithms in Graph Neural Networks." pith.science (2026). https://pith.science/paper/74DTPCMP

@misc{pith2026250814338,
  author       = {Pith},
  title        = {Pith review of: On the Interplay between Graph Structure and Learning Algorithms in Graph Neural Networks},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/74DTPCMP}},
  note         = {Machine review of arXiv:2508.14338}
}
read the original abstract

This paper studies the interplay between learning algorithms and graph structure for graph neural networks (GNNs). Existing theoretical studies on the learning dynamics of GNNs primarily focus on the convergence rates of learning algorithms under the interpolation regime (noise-free) and offer only a crude connection between these dynamics and the actual graph structure (e.g., maximum degree). This paper aims to bridge this gap by investigating the excessive risk (generalization performance) of learning algorithms in GNNs within the generalization regime (with noise). Specifically, we extend the conventional settings from the learning theory literature to the context of GNNs and examine how graph structure influences the performance of learning algorithms such as stochastic gradient descent (SGD) and Ridge regression. Our study makes several key contributions toward understanding the interplay between graph structure and learning in GNNs. First, we derive the excess risk profiles of SGD and Ridge regression in GNNs and connect these profiles to the graph structure through spectral graph theory. With this established framework, we further explore how different graph structures (regular vs. power-law) impact the performance of these algorithms through comparative analysis. Additionally, we extend our analysis to multi-layer linear GNNs, revealing an increasing non-isotropic effect on the excess risk profile, thereby offering new insights into the over-smoothing issue in GNNs from the perspective of learning algorithms. Our empirical results align with our theoretical predictions, \emph{collectively showcasing a coupling relation among graph structure, GNNs and learning algorithms, and providing insights on GNN algorithm design and selection in practice.}

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

79 extracted references · 65 canonical work pages

  1. [1]

    A convergence analysis of gradient descent on graph neural networks

    Awasthi, P., Das, A., and Gollapudi, S. A convergence analysis of gradient descent on graph neural networks. Advances in Neural Information Processing Systems, 34: 0 20385--20397, 2021

    work page 2021

  2. [2]

    and Moulines, E

    Bach, F. and Moulines, E. Non-strongly-convex smooth stochastic approximation with convergence rate o (1/n). Advances in neural information processing systems, 26, 2013

    work page 2013

  3. [3]

    Graph convolution for semi-supervised classification: Improved linear separability and out-of-distribution generalization

    Baranwal, A., Fountoulakis, K., and Jagannath, A. Graph convolution for semi-supervised classification: Improved linear separability and out-of-distribution generalization. arXiv preprint arXiv:2102.06966, 2021

    arXiv 2021

  4. [4]

    L., Long, P

    Bartlett, P. L., Long, P. M., Lugosi, G., and Tsigler, A. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 117 0 (48): 0 30063--30070, 2020

    work page 2020

  5. [5]

    Tight nonparametric convergence rates for stochastic gradient descent under the noiseless linear model

    Berthier, R., Bach, F., and Gaillard, P. Tight nonparametric convergence rates for stochastic gradient descent under the noiseless linear model. Advances in Neural Information Processing Systems, 33: 0 2576--2586, 2020

    work page 2020

  6. [6]

    Stochastic training of graph convolutional networks with variance reduction

    Chen, J., Zhu, J., and Song, L. Stochastic training of graph convolutional networks with variance reduction. arXiv preprint arXiv:1710.10568, 2017

    arXiv 2017

  7. [7]

    Fastgcn: fast learning with graph convolutional networks via importance sampling

    Chen, J., Ma, T., and Xiao, C. Fastgcn: fast learning with graph convolutional networks via importance sampling. arXiv preprint arXiv:1801.10247, 2018

    arXiv 2018

  8. [8]

    Eigenvalues of random power law graphs

    Chung, F., Lu, L., and Vu, V. Eigenvalues of random power law graphs. Annals of Combinatorics, 7 0 (1): 0 21--33, 2003

    work page 2003

Show all 79 references
  1. [9]

    Chung, F. R. Spectral graph theory, volume 92. American Mathematical Soc., 1997

    1997

  2. [10]

    and Bach, F

    D \'e fossez, A. and Bach, F. Averaged least-mean-squares: Bias-variance trade-offs and optimal sampling distributions. In Artificial Intelligence and Statistics, pp.\ 205--213. PMLR, 2015

    2015

  3. [11]

    S., Foster, D

    Dhillon, P. S., Foster, D. P., Kakade, S. M., and Ungar, L. H. A risk comparison of ordinary least squares vs ridge regression. The Journal of Machine Learning Research, 14 0 (1): 0 1505--1511, 2013

    2013

  4. [12]

    Harder, better, faster, stronger convergence rates for least-squares regression

    Dieuleveut, A., Flammarion, N., and Bach, F. Harder, better, faster, stronger convergence rates for least-squares regression. The Journal of Machine Learning Research, 18 0 (1): 0 3520--3570, 2017

    2017

  5. [13]

    and Wager, S

    Dobriban, E. and Wager, S. High-dimensional asymptotics of prediction: Ridge regression and classification. The Annals of Statistics, 46 0 (1): 0 247--279, 2018

    2018

  6. [14]

    S., Hou, K., Salakhutdinov, R

    Du, S. S., Hou, K., Salakhutdinov, R. R., Poczos, B., Wang, R., and Xu, K. Graph neural tangent kernel: Fusing graph neural networks with graph kernels. Advances in neural information processing systems, 32, 2019

    2019

  7. [15]

    Networks, crowds, and markets, volume 8

    Easley, D., Kleinberg, J., et al. Networks, crowds, and markets, volume 8. Cambridge university press Cambridge, 2010

    2010

  8. [16]

    On power-law relationships of the internet topology

    Faloutsos, M., Faloutsos, P., and Faloutsos, C. On power-law relationships of the internet topology. ACM SIGCOMM computer communication review, 29 0 (4): 0 251--262, 1999

    1999

  9. [17]

    real-world

    Farkas, I. J., Der \'e nyi, I., Barab \'a si, A.-L., and Vicsek, T. Spectra of “real-world” graphs: Beyond the semicircle law. Physical Review E, 64 0 (2): 0 026704, 2001

    2001

  10. [18]

    Community detection in graphs

    Fortunato, S. Community detection in graphs. Physics reports, 486 0 (3-5): 0 75--174, 2010

    2010

  11. [19]

    Identifying network structure similarity using spectral graph theory

    Gera, R., Alonso, L., Crawford, B., House, J., Mendez-Bermudez, J., Knuth, T., and Miller, R. Identifying network structure similarity using spectral graph theory. Applied network science, 3: 0 1--15, 2018

    2018

  12. [20]

    S., Riley, P

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

    2017

  13. [21]

    Spectra and eigenvectors of scale-free networks

    Goh, K.-I., Kahng, B., and Kim, D. Spectra and eigenvectors of scale-free networks. Physical Review E, 64 0 (5): 0 051903, 2001

    2001

  14. [22]

    Exploring network structure, dynamics, and function using networkx

    Hagberg, A., Swart, P., and S Chult, D. Exploring network structure, dynamics, and function using networkx. Technical report, Los Alamos National Lab.(LANL), Los Alamos, NM (United States), 2008

    2008

  15. [23]

    L., Ying, R., and Leskovec, J

    Hamilton, W. L., Ying, R., and Leskovec, J. Inductive representation learning on large graphs, 2018

    2018

  16. [24]

    K., Vandergheynst, P., and Gribonval, R

    Hammond, D. K., Vandergheynst, P., and Gribonval, R. Wavelets on graphs via spectral graph theory. Applied and Computational Harmonic Analysis, 30 0 (2): 0 129--150, 2011

    2011

  17. [25]

    H., and Friedman, J

    Hastie, T., Tibshirani, R., Friedman, J. H., and Friedman, J. H. The elements of statistical learning: data mining, inference, and prediction, volume 2. Springer, 2009

    2009

  18. [26]

    Hastie, T., Montanari, A., Rosset, S., and Tibshirani, R. J. Surprises in high-dimensional ridgeless least squares interpolation. Annals of statistics, 50 0 (2): 0 949, 2022

    2022

  19. [27]

    M., and Zhang, T

    Hsu, D., Kakade, S. M., and Zhang, T. Random design analysis of ridge regression. In Twenty-Fifth Annual Conference on Learning Theory, 2012

    2012

  20. [28]

    Adaptive sampling towards fast graph representation learning

    Huang, W., Zhang, T., Rong, Y., and Huang, J. Adaptive sampling towards fast graph representation learning. arXiv preprint arXiv:1809.05343, 2018

    2018 arXiv

  21. [29]

    M., Kidambi, R., Netrapalli, P., Pillutla, V

    Jain, P., Kakade, S. M., Kidambi, R., Netrapalli, P., Pillutla, V. K., and Sidford, A. A markov chain theory approach to characterizing the minimax optimality of stochastic gradient descent (for least squares). arXiv preprint arXiv:1710.09430, 2017

    2017 arXiv

  22. [30]

    M., Kidambi, R., Netrapalli, P., and Sidford, A

    Jain, P., Kakade, S. M., Kidambi, R., Netrapalli, P., and Sidford, A. Parallelizing stochastic gradient descent for least squares regression: mini-batching, averaging, and model misspecification. Journal of machine learning research, 18 0 (223): 0 1--42, 2018

    2018

  23. [31]

    Theory of graph neural networks: Representation and learning

    Jegelka, S. Theory of graph neural networks: Representation and learning. In The International Congress of Mathematicians, 2022

    2022

  24. [32]

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

    2017

  25. [33]

    The optimal ridge penalty for real-world high-dimensional data can be zero or negative due to the implicit ridge regularization

    Kobak, D., Lomond, J., and Sanchez, B. The optimal ridge penalty for real-world high-dimensional data can be zero or negative due to the implicit ridge regularization. The Journal of Machine Learning Research, 21 0 (1): 0 6863--6878, 2020

    2020

  26. [34]

    and Szepesvari, C

    Lakshminarayanan, C. and Szepesvari, C. Linear stochastic approximation: How far does constant step-size and iterate averaging go? In International conference on artificial intelligence and statistics, pp.\ 1347--1355. PMLR, 2018

    2018

  27. [35]

    and Weisfeiler, B

    Leman, A. and Weisfeiler, B. A reduction of a graph to a canonical form and an algebra arising during this reduction. Nauchno-Technicheskaya Informatsiya, 2 0 (9): 0 12--16, 1968

    1968

  28. [36]

    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 Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018

    2018

  29. [37]

    Diffusion convolutional recurrent neural network: Data-driven traffic forecasting

    Li, Y., Yu, R., Shahabi, C., and Liu, Y. Diffusion convolutional recurrent neural network: Data-driven traffic forecasting. arXiv preprint arXiv:1707.01926, 2017

    2017 arXiv

  30. [38]

    A \ pac \ -bayesian approach to generalization bounds for graph neural networks

    Liao, R., Urtasun, R., and Zemel, R. A \ pac \ -bayesian approach to generalization bounds for graph neural networks. In International Conference on Learning Representations, 2021. URL https://openreview.net/forum?id=TR-Nj6nFx42

    2021

  31. [39]

    Visual relationship detection with language priors, 2016

    Lu, C., Krishna, R., Bernstein, M., and Fei-Fei, L. Visual relationship detection with language priors, 2016

    2016

  32. [40]

    Generalization bounds for graph convolutional neural networks via rademacher complexity, 2021

    Lv, S. Generalization bounds for graph convolutional neural networks via rademacher complexity, 2021

    2021

  33. [41]

    Subgroup generalization and fairness of graph neural networks

    Ma, J., Deng, J., and Mei, Q. Subgroup generalization and fairness of graph neural networks. arXiv preprint arXiv:2106.15535, 2021

    2021 arXiv

  34. [42]

    and Suzuki, T

    Oono, K. and Suzuki, T. Optimization and generalization analysis of transduction through gradient boosting and application to multi-scale graph neural networks. Advances in Neural Information Processing Systems, 33: 0 18917--18930, 2020

    2020

  35. [43]

    Implicit regularization or implicit conditioning? exact risk trajectories of sgd in high dimensions

    Paquette, C., Paquette, E., Adlam, B., and Pennington, J. Implicit regularization or implicit conditioning? exact risk trajectories of sgd in high dimensions. Advances in Neural Information Processing Systems, 35: 0 35984--35999, 2022

    2022

  36. [44]

    and Barab \'a si, A.-L

    P \'o sfai, M. and Barab \'a si, A.-L. Network science. Citeseer, 2016

    2016

  37. [45]

    C., and Bonvin, A

    R \'e au, M., Renaud, N., Xue, L. C., and Bonvin, A. M. Deeprank-gnn: a graph neural network framework to learn patterns in protein--protein interfaces. Bioinformatics, 39 0 (1): 0 btac759, 2023

    2023

  38. [46]

    Graph neural networks for materials science and chemistry

    Reiser, P., Neubert, M., Eberhard, A., Torresi, L., Zhou, C., Shao, C., Metni, H., van Hoesel, C., Schopmans, H., Sommer, T., et al. Graph neural networks for materials science and chemistry. Communications Materials, 3 0 (1): 0 93, 2022

    2022

  39. [47]

    K., Bronstein, M

    Rusch, T. K., Bronstein, M. M., and Mishra, S. A survey on oversmoothing in graph neural networks, 2023. URL https://arxiv.org/abs/2303.10993

    2023 arXiv

  40. [48]

    A survey on the expressive power of graph neural networks

    Sato, R. A survey on the expressive power of graph neural networks. arXiv preprint arXiv:2003.04078, 2020

    2003 arXiv

  41. [49]

    C., and Hagenbuchner, M

    Scarselli, F., Tsoi, A. C., and Hagenbuchner, M. The vapnik--chervonenkis dimension of graph and recursive neural networks. Neural Networks, 108: 0 248--259, 2018

    2018

  42. [50]

    Mspipe: Efficient temporal gnn training via staleness-aware pipeline

    Sheng, G., Su, J., Huang, C., and Wu, C. Mspipe: Efficient temporal gnn training via staleness-aware pipeline. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp.\ 2651--2662, 2024

    2024

  43. [51]

    Spectral graph theory

    Spielman, D. Spectral graph theory. Combinatorial scientific computing, 18: 0 18, 2012

    2012

  44. [52]

    and Wu, C

    Su, J. and Wu, C. On the topology awareness and generalization performance of graph neural networks. In European Conference on Computer Vision, pp.\ 73--89. Springer, 2024

    2024

  45. [53]

    Pres: Toward scalable memory-based dynamic graph neural networks, 2024

    Su, J., Zou, D., and Wu, C. Pres: Toward scalable memory-based dynamic graph neural networks, 2024. URL https://arxiv.org/abs/2402.04284

    2024 arXiv

  46. [54]

    and Liu, Y

    Tang, H. and Liu, Y. Towards understanding generalization of graph neural networks. In International Conference on Machine Learning, pp.\ 33674--33719. PMLR, 2023

    2023

  47. [55]

    P., Dong, X., and Bronstein, M

    Topping, J., Di Giovanni, F., Chamberlain, B. P., Dong, X., and Bronstein, M. M. Understanding over-squashing and bottlenecks on graphs via curvature. arXiv preprint arXiv:2111.14522, 2021

    2021 arXiv

  48. [56]

    and Bartlett, P

    Tsigler, A. and Bartlett, P. Benign overfitting in ridge regression. arXiv preprint arXiv:2009.14286, 2020

    2009 arXiv

  49. [57]

    and Bartlett, P

    Tsigler, A. and Bartlett, P. L. Benign overfitting in ridge regression. J. Mach. Learn. Res., 24: 0 123--1, 2023

    2023

  50. [58]

    Compound--protein interaction prediction with end-to-end learning of neural networks for graphs and sequences

    Tsubaki, M., Tomii, K., and Sese, J. Compound--protein interaction prediction with end-to-end learning of neural networks for graphs and sequences. Bioinformatics, 35 0 (2): 0 309--318, 2019

    2019

  51. [59]

    Graph spectra for complex networks

    Van Mieghem, P. Graph spectra for complex networks. Cambridge university press, 2023

    2023

  52. [60]

    Graph attention networks

    Veli c kovi \'c , P., Cucurull, G., Casanova, A., Romero, A., Lio, P., and Bengio, Y. Graph attention networks. arXiv preprint arXiv:1710.10903, 2017

    2017 arXiv

  53. [61]

    and Zhang, Z.-L

    Verma, S. and Zhang, Z.-L. Stability and generalization of graph convolutional neural networks, 2019

    2019

  54. [62]

    and Xu, J

    Wu, D. and Xu, J. On the optimal weighted ell\_2 regularization in overparameterized linear regression. Advances in Neural Information Processing Systems, 33: 0 10112--10123, 2020

    2020

  55. [63]

    Simplifying graph convolutional networks

    Wu, F., Souza, A., Zhang, T., Fifty, C., Yu, T., and Weinberger, K. Simplifying graph convolutional networks. In International conference on machine learning, pp.\ 6861--6871. PMLR, 2019

    2019

  56. [64]

    Wu, J., Zou, D., Chen, Z., Braverman, V., Gu, Q., and Kakade, S. M. Finite-sample analysis of learning high-dimensional single relu neuron. In International Conference on Machine Learning, pp.\ 37919--37951. PMLR, 2023

    2023

  57. [65]

    Handling distribution shifts on graphs: An invariance perspective, 2022

    Wu, Q., Zhang, H., Yan, J., and Wipf, D. Handling distribution shifts on graphs: An invariance perspective, 2022

    2022

  58. [66]

    B., and Fei-Fei, L

    Xu, D., Zhu, Y., Choy, C. B., and Fei-Fei, L. Scene graph generation by iterative message passing, 2017

    2017

  59. [67]

    and Hsu, D

    Xu, J. and Hsu, D. J. On the number of variables to use in principal component regression. Advances in neural information processing systems, 32, 2019

    2019

  60. [68]

    How powerful are graph neural networks? arXiv preprint arXiv:1810.00826, 2018

    Xu, K., Hu, W., Leskovec, J., and Jegelka, S. How powerful are graph neural networks? arXiv preprint arXiv:1810.00826, 2018

    2018 arXiv

  61. [69]

    Z., Guo, Z., Zhou, K., Zhang, W., and Liu, Z

    Yang, J., Ang, Y. Z., Guo, Z., Zhou, K., Zhang, W., and Liu, Z. Panoptic scene graph generation, 2022

    2022

  62. [70]

    Neural motifs: Scene graph parsing with global context, 2018

    Zellers, R., Yatskar, M., Thomson, S., and Choi, Y. Neural motifs: Scene graph parsing with global context, 2018

    2018

  63. [71]

    The expressive power of graph neural networks: A survey, 2023 a

    Zhang, B., Fan, C., Liu, S., Huang, K., Zhao, X., Huang, J., and Liu, Z. The expressive power of graph neural networks: A survey, 2023 a . URL https://arxiv.org/abs/2308.08235

    2023 arXiv

  64. [72]

    A complete expressiveness hierarchy for subgraph gnns via subgraph weisfeiler-lehman tests

    Zhang, B., Feng, G., Du, Y., He, D., and Wang, L. A complete expressiveness hierarchy for subgraph gnns via subgraph weisfeiler-lehman tests. In International Conference on Machine Learning, pp.\ 41019--41077. PMLR, 2023 b

    2023

  65. [73]

    Rethinking the expressive power of gnns via graph biconnectivity

    Zhang, B., Luo, S., Wang, L., and He, D. Rethinking the expressive power of gnns via graph biconnectivity. arXiv preprint arXiv:2301.09505, 2023 c

    2023 arXiv

  66. [74]

    Zhu, G., Zhang, L., Jiang, Y., Dang, Y., Hou, H., Shen, P., Feng, M., Zhao, X., Miao, Q., Shah, S. A. A., and Bennamoun, M. Scene graph generation: A comprehensive survey, 2022

    2022

  67. [75]

    Shift-robust gnns: Overcoming the limitations of localized graph training data, 2021

    Zhu, Q., Ponomareva, N., Han, J., and Perozzi, B. Shift-robust gnns: Overcoming the limitations of localized graph training data, 2021

    2021

  68. [76]

    P., and Kakade, S

    Zou, D., Wu, J., Braverman, V., Gu, Q., Foster, D. P., and Kakade, S. The benefits of implicit regularization from sgd in least squares problems. Advances in neural information processing systems, 34: 0 5456--5468, 2021 a

    2021

  69. [77]

    Benign overfitting of constant-stepsize sgd for linear regression

    Zou, D., Wu, J., Braverman, V., Gu, Q., and Kakade, S. Benign overfitting of constant-stepsize sgd for linear regression. In Conference on Learning Theory, pp.\ 4633--4635. PMLR, 2021 b

    2021

  70. [78]

    Zou, D., Wu, J., Braverman, V., Gu, Q., and Kakade, S. M. Benign overfitting of constant-stepsize sgd for linear regression. Journal of Machine Learning Research, 24 0 (326): 0 1--58, 2023

    2023

  71. [79]

    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 5, 2026 · model on record in the stance chip above.