Pith. sign in

REVIEW 4 major objections 6 minor 57 references

PAC-Bayesian Generalization Bounds for Graph Convolutional Networks on Inductive Node Classification

T0 review · 4 major / 6 minor · reviewed 2026-08-15 · deepseek-v4-flash

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

Pith's one-line read For one-layer GCNs, expected risk on newly arriving nodes is bounded by empirical risk plus explicit penalties for data dependence, distribution shift, and link-pattern mismatch, with the sampling term decaying under a Markov assumption.

desk verdict New inductive GCN setting worth attention, but a norm mismatch in the proof breaks the announced convergence to zero. read the letter →

arxiv 2509.06600 v1 pith:PY4FHE3W submitted 2025-09-08 cs.LG

Huayi Tang , Yong Liu This is my paper · ORCID
classification cs.LG MSC 68Q3268T0760J05
keywords PAC-Bayesianboundsgraphconvolutionalnetworksinductivenodeclassificationgeneralizationdependentdatanon-identicallydistributedMarkovchainsRényidivergence
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 proves PAC-Bayesian generalization bounds for graph convolutional networks in the inductive setting, where the model must classify new nodes whose features and connections were unknown during training. Because nodes are neither independent nor identically distributed, the authors first derive a general PAC-Bayesian bound for dependent, non-identically distributed data, then specialize it to one- and two-layer GCNs. The bound splits the inductive generalization gap into a concentration term governed by a dependency matrix $\Gamma$, plus total-variation terms measuring how far the incoming node's distribution is from the training nodes and how far the real link-formation process is from an auxiliary distribution that mimics an existing node's neighborhood. When the node stream is modeled as a geometrically ergodic Markov chain, the sampling term decays as $O(\sqrt{\log n / n})$ and the remaining constants depend on how fast the chain mixes to stationarity. The two-layer extension shows that depth moves the burden to graph topology: the squared Frobenius norm of the normalized adjacency matrix must grow slower than $n$ for the gap to vanish.

What carries the argument

The argument is carried by three linked devices. First, a general PAC-Bayesian bound (Theorem 3.1) for dependent and non-identically distributed data, which uses Rényi divergence for the change of measure and encodes dependence through the Wasserstein matrix $\Gamma$, whose $(i,j)$-th entry measures how perturbing the $i$-th data point shifts the conditional law of later points. Second, the decomposition of the generalization gap into $E_1$ (the part of the empirical risk that is unbiased in expectation) and $E_2$ (the biased part), with $E_2$ handled by inserting an auxiliary distribution over the new node's aggregation coefficients that copies the neighborhood pattern of one training node. Third, Assumption 3.1, the decoupling condition that the new node's features are independent of its aggregation coefficients and of the existing graph's node features, which makes the $E_2$ decomposition valid. Under the Markov-chain assumption, Proposition 3.3 shows the norms $\|\Gamma\|$ and $\|\widetilde{\Gamma}\|_\infty$ are $O(1)$ constants determined by the chain's mixing rate, yielding Corollary 3.1 with explicit constants.

What would settle it

On any real graph dataset, compute the mutual information between a held-out node's features and its connection vector to the training graph; if it is non-negligible, Assumption 3.1 is violated. Then train a one-layer GCN and compare the observed generalization gap against the paper's bound at the stated confidence level: if the gap systematically exceeds the bound, the decoupling premise is the cause.

Watch

Extended reading notes

Core claim

The central result, Theorem 3.3, states that with probability at least $1-\delta$ over the randomness of the training nodes and the adjacency matrix, the posterior-expected risk of a one-layer GCN on the incoming node is at most its empirical risk plus three explicit charges: a concentration term built from the Wasserstein dependency matrix $\Gamma$ and a Lipschitz sensitivity vector; the mean total-variation distance between the conditional law of the new node and the conditional laws of older nodes, which measures non-stationarity; a conditional-dependency term; and the total variation between the true distribution of the incoming node's aggregation coefficients and an auxiliary distribution. The technical core is a decomposition of the gap into an unbiased part $E_1$, handled by martingale concentration, and a biased part $E_2$, re-expressed through the auxiliary distribution and bounded by the discrepancy terms. Under a geometrically ergodic Markov assumption on the node sequence, the concentration term becomes $O(\sqrt{\log n / n})$ and the non-stationarity terms converge to the expected distance between the transition kernel and its stationary distribution, giving a full convergence statement for the inductive gap.

Load-bearing premise

The whole argument rests on the new node's features being statistically independent of how it attaches to the existing graph and of the existing nodes' features; in real networks, where edges form because of node attributes, that premise fails and the bound no longer applies.

Editorial extensions

If this is right

  • Under a geometrically ergodic Markov model of the node stream, a one-layer GCN's inductive generalization gap converges to zero at rate $O(\sqrt{\log n / n})$ plus a constant fixed by the chain's mixing speed, so adding nodes provably helps in stationary regimes up to that floor.
  • Distribution shift is priced separately: the bound grows with the total-variation distance between the incoming node's conditional distribution and those of the older nodes, so a drifting node distribution shows up directly in the guarantee.
  • For two-layer GCNs the squared Frobenius norm of the normalized adjacency matrix must be $o(n)$ for the gap to vanish — satisfied, for instance, by hub–leaf graphs with $o(n)$ leaf–leaf edges — so extra depth shifts the convergence burden onto graph topology.
  • The bound isolates sampling dependence, distribution shift, and link-pattern mismatch as three separate additive costs, which makes it usable as a diagnostic for which factor dominates an inductive failure.

Reading between the lines

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

  • The authors leave implicit that on persistently drifting graphs the non-stationarity terms never vanish, so beyond a certain sample size more training nodes stop shrinking the gap; the practical lever becomes modeling the dynamics, not collecting more snapshots.
  • A testable extension: estimate the three total-variation terms on a real dynamic network and compare the predicted bound with the measured gap to identify which source of error dominates in practice.
  • The auxiliary-distribution trick — replacing the real attachment distribution with one that copies an existing node's neighborhood — could serve as a template for inductive guarantees of attention-based or other feature-dependent aggregators, but only if their edge-formation model is made explicit rather than assumed away.
  • The result suggests that purely topological conditions on normalized adjacency matrices are the wrong place to look for two-layer guarantees; the extra cost of depth appears to come from feature–edge coupling, which the one-layer analysis sidesteps by assumption.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

4 major / 6 minor

Summary. The paper studies inductive node classification with GCNs under a PAC-Bayesian framework. It treats the training nodes as dependent, non-identically distributed random variables and models the test node as a newly added node with random features and random connections. The authors first prove a general PAC-Bayesian bound for dependent data (Theorem 3.1) using Wasserstein-matrix concentration and Rényi divergence, together with a Langford-Seeger-Maurer-type version and a single-draw bound (Theorem 3.2). They then specialize to one-layer GCNs by decomposing the inductive generalization gap into an unbiased term E1 and a biased term E2; the E2 analysis introduces an auxiliary distribution over the new node's aggregation coefficients and produces terms measuring non-stationarity, conditional dependence, and the mismatch between true and auxiliary connection distributions. Under a geometrically ergodic Markov chain assumption, Corollary 3.1 claims a bound of order O(sqrt(log n / n)) plus constants depending on the chain's mixing. Theorem 3.4 extends the analysis to two-layer GCNs, with an additional dependence on the squared Frobenius norm of the normalized adjacency matrix. The appendix contains all proofs.

Significance. Conceptually, the paper's decomposition of the inductive gap into E1 and E2 is a useful way to separate data non-stationarity, data dependence, and distribution mismatch of the new node's neighborhood, and the general dependent-data bound in Theorem 3.1 may be of independent interest. The Markov-chain refinement in Propositions 3.3 and 3.4 and the explicit hub-leaf example for the two-layer normalization term are concrete, nontrivial elements. If the technical gaps identified below are repaired, the paper would be a valuable contribution to the theory of GNN generalization in inductive settings. The authors are also transparent in Section 4 that Assumption 3.1 excludes feature-dependent edge formation, so the practical scope is narrower than the abstract's general phrasing. At present, however, the central convergence claim is not established because of the norm mismatch in the proofs and the invalid example distribution in Eq. (29).

major comments (4)
  1. [A.3, Eqs. (66)-(67); Theorem 3.3; Eq. (128)] Assumption 2.2 bounds the Frobenius norm of the normalized adjacency matrices, but the proof of Proposition 3.1 uses the infinity-norm bound sum_{j != i} tilde-a_{j,i} <= ||tilde-a||_infty <= c_a. For a d-regular graph, ||tilde-a||_F = sqrt(n/(d+1)) grows with n while every row sum equals 1, so the constant c_a cannot be taken as O(1) from Assumption 2.2. If c_a is set to the Frobenius bound, the concentration term in Theorem 3.3 scales as Theta(sqrt(log n)) rather than the advertised O(sqrt(log n / n)). Interpreting c_a as a row-sum bound would be a new assumption, and it is violated by graphs with a hub of degree Omega(n). The same Frobenius-versus-infinity misuse occurs in Eq. (128) in the two-layer proof. This is load-bearing for the convergence-to-zero claim in Corollary 3.1 and for the corresponding claim in Theorem 3.4.
  2. [Section 2.2, Eq. (20), Eq. (23)] There is an inconsistency between the definition of A_{n+1,[n+1]} as binary edge indicators and its use as real-valued normalized aggregation coefficients. Section 2.2 specifies A_{i,j} in {0,1}, A_{n+1,n+1}=0, and symmetry A_{i,n+1}=A_{n+1,i}; the forward model in Eq. (4) then uses A_{n+1,k} as unnormalized coefficients. However, the auxiliary distribution in Eq. (20) assigns probability to events {A_{n+1,k} = tilde-A_{i,k}} with normalized real values, and Eq. (23) evaluates the loss at such real-valued coefficient vectors. Under the stated binary semantics these events are outside the support of a binary-valued A_{n+1,[n+1]}, and the forward computation would not be the one in Eq. (23). The paper should either redefine A_{n+1,[n+1]} as real-valued normalized coefficients throughout or construct a binary auxiliary distribution; as written, the E2 decomposition and the total variation term D_TV(P_A,Q_A) are not well posed.
  3. [Eqs. (28)-(30), Corollary 3.1] The distribution P_A defined in Eq. (29) is not shown to be a valid probability measure. The n+k events listed are disjoint only if the vectors tilde-A_i (with coordinate i set to 0 and coordinate n+1 set to tilde-A_{i,i}) are all distinct from one another and from all tilde-b_j; no such condition is imposed on the set tilde-B in Eq. (28). If, for example, some tilde-b_j equals one of these modified tilde-A_i rows, the assigned probabilities sum to more than 1. Since Eq. (30)'s value D_TV(P_A,Q_A)=1/sqrt(n) and hence the M/sqrt(n) term in Corollary 3.1 depend on this construction, the convergence demonstration for the auxiliary-distribution term is incomplete.
  4. [Assumption 3.1 and Section 4] The decoupling in Assumption 3.1 is the load-bearing step that makes the E2 decomposition in Eq. (22) valid: it replaces the joint conditional law of the new node's features and connections by a product of marginals. The authors acknowledge in Section 4 that this excludes feature-dependent edge formation, such as graph attention mechanisms, so the advertised scope is narrower than the introduction suggests. This is a stated restriction rather than a hidden flaw, but the abstract and Theorem 3.3 should be phrased explicitly as conditional on Assumption 3.1; the current wording suggests coverage of general dynamic graphs without the qualifier.
minor comments (6)
  1. [Abstract] The phrase 'we presents' is a typo and should read 'we present'.
  2. [Section 2.2] The sentence 'where V and E are the edge sets and node sets, respectively' reverses the definitions; V is the node set and E is the edge set.
  3. [Introduction, Section 3] The introduction states that 'the experimental setting and results are detailed in Section', but the manuscript contains no experimental section; either add one or remove the sentence.
  4. [Eq. (38)] The inequality sum_i p_i(1-p_i) <= (N-1)/N^2 appears to be off by a factor of N; the standard bound is 1 - sum_i p_i^2 <= (N-1)/N, and equality holds for the uniform distribution. The qualitative conclusion is unaffected because max_j alpha_j can be chosen small, but the displayed inequality is false.
  5. [Corollary 3.1 and Theorem 3.3] Corollary 3.1 uses log(2*sqrt(n)/delta) while Theorem 3.3 has log(2*sqrt(2n)/delta); the discrepancy should be reconciled.
  6. [Throughout] The notation for the independent copy of the sample is inconsistent: E_{S'[n]}[...] and E_{S'}[...] are used interchangeably, and the arguments sometimes mix s[n] and S'[n]. Unifying this notation would improve readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation: the PAC-Bayesian bounds follow from external concentration and change-of-measure inequalities; the constructed auxiliary and Markov distributions are explicit sufficient conditions, not fitted predictions.

full rationale

The derivation chain is self-contained. Theorem 3.1 is obtained by combining the Kontorovich–Raginsky/Kontorovich–Ramanan concentration inequality (Eq. (44), appendix A.1) with the standard variational formula for Rényi divergence; neither ingredient is supplied by the paper's own claims. Theorem 3.2 then follows by sub-Gaussian and Rényi-change-of-measure arguments (Wainwright, Esposito et al.), again independent. Proposition 3.1 computes the Hamming Lipschitz constants of the decomposed empirical-risk term directly from Assumptions 2.1–2.6, and Proposition 3.2 bounds the bias term E2 by a triangle inequality over an explicitly constructed auxiliary distribution Q in Eq. (20); the bound's dependence on DTV(P_A,Q) is a genuine statement about the true attachment distribution, not a restatement of the conclusion. Corollary 3.1 is explicitly conditional: it assumes P_A is the distribution in Eq. (29) and a Markov chain satisfying Proposition 3.3; the TV terms are then bounded by direct computation (Eq. (30)) and by geometric ergodicity (Proposition 3.4). The Markov example in Section 3.2 is likewise presented as an existence example with tunable alpha_j, not as a fitted prediction. The only self-citations (Tang and Liu 2023) are contextual (transductive framework, log-softmax Lipschitz constant) and are not load-bearing: the Lipschitz fact is a simple calculation and the theorems use generic constants. The paper also explicitly flags the limitation that Assumption 3.1 decouples features from aggregation coefficients, which is a scope restriction rather than a hidden circular input. A separate mathematical concern exists: the proof of Proposition 3.1 uses ||a_tilde||_infinity <= c_a at Eq. (67) while Assumption 2.2 bounds only the Frobenius norm; this is a correctness issue in the claimed O(sqrt(log n/n)) rate, not a circularity, and does not affect the circularity score.

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

The central claim rests on standard PAC-Bayesian and concentration machinery, plus a set of regularity assumptions common in GNN theory. The most fragile step is Assumption 3.1, which decouples the new node's features from its graph connections. The convergence results also rely on the ad hoc construction of P_A in Eq. (29) and a chosen Markov chain example, which limits the generality of the 'converges to zero' statement.

free parameters (2)
  • mass parameters of P_A in Eq. (29) = 1/n - 1/n^(3/2) per row; 1/(k sqrt(n)) per extra event
    Chosen so that D_TV(P_A, Q_A) = 1/sqrt(n) in Eq. (30). This is an ad hoc construction used to demonstrate convergence in Corollary 3.1.
  • Markov example coefficients alpha_j = max_j alpha_j <= epsilon/2
    Chosen to make the non-stationarity slack E_{S~pi}[D_TV(P(S,.),pi)] arbitrarily small. Only affects the illustrative finite-state example, not the general bound.
assumptions (5)
  • domain assumption Assumption 3.1: S_{n+1} is independent of A_{n+1,[n+1]} and (A_{i,j})_{n×n}, and A_{n+1,[n+1]} is independent of S_[n]
    Load-bearing for the decomposition of E2 in Proposition 3.2. Unrealistic when edge formation depends on node features; the authors explicitly acknowledge this limitation in the Discussion.
  • domain assumption S_[n] is a geometrically ergodic Markov chain in Corollary 3.1
    Used to bound the dependence matrix Gamma, Gamma-tilde, and the non-stationarity terms. Not required for the general Theorem 3.3.
  • domain assumption Bounded features, weights, adjacency, loss, and Lipschitz continuity (Assumptions 2.1 through 2.7)
    Standard regularity conditions needed to derive the finite Lipschitz constants in Propositions 3.1 and 3.4.
  • standard math Kontorovich-Raginsky concentration inequality (2017)
    Used as the dependence-aware concentration tool in the proof of Theorem 3.1.
  • ad hoc to paper The distribution P_A in Eq. (29) is a valid probability measure
    It is constructed to make D_TV(P_A, Q_A) = 1/sqrt(n). Corollary 3.1 assumes this distribution to show a vanishing slack term.

how reviews work

0 comments
Cite this review

Pith. "Pith review of PAC-Bayesian Generalization Bounds for Graph Convolutional Networks on Inductive Node Classification." pith.science (2026). https://pith.science/paper/PY4FHE3W

@misc{pith2026250906600,
  author       = {Pith},
  title        = {Pith review of: PAC-Bayesian Generalization Bounds for Graph Convolutional Networks on Inductive Node Classification},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PY4FHE3W}},
  note         = {Machine review of arXiv:2509.06600}
}
read the original abstract

Graph neural networks (GNNs) have achieved remarkable success in processing graph-structured data across various applications. A critical aspect of real-world graphs is their dynamic nature, where new nodes are continually added and existing connections may change over time. Previous theoretical studies, largely based on the transductive learning framework, fail to adequately model such temporal evolution and structural dynamics. In this paper, we presents a PAC-Bayesian theoretical analysis of graph convolutional networks (GCNs) for inductive node classification, treating nodes as dependent and non-identically distributed data points. We derive novel generalization bounds for one-layer GCNs that explicitly incorporate the effects of data dependency and non-stationarity, and establish sufficient conditions under which the generalization gap converges to zero as the number of nodes increases. Furthermore, we extend our analysis to two-layer GCNs, and reveal that it requires stronger assumptions on graph topology to guarantee convergence. This work establishes a theoretical foundation for understanding and improving GNN generalization in dynamic graph environments.

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

57 extracted references · 49 canonical work pages

  1. [1]

    Generalization bounds for mixing processes via delayed online-to-PAC conversions

    Baptiste Ab\' e l\` e s , Eugenio Clerico, and Gergely Neu. Generalization bounds for mixing processes via delayed online-to-PAC conversions. In International Conference on Algorithmic Learning Theory, pages 23--40, 2025

    work page 2025

  2. [2]

    User-friendly introduction to PAC-Bayes bounds

    Pierre Alquier. User-friendly introduction to PAC-Bayes bounds. Foundations and Trends ^ in Machine Learning, 17 0 (2): 0 174--303, 2024

    work page 2024

  3. [3]

    Simpler PAC-Bayesian bounds for hostile data

    Pierre Alquier and Benjamin Guedj. Simpler PAC-Bayesian bounds for hostile data. Machine Learning, 107 0 (5): 0 887--902, 2018

    work page 2018

  4. [4]

    Robust bounds on risk-sensitive functionals via R \' e nyi divergence

    Rami Atar, Kenny Chowdhary, and Paul Dupuis. Robust bounds on risk-sensitive functionals via R \' e nyi divergence. SIAM/ASA Journal on Uncertainty Quantification, 3 0 (1): 0 18--33, 2015

    work page 2015

  5. [5]

    PAC-Bayesian bounds based on the R \' e nyi divergence

    Luc B \' e gin, Pascal Germain, Fran c ois Laviolette, and Jean - Francis Roy. PAC-Bayesian bounds based on the R \' e nyi divergence. In International Conference on Artificial Intelligence and Statistics, pages 435--444, 2016

    work page 2016

  6. [6]

    Graph neural networks with convolutional arma filters

    Filippo Maria Bianchi, Daniele Grattarola, Lorenzo Livi, and Cesare Alippi. Graph neural networks with convolutional arma filters. IEEE Transactions on Pattern Analysis and Machine Intelligence, 44 0 (7): 0 3496--3507, 2022

    work page 2022

  7. [7]

    Zheng, Hongyun Cai, Kevin Chen-Chuan Chang, and Erik Cambria

    Sandro Cavallari, Vincent W. Zheng, Hongyun Cai, Kevin Chen-Chuan Chang, and Erik Cambria. Learning community embedding with community detection and node embedding on graphs. In ACM on Conference on Information and Knowledge Management , page 377–386, 2017

    work page 2017

  8. [8]

    Simple and deep graph convolutional networks

    Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In International Conference on Machine Learning, pages 1725--1735, 2020

    work page 2020

Show all 57 references
  1. [9]

    Adaptive universal generalized pagerank graph neural network

    Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. In International Conference on Learning Representations, 2021

    2021

  2. [10]

    A unified recipe for deriving (time-uniform) PAC-Bayes bounds

    Ben Chugg, Hongjian Wang, and Aaditya Ramdas. A unified recipe for deriving (time-uniform) PAC-Bayes bounds. Journal of Machine Learning Research, 24 0 (372): 0 1--61, 2023

    2023

  3. [11]

    On provable benefits of depth in training graph convolutional networks

    Weilin Cong, Morteza Ramezani, and Mehrdad Mahdavi. On provable benefits of depth in training graph convolutional networks. In Advances in Neural Information Processing Systems, 2021

    2021

  4. [12]

    Convolutional neural networks on graphs with fast localized spectral filtering

    Micha\" e l Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Advances in Neural Information Processing Systems, 2016

    2016

  5. [13]

    Generalization error bounds via R \' e nyi , f -divergences and maximal leakage

    Amedeo Roberto Esposito, Michael Gastpar, and Ibrahim Issa. Generalization error bounds via R \' e nyi , f -divergences and maximal leakage. IEEE Transactions on Information Theory, 67 0 (8): 0 4986--5004, 2021

    2021

  6. [14]

    Vankadara, and Debarghya Ghoshdastidar

    Pascal Mattia Esser, Leena C. Vankadara, and Debarghya Ghoshdastidar. Learning theory can (sometimes) explain generalisation in graph neural networks. In Advances in Neural Information Processing Systems, pages 27043--27056, 2021

    2021

  7. [15]

    Recent developments in GNNs for drug discovery

    Zhengyu Fang, Xiaoge Zhang, Anyin Zhao, Xiao Li, Huiyuan Chen, and Jing Li. Recent developments in GNNs for drug discovery. arXiv preprint arXiv:2506.01302, 2025

    2025 arXiv

  8. [16]

    A comprehensive survey of dynamic graph neural networks: Models, frameworks, benchmarks, experiments and challenges

    ZhengZhao Feng, Rui Wang, TianXing Wang, Mingli Song, Sai Wu, and Shuibing He. A comprehensive survey of dynamic graph neural networks: Models, frameworks, benchmarks, experiments and challenges. arXiv preprint arXiv:2405.00476, 2024

    2024 arXiv

  9. [17]

    A survey of graph neural networks for recommender systems: Challenges, methods, and directions

    Chen Gao, Yu Zheng, Nian Li, Yinfeng Li, Yingrong Qin, Jinghua Piao, Yuhan Quan, Jianxin Chang, Depeng Jin, Xiangnan He, and Yong Li. A survey of graph neural networks for recommender systems: Challenges, methods, and directions. ACM Transactions on Recommender Systems, 1 0 (1), 2023

    2023

  10. [18]

    Generalization and representational limits of graph neural networks

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

    2020

  11. [19]

    Predict then propagate: Graph neural networks meet personalized pagerank

    Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In International Conference on Learning Representations, 2019

    2019

  12. [20]

    Schoenholz, Patrick F

    Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In International Conference on Machine Learning, pages 1263--1272, 2017

    2017

  13. [21]

    A new model for learning in graph domains

    Marco Gori, Gabriele Monfardini, and Franco Scarselli. A new model for learning in graph domains. In International Joint Conference on Neural Networks, pages 729--734, 2005

    2005

  14. [22]

    Inductive representation learning on large graphs

    Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, 2017

    2017

  15. [23]

    Foundations of Deep Learning

    Fengxiang He and Dacheng Tao. Foundations of Deep Learning. Springer, 2025

    2025

  16. [24]

    Bernnet: Learning arbitrary graph spectral filters via bernstein approximation

    Mingguo He, Zhewei Wei, Zengfeng Huang, and Hongteng Xu. Bernnet: Learning arbitrary graph spectral filters via bernstein approximation. In Advances in Neural Information Processing Systems, 2021

    2021

  17. [25]

    Generalization bounds via information density and conditional information density

    Fredrik Hellstr \"o m and Giuseppe Durisi. Generalization bounds via information density and conditional information density. IEEE Journal on Selected Areas in Information Theory, 1 0 (3): 0 824--839, 2020

    2020

  18. [26]

    Generalization bounds: Perspectives from information theory and PAC-Bayes

    Fredrik Hellstr \"o m, Giuseppe Durisi, Benjamin Guedj, and Maxim Raginsky. Generalization bounds: Perspectives from information theory and PAC-Bayes . Foundations and Trends ^ in Machine Learning, 18 0 (1): 0 1--223, 2025

    2025

  19. [27]

    Large deviations for sums of partly dependent random variables

    Svante Janson. Large deviations for sums of partly dependent random variables. Random Structure & Algorithms, 24 0 (3): 0 234–248, 2004

    2004

  20. [28]

    Kipf and Max Welling

    Thomas N. Kipf and Max Welling. Variational graph auto-encoders. NIPS Workshop on Bayesian Deep Learning, 2016

    2016

  21. [29]

    Kipf and Max Welling

    Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017

    2017

  22. [30]

    Concentration of measure without independence: A unified approach via the martingale method

    Aryeh Kontorovich and Maxim Raginsky. Concentration of measure without independence: A unified approach via the martingale method. In Convexity and Concentration, pages 183--210, 2017

    2017

  23. [31]

    Concentration inequalities for dependent random variables via the martingale method

    Leonid (Aryeh) Kontorovich and Kavita Ramanan. Concentration inequalities for dependent random variables via the martingale method . The Annals of Probability, 36 0 (6): 0 2126 -- 2158, 2008

    2008

  24. [32]

    Learning theory and algorithms for forecasting non-stationary time series

    Vitaly Kuznetsov and Mehryar Mohri. Learning theory and algorithms for forecasting non-stationary time series. In Advances in Neural Information Processing Systems, 2015

    2015

  25. [33]

    Discrepancy-based theory and algorithms for forecasting non stationary time series

    Vitaly Kuznetsov and Mehryar Mohri. Discrepancy-based theory and algorithms for forecasting non stationary time series. Annals of Mathematics and Artificial Intelligence, 88 0 (4): 0 367--399, 2020

    2020

  26. [34]

    Yujia Li, Daniel Tarlow, Marc Brockschmidt, and Richard S. Zemel. Gated graph sequence neural networks. In International Conference on Learning Representations, 2016

    2016

  27. [35]

    A PAC-Bayesian approach to generalization bounds for graph neural networks

    Renjie Liao, Raquel Urtasun, and Richard Zemel. A PAC-Bayesian approach to generalization bounds for graph neural networks. In International Conference on Learning Representations, 2021

    2021

  28. [36]

    Yu, and Chuan Shi

    Jiawei Liu, Cheng Yang, Zhiyuan Lu, Junze Chen, Yibo Li, Mengmei Zhang, Ting Bai, Yuan Fang, Lichao Sun, Philip S. Yu, and Chuan Shi. Graph foundation models: Concepts, opportunities and challenges. IEEE Transactions on Pattern Analysis and Machine Intelligence, 47 0 (6): 0 50...

    2025

  29. [37]

    Position: Graph foundation models are already here

    Haitao Mao, Zhikai Chen, Wenzhuo Tang, Jianan Zhao, Yao Ma, Tong Zhao, Neil Shah, Mikhail Galkin, and Jiliang Tang. Position: Graph foundation models are already here. In International Conference on Machine Learning, pages 34670--34692, 2024

    2024

  30. [38]

    Tweedie, and Peter W

    Sean Meyn, Richard L. Tweedie, and Peter W. Glynn. Markov Chains and Stochastic Stability. Cambridge University Press, 2009

    2009

  31. [39]

    Bronstein, Martin Grohe, and Stefanie Jegelka

    Christopher Morris, Fabrizio Frasca, Nadav Dym, Haggai Maron, Ismail Ilkan Ceylan, Ron Levie, Derek Lim, Michael M. Bronstein, Martin Grohe, and Stefanie Jegelka. Position: Future directions in the theory of graph machine learning. In International Conference on Machine Learning, 2024

    2024

  32. [40]

    Optimization and generalization analysis of transduction through gradient boosting and application to multi-scale graph neural networks

    Kenta Oono and Taiji Suzuki. Optimization and generalization analysis of transduction through gradient boosting and application to multi-scale graph neural networks. In Advances in Neural Information Processing Systems, 2020

    2020

  33. [41]

    Graph neural networks for intelligent transportation systems: A survey

    Saeed Rahmani, Asiye Baghbani, Nizar Bouguila, and Zachary Patterson. Graph neural networks for intelligent transportation systems: A survey. IEEE Transactions on Intelligent Transportation Systems, 24 0 (8): 0 8846--8885, 2023

    2023

  34. [42]

    Real and complex analysis

    Walter Rudin. Real and complex analysis. McGraw-Hill, Inc., 1987

    1987

  35. [43]

    The graph neural network model

    Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20 0 (1): 0 61--80, 2009

    2009

  36. [44]

    Towards understanding generalization of graph neural networks

    Huayi Tang and Yong Liu. Towards understanding generalization of graph neural networks. In International Conference on Machine Learning, pages 33674--33719, 2023

    2023

  37. [45]

    R \' e nyi Divergence and Kullback-Leibler Divergence

    Tim van Erven and Peter Harremos. R \' e nyi Divergence and Kullback-Leibler Divergence . IEEE Transactions on Information Theory, 60 0 (7): 0 3797--3820, 2014

    2014

  38. [46]

    Vladimir N. Vapnik. Estimation of Dependences Based on Empirical Data: Empirical Inference Science. Springer, 1982

    1982

  39. [47]

    Vladimir N. Vapnik. Statistical Learning Theory. Wiley, 1998

    1998

  40. [48]

    Survey on generalization theory for graph neural networks

    Antonis Vasileiou, Stefanie Jegelka, Ron Levie, and Christopher Morris. Survey on generalization theory for graph neural networks. arXiv preprint arXiv:2503.15650, pages 36294--36307, 2025

    2025 arXiv

  41. [49]

    Graph attention networks

    Petar Veli c kovi \' c , Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Li \` o , and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018

    2018

  42. [50]

    Wainwright

    Martin J. Wainwright. High-Dimensional Statistics: A Non-Asymptotic Viewpoint. Cambridge University Press, 2019

    2019

  43. [51]

    A review on graph neural network methods in financial applications

    Jianian Wang, Shenmin Zhang, Yanghua Xiao, and Rui Song. A review on graph neural network methods in financial applications. arXiv preprint arXiv:2111.15367, 2022

    2022 arXiv

  44. [52]

    A compact review of molecular property prediction with graph neural networks

    Oliver Wieder, Stefan Kohlbacher, Mélaine Kuenemann, Arthur Garon, Pierre Ducrot, Thomas Seidel, and Thierry Langer. A compact review of molecular property prediction with graph neural networks. Drug Discovery Today: Technologies, 37: 0 1--12, 2020

    2020

  45. [53]

    Representation learning on graphs with jumping knowledge networks

    Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken - ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In International Conference on Machine Learning, pages 5449--5458, 2018

    2018

  46. [54]

    A survey of graph transformers: Architectures, theories and applications

    Chaohao Yuan, Kangfei Zhao, Ercan Engin Kuruoglu, Liang Wang, Tingyang Xu, Wenbing Huang, Deli Zhao, Hong Cheng, and Yu Rong. A survey of graph transformers: Architectures, theories and applications. arXiv preprint arXiv:2502.16533, 2025

    2025 arXiv

  47. [55]

    The expressive power of graph neural networks: A survey

    Bingxu Zhang, Changjun Fan, Shixuan Liu, Kuihua Huang, Xiang Zhao, Jincai Huang, and Zhong Liu. The expressive power of graph neural networks: A survey. IEEE Transactions on Knowledge and Data Engineering, 37 0 (3): 0 1455–1474, 2025

    2025

  48. [56]

    Mcdiarmid-type inequalities for graph-dependent variables and stability bounds

    Rui (Ray) Zhang, Xingwu Liu, Yuyi Wang, and Liwei Wang. Mcdiarmid-type inequalities for graph-dependent variables and stability bounds. In Advances in Neural Information Processing Systems, 2019

    2019

  49. [57]

    Interpreting and unifying graph neural networks with an optimization framework

    Meiqi Zhu, Xiao Wang, Chuan Shi, Houye Ji, and Peng Cui. Interpreting and unifying graph neural networks with an optimization framework. In Proceedings of the Web Conference 2021, pages 1215--1226, 2021

    2021

Pith tools

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