Rethinking Epistemic Uncertainty in Node Classification through Information Growth

Preprint

R ETHINKING E PISTEMIC U NCERTAINTY IN N ODE C LASSIFICATION THROUGH I NFORMATION G ROWTH Emma Meneghini1,2 , Francesco Ferrini2 , Bruno Lepri2 , Andrea Passerini1 , Veronica Lachi3 1

University of Trento, 2 Fondazione Bruno Kessler, FBK, 3 University of Tromsø

arXiv:2610.03418v1 [cs.LG] 2 Oct 2026

A BSTRACT Epistemic uncertainty should decrease as additional information about the datagenerating 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

I NTRODUCTION

Machine learning models are increasingly expected to provide not only accurate predictions, but also reliable estimates of predictive uncertainty (Abdar et al., 2021; Gawlikowski et al., 2023; Wang et al., 2025). Predictive uncertainty is commonly decomposed into aleatoric uncertainty, arising from intrinsic ambiguity in the data-generating process (DGP) and thus irreducible, and epistemic uncertainty, arising from limited knowledge of that process and thus reducible with additional data (Hüllermeier & Waegeman, 2021; Sale et al., 2026). In classical supervised learning with independent and identically distributed (i.i.d.) observations, under suitable regularity conditions, epistemic uncertainty is operationally characterized to decrease monotonically as information increases and eventually vanish (Bengs et al., 2022; Juergens et al., 2024; Shen et al., 2024). Extending this characterization to node classification on graphs is non-trivial. While increasing sample size provides a natural information-growth mechanism in the i.i.d. setting, no analogous mechanism is readily available for node classification. Intuitively, information growth would involve progressively larger graph observations and training sets becoming available, allowing predictors to be retrained on more informative observations for the same node classification problem. However, nodes are dependent, and observing more of them does not necessarily yield more information about the same underlying DGP (Shalizi & Rinaldo, 2013). Consequently, node classification currently lacks a framework for assessing the reducibility of epistemic uncertainty under information growth. Graph uncertainty quantification has been studied using a variety of approaches (see Wang et al. (2024); Chen et al. (2024) for reviews). Among these, evidential deep learning (EDL) methods (Zhao et al., 2020; Stadler et al., 2021; Hart et al., 2023; Damke & Hüllermeier, 2024a;b) are particularly relevant because they make the epistemic interpretation a central modeling objective, 1

Preprint

prescribing appropriate uncertainty behavior through graph-specific principles, including reducibility through feature support and structural support, and the reducibility or irreducibility due to neighborhood conflict. However, these principles are defined with respect to the features and topology of a fixed observed graph rather than under information growth. Empirical evaluations likewise assess epistemic uncertainty through its utility for out-of-distribution (OOD) detection, whose optimal predictors need not coincide with predictors of reducible epistemic uncertainty (Paplhám et al., 2026). While informative about task-specific downstream utility, such evaluations therefore cannot establish whether an uncertainty score has this epistemic interpretation. Together, these limitations raise fundamental questions about how epistemic uncertainty should be defined and modeled in node classification. We investigate these issues through three research questions: (RQ1) What constitutes a principled statistical framework for epistemic predictors in node classification? (RQ2) Are graph EDL models consistent epistemic predictors, and, if not, what are their fundamental limitations? (RQ3) Which alternative approach can address these limitations? Contributions. We address these questions through three main contributions. (1) We establish the first statistical framework for epistemic uncertainty under information growth in node classification, comprising an information-growth experimental protocol and a definition of consistent epistemic predictors. The former naturally requires projective graph DGPs to preserve the underlying node-classification problem across nested graphs and learning tasks (Shalizi & Rinaldo, 2013), while the latter requires decreasing and asymptotically vanishing uncertainty. Together, these provide a statistical basis for assessing epistemic reducibility beyond conventional evaluations. (2) We unify graph EDL objectives and characterize their population optima, showing how model hyperparameters artificially regulate epistemic uncertainty in the absence of explicit estimation of data uncertainty (Shen et al., 2024), arising from observing a single finite realization of the DGP, ultimately precluding epistemic consistency. Controlled information-growth experiments on projective graphs confirm insufficient epistemic concentration and persistent parameterization dependence, corroborating the structural limitations that undermine their use as consistent epistemic predictors. (3) Motivated by evidence that bootstrap-based ensembles capture data and procedural uncertainty (Jimenez et al., 2026), thus enabling decreasing epistemic uncertainty in the i.i.d. setting (Jain & Bates, 2025), we extend this approach to graphs through graph bootstrap ensembles. Under the same protocol as in (2), the experiments support these ensembles as a family of candidate consistent epistemic predictors, demonstrating the ability to recover epistemic concentration absent from standard deep ensembles. Together, these contributions establish a statistical foundation for understanding epistemic uncertainty in node classification, reveal the limitations of existing evidential approaches when assessed through information growth, and introduce graph bootstrap ensembles as a theoretically motivated, empirically supported alternative for modeling epistemic uncertainty that contracts under information growth.

2

BACKGROUND ON P REDICTIVE U NCERTAINTY AND M OTIVATION

Let G = (V, E) be an undirected attributed graph with |V| = N , adjacency matrix A ∈ {0, 1}N ×N , and node feature matrix X ∈ RN ×D . Let Y = {1, . . . , C} denote the set of class labels. In semisupervised node classification, a set of labeled nodes T (tr) ⊂ V is used to predict the labels of the remaining nodes T (te) = V \ T (tr) . We consider quantifying the uncertainty of these predictions. A probabilistic classifier associates each node i ∈ V with a predictive categorical distribution θ(i) ∈ PC ∆C , where ∆C = {θ ∈ RC : θc ≥ 0, c=1 θc = 1} denotes the probability simplex over Y. We adopt a second-order probabilistic framework in which the predictive distribution is itself regarded as a random variable Θ(i) . The second-order predictor Q(i) specifies a distribution over predictive distributions Θ(i) ∼ Q(i) , with Q : (G, i) 7→ P(∆C ). We use the standard information-theoretic decomposition of total predictive uncertainty into aleatoric and epistemic components (Depeweg, 2019; Wimmer et al., 2023). Since the following quantities are defined node-wise, we omit the superscript (i) and define the predictive mean by θ̄ = EQ [Θ]. The total uncertainty (TU) is the 2

Preprint

Shannon entropy of the predictive mean, TU(Q) = H(EQ [Θ]) = −

C X

θ̄c log θ̄c .

(1)

c=1

Aleatoric uncertainty (AU) is the irreducible uncertainty about the class label remaining after conditioning on the predictive distribution and is given by the conditional entropy H(Y |Θ), Z X C AU(Q) = H(Y |Θ) = EQ [H(θ)] = − θc log θc dQ(θ). (2) ∆C c=1

Epistemic uncertainty (EU) quantifies uncertainty about which predictive distribution should be assigned to the node and is given by the mutual information (MI) I between Y and Θ,   EU(Q) = I(Y ; Θ) = TU(Q) − AU(Q) = EQ DKL (θ∥θ̄) , (3) where DKL (·∥·) denotes the Kullback-Leibler divergence. We next review graph EDL methods, which directly parameterize Q and are the main second-order baselines considered in this work. 2.1

G RAPH EDL M ODELS (i)

Evidential node classifiers predict a second-order Dirichlet distribution Qψ = Dir(θ; α(i) ), with (i)

(i) α(i) = 1 + e(i) and class-wise evidence e(i) ∈ RC = α(i) /α0 gives the predictive >0 . Its mean θ̄ PC (i) (i) probabilities, while α0 = c=1 αc controls concentration. We organize graph EDL methods by their evidence parameterization and treatment of epistemic uncertainty: reduction through feature support and structural support, and reduction or irreducibility due to neighborhood conflict.

Direct parameterization. S-BGCN-K (Zhao et al., 2020) directly predicts Dirichlet evidence with a Bayesian GNN and uses dropout-induced variability for uncertainty estimation. During training, its prediction is regularized toward a node-specific, graph-dependent GKDE prior assigning higher evidence to nodes closer to labeled nodes of the corresponding class, thereby encoding structural support; S-BGCN-T-K additionally introduces a teacher network to improve predictive performance. (i) Assuming the Gaussian likelihood and denoting the one-hot ground-truth label ey , its objective is h i (i) prior,(i) 2 ℓMSE (ψ; i) = Eθ(i) ∼Q(i) ∥θ(i) − e(i) + λDKL (Qψ ∥QGKDE ). (4) y ∥ ψ

Density parameterization. GPN (Stadler et al., 2021) constructs evidence pseudo-counts from class-conditional densities in latent space, so that low-density regions receive little evidence, implementing feature support (Charpentier et al., 2020; 2022). These pseudo-counts are propagated P agg,(i) ft,(j) = j∈V ΠPPR , yielding α(i) = 1 + β agg,(i) , where through Personalized PageRank, βc i,j βc 1 is a uniform Dirichlet prior. Propagation implements structural support by diffusing evidence across neighboring nodes, while accumulating conflicting class evidence within the same Dirichlet implements neighborhood conflict, attributing disagreement to irreducible aleatoric uncertainty. Assuming the categorical likelihood p(y (i) |θ(i) ) = θy(i) , GPN minimizes (i)

ℓUCE (ψ; i) = Eθ(i) ∼Q(i) [−e(i)⊤ log θ(i) ] − λH[Qψ ]. y

(5)

ψ

Distance-regularized GPN-GD (Hart et al., 2023) augments this formulation with pairwise regularization of latent representations and evidence. CUQ-GNN (Damke & Hüllermeier, 2024b) retains the density-based parameterization and UCE objective but replaces the independent encoder and subsequent propagation step with a GNN encoder, jointly learning feature support, structural support, and the handling of neighborhood conflict. GPNLOP (Damke & Hüllermeier, 2024a) instead retains GPN’s feature pseudo-counts but aggregates the P (i) ft,(j) resulting Dirichlet distributions, Qψ = j∈V ΠPPR , allowing neighborhood disagreement i,j Qψ to contribute to epistemic, rather than necessarily aleatoric, uncertainty. It is trained using a tractable upper bound on the UCE loss of the mixture,   X ft,(j) ℓGPN−LOP (ψ; i) = ΠPPR Eθ(j) ∼Qft,(j) [−e(i)⊤ log θ(j) ] − λH[Qψ ] . (6) i,j y ψ

j∈V

3

Preprint

2.2

W HY E VALUATE E PISTEMIC U NCERTAINTY UNDER I NFORMATION G ROWTH ?

Epistemic uncertainty is commonly considered useful a priori for downstream tasks such as OOD detection on graphs, as the lack of model knowledge about OOD inputs is expected to result in higher epistemic uncertainty (Bazhenov et al., 2023; Wang et al., 2024), and performance on these benchmarks is therefore used to assess the quality of EDL uncertainty estimates. However, our results show that the most effective uncertainty type depends on the particular model and OOD protocol, with AU/TU typically performing best for leave-out-classes (LOC) and feature isolation (FI) with Bernoulli perturbations, and EU for Gaussian FI (Table 1; additional results in Appendix F). That non-epistemic components can outperform EU supports growing criticism that OOD discrimination and the reducibility of epistemic uncertainty under increasing information constitute distinct objectives whose optimal predictors need not coincide (Li et al., 2025; Paplhám et al., 2026). This motivates evaluating epistemic uncertainty under information growth. Table 1: AUROC for OOD detection on PubMed under LOC and FI protocols. Best-performing uncertainty type(s) for each EDL model and OOD protocol are shown in bold. LOC

3

FI (Bernoulli)

FI (Gaussian)

Model

TU

AU

EU

TU

AU

EU

TU

AU

EU

CUQ-APPNP CUQ-GAT CUQ-GCN GPN GPN-GDEVI GPN-GDLAT GPN-LOP S-BGCN-K S-BGCN-T-K

0.693 0.709 0.717 0.730 0.800 0.724 0.748 0.625 0.607

0.693 0.709 0.717 0.730 0.771 0.724 0.781 0.627 0.611

0.643 0.618 0.591 0.769 0.857 0.764 0.651 0.500 0.507

0.652 0.586 0.613 0.593 0.585 0.596 0.578 0.646 0.654

0.652 0.586 0.613 0.593 0.579 0.596 0.446 0.679 0.677

0.616 0.540 0.554 0.638 0.615 0.640 0.689 0.288 0.308

0.975 0.660 0.936 0.560 0.578 0.559 0.696 0.342 0.447

0.942 0.659 0.858 0.560 0.569 0.559 0.588 0.001 0.006

0.994 0.684 0.945 0.642 0.621 0.658 0.767 1.000 1.000

A S TATISTICAL F RAMEWORK FOR G RAPH E PISTEMIC U NCERTAINTY

Addressing (RQ1), we extend the i.i.d. characterization of epistemic predictors (Bengs et al., 2022; Juergens et al., 2024) to node classification by defining a statistical framework with an informationgrowth experimental protocol and a consistency criterion for epistemic predictors. 3.1

I NFORMATION -G ROWTH E XPERIMENTAL P ROTOCOL

Constructing an information-growth experimental protocol for node classification requires three components: (i) the sampling unit, i.e., what constitutes one observation from the DGP; (ii) the sampling scheme, i.e., how increasingly informative observations are generated from the same DGP; and (iii) the learning task, i.e., how the supervised prediction problem evolves along this sequence. Sampling unit. Unlike classical datasets, the nodes of a graph are not a collection of i.i.d. observations. We therefore take the observed graph G = (V, E), equivalently the subgraph induced by V, as the sampling unit, following the graph-as-observation perspective of Shalizi & Rinaldo (2013). Increasing information then corresponds to observing nested graphs G ⊂ G ′ , with V ⊂ V ′ and G equal to the subgraph of G ′ induced by V. Sampling scheme. Requiring two nested graphs to arise from the same DGP is non-trivial. This consistency is implicit in the i.i.d. setting, where every finite sample is a restriction of the same infinite sequence, but need not hold across graphs of different sizes. We make it explicit through projectibility (Shalizi & Rinaldo, 2013). Let A be a collection of finite subsets of a countable node index set I, ordered by inclusion, and let {PA,ϕ }A∈A,ϕ∈Φ denote a family of finite-dimensional DGPs, where GA ∼ PA,ϕ denotes the attributed graph indexed by A. For A ⊂ B, let πB→A denote the natural projection that restricts an observation indexed by B to the indices in A. Definition 3.1 (Projective DGP). The family {PA,ϕ }A∈A,ϕ∈Φ is projective if, for every A ⊂ B, −1 PA,ϕ = PB,ϕ ◦ πB→A

∀ϕ ∈ Φ.

(7)

Thus, projectibility gives a coherent meaning to information growth by ensuring that every smaller observation has exactly the distribution obtained by marginalizing any larger observation under 4

Preprint

the stochastic process with the same parameter ϕ. Moreover, by the Kolmogorov extension theorem (Kallenberg, 1997), every such projective family uniquely defines an infinite-dimensional distribution Pϕ whose finite-dimensional marginals are precisely {PA,ϕ }A∈A . Dense graphons are an important class of projective graph families (Veitch & Roy, 2015) and will serve as the concrete instantiation of this framework in our experiments. Other prominent graph models, including many exponential random graph models and sparse random graph formulations, are not projective (Shalizi & Rinaldo, 2013; Schweinberger et al., 2017). Learning task. Finally, the supervised tasks induced by increasingly large graph observations must exploit the corresponding information growth. If T (tr) ⊂ V and T ′(tr) ⊂ V ′ denote the training sets associated with G ⊂ G ′ , respectively, we require T (tr) ⊂ T ′(tr) , so that each larger task extends the previous one with additional information about the same underlying node-classification problem. Validation and test sets are defined analogously. 3.2

C ONSISTENT E PISTEMIC P REDICTORS

We now characterize a consistent epistemic predictor under this information-growth experimen(i) tal protocol. For an increasing sequence An ⊂ An+1 , with |An | = n, let QAn = {QAn }i∈An denote the collection of node-wise second-order predictors. For an epistemic uncertainty measure U , we define the uncertainty of this collection as the average node-wise uncertainty ŪAn := P (i) |An |−1 i∈An U (QAn ). We define consistency over the full node set An , even though empirically we evaluate uncertainty on the test nodes. Let p⋆ϕ denote the Bayes-optimal predictor under the infinite-dimensional law Pϕ induced by projectibility, and p⋆ϕ |An its restriction to An . Definition 3.2 (Consistent epistemic predictors). Under the information-growth experimental protocol defined in Section 3.1, a sequence of collections of second-order predictors {QAn }n≥1 is consistent if the following two conditions hold: 1. Monotonicity. For every n, EGAn [ŪAn ] ≥ EGAn+1 [ŪAn+1 ]. Furthermore, there exist n0 and k > 0 such that EGAn [ŪAn0 ] > EGAn +k [ŪAn0 +k ]. 0

0

2. Consistency. As |An | → ∞, QAn converges in probability to the Dirac measure at p⋆ϕ |An P (i) (i) under the distance d(QAn , δp⋆ϕ|A ) = |An |−1 i∈An d(QAn , δp⋆ ), where the noden

ϕ|An

wise distance d metrizes weak convergence on P(∆C ). These requirements characterize epistemic uncertainty as reducible with information: by condition (1), it decreases in expectation, excluding constant uncertainty sequences (Juergens et al., 2024), and by (2), it vanishes through concentration on the limiting Bayes-optimal predictor (Bengs et al., 2022). For the entropy-based uncertainty considered here, this yields limn→∞ EGAn [ŪAn )] = 0, leaving only true aleatoric uncertainty. Such consistency requires strong assumptions (Jain & Bates, 2025); in practice, model misspecification and estimation bias may affect the predictor’s estimates without being explicitly represented by its epistemic uncertainty (Jimenez et al., 2026).

4

G RAPH EDL UNDER I NFORMATION G ROWTH

We examine graph EDL methods considered in Section 2.1 when estimation and approximation errors are removed. By analyzing their population optima, we study whether they are consistent epistemic predictors per Definition 3.2. Unlike their i.i.d. counterparts, these methods incorporate graphspecific uncertainty principles and losses, motivating an extension of the analogous population-level analysis by Shen et al. (2024). To analyze them within a common framework, we express their objectives through the following unified loss. Definition 4.1 (Unified EDL loss). Let Qprior be a fixed Dirichlet prior, p(y|θ) a likelihood, and ν > 0 a tempering parameter. For each node i, the unified EDL loss is (i)

ℓU (ψ; i) := DKL (Qψ ∥Qν (·|y (i) )), where Qν (θ|y) ∝ Qprior (θ)p(y|θ)ν denotes the tempered posterior. 5

(8)

Preprint

The next lemma establishes the equivalence between ℓU and the training objectives of each method. Lemma 4.2. The unified EDL loss ℓU is equivalent, up to positive scaling and a ψ-independent additive constant, to the EDL objectives under the following choices: (i)

(i)

1. p(ey |θ(i) ) = N (ey ; θ(i) , σ 2 IC ), Qprior is a fixed Dirichlet prior, and λ = 2σ 2 /ν, yielding ℓMSE . (i)

2. p(y (i) |θ(i) ) = θy(i) , Qprior is a uniform Dirichlet prior, and λ = ν −1 , yielding ℓUCE . 3. With a uniform Dirichlet prior Qprior and λ = ν −1 , evaluating the UCE loss at the (j) PPR-weighted soft target ẽy yields the reformulated GPN-LOP node-wise objective ℓ̃GPN−LOP (ψ, j) ∝ ℓ̃UCE (ψ, j); hence, it is equivalent to the unified objective ℓ̃U (ψ; j). We now characterize the population optimum of this common loss. Theorem 4.3. The population minimizer of the unified EDL loss ℓU under Pϕ satisfies (i)

arg min EPϕ (A,X,Y ) [ℓU (ψ; i)] = arg min EPϕ (A,X) [DKL (Qψ ∥Q⋆,(i) )], ψ

where Q⋆,(i) (θ) = R

(9)

ψ

Qprior (θ) exp(νEPϕ (y(i) |X,A) [log p(y (i) |θ(i) )]) ∆C

Qprior (θ′ ) exp(νEPϕ (y(i) |X,A) [log p(y (i) |θ′ )]) dθ′

.

(10)

The proofs of Lemma 4.2 and Theorem 4.3 are provided in Appendix A.1. For fixed Qprior and finite ν, GPN, GPN-LOP, and CUQ-GNN retain non-vanishing epistemic uncertainty at the population optimum, failing Definition 3.2, while their aleatoric uncertainty depends on ν and may differ from that of the Bayes-optimal predictor; see Appendix A.2.1 for more details on GPN-LOP. For S-BGCN-K, an unbounded increase in local evidence, such as under the dense graphon setting, implies convergence of the population-level GKDE prior and the corresponding population optimum to a Dirac distribution; see Appendix A.2.2. With Monte Carlo dropout, however, epistemic uncertainty need not vanish (Verdoja & Kyrki, 2020). The location of the limiting Dirac also depends on the GKDE construction and need not be Bayes-optimal. Moreover, because they are deterministic models, none of these methods account for epistemic uncertainty induced by data sampling (Shen et al., 2024), which is a recognized source of epistemic uncertainty (Jimenez et al., 2026) and, in our setting, corresponds to randomness from observing a single finite graph. S-BGCN-T-K and GPN-GD additionally regularize class-probability estimation and pairwise relations between training nodes, respectively, without introducing further mechanisms for evidence accumulation under graph growth, and are therefore not analyzed separately. Thus, the asymptotic behavior of epistemic and aleatoric uncertainty predicted by S-BGCN-K, GPN, GPN-LOP, and CUQ-GNN is determined externally, either by the loss regularization or by the construction of the prior. Graph-specific uncertainty principles defined on a fixed graph therefore do not by themselves guarantee the required information-growth behavior.

5

G RAPH B OOTSTRAP E NSEMBLES

The previous analysis motivates constructing a second-order predictor whose uncertainty is tied explicitly to the information available about the graph DGP. We pursue this idea through graph bootstrap ensembles (GB-Ens), extending deep ensembles, an already understudied approach in node classification (Vieira et al., 2026), to the largely unexplored setting of graph bootstrapping. For each of B bootstrap graph realizations, we train S independently initialized GNNs, mirroring i.i.d. bootstrap ensembles that combine procedural and data variability through resampling (Juergens et al., 2024; Shen et al., 2024; Jain & Bates, 2025; Jimenez et al., 2026). The ability to represent both recognized sources of epistemic uncertainty (Jain & Bates, 2025; Jimenez et al., 2026) provides a key motivation for using bootstrap ensembles rather than alternative second-order predictors, including EDL models and deep ensembles, which may fail to capture one or both sources. In the i.i.d. setting, bootstrap-based MI has also been shown, under suitable conditions, to converge asymptotically to its Bayesian counterpart (Jain & Bates, 2025), providing theoretical support for 6

Preprint

bootstrap-based epistemic uncertainty estimation with neural networks. For graphs, however, bootstrap guarantees remain restricted to specific combinations of graph DGPs, bootstrap schemes, and estimation targets (Schmid & Desmarais, 2017; Levin & Levina, 2019; Green & Shalizi, 2022; Lin et al., 2020; Shao & Le, 2024), with no analogous result for MI. Nevertheless, projective synthetic graph DGPs whose sampling process can be accurately approximated by a bootstrap procedure provide a tractable setting for studying whether graph bootstrap ensembles empirically exhibit the consistent information-growth behavior of Definition 3.2, analogous to that established in the i.i.d. setting. GB-Ens is also computationally feasible despite increased total cost, through parallel training and sequential inference; see Appendix G for computational comparisons. (i)

Uncertainty decomposition. For node i, let θb,s ∈ ∆C be the predictive distribution from seed s on bootstrap realization b. The resulting second-order predictor and predictive mean are B

(i)

QB,S =

S

B

1 XX δθ(i) , b,s BS s=1

θ̄(i) =

b=1

S

1 X X (i) θb,s , BS s=1

(11)

b=1

(i)

where δθ(i) denotes the Dirac measure concentrated at θb,s , with b,s

B

TU(i) = H(θ̄(i) ),

AU(i) =

S

1 XX (i) H(θb,s ), BS s=1

EU(i) = TU(i) − AU(i) .

(12)

b=1

The crossed B × S design further allows us to separate the two sources of epistemic uncertainty PS (i) (i) represented by GB-Ens. With the seed-averaged prediction θ̄b = S −1 s=1 θb,s , " # B B S X X X 1 1 1 (i) (i) (i) (i) (i) EUboot = H(θ̄(i) ) − H(θ̄b ), EUseed = H(θ̄b ) − H(θb,s ) . (13) B B S s=1 b=1

b=1

Here, EUboot measures disagreement across bootstrap graph realizations, while EUseed measures (i) (i) training-induced disagreement within each realization, and EU(i) = EUboot + EUseed . Graph resampling. To instantiate the graph-resampling component of GB-Ens, we adopt a local non-parametric bootstrap adapted from Jeong & Donnat (2025), developed under an exchangeable graphon model. It estimates asymptotically unbiased edge probabilities from the observed connectivity of similar nodes and samples graph realizations accordingly. We use an edge-only bootstrap that retains node identities, features, and labels across realizations, thereby preserving the node classification task while capturing sampling variability in the graph structure. The complete resampling procedure and implementation details are given in Appendix C.

6

E XPERIMENTS

We empirically address (RQ2)–(RQ3) through controlled experiments on synthetic projective graph DGPs. For (RQ2), we validate our analysis of graph EDL uncertainty under information growth. For (RQ3), we assess graph bootstrap ensembles as an alternative approach to epistemic prediction. Code is available at https://github.com/emmamenegh/Research-Code-Release. Models. We evaluate S-BGCN-K and S-BGCN-T-K (Zhao et al., 2020), GPN (Stadler et al., 2021), GPN-GDEVI and GPN-GDLAT (Hart et al., 2023), GPN-LOP (Damke & Hüllermeier, 2024a), CUQAPPNP, CUQ-GAT, and CUQ-GCN (Damke & Hüllermeier, 2024b) as EDL baselines, and GB-Ens with APPNP, GAT, and GCN architectures. Each GB-Ens comprises 25 × 4 models, corresponding to 25 bootstrap samples and 4 random seeds per sample. Model parameterizations are reported in Appendix D. Datasets. Our experiments comprise two synthetic projective graphon DGPs. The synthetic DGPs are an exponential-decay graphon and an assortative stochastic-block model (SBM), which define complementary continuous- and discrete-structure regimes for a balanced seven-class nodeclassification problem. For each DGP, we generate 20 independent replicates of a projective sequence, with six graph sizes logarithmically spaced between 500 and 10,000 nodes. At each graph size, we use 5%/15%/80% class-stratified train/validation/test splits constructed according to the 7

Preprint

(b) Aleatoric uncertainty across λ at N = 10,000.

(a) Epistemic uncertainty under information growth.

Figure 1: Uncertainty estimates of EDL models on the exponential-decay graphon.

protocol in Section 3.1 and fixed across bootstrap replicates for each observed graph. Full DGP specifications and graphon statistics are reported in Appendices B and C. RQ2: Graph EDL models are inconsistent epistemic predictors. We examine whether the uncertainty behavior of graph EDL models characterized at the nonparametric population optimum by Theorem 4.3 persists with finite data and parametric models. We assess both EU concentration with increasing information and the dependence of EU and AU on model parameterization. Figure 1a shows mean EU across 20 projective-sequence replicates of the exponential-decay graphon, with 95% bootstrap confidence intervals (CIs). S-BGCN-K and SBGCN-T-K exhibit decreasing EU, as permitted by their information-dependent prior, but remain non-negligible over the observed sequence, whereas GPN, GPN-GD, GPN-LOP, and CUQ-GNN remain approximately constant, consistent with their population optima retaining finite evidence. EU magnitude also differs substantially across methods, reflecting its theoretical dependence on the parameterization, as illustrated by the similar magnitudes of GPN, GPN-GD, and CUQ-GNN under shared parameter values. At N = 10,000, varying the EDL regularization parameter λ reveals substantial changes in AU on the same observed graph (Figure 1b), demonstrating its dependence on model parameterization rather than on the DGP alone. Analogous results for the SBM are reported in Appendix E. RQ3: GB-Ens is a family of candidate consistent epistemic predictors. Figure 2a shows mean GB-Ens epistemic uncertainty across 20 projective-sequence replicates of the exponential-decay graphon, with pointwise 95% bootstrap CIs. From N = 500 to N = 10,000, EU decreases monotonically by 94% for GCN, 91% for APPNP, and 61% for GAT. On the SBM (Appendix E), EU similarly decreases substantially for APPNP and GCN, whereas GAT shows a weaker, non-monotonic reduction due to persistent randomized-training variability, plausibly reflecting its sensitivity to learned attention weights and additional attention dropout. The decomposition in Figure 2b further shows comparable randomized-seed and bootstrap contributions to EU that decrease with increasing information, with relative magnitude depending on the backbone and DGP. Finally, Figure 3b shows that GB-Ens AU decreases and eventually stabilizes, with all three backbones approaching similar plateaus, consistent with convergence toward a predictor-independent estimate of aleatoric uncertainty. The same behavior is observed for the SBM (Appendix E). To assess the effect of graph resampling, we compare GB-Ens with standard graph deep ensembles (G-Ens), trained with 10 different random seeds on the observed graph using the same backbones. Figure 3a shows that, on the exponential-decay graphon, G-Ens exhibit no consistent EU contraction, while Figure 3b shows strongly backbone-dependent AU trajectories, with GAT trending upward and GCN continuing to decrease. Similar behavior is observed on the SBM (Appendix E). Moreover, the gap between G-Ens EU and the randomized-training component of GB-Ens widens with graph size, as the latter contracts under information growth while the former does not. Graph resampling therefore does not simply add bootstrap variability, but induces convergent behavior also in the seed component, enabling EU contraction that is not observed for standard deep ensembles. 8

Preprint

(a) Total epistemic uncertainty.

(b) Bootstrap and training-seed decomposition.

Figure 2: GB-Ens mean epistemic uncertainty on the exponential-decay graphon.

(a) Epistemic uncertainty of G-Ens.

(b) Aleatoric uncertainty of GB-Ens and G-Ens.

Figure 3: Ensemble mean uncertainties on the exponential-decay graphon.

As a simple diagnostic of GB-Ens’s approximation to the full second-order distribution induced by true-DGP resampling, which captures predictive variability without DGP estimation error, we compare the two distributions using normalized node-wise Wasserstein-1 distances. On the exponentialdecay graphon, distances remain small and stable with graph size for APPNP (≈ 0.29) and GCN (≈ 0.21), indicating good agreement, while increasing from 0.45 to 0.62 for GAT. Similar results on the SBM are reported in Appendix E, suggesting that approximation quality varies across predictors. Overall, these results support GB-Ens as a family of candidate consistent epistemic predictors. This behavior nevertheless remains predictor-specific, as EU contraction ultimately relies on regularity of the underlying learning procedure; persistent training variability can therefore produce weaker and partly non-monotonic reductions.

7

C ONCLUSIONS

Take-home message. Epistemic uncertainty in node classification should be assessed through its behavior under increasing information, rather than solely by obeying principles or being useful for downstream tasks on a fixed graph. This perspective identifies consistent epistemic uncertainty as requiring estimates that reflect data uncertainty rather than remaining hyperparameter-dependent, a requirement generally not met by graph EDL models. GB-Ens provides a constructive approach by capturing data and procedural uncertainty, with controlled experiments supporting it as a family of candidate consistent predictors. Limitations & future work. The theoretical consistency of bootstrap-based graph epistemic predictors remains to be established. Moreover, information-growth behavior cannot be evaluated on standard real-world benchmarks, which lack the sampling process required to generate increasingly informative observations from the same DGP. Benchmarks leveraging real graph-growth mechanisms, 9

Preprint

where projectibility is often natural (Shalizi & Rinaldo, 2013), could extend our analysis beyond synthetic random graphs, either retaining node classification and motivating improved bootstrapbased predictors or considering tasks more naturally aligned with graph growth.

R EFERENCES Moloud Abdar, Farhad Pourpanah, Sadiq Hussain, Dana Rezazadegan, Li Liu, Mohammad Ghavamzadeh, Paul Fieguth, Xiaochun Cao, Abbas Khosravi, U Rajendra Acharya, et al. A review of uncertainty quantification in deep learning: Techniques, applications and challenges. Information fusion, 76:243–297, 2021. Gleb Bazhenov, Denis Kuznedelev, Andrey Malinin, Artem Babenko, and Liudmila Prokhorenkova. Revisiting uncertainty estimation for node classification: New benchmark and insights, 2023. URL https://openreview.net/forum?id=DB3BH3arU2Y. Viktor Bengs, Eyke Hüllermeier, and Willem Waegeman. Pitfalls of epistemic uncertainty quantification through loss minimisation. Advances in Neural Information Processing Systems, 35: 29205–29216, 2022. Bertrand Charpentier, Daniel Zügner, and Stephan Günnemann. Posterior network: Uncertainty estimation without ood samples via density-based pseudo-counts. Advances in neural information processing systems, 33:1356–1367, 2020. Bertrand Charpentier, Oliver Borchert, Daniel Zügner, Simon Geisler, and Stephan Günnemann. Natural posterior network: Deep bayesian predictive uncertainty for exponential family distributions. In International Conference on Learning Representations, 2022. URL https: //openreview.net/forum?id=tV3N0DWMxCg. Chao Chen, Chenghua Guo, Rui Xu, Jiujiu Chen, Xiangwen Liao, Xi Zhang, Sihong Xie, Hui Xiong, and Philip Yu. Uncertainty quantification on graph learning: a survey. arXiv preprint arXiv:2404.14642, 2024. Clemens Damke and Eyke Hüllermeier. Linear opinion pooling for uncertainty quantification on graphs. In The 40th Conference on Uncertainty in Artificial Intelligence, 2024a. URL https: //openreview.net/forum?id=qLGkfpXTSn. Clemens Damke and Eyke Hüllermeier. Cuq-gnn: Committee-based graph uncertainty quantification using posterior networks. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 306–323. Springer, 2024b. Stefan Depeweg. Modeling epistemic and aleatoric uncertainty with bayesian neural networks and latent variables. PhD thesis, Technische Universität München, 2019. Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. Combining neural networks with personalized pagerank for classification on graphs. In International Conference on Learning Representations, 2019. URL https://openreview.net/forum?id=H1gL-2A9Ym. Jakob Gawlikowski, Cedrique Rovile Njieutcheu Tassi, Mohsin Ali, Jongseok Lee, Matthias Humt, Jianxiang Feng, Anna Kruspe, Rudolph Triebel, Peter Jung, Ribana Roscher, et al. A survey of uncertainty in deep neural networks: J. gawlikowski et al. Artificial intelligence review, 56(Suppl 1):1513–1589, 2023. C Lee Giles, Kurt D Bollacker, and Steve Lawrence. Citeseer: An automatic citation indexing system. In Proceedings of the third ACM conference on Digital libraries, pp. 89–98, 1998. Alden Green and Cosma Rohilla Shalizi. Bootstrapping exchangeable random graphs. Electronic Journal of Statistics, 16(1):1058–1095, 2022. Russell Hart, Linlin Yu, Yifei Lou, and Feng Chen. Improvements on uncertainty quantification for node classification via distance based regularization. Advances in Neural Information Processing Systems, 36:55454–55478, 2023. 10

Preprint

Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 33:22118–22133, 2020. Eyke Hüllermeier and Willem Waegeman. Aleatoric and epistemic uncertainty in machine learning: An introduction to concepts and methods. Machine learning, 110(3):457–506, 2021. Anchit Jain and Stephen Bates. Deep ensembles for epistemic uncertainty: A frequentist perspective. arXiv preprint arXiv:2510.22063, 2025. Sowon Jeong and Claire Donnat. LOBSTUR: A local bootstrap framework for tuning unsupervised representations in graph neural networks. In Machine Learning on Graphs in the Era of Generative Artificial Intelligence, 2025. URL https://openreview.net/forum?id= xRasvIyMcW. Sebastian Jimenez, Mira Juergens, and Willem Waegeman. Position: Epistemic uncertainty estimation methods are fundamentally incomplete. In Forty-third International Conference on Machine Learning Position Paper Track, 2026. URL https://openreview.net/forum? id=g598HZM6ib. Mira Juergens, Nis Meinert, Viktor Bengs, Eyke Hüllermeier, and Willem Waegeman. Is epistemic uncertainty faithfully represented by evidential deep learning methods? In Forty-first International Conference on Machine Learning, 2024. URL https://openreview.net/forum? id=mxjB0LIgpT. Olav Kallenberg. Foundations of modern probability. Springer, 1997. Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017. URL https: //openreview.net/forum?id=SJU4ayYgl. Keith Levin and Elizaveta Levina. Bootstrapping networks with latent space structure. arXiv preprint arXiv:1907.10821, 2019. Yucen Lily Li, Daohan Lu, Polina Kirichenko, Shikai Qiu, Tim GJ Rudner, C Bayan Bruss, and Andrew Gordon Wilson. Position: Supervised classifiers answer the wrong questions for ood detection. In Forty-second International Conference on Machine Learning Position Paper Track, 2025. Qiaohui Lin, Robert Lunde, and Purnamrita Sarkar. Trading off accuracy for speedup: Multiplier bootstraps for subgraph counts. arXiv preprint arXiv:2009.06170, 2020. Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. Automating the construction of internet portals with machine learning. Information Retrieval, 3(2):127–163, 2000. Galileo Namata, Ben London, Lise Getoor, and Bert Huang. Query-driven active surveying for collective classification. 2012. URL https://api.semanticscholar.org/CorpusID: 15384610. Jakub Paplhám, Willem Waegeman, Eyke Hüllermeier, and Vojtěch Franc. Evaluating epistemic uncertainty: Beyond ood detection and active learning. arXiv preprint arXiv:2607.14817, 2026. Yusuf Sale, Nikita Kotelevskii, Maxim Panov, and Eyke Hüllermeier. The aleatoric-epistemic dichotomy of uncertainty is meaningful and indispensable for machine learning. Available at SSRN 6783338, 2026. Christian S Schmid and Bruce A Desmarais. Exponential random graph models with big networks: Maximum pseudolikelihood estimation and the parametric bootstrap. In 2017 IEEE international conference on big data (Big Data), pp. 116–121. IEEE, 2017. Michael Schweinberger, Pavel N Krivitsky, and Carter T Butts. A note on the role of projectivity in likelihood-based inference for random graph models. arXiv preprint arXiv:1707.00211, 2017. 11

Preprint

Cosma Rohilla Shalizi and Alessandro Rinaldo. Consistency under sampling of exponential random graph models. Annals of statistics, 41(2):508, 2013. Zhixuan Shao and Can M Le. Parametric bootstrap for fixed edge-probability network models. arXiv preprint arXiv:2402.01866, 2024. Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint arXiv:1811.05868, 2018. Maohao Shen, Jongha Jon Ryu, Soumya Ghosh, Yuheng Bu, Prasanna Sattigeri, Subhro Das, and Gregory W Wornell. Are uncertainty quantification capabilities of evidential deep learning a mirage? Advances in Neural Information Processing Systems, 37:107830–107864, 2024. Maximilian Stadler, Bertrand Charpentier, Simon Geisler, Daniel Zügner, and Stephan Günnemann. Graph posterior network: Bayesian predictive uncertainty for node classification. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 18033–18048. Curran Associates, Inc., 2021. URL https://proceedings.neurips.cc/paper_files/paper/2021/ file/95b431e51fc53692913da5263c214162-Paper.pdf. Victor Veitch and Daniel M Roy. The class of random graphs arising from exchangeable random measures. arXiv preprint arXiv:1512.03099, 2015. Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018. URL https://openreview.net/forum?id=rJXMpikCZ. Francesco Verdoja and Ville Kyrki. arXiv:2008.02627, 2020.

Notes on the behavior of mc dropout.

arXiv preprint

Pedro C Vieira, Pedro Ribeiro, and Viacheslav Borovitskiy. Do deep ensembles actually capture uncertainty in graph neural networks? arXiv preprint arXiv:2605.22593, 2026. Fangxin Wang, Yuqing Liu, Kay Liu, Yibo Wang, Sourav Medya, and Philip S. Yu. Uncertainty in graph neural networks: A survey. Transactions on Machine Learning Research, 2024. ISSN 2835-8856. URL https://openreview.net/forum?id=0e1Kn76HM1. Kaizheng Wang, Fabio Cuzzolin, Keivan Shariatmadar, David Moens, and Hans Hallez. A review of uncertainty representation and quantification in neural networks. IEEE transactions on pattern analysis and machine intelligence, 2025. Lisa Wimmer, Yusuf Sale, Paul Hofman, Bernd Bischl, and Eyke Hüllermeier. Quantifying aleatoric and epistemic uncertainty in machine learning: Are conditional entropy and mutual information appropriate measures? In Uncertainty in artificial intelligence, pp. 2282–2292. PMLR, 2023. Hongteng Xu, Dixin Luo, Lawrence Carin, and Hongyuan Zha. Learning graphons via structured gromov-wasserstein barycenters. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 10505–10513, 2021. Xujiang Zhao, Feng Chen, Shu Hu, and Jin-Hee Cho. Uncertainty aware semi-supervised learning on graph data. Advances in neural information processing systems, 33:12827–12836, 2020.

A

G RAPH EDL U NDER I NFORMATION G ROWTH

A.1

U NIFIED EDL L OSS

In this section, we extend the unified formulation of EDL losses from the i.i.d. setting (Shen et al., 2024) to node classification. We begin by defining a unified EDL loss and establishing its equivalence to the MSE and UCE losses used by existing graph EDL methods. 12

Preprint

Let Qprior be a fixed Dirichlet prior and p(y|θ) a likelihood. For a tempering parameter ν > 0, define the tempered posterior Qν (θ|y) := R

Qprior (θ)p(y|θ)ν . Qprior (θ′ )p(y|θ′ )ν dθ′ ∆C

(1)

For each node i, the unified EDL loss is (i)

ℓU (ψ; i) := DKL (Qψ ∥Qν (·|y (i) )).

(2)

Expanding the KL divergence gives (i)

ℓU (ψ; i) = DKL (Qψ ∥Qprior ) − νEθ(i) ∼Q(i) [log p(y (i) |θ(i) )] + C,

(3)

ψ

where C is independent of ψ. (i)

(i)

Lemma A.1. For the Gaussian likelihood p(ey |θ(i) ) = N (ey ; θ(i) , σ 2 IC ) and a fixed Dirichlet prior Qprior , setting λ = 2σ 2 /ν yields ℓU (ψ; i) = λ−1 ℓMSE (ψ; i) + C, where

(4) (i)

2 prior ℓMSE (ψ; i) = Eθ(i) ∼Q(i) [∥θ(i) − e(i) ), y ∥ ] + λDKL (Qψ ∥Q

(5)

ψ

and C is independent of ψ. Thus, ℓU is equivalent, up to scaling and additive constants, to ℓMSE . Proof. Since (i) − log p(e(i) y |θ ) =

1 2 ′ ∥θ(i) − e(i) y ∥ +C , 2σ 2

(6)

substitution into equation 3 gives the result. (i)

Lemma A.2. For the categorical likelihood p(y (i) |θ(i) ) = θy(i) and a uniform Dirichlet prior Qprior , setting λ = ν −1 yields ℓU (ψ; i) = νℓUCE (ψ; i) + C, where

(7) (i)

ℓUCE (ψ; i) = Eθ(i) ∼Q(i) [−e(i)⊤ log θ(i) ] − λH(Qψ ), y

(8)

ψ

and C is independent of ψ. Thus, ℓU is equivalent, up to scaling and additive constants, to ℓUCE . (i)

(i)

Proof. The result follows directly from equation 3 and DKL (Qψ ∥Qprior ) = −H(Qψ ) + C ′ for a uniform Dirichlet prior. Lemma A.3. For each node j ∈ V with X

wj :=

ΠPPR > 0, i,j

(9)

i∈T (tr)

define the soft target ẽ(j) y :=

1 X PPR (i) Πi,j ey . wj (tr)

(10)

i∈T

The reformulated GPN-LOP node-wise loss satisfies ℓ̃GPN−LOP (ψ; j) = wj ℓ̃UCE (ψ; j), where

(11) ft,(j)

ℓ̃UCE (ψ; j) := Eθ(j) ∼Qft,(j) [−ẽ(j)⊤ log θ(j) ] − λH(Qψ y

).

(12)

ψ

Let

ft,(j)

ℓ̃U (ψ; j) := DKL (Qψ 13

∥Q̃(j) ν ),

(13)

Preprint

(j)

where Q̃ν denotes the tempered posterior under the soft-target categorical likelihood, QC (j) (j) (j) p(ẽy |θ(j) ) ∝ c=1 (θc )ẽy,c . Hence, under this soft-target likelihood, a uniform Dirichlet prior Qprior , and λ = ν −1 , ν ℓ̃GPN−LOP (ψ; j) + C, (14) ℓ̃U (ψ; j) = wj where C is independent of ψ. Thus, ℓ̃GPN−LOP is equivalent, up to scaling and an additive constant, (j) to the unified loss ℓ̃U associated with the soft target ẽy . Proof. Starting from the training objective,   X X ft,(j) L(ψ) = ΠPPR Eθ(j) ∼Qft,(j) [−e(i)⊤ log θ(j) ] − λH[Qψ ] , i,j y

(15)

ψ

i∈T (tr) j∈V

interchanging the finite sums gives L(ψ) =

X

ℓ̃GPN−LOP (ψ; j).

(16)

j∈V

For fixed j, linearity of expectation yields 



ℓ̃GPN−LOP (ψ; j) = Eθ(j) ∼Qft,(j) −(

X

(i) ⊤ (j)  ΠPPR i,j ey ) log θ

ψ

(17)

i∈T (tr)

−λ

X

ft,(j)

ΠPPR i,j H(Qψ

)

(18)

i∈T (tr)

  ft,(j) = wj Eθ(j) ∼Qft,(j) [−ẽ(j)⊤ log θ(j) ] − λH(Qψ ) y

(19)

= wj ℓ̃UCE (ψ; j).

(20)

ψ

Applying Lemma A.2 to this soft-target extension, ℓ̃U (ψ; j) = ν ℓ̃UCE (ψ; j) + C,

(21)

and substituting ℓ̃UCE (ψ; j) = wj−1 ℓ̃GPN−LOP (ψ; j) gives the result. We next characterize the unconstrained minimizer of the unified objective. Theorem A.4. The population minimizer of the unified EDL loss ℓU under Pϕ satisfies (i)

(i)

arg min EPϕ (X,A,Y ) [DKL (Qψ ∥Qν (·|y (i) ))] = arg min EPϕ (A,X) [DKL (Qψ ∥Q⋆,(i) )], ψ

(22)

ψ

where Q⋆,(i) (θ) = R

Qprior (θ) exp(νEPϕ (y(i) |X,A) [log p(y (i) |θ(i) )]) ∆C

Qprior (θ′ ) exp(νEPϕ (y(i) |X,A) [log p(y (i) |θ′ )]) dθ′

.

(23)

Proof. The proof follows analogously to the i.i.d. case in Theorem 5.1 of Shen et al. (2024), with (A, X) replacing the i.i.d. covariates. A.2 A.2.1

M ODEL -S PECIFIC P OPULATION O PTIMA GPN-LOP

For GPN-LOP, the population-optimal feature-based Dirichlet distribution at node j is deterP (k) mined by the PPR-weighted conditional class probabilities η̃ (j) = wj−1 k∈T (tr) ΠPPR , where k,j η P (k) PPR (k) wj = and η = EPϕ (y(k) |A,X) [ey ]. Under the categorical likelihood and k∈T (tr) Πk,j
uniform Dirichlet prior, Theorem A.4 therefore gives Qft⋆,(j) = Dir θ; αprior + ν η̃ (j) . Since PC (j) prior + ν, which remains finite for fixed ν. c=1 η̃c = 1, each component has total concentration α0 14

Preprint

P ft⋆,(j) . GPN-LOP aggregates these feature-based distributions through PPR, Q⋆,(i) = j∈V ΠPPR i,j Q Its epistemic uncertainty decomposes as X X ft,(j) (j) (i) EU(Q(i) ) = ΠPPR )+ ΠPPR ∥θ̄ ), (24) i,j EU(Q i,j DKL (θ̄ j∈V

where θ̄(i) =

j∈V

PPR (j) . j∈V Πi,j θ̄

P

The first term is strictly positive for finite ν, since each Dirichlet component has finite concentration, while the second term is non-negative. Hence, the GPN-LOP population optimum retains strictly positive epistemic uncertainty even when the component means agree. A.2.2

S-BGCN-K

Theorem A.4 characterizes the population optimum for a fixed prior and therefore does not directly apply to S-BGCN-K, whose GKDE prior depends on the observed graph and training labels. Marginalizing this data-dependent prior in the population objective yields an effective prior prior,(i) prior,(i) Qn , defined, for the data-dependent GKDE prior QGAn , by prior,(i)

Qprior,(i) (θ) ∝ exp(EGAn ∼PAn ,ϕ [log QGAn n

(θ)]).

(25)

This effective prior changes with graph size n. We first show that convergence of these priors implies convergence of the corresponding population optima, and then establish conditions under which the effective GKDE prior concentrates under graph growth. prior,(i)

}n≥1 be a sequence of Lemma A.5 (Population optima under convergent priors). Let {Qn prior,(i) prior,(i) . For fixed finite ν, suppose that g (i) is continuous and ⇒ Q∞ priors such that Qn strictly positive on ∆C . Then, the corresponding population optima prior,(i)

Q⋆,(i) (dθ) = R n ⋆,(i)

⋆,(i)

⋆,(i)

satisfy Qn ⇒ Q∞ , where Q∞ prior,(i) , namely, limiting prior Q∞

g (i) (θ)Qn

(dθ)

is the population optimum of Theorem A.4 associated with the prior,(i)

Q⋆,(i) ∞ (dθ) = R

g (i) (θ)Q∞

(dθ)

prior,(i) (dϑ) g (i) (ϑ)Q∞ ∆C

⋆,(i)

Moreover, Q∞

(26)

prior,(i) (dϑ) g (i) (ϑ)Qn ∆C

prior,(i)

is a Dirac distribution if and only if Q∞

.

(27)

is a Dirac distribution.

Proof. For any bounded continuous f : ∆C → R, R prior,(i) Z f (θ)g (i) (θ)Qn (dθ) ⋆,(i) f (θ)Qn (dθ) = ∆RC . prior,(i) (i) (θ)Q ∆C g (dθ) n ∆C

(28)

Since ∆C is compact, continuity of g (i) implies that g (i) and f g (i) are bounded and continuous. The prior,(i) prior,(i) assumed weak convergence Qn ⇒ Q∞ therefore gives Z Z Z Z (i) prior,(i) (i) prior,(i) (i) prior,(i) f g dQn → f g dQ∞ and g dQn → g (i) dQprior,(i) . (29) ∞ ⋆,(i)

⋆,(i)

Since g (i) is strictly positive on ∆C , the latter limit is strictly positive, and hence Qn ⇒ Q∞ . ⋆,(i) prior,(i) Moreover, strict positivity implies that Q∞ and Q∞ have the same null sets, and hence one is concentrated at a single point if and only if the other is. For the Gaussian likelihood underlying ℓMSE , we define the likelihood-derived weighting function g (i) (θ) = exp{ν EPϕ (y(i) |X,A) [log p(y (i) |θ)]}, which is continuous and strictly positive on the compact simplex. Hence, Lemma A.5 applies to any convergent sequence of priors. We next give sufficient conditions for a sequence of Dirichlet priors to concentrate. 15

Preprint

Lemma A.6 (Concentration of Dirichlet priors). Let (i)

Qprior,(i) = Dir(θ; βn(i) ), n

β0,n =

C X

(i)

(i) βn,c ,

βn

m(i) n =

(i)

(i)

(i)

prior,(i)

If β0,n → ∞ and mn → m(i) ∈ ∆C , then Qn (i)

prior,(i)

(i)

.

(30)

β0,n

c=1

⇒ δm(i) .

(i)

(i)

Proof. Let Θn ∼ Qn . Then, E[Θn ] = mn . Moreover, since mn,c ∈ [0, 1], we have (i) (i) mn,c (1 − mn,c ) ≤ 1/4, and thus, for each class c, (i)

Var(Θ(i) n,c ) =

(i)

mn,c (1 − mn,c ) (i) β0,n + 1

≤

1

→ 0,

(i) 4(β0,n + 1)

(i)

(i)

(31)

(i)

where the convergence follows from β0,n → ∞. Therefore, Θn − mn → 0 in probability. Since (i)

(i)

prior,(i)

mn → m(i) , it follows that Θn → m(i) in probability, and hence Qn (i)

prior,(i)

(i)

Thus, if β0,n → ∞ and mn → m(i) , Lemmas A.6 and A.5 give Qn δm(i) . Consequently, EU(Q⋆,(i) )→0 n

and

⇒ δm(i) . ⋆,(i)

⇒ δm(i) and Qn

AU(Q⋆,(i) ) → H(m(i) ). n

S-BGCN-K provides a graph-dependent Dirichlet prior through GKDE, with parameters X (i) βn,c =1+ 1{y (j) = c}gσ (dij ),

⇒

(32)

(33)

(tr) j∈Tn

where dij denotes the graph distance between nodes i and j, and gσ (dij ) is the Gaussian kernel applied to this distance, with bandwidth σ. Since the expectation of a Dirichlet log-density differs from the log-density of a Dirichlet distribution with expected parameters only by a θ-independent constant, the effective population prior is Qprior,(i) = Dir(θ; βn(i) ), n

(i) (i) βn,c = EGAn ∼PAn ,ϕ [βn,c ].

Summing over classes gives the total concentration of the effective prior, h X i (i) β0,n = C + EGAn ∼PAn ,ϕ gσ (dij ) .

(34)

(35)

(tr)

j∈Tn

Thus, concentration grows with the expected amount of kernel-weighted labeled evidence available around node i. In particular, for any fixed finite D, (i)

β0,n ≥ C + gσ (D)EGAn ∼PAn ,ϕ [|{j ∈ Tn(tr) : dij ≤ D}|],

(36)

where we use that the Gaussian kernel is non-increasing in distance. Hence, a sufficient condition (i) (tr) for β0,n → ∞ is the existence of a fixed D such that EGAn ∼PAn ,ϕ [|{j ∈ Tn : dij ≤ D}|] → ∞. Under the dense projective graph DGPs considered in our experiments, positive population normalized degree for node i, together with a training-label sampling scheme that retains a positive fraction of its neighbors, yields a diverging expected number of labeled one-hop neighbors, so the (i) condition holds with D = 1. If, in addition, the normalized GKDE evidence converges, mn → prior,(i) ⋆,(i) m(i) , Lemma A.6 gives Qn ⇒ δm(i) and Lemma A.5 then yields Qn ⇒ δm(i) . However, m(i) is the limiting vector of normalized population-averaged kernel-weighted class evidence induced by the GKDE construction and is not guaranteed to coincide with the Bayes-optimal ⋆,(i) predictor pϕ , as it depends on choices such as the GKDE bandwidth and the graph-distance weighting function. Hence, despite concentration of the evidential distribution, Definition 3.2 need ⋆,(i) ⋆,(i) not be satisfied, and AU(Qn ) → H(m(i) ) need not equal the true aleatoric uncertainty H(pϕ ). The analysis above considers S-BGCN-K with Monte Carlo (MC) dropout disabled, thereby isolating the uncertainty induced by the evidential objective. When MC dropout with a fixed Bernoulli 16

Preprint

dropout rate is enabled, as in the original formulation, concentration of the evidential distribution is no longer sufficient for concentration of the resulting predictive distribution: the predictions must additionally become invariant to the dropout mask as information grows. Fixed-rate MC dropout does not in general ensure such concentration, and has been shown to retain predictive variability independently of the amount of observed data in simple settings (Verdoja & Kyrki, 2020).

B

S YNTHETIC G RAPHONS

We consider two complementary homophilic graph DGPs: a smooth exponential-decay graphon, representing continuous latent similarity, and an assortative stochastic block model (SBM) graphon, representing discrete community structure, both commonly considered in the literature (Xu et al., 2021). Besides providing qualitatively different graph structure, the SBM connects our construction to projective dyadic-independence models studied within the exponential random-graph model framework of Shalizi & Rinaldo (2013). Both follow the graphon construction iid

Ui ∼ Unif(0, 1), Aij |Ui , Uj ∼ Bernoulli(W (Ui , Uj )),

(37) (38)

where W : [0, 1]2 → [0, 1] maps pairs of latent positions to edge probabilities. For the exponentialdecay graphon, this mapping depends directly on the distance between latent positions, Wexp (Ui , Uj ) = exp(−β|Ui − Uj |),

(39)

such that connectivity decreases smoothly with latent distance. For the SBM graphon, the latent space is instead partitioned into K blocks through a mapping b : [0, 1] → {1, . . . , K}. Edge probabilities are then determined by the corresponding entries of an assortative block probability matrix P , yielding the step-function graphon WSBM (Ui , Uj ) = Pb(Ui ),b(Uj ) .

(40)

Both DGPs define balanced seven-class node-classification problems in which labels and features depend on the latent position, with Yi | Ui ∼ PY ( · | Ui ), Xi | Ui ∼ PX ( · | Ui ).

(41) (42)

For the exponential-decay graphon, class probabilities vary smoothly over the latent space, with greater label ambiguity near transitions between neighboring classes. For the SBM graphon, class probabilities follow the block structure but vary smoothly within blocks, with greater ambiguity near block transitions. Each node additionally receives 12 noisy continuous and binary features that are informative of the latent class structure without deterministically identifying the observed label. Feature informativeness is likewise allowed to vary with latent position, such that graph structure and node features provide complementary and imperfect information about the class. Complete generator specifications and parameter settings are provided in Table 2. Tables 3–4 report the realized structural properties of the generated graph sequences across 20 independent realizations. Each projective graphon sequence comprises six graph sizes, logarithmically spaced between 500 and 10,000 nodes. We first generate the largest graph and construct each smaller graph as the induced subgraph on its first n nodes, thereby yielding a nested sequence from the same underlying realization.

17

Preprint

Table 2: Parameters used for the synthetic graph DGPs.

C

Component

Parameter

Value

Generation

Graph sizes n Independent sequences

500, 910, 1657, 3017, 5493, 10000 20

Exponential graphon

Decay β

15

SBM graphon

Blocks K Between-block probability pout Within-block increment δ Block-probability noise σP

7 0.02 0.83 0.02

Features

Dimension d Continuous-feature noise σX Binary-feature flip probability

12 0.04 0.20

Exponential labels

Gaussian width σY

0.03

SBM labels

Center / boundary class probability Boundary width

0.90/0.65 0.15

SBM features

Center / boundary class probability Boundary width

0.80/0.55 0.15

L OCAL B OOTSTRAP

We construct bootstrap graph replicates using a non-parametric procedure adapted from the local probability estimator of Jeong & Donnat (2025), developed under an exchangeable graphon model and exploiting node similarity. The procedure preserves the observed node set, features and labels across replicates, while resampling the graph structure from smoothed edge probabilities. For each node i ∈ V, we first construct a set Nk (i) of its k most similar nodes according to a chosen node similarity metric. In the synthetic graphon experiments, where the latent coordinates Ui are known, we use Euclidean distance in latent space, d(i, j) = ∥Ui − Uj ∥2 ,

i ̸= j.

(43)

For the OOD benchmark datasets, where latent coordinates are unavailable, we instead use the openneighborhood Jaccard similarity suggested by Jeong & Donnat (2025), J(i, j) =

|N (i) ∩ N (j)| , |N (i) ∪ N (j)|

i ̸= j,

(44)

where N (i) denotes the open graph neighborhood of node i. This criterion favors nodes with similar observed connectivity profiles, so that the selected neighbors provide local substitutes for node i when estimating its edge probabilities. The directed edge probability between nodes i and j is then estimated by averaging the observed adjacency of j over Nk (i): X 1 p̂ij = Auj . (45) |Nk (i)| u∈Nk (i)

Thus, p̂ij is the empirical fraction of nodes locally similar to i that are adjacent to j in the observed graph. Because this estimate is generally asymmetric, we obtain an undirected edge probability by 1 (46) p̂sym = (p̂ij + p̂ji ), ij 2 which preserves the asymptotic unbiasedness of the local probability estimator under the conditions of Jeong & Donnat (2025). Conditional on the resulting probability matrix, bootstrap graphs are generated independently by sampling each unordered node pair according to iid

sym Aboot ∼ Bernoulli(p̂sym ij,b |p̂ij ij ),

i < j,

b ∈ {1, . . . , B},

(47)

and setting Aboot ii,b = 0. The complete graph resampling procedure is given in Algorithm 1. Following the finite-sample specification of Jeong & Donnat (2025), we use k = 20 for both the synthetic graphons and the node classification benchmark datasets. 18

Preprint

Algorithm 1 Conditional local graph bootstrap Require: Graph G = (A, X), neighborhood size k, pairwise node similarity metric d, number of replicates B Ensure: Bootstrap graphs {Gbboot = (Aboot , X)}B b b=1 1: for i ∈ V do 2: Construct Nk (i) as the k nearest nodes similar to i according to d 3: end for 4: for i, j ∈ V, i ̸= j do X 1 5: p̂ij ← Auj |Nk (i)| u∈Nk (i)

6: end for 7: for i < j do p̂ij + p̂ji ← 8: p̂sym ij 2 9: end for 10: for b = 1, . . . , B do 11: for i < j do sym
12: Aboot ij,b ∼ Bernoulli p̂ij boot 13: Aboot ji,b ← Aij,b 14: end for 15: Aboot ii,b ← 0 for all i ∈ V 16: Gbboot ← (Aboot , X) b 17: end for 18: return {Gbboot = (Aboot , X)}B b b=1 .

The statistics of 25 bootstrap graphs are compared with those of the original graphs for the synthetic graphons and node classification benchmark datasets in Tables 3– 4 and 5, respectively. Table 3: Original and bootstrap graph statistics for the exponential-decay graphon at increasing sizes. Values are mean ± standard deviation across 20 graphon realizations, with bootstrap statistics averaged across 25 replicates per realization. n = 500

Metric

Original

Bootstrap

Features 12 12 Classes 7 7 Nodes 500 500 Edges Edges (1.547 × 104 ) ± 212.020 (1.530 × 104 ) ± 220.126 Average degree 61.882 ± 0.848 61.206 ± 0.881 Degree std. 10.118 ± 1.385 10.327 ± 1.311 Density (1.240 × 10−1 ) ± (1.700 × 10−3 ) (1.227 × 10−1 ) ± (1.765 × 10−3 ) Local clustering 0.404 ± 0.005 0.394 ± 0.004 Components 1 1 Giant component 500 500 Assortativity 0.416 ± 0.096 0.371 ± 0.093 Node homophily 0.631 ± 0.011 0.623 ± 0.012 Edge homophily 0.620 ± 0.013 0.612 ± 0.013 Transitivity 0.396 ± 0.005 0.386 ± 0.005 Triangle density (6.169 × 10−3 ) ± (1.826 × 10−4 ) (5.889 × 10−3 ) ± (1.837 × 10−4 )

n = 910

Metric Features Classes Nodes Edges Average degree Degree std.

Original

Bootstrap

12 7 910 (5.131 × 104 ) ± 361.446 112.768 ± 0.794 16.285 ± 1.714

12 7 910 (5.095 × 104 ) ± 362.437 111.969 ± 0.797 16.549 ± 1.712

19

Preprint

Density (1.241 × 10−1 ) ± (8.739 × 10−4 ) (1.232 × 10−1 ) ± (8.763 × 10−4 ) Local clustering 0.404 ± 0.003 0.399 ± 0.003 Components 1 1 Giant component 910 910 Assortativity 0.496 ± 0.082 0.464 ± 0.081 Node homophily 0.632 ± 0.005 0.628 ± 0.005 Edge homophily 0.621 ± 0.005 0.617 ± 0.005 Transitivity 0.396 ± 0.003 0.391 ± 0.003 Triangle density (6.170 × 10−3 ) ± (9.183 × 10−5 ) (6.013 × 10−3 ) ± (9.348 × 10−5 )

n = 1657

Metric

Original

Bootstrap

Features 12 12 Classes 7 7 Nodes 1657 1657 Edges Edges (1.705 × 105 ) ± (1.041 × 103 ) (1.697 × 105 ) ± (1.034 × 103 ) Average degree 205.798 ± 1.256 204.886 ± 1.249 Degree std. 27.837 ± 2.599 28.184 ± 2.567 Density (1.243 × 10−1 ) ± (7.585 × 10−4 ) (1.237 × 10−1 ) ± (7.540 × 10−4 ) Local clustering 0.404 ± 0.002 0.401 ± 0.002 Components 1 1 Giant component 1657 1657 Assortativity 0.572 ± 0.062 0.548 ± 0.062 Node homophily 0.631 ± 0.004 0.629 ± 0.004 Edge homophily 0.620 ± 0.004 0.618 ± 0.004 Transitivity 0.396 ± 0.003 0.393 ± 0.002 Triangle density (6.196 × 10−3 ) ± (8.944 × 10−5 ) (6.109 × 10−3 ) ± (8.044 × 10−5 )

n = 3017

Metric

Original

Bootstrap

Features 12 12 Classes 7 7 Nodes 3017 3017 Edges (5.661 × 105 ) ± (2.464 × 103 ) (5.646 × 105 ) ± (2.505 × 103 ) Average degree 375.244 ± 1.634 374.306 ± 1.661 Degree std. 48.265 ± 2.831 48.657 ± 2.799 Density (1.244 × 10−1 ) ± (5.417 × 10−4 ) (1.241 × 10−1 ) ± (5.506 × 10−4 ) Local clustering 0.403 ± 0.002 0.402 ± 0.002 Components 1 1 Giant component 3017 3017 Assortativity 0.609 ± 0.043 0.593 ± 0.044 Node homophily 0.631 ± 0.003 0.630 ± 0.003 Edge homophily 0.620 ± 0.003 0.619 ± 0.003 Transitivity 0.395 ± 0.002 0.395 ± 0.001 Triangle density (6.206 × 10−3 ) ± (5.918 × 10−5 ) (6.170 × 10−3 ) ± (6.114 × 10−5 )

n = 5493

Metric Features Classes Nodes Edges Average degree Degree std. Density Local clustering Components

Original

Bootstrap

12 12 7 7 5493 5493 (1.878 × 106 ) ± (6.496 × 103 ) (1.875 × 106 ) ± (6.503 × 103 ) 683.611 ± 2.365 682.675 ± 2.368 85.005 ± 4.412 85.439 ± 4.400 (1.245 × 10−1 ) ± (4.306 × 10−4 ) (1.243 × 10−1 ) ± (4.311 × 10−4 ) 0.404 ± 0.002 0.403 ± 0.001 1 1

20

Preprint

Giant component 5493 5493 Assortativity 0.632 ± 0.035 0.622 ± 0.035 Node homophily 0.631 ± 0.003 0.631 ± 0.003 Edge homophily 0.620 ± 0.003 0.619 ± 0.003 Transitivity 0.397 ± 0.002 0.395 ± 0.001 Triangle density (6.236 × 10−3 ) ± (5.362 × 10−5 ) (6.199 × 10−3 ) ± (4.463 × 10−5 )

n = 10000

Metric

Original

Bootstrap

Features 12 12 Classes 7 7 Nodes 10000 10000 Edges (6.224 × 106 ) ± (1.645 × 104 ) (6.220 × 106 ) ± (1.655 × 104 ) Average degree 1244.879 ± 3.290 1243.939 ± 3.310 Degree std. 152.286 ± 6.828 152.737 ± 6.834 Density (1.245 × 10−1 ) ± (3.291 × 10−4 ) (1.244 × 10−1 ) ± (3.310 × 10−4 ) Local clustering 0.404 ± 0.002 0.403 ± 0.002 Components 1 1 Giant component 10000 10000 Assortativity 0.652 ± 0.031 0.646 ± 0.031 Node homophily 0.631 ± 0.002 0.631 ± 0.002 Edge homophily 0.620 ± 0.002 0.620 ± 0.002 Transitivity 0.396 ± 0.002 0.396 ± 0.001 Triangle density (6.222 × 10−3 ) ± (4.641 × 10−5 ) (6.213 × 10−3 ) ± (3.253 × 10−5 )

Table 4: Original and bootstrap graph statistics for the SBM graphon at increasing sizes. Values are mean ± standard deviation across 20 graphon realizations, with bootstrap statistics averaged across 25 replicates per realization. n = 500

Metric

Original

Bootstrap

Features 12 12 Classes 7 7 Nodes 500 500 Edges (1.755 × 104 ) ± 161.030 (1.738 × 104 ) ± 169.203 Average degree 70.203 ± 0.644 69.502 ± 0.677 Degree std. 8.206 ± 1.813 8.799 ± 1.683 Density (1.407 × 10−1 ) ± (1.291 × 10−3 ) (1.393 × 10−1 ) ± (1.356 × 10−3 ) Local clustering 0.643 ± 0.005 0.550 ± 0.008 Components 1 1 Giant component 500 500 Assortativity 0.570 ± 0.127 0.458 ± 0.125 Node homophily 0.620 ± 0.016 0.601 ± 0.016 Edge homophily 0.619 ± 0.016 0.600 ± 0.017 Transitivity 0.641 ± 0.007 0.549 ± 0.010 Triangle density (1.270 × 10−2 ) ± (2.959 × 10−4 ) (1.070 × 10−2 ) ± (3.086 × 10−4 )

n = 910

Metric Features Classes Nodes Edges Average degree Degree std. Density

Original

Bootstrap

12 12 7 7 910 910 (5.804 × 104 ) ± 237.804 (5.767 × 104 ) ± 240.446 127.554 ± 0.523 126.742 ± 0.528 11.021 ± 2.066 11.708 ± 1.985 (1.403 × 10−1 ) ± (5.750 × 10−4 ) (1.394 × 10−1 ) ± (5.814 × 10−4 )

21

Preprint

Local clustering 0.644 ± 0.002 0.589 ± 0.006 Components 1 1 Giant component 910 910 Assortativity 0.576 ± 0.116 0.501 ± 0.115 Node homophily 0.612 ± 0.011 0.603 ± 0.011 Edge homophily 0.612 ± 0.010 0.603 ± 0.011 Transitivity 0.641 ± 0.004 0.586 ± 0.007 Triangle density (1.262 × 10−2 ) ± (1.232 × 10−4 ) (1.142 × 10−2 ) ± (1.594 × 10−4 )

n = 1657

Metric

Original

Bootstrap

Features 12 12 Classes 7 7 Nodes 1657 1657 Edges (1.926 × 105 ) ± 555.421 (1.919 × 105 ) ± 563.833 Average degree 232.496 ± 0.670 231.675 ± 0.681 Degree std. 15.500 ± 3.951 16.232 ± 3.744 Density (1.404 × 10−1 ) ± (4.048 × 10−4 ) (1.399 × 10−1 ) ± (4.110 × 10−4 ) Local clustering 0.644 ± 0.002 0.613 ± 0.004 Components 1 1 Giant component 1657 1657 Assortativity 0.575 ± 0.138 0.520 ± 0.137 Node homophily 0.607 ± 0.008 0.603 ± 0.007 Edge homophily 0.607 ± 0.008 0.602 ± 0.007 Transitivity 0.642 ± 0.003 0.612 ± 0.004 Triangle density (1.266 × 10−2 ) ± (1.082 × 10−4 ) (1.200 × 10−2 ) ± (1.083 × 10−4 )

n = 3017

Metric

Original

Bootstrap

Features 12 12 Classes 7 7 Nodes 3017 3017 Edges (6.388 × 105 ) ± 915.115 (6.375 × 105 ) ± 954.026 Average degree 423.445 ± 0.607 422.636 ± 0.632 Degree std. 23.506 ± 4.586 24.242 ± 4.521 Density (1.404 × 10−1 ) ± (2.011 × 10−4 ) (1.401 × 10−1 ) ± (2.097 × 10−4 ) Local clustering 0.644 ± 0.003 0.627 ± 0.003 Components 1 1 Giant component 3017 3017 Assortativity 0.638 ± 0.079 0.594 ± 0.086 Node homophily 0.612 ± 0.006 0.610 ± 0.006 Edge homophily 0.611 ± 0.006 0.609 ± 0.006 Transitivity 0.642 ± 0.003 0.626 ± 0.003 Triangle density (1.266 × 10−2 ) ± (7.382 × 10−5 ) (1.231 × 10−2 ) ± (7.212 × 10−5 )

n = 5493

Metric

Original

Bootstrap

Features 12 12 Classes 7 7 Nodes 5493 5493 Edges (2.118 × 106 ) ± (2.087 × 103 ) (2.116 × 106 ) ± (2.135 × 103 ) Average degree 771.060 ± 0.760 770.270 ± 0.777 Degree std. 37.061 ± 6.232 37.786 ± 6.088 Density (1.404 × 10−1 ) ± (1.384 × 10−4 ) (1.403 × 10−1 ) ± (1.415 × 10−4 ) Local clustering 0.644 ± 0.002 0.634 ± 0.002 Components 1 1 Giant component 5493 5493

22

Preprint

Assortativity Node homophily Edge homophily Transitivity Triangle density

0.690 ± 0.052 0.658 ± 0.059 0.616 ± 0.004 0.615 ± 0.004 0.616 ± 0.004 0.615 ± 0.004 0.642 ± 0.003 0.633 ± 0.002 (1.268 × 10−2 ) ± (5.112 × 10−5 ) (1.247 × 10−2 ) ± (3.925 × 10−5 )

n = 10000

Metric

Original

Bootstrap

Features 12 12 Classes 7 7 Nodes 10000 10000 Edges (7.019 × 106 ) ± (3.921 × 103 ) (7.015 × 106 ) ± (3.931 × 103 ) Average degree 1403.808 ± 0.784 1403.021 ± 0.786 Degree std. 59.618 ± 7.229 60.364 ± 7.116 Density (1.404 × 10−1 ) ± (7.843 × 10−5 ) (1.403 × 10−1 ) ± (7.863 × 10−5 ) Local clustering 0.644 ± 0.003 0.638 ± 0.001 Components 1 1 Giant component 10000 10000 Assortativity 0.725 ± 0.027 0.703 ± 0.029 Node homophily 0.618 ± 0.004 0.617 ± 0.004 Edge homophily 0.617 ± 0.004 0.617 ± 0.004 Transitivity 0.641 ± 0.002 0.637 ± 0.001 Triangle density (1.266 × 10−2 ) ± (3.880 × 10−5 ) (1.257 × 10−2 ) ± (2.195 × 10−5 )

Table 5: Original and bootstrap graph statistics for OOD datasets. Values are bootstrap means ± standard deviations across 25 bootstrap replicates. CoraML Metric

Original

PubMed

Bootstrap

Original

Bootstrap

Features 2879 2879 500 500 Classes 7 7 3 3 Nodes 2995 2995 19717 19717 Edges 8158 9802.200 ± 82.619 44324 60935.400 ± 243.491 Average degree 5.450 6.546 ± 0.055 4.500 6.181 ± 0.025 Degree std. 8.240 7.458 ± 0.132 7.430 8.509 ± 0.049 Density 1.820 × 10−3 (2.186 × 10−3 ) ± (1.843 × 10−5 ) 2.280 × 10−4 (3.135 × 10−4 ) ± (1.253 × 10−6 ) Local clustering 0.285 0.062 ± 0.004 0.061 0.027 ± 0.003 Components 61 66.360 ± 6.557 1 1278.800 ± 37.791 Giant component 2810 2928.680 ± 6.638 19717 18415.600 ± 38.176 Assortativity −0.072 −0.062 ± 0.004 −0.044 −0.038 ± 0.005 Node homophily 0.810 0.560 ± 0.005 0.792 0.626 ± 0.002 Edge homophily 0.789 0.595 ± 0.005 0.802 0.696 ± 0.002 Transitivity 0.116 0.046 ± 0.002 0.054 0.025 ± 0.001 Triangle density 1.190 × 10−6 (4.712 × 10−7 ) ± (1.986 × 10−8 ) 9.840 × 10−9 (6.590 × 10−9 ) ± (2.318 × 10−10 )

CiteSeer Metric Features Classes Nodes Edges Average degree Degree std. Density Local clustering Components

Original

AmazonComputers

Bootstrap

Original

Bootstrap

3703 3703 767 767 6 6 10 10 3327 3327 13752 13752 4552 5887.080 ± 97.053 245861 268828.640 ± 434.954 2.740 3.539 ± 0.058 35.800 39.097 ± 0.063 3.380 4.133 ± 0.092 70.300 66.104 ± 0.153 8.230 × 10−4 (1.064 × 10−3 ) ± (1.754 × 10−5 ) 2.600 × 10−3 (2.843 × 10−3 ) ± (4.600 × 10−6 ) 0.150 0.019 ± 0.002 0.362 0.190 ± 0.003 438 362.360 ± 24.088 314 9.640 ± 3.187

23

Preprint

Giant component 2120 2931.480 ± 28.849 13381 13743.360 ± 3.187 Assortativity 0.048 0.041 ± 0.013 −0.057 −0.052 ± 0.001 Node homophily 0.706 0.333 ± 0.005 0.785 0.733 ± 0.001 Edge homophily 0.736 0.447 ± 0.005 0.777 0.746 ± 0.001 Transitivity 0.131 0.036 ± 0.002 0.108 0.090 ± 0.001 Triangle density 1.910 × 10−7 (8.483 × 10−8 ) ± (7.211 × 10−9 ) 3.550 × 10−6 (2.790 × 10−6 ) ± (3.004 × 10−8 )

AmazonPhotos Metric

Original

CoauthorCS

Bootstrap

Original

Bootstrap

Features 745 745 6805 6805 Classes 8 8 15 15 Nodes 7650 7650 18333 18333 Edges 119081 133971.160 ± 265.568 81894 91787.760 ± 266.237 Average degree 31.100 35.025 ± 0.069 8.930 10.013 ± 0.029 Degree std. 47.300 45.657 ± 0.125 9.110 8.149 ± 0.043 Density 4.070 × 10−3 (4.579 × 10−3 ) ± (9.077 × 10−6 ) 4.870 × 10−4 (5.462 × 10−4 ) ± (1.584 × 10−6 ) Local clustering 0.406 0.254 ± 0.003 0.356 0.056 ± 0.002 Components 136 6.400 ± 2.273 1 55.480 ± 7.434 Giant component 7487 7644.600 ± 2.273 18333 18278.240 ± 7.683 Assortativity −0.045 −0.031 ± 0.001 0.113 0.088 ± 0.004 Node homophily 0.836 0.782 ± 0.001 0.832 0.638 ± 0.002 Edge homophily 0.827 0.794 ± 0.001 0.808 0.665 ± 0.001 Transitivity 0.178 0.156 ± 0.001 0.185 0.062 ± 0.001 Triangle density 9.650 × 10−6 (8.917 × 10−6 ) ± (8.917 × 10−8 ) 8.470 × 10−8 (2.901 × 10−8 ) ± (5.275 × 10−10 )

CoauthorPhysics Metric

Original

OGBN-ArXiv

Bootstrap

Original

Bootstrap

Features 8415 8415 128 128 Classes 5 5 40 40 Nodes 34493 34493 169343 169343 Edges 247962 266575.000 ± 462.087 1.158 × 106 (1.902 × 106 ) ± (1.061 × 103 ) Average degree 14.400 15.457 ± 0.027 13.700 22.469 ± 0.013 Degree std. 15.600 13.170 ± 0.042 68.600 78.516 ± 0.117 Density 4.170 × 10−4 (4.481 × 10−4 ) ± (7.768 × 10−7 ) 8.070 × 10−5 (1.327 × 10−4 ) ± (7.403 × 10−8 ) Local clustering 0.373 0.076 ± 0.001 0.235 0.060 ± 0.002 Components 1 28.000 ± 4.933 1 1123.560 ± 28.833 Giant component 34493 34465.960 ± 4.945 169343 168214.880 ± 29.359 Assortativity 0.201 0.213 ± 0.003 −0.043 −0.056 ± 0.000 Node homophily 0.915 0.811 ± 0.001 0.635 0.429 ± 0.000 Edge homophily 0.931 0.862 ± 0.001 0.654 0.435 ± 0.000 Transitivity 0.189 0.073 ± 0.001 0.016 0.008 ± 0.000 Triangle density 6.900 × 10−8 (2.421 × 10−8 ) ± (3.094 × 10−10 ) 2.740 × 10−9 (1.893 × 10−9 ) ± (5.433 × 10−11 )

D

M ODEL A RCHITECTURES AND PARAMETERS

D.1

G RAPH EDL M ODELS

For the graph EDL baselines, we consider S-BGCN-K and S-BGCN-T-K (Zhao et al., 2020), GPN (Stadler et al., 2021), GPN-GDEVI and GPN-GDLAT (Hart et al., 2023), GPN-LOP (Damke & Hüllermeier, 2024a), and CUQ-GCN, CUQ-GAT, and CUQ-APPNP (Damke & Hüllermeier, 2024b). Unless otherwise specified, we use the same hyperparameters across the graphon information-growth experiments, while for the OOD benchmarks we use the dataset-specific configurations suggested in the original implementations. GPN, GPN-GD, GPN-LOP, CUQ-GNN. GPN, all GPN-GD variants, GPN-LOP, and all CUQGNN variants use a learning rate of 0.01 across all datasets and 10 radial-flow layers for density estimation. For GPN, all GPN-GD variants, GPN-LOP, and CUQ-APPNP, APPNP propagation uses K = 10. CUQ-GCN, CUQ-GAT, and CUQ-APPNP differ only in the graph convolution used before 24

Preprint

Table 6: Hyperparameters for GPN, GPN-LOP, and CUQ-GNN. Dataset

Hidden

Latent

Layers

Dropout

APPNP α

Entropy reg. −3

Weight decay

Graphons

64

16

2

0.50

0.10

10

10−3

CoraML CiteSeer PubMed AmazonComputers AmazonPhotos CoauthorCS CoauthorPhysics OGBN-ArXiv

64 64 64 64 64 64 64 256

16 16 16 10 10 16 16 16

2 2 2 2 2 2 2 3

0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.25

0.10 0.10 0.10 0.20 0.20 0.10 0.10 0.20

10−3 10−3 10−3 10−5 10−5 10−3 10−3 10−3

10−3 10−3 10−3 5 × 10−4 5 × 10−4 10−3 10−3 0

Table 7: Hyperparameters for GPN-GD. Dataset

Entropy reg.

Distance reg.

Activation

Graphons

0

10−4

GELU

CoraML CiteSeer PubMed AmazonComputers AmazonPhotos CoauthorCS CoauthorPhysics OGBN-ArXiv

−4

0 10−4 10−5 10−5 10−5 0 10−4 10−5

10 10−9.5 10−4 10−4 10−11 10−6 10−4.5 10−8

GELU LogSigmoid ReLU ReLU ReLU ReLU LogSigmoid ReLU

density estimation; CUQ-GAT uses one attention head per layer, negative slope 0.2, and no attentioncoefficient dropout. GPN-GD uses the same hyperparameters as GPN, and additionally tunes the graph distance regularization weight and activation function, using the same hyperparameters for both variants. Graphon and OOD dataset-specific hyperparameters are reported in Tables 6 and 7. S-BGCN. We evaluate S-BGCN-K and S-BGCN-T-K. We use a learning rate of 0.01 across datasets. S-BGCN-K uses λ1 to weight the KL regularization term, while S-BGCN-T-K additionally uses λ2 to weight the teacher regularization term. The graphon and OOD dataset-specific hyperparameters are reported in Table 8. Uncertainty estimates are computed using 100 MC dropout samples. D.2

G-E NS AND GB-E NS

Unless otherwise specified, G-Ens and GB-Ens use the same hyperparameters for the graphons, while for the OOD benchmarks we perform the same dataset-specific hyperparameter search, selecting model and training hyperparameters by validation accuracy; GB-Ens additionally applies graph bootstrapping. APPNP backbone. For the graphon experiments, we use an APPNP architecture (Gasteiger et al., 2019) consisting of a two-layer MLP with hidden dimension 64, dropout 0.3, followed by APPNP propagation with K = 10 iterations and teleport probability α = 0.1. We use a learning rate of 0.01 and weight decay 5 × 10−4 . For the OOD datasets, we fix the MLP to two layers and K = 10, and search over hidden dimensions in {64, 128, 256}; dropout rates in {0.3, 0.5, 0.6}; teleport probabilities in {0.05, 0.1, 0.2}; learning rates in {0.005, 0.01, 0.02}; and weight decay in {10−5 , 5 × 10−4 , 5 × 10−3 }. GAT backbone. For the graphon experiments, we use a two-layer GAT (Veličković et al., 2018) with total hidden dimension 64, 8 attention heads, feature and attention-coefficient dropout rates of 0.3 and 0.2, respectively, attention negative slope of 0.2, learning rate of 0.005, and weight decay of 5 × 10−4 . For the OOD datasets, we search over 2 or 3 GAT layers; total hidden dimensions in {64, 128, 256}; 4 or 8 attention heads; feature dropout rates in {0.2, 0.3, 0.5, 0.6}; attentioncoefficient dropout rates in {0.3, 0.5, 0.6}; learning rates in {0.005, 0.01}; and weight decay in {10−4 , 10−3 }. The attention negative slope is fixed to 0.2. GCN backbone. For the graphon experiments, we use a two-layer GCN (Kipf & Welling, 2017) with hidden dimension 64, dropout of 0.3, learning rate of 0.01, and weight decay of 5 × 10−4 . For 25

Preprint

Table 8: Hyperparameters for S-BGCN-K and S-BGCN-T-K. Dataset

Hidden

Dropout

L2 reg. −4

λ1 −3

λ2

Graphons

16

0.50

5 × 10

10

1

CoraML CiteSeer PubMed AmazonComputers AmazonPhotos CoauthorCS CoauthorPhysics OGBN-ArXiv

16 16 16 64 64 64 64 64

0.50 0.50 0.50 0.20 0.20 0.10 0.10 0.50

5 × 10−4 5 × 10−4 5 × 10−4 10−4 10−4 10−3 10−3 10−4

10−3 10−3 10−3 10−3 10−3 10−3 10−3 10−4

1 1 1 1 1 1 1 1

(b) Aleatoric uncertainty across λ at N = 10,000.

(a) Epistemic uncertainty under information growth.

Figure 4: Uncertainty estimates of EDL models on the SBM. the OOD datasets, we search over 2 or 3 GCN layers; hidden dimensions in {64, 128, 256}; dropout rates in {0.2, 0.4, 0.5}; learning rates in {0.01, 0.02, 0.03}; and weight decay in {5 × 10−5 , 5 × 10−4 , 5 × 10−3 }.

E

A DDITIONAL E XPERIMENTAL R ESULTS

RQ2: Graph EDL models are inconsistent epistemic predictors. The SBM results in Figures 4a and 4b reproduce the patterns observed for the exponential-decay graphon: EDL methods fail to exhibit consistent EU concentration, while AU remains sensitive to the regularization parameter λ. Similar differences in EU magnitude across methods persist on real-world datasets, as shown in Table 9. For completeness, Table 10 reports predictive accuracy averaged over the two graphon sequences; GPN variants share a common parameterization, as in their original formulations, resulting in lower accuracy for some variants, particularly GPN-GDEVI . RQ3: GB-Ens is a family of candidate consistent epistemic predictors. Complementing the results reported in the main text, Figure 5a shows that on the SBM, GB-Ens EU decreases from N = 500 to N = 10, 000 by 92% for APPNP and 94% for GCN, while GAT exhibits a weaker, non-monotonic EU reduction of 34%, reaching a maximum of 42% at an intermediate graph size. Figure 5b further decomposes EU into seed and bootstrap contributions of similar magnitude, both decreasing with increasing information. For GAT, the non-monotonicity is driven primarily by the seed component, whereas the bootstrap component follows a more consistently decreasing trajectory. Regarding aleatoric uncertainty, Figure 6b shows that GB-Ens AU decreases and eventually stabilizes, with all three backbones approaching similar plateaus. Figure 6a shows that G-Ens similarly exhibit no consistent EU contraction on the SBM, while Figure 6b shows strongly backbone-dependent AU trajectories. For completeness, Table 12 reports predictive accuracy averaged over the two graphon information-growth sequences for G-Ens and GB-Ens. For the true-DGP resampling diagnostic, we compute normalized node-wise Wasserstein-1 distances on a random 10% subset of test nodes and average them across nodes and 20 projective26

Preprint

Table 9: Mean epistemic uncertainty estimated by EDL methods on OOD datasets. Method CUQ-APPNP CUQ-GAT CUQ-GCN GPN GPN-GDEVI GPN-GDLAT GPN-LOP S-BGCN-K S-BGCN-T-K

CoraML

CiteSeer

−4

−4

4.42 × 10 1.87 × 10−4 7.97 × 10−4 3.65 × 10−4 8.89 × 10−2 2.21 × 10−4 3.15 × 10−1 2.69 × 10−2 4.30 × 10−2

6.64 × 10 4.07 × 10−4 7.90 × 10−4 6.21 × 10−4 5.01 × 10−3 4.77 × 10−3 2.09 × 10−1 7.88 × 10−2 6.32 × 10−2

Method

PubMed AmazonPhotos AmazonComputers 4.80 × 10−5 2.60 × 10−5 1.79 × 10−4 5.00 × 10−6 4.44 × 10−2 1.93 × 10−6 1.81 × 10−1 4.47 × 10−2 4.38 × 10−2

8.00 × 10−6 4.20 × 10−5 2.20 × 10−4 1.00 × 10−5 1.76 × 10−5 8.05 × 10−6 2.46 × 10−1 2.66 × 10−3 4.36 × 10−3

CoauthorCS CoauthorPhysics

CUQ-APPNP CUQ-GAT CUQ-GCN GPN GPN-GDEVI GPN-GDLAT GPN-LOP S-BGCN-K S-BGCN-T-K

−4

1.09 × 10 5.79 × 10−2 3.48 × 10−2 4.00 × 10−6 1.02 × 10−2 1.02 × 10−6 5.33 × 10−1 1.62 × 10−3 5.62 × 10−3

−4

1.44 × 10 2.10 × 10−5 2.08 × 10−4 1.10 × 10−5 5.31 × 10−2 2.72 × 10−5 2.65 × 10−1 4.35 × 10−3 7.06 × 10−3

4.00 × 10−6 1.66 × 10−4 5.65 × 10−4 7.00 × 10−6 1.38 × 10−1 3.32 × 10−6 3.23 × 10−1 1.71 × 10−3 2.85 × 10−3

OGBN-ArXiv 1.20 × 10−2 4.10 × 10−1 2.40 × 10−1 5.44 × 10−3 2.05 × 10−3 1.05 × 10−5 OOM 5.33 × 10−2 5.68 × 10−2

Table 10: EDL test accuracy averaged across each graphon sequence. DGP

CUQ-APPNP CUQ-GAT CUQ-GCN

Exp.-decay SBM

0.940 0.822

0.910 0.832

0.848 0.800

GPN 0.555 0.786

GPN-GDEVI GPN-GDLAT GPN-LOP S-BGCN-K S-BGCN-T-K 0.158 0.159

0.761 0.821

0.793 0.834

0.904 0.823

0.906 0.823

√ sequence replicates, using the Euclidean diameter 2 of the probability simplex for normalization. Table 11 shows that, on the SBM, distances remain relatively low for GCN (0.12–0.14) and APPNP (0.20–0.34), whereas GAT exhibits larger distances ranging from 0.24 to 0.45.

F

O UT-O F -D ISTRIBUTION D ETECTION

We report the full OOD detection results for the EDL baselines and, for completeness, extend the evaluation to G-Ens and GB-Ens in Tables 13 to 20, for which we similarly find that the most effective uncertainty type depends on the model and OOD protocol. Bold highlights the best-performing uncertainty type(s) for each model and shift. GB-Ens bootstrap and original dataset statistics are reported in Table 5. The observed discrepancies in graph statistics indicate that the local bootstrap does not preserve all topological properties of the observed graphs, limiting its fidelity as an approximation of graph observation variability; nevertheless, in these downstream OOD experiments uncertainty serves only as a detection score, and this structural degradation does not automatically translate into degraded OOD detection performance. We follow the leave-out-classes (LOC) and feature isolation (FI) protocols of Stadler et al. (2021); Damke & Hüllermeier (2024a;b). On OGBN-ArXiv, CUQ-GAT and CUQ-GCN achieve very low accuracy (≈ 0.051–0.073) using the hyperparameters recommended in the original paper (Damke & Hüllermeier, 2024b), while GPNLOP exceeds the available 80 GB of NVIDIA A100 GPU memory; we therefore do not report results for these models. Datasets. We use CoraML (McCallum et al., 2000), CiteSeer (Giles et al., 1998), PubMed (Namata et al., 2012), CoauthorCS, CoauthorPhysics, AmazonComputers, AmazonPhotos (Shchur et al., 2018), and OGBN-ArXiv (Hu et al., 2020). Leave-out-classes (LOC). Following Stadler et al. (2021), we partition the label space Y into retained classes YID and the same left-out classes YOOD used in their LOC setup. Nodes from YOOD are excluded from training and validation but remain in G, preserving the transductive setting. For GB-Ens, the same class partition is fixed across bootstrap replicates, with each ensemble member evaluated on its corresponding bootstrap graph. 27

Preprint

(a) Total epistemic uncertainty.

(b) Bootstrap and training-seed decomposition.

Figure 5: GB-Ens mean epistemic uncertainty on the SBM.

(a) Epistemic uncertainty of G-Ens.

(b) Aleatoric uncertainty of GB-Ens and G-Ens.

Figure 6: Ensemble mean uncertainties on the SBM.

Feature isolation (FI). We sample niso = 100 test nodes and, for each node i, construct a copy of G in which only Xi is replaced by coordinate-wise Gaussian N (0, σ 2 ID ) or Bernoulli Bernoulli(0.5) noise. For GB-Ens, the same nodes and feature perturbations are used across bootstrap replicates. Each perturbed node is evaluated in its corresponding graph as OOD; for GB-Ens, this evaluation is performed separately on each member’s bootstrap graph, while the unperturbed test set T (te) forms the ID set. Metrics. Using total, aleatoric, and epistemic uncertainty as OOD scores, we report AUROC, together with ID accuracy and FI OOD accuracy.

G

C OMPUTATIONAL C OMPLEXITY

Graph EDL methods can themselves incur substantial computational costs, with different methods trading off preprocessing, training, inference, and memory requirements. Ensemble-based methods require repeated model fitting, but retain manageable per-model computation and peak memory and are naturally parallelizable. GPN and CUQ-GCN admit O(N +M ) implementations, whereas GPNLOP and S-BGCN-K can incur O(N 2 ) computation due to dense propagation and pairwise GKDE prior construction, respectively. For GCN-based ensembles, training costs O(N + M ) per member; GB-Ens additionally requires bootstrap generation, whose cost depends on the k-NN construction and can reach O(N 2 ) for general similarity search, although cheaper alternatives are available, such as the open Jaccard similarity metric used in our experiments. Bootstrap generation is repeated for each bootstrap sample. Across ensemble members, training cost scales linearly for both GB-Ens and G-Ens but is naturally parallelizable. Moreover, processing members independently and accumulating uncertainty statistics online keeps peak memory at O(N +M ), comparable to GPN, CUQ-GNN, and S-BGCN-K, whereas GPN-LOP can require O(N 2 ) memory due to dense propagation. 28

Preprint

Table 11: Mean normalized Wasserstein distances between GB-Ens- and true-DGP-induced secondorder distributions. Graph size Graphon

Backbone

500

910

1657

3017

5493

10000

Exp.-decay

APPNP GAT GCN

0.2991 0.4482 0.2053

0.2931 0.5102 0.2113

0.2870 0.5505 0.2119

0.2886 0.5790 0.2071

0.2841 0.5946 0.2059

0.2826 0.6156 0.2050

SBM

APPNP GAT GCN

0.2049 0.2440 0.1277

0.2185 0.2998 0.1194

0.3146 0.3684 0.1437

0.3483 0.4130 0.1527

0.3471 0.4365 0.1524

0.3431 0.4506 0.1480

Table 12: G-Ens and GB-Ens test accuracy averaged across each graphon sequence. DGP Exp.-decay SBM

APPNP G-Ens

GAT G-Ens

GCN G-Ens

APPNP GB-Ens

GAT GB-Ens

GCN GB-Ens

0.808 0.704

0.731 0.772

0.902 0.814

0.946 0.816

0.931 0.830

0.932 0.830

Tables 21, 22 and 23 complement the asymptotic analysis with empirical measurements on CoraML, CoauthorPhysics and OGBN-ArXiv, obtained on a dedicated NVIDIA A100 64 GB GPU. GB-Ens uses 100 models in the 25 × 4 bootstrap–seed decomposition, while G-Ens uses 10 randomly initialized models. Preprocessing time reports the total preprocessing cost required by each method, including generation of all bootstrap samples for GB-Ens. Epoch time is reported per model and training epoch, while inference time reports the total cost of producing one uncertainty estimate, aggregating the 100 forward passes required by GB-Ens and S-BGCN variants and the 10 forward passes required by G-Ens. Peak inference memory is measured when processing ensemble members sequentially. GB-Ens therefore trades increased total preprocessing, training, and inference costs for moderate peak memory requirements: graph bootstrapping becomes particularly costly on larger graphs, while its 100 members can be trained independently and in parallel, and sequential inference limits peak memory. This trade-off differs across EDL baselines: some avoid repeated model fitting and inference, whereas preprocessing-heavy methods such as S-BGCN-K incur comparable preprocessing costs on OGBN-ArXiv, and dense propagation makes GPN-LOP considerably more expensive on CoauthorPhysics and infeasible on OGBN-ArXiv under the available GPU memory.

29

Preprint

Table 13: OOD detection on CoraML measured by AUROC. Model

ID ACC

LOC

FI Gaussian

FI Bernoulli

TU

AU

EU

OOD ACC

TU

AU

EU

OOD ACC

TU

AU

EU

CUQ-APPNP CUQ-GAT CUQ-GCN GPN GPN-GDEVI GPN-GDLAT LOP-GPN S-BGCN-K S-BGCN-T-K

0.790 0.764 0.712 0.802 0.782 0.790 0.795 0.513 0.786

0.761 0.697 0.715 0.836 0.892 0.832 0.837 0.865 0.885

0.761 0.697 0.715 0.836 0.862 0.832 0.865 0.864 0.890

0.665 0.562 0.616 0.837 0.879 0.824 0.507 0.462 0.368

0.080 0.070 0.110 0.790 0.760 0.790 0.840 0.260 0.240

1.000 0.996 1.000 0.559 0.554 0.555 0.726 0.028 0.169

0.992 0.996 0.998 0.559 0.551 0.555 0.641 0.002 0.009

1.000 1.000 1.000 0.583 0.545 0.595 0.836 1.000 1.000

0.760 0.740 0.700 0.800 0.760 0.790 0.810 0.500 0.780

0.603 0.544 0.574 0.578 0.556 0.579 0.668 0.571 0.633

0.603 0.544 0.574 0.578 0.554 0.579 0.644 0.579 0.653

0.596 0.537 0.531 0.577 0.544 0.585 0.673 0.423 0.362

G-EnsAPPNP G-EnsGAT G-EnsGCN

0.814 0.814 0.816

0.835 0.850 0.848

0.831 0.857 0.847

0.789 0.621 0.810

0.240 0.200 0.200

0.272 0.217 0.226

0.072 0.002 0.080

0.668 0.863 0.540

0.725 0.735 0.810

0.667 0.633 0.670

0.671 0.644 0.671

0.532 0.469 0.614

GB-EnsAPPNP GB-EnsGAT GB-EnsGCN

0.794 0.770 0.687

0.807 0.797 0.766

0.799 0.812 0.758

0.726 0.625 0.683

0.240 0.210 0.280

0.304 0.389 0.533

0.025 0.002 0.070

0.825 0.989 0.983

0.650 0.680 0.730

0.728 0.658 0.603

0.734 0.679 0.626

0.499 0.520 0.479

Table 14: OOD detection on CiteSeer measured by AUROC. Model

ID ACC

LOC

FI Gaussian

FI Bernoulli

TU

AU

EU

OOD ACC

TU

AU

EU

OOD ACC

TU

AU

EU

CUQ-APPNP CUQ-GAT CUQ-GCN GPN GPN-GDEVI GPN-GDLAT LOP-GPN S-BGCN-K S-BGCN-T-K

0.647 0.613 0.557 0.678 0.688 0.687 0.680 0.699 0.723

0.751 0.768 0.593 0.741 0.807 0.805 0.748 0.739 0.861

0.751 0.768 0.594 0.741 0.807 0.805 0.724 0.737 0.876

0.616 0.679 0.571 0.615 0.774 0.773 0.596 0.413 0.255

0.080 0.100 0.110 0.690 0.660 0.670 0.640 0.280 0.260

1.000 0.941 0.999 0.489 0.486 0.486 0.746 0.159 0.230

0.711 0.701 0.535 0.487 0.482 0.482 0.596 0.002 0.005

1.000 0.989 1.000 0.702 0.599 0.598 0.874 1.000 1.000

0.570 0.560 0.480 0.630 0.670 0.680 0.620 0.720 0.740

0.640 0.597 0.576 0.599 0.568 0.568 0.700 0.683 0.704

0.640 0.597 0.576 0.599 0.568 0.568 0.620 0.708 0.731

0.591 0.597 0.479 0.569 0.558 0.557 0.713 0.415 0.393

G-EnsAPPNP G-EnsGAT G-EnsGCN

0.716 0.715 0.706

0.805 0.799 0.829

0.804 0.793 0.829

0.545 0.565 0.674

0.185 0.180 0.210

0.099 0.121 0.117

0.002 0.005 0.016

0.767 0.862 0.581

0.540 0.535 0.720

0.832 0.684 0.701

0.839 0.694 0.702

0.238 0.458 0.461

GB-EnsAPPNP GB-EnsGAT GB-EnsGCN

0.676 0.666 0.667

0.771 0.802 0.789

0.771 0.788 0.794

0.399 0.548 0.355

0.200 0.210 0.160

0.037 0.075 0.036

0.000 0.000 0.000

0.777 1.000 0.970

0.370 0.360 0.410

0.892 0.764 0.771

0.902 0.781 0.812

0.125 0.418 0.154

Table 15: OOD detection on PubMed measured by AUROC. Model

ID ACC

LOC

FI Gaussian

FI Bernoulli

TU

AU

EU

OOD ACC

TU

AU

EU

OOD ACC

TU

AU

EU

CUQ-APPNP CUQ-GAT CUQ-GCN GPN GPN-GDEVI GPN-GDLAT LOP-GPN S-BGCN-K S-BGCN-T-K

0.852 0.835 0.845 0.837 0.827 0.842 0.834 0.848 0.850

0.693 0.709 0.717 0.730 0.800 0.724 0.748 0.625 0.607

0.693 0.709 0.717 0.730 0.771 0.724 0.781 0.627 0.611

0.643 0.618 0.591 0.769 0.857 0.764 0.651 0.500 0.507

0.300 0.670 0.340 0.820 0.820 0.810 0.780 0.400 0.400

0.975 0.660 0.936 0.560 0.578 0.559 0.696 0.342 0.447

0.942 0.659 0.858 0.560 0.569 0.559 0.588 0.001 0.006

0.994 0.684 0.945 0.642 0.621 0.658 0.767 1.000 1.000

0.770 0.780 0.770 0.820 0.820 0.800 0.770 0.770 0.790

0.652 0.586 0.613 0.593 0.585 0.596 0.578 0.646 0.654

0.652 0.586 0.613 0.593 0.579 0.596 0.446 0.679 0.677

0.616 0.540 0.554 0.638 0.615 0.640 0.689 0.288 0.308

G-EnsAPPNP G-EnsGAT G-EnsGCN

0.867 0.845 0.854

0.663 0.698 0.728

0.664 0.697 0.728

0.641 0.657 0.733

0.385 0.365 0.400

0.138 0.397 0.192

0.028 0.034 0.083

0.463 0.679 0.375

0.730 0.765 0.820

0.781 0.648 0.696

0.780 0.652 0.696

0.540 0.560 0.604

GB-EnsAPPNP GB-EnsGAT GB-EnsGCN

0.857 0.845 0.829

0.647 0.676 0.618

0.648 0.675 0.626

0.600 0.657 0.568

0.380 0.320 0.400

0.175 0.573 0.261

0.025 0.029 0.060

0.536 0.962 0.780

0.640 0.730 0.720

0.775 0.661 0.641

0.773 0.668 0.649

0.551 0.576 0.514

30

Preprint

Table 16: OOD detection on Amazon Computers measured by AUROC. Model

ID ACC

LOC

FI Gaussian

FI Bernoulli

TU

AU

EU

OOD ACC

TU

AU

EU

OOD ACC

TU

AU

EU

CUQ-APPNP CUQ-GAT CUQ-GCN GPN GPN-GDEVI GPN-GDLAT LOP-GPN S-BGCN-K S-BGCN-T-K

0.838 0.875 0.831 0.810 0.381 0.832 0.792 0.396 0.626

0.717 0.773 0.632 0.749 0.408 0.768 0.825 0.752 0.785

0.717 0.773 0.632 0.749 0.382 0.768 0.876 0.753 0.787

0.589 0.719 0.538 0.762 0.511 0.607 0.507 0.593 0.581

0.010 0.170 0.210 0.720 0.910 0.900 0.720 0.400 0.320

1.000 0.908 0.896 0.551 0.515 0.515 0.891 0.235 0.140

1.000 0.907 0.895 0.551 0.515 0.515 0.818 0.164 0.078

1.000 0.909 0.942 0.562 0.582 0.580 0.871 0.960 0.980

0.720 0.820 0.790 0.730 0.430 0.800 0.740 0.440 0.660

0.698 0.503 0.526 0.554 0.497 0.567 0.713 0.491 0.507

0.698 0.503 0.526 0.554 0.505 0.567 0.637 0.491 0.506

0.543 0.484 0.494 0.560 0.482 0.583 0.717 0.509 0.502

G-EnsAPPNP G-EnsGAT G-EnsGCN

0.875 0.852 0.854

0.773 0.810 0.727

0.774 0.817 0.722

0.751 0.760 0.781

0.140 0.170 0.370

0.359 0.866 0.501

0.064 0.120 0.375

0.580 0.980 0.759

0.785 0.830 0.820

0.737 0.537 0.507

0.737 0.538 0.508

0.697 0.511 0.476

GB-EnsAPPNP GB-EnsGAT GB-EnsGCN

0.871 0.857 0.835

0.762 0.817 0.727

0.764 0.827 0.730

0.717 0.763 0.656

0.130 0.150 0.540

0.447 0.937 0.537

0.059 0.107 0.439

0.739 1.000 0.819

0.790 0.850 0.770

0.747 0.538 0.503

0.747 0.537 0.504

0.698 0.510 0.481

Table 17: OOD detection on Amazon Photos measured by AUROC. Model

ID ACC

LOC

FI Gaussian

FI Bernoulli

TU

AU

EU

OOD ACC

TU

AU

EU

OOD ACC

TU

AU

EU

CUQ-APPNP CUQ-GAT CUQ-GCN GPN GPN-GDEVI GPN-GDLAT LOP-GPN S-BGCN-K S-BGCN-T-K

0.901 0.915 0.912 0.900 0.900 0.899 0.892 0.446 0.717

0.720 0.842 0.802 0.835 0.812 0.810 0.865 0.629 0.664

0.721 0.842 0.802 0.835 0.812 0.810 0.897 0.630 0.665

0.694 0.823 0.738 0.892 0.855 0.855 0.569 0.359 0.361

0.100 0.220 0.130 0.910 0.410 0.790 0.880 0.250 0.210

1.000 0.927 0.948 0.522 0.712 0.561 0.763 0.126 0.196

0.999 0.927 0.947 0.522 0.719 0.561 0.683 0.071 0.084

1.000 0.936 0.953 0.568 0.689 0.583 0.951 0.976 0.997

0.800 0.870 0.900 0.910 0.910 0.900 0.870 0.360 0.640

0.693 0.510 0.503 0.552 0.563 0.554 0.679 0.520 0.551

0.693 0.510 0.503 0.552 0.563 0.554 0.584 0.522 0.553

0.612 0.497 0.474 0.565 0.573 0.579 0.848 0.477 0.488

G-EnsAPPNP G-EnsGAT G-EnsGCN

0.930 0.916 0.921

0.843 0.786 0.847

0.844 0.801 0.847

0.807 0.703 0.839

0.135 0.290 0.240

0.481 0.895 0.331

0.145 0.289 0.270

0.681 0.999 0.590

0.900 0.900 0.900

0.725 0.497 0.530

0.726 0.498 0.531

0.715 0.520 0.489

GB-EnsAPPNP GB-EnsGAT GB-EnsGCN

0.926 0.887 0.862

0.777 0.832 0.739

0.778 0.866 0.741

0.740 0.810 0.497

0.140 0.270 0.230

0.504 0.906 0.158

0.164 0.251 0.137

0.737 1.000 0.791

0.890 0.890 0.860

0.718 0.471 0.526

0.719 0.474 0.527

0.701 0.486 0.531

Table 18: OOD detection on Coauthor CS measured by AUROC. Model

ID ACC

LOC

FI Gaussian

FI Bernoulli

TU

AU

EU

OOD ACC

TU

AU

EU

OOD ACC

TU

AU

EU

CUQ-APPNP CUQ-GAT CUQ-GCN GPN GPN-GDEVI GPN-GDLAT LOP-GPN S-BGCN-K S-BGCN-T-K

0.910 0.787 0.797 0.884 0.872 0.885 0.886 0.350 0.709

0.770 0.676 0.730 0.755 0.771 0.716 0.706 0.659 0.642

0.770 0.678 0.730 0.755 0.760 0.716 0.883 0.660 0.643

0.741 0.639 0.658 0.931 0.919 0.928 0.149 0.551 0.543

0.060 0.580 0.110 0.860 0.840 0.880 0.880 0.240 0.190

1.000 0.663 0.979 0.531 0.522 0.541 0.678 0.148 0.144

1.000 0.645 0.940 0.531 0.522 0.541 0.629 0.112 0.090

1.000 0.663 0.979 0.557 0.539 0.515 0.723 0.924 0.994

0.830 0.820 0.770 0.860 0.840 0.880 0.870 0.440 0.730

0.553 0.492 0.538 0.537 0.524 0.545 0.620 0.465 0.542

0.553 0.492 0.541 0.537 0.524 0.545 0.626 0.465 0.542

0.507 0.452 0.519 0.550 0.538 0.556 0.588 0.517 0.488

G-EnsAPPNP G-EnsGAT G-EnsGCN

0.934 0.915 0.926

0.940 0.914 0.924

0.940 0.920 0.924

0.934 0.855 0.939

0.105 0.155 0.180

0.724 0.805 0.558

0.312 0.156 0.374

0.889 0.958 0.788

0.875 0.870 0.880

0.736 0.580 0.584

0.736 0.583 0.584

0.713 0.551 0.566

GB-EnsAPPNP GB-EnsGAT GB-EnsGCN

0.924 0.888 0.865

0.826 0.728 0.657

0.828 0.757 0.670

0.779 0.607 0.410

0.100 0.130 0.200

0.750 0.872 0.191

0.289 0.082 0.114

0.963 1.000 0.810

0.870 0.850 0.800

0.753 0.570 0.544

0.752 0.576 0.543

0.745 0.536 0.541

31

Preprint

Table 19: OOD detection on Coauthor Physics measured by AUROC. Model

ID ACC

LOC

FI Gaussian

FI Bernoulli

TU

AU

EU

OOD ACC

TU

AU

EU

OOD ACC

TU

AU

EU

CUQ-APPNP CUQ-GAT CUQ-GCN GPN GPN-GDEVI GPN-GDLAT LOP-GPN S-BGCN-K S-BGCN-T-K

0.948 0.945 0.944 0.938 0.934 0.926 0.931 0.863 0.944

0.861 0.848 0.826 0.876 0.912 0.902 0.832 0.905 0.885

0.861 0.848 0.826 0.876 0.897 0.902 0.877 0.905 0.885

0.814 0.784 0.782 0.957 0.957 0.961 0.698 0.814 0.826

0.240 0.260 0.300 0.900 0.920 0.920 0.890 0.430 0.360

1.000 0.998 0.992 0.562 0.613 0.547 0.751 0.284 0.400

0.999 0.996 0.992 0.562 0.609 0.547 0.702 0.197 0.290

1.000 1.000 0.992 0.607 0.643 0.581 0.767 0.959 0.965

0.920 0.930 0.900 0.900 0.920 0.920 0.870 0.820 0.960

0.594 0.487 0.524 0.609 0.618 0.561 0.701 0.593 0.601

0.594 0.487 0.524 0.609 0.615 0.561 0.712 0.593 0.601

0.544 0.417 0.474 0.600 0.641 0.578 0.634 0.568 0.581

G-EnsAPPNP G-EnsGAT G-EnsGCN

0.960 0.953 0.956

0.940 0.914 0.924

0.940 0.920 0.924

0.934 0.855 0.939

0.210 0.270 0.330

0.409 0.617 0.574

0.279 0.257 0.467

0.514 0.695 0.730

0.960 0.960 0.960

0.750 0.606 0.610

0.751 0.606 0.610

0.684 0.600 0.592

GB-EnsAPPNP GB-EnsGAT GB-EnsGCN

0.954 0.932 0.924

0.928 0.907 0.885

0.931 0.916 0.892

0.896 0.844 0.733

0.210 0.280 0.400

0.750 0.817 0.407

0.420 0.307 0.362

0.868 0.990 0.701

0.900 0.900 0.900

0.763 0.600 0.604

0.764 0.600 0.604

0.745 0.595 0.597

Table 20: OOD detection on OGBN-ArXiv measured by AUROC. Model

ID ACC

LOC

FI Gaussian

FI Bernoulli

TU

AU

EU

OOD ACC

TU

AU

EU

OOD ACC

TU

AU

EU

CUQ-APPNP CUQ-GAT CUQ-GCN GPN GPN-GDEVI GPN-GDLAT LOP-GPN S-BGCN-K S-BGCN-T-K

0.697 N/A N/A 0.696 0.675 0.701 OOM 0.622 0.645

0.685 0.395 0.523 0.706 0.690 0.689 OOM 0.647 0.637

0.685 0.405 0.516 0.705 0.690 0.689 OOM 0.648 0.639

0.662 0.387 0.523 0.747 0.730 0.753 OOM 0.605 0.590

0.390 N/A N/A 0.660 0.680 0.690 OOM 0.420 0.480

0.823 N/A N/A 0.540 0.534 0.548 OOM 0.540 0.600

0.823 N/A N/A 0.539 0.534 0.548 OOM 0.469 0.499

0.811 N/A N/A 0.604 0.601 0.597 OOM 0.775 0.792

0.680 N/A N/A 0.660 0.680 0.690 OOM 0.640 0.660

0.581 N/A N/A 0.540 0.533 0.548 OOM 0.591 0.586

0.578 N/A N/A 0.539 0.533 0.548 OOM 0.601 0.597

0.676 N/A N/A 0.604 0.601 0.597 OOM 0.438 0.450

G-EnsAPPNP G-EnsGAT G-EnsGCN

0.706 0.710 0.714

0.642 0.695 0.667

0.641 0.694 0.666

0.708 0.702 0.705

0.340 0.550 0.580

0.540 0.651 0.596

0.508 0.601 0.584

0.942 0.888 0.680

0.740 0.720 0.710

0.598 0.529 0.509

0.598 0.529 0.509

0.442 0.511 0.493

GB-EnsAPPNP GB-EnsGAT GB-EnsGCN

0.661 0.663 0.644

0.607 0.658 0.636

0.589 0.551 0.598

0.608 0.649 0.634

0.150 0.150 0.380

0.279 0.232 0.514

0.904 0.966 0.701

0.364 0.470 0.558

0.530 0.590 0.610

0.716 0.555 0.573

0.614 0.542 0.573

0.718 0.558 0.572

Table 21: Computational cost on CoraML. Model

Params

Models

Preproc. (s)

Epoch (ms)

Fwd

Infer. (ms)

Peak (MiB)

CUQ-APPNP CUQ-GAT CUQ-GCN GPN GPN-GDEVI GPN-GDLAT GPN-LOP S-BGCN-K S-BGCN-T-K

186,620 195,196 194,940 186,620 186,620 186,620 186,620 46,199 46,199

1 1 1 1 1 1 1 1 1

– – – – – – – 0.1 0.5

17.0 16.9 16.4 16.4 17.8 16.7 24.7 2.4 2.7

1 1 1 1 1 1 1 100 100

7.0 6.6 6.9 6.8 7.0 6.9 15.3 80.0 80.0

268 253 235 173 202 188 320 92 92

G-EnsAPPNP G-EnsGAT G-EnsGCN

184,775 184,917 184,775

10 10 10

– – –

3.5 3.3 2.1

10 10 10

17.0 13.0 9.0

55 64 177

GB-EnsAPPNP GB-EnsGAT GB-EnsGCN

184,775 184,917 184,775

100 100 100

32.5 32.5 32.5

3.6 3.3 2.1

100 100 100

170.0 140.0 100.0

167 176 175

32

Preprint

Table 22: Computational cost on CoauthorPhysics. Model

Params

Models

Preproc. (s)

Epoch (ms)

Fwd

Infer. (ms)

Peak (MiB)

CUQ-APPNP CUQ-GAT CUQ-GCN GPN GPN-GDEVI GPN-GDLAT GPN-LOP S-BGCN-K S-BGCN-T-K

540,564 549,140 548,884 540,564 540,564 540,564 540,564 538,949 538,949

1 1 1 1 1 1 1 1 1

– – – – – – – 18.4 20.5

46.6 36.4 34.9 32.2 32.3 31.9 1835.1 12.0 11.7

1 1 1 1 1 1 1 100 100

24.6 19.0 18.8 17.1 16.1 16.2 1824.7 620.0 620.0

2,886 2,760 2,633 2,127 2,127 2,249 28,643 2,540 2,545

G-EnsAPPNP G-EnsGAT G-EnsGCN

2,155,781 1,078,159 2,155,781

10 10 10

– – –

21.0 18.6 26.0

10 10 10

91.0 72.0 119.0

1,883 2,370 2,905

GB-EnsAPPNP GB-EnsGAT GB-EnsGCN

2,155,781 1,078,159 2,155,781

100 100 100

617.5 617.5 617.5

21.0 18.5 26.0

100 100 100

900.0 720.0 1180.0

1,858 2,370 2,905

Table 23: Computational cost on OGBN-ArXiv. Model

Params

Models

Preproc. (s)

Epoch (ms)

Fwd

Infer. (ms)

Peak (MiB)

CUQ-APPNP CUQ-GAT CUQ-GCN GPN GPN-GDEVI GPN-GDLAT GPN-LOP S-BGCN-K S-BGCN-T-K

111,152 243,760 242,736 111,152 111,152 111,152 OOM 10,856 10,856

1 1 1 1 1 1 OOM 1 1

– – – – – – OOM 7331.9 7328.0

778.6 930.0 537.0 509.5 575.0 522.6 OOM 22.0 21.9

1 1 1 1 1 1 OOM 100 100

505.4 380.3 379.7 367.4 367.4 367.0 OOM 770.0 780.0

48,500 43,686 38,870 38,664 47,412 42,598 OOM 1,594 1,620

G-EnsAPPNP G-EnsGAT G-EnsGCN

110,120 43,896 109,096

10 10 10

– – –

67.2 67.3 80.8

10 10 10

3040.0 2540.0 3820.0

1,024 5,452 5,541

GB-EnsAPPNP GB-EnsGAT GB-EnsGCN

110,120 43,896 109,096

100 100 100

8362.5 8362.5 8362.5

67.3 67.1 81.3

100 100 100

2970.0 2550.0 3820.0

1,025 5,452 5,541

33

Related documents

• Rethinking Epistemic Uncertainty in Node Classification through Information Growth#1188096
• Plain Transformers are Surprisingly Powerful Link Predictors#1118471
• Robust Evidential Learning Through Latent Consistency#1156656
• Deep Evidential Regression for Sparse Forest Height Estimation from Multimodal Satellite Imagery#1109119
• Advancing graph neural networks : addressing representation challenges in the vision domain#413324