Certified Node Classification with Chromatic PAC-Bayes Bounds

A graph neural network that classifies nodes, for example labeling papers in a citation graph, computes each prediction from the node's neighborhood. Two training nodes whose neighborhoods overlap therefore do not give independent evidence about how well the model generalizes. Standard generalization certificates ignore this overlap. Those certificates are high-probability upper bounds on test error that a model can be trained to minimize directly. They count every labeled node as an independent sample, so they are overconfident exactly where graph models are used. This proposal builds certificates for node classification that count evidence correctly and can be trained end to end. The key observation is that the overlap structure is not a fixed property of the data. It is set by the model's depth. A network that passes messages through $L$ layers sees each node's $L$-hop neighborhood, so two training nodes interact exactly when they lie within $2L$ hops of each other. Deeper models fit better but have less independent evidence behind them, and a correct certificate should be able to see that trade-off.

The tool that makes this possible is the chromatic PAC-Bayes bound. PAC-Bayes bounds certify a randomized predictor, meaning a distribution over network weights, by charging its divergence from a fixed reference distribution. The chromatic version splits a dependent sample into groups that are internally independent, and it replaces the sample size $n$ with an effective sample size $n/\chi_f$. Here $\chi_f$ is the fractional chromatic number of the graph whose edges record which samples depend on each other. We turn this bound into a training objective for message-passing networks. We make it computable on real graphs, and we let it choose the model's depth.

Core Claim

For a fixed graph, assume node features and labels are drawn independently given the structure. Under that assumption, a depth-$L$ message-passing network's losses at training nodes $i$ and $j$ are independent whenever their $L$-hop neighborhoods are disjoint. The loss dependency graph is then the $2L$-th power of the graph, restricted to training nodes. Any valid fractional cover of this graph gives a valid bound. A fractional cover is a weighting $w$ of independent sets such that every node is covered with total weight at least one. Its total weight $\chi_w$ is at least $\chi_f$, so the NP-hardness of computing $\chi_f$ exactly is not an obstacle to soundness. It only costs tightness.

The objective we minimize takes the chromatic kl form. This is the form that Fast-Rate PAC-Bayesian Generalization Bounds for Meta-Learning established for dependent tasks and that Chromatic PAC-Bayes Bounds for Non-IID Data established in McAllester form:

$$\mathrm{kl}\big(\hat R_S(Q)\,\|\,R(Q)\big) \le \frac{\chi_w(G_L)}{n}\Big[\mathrm{KL}(Q\|P) + \ln\frac{2 L_{\max}\sqrt{n/\chi_w(G_L)}}{\delta}\Big].$$

The symbols are as follows. $Q$ and $P$ are the learned and reference Gaussian distributions over weights. $\hat R_S(Q)$ is the average training 0-1 loss over all $n$ labeled nodes. $R(Q)$ is the average over those nodes of their expected loss under fresh feature and label draws. $G_L$ is the depth-$L$ dependency graph. The factor $L_{\max}$ comes from a union bound that pays for selecting $L$ among $L_{\max}$ candidate depths.

The claim has three parts. First, this objective produces the first non-vacuous, provably valid certificates for node classification. Second, the bound's preferred depth differs from the depth that an IID bound would prefer. Third, it tracks true risk better than training on an independent subset.

Research Program

The first piece is theory. The chromatic results of Ralaivola et al. assume identical marginal distributions across samples, as noted in Chromatic PAC-Bayes Bounds for Non-IID Data: Applications to Ranking and Stationary β-Mixing Processes. Nodes with different neighborhoods violate that assumption. We will restate the result so that it controls the average of node-wise risks rather than a shared marginal risk. We expect this change to go through with the same cover-and-Jensen argument. We will also check carefully that the bound holds for any fixed feasible cover and not only an optimal one. The cover must depend only on the graph structure, never on features or labels, so that choosing it does not invalidate the bound.

The second piece is computation. On powers of sparse graphs we compute covers by column generation on the fractional coloring linear program, pricing new independent sets with greedy heuristics. We compare the result against greedy integer coloring, which bounds $\chi$ and is often loose because of a few high-degree nodes. We also compare against the degree bound $\Delta+1$.

The third piece is training. The objective above plugs into the PAC-Bayes-SGD recipe of Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data. That recipe optimizes Gaussian means and variances, uses a differentiable surrogate loss, and applies kl inversion at certification time. We run it separately for each depth $L$ and certify the minimizing depth.

This work also fills gaps left by two papers. Understanding Generalization in Node and Link Prediction uses chromatic numbers for message-passing networks, but through robustness bounds that are neither PAC-Bayesian nor trained on. In-distribution and Out-of-distribution Generalization for Graph Neural Networks gives PAC-Bayes bounds for graph neural networks, but only at the graph level, computed after training and without modeling dependency. We use the kl form rather than Catoni's because Guan and Lu report that the Catoni bound could not be extended to dependent samples.

Baselines

The naive reference is PAC-Bayes-SGD with the nominal sample size $n$. This is the method of Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data applied unchanged to node classification. Its certificate will look tighter than ours, but it is not a valid bound. On synthetic graphs, where true risk can be measured by resampling, we will report how often it falls below true risk. Beating it means our certificates are never violated at the stated confidence while theirs are.

The strongest valid competitor is independent-subset training. It takes a maximum independent set of $G_L$, which is IID by construction, and runs the same PAC-Bayes-SGD with the same architecture, number of optimizer steps, and hyperparameter grid. Its certificate is valid, and the procedure is the natural choice for a skeptical reviewer. Beating it means a lower certified error and a lower test error at every depth, given the same labeled nodes. Ralaivola et al. predict that the full weighted sample is better, but this has never been tested with trained deep models.

No certificate for node classification is reported in the file. For the image setting, the reference PAC-Bayes-SGD result is a bound of 0.201 for a network of about 1.2 million parameters on MNIST, with test error around 3%, reported in the Dziugaite and Roy paper.

Two ablations isolate the ingredients. The first swaps the column-generated fractional cover for greedy integer coloring, which shows how much the fractional relaxation buys. The second fixes $L$ at the value that maximizes validation accuracy instead of selecting it by the bound, which shows whether the dependency-aware depth trade-off matters.

Why not just…?

Why not just divide $n$ by a crude dependency factor inside the existing objective? That is essentially the objective here. We do not claim that changing the objective is the contribution. The contributions are knowing which factor is valid for message passing, namely the fractional cover of the $2L$-power graph; computing a tight enough cover on real graphs; and showing that the factor changes decisions such as depth. The cover ablation measures how much a crude factor like $\Delta+1$ loses. If greedy coloring matches column generation on our graphs, we will report that the simple version suffices.

Why not just train and certify on an independent subset? This is the most serious threat. It is valid, simple, and tighter than ours whenever $\chi_w$ is close to $n$ divided by the independence number. Ralaivola et al. prove that using the full sample dominates in the bound. Understanding Generalization in Node and Link Prediction found that the generalization gap on PATTERN grows from 0.0625 to 1.552 when training concentrates on fewer graphs, which suggests that sample coverage matters. The head-to-head baseline comparison settles the question empirically, and we will report depths where the subset wins if they exist.

Why not just hold out labeled nodes and use a test-set bound? Held-out nodes are also dependent on each other, so a valid test-set bound needs the same chromatic correction. It also spends labels, which in semi-supervised benchmarks like Cora number only in the low hundreds. We will run a chromatic Hoeffding test-set bound on a held-out split as an additional comparison. If it wins at high label counts, we will say so and position our method for the label-scarce regime.

Proposed Experiments

Contextual stochastic block models. These are the synthetic graph families used by Sales and Liao, in which features are Gaussian given community labels. Fixing the graph and resampling features and labels gives exact true risk. Here we check validity: the violation rate of every certificate at $\delta=0.05$ across 100 redraws. We also check calibration, meaning the gap between certified and true risk, as depth and edge density vary.

PATTERN from Benchmarking Graph Neural Networks. PATTERN consists of many graphs, so $G_L$ is a disjoint union of per-graph dependency graphs, and $\chi_w$ is set by the worst single graph rather than growing with the number of graphs. We predict that certificates tighten sharply when labels are spread across more graphs, a quantitative counterpart of Vasileiou et al.'s sampling-diversity finding.

Cora and Citeseer, as distributed with the same benchmark. Here the independence assumption is a modeling choice, and we state it as such. The question is whether the certificate is non-vacuous at all under standard label budgets, and how its selected depth compares with the validation-selected depth.

Decisive checks. The project succeeds if three things hold. First, our certificates are never violated on synthetic data while the nominal-$n$ certificates are. Second, they are non-vacuous, meaning below 0.5 for binary pattern tasks, on PATTERN. Third, they beat independent-subset training in both certificate and test error. The bound-selected depth should also be shallower than the IID-selected depth on dense graphs. If it never differs, that finding is itself informative: dependency would then matter for validity but not for model selection.