Transductive Generalization Bounds When Labels Arrive in Neighborhoods

Every transductive generalization bound for graph neural networks rests on one quiet assumption: the labeled nodes are a uniformly random subset of the graph. "Transductive" means the whole graph, including the nodes we must predict, is visible during training, and only some labels are hidden. Real labels are rarely collected uniformly. An annotator labels a paper and the papers it cites. A crawler reaches a seed account and labels its followers. Labeled sets built this way cover whole neighborhoods at once. They over-represent well-connected nodes, and they leave a test set tilted toward the periphery of the graph. Under such a labeling process, the existing bounds are not just loose. Their proofs do not apply at all, and training error becomes a biased estimate of test error.

This note proposes a generalization bound that stays valid when labels come from neighborhood-based collection. The key observation is simple. If labels are collected by picking random seed nodes and labeling everything within $r$ hops of each seed, then whether a node ends up labeled depends only on the seeds near it. Two nodes' labeled/unlabeled status is therefore coupled only when their neighborhoods overlap. That is exactly the kind of structured dependence that graph-coloring ("chromatic") bounds were built for. We combine three ingredients. From transductive Rademacher complexity we take the capacity measure over the fixed set of nodes. From finite-population sampling we take inclusion-probability weighting, which removes the bias. From chromatic bounds we take the decoupling of the dependent label indicators. The result is a certificate on unlabeled-node error for GNNs trained on neighborhood-collected labels, plus an empirical test of whether current uniform-split bounds actually fail under such collection.

Where the gap really is

The research file frames the open problem at this intersection as a "two-layer dependency": sampling without replacement plus graph dependence among the nodes. That framing needs correcting before anything is built. In transductive learning the graph, the features and the hidden labels are all fixed. For a fixed hypothesis, the loss at each node is a fixed number. The only randomness is which nodes get labeled. Edges between nodes therefore create no statistical dependence, as long as the labeled set is a uniform random subset.

The uniform-split tools already cover that case completely. Transductive Rademacher Complexity and Its Applications bounds learners over a fixed population under uniform partitions. Learning Theory Can (Sometimes) Explain Generalisation in Graph Neural Networks applies this to GNNs, with the graph entering only through the capacity term $\|SX\|_{2\to\infty}$. Several papers sharpen the concentration step for uniform without-replacement sampling. Towards Understanding Generalization of Graph Neural Networks adds algorithmic stability under stochastic gradient descent. A New Concentration Inequality for Sampling Without Replacement and Its Application for Transductive Learning develops local complexities. Improved Risk Bounds with Unbounded Losses for Transductive Learning handles unbounded losses. All of these assume the split is exchangeable.

Graph dependence genuinely matters only when the labeling process itself follows the graph. None of the surveyed papers treats that case. The chromatic line of work, Generalization error bounds for classifiers trained with interdependent data and Chromatic PAC-Bayes Bounds for Non-IID Data, handles dependence among random variables generated from independent base variables. It has never been applied to the selection indicators of a transductive split. Understanding Generalization in Node and Link Prediction builds dependency graphs from overlapping computation trees. It uses robustness and stability arguments, and it does not model a labeling design. Its PATTERN result motivates our concern: a gap of 0.0625 when samples are spread across graphs versus 1.552 when they are concentrated on few graphs shows that how samples are collected can change the gap by more than an order of magnitude.

Core Claim

Neighborhood-based labeling turns the transductive split into a set of dependent inclusion indicators with a known dependency graph. Each node's chance of being labeled is computable from the graph. Weighting training losses by these chances removes the bias toward hubs. Fractionally coloring the neighborhood-overlap graph then decouples the indicators, so that a transductive Rademacher bound holds within each color class. The resulting certificate degrades gracefully with the overlap structure rather than collapsing.

Concretely, suppose each node becomes a seed independently with probability $p$, and node $v$ is labeled ($T_v=1$) if any seed lies in its reverse $r$-hop neighborhood $R(v)$. Node $v$'s inclusion probability is then $\pi_v = 1-(1-p)^{|R(v)|}$, which is known from the graph alone. For a hypothesis $h$ with loss $\ell_v(h)$ at node $v$, the weighted training loss $\sum_v T_v \frac{1-\pi_v}{\pi_v}\ell_v(h)$ has the same expectation as the total test loss $\sum_v (1-T_v)\ell_v(h)$. Their difference is

$$G(h) \;=\; \sum_{v=1}^{n} \ell_v(h)\,\frac{T_v-\pi_v}{\pi_v},$$

which has mean zero and is linear in the centered indicators. $T_v$ and $T_w$ are dependent only if $R(v)\cap R(w)\neq\emptyset$. Given any fractional cover of this overlap graph by independent sets $C_k$ with weights $\alpha_k$, the argument of Usunier et al. carries over: within each $C_k$ the indicators are independent functions of disjoint seed sets. We therefore expect $\sup_h G(h)/n$ to be bounded by a weighted sum of transductive Rademacher complexities, one per color class, plus a deviation term of order $B\sqrt{\chi_f \log(1/\delta)/n}$. Here $\chi_f=\sum_k\alpha_k$ is the fractional chromatic number (the total weight of the cover), and $B$ bounds $\ell_v/\pi_v$. The square-root form comes from the McDiarmid-style step applied class by class, as in the chromatic PAC-Bayes analysis. Computing $\chi_f$ exactly is NP-hard, but that does not block the method. Any feasible cover gives a valid bound, so a greedy cover suffices and only costs tightness.

Research Program

The theory has three parts. The first is the Bernoulli-seeding bound above. It pairs the fractional Rademacher machinery with per-class transductive Rademacher complexity of the GNN class. For per-class capacity we reuse Esser et al.'s $\|SX\|_{2\to\infty}$ analysis, restricted to the rows in $C_k$.

The second part handles fixed seed budgets, which are the realistic case: an annotator is given exactly $k$ seeds. Two routes exist. The cheap route is conditioning on the seed count. It inflates the failure probability by roughly $\sqrt{k}$, which costs only an additive $\tfrac12\log k$ inside the logarithm. The direct route uses the fact that fixed-size seed indicators are negatively associated, and that coverage indicators are increasing functions of disjoint seed sets within a color class. This could recover a finite-population correction, the $u/(n-1)$ variance shrinkage behind Serfling-type bounds in Error Bounds for Transductive Learning via Compression and Clustering. That shrinkage matters only when a large fraction of the graph is seeded. Proving it under a supremum over hypotheses is the main open technical question.

The third part extends the design class. Random-walk collection has computable inclusion probabilities, so it fits the framework. We also cover the mixture of uniform labels and neighborhood labels that describes real annotation.

Empirically, we build a small library that does three things for any labeling design: it computes $\pi_v$ (exactly or by Monte Carlo simulation of the design), it builds a greedy fractional cover of the overlap graph, and it evaluates the certificate for trained GNNs.

Baselines

The naive reference point is the unweighted training loss, used as if it estimated test loss. This is what practitioners do implicitly. It will be run on the identical splits and trained models. Beating it means a smaller absolute error between estimated and realized test loss, averaged over many resampled splits.

The strongest existing competitor is the uniform-split transductive Rademacher bound of Learning Theory Can (Sometimes) Explain Generalisation in Graph Neural Networks. The companion is the stability-plus-Rademacher bound of Towards Understanding Generalization of Graph Neural Networks, applied naively to neighborhood-collected splits. These are the only bounds reported to be non-vacuous for GNNs on Cora-type graphs, so they are the natural comparison. We will compute them with the authors' capacity terms on the same trained weights, at the same confidence level $\delta$. The file contains no reported numerical bound value or gap on Cora, Citeseer, Pubmed or ogbn-arxiv for either paper. Those results appear only graphically, so we find no reported result on Lacuna for their numerical values, and we will recompute them. Beating them has two parts. First, our certificate must be violated at a rate at most $\delta$ over resampled neighborhood splits while theirs is violated more often. Second, under uniform splits, where theirs is valid, ours must be no more than modestly looser.

Two ablations isolate the key ingredients. The first keeps the inclusion-probability weighting but treats the indicators as independent, using an ordinary Hoeffding or Rademacher step. It should be valid on average but under-cover, which would show that coloring is doing real work. The second keeps the coloring but drops the weighting. It should be tight but biased on graphs with heavy-tailed degree. We also include independent-set subsampling, which keeps a single color class and applies a standard bound to it.

Why not just…?

Why not just use the existing uniform-split bounds, since they are already non-vacuous? Their proofs require an exchangeable split. Under neighborhood collection, the test set is systematically more peripheral than the training set. The bound's centering is then wrong, not merely its width. The decisive experiment below measures exactly how often these bounds are violated. If violations stay below $\delta$ on real graphs, the practical case for this project collapses to theoretical hygiene, and we will say so.

Why not treat each seed's neighborhood as one unit and apply standard transductive bounds at the unit level? This works when neighborhoods are disjoint, as in cluster sampling. Neighborhoods on citation graphs overlap heavily, however. The test set is the complement of a union of neighborhoods, not a sample of units, so the unit-level reduction does not describe the quantity we must bound. We will still include the unit-level bound on synthetic stochastic block model graphs with well-separated blocks. There it should match ours, which serves as a sanity check.

Why not keep one independent set and discard the rest? Chromatic PAC-Bayes Bounds for Non-IID Data proves that using the full dependent sample with a fractional cover is tighter than any single independent sub-sample. We expect the same here and will report both.

Why not simply fix the seed count by conditioning, instead of proving a negative-association bound? This alternative is a real threat. The $\sqrt{k}$ inflation costs only a logarithmic term. We therefore adopt conditioning as the default construction and treat the negative-association version as a research question. It earns its place only if it produces a visibly tighter certificate when a large fraction of nodes is seeded. We test exactly that by sweeping $p$ up to large coverage fractions.

Proposed Experiments

We use Cora, Citeseer, Pubmed and ogbn-arxiv, the graphs used by Esser et al. and Tang and Liu, with GCN, SGC, APPNP and GCNII. We also use the synthetic stochastic block model with Gaussian mixture features from Esser et al., where degree spread and neighborhood overlap can be dialed. Labeling designs are uniform (the control), 1-hop and 2-hop seeded neighborhoods, and random-walk collection. Seed probabilities are matched so that the expected labeled fraction is the same across designs.

For each configuration we draw many splits. On each split we record five quantities: the realized test-minus-train loss gap, the naive estimate, the weighted estimate, every bound's value, and whether each bound was violated.

The first decisive check is whether uniform-split bounds are violated at rates above $\delta$ under neighborhood designs, especially on degree-skewed graphs. The second is whether our certificate is non-vacuous for 1-hop designs on Cora and Citeseer, and at what hop radius $\chi_f$ makes it vacuous. We expect this to happen quickly on ogbn-arxiv because of hubs, and reporting that limit is part of the result. The third is whether the weighted estimate removes the degree-driven bias, measured as a regression of per-split estimation error on the mean degree of the test set. A positive outcome on all three would establish that the labeling design, not the architecture alone, must enter GNN generalization theory.