Rethinking Epistemic Uncertainty in Node Classification through Information Growth

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

cs.LGOct 2, 2026

Rethinking Epistemic Uncertainty in Node Classification through Information Growth

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

Organizations: University of Trento · Fondazione Bruno Kessler, FBK · University of Tromsø

Abstract

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

Figures & tables

	LOC			FI (Bernoulli)			FI (Gaussian)
Model	TU	AU	EU	TU	AU	EU	TU	AU	EU
CUQ-APPNP	0.693	0.693	0.643	0.652	0.652	0.616	0.975	0.942	0.994
CUQ-GAT	0.709	0.709	0.618	0.586	0.586	0.540	0.660	0.659	0.684
CUQ-GCN	0.717	0.717	0.591	0.613	0.613	0.554	0.936	0.858	0.945
GPN	0.730	0.730	0.769	0.593	0.593	0.638	0.560	0.560	0.642
GPN-GD EVI	0.800	0.771	0.857	0.585	0.579	0.615	0.578	0.569	0.621

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.

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

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

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

Appendix figures & tables25 assets

Supplementary material from the paper’s appendix.

Appendix

Component	Parameter	Value
Generation	Graph sizes $n$	$500,910,1657,3017,5493,10000$
	Independent sequences	$20$
Exponential graphon	Decay $\beta$	$15$
SBM graphon	Blocks $K$	$7$
	Between-block probability $p_{\mathrm{out}}$	$0.02$
	Within-block increment $\delta$	$0.83$

Appendix

Table 2: Parameters used for the synthetic graph DGPs.

	$n=500$
Metric	Original	Bootstrap
Features	$12$	$12$
Classes	$7$	$7$
Nodes	$500$	$500$
Edges Edges	$(1.547\times 10^{4})\pm 212.020$	$(1.530\times 10^{4})\pm 220.126$
Average degree	$61.882\pm 0.848$	$61.206\pm 0.881$

Appendix

Table 3: Original and bootstrap graph statistics for the exponential-decay graphon at increasing sizes. Values are mean

\pm

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\times 10^{4})\pm 161.030$	$(1.738\times 10^{4})\pm 169.203$
Average degree	$70.203\pm 0.644$	$69.502\pm 0.677$

Appendix

Table 4: Original and bootstrap graph statistics for the SBM graphon at increasing sizes. Values are mean

\pm

standard deviation across

20

graphon realizations, with bootstrap statistics averaged across

25

replicates per realization.

	CoraML		PubMed
Metric	Original	Bootstrap	Original	Bootstrap
Features	$2879$	$2879$	$500$	$500$
Classes	$7$	$7$	$3$	$3$
Nodes	$2995$	$2995$	$19717$	$19717$
Edges	$8158$	$9802.200\pm 82.619$	$44324$	$60935.400\pm 243.491$
Average degree	$5.450$	$6.546\pm 0.055$	$4.500$	$6.181\pm 0.025$

Appendix

Table 5: Original and bootstrap graph statistics for OOD datasets. Values are bootstrap means

\pm

standard deviations across

25

bootstrap replicates.

Dataset	Hidden	Latent	Layers	Dropout	APPNP $\alpha$	Entropy reg.	Weight decay
Graphons	64	16	2	0.50	0.10	$10^{-3}$	$10^{-3}$
CoraML	64	16	2	0.50	0.10	$10^{-3}$	$10^{-3}$
CiteSeer	64	16	2	0.50	0.10	$10^{-3}$	$10^{-3}$
PubMed	64	16	2	0.50	0.10	$10^{-3}$	$10^{-3}$
AmazonComputers	64	10	2	0.50	0.20	$10^{-5}$	$5\times 10^{-4}$
AmazonPhotos	64	10	2	0.50	0.20	$10^{-5}$	$5\times 10^{-4}$

Appendix

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

Dataset	Entropy reg.	Distance reg.	Activation
Graphons	$0$	$10^{-4}$	GELU
CoraML	$0$	$10^{-4}$	GELU
CiteSeer	$10^{-4}$	$10^{-9.5}$	LogSigmoid
PubMed	$10^{-5}$	$10^{-4}$	ReLU
AmazonComputers	$10^{-5}$	$10^{-4}$	ReLU
AmazonPhotos	$10^{-5}$	$10^{-11}$	ReLU

Appendix

Table 7: Hyperparameters for GPN-GD.

Dataset	Hidden	Dropout	$L_{2}$ reg.	$\lambda_{1}$	$\lambda_{2}$
Graphons	16	0.50	$5\times 10^{-4}$	$10^{-3}$	$1$
CoraML	16	0.50	$5\times 10^{-4}$	$10^{-3}$	$1$
CiteSeer	16	0.50	$5\times 10^{-4}$	$10^{-3}$	$1$
PubMed	16	0.50	$5\times 10^{-4}$	$10^{-3}$	$1$
AmazonComputers	64	0.20	$10^{-4}$	$10^{-3}$	$1$
AmazonPhotos	64	0.20	$10^{-4}$	$10^{-3}$	$1$

Appendix

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

Panel of Figure 4 — Figure 4: Uncertainty estimates of EDL models on the SBM.

Method	CoraML	CiteSeer	PubMed	AmazonPhotos	AmazonComputers
CUQ-APPNP	$4.42\times 10^{-4}$	$6.64\times 10^{-4}$	$4.80\times 10^{-5}$	$8.00\times 10^{-6}$	$4.00\times 10^{-6}$
CUQ-GAT	$1.87\times 10^{-4}$	$4.07\times 10^{-4}$	$2.60\times 10^{-5}$	$4.20\times 10^{-5}$	$1.66\times 10^{-4}$
CUQ-GCN	$7.97\times 10^{-4}$	$7.90\times 10^{-4}$	$1.79\times 10^{-4}$	$2.20\times 10^{-4}$	$5.65\times 10^{-4}$
GPN	$3.65\times 10^{-4}$	$6.21\times 10^{-4}$	$5.00\times 10^{-6}$	$1.00\times 10^{-5}$	$7.00\times 10^{-6}$
GPN-GD EVI	$8.89\times 10^{-2}$	$5.01\times 10^{-3}$	$4.44\times 10^{-2}$	$1.76\times 10^{-5}$	$1.38\times 10^{-1}$
GPN-GD LAT	$2.21\times 10^{-4}$	$4.77\times 10^{-3}$	$1.93\times 10^{-6}$	$8.05\times 10^{-6}$	$3.32\times 10^{-6}$

Appendix

Table 9: Mean epistemic uncertainty estimated by EDL methods on OOD datasets.

DGP	CUQ-APPNP	CUQ-GAT	CUQ-GCN	GPN	GPN-GD EVI	GPN-GD LAT	GPN-LOP	S-BGCN-K	S-BGCN-T-K
Exp.-decay	0.940	0.910	0.848	0.555	0.158	0.761	0.793	0.904	0.906
SBM	0.822	0.832	0.800	0.786	0.159	0.821	0.834	0.823	0.823

Appendix

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

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

Panel of Figure 6 — Figure 6: Ensemble mean uncertainties on the SBM.

		Graph size
Graphon	Backbone	500	910	1657	3017	5493	10000
Exp.-decay	APPNP	0.2991	0.2931	0.2870	0.2886	0.2841	0.2826
	GAT	0.4482	0.5102	0.5505	0.5790	0.5946	0.6156
	GCN	0.2053	0.2113	0.2119	0.2071	0.2059	0.2050
SBM	APPNP	0.2049	0.2185	0.3146	0.3483	0.3471	0.3431
	GAT	0.2440	0.2998	0.3684	0.4130	0.4365	0.4506

Appendix

Table 11: Mean normalized Wasserstein distances between GB-Ens- and true-DGP-induced second-order distributions.

DGP	APPNP G-Ens	GAT G-Ens	GCN G-Ens	APPNP GB-Ens	GAT GB-Ens	GCN GB-Ens
Exp.-decay	0.808	0.731	0.902	0.946	0.931	0.932
SBM	0.704	0.772	0.814	0.816	0.830	0.830

Appendix

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

Model	ID ACC	LOC			FI Gaussian				FI Bernoulli
		TU	AU	EU	OOD ACC	TU	AU	EU	OOD ACC	TU	AU	EU
CUQ-APPNP	0.790	0.761	0.761	0.665	0.080	1.000	0.992	1.000	0.760	0.603	0.603	0.596
CUQ-GAT	0.764	0.697	0.697	0.562	0.070	0.996	0.996	1.000	0.740	0.544	0.544	0.537
CUQ-GCN	0.712	0.715	0.715	0.616	0.110	1.000	0.998	1.000	0.700	0.574	0.574	0.531
GPN	0.802	0.836	0.836	0.837	0.790	0.559	0.559	0.583	0.800	0.578	0.578	0.577
GPN-GD EVI	0.782	0.892	0.862	0.879	0.760	0.554	0.551	0.545	0.760	0.556	0.554	0.544

Appendix

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	0.647	0.751	0.751	0.616	0.080	1.000	0.711	1.000	0.570	0.640	0.640	0.591
CUQ-GAT	0.613	0.768	0.768	0.679	0.100	0.941	0.701	0.989	0.560	0.597	0.597	0.597
CUQ-GCN	0.557	0.593	0.594	0.571	0.110	0.999	0.535	1.000	0.480	0.576	0.576	0.479
GPN	0.678	0.741	0.741	0.615	0.690	0.489	0.487	0.702	0.630	0.599	0.599	0.569
GPN-GD EVI	0.688	0.807	0.807	0.774	0.660	0.486	0.482	0.599	0.670	0.568	0.568	0.558

Appendix

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	0.852	0.693	0.693	0.643	0.300	0.975	0.942	0.994	0.770	0.652	0.652	0.616
CUQ-GAT	0.835	0.709	0.709	0.618	0.670	0.660	0.659	0.684	0.780	0.586	0.586	0.540
CUQ-GCN	0.845	0.717	0.717	0.591	0.340	0.936	0.858	0.945	0.770	0.613	0.613	0.554
GPN	0.837	0.730	0.730	0.769	0.820	0.560	0.560	0.642	0.820	0.593	0.593	0.638
GPN-GD EVI	0.827	0.800	0.771	0.857	0.820	0.578	0.569	0.621	0.820	0.585	0.579	0.615

Appendix

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	0.838	0.717	0.717	0.589	0.010	1.000	1.000	1.000	0.720	0.698	0.698	0.543
CUQ-GAT	0.875	0.773	0.773	0.719	0.170	0.908	0.907	0.909	0.820	0.503	0.503	0.484
CUQ-GCN	0.831	0.632	0.632	0.538	0.210	0.896	0.895	0.942	0.790	0.526	0.526	0.494
GPN	0.810	0.749	0.749	0.762	0.720	0.551	0.551	0.562	0.730	0.554	0.554	0.560
GPN-GD EVI	0.381	0.408	0.382	0.511	0.910	0.515	0.515	0.582	0.430	0.497	0.505	0.482

Appendix

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	0.901	0.720	0.721	0.694	0.100	1.000	0.999	1.000	0.800	0.693	0.693	0.612
CUQ-GAT	0.915	0.842	0.842	0.823	0.220	0.927	0.927	0.936	0.870	0.510	0.510	0.497
CUQ-GCN	0.912	0.802	0.802	0.738	0.130	0.948	0.947	0.953	0.900	0.503	0.503	0.474
GPN	0.900	0.835	0.835	0.892	0.910	0.522	0.522	0.568	0.910	0.552	0.552	0.565
GPN-GD EVI	0.900	0.812	0.812	0.855	0.410	0.712	0.719	0.689	0.910	0.563	0.563	0.573

Appendix

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	0.910	0.770	0.770	0.741	0.060	1.000	1.000	1.000	0.830	0.553	0.553	0.507
CUQ-GAT	0.787	0.676	0.678	0.639	0.580	0.663	0.645	0.663	0.820	0.492	0.492	0.452
CUQ-GCN	0.797	0.730	0.730	0.658	0.110	0.979	0.940	0.979	0.770	0.538	0.541	0.519
GPN	0.884	0.755	0.755	0.931	0.860	0.531	0.531	0.557	0.860	0.537	0.537	0.550
GPN-GD EVI	0.872	0.771	0.760	0.919	0.840	0.522	0.522	0.539	0.840	0.524	0.524	0.538

Appendix

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	0.948	0.861	0.861	0.814	0.240	1.000	0.999	1.000	0.920	0.594	0.594	0.544
CUQ-GAT	0.945	0.848	0.848	0.784	0.260	0.998	0.996	1.000	0.930	0.487	0.487	0.417
CUQ-GCN	0.944	0.826	0.826	0.782	0.300	0.992	0.992	0.992	0.900	0.524	0.524	0.474
GPN	0.938	0.876	0.876	0.957	0.900	0.562	0.562	0.607	0.900	0.609	0.609	0.600
GPN-GD EVI	0.934	0.912	0.897	0.957	0.920	0.613	0.609	0.643	0.920	0.618	0.615	0.641

Appendix

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	0.697	0.685	0.685	0.662	0.390	0.823	0.823	0.811	0.680	0.581	0.578	0.676
CUQ-GAT	N/A	0.395	0.405	0.387	N/A	N/A	N/A	N/A	N/A	N/A	N/A	N/A
CUQ-GCN	N/A	0.523	0.516	0.523	N/A	N/A	N/A	N/A	N/A	N/A	N/A	N/A
GPN	0.696	0.706	0.705	0.747	0.660	0.540	0.539	0.604	0.660	0.540	0.539	0.604
GPN-GD EVI	0.675	0.690	0.690	0.730	0.680	0.534	0.534	0.601	0.680	0.533	0.533	0.601

Appendix

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

Model	Params	Models	Preproc. (s)	Epoch (ms)	Fwd	Infer. (ms)	Peak (MiB)
CUQ-APPNP	186,620	1	–	17.0	1	7.0	268
CUQ-GAT	195,196	1	–	16.9	1	6.6	253
CUQ-GCN	194,940	1	–	16.4	1	6.9	235
GPN	186,620	1	–	16.4	1	6.8	173
GPN-GD EVI	186,620	1	–	17.8	1	7.0	202
GPN-GD LAT	186,620	1	–	16.7	1	6.9	188

Appendix

Table 21: Computational cost on CoraML.

Model	Params	Models	Preproc. (s)	Epoch (ms)	Fwd	Infer. (ms)	Peak (MiB)
CUQ-APPNP	540,564	1	–	46.6	1	24.6	2,886
CUQ-GAT	549,140	1	–	36.4	1	19.0	2,760
CUQ-GCN	548,884	1	–	34.9	1	18.8	2,633
GPN	540,564	1	–	32.2	1	17.1	2,127
GPN-GD EVI	540,564	1	–	32.3	1	16.1	2,127
GPN-GD LAT	540,564	1	–	31.9	1	16.2	2,249

Appendix

Table 22: Computational cost on CoauthorPhysics.

Model	Params	Models	Preproc. (s)	Epoch (ms)	Fwd	Infer. (ms)	Peak (MiB)
CUQ-APPNP	111,152	1	–	778.6	1	505.4	48,500
CUQ-GAT	243,760	1	–	930.0	1	380.3	43,686
CUQ-GCN	242,736	1	–	537.0	1	379.7	38,870
GPN	111,152	1	–	509.5	1	367.4	38,664
GPN-GD EVI	111,152	1	–	575.0	1	367.4	47,412
GPN-GD LAT	111,152	1	–	522.6	1	367.0	42,598

Appendix

Table 23: Computational cost on OGBN-ArXiv.

Epistemic Uncertainty

Epistemic uncertainty is uncertainty arising from limited knowledge or model support, rather than irreducible randomness in data.

See all 113 papers

May 21, 2026

Do Deep Ensembles Actually Capture Uncertainty in Graph Neural Networks?

While deep ensembles are widely considered to be the default method for uncertainty quantification in deep learning, their effectiveness for graph-structured data is often simply assumed based on successes in domains like computer vision. We investigate standard deep ensembles specifically for message-passing graph neural networks. Benchmarking across eight datasets representing varied tasks and complexities, we reveal that ensembles provide only marginal improvement over a single model. These marginal gains stem primarily from averaging out optimization noise in point predictions rather than from meaningfully better uncertainty estimates. Through an aleatoric-epistemic decomposition, we identify epistemic collapse: independently trained networks consistently converge to overly similar predictions. Because disagreement is the fundamental mechanism through which ensembles capture epistemic uncertainty, this lack of diversity neutralizes their key advantage. Towards explaining this phenomenon, we derive a bound on epistemic variance in terms of the graph topology and Dirichlet energy budget, linking epistemic collapse to the smoothing bias of message passing. Our results suggest that deep ensemble success does not seamlessly transfer to graph machine learning.

Pedro C. Vieira, Pedro Ribeiro, Viacheslav Borovitskiy

University of Edinburgh · DCC/FCUP, University of Porto

Graph Neural Networks Deep Ensembles Epistemic Uncertainty

Ask PDF

Jun 10, 2026

Epistemic Uncertainty Is Not the Reducible Kind

The standard taxonomy of predictive uncertainty defines epistemic uncertainty as the part removable by collecting more data, while the standard measure identifies it with a mutual-information term. We prove the definition and the measure are extensionally inconsistent. On an explicit construction, the measure assigns all uncertainty to the epistemic class, yet no quantity of training data reduces it. Reducibility is instead a property of the pair (uncertainty, acquisition class), and the dichotomy resolves into three parts: aleatoric, sample-reducible epistemic, and mechanism-reducible epistemic uncertainty. An exact identity for the value of an observation shows that in-distribution data never reduces mechanism-irreducible uncertainty and generically increases it. Ensemble disagreement, the deployed epistemic estimate, tracks the training procedure rather than the epistemic term. It collapses to zero beneath a positive truth under consistent training, and equals hyperparameter-scaled initialization noise under interpolation. A finite-sample falsification test and seed-swept experiments confirm the theory.

Robin Young

University of Cambridge

Uncertainty Quantification Uncertainty Decomposition Epistemic Uncertainty

Ask PDF

May 25, 2026

Generalized Evidential Deep Learning: From a Bayesian Perspective

Evidential Deep Learning (EDL) has emerged as an efficient, sampling-free strategy for uncertainty estimation. A series of EDL variants have been proposed to address specific limitations of the original framework, achieving notable success. However, the underlying theoretical structure of EDL and the relationships among these variants have received limited systematic investigation. In this work, we establish a principled theoretical foundation for EDL by interpreting it within a generalized Bayesian framework that includes prior specification, posterior update, and training objective. We further characterize evidential uncertainty from a Bayesian distributional uncertainty viewpoint, established via asymptotic analysis. Building on this perspective, we further propose Generalized Evidential Deep Learning (GEDL), a unified and extensible framework that explicitly disentangles the roles of individual components and systematically relates GEDL to existing variants. Extensive experiments demonstrate that GEDL yields comparable results on classification, uncertainty estimation and OOD detections, with theoretical grounding.

Yuanye Liu, Yibo Gao, Yuanyang Chen +1

School of Data Science, Fudan University, Shanghai, China.

Evidential Deep Learning Uncertainty Quantification Bayesian Inference Epistemic Uncertainty

Ask PDF

Abstract

Epistemic Uncertainty

Explore similar work

Do Deep Ensembles Actually Capture Uncertainty in Graph Neural Networks?

Epistemic Uncertainty Is Not the Reducible Kind

Generalized Evidential Deep Learning: From a Bayesian Perspective