When a graph neural network labels the nodes of one citation graph, the usual way to prove it will generalize is to treat the nodes as random draws. The nodes are clearly dependent, since neighbors share features and labels. The bound is then charged for that dependence by dividing the sample size by the number of colors needed to separate dependent nodes, which on dense graphs makes the bound useless. This proposal argues that, in the most common graph setting, this charge is aimed at the wrong thing. In transductive node classification the graph, its features, and every node's true label are fixed. The only randomness is which nodes the experimenter happens to label. Dependence among the data is not a source of uncertainty at all. The only dependence that matters is the dependence created by how the labeled set is sampled.
We combine three tools to get certificates that use this observation. The first is sample compression: a predictor rebuilt from a small labeled subset can be tested "for free" on the labeled nodes it never saw. The second is exact concentration for sampling without replacement from a finite population. The third is a chromatic (graph-coloring) penalty, applied only where the sampling design forces it, for example when losses are computed on pairs of sampled nodes, as in link prediction. The result is a self-certified graph learner whose guarantee depends on the compression set size and the split ratio. Under uniform node splits it does not depend on the chromatic number of the graph at all.
Core Claim
Fix a graph with $N$ nodes and their unknown labels. A uniformly random subset of $m$ nodes is labeled, and the remaining $u = N - m$ are the test nodes. Let a reconstruction function map a $k$-node compression set (with labels), together with the fully observed unlabeled graph, to a predictor. Condition on the compression set sitting at a fixed set of positions within a random permutation of the nodes. The other $m-k$ labeled nodes are then a uniform without-replacement sample from the $N-k$ non-compression nodes. The predictor's errors on those $N-k$ nodes are a fixed, unknown number $E$. The number of errors observed on the $m-k$ labeled non-compression nodes is therefore exactly hypergeometric. Inverting its tail gives
$$ \Pr\Big[\, \hat e_{m-k} \le t \;\Big|\; E \Big] = \sum_{j \le t} \frac{\binom{E}{j}\binom{N-k-E}{m-k-j}}{\binom{N-k}{m-k}}, $$
where $\hat e_{m-k}$ is the observed error count and $t$ a threshold. We then take a union bound over the $\binom{m}{k}$ position subsets and over $k$, with weights as in standard compression bounds. This yields a high-probability upper bound on the number of test-node errors, $E - \hat e_{m-k}$, with no chromatic factor and no infinite-distribution assumption.
The chromatic factor comes back only when the unit that is sampled differs from the unit that is scored. In link prediction under a node split, the test loss averages over pairs of test nodes. Two such pairs are dependent when they share a node. The right penalty is then the fractional chromatic number of that pair-overlap graph, which is about $u/2$ pairs' worth of independent information. Ralaivola et al. found the same factor for ranking.
The new claim is this division of labor between the three tools, together with a valid certificate built on it. The obvious combination, which plugs $\chi_f(G)$ into a sample compression bound, gives a bound that is valid but needlessly loose in the node case. We will show this empirically.
Relation to Prior Work
Three lines of work supply the pieces. Chromatic bounds motivate the problem and also show the cost we want to avoid. Usunier et al. inflate Rademacher complexity by $\chi(G)$, and Ralaivola et al. show that $\chi_f(G)$ is the right penalty inside PAC-Bayes, with effective sample size $n/\chi_f(G)$. Both are inductive. Vasileiou, Stoll and Morris bring chromatic dependency graphs to message-passing networks, including a transductive setting, but there they rely on stability rather than without-replacement concentration, and they give no compression scheme. We keep their chromatic machinery only for designs that sample tuples, and replace stability with an exact hypergeometric argument.
Finite-population theory supplies the concentration step. Derbeko, El-Yaniv and Meir already joined transduction with compression: support vectors serve as the compression set and Serfling's inequality does the concentration. Their bounds are restricted to 0-1 loss, assume an unstructured pool, and diverge as $u$ grows, as Bégin et al. showed. Bégin et al. fixed the divergence with a ratio-aware divergence, but for posteriors over models rather than compression sets. Exact hypergeometric inversion avoids both Serfling's slack and the ratio restrictions ($m \gg u^2$ or $u \gg m^2$) that the sharp inequality of Yang requires. Those restrictions fail for ordinary 80/20 or few-label splits.
Compression supplies the learner. Pick-to-Learn, as analyzed by Paccagnan et al., repeatedly adds the highest-loss example to the compression set and retrains. Marks and Paccagnan add early stopping (P2L-ES) and report tighter certificates than a train-test split. Bazinet, Zantedeschi and Germain extend compression bounds to real-valued losses and large networks. All three assume IID samples. Dagan et al. handle dependent data under Dobrushin's high-temperature condition. That condition constrains our design: it is a statement about a random dependent distribution and fails under strong dependence. Our argument sidesteps it entirely by conditioning on the fixed graph.
Research Program
The theoretical work has three parts. The first is the node-level theorem above. It covers bounded losses through the hypergeometric inversion. For real-valued losses we use a without-replacement version of the comparator-function argument of Bazinet et al., with an early-stopping penalty for residual points following Marks and Paccagnan. The second is a tuple-level theorem for designs where the scored units are pairs or groups of sampled units. Examples are link prediction under node splits and multi-graph datasets where whole graphs are sampled and losses are averaged over their nodes. Here we write the pair-level test loss as an average over fractional covers of the overlap graph, as Ralaivola et al. do. Each cover element is then concentrated with the generalized McDiarmid inequality for symmetric functions of a without-replacement sample, due to Cortes et al.. The open technical question is whether the without-replacement gain and the chromatic penalty multiply cleanly. We will prove what holds and report where the analysis is loose. The third part is a statement of when conditioning is not legitimate. If the labeled set is chosen by the graph's structure, for instance by snowball or ego-net sampling, the sampling design itself creates dependence, and the chromatic penalty is needed even for node losses.
On the algorithmic side we build Graph P2L. We start from an empty labeled compression set. A graph convolutional network or label-propagation model is trained on the compression set while using the full unlabeled graph. The highest-loss labeled node outside the set is added at each step, with early stopping. The certificate is computed from the errors on the labeled nodes outside the compression set. Because the reconstruction may use the unlabeled graph freely, the compression set can stay small. For label propagation and sparse Gaussian processes, the Schur-complement updates of Marks and Paccagnan keep the cost manageable.
Baselines
The naive reference point is the empirical training error, reported alongside the realized test error over many random splits. It shows how much any certificate costs.
The strongest practical competitor is a hold-out certificate. A model is trained on a fraction of the labeled nodes. An exact hypergeometric bound is then computed on the held-out labeled nodes, which is valid for exactly the same reason as our theorem. This baseline is strong because it is simple and tight. Marks and Paccagnan report that P2L-ES beats the train-test approach on UCI Energy, Concrete and MNIST, but the file gives no scalar values, so no reported result was found on Lacuna for graph data. We run it with the same architecture, the same splits, and holdout fractions tuned over the same grid we use for our early-stopping budget. To beat it, our certificate must be lower on average at an equal number of labels, with test accuracy within one point.
The strongest existing compression method is the IID bound of Bazinet et al. applied to Graph P2L as if nodes were independent. Its reported certificates are about 5% for a CNN on MNIST with 0.25% test error, and 13.91% for DistilBERT on Amazon Polarity. No reported result was found on Lacuna for any certificate on Cora, Citeseer, Pubmed or ogbn-arxiv.
We also run the obvious combination, which divides that bound's effective sample size by an upper bound on $\chi_f$ of the node dependency graph (maximum degree plus one, or a greedy fractional cover). The ablation that isolates our key ingredient swaps the exact hypergeometric inversion for Serfling's inequality, as in Derbeko et al.
For the accuracy cost of compression we compare against the standard full-data network. The SubMix paper reports a baseline accuracy of 77.98% on ogbn-arxiv, which marks the uncertified accuracy level we should not fall far below.
Why not just…?
Why not just hold out labeled nodes and certify on them? This is the real threat. The hold-out certificate is valid in the transductive setting for the same conditioning reason as ours, and it is very hard to beat when labels are plentiful. Its weakness is that it spends labels on certification that could have trained the model. That cost should matter most in the few-label regime typical of Cora-style splits. The experiments sweep the label budget, and if hold-out certificates match ours at every budget, we will report that compression adds nothing here.
Why not just multiply the IID compression bound by the chromatic number? It is valid but answers the wrong question. It treats fixed labels as random and then pays for dependence that has no randomness behind it. On a citation graph, the maximum degree is in the hundreds, so the corrected bound should be vacuous. The direct comparison on Cora and Pubmed shows the size of this gap.
Why not just use the IID compression bound and ignore dependence? That bound certifies risk on an imaginary infinite distribution, not on the specific unlabeled nodes. Under node-level sampling it may happen to be numerically close to ours, but under tuple or graph-level designs it can undercover. The coverage check on PATTERN and on link splits tests this directly.
Why not use transductive PAC-Bayes on the weights instead? The bounds of Bégin et al. are stable and tight on UCI data, but they need a posterior over models and a prior chosen in advance. For message-passing networks, that means stochastic training and a divergence term that grows with model size. Compression bounds do not depend on parameter count. We include Bégin et al.'s bound with AdaBoost stumps on the UCI datasets they used, as a check that our hypergeometric inversion is at least as tight in their own setting.
Proposed Experiments
For node classification we use Cora, Citeseer and Pubmed under random splits at several label fractions, plus ogbn-arxiv for scale. We report the certified test error rate, the realized test error, and coverage: the fraction of 200 random splits on which the certificate holds, which must be at least $1-\delta$. The pair-level theorem is tested by link prediction under node splits on the same graphs. Group-level sampling is tested on PATTERN, where Vasileiou et al. report generalization gaps of 0.0625 under uniform sampling across graphs and 1.552 when sampling concentrates on fewer graphs. Our tuple-level certificate should widen in the concentrated design and stay valid there, while the node-level certificate, if misapplied, should undercover.
A decisive negative control replaces uniform node splits with ego-net or snowball splits. The node-level theorem's assumptions then fail, so its coverage should drop below $1-\delta$, while the chromatic version recovers coverage. If coverage holds anyway, the theory is more conservative than it needs to be, and we will say so. The primary decisive check is threefold. Under uniform splits, the node certificate must hold at the nominal rate. It must be markedly tighter than the chromatic-corrected compression bound. And in the few-label regime it must be at least as tight as the tuned hold-out certificate. If the last condition fails, the contribution narrows to the theory explaining why the chromatic penalty is unnecessary, rather than a better certificate.
References
- Generalization error bounds for classifiers trained with interdependent data
- Chromatic PAC-Bayes Bounds for Non-IID Data: Applications to Ranking and Stationary β-Mixing Processes
- Understanding Generalization in Node and Link Prediction
- Error Bounds for Transductive Learning via Compression and Clustering
- PAC-Bayesian Theory for Transductive Learning
- A New Concentration Inequality for Sampling Without Replacement and Its Application for Transductive Learning
- Pick-to-Learn for Systems and Control: Data-driven Synthesis with State-of-the-art Safety Guarantees
- Pick-to-Learn and Self-Certified Gaussian Process Approximations
- Sample Compression Unleashed: New Generalization Bounds for Real Valued Losses
- Learning from Weakly Dependent Data under Dobrushin's Condition
- Stability of transductive regression algorithms