PaperlayerView exact revision on arXiv

Source-linked AI summary

Rethinking Epistemic Uncertainty in Node Classification through Information Growth

Emma Meneghini, Francesco Ferrini, Bruno Lepri, Andrea Passerini, Veronica Lachi

arXiv:2610.03418v1cs.LGcs.AI

TL;DR

Node classification lacks a direct test of whether epistemic uncertainty decreases as information about the same DGP grows. The paper defines an information-growth framework, analyzes graph EDL and proposes graph bootstrap ensembles; experiments support the latter as candidate consistent predictors.

  • Problem

    Graph EDL uncertainty is commonly grounded in fixed-graph properties and evaluated through OOD detection, which does not test its reducibility as information about the same DGP grows.

    Source: §1 · pp. 1–2

  • Method

    The paper defines an information-growth protocol using projective graph DGPs and a consistency criterion, then evaluates graph EDL and graph bootstrap ensembles under that protocol.

    Source: §1 · p. 2, §3.1 · pp. 4–5

  • Results

    Under information growth, graph bootstrap ensembles show decreasing epistemic uncertainty beyond standard deep ensembles, while graph EDL methods exhibit insufficient concentration and parameterization dependence.

    Source: §6 · p. 8, §7 · p. 9

  • Takeaways & Limitations

    The experiments support graph bootstrap ensembles as candidate consistent epistemic predictors because they capture data and procedural uncertainty.

    Source: §7 · p. 9

    Theoretical consistency of bootstrap-based graph predictors remains unestablished, and standard real-world benchmarks lack the sampling process needed to evaluate information growth.

    Source: §7 · p. 9

Abstract

from arXiv · show

Epistemic uncertainty should decrease as additional information about the data-generating process (DGP) becomes available to the predictor. Yet, existing graph evidential deep learning (EDL) methods for node classification typically construct epistemic uncertainty from graph-specific properties and evaluate it on downstream tasks such as out-of-distribution detection, which do not test its reducibility as information about the DGP increases. To make reducibility directly testable, we introduce a statistical framework for studying epistemic uncertainty under information growth. Our framework specifies an information-growth experimental protocol and a consistency criterion for epistemic predictors, while using projective graph DGPs to ensure that growing graphs, which in general need not provide increasing information about the same DGP, constitute coherent observations of the same underlying process. We show that EDL methods do not explicitly estimate data uncertainty arising from a single finite graph observation and instead regulate epistemic uncertainty through model hyperparameters, precluding consistency, as corroborated by controlled information-growth experiments. As an alternative, we propose graph bootstrap ensembles, capturing both data and procedural uncertainty through graph resampling and randomized training. Under the same experimental protocol, these ensembles exhibit epistemic uncertainty reduction beyond standard deep ensembles. These findings support bootstrap ensembles as candidate consistent epistemic predictors under information growth.

1 INTRODUCTION

Node classification lacks a principled way to test whether epistemic uncertainty falls as information about the same data-generating process grows. This paper introduces such a framework, finds graph EDL methods fall short of its consistency criterion, and presents graph bootstrap ensembles as candidate alternatives.

1 INTRODUCTION

  • Graph-specific EDL principles are defined on a fixed graph, while OOD detection evaluates downstream utility that need not establish epistemic reducibility.The paper frames these gaps through three research questions on a statistical framework, EDL consistency, and alternatives.Source: §1 · p. 2
  • The framework defines information-growth experiments and consistent epistemic predictors, using projective graph DGPs to keep nested graphs observations of the same process.Consistency requires decreasing and asymptotically vanishing uncertainty.Source: §1 · p. 2
  • Graph EDL methods omit data uncertainty from observing one finite graph and regulate epistemic uncertainty through hyperparameters, precluding consistency in the analysis and controlled experiments.Experiments corroborate insufficient epistemic concentration and persistent parameterization dependence.Source: §1 · p. 2
  • Graph bootstrap ensembles capture data and procedural uncertainty through graph resampling and randomized training, and experiments support them as candidate consistent predictors.They recover epistemic concentration absent from standard deep ensembles under the same protocol.Source: §1 · p. 2

2 BACKGROUND ON PREDICTIVE UNCERTAINTY AND MOTIVATION

The section establishes the predictive-uncertainty concepts and graph EDL approaches used in the paper, then explains why OOD performance does not test uncertainty reducibility under information growth.

2 BACKGROUND ON PREDICTIVE UNCERTAINTY AND MOTIVATION

  • Predictive uncertainty is decomposed into aleatoric uncertainty, which is irreducible, and epistemic uncertainty, which is reducible with additional data.The section represents a second-order predictor as a distribution over predictive distributions and defines TU, AU, and EU through entropy and mutual information.Source: §2 · pp. 2–3

2.1 GRAPH EDL MODELS

  • Graph EDL methods parameterize second-order predictions and organize uncertainty around feature support, structural support, and neighborhood conflict.S-BGCN-K uses a graph-dependent prior and dropout; density-based methods construct evidence from latent class densities and propagate it, while CUQ-GNN and GPN-LOP modify encoding or aggregation.Source: §2.1 · p. 3

2.2 WHY EVALUATE EPISTEMIC UNCERTAINTY UNDER INFORMATION GROWTH?

  • OOD detection does not establish epistemic reducibility: the best-performing uncertainty type varies by model and protocol, with AU/TU often best for LOC and Bernoulli FI and EU for Gaussian FI.Table 1 reports AUROC for PubMed under LOC and FI protocols.Source: §2.2 · p. 4, Table 1 · p. 4

3 A STATISTICAL FRAMEWORK FOR GRAPH EPISTEMIC UNCERTAINTY

The framework treats growing graphs as increasingly informative observations of one process and defines epistemic consistency through uncertainty reduction and convergence toward the Bayes-optimal predictor.

3 A STATISTICAL FRAMEWORK FOR GRAPH EPISTEMIC UNCERTAINTY

  • The framework extends the i.i.d. characterization of epistemic predictors to node classification with an information-growth protocol and a consistency criterion.It requires graph DGPs to be projective so nested observations preserve the same underlying process.Source: §3 · p. 4, §3.1 · p. 4

3.1 INFORMATION-GROWTH EXPERIMENTAL PROTOCOL

  • Information growth uses the graph as the sampling unit, nested graph observations from a projective DGP, and expanding training sets for the same node-classification task.The smaller graph must be induced within the larger graph, and its training set must be contained in the larger task's training set.Source: §3.1 · pp. 4–5

3.2 CONSISTENT EPISTEMIC PREDICTORS

  • Consistent predictors have uncertainty that decreases in expectation and converge in probability to a point mass at the restricted Bayes-optimal predictor.For the entropy-based measure considered, expected uncertainty tends to zero, leaving true aleatoric uncertainty; the criterion requires strong assumptions.Source: §3.2 · p. 5

4 GRAPH EDL UNDER INFORMATION GROWTH

The population analysis finds graph EDL methods do not generally meet the paper's consistency criterion because their uncertainty is set by priors or loss regularization rather than data-sampling uncertainty.

4 GRAPH EDL UNDER INFORMATION GROWTH

  • The analysis places several graph EDL objectives under one unified loss and studies their population optima after removing estimation and approximation errors.The unified loss is shown equivalent to the training objectives under method-specific choices of likelihood, prior, and parameters.Source: §4 · pp. 5–6
  • Graph EDL methods do not account for uncertainty from sampling a single finite graph, while fixed priors and finite tempering can leave non-vanishing epistemic uncertainty at population optima.For S-BGCN-K, increasing local evidence can yield a Dirac limit, but dropout need not vanish and the limit need not be Bayes-optimal.Source: §4 · p. 6
  • The asymptotic epistemic and aleatoric uncertainty of S-BGCN-K, GPN, GPN-LOP, and CUQ-GNN is determined externally by loss regularization or prior construction.Graph-specific uncertainty principles on a fixed graph do not by themselves guarantee information-growth behavior.Source: §4 · p. 6

5 GRAPH BOOTSTRAP ENSEMBLES

Graph bootstrap ensembles (GB-Ens) tie second-order predictive uncertainty to information available about the graph DGP by combining graph resampling with randomized training. This design represents both data and procedural variability, and projective synthetic graph DGPs provide a setting to assess its information-growth behavior.

5 GRAPH BOOTSTRAP ENSEMBLES

  • GB-Ens trains independently initialized GNNs on bootstrap graph realizations, combining data variability from resampling with procedural variability from randomized training.The crossed design separates disagreement across bootstrap realizations from training-induced disagreement within each realization.Source: §5 · pp. 6–7
  • The approach extends deep ensembles to graph bootstrapping, a setting described as largely unexplored, and is computationally feasible through parallel training and sequential inference.Its total computational cost is increased.Source: §5 · pp. 6–7
  • Projective synthetic graph DGPs with sampling processes accurately approximated by bootstrap provide a tractable setting to test whether GB-Ens exhibits consistent information-growth behavior.Graph bootstrap guarantees remain limited to specific combinations of DGPs, bootstrap schemes, and estimation targets, with no analogous result for mutual information.Source: §5 · p. 7
  • An edge-only local non-parametric bootstrap retains node identities, features, and labels while resampling graph structure to preserve the node-classification task.The procedure estimates edge probabilities from connectivity among similar nodes under an exchangeable graphon model.Source: §5 · p. 7

6 EXPERIMENTS

Controlled experiments on synthetic projective graph DGPs find that GB-Ens uncertainty contracts with information growth, unlike standard graph deep ensembles, while graph EDL uncertainty remains non-negligible or approximately constant and varies with parameterization. The degree of contraction depends on the predictor and learning procedure.

RQ2: Graph EDL models are inconsistent epistemic predictors

  • EDL methods either retain non-negligible epistemic uncertainty or remain approximately constant as information grows, and their uncertainty magnitudes depend substantially on model parameterization.At N = 10,000, changing the EDL regularization parameter λ substantially changes aleatoric uncertainty on the same graph.Source: §6 · p. 8, Figure 1 · p. 8

RQ3: GB-Ens is a family of candidate consistent epistemic predictors

  • 94% for GCN, 91% for APPNP, and 61% for GAT: GB-Ens epistemic uncertainty decreases monotonically from N = 500 to N = 10,000 on the exponential-decay graphon.On the SBM, APPNP and GCN also decrease substantially, while GAT shows a weaker, non-monotonic reduction.Source: §6 · p. 8, Figure 2 · p. 9
  • GB-Ens aleatoric uncertainty decreases and eventually stabilizes, with the three backbones approaching similar plateaus on both synthetic DGPs.The decomposition shows comparable seed and bootstrap contributions to epistemic uncertainty that decline with information, with relative magnitude varying by backbone and DGP.Source: §6 · p. 8, Figure 3 · p. 9
  • Standard graph deep ensembles show no consistent epistemic-uncertainty contraction, whereas graph resampling in GB-Ens induces convergence in the seed component as well as the bootstrap component.The gap between deep-ensemble uncertainty and GB-Ens randomized-training uncertainty widens with graph size.Source: §6 · p. 8, Figure 3 · p. 9
  • GB-Ens approximates true-DGP-resampling predictive variability well for APPNP and GCN, with normalized node-wise Wasserstein-1 distances of approximately 0.29 and 0.21, respectively; GAT’s distance rises from 0.45 to 0.62.The reported approximation quality varies across predictors.Source: §6 · p. 9

6 EXPERIMENTS

  • The results support GB-Ens as candidate consistent epistemic predictors, but contraction remains predictor-specific and can be weaker or partly non-monotonic when training variability persists.Experiments use synthetic projective graph DGPs, including an exponential-decay graphon and an assortative SBM.Source: §6 · pp. 7, 9

7 CONCLUSIONS

The paper argues that epistemic uncertainty in node classification should be assessed under information growth, and presents GB-Ens as a candidate approach that captures data and procedural uncertainty. Its appendix unifies graph EDL losses and shows that the GPN-LOP population optimum can retain positive epistemic uncertainty.

7 CONCLUSIONS

  • Epistemic uncertainty should be assessed under increasing information, and controlled experiments support GB-Ens as a family of candidate consistent predictors that captures data and procedural uncertainty.The paper notes that graph EDL models generally remain hyperparameter-dependent rather than estimating data uncertainty.Source: §7 · p. 9
  • Theoretical consistency of bootstrap-based graph epistemic predictors remains unestablished, and standard real-world benchmarks lack the sampling process needed to evaluate information growth from the same DGP.The paper points to real graph-growth benchmarks as a possible extension beyond synthetic random graphs.Source: §7 · pp. 9–10

A.1 UNIFIED EDL LOSS

  • The unified EDL loss is equivalent, up to scaling and additive constants, to the MSE loss under the stated Gaussian likelihood and parameter setting.For a uniform Dirichlet prior, the unified loss is likewise equivalent up to scaling and additive constants to the UCE loss.Source: §A.1 · p. 13

A.2.1 GPN-LOP

  • GPN-LOP’s population optimum retains strictly positive epistemic uncertainty for finite ν, even when the component means agree.The stated reason is that the Dirichlet components have finite concentration; an additional non-negative term contributes to the uncertainty.Source: §A.2.1 · p. 15

A.2.2 S-BGCN-K

The S-BGCN-K analysis relates graph growth to concentration of its graph-dependent GKDE prior, but that concentration need not yield a Bayes-optimal predictor. The experiments use projective graphon sequences and a local graph bootstrap that resamples graph structure while retaining node information.

A.2.2 S-BGCN-K

  • Under dense graph growth, an increasing amount of kernel-weighted labeled evidence can concentrate the effective GKDE prior and population optimum at a Dirac distribution.A sufficient condition is a diverging expected count of labeled nodes within some fixed graph distance; in the stated dense setting, positive normalized degree and retention of a positive fraction of neighbors give this for one-hop neighbors.Source: §A.2.2 · pp. 15–16
  • The limiting GKDE evidence vector need not equal the Bayes-optimal predictor, since it depends on choices such as bandwidth and graph-distance weighting.Thus concentration of the evidential distribution does not by itself guarantee the paper's consistency criterion.Source: §A.2.2 · p. 16
  • With fixed-rate MC dropout, evidential concentration is insufficient for predictive concentration unless predictions also become invariant to the dropout mask as information grows.The passage states that fixed-rate MC dropout does not generally ensure this invariance.Source: §A.2.2 · p. 17

B SYNTHETIC GRAPHONS

  • The experiments use two complementary homophilic graphon DGPs: an exponential-decay graphon for continuous latent similarity and an assortative SBM for discrete community structure.Both define balanced seven-class classification problems, with labels and features depending on latent position.Source: B SYNTHETIC GRAPHONS · p. 17
  • Each graphon sequence contains six logarithmically spaced sizes from 500 to 10,000 nodes, with smaller graphs formed as induced subgraphs of the largest realization.This yields nested observations from the same underlying realization.Source: B SYNTHETIC GRAPHONS · p. 17

C LOCAL BOOTSTRAP

  • The local bootstrap keeps node identities, features, and labels fixed while resampling graph structure from smoothed edge probabilities estimated using similar nodes.For synthetic graphons, similarity uses latent-coordinate Euclidean distance; for OOD benchmarks, it uses open-neighborhood Jaccard similarity, which favors similar observed connectivity profiles.Source: C LOCAL BOOTSTRAP · p. 18
  • For each node pair, the bootstrap estimates edge probability from the observed adjacency of locally similar nodes, then samples bootstrap graphs conditional on the resulting probability matrix.The directed estimate averages adjacency over the selected neighbors and is generally asymmetric; the procedure obtains an undirected edge probability before sampling unordered pairs.Source: C LOCAL BOOTSTRAP · p. 18

D MODEL ARCHITECTURES AND PARAMETERS

The appendix specifies the graph EDL baselines and the G-Ens and GB-Ens architectures. The ensembles share graphon hyperparameters, while GB-Ens additionally bootstraps graphs; OOD configurations are selected by dataset-specific validation searches.

D.1 GRAPH EDL MODELS

  • Graph EDL baselines include S-BGCN-K and S-BGCN-T-K, GPN variants, GPN-LOP, and CUQ-GNN variants, with OOD settings taken from dataset-specific configurations.The S-BGCN variants use 100 MC dropout samples for uncertainty estimates.Source: §D.1 · pp. 24–25
  • GPN, GPN-GD, GPN-LOP, and CUQ-GNN variants use learning rate 0.01 and 10 radial-flow layers; specified APPNP variants use K = 10.CUQ-GCN, CUQ-GAT, and CUQ-APPNP differ in the graph convolution used before density estimation; CUQ-GAT uses one attention head per layer, negative slope 0.2, and no attention-coefficient dropout.Source: §D.1 · pp. 24–25

D.2 G-ENS AND GB-ENS

  • G-Ens and GB-Ens share graphon hyperparameters, while OOD model and training hyperparameters are selected by validation accuracy and GB-Ens additionally applies graph bootstrapping.The graphon APPNP backbone uses a two-layer MLP with hidden dimension 64, dropout 0.3, and APPNP propagation with K = 10 and teleport probability 0.1.Source: §D.2 · p. 25
  • The graphon GAT backbone has two layers, total hidden dimension 64, and eight attention heads; the graphon GCN backbone has two layers and hidden dimension 64.For OOD data, the appendix searches over layer counts, dimensions, dropout, learning rates, weight decay, and, for GAT, attention-head counts.Source: §D.2 · pp. 25–26
  • Figure 4 presents uncertainty estimates from EDL models on the SBM.The supplied caption identifies the figure's scope but does not state a comparison outcome.Source: Figure 4 · p. 26

E ADDITIONAL EXPERIMENTAL RESULTS

On the SBM, EDL methods do not show consistent epistemic-uncertainty concentration, while GB-Ens shows substantial reductions for APPNP and GCN. Standard deep ensembles likewise lack consistent contraction, and GB-Ens uncertainty components and true-DGP distances vary by backbone.

E ADDITIONAL EXPERIMENTAL RESULTS

  • EDL methods fail to exhibit consistent EU concentration on SBM, while AU remains sensitive to λ; method differences in mean EU also persist on real-world OOD datasets.Table 9 reports mean epistemic uncertainty for EDL methods on OOD datasets.Source: E ADDITIONAL EXPERIMENTAL RESULTS · p. 26, Table 9 · p. 27
  • On SBM, GB-Ens EU falls 92% for APPNP and 94% for GCN from N = 500 to N = 10,000, versus a non-monotonic 34% reduction for GAT (maximum 42%).Figure 5a reports the reductions; GAT's maximum occurs at an intermediate graph size.Source: E ADDITIONAL EXPERIMENTAL RESULTS · p. 26
  • GB-Ens seed and bootstrap uncertainty contributions both decrease with information; its AU decreases and stabilizes at similar plateaus across backbones.For GAT, the EU reduction is non-monotonic mainly because of the seed component; the bootstrap component decreases more consistently.Source: E ADDITIONAL EXPERIMENTAL RESULTS · p. 26
  • G-Ens shows no consistent EU contraction on SBM, and its AU trajectories depend strongly on the backbone.The reported comparison concerns ensemble mean uncertainties on SBM.Source: E ADDITIONAL EXPERIMENTAL RESULTS · p. 26
  • On the SBM, distances normalized by the probability simplex’s Euclidean diameter of 2 remain relatively low for GCN (0.12–0.14) and APPNP (0.20–0.34), while GAT is larger (0.24–0.45).Source: E ADDITIONAL EXPERIMENTAL RESULTS · p. 27

F OUT-OF-DISTRIBUTION DETECTION

The OOD experiments evaluate uncertainty scores under leave-out-classes and feature-isolation protocols. Across models and OOD protocols, the most effective uncertainty type varies; some baselines could not be evaluated on OGBN-ArXiv under the reported settings.

F OUT-OF-DISTRIBUTION DETECTION

  • Across OOD experiments, the most effective uncertainty type depends on both the model and the OOD protocol.The reported evaluation includes EDL baselines, G-Ens, and GB-Ens.Source: F OUT-OF-DISTRIBUTION DETECTION · p. 27
  • On OGBN-ArXiv, CUQ-GAT and CUQ-GCN had accuracy ≈0.051–0.073, while GPN-LOP exceeded 80 GB of A100 GPU memory; these models are not reported.The accuracy uses hyperparameters recommended in the original paper.Source: F OUT-OF-DISTRIBUTION DETECTION · p. 27
  • The evaluation uses eight node-classification datasets, with leave-out classes excluded from training and validation but retained in the transductive graph.For GB-Ens, the same class partition is fixed across bootstrap replicates.Source: F OUT-OF-DISTRIBUTION DETECTION · p. 27
  • Feature isolation perturbs 100 test nodes with Gaussian or Bernoulli noise, and OOD scores are assessed using AUROC alongside ID and FI OOD accuracy.The same test nodes and perturbations are used across GB-Ens bootstrap replicates.Source: F OUT-OF-DISTRIBUTION DETECTION · p. 28

G COMPUTATIONAL COMPLEXITY

The complexity analysis contrasts the per-model costs of graph uncertainty methods and the additional resampling and repeated fitting required by GB-Ens. GB-Ens trades higher total preprocessing, training, and inference costs for moderate peak memory, with parallelizable member training and sequential inference.

G COMPUTATIONAL COMPLEXITY

  • GPN and CUQ-GCN admit O(N + M) implementations, whereas GPN-LOP and S-BGCN-K can incur O(N^2) computation.The cited costs arise from dense propagation for GPN-LOP and pairwise GKDE prior construction for S-BGCN-K.Source: G COMPUTATIONAL COMPLEXITY · p. 28
  • For GCN ensembles, training costs O(N + M) per member; GB-Ens also generates bootstrap graphs, at up to O(N^2) for general similarity search.The experiments use open Jaccard similarity as a cheaper alternative; bootstrap generation is repeated for each sample.Source: G COMPUTATIONAL COMPLEXITY · p. 28
  • GB-Ens trades higher total preprocessing, training, and inference costs for moderate peak memory, while sequential inference keeps memory at O(N + M).Its 100 members can be trained independently and in parallel; graph bootstrapping is particularly costly on larger graphs.Source: G COMPUTATIONAL COMPLEXITY · pp. 28–29, Table 21 · p. 32, Table 22 · p. 33

Related papers

Loading 2610.03418v1…