A new framework for epistemic uncertainty in node classification: graph EDL methods fail information-growth consistency, while graph bootstrap ensembles recover uncertainty contraction

It proposes the first statistical framework for epistemic uncertainty in node classification, comprising an information-growth experimental protocol and a definition of consistent epistemic predictors. Prior graph EDL methods construct epistemic uncertainty from graph-specific principles such as feature support, structural support, and neighborhood conflict on a fixed graph, and evaluate it on downstream tasks such as OOD detection, which cannot test reducibility as information about the data-generating process increases; this framework extends the i.i.d. characterization of reducibility to node classification. The framework has three components: the observed graph (induced subgraph) as the sampling unit, projective graph data-generating processes to ensure nested graphs arise from the same process, and learning tasks that extend as graphs grow; the consistency criterion requires uncertainty to decrease monotonically and to converge asymptotically to a Dirac measure at the Bayes-optimal predictor.

It unifies graph EDL objectives and characterizes their population optima, showing that their epistemic uncertainty is externally regulated by hyperparameters rather than explicitly estimating data uncertainty, thereby precluding consistency. It expresses the training objectives of S-BGCN-K, GPN, GPN-LOP, and CUQ-GNN through a unified EDL loss with a tempering parameter and derives the population optimum in closed form, enabling comparison within a common framework. Theorem 4.3 gives the population optimum of the unified loss; for fixed finite parameters, GPN, GPN-LOP, and CUQ-GNN retain non-vanishing epistemic uncertainty at the population optimum; S-BGCN-K's evidential distribution converges to a Dirac under the dense graphon setting, but its location depends on the GKDE construction and need not be Bayes-optimal, and with MC dropout epistemic uncertainty need not vanish; controlled information-growth experiments corroborate insufficient epistemic concentration and persistent parameterization dependence.

It proposes graph bootstrap ensembles (GB-Ens), which capture both data and procedural uncertainty through graph resampling and randomized training and exhibit epistemic uncertainty contraction under the same protocol. It extends to graphs the i.i.d. idea that bootstrap ensembles capture both data and procedural uncertainty and, under suitable conditions, converge asymptotically to their Bayesian counterpart, using an edge-only local non-parametric bootstrap that retains node identities, features, and labels. On two projective graphon DGPs, an exponential-decay graphon and an SBM, GB-Ens epistemic uncertainty decreases monotonically with graph size (by the reported proportions for GCN, APPNP, and GAT on the exponential-decay graphon), with both randomized-seed and bootstrap components decreasing as information grows; standard graph deep ensembles (G-Ens) show no consistent epistemic uncertainty contraction; normalized Wasserstein-1 distances to true-DGP resampling remain small and stable for APPNP and GCN but increase with graph size for GAT.

The framework applies to settings where a projective graph data-generating process can be defined, that is, where nested graph observations are coherent observations of the same underlying process; experiments use two synthetic projective graphon DGPs, an exponential-decay graphon and an SBM, covering continuous and discrete structure regimes for a balanced seven-class node-classification problem, with six logarithmically spaced graph sizes. For researchers seeking to evaluate or design graph epistemic uncertainty predictors, the protocol offers an operational standard for testing reducibility under information growth; GB-Ens is instantiated with an edge-only bootstrap that retains node identities, features, and labels, and can control peak memory through parallel training and sequential inference.

The theoretical consistency of bootstrap-based graph epistemic predictors remains to be established; information-growth behavior cannot be evaluated on standard real-world benchmarks that lack the sampling process required to generate increasingly informative observations from the same DGP, so conclusions currently rest mainly on synthetic graphons. Approximation quality varies across predictors: GAT's Wasserstein-1 distance to true-DGP resampling increases with graph size, and its epistemic uncertainty reduction is weaker and partly non-monotonic, suggesting contraction relies on regularity of the underlying learning procedure. In addition, the local bootstrap does not preserve all topological properties of the observed graphs, limiting its fidelity as an approximation of graph observation variability. Some table values are absent from the loaded text, so restatements of specific numbers follow the proportions and distance ranges stated explicitly in the main text.