Graph neural networks (GNNs), models that classify a node by repeatedly mixing its features with those of its neighbors, are routinely evaluated on one fixed graph where only a few nodes carry labels. Theory has struggled to certify how well such a model will do on the remaining unlabeled nodes. Every node's prediction depends on its neighborhood, so the errors are statistically tangled. The usual fix is to charge a "price of dependency" that grows with node degree or with how much neighborhoods overlap, and on real graphs with hub nodes that price makes the bound vacuous: the guaranteed error comes out above 100%. We propose to move the randomness somewhere else. In semi-supervised node classification, the graph and all node features are observed. What is actually random is which nodes got labeled. If we condition on the graph and treat the labeling procedure as the source of randomness, as a survey statistician treats a sampling design, then the dependency between neighboring nodes stops being an obstacle. The bound depends only on how labels were chosen, and when labels were chosen uniformly, it inherits exact finite-population concentration with no degree term at all.
This change of viewpoint also solves a second problem that has kept bounds from reaching deployed models. PAC-Bayesian bounds certify randomized predictors, meaning averages over noisy copies of the weights. Converting them into guarantees for the single deterministic network people actually use has required either a factor-of-two penalty or closed-form integrals that exist only for one-hidden-layer networks. On a single graph, the test nodes' inputs are all in hand. We can therefore measure exactly how often the deterministic network disagrees with its noisy copies on the test nodes, without any labels, and add that disagreement to the bound. The result is a certificate for arbitrary deep GNNs, including attention-based ones, that needs only forward passes.
Core Claim
For transductive node classification, meaning prediction on the unlabeled nodes of one observed graph, a non-vacuous risk certificate for a deep, deterministic GNN can be obtained by combining three ingredients. The first is a transductive PAC-Bayesian bound whose only randomness is the label-selection design. The second is a data-dependent prior trained on a random subset of the labeled nodes. The third is a label-free derandomization term computed on the unlabeled nodes. Graph dependency re-enters only when the labeling design itself is structured, for example when labels are gathered in neighborhood clusters or by snowball sampling. There the right penalty is a fractional-coloring charge on the design's clusters, not on the message-passing neighborhoods.
Concretely, let $V$ be the $N$ nodes, let $S \subset V$ be the $m$ labeled nodes, and let $U = V \setminus S$. For a classifier $h$, write $R_U(h)$ for its error rate on $U$. For a weight distribution $Q$, write $R_U(Q)$ for the error rate averaged over classifiers drawn from $Q$. For the deterministic network $h_w$ at the trained weights $w$, the zero-one triangle inequality gives
$$R_U(h_w) \le R_U(Q) + \mathbb{E}_{h \sim Q}\,\frac{1}{|U|}\sum_{v \in U} \mathbf{1}[h(v) \ne h_w(v)].$$
The second term needs no labels. We estimate it with $M$ weight draws, and a Hoeffding term of order $\sqrt{\ln(1/\delta)/M}$ accounts for the Monte Carlo error. Because this term can be driven down with compute, it does not carry the fixed factor of two. $R_U(Q)$ is bounded with the transductive PAC-Bayes theorem of PAC-Bayesian Theory for Transductive Learning. That paper derives bounds for a labeled sample drawn without replacement from a finite population, using a divergence that accounts for the labeled fraction $m/N$, and verifies them with AdaBoost on UCI tables. We reuse its theorem as the core tool and apply it to deep message-passing networks with learned priors, which it did not consider.
To see why the neighborhood dependency disappears, note that once we condition on the graph, the features and the true labels of every node are fixed numbers. Each node's loss under a fixed $h$ is then a fixed number too. Uniform selection of $S$ makes the labeled losses a simple random sample from that fixed list, however entangled the GNN's receptive fields are.
Relation to Prior Work
Two lines of work motivate the gap. Generalization in Graph Neural Networks: Improved PAC-Bayesian Bounds on Graph Diffusion replaces maximum degree with the spectral norm of the diffusion matrix and uses loss-landscape flatness to get bounds that track the gap. It treats each graph as an independent sample and explicitly leaves node-level tasks open. Subgroup Generalization and Fairness of Graph Neural Networks gives transductive PAC-Bayes bounds for node subgroups. Its bounds are proved only for SGC-style models, where propagation is decoupled from learning, and are numerically loose. Our derandomization term removes the architectural restriction, and the learned prior targets the looseness.
Two further papers constrain what we can hope to beat with dependency-aware tools. The stability analysis in Towards Understanding Generalization of Graph Neural Networks scales with maximum degree and parameter dimension. PAC-Bayesian Generalization Bounds for Graph Convolutional Networks on Inductive Node Classification is limited to one- and two-layer GCNs and to particular hub-leaf topologies. Both model the data as generated with dependence. We sidestep this by not modeling data generation at all, at the cost that our target is risk on this graph's unlabeled nodes rather than on a population of future graphs. That is a narrower question, and we state it as such.
The chromatic framework of Chromatic PAC-Bayes Bounds for Non-IID Data scales the PAC-Bayes penalty by the fractional chromatic number of a dependency graph, roughly the number of groups needed to split the sample into mutually independent pieces. We reuse it, but apply it to the labeling design rather than to message-passing overlaps. Under cluster sampling, the dependency graph links nodes labeled in the same cluster, which is small and known exactly. Computing the chromatic parameter is NP-hard in general, but here it is trivial.
Non-Vacuous Generalisation Bounds for Shallow Neural Networks supplies the data-dependent-prior recipe: train a prior on 60% of the data, then couple it to the full-data posterior. That paper reaches a 29.3% certified bound for a network with 4.3% MNIST test error, but only for one hidden layer with erf or GELU activations, with a factor-two derandomization slack, and with vacuous results on CIFAR-10. Our label-free disagreement term is the component that lets the recipe reach multi-layer GCN and GAT models. It exists only because transductive test inputs are observed.
Research Program
The prior and the bound use disjoint label sets. We split $S$ uniformly into a prior set $S_P$ and a bound set $S_B$. We train a prior network on $S_P$ labels while using the whole graph's features and edges. This is legitimate because we condition on those. We then train the posterior mean on all of $S$, and fit an isotropic or layerwise Gaussian posterior variance by optimizing the bound itself. Conditional on $S_P$, the set $S_B$ is a uniform draw from $V \setminus S_P$, so the transductive theorem bounds risk on $V \setminus S_P$. We recover risk on $U$ exactly by subtracting the known errors on $S_B$.
For attention models, perturbing weights also perturbs the attention coefficients. This breaks the static-diffusion arguments in the graph-diffusion bound. It is irrelevant to ours, since the disagreement term is measured by forward passes.
The second component extends the bound to structured designs. For a stratified design, such as the Planetoid split's 20 labels per class, we apply the bound per stratum and combine by union. For a cluster or snowball design, the labeled nodes' losses are dependent through the design. There we apply the chromatic decomposition with the design's cluster graph and derive the penalty. The analysis also has to say what is lost: under a design biased toward the neighborhood of a seed node, the certificate is necessarily for a reweighted population. Following the subgroup paper's finding that error grows with distance from the training set, we expect a naive uniform-design bound to be violated there.
The third component is empirical auditing of validity. We redraw the label mask many times from a known design and check that the certified bound holds at the promised rate $1-\delta$.
Baselines
The naive reference point is a classical i.i.d. McAllester PAC-Bayes bound with a data-free Gaussian prior, applied to the labeled nodes as if they were independent. It should be vacuous, and it anchors the scale.
The strongest competitor is the held-out test-set bound. We train on $S_P$ only and certify with an exact hypergeometric tail bound on $S_B$, which is valid under the uniform design. It is the strongest because it is tight, simple, and immune to the capacity issues that plague bounds for deep networks. It will receive the same splits, the same architecture, and the same hyperparameter budget. Beating it means one of two things: a lower certified error on $U$ at the same $\delta$, or an equal certificate for a model trained on all $m$ labels whose test accuracy is higher.
The dependency-aware theoretical baselines are three. We will evaluate the transductive stability bound of Tang and Liu numerically with its Lipschitz constants, on GCN, SGC and APPNP. We will evaluate Ma et al.'s subgroup PAC-Bayes bound on SGC. We will evaluate a generative chromatic bound in which the dependency graph links nodes with overlapping $K$-hop receptive fields, with its chromatic number upper-bounded by greedy coloring. All three are computed at the same $\delta$ on the same trained models.
Two ablations isolate our ingredients. The first swaps the label-free disagreement term for the factor-two majority-vote conversion. The second swaps the learned prior for a data-free prior. We also report posterior accuracy against deterministic accuracy.
No reported numerical risk certificate for transductive node classification was found on Lacuna for any baseline. The accuracy references available are GAT at 83.0% on Cora and 72.5% on CiteSeer, from Graph Attention Networks. We will report our own measured accuracies alongside every certificate.
Why not just…?
Why not just hold out labeled nodes and use a test-set bound? This is the real threat. Under a uniform design it is valid despite graph dependency, for exactly the reason our method is. The i.i.d. literature suggests that data-dependent-prior PAC-Bayes often ties with it. Our advantage can only come from label-scarce regimes, such as 140 labels on Cora, where holding out 40% of labels lowers both the model's accuracy and the holdout bound's resolution. We will sweep the label budget $m$ and report the crossover point. If the test-set bound wins everywhere, we will say so. The design-based contribution then survives as the validity argument that applies to both, together with the cluster-design extension, but the PAC-Bayes machinery does not.
Why not just use conformal prediction? Under a uniform design, split conformal is also exchangeable conditional on the graph. Graph-aware variants such as Uncertainty Quantification over Graph with Conformalized Graph Neural Networks, which reports up to 74% smaller sets, and the benchmark in Conformal Prediction: A Theoretical Note and Benchmarking Transductive Node Classification in Graphs give valid prediction sets. But conformal guarantees marginal set coverage, not the error rate of a point classifier. It also needs held-out calibration labels, the same cost the test-set bound pays. We see it as complementary and will not claim to replace it.
Why not just use the existing dependency-graph or stability bounds? They answer a harder, generative question, and they pay for it with degree-dependent constants. We will show numerically how far they are from non-vacuous on Cora and ogbn-arxiv. Their target, risk on new graphs, is not the target here.
Why not just regularize for flatness and report test accuracy? Flatness methods do help GNNs, as shown in The Split Matters: Flat Minima Methods for Improving the Performance of GNNs, which reports gains of over 2 points for GAT on CiteSeer, and Ju et al.'s noise-stability training reaches 79.31% ROC-AUC on ClinTox versus 61.06% for early stopping. But these methods produce no certificate. We will use sharpness-aware training as the posterior optimizer and ask whether it shrinks the disagreement term.
Proposed Experiments
We will use Cora, CiteSeer and PubMed, with both the Planetoid stratified split and random uniform masks at label budgets from 1% to 30%, and ogbn-arxiv for scale. Heterophilic graphs from the selective-blocking literature (Selective Blocking for Message-Passing Neural Networks on Heterophilic Graphs) test whether the certificate remains informative when message passing hurts. Architectures are SGC, APPNP, two- and four-layer GCN, and GAT. Metrics are the certified error on $U$ at $\delta = 0.05$, the true error on $U$, the ratio between the two, and the empirical violation rate over 200 mask redraws.
Three results would be decisive. First, the certificate should be non-vacuous, below 50% on Cora for a GAT whose true error is near 17%, while all dependency-aware baselines exceed 100%. Second, the sweep over label budgets should locate where PAC-Bayes beats the hypergeometric holdout bound, if anywhere. Third, the validity audit should come out right: under a cluster-sampling design, the uniform-design bound should be violated at well above rate $\delta$, and the chromatic design correction should restore the nominal rate. If the first check fails because the disagreement term is large, the ablation with sharpness-aware posteriors tells us whether flatness is the missing ingredient or whether deep GNNs are genuinely too unstable under weight noise to certify this way.
References
- PAC-Bayesian Theory for Transductive Learning
- Generalization in Graph Neural Networks: Improved PAC-Bayesian Bounds on Graph Diffusion
- Subgroup Generalization and Fairness of Graph Neural Networks
- Towards Understanding Generalization of Graph Neural Networks
- PAC-Bayesian Generalization Bounds for Graph Convolutional Networks on Inductive Node Classification
- Chromatic PAC-Bayes Bounds for Non-IID Data
- Non-Vacuous Generalisation Bounds for Shallow Neural Networks
- Graph Attention Networks
- Uncertainty Quantification over Graph with Conformalized Graph Neural Networks
- Conformal Prediction: A Theoretical Note and Benchmarking Transductive Node Classification in Graphs
- The Split Matters: Flat Minima Methods for Improving the Performance of GNNs
- Selective Blocking for Message-Passing Neural Networks on Heterophilic Graphs