Pith. sign in

REVIEW 3 major objections 4 minor 2 cited by

Learning from one graph: transductive learning guarantees via the geometry of small random worlds

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

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

Pith's one-line read This paper proves finite-sample transductive learning guarantees for GCNs on a single graph, reaching the optimal N^{-1/2} convergence rate.

desk verdict Solid framework with a real error in the headline ER corollary; conditionally interesting but needs revision. read the letter →

arxiv 2509.06894 v1 pith:VGPWRSPR submitted 2025-09-08 stat.ML cs.LGmath.MGmath.PRmath.STstat.TH

Nils Detering , Luca Galimberti , Anastasis Kratsios , Giulia Livieri , A. Martina Neuman This is my paper
classification stat.MLcs.LGmath.MGmath.PRmath.STstat.TH MSC 68T0760B1054E40
keywords transductivelearninggraphconvolutionalnetworksgeneralizationboundsWassersteinconcentrationmetricembeddingssnowflakemetricsErdős-Rényigraphsnonparametricrates
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

Transductive learning on graphs normally lacks the multiple independent samples that standard generalization theory requires. The paper shows that for one observed graph, one feature matrix, and a subset of labels, the worst-case gap between a model's true and empirical risks can still be controlled uniformly over graph-convolutional hypothesis classes. The device is to treat the labeled vertices as an empirical measure on the graph metric space and to prove that this measure concentrates at the nonparametric rate N^{-1/2}, where N is the number of labels. The results cover arbitrary deterministic graphs without isolated vertices and single draws of Erdős-Rényi-like random graphs with edge probability on the order of sqrt(log k / k).

What carries the argument

The argument runs through three linked tools: the alpha-snowflake of a metric space, in which every distance is raised to the power alpha; bi-Lipschitz embeddings of the snowflaked graph metric into (R^m, ell8) whose dimension depends on the doubling constant and distortion but not on the number of vertices; and a concentration result for empirical measures in the 1-Wasserstein distance on such spaces, giving rate N^{-1/2} in dimension one and log(N)/N^{1/2} in dimension two. Kantorovich-Rubinstein duality converts the worst-case loss gap into a 1/2-Wasserstein distance between the true and empirical label distributions, so the whole transductive bound reduces to how fast the empirical distr

What would settle it

Compute the mean and tail of the 1-Wasserstein distance W_1(mu, mu_N) for mu uniform on [0,1]^m with the ell8 distance, for m = 1, 2, 3 and N up to 10^6. Lemma B.2 predicts mean rates N^{-1/2} for m = 1, log(N)/N^{1/2} for m = 2, and N^{-1/m} for m >= 3 with specific constants; any deviation at those thresholds would falsify Proposition 4.1 and hence both main theorem bounds.

Watch

Extended reading notes

Core claim

The central claim is that the transductive generalization gap sup over generalized GCNs of |R_{G,X}(f) - R^N_{G,X}(f)| admits finite-sample uniform bounds of order (diameter)^{1/2} min{log2(N), k}/N^{1/2} plus (log(1/delta))^{1/2}/N^{1/2}. For deterministic graphs the bound holds for any graph with no isolated vertices and bounded features; for common noise, when the graph is a single draw of an Erdős-Rényi random graph with p = (C log k / k)^{1/2}, the same type of bound holds with probability at least 1-2delta uniformly over the GCN class. The rate is the optimal nonparametric O(N^{-1/2}), and the min-term creates a two-phase regime so that the bounds stay informative even when very few la

Load-bearing premise

The transductive bounds all flow through Lemma B.2, a concentration estimate for empirical measures under the ell8 norm that is cited from another paper with its proof omitted; if that lemma's rates or constants are wrong, the main theorems lose their support.

Editorial extensions

If this is right

  • The deterministic bound applies to any graph with no isolated vertices, giving a uniform GCN generalization certificate for a fixed real-world graph once labels are sampled.
  • For a single Erdős-Rényi draw with p = (C log k / k)^{1/2}, the uniform bound holds with probability at least 1 - 2delta and remains finite for small N.
  • The two-phase form of the bound means a label-budget regime: before a graph-size-dependent threshold the bound carries a log2(N) factor, after it the pure N^{-1/2} nonparametric rate appears.
  • Because the random-graph theorem reduces to the deterministic one by conditioning on diameter-at-most-2 and a minimal-degree event, any admissible random graph model with those properties inherits the same learning guarantee.
  • The GCN Lipschitz constant is computed explicitly from the spectral norm of the normalized Laplacian and the network weights, so the constants in the bound are in principle computable.

Reading between the lines

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

  • Proposition 4.1 is stated for any doubling metric space, so the same proof template should transfer to other single-sample graph ensembles, such as random geometric graphs or bounded-doubling graphs, provided their diameter and minimum degree can be controlled.
  • The min over r1(N) and r2(N) yields a concrete label-budget rule: labeling more nodes is worthwhile until the min switches the bound from the log2(N)/N^{1/2} regime to the pure N^{-1/2} regime; the paper identifies the phase transition but does not optimize the switch point.
  • The constant D grows with feature dimension, depth, and the product of weight norms, so the bound doubles as a design guideline: smaller feature dimension, shallower networks, and smaller spectral norms of the weights tighten the single-graph guarantee.
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 / 4 minor

Summary. The paper develops transductive generalization bounds for graph-based learners, in particular generalized GCNs, operating on a single observed graph. Two regimes are considered: deterministic graphs with no isolated vertices, and random graphs with shared input randomness. The technical route is to embed the snowflaked graph metric into a low-dimensional ℓ_8 space using doubling-metric embedding theory, then to control the 1/2-Wasserstein distance between the true and empirical label distributions. The main results are Theorem 3.1 for deterministic graphs, Theorem 3.2 for admissible random graphs, and Corollary 3.2 specializing the latter to Erdős–Rényi graphs with p=(C log k/k)^{1/2}. The paper claims uniform finite-sample bounds of order N^{-1/2} that remain informative for small labeled sample sizes N, with two-phase behavior governed by min{log_2 N, k C(\theta_GCN)}.

Significance. If the results are correct, they provide some of the first finite-sample uniform transductive learning guarantees for single-graph GCNs, with a genuinely nonparametric N^{-1/2} rate. The metric-embedding and Wasserstein-concentration framework is a welcome addition, and the explicit probability estimates in Lemma A.1 and the measurability argument in Proposition 4.2 are useful standalone ingredients. The paper also benefits from being explicit about constants and rates in several auxiliary results. However, the headline Corollary 3.2 contains a substitution error in its constant D, and one of the two central concentration tools is imported from the authors' prior work with an omitted proof. These issues are load-bearing and must be repaired before the claims can be regarded as established.

major comments (3)
  1. [Corollary 3.2 / Appendix A.2, Eq. (3.9)] The displayed D in (3.9) is not obtained by substituting Lemma A.1 into Theorem 3.2's D in (3.7). Lemma A.1 gives c_k =(c_1/2)(k log k)^{1/2}; hence c_k^{-1/2}(k-1)^{1/2} ∼ k^{1/4}(log k)^{-1/4}. In contrast, with p=(C log k/k)^{1/2}, the expression inside (3.9) satisfies (c p(k-1)/(k log k))^{1/2} ∼ k^{-1/4}(log k)^{-1/4}. The two terms differ by a factor k^{1/2} in growth. Since D enters both the prefactor (2B_ℓ D)^{1/2} and the factor (2+D)^{1/2}, Corollary 3.2's stated guarantee is not a consequence of Theorem 3.2 and Lemma A.1 as written. The corollary must be corrected or restated with the actual D that follows from the substitution.
  2. [Appendix B.2, Lemma B.2 and Table 1] Lemma B.2 is the concentration engine behind Proposition 4.1, and therefore behind both main theorems and both GCN corollaries. Its proof is not provided: the text says the argument 'closely parallels [25, Lemma 16]' and then 'We omit further details.' The adaptation from the Euclidean setting of [25] to the ℓ_8 norm, and the exact constants in Table 1, are asserted rather than derived. Since any error in these constants or rates propagates directly into the final bounds, the authors should include a self-contained proof of Lemma B.2, or at least a full derivation of Table 1 from [25].
  3. [Section 3.1 and Corollaries 3.1–3.2] Theorem 3.1 requires the target function f^* to be B-Lipschitz in the sense of (2.2)–(2.3) with the same B as the hypothesis class. In the GCN corollaries, the proofs verify this regularity only for f in F_GCN, producing the constant B in (3.6) or D in (3.9). No assumption on f^* is stated in the corollaries. If f^* is an arbitrary labeling, not necessarily a member of F_GCN or B-Lipschitz with the same constant, then inequality (5.6) fails and the corollaries do not follow. The authors need to state explicitly that f^* is assumed to lie in the relevant smooth/hypothesis class, or else include the Lipschitz constant of f^* in the bound.
minor comments (4)
  1. [Appendix A.2] The line 'It follows from the conclusion (3.8) of Theorem 3.8' should read 'Theorem 3.2'.
  2. [Notation] The symbol M is used both for the feature bound in Assumption 3.2 and for the metric doubling constant in Section 2. This overloading is confusing in Theorem 3.2 and Corollary 3.2; please disambiguate.
  3. [Theorem 3.2] The joint law of G and X is not specified. The proof conditions on the event G ∈ U_k, so the authors should clarify that the conditional argument is with respect to the joint distribution and state whether G and X are independent.
  4. [Eq. (1.1)] The footnote explaining that C(θ_GCN) also depends on k is helpful, but the displayed informal theorem is still easy to misread. Consider making the k-dependence part of the formal statement or using a notation that does not suggest k-free constants.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation: the transductive bounds are derived from external concentration and embedding results; the load-bearing self-citation (Lemma B.2 from the authors' own [25]) is an omitted-proof/reproducibility issue, not a definitional reduction.

full rationale

The derivation chain is self-contained in the relevant sense. Theorem 3.1 follows from Proposition 4.1 (Wasserstein concentration on a doubling metric space) plus the Lipschitz regularity of the GCN class established in Corollary 3.1. Theorem 3.2 conditions on the admissible event G_k in U_k, applies Theorem 3.1, and substitutes the Lipschitz bound D; Corollary 3.2 then uses the Erdős-Rényi degree and diameter estimates of Lemma A.1. No step fits a parameter to the target quantity and then relabels it as a prediction, and no object is defined in terms of the transductive generalization gap itself. The only apparent circularity candidate is Appendix B.2, where Lemma B.2's proof is omitted: 'The argument closely parallels the proof of [25, Lemma 16] ... We omit further details.' This is a genuine omitted-proof flag, and the lemma is load-bearing for Proposition 4.1 and hence for Theorems 3.1 and 3.2. However, [25, Lemma 16] is a published, parameter-free concentration inequality for empirical measures on R^m with explicit stated assumptions and constants; it does not presuppose the present paper's transductive risk, graph class, or fitted values. The self-citation is therefore independent evidence rather than a circular reduction. I also note an apparent algebraic inconsistency in Corollary 3.2: substituting Lemma A.1's c_k = (c1/2)(k log k)^{1/2} into Theorem 3.2's D in (3.7) gives an interior term growing like k^{1/4}, while the displayed D in (3.9) has an interior term shrinking like k^{-1/4}. This is a correctness/consistency concern, not a circularity, and does not affect the circularity score.

Assumptions & free parameters 1 free parameters · 7 assumptions · 0 invented entities

The paper introduces no new physical or algorithmic entities. It relies on metric-space theorems, boundedness assumptions on graphs and features, and a chosen snowflake exponent of 1/2. The most fragile imported item is the Wasserstein concentration lemma from the authors' earlier work, whose proof is not reproduced.

free parameters (1)
  • Snowflake degree alpha = 1/2
    The entire argument fixes alpha=1/2: risks use sqrt loss and the metric is snowflaked by 1/2. This exponent is chosen by hand to make the loss 1/2-Hölder and to fit the W_{1/2} machinery; it is not estimated.
assumptions (7)
  • standard math Assouad embedding theorem for doubling metrics into R^m with dimension independent of k (Neiman 2016, used in Lemma B.1).
    Used to embed snowflaked graph metrics into low-dimensional ℓ8 space while controlling distortion.
  • standard math Empirical measure concentration for Wasserstein distances on R^m with ℓ8 (Lemma B.2, imported from Hou et al. [25]; proof omitted).
    This is the load-bearing concentration result behind Proposition 4.1 and both main theorems.
  • standard math Kantorovich-Rubinstein duality and the Hölder dual representation of W_{1/2}.
    Connects the generalization gap to the Wasserstein distance between the empirical and true node distributions.
  • domain assumption Graph is in an admissible class U_k: diameter at most 2 and minimum degree at least c_k with high probability (Assumption 3.1).
    Needed for bounded graph diameter, doubling constant bounds, and the Lipschitz constant B of GCNs.
  • domain assumption Features are bounded: entries of X lie in [-M,M] almost surely; labels and E_out are bounded (Assumption 3.2).
    Used to control diameters, uniform integrability, and the supremum over the hypothesis class.
  • domain assumption Target function and all hypotheses belong to the B-Lipschitz class F_B with respect to both features and graph metric; loss ℓ is Bℓ-Lipschitz.
    This Lipschitz structure is what allows function discrepancies to be bounded by graph metric distances.
  • domain assumption Generalized GCNs have 1-Lipschitz activations and weight matrices with ||W_l||_op ≤ β_l; the normalized graph Laplacian operator norm bound in Proposition A.1 holds.
    These conditions make GCNs fall into the Lipschitz class F_B with the explicit constant B.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Learning from one graph: transductive learning guarantees via the geometry of small random worlds." pith.science (2026). https://pith.science/paper/VGPWRSPR

@misc{pith2026250906894,
  author       = {Pith},
  title        = {Pith review of: Learning from one graph: transductive learning guarantees via the geometry of small random worlds},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VGPWRSPR}},
  note         = {Machine review of arXiv:2509.06894}
}
abstract

Since their introduction by Kipf and Welling in $2017$, a primary use of graph convolutional networks is transductive node classification, where missing labels are inferred within a single observed graph and its feature matrix. Despite the widespread use of the network model, the statistical foundations of transductive learning remain limited, as standard inference frameworks typically rely on multiple independent samples rather than a single graph. In this work, we address these gaps by developing new concentration-of-measure tools that leverage the geometric regularities of large graphs via low-dimensional metric embeddings. The emergent regularities are captured using a random graph model; however, the methods remain applicable to deterministic graphs once observed. We establish two principal learning results. The first concerns arbitrary deterministic $k$-vertex graphs, and the second addresses random graphs that share key geometric properties with an Erd\H{o}s-R\'{e}nyi graph $\mathbf{G}=\mathbf{G}(k,p)$ in the regime $p \in \mathcal{O}((\log (k)/k)^{1/2})$. The first result serves as the basis for and illuminates the second. We then extend these results to the graph convolutional network setting, where additional challenges arise. Lastly, our learning guarantees remain informative even with a few labelled nodes $N$ and achieve the optimal nonparametric rate $\mathcal{O}(N^{-1/2})$ as $N$ grows.

Discussion (0). Sign in to comment.

Forward citations

Cited by 2 Pith papers

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

  1. Statistical Guarantees for Reasoning Probes on Looped Boolean Circuits

    stat.ML 2026-02 conditional novelty 6.0 of 10

    GCN-parameterized reasoning probes on looped ν-ary Boolean circuits achieve O(1/√N) transductive generalization error with high probability, independent of circuit size when the snowflake loss exponent α≍1/h.

  2. Finite-Agent Stochastic Differential Games on Large Graphs: II. Graph-Based Architectures

    cs.LG 2025-09 conditional novelty 5.0 of 10

    A graph-sparsified neural network, NTM, approximates Nash equilibrium strategies in stochastic differential games with far fewer trainable parameters and accuracy comparable to fully connected networks.

Reference graph

Works this paper leans on

68 extracted references · 59 canonical work pages · cited by 2 Pith papers

  1. [25]

    Instance- dependent generalization bounds via optimal transport.Journal of Machine Learning Research, 24(349):1–51, 2023

    Songyan Hou, Parnian Kassraie, Anastasis Kratsios, Andreas Krause, and Jonas Rothfuss. Instance- dependent generalization bounds via optimal transport.Journal of Machine Learning Research, 24(349):1–51, 2023

    work page 2023

  2. [1]

    Zero-one laws of graph neural networks.Advances in Neural Information Processing Systems, 36:70733–70756, 2023

    Sam Adam-Day and Ismail Ceylan. Zero-one laws of graph neural networks.Advances in Neural Information Processing Systems, 36:70733–70756, 2023

    work page 2023

  3. [2]

    Stronger generalization bounds for deep nets via a compression approach

    Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via a compression approach. InInternational Conference on Machine Learning, pages 254–263. PMLR, 2018

    2018

  4. [3]

    Plongements Lipschitziens dansRn.Bulletin de la Société Mathématique de France, 111:429–448, 1983

    Patrice Assouad. Plongements Lipschitziens dansRn.Bulletin de la Société Mathématique de France, 111:429–448, 1983

    work page 1983

  5. [4]

    High-dimensional analysis of double descent for linear regression with random projections

    Francis Bach. High-dimensional analysis of double descent for linear regression with random projections. SIAM Journal on Mathematics of Data Science, 6(1):26–50, 2024

    work page 2024

  6. [5]

    Failures of model-dependent generalization bounds for least-norm interpolation.Journal of Machine Learning Research, 22(204):1–15, 2021

    Peter L Bartlett and Philip M Long. Failures of model-dependent generalization bounds for least-norm interpolation.Journal of Machine Learning Research, 22(204):1–15, 2021

    work page 2021

  7. [6]

    Two models of double descent for weak features.SIAM Journal on Mathematics of Data Science, 2(4):1167–1180, 2020

    Mikhail Belkin, Daniel Hsu, and Ji Xu. Two models of double descent for weak features.SIAM Journal on Mathematics of Data Science, 2(4):1167–1180, 2020

    2020

  8. [7]

    Cambridge University Press, Cambridge, second edition, 2001

    Béla Bollobás.Random graphs, volume 73 ofCambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, second edition, 2001

    work page 2001

Show all 68 references
  1. [8]

    Compositional PAC-bayes: Generalization of GNNs with persistence and beyond

    Kirill Brilliantov, Amauri H Souza, and Vikas Garg. Compositional PAC-bayes: Generalization of GNNs with persistence and beyond. InThe Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024

    2024

  2. [9]

    Geometric deep learning: Grids, groups, graphs, geodesics, and gauges.arXiv preprint arXiv:2104.13478, 2021

    Michael M Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković. Geometric deep learning: Grids, groups, graphs, geodesics, and gauges.arXiv preprint arXiv:2104.13478, 2021

    2021 arXiv

  3. [10]

    Tony Cai and Mark G

    T. Tony Cai and Mark G. Low. Testing composite hypotheses, Hermite polynomials and optimal esti- mation of a nonsmooth functional.The Annals of Statistics, 39(2):1012–1041, 2011

    2011

  4. [11]

    Mean field games with common noise.The Annals of Probability, 44(6):3740–3803, 2016

    René Carmona, Francois Delarue, and Daniel Lacker. Mean field games with common noise.The Annals of Probability, 44(6):3740–3803, 2016

    2016

  5. [12]

    Connected components in random graphs with given expected degree sequences.Annals of Combinatorics, 6(2):125–145, 2002

    Fan Chung and Linyuan Lu. Connected components in random graphs with given expected degree sequences.Annals of Combinatorics, 6(2):125–145, 2002

    2002

  6. [13]

    Das and Pawan Kumar

    Kinkar Ch. Das and Pawan Kumar. Some new bounds on the spectral radius of graphs.Discrete Mathematics, 281(1-3):149–161, 2004

    2004

  7. [14]

    A non-probabilistic proof of the Assouad embedding theorem with bounds on the dimension.Analysis and Geometry in Metric Spaces, 1(2013):36–41, 2013

    Guy David and Marie Snipes. A non-probabilistic proof of the Assouad embedding theorem with bounds on the dimension.Analysis and Geometry in Metric Spaces, 1(2013):36–41, 2013

    2013

  8. [15]

    McKean-Vlasov optimal control: the dynamic programming principle.The Annals of Probability, 50(2):791–833, 2022

    Mao Fabrice Djete, Dylan Possamaï, and Xiaolu Tan. McKean-Vlasov optimal control: the dynamic programming principle.The Annals of Probability, 50(2):791–833, 2022

    2022

  9. [16]

    Doublingconstantsandspectraltheory on graphs.Discrete Mathematics, 346(6):Paper No

    EstibalitzDurand-Cartagena, JavierSoria, andPedroTradacete. Doublingconstantsandspectraltheory on graphs.Discrete Mathematics, 346(6):Paper No. 113354, 17, 2023

    2023

  10. [17]

    Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data.arXiv preprint arXiv:1703.11008, 2017

    Gintare Karolina Dziugaite and Daniel M Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data.arXiv preprint arXiv:1703.11008, 2017

    2017 arXiv

  11. [18]

    On the approximation capability of gnns in node classification/regression tasks.Soft Computing, 28(13):8527– 8547, 2024

    Giuseppe Alessio D’Inverno, Monica Bianchini, Maria Lucia Sampoli, and Franco Scarselli. On the approximation capability of gnns in node classification/regression tasks.Soft Computing, 28(13):8527– 8547, 2024

    2024

  12. [19]

    Transductive Rademacher complexity and its applications.Journal of Artificial Intelligence Research, 35:193–234, 2009

    Ran El-Yaniv and Dmitry Pechyony. Transductive Rademacher complexity and its applications.Journal of Artificial Intelligence Research, 35:193–234, 2009. 29

    2009

  13. [20]

    On the rate of convergence in Wasserstein distance of the empirical measure.Probability Theory and Related Fields, 162(3):707–738, 2015

    Nicolas Fournier and Arnaud Guillin. On the rate of convergence in Wasserstein distance of the empirical measure.Probability Theory and Related Fields, 162(3):707–738, 2015

    2015

  14. [21]

    Generalization and representational limits of graph neural networks

    Vikas Garg, Stefanie Jegelka, and Tommi Jaakkola. Generalization and representational limits of graph neural networks. InInternational Conference on Machine Learning, pages 3419–3430. PMLR, 2020

    2020

  15. [22]

    Fast construction of nets in low-dimensional metrics and their applications.SIAM Journal on Computing, 35(5):1148–1184, 2006

    Sariel Har-Peled and Manor Mendel. Fast construction of nets in low-dimensional metrics and their applications.SIAM Journal on Computing, 35(5):1148–1184, 2006

    2006

  16. [23]

    Universitext

    Juha Heinonen.Lectures on analysis on metric spaces. Universitext. Springer-Verlag, New York, 2001

    2001

  17. [24]

    Cambridge university press, 2012

    Roger A Horn and Charles R Johnson.Matrix analysis. Cambridge university press, 2012

    2012

  18. [26]

    Big Data + Big Cities: Graph Signals of Urban Air Pollution [Exploratory Sp].IEEE Signal Processing Magazine, 31(5):130–136, 2014

    Rishee K Jain, Jose MF Moura, and Constantine E Kontokosta. Big Data + Big Cities: Graph Signals of Urban Air Pollution [Exploratory Sp].IEEE Signal Processing Magazine, 31(5):130–136, 2014

    2014

  19. [27]

    Practical graph signal sampling with log-linear size scaling

    Ajinkya Jayawant and Antonio Ortega. Practical graph signal sampling with log-linear size scaling. Signal Processing, 194:108436, 2022

    2022

  20. [28]

    Prediction of protein–protein interaction using graph neural networks.Scientific Reports, 12(1):8360, 2022

    Kanchan Jha, Sriparna Saha, and Hiteshi Singh. Prediction of protein–protein interaction using graph neural networks.Scientific Reports, 12(1):8360, 2022

    2022

  21. [29]

    Minimax estimation of functionals of discrete distributions.IEEE Transactions on Information Theory, 61(5):2835–2885, 2015

    Jiantao Jiao, Kartik Venkat, Yanjun Han, and Tsachy Weissman. Minimax estimation of functionals of discrete distributions.IEEE Transactions on Information Theory, 61(5):2835–2885, 2015

    2015

  22. [30]

    Personalized Explanations for Early Diagnosis of Alzheimer’s Disease Using Explainable Graph Neural Networks with Population Graphs.Bioengineering, 10(6):701, 2023

    So Yeon Kim. Personalized Explanations for Early Diagnosis of Alzheimer’s Disease Using Explainable Graph Neural Networks with Population Graphs.Bioengineering, 10(6):701, 2023

    2023

  23. [31]

    Kipf and Max Welling

    Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In Proceedings of the International Conference on Learning Representations (ICLR), 2017

    2017

  24. [32]

    Kloeckner

    Benoît R. Kloeckner. Empirical measures: regularity is a counter-curse to dimensionality.ESAIM. Probability and Statistics, 24:408–434, 2020

    2020

  25. [33]

    Exactlowerboundsfortheagnosticprobably-approximately-correct (PAC) machine learning model.The Annals of Statistics, 47(5):2822–2854, 2019

    AryehKontorovichandIosifPinelis. Exactlowerboundsfortheagnosticprobably-approximately-correct (PAC) machine learning model.The Annals of Statistics, 47(5):2822–2854, 2019

    2019

  26. [34]

    Tighter generalization bounds on digital computers via discrete optimal transport.arXiv preprint arXiv:2402.05576, 2024

    Anastasis Kratsios, A Martina Neuman, and Gudmund Pammer. Tighter generalization bounds on digital computers via discrete optimal transport.arXiv preprint arXiv:2402.05576, 2024

    2024 arXiv

  27. [35]

    Learning skillful medium-range global weather forecasting.Science, 382(6677):1416–1421, 2023

    Remi Lam, Alvaro Sanchez-Gonzalez, Matthew Willson, Peter Wirnsberger, Meire Fortunato, Ferran Alet, Suman Ravuri, Timo Ewalds, Zach Eaton-Rosen, Weihua Hu, et al. Learning skillful medium-range global weather forecasting.Science, 382(6677):1416–1421, 2023

    2023

  28. [36]

    Lepski, A

    O. Lepski, A. Nemirovski, and V. Spokoiny. On estimation of theLr norm of a regression function. Probability Theory and Related Fields, 113(2):221–253, 1999

    1999

  29. [37]

    A graphon-signal analysis of graph neural networks.Advances in Neural Information Pro- cessing Systems, 36:64482–64525, 2023

    Ron Levie. A graphon-signal analysis of graph neural networks.Advances in Neural Information Pro- cessing Systems, 36:64482–64525, 2023

    2023

  30. [38]

    A pac-bayesian approach to generalization bounds for graph neural networks.arXiv preprint arXiv:2012.07690, 2020

    Renjie Liao, Raquel Urtasun, and Richard Zemel. A pac-bayesian approach to generalization bounds for graph neural networks.arXiv preprint arXiv:2012.07690, 2020

    2012 arXiv

  31. [39]

    Lorentz, Manfred v

    George G. Lorentz, Manfred v. Golitschek, and Yuly Makovoz.Constructive approximation - Advanced Problems, volume 304 ofGrundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Springer-Verlag, Berlin, 1996. Advanced problems

    1996

  32. [40]

    Cambridge University Press, 2021

    Yao Ma and Jiliang Tang.Deep learning on graphs. Cambridge University Press, 2021

    2021

  33. [41]

    Generalization bounds for message passing networks on mixture of graphons.SIAM Journal on Mathematics of Data Science, 7(2):802–825, 2025

    Sohir Maskey, Gitta Kutyniok, and Ron Levie. Generalization bounds for message passing networks on mixture of graphons.SIAM Journal on Mathematics of Data Science, 7(2):802–825, 2025. 30

    2025

  34. [42]

    Bi-lipschitz embeddings into low-dimensional euclidean spaces.Commentationes Math- ematicae Universitatis Carolinae, 031(3):589–600, 1990

    Jiří Matoušek. Bi-lipschitz embeddings into low-dimensional euclidean spaces.Commentationes Math- ematicae Universitatis Carolinae, 031(3):589–600, 1990

    1990

  35. [43]

    Springer- Verlag, New York, 2002

    Jiří Matoušek.Lectures on discrete geometry, volume 212 ofGraduate Texts in Mathematics. Springer- Verlag, New York, 2002

    2002

  36. [44]

    When and why are deep networks better than shallow ones? InProceedings of the AAAI conference on artificial intelligence, volume 31, 2017

    Hrushikesh Mhaskar, Qianli Liao, and Tomaso Poggio. When and why are deep networks better than shallow ones? InProceedings of the AAAI conference on artificial intelligence, volume 31, 2017

    2017

  37. [45]

    Assouad’s theorem with dimension independent of the snowflaking.Revista Matematica Iberoamericana, 28(4):1123–1142, 2012

    Assaf Naor and Ofer Neiman. Assouad’s theorem with dimension independent of the snowflaking.Revista Matematica Iberoamericana, 28(4):1123–1142, 2012

    2012

  38. [46]

    Low dimensional embeddings of doubling metrics.Theory Comput

    Ofer Neiman. Low dimensional embeddings of doubling metrics.Theory Comput. Syst., 58(1):133–152, 2016

    2016

  39. [47]

    A Martina Neuman, Rongrong Wang, and Yuying Xie. Theoretical guarantees for the advantage of GNNs over NNs in generalizing bandlimited functions on Euclidean cubes.Information and Inference: A Journal of the IMA, 14(2):iaaf007, 2025

    2025

  40. [48]

    Kenta Oono and Taiji Suzuki. Optimization and generalization analysis of transduction through gra- dient boosting and application to multi-scale graph neural networks.Advances in Neural Information Processing Systems, 33:18917–18930, 2020

    2020

  41. [49]

    Fake news detection: A survey of graph neural network methods.Applied Soft Computing, 139:110235, 2023

    Huyen Trang Phan, Ngoc Thanh Nguyen, and Dosam Hwang. Fake news detection: A survey of graph neural network methods.Applied Soft Computing, 139:110235, 2023

    2023

  42. [50]

    Real analysis, 4th edition.Printice-Hall Inc, Boston, 2010

    Halsey Lawrence Royden and PM Fitzpatrick. Real analysis, 4th edition.Printice-Hall Inc, Boston, 2010

    2010

  43. [51]

    The Vapnik-Chervonenkis dimension of graph and recursive neural networks.Neural Networks, 108:248–259, 2018

    Franco Scarselli, Ah Chung Tsoi, and Markus Hagenbuchner. The Vapnik-Chervonenkis dimension of graph and recursive neural networks.Neural Networks, 108:248–259, 2018

    2018

  44. [52]

    Metric spaces and completely monotone functions.Annals of Mathematics, 39(4):811–841, 1938

    Isaac J Schoenberg. Metric spaces and completely monotone functions.Annals of Mathematics, 39(4):811–841, 1938

    1938

  45. [53]

    Cambridge university press, 2014

    Shai Shalev-Shwartz and Shai Ben-David.Understanding machine learning: From theory to algorithms. Cambridge university press, 2014

    2014

  46. [54]

    Homophily modulates double descent generalization in graph convolution networks.Proceedings of the National Academy of Sciences, 121(8):e2309504121, 2024

    Cheng Shi, Liming Pan, Hong Hu, and Ivan Dokmanić. Homophily modulates double descent generalization in graph convolution networks.Proceedings of the National Academy of Sciences, 121(8):e2309504121, 2024

    2024

  47. [55]

    The least doubling constant of a metric measure space.Annales Fennici Mathematici, 44(2):1015–1030, 2019

    Javier Soria and Pedro Tradacete. The least doubling constant of a metric measure space.Annales Fennici Mathematici, 44(2):1015–1030, 2019

    2019

  48. [56]

    Bronstein

    Baskaran Sripathmanathan, Xiaowen Dong, and Michael M. Bronstein. On the impact of sample size in reconstructing graph signals. InFourteenth International Conference on Sampling Theory and Appli- cations, 2023

    2023

  49. [57]

    Information-theoretic generalization bounds for transductive learning and its applications.arXiv preprint arXiv:2311.04561, 2023

    Huayi Tang and Yong Liu. Information-theoretic generalization bounds for transductive learning and its applications.arXiv preprint arXiv:2311.04561, 2023

    2023 arXiv

  50. [58]

    Weak convergence

    Aad W Van Der Vaart and Jon A Wellner. Weak convergence. InWeak convergence and empirical processes: with applications to statistics. Springer, 1996

    1996

  51. [59]

    Estimation of dependences based on empirical data: Springer series in statistics (springer series in statistics), 1982

    Vladimir Vapnik. Estimation of dependences based on empirical data: Springer series in statistics (springer series in statistics), 1982

    1982

  52. [60]

    Springer, 2009

    Cédric Villani et al.Optimal transport: old and new, volume 338. Springer, 2009

    2009

  53. [61]

    Recommending related products using graph neural networks in directed graphs

    Srinivas Virinchi, Anoop Saladi, and Abhirup Mondal. Recommending related products using graph neural networks in directed graphs. InJoint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 541–557. Springer, 2022. 31

    2022

  54. [62]

    Machining feature process route planning based on a graph convolutional neural network.Advanced Engineering Informatics, 59:102249, 2024

    Zhen Wang, Shusheng Zhang, Hang Zhang, Yajun Zhang, Jiachen Liang, Rui Huang, and Bo Huang. Machining feature process route planning based on a graph convolutional neural network.Advanced Engineering Informatics, 59:102249, 2024

    2024

  55. [63]

    Sharp generalization of transductive learning: A transductive local Rademacher com- plexity approach.arXiv preprint arXiv:2309.16858, 2023

    Yingzhen Yang. Sharp generalization of transductive learning: A transductive local Rademacher com- plexity approach.arXiv preprint arXiv:2309.16858, 2023

    2023

  56. [64]

    Corner Gradient Descent.arXiv preprint arXiv:2504.12519, 2025

    Dmitry Yarotsky. Corner Gradient Descent.arXiv preprint arXiv:2504.12519, 2025

    2025 arXiv

  57. [65]

    The phase diagram of approximation rates for deep neural networks

    Dmitry Yarotsky and Anton Zhevnerchuk. The phase diagram of approximation rates for deep neural networks. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors,Advances in Neural Information Processing Systems, volume 33, pages 13005–13015. Curran Associat...

    2020

  58. [66]

    Strong data processing inequalities for locally differentially private mechanisms

    Behnoosh Zamanlooy and Shahab Asoodeh. Strong data processing inequalities for locally differentially private mechanisms. In2023 IEEE International Symposium on Information Theory (ISIT), pages 1794–1799. IEEE, 2023

    2023

  59. [67]

    Link prediction based on graph neural networks

    Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. InAdvances in Neural Information Processing Systems (NeurIPS), volume 31, 2018

    2018

  60. [68]

    Dgcn: Diversified recommendation with graph convolutional networks

    Yu Zheng, Chen Gao, Liang Chen, Depeng Jin, and Yong Li. Dgcn: Diversified recommendation with graph convolutional networks. InProceedings of the Web Conference 2021, pages 401–412, 2021. 32

    2021

Pith tools

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