acceptodds
Under review as a conference paper at ICLR 2027

Rethinking Epistemic Uncertainty in Node Classification through Information Growth

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.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
Epistemic Uncertainty, Uncertainty Quantification, Evidential Deep Learning, Node Classification, Graph Bootstrap Ensembles, Graph Neural Networks

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_3WGGOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes to study how epistemic uncertainty evolves over increasing information for training instead of surrogate metrics. The authors establish how evidential methods exhibit pathological behaviour under this metric and propose bootstrap ensembles as a candidate remedy. They empirically back these claims on synthetic graphs.

Critical strengths
  • The paper proposes a way to study if uncertainty decreases monotonically with more information similar to literature in i.i.d. domains
  • The paper formally identifies pathological behaviour of EDL methods for graphs
  • The paper empirically shows that bootstrap ensembles are well behaved under the proposed criterion
Critical weaknesses
  • I am not familiar with the i.i.d. work on information growth and find the explanation for graphs provided in the paper hard to understand (see questions section).
  • The empirical results are limited to synthetic graphs only. From the procedure outlined in Algorithm 1, I see no reason why the authors wouldn't instead study real-world graphs (as acknowledged in the conclusion of the paper).
  • The focus on EDL is a valid restriction but limiting the relevance of the paper as there is an abundance of uncertainty estimators, also for graphs, in the literature. In particular, the experiments ignore all non-EDL baselines. This is particularly critical as the authors propose bootstrap ensembles as a solution to the limitations of EDL but the paper does not give a good context of where these stand in comparison to other non-EDL methods. Also their performance on the well established OOD detection task would be valuable to the community to assess boostrap ensembles as an alternative to existing methods.
Questions for authors

Information Growth:

  • For the sampling unit, how are G' and V' defined?
  • What precisely do "nested graphs" mean in this context?
  • In the sampling scheme, what does "natural projection that restricts an observation" mean?
  • How is its inverse as in Eq. 7 defined?
  • What is the role of the parameter phi, and what is its natural interpretation in this context?
  • I don't understand the connection to the empirical models used in the paper. Is the procedure of Algorithm A a projected DGP? How do the synthetic datasets relate or instantiate the requirements of a DGP and connect to the theory section? Other:
  • In 2.2., the authors note that TU or AU sometimes perform better for OOD detection under certain shifts and interpret this as a shortcoming of OOD detection. However, OOD detection is (also for i.i.d.) data the most established proxy and performance criterion. Could this not also be attributed to the methods struggling to properly disentangle uncertainty rather than evidence against this experimental proxy?
  • Fig 1a: It seems as EU does actually decrease for S-BGCN and its variants -- isn't this actually in favor of EDL for graphs?
  • Fig 2a: Here, a comparison to EDL would be interesting: Are they also well behaved like bootstrap ensembles or do they show pathological behavior?
  • Fig 3b: AU seems to be non-constant for many variants of the bootstrap ensembles. Isn't this a problem?
5 comments
AuthorsOpenReview ↗

Response to Reviewer 3WGG (1/3)

We thank the reviewer for their constructive feedback and for recognizing the value of evaluating epistemic uncertainty under information growth, our theoretical characterization of the behavior of graph EDL methods, and the empirical findings concerning bootstrap ensembles. We address the concerns and questions raised below.

  1. Question: “For the sampling unit, how are G' and V' defined?” and “What precisely do "nested graphs" mean in this context?”
    Answer: By nested graphs, we mean graphs observed at successive stages of information growth, where each smaller graph is an induced subgraph of the subsequent larger graph. Specifically, given G=(V, E)G=(V,\ E), G′=(V′, E′)G'=(V',\ E') denotes the larger graph observed at a subsequent stage, with V′V' its node set and V⊂V′V\subset V'. We require that GG is the subgraph of G′G' induced by VV, i.e., E={(u,v) ∈E′: u,v ∈V}E=\lbrace (u,v)\ \in E':\ u,v\ \in V \rbrace. We will clarify this definition in the revised version of the paper.
  2. Question: “In the sampling scheme, what does "natural projection that restricts an observation" mean?”
    Answer: The natural projection πB→A\pi_{B\rightarrow A}, for A⊂BA\subset B, is the operation that maps an observation indexed by BB to the corresponding observation indexed by AA. For an attributed graph GB=(B, EB, XB, YB)G_B=(B,\ E_B,\ X_B,\ Y_B), this means retaining only the nodes in AA, their attributes and labels, and the edges between them: πB→A(GB)=(GB[A], XB∣A, YB∣A)\pi_{B\rightarrow A}(G_B)=(G_B[A],\ X_B|A,\ Y_B|A), where GB[A]G_B[A] is the subgraph induced by AA, and XB∣AX_B|A, YB∣AY_B|A denote the restrictions of node features and labels to AA. We will clarify this definition in the revised version of the paper.
  3. Question: “How is its inverse as in Eq. 7 defined?”
    Answer: The notation πB→A−1\pi^{-1}_{B\rightarrow A} in Equation (7) denotes the preimage of a set under the projection, not an inverse function. Since πB→A\pi_{B\rightarrow A} discards nodes and edges, it is generally not invertible because the original larger graph cannot be reconstructed from its induced subgraph. Formally, let χA\chi_A and χB\chi_B denote the sample spaces of graph observations indexed by AA and BB, respectively. For any measurable set C⊆χAC\subseteq \chi_A, πB→A−1(C)={GB∈XB:πB→A(GB)∈C}\pi_{B\rightarrow A}^{-1}(C)=\lbrace G_B\in X_B:\pi_{B\rightarrow A}(G_B)\in C \rbrace. In other words, the preimage contains all larger graphs whose restriction to AA belongs to CC. Consequently, Equation (7) PA,ϕ=PB,ϕ∘πB→A−1P_{A,\phi }=P_{B,\phi }\circ \pi_{B\rightarrow A}^{-1}, means that PA,ϕ(C)=PB,ϕ(πB→A−1(C))P_{A,\phi }(C)=P_{B,\phi }(\pi_{B\rightarrow A}^{-1}(C)) for every measurable C ⊆χAC\ \subseteq \chi_A. This is precisely the projectibility condition: the distribution PA, ϕP_{A,\ \phi } coincides with the marginal distribution of PB,ϕP_{B,\phi } obtained by restricting the observations to the indices in AA, for every A⊂BA\subset B and ϕ∈Φ\phi \in \Phi.
  4. Question: “What is the role of the parameter phi, and what is its natural interpretation in this context?”
    Answer: The parameter ϕ∈Φ\phi \in \Phi indexes the underlying projective graph data-generating process, with GA∼PA,ϕG_A\sim P_{A,\phi } denoting the distribution of a graph generated on the node index set AA. For example, in a graphon model, ϕ\phi represents the parameters specifying the graphon function that governs graph generation. We will clarify its meaning in the revised version of the paper.
  5. Question: “I don't understand the connection to the empirical models used in the paper. Is the procedure of Algorithm A a projected DGP? How do the synthetic datasets relate or instantiate the requirements of a DGP and connect to the theory section? Other:”
    Answer: In the paper, Algorithm 1 in Appendix C describes the local graph bootstrap procedure, whereas projectibility is a property of the underlying DGP, which we require to construct coherent sequences of larger and nested graphs, not of the bootstrap algorithm. The exponential-decay and SBM graphons used in our synthetic experiments define projectible DGPs (Veitch & Roy, 2015), thereby satisfying the projectibility requirement of our theoretical framework. The local graph bootstrap is subsequently applied to graphs sampled from these DGPs as part of GB-Ens. We have clarified this connection in the revised paper.
AuthorsOpenReview ↗

Response to Reviewer 3WGG (2/3)

  1. Question: “In 2.2., the authors note that TU or AU sometimes perform better for OOD detection under certain shifts and interpret this as a shortcoming of OOD detection. However, OOD detection is (also for i.i.d.) data the most established proxy and performance criterion. Could this not also be attributed to the methods struggling to properly disentangle uncertainty rather than evidence against this experimental proxy?”
    Answer: The use of OOD detection as a proxy for evaluating epistemic uncertainty is increasingly challenged in the literature (Li et al., 2025; Sale et al., 2026; Paplham et al., 2026). Typically, OOD detection is used to validate epistemic uncertainty based on the assumption that it should be high for atypical inputs. However, Li et al., (2025) and Sale et al. (2026) argue that model-based epistemic uncertainty represents a “lack of knowledge” about the underlying DGP, whereas the notion of “out-of-distribution” lacks a universally accepted definition and encompasses different types of distributional shifts, such as feature perturbations and leave-out classes. Taken literally, OOD refers to observations outside the underlying DGP, which is not equivalent to atypical observations under that DGP. Thus, epistemic uncertainty is not necessarily the appropriate quantity for detecting OOD inputs. Paplham et al. (2026) further derives the Bayes-optimal discriminator between ID and OOD inputs, which generally corresponds to neither TU, AU, nor EU. These works motivate reconsidering the standard formulation and use of OOD detection for the evaluation of epistemic uncertainty.

    The observation that TU or AU outperform EU under certain shifts is compatible with poor uncertainty disentanglement. However, even perfectly estimated uncertainty measures would not necessarily make EU the best-performing OOD detection score, since none of TU, AU, or EU is inherently optimal for this task. Our results are therefore consistent with both explanations, which we will clarify in the revised manuscript.

  2. Question: “Fig 1a: It seems as EU does actually decrease for S-BGCN and its variants -- isn't this actually in favor of EDL for graphs?”
    Answer: We emphasize that the key question is not merely whether a model achieves EU→0EU\rightarrow 0, but how it does so. First, S-BGCN-K/T-K also incorporate Bayesian dropout, which may yield non-vanishing EU asymptotically (Verdoja & Kyrki, 2020). The observed empirical decrease in EU is driven by the prior's dependence on neighborhood size. For dense graphs, neighborhood size grows unboundedly, thereby driving EU downward. However, this does not, in general, establish consistency or constitute a statistically justified procedure for estimating EU, since the EDL model does not account for uncertainty in its learned parameters due to limited training data, which remain point estimates. In contrast, GB-Ens employs graph bootstrapping, a frequentist approach that, in principle, can capture this source of uncertainty. For further details, we refer to our response to reviewer U45f, Question 4(e).

  3. Question: “Fig 2a: Here, a comparison to EDL would be interesting: Are they also well behaved like bootstrap ensembles or do they show pathological behavior?”
    Answer: This comparison is already provided in Figure 1a, where we show that graph EDL models generally fail to exhibit the expected concentration of EU under information growth, consistent with our theoretical analysis.

  4. Question: “Fig 3b: AU seems to be non-constant for many variants of the bootstrap ensembles. Isn't this a problem?”
    Answer: AU would be constant if the learned predictor had already converged to a limiting predictor, which may not be the case at finite graph sizes. Moreover, AU and EU estimates have been found to be positively correlated, as they are computed from the same model and jointly contribute to TU (Sale et al., 2026). It is therefore natural to observe a decrease in both AU and EU, with AU eventually stabilizing as the learned predictor converges to a stable solution with increasing information. We will clarify this interpretation in the revised paper.

AuthorsOpenReview ↗

Response to Reviewer 3WGG (3/3)

References:

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.

Jakub Paplham, Willem Waegeman, Eyke Hullermeier, and Vojtech Franc. Evaluating epistemic uncertainty: Beyond OOD detection and active learning. arXiv preprint 2607.14817, 2026.

Yusuf Sale, Nikita Kotelevskii, Maxim Panov, and Eyke Hullermeier. The aleatoric-epistemic dichotomy of uncertainty is meaningful and indispensable for machine learning. Available at SSRN 6783338, 2026.

Victor Veitch and Daniel M Roy. The class of random graphs arising from exchangeable random measures. arXiv preprint 1512.03099, 2015.

Francesco Verdoja and Ville Kyrki. Notes on the behavior of mc dropout. arXiv preprint 2008.02627, 2020.

Reviewer_U45fOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary
  • This paper investigates whether epistemic uncertainty estimates for graph node classification decrease appropriately as more information about the DGP becomes available. The authors introduce an information-growth evaluation framework based on projective graph DGPs and define consistency criteria for epistemic predictors.
  • Through a unified analysis of Graph EDL objectives, the paper shows that uncertainty estimates can remain dependent on model hyperparameters rather than reflecting the increasing amount of observed information.
  • As an alternative, the authors propose GB-Ens, combining graph resampling and randomized training. Controlled synthetic experiments demonstrate stronger epistemic uncertainty reduction than existing EDL methods and standard deep ensembles.
Critical strengths
  1. Meaningful problem formulation: The paper clearly explains why OOD detection performance is insufficient to evaluate whether epistemic uncertainty decreases with increasing information. Introducing a dedicated statistical evaluation framework is an important contribution.

  2. Theoretical analysis: The unified analysis of graph EDL objectives provides a mathematical explanation for why several existing methods may retain non-vanishing epistemic uncertainty under fixed regularization settings. This meaningfully extends prior theoretical critiques of EDL to graph learning.

  3. Systematic evaluation: The experiments use controlled graph-growth sequences from the same DGP and compare multiple EDL methods and deep ensembles. The decomposition of uncertainty into graph-resampling and training-seed components is also informative.

Critical weaknesses
  1. Dependence on unavailable latent information: Appendix C indicates that the main synthetic experiments use ground-truth latent coordinates from the DGP to determine node similarity during bootstrapping. Since such information is generally unavailable in practical graph learning, it remains unclear whether the reported uncertainty reduction holds when relying only on the observed graph.

  2. Limited evidence for consistency: Definition 3.2 requires not only decreasing uncertainty but also convergence toward the Bayes-optimal predictor. However, theoretical consistency of GB-Ens is not established, and the experiments primarily demonstrate uncertainty contraction. Moreover, GAT exhibits non-monotonic behavior, while its Wasserstein distance from true-DGP resampling increases with graph size.

  3. Uncertain validity of graph resampling: Appendix C reports substantial structural changes after bootstrapping on some real-world graphs. For example, in CiteSeer, it is unclear whether such changes reflect genuine sampling variability or distortions introduced by the bootstrap procedure.

  4. Limited methodological novelty and comparison fairness:

  • GB-Ens combines existing bootstrap and deep ensemble techniques, making its algorithmic novelty relatively limited. Furthermore, the standard deep ensemble baseline uses 10 models, whereas GB-Ens uses 100, motivating comparisons under matched computational budgets and additional ablation studies.
  • Information-growth experiments are limited to two synthetic dense graphon DGPs. The applicability to sparse graphs and other realistic graph-growth settings remains unclear. More detailed results on accuracy, NLL, and calibration across graph sizes would also help establish the practical relevance of uncertainty contraction.
Questions for authors
  1. Does GB-Ens exhibit similar uncertainty contraction when node similarity is estimated solely from the observed graph rather than using ground-truth latent coordinates? Could the authors compare latent-coordinate-based similarity with alternatives such as Jaccard similarity?

  2. Beyond decreasing epistemic uncertainty, what evidence supports convergence toward the Bayes-optimal predictor as required by Definition 3.2? How do the authors interpret the non-monotonic behavior and increasing Wasserstein distances observed for GAT?

  3. How do the substantial changes in graph statistics after resampling affect the uncertainty estimates? Can the authors provide additional evidence that the bootstrap distribution adequately approximates sampling variability under the underlying DGP?

  4. Fair comparisons and ablations: Could the authors compare GB-Ens against standard deep ensembles using the same number of models or a matched computational budget? How sensitive are the results to the number of bootstrap samples, random seeds, and neighborhood size k?

  5. Could graph EDL methods recover epistemic consistency if their regularization or tempering parameters were adjusted with graph size? How would such alternatives compare with GB-Ens?

  6. Do the conclusions hold for sparse graphs or other projective DGPs? Could the authors also report accuracy and calibration trends across graph sizes to clarify whether uncertainty contraction corresponds to reliable predictive performance?

10 comments
AuthorsOpenReview ↗

Response to Reviewer U45f (1/5)

We thank the reviewer for their careful assessment and constructive feedback, as well as for recognizing the importance of our problem formulation, the contribution of our theoretical analysis of graph EDL objectives, and the systematic nature of our experimental evaluation. We address the concerns and questions raised below.

  1. Weakness: “Dependence on unavailable latent information: Appendix C indicates that the main synthetic experiments use ground-truth latent coordinates from the DGP to determine node similarity during bootstrapping. Since such information is generally unavailable in practical graph learning, it remains unclear whether the reported uncertainty reduction holds when relying only on the observed graph.”
    Related question: “Does GB-Ens exhibit similar uncertainty contraction when node similarity is estimated solely from the observed graph rather than using ground-truth latent coordinates? Could the authors compare latent-coordinate-based similarity with alternatives such as Jaccard similarity?”
    Answer: Reviewer aG55 raised a similar question (see our response to Question 1(d)). Briefly, we used ground-truth latent coordinates to isolate the epistemic behavior of GB-Ens under controlled information growth, avoiding additional approximation error from estimating node similarity. We acknowledge the value of a Jaccard-based robustness assessment and will provide the corresponding ablation by the end of the rebuttal period.

  2. This question raises two distinct points, which we address separately.
    (a) Weakness: “Limited evidence for consistency: Definition 3.2 requires not only decreasing uncertainty but also convergence toward the Bayes-optimal predictor. However, theoretical consistency of GB-Ens is not established, and the experiments primarily demonstrate uncertainty contraction.”
    Related question: “Beyond decreasing epistemic uncertainty, what evidence supports convergence toward the Bayes-optimal predictor as required by Definition 3.2?”
    We acknowledge that an ensemble may become increasingly confident in incorrect predictions. This is a general limitation of model-based bootstrap uncertainty estimators relying on deep neural networks (Jain & Bates, 2026), rather than one specific to GB-Ens. Establishing asymptotic consistency would require additional assumptions concerning the expressiveness of the hypothesis class, parameter identifiability, the statistical consistency of the constituent learning procedures, and the consistency of the bootstrap approximation. The first three assumptions are shared with other deep learning methods, and they are difficult to establish for neural network learning procedures in practice.

    Our experiments therefore provide evidence of uncertainty contraction, but not direct evidence of convergence toward the Bayes-optimal predictor. Such direct assessment would require evaluating the Bayes posterior predictive distribution pBayes(y∣X,A){p}^{Bayes}(y|X,A). Although specifying the synthetic data-generating process defines this distribution, it does not make its evaluation analytically tractable. For our graphon models, evaluation requires posterior inference over unobserved node-level latent variables, followed by marginalization of the label probabilities under the resulting posterior. Even for the SBM graphon, where structural simplifications are possible, posterior inference remains necessary. Developing and validating sufficiently accurate posterior approximations would therefore require a separate inference study, beyond the scope of the present work. We will add these considerations in the revised paper.

AuthorsOpenReview ↗

Response to Reviewer U45f (2/5)

  1. This question raises two distinct points, which we address separately.
    (b) Weakness: “Moreover, GAT exhibits non-monotonic behavior, while its Wasserstein distance from true-DGP resampling increases with graph size.”
    Related question: “How do the authors interpret the non-monotonic behavior and increasing Wasserstein distances observed for GAT?”
    Answer: Recall that GAT's non-monotonic EU behavior is observed primarily on the SBM graphon and it is driven by the seed-based component of EU, as discussed in our paper. We hypothesize that this difference from the more consistently decreasing EU observed for APPNP and GCN arises from GAT's distinct propagation mechanism. While APPNP and GCN employ propagation weights determined by the adjacency matrix and its normalization, GAT learns attention coefficients that depend on node representations and model parameters. Consequently, GAT's propagation weights are themselves parameter-dependent, potentially increasing sensitivity to training randomness and contributing to the observed seed-based EU fluctuations. This interpretation remains a hypothesis, and further investigation of the interaction between GAT's architecture and seed-based EU would be valuable, particularly in light of existing findings that attention-based propagation may not always benefit node classification on SBMs under different signal-to-noise ratios (Ma et al., 2025).

    Regarding the increasing normalized Wasserstein distances between the second-order predictive distributions induced by GB-Ens and the true-DGP resampling reference ensemble, we emphasize that this behavior is not unique to GAT: it is also observed for APPNP and GCN on the SBM graphon. Therefore, it cannot be attributed exclusively to GAT's attention mechanism. Moreover, EU contraction and convergence of the bootstrap-induced second-order predictive distribution toward its true-DGP resampling counterpart are distinct properties; the former does not imply the latter. In the absence of consistency guarantees for GB-Ens, decreasing Wasserstein distances are not theoretically guaranteed. We hypothesize that the observed discrepancies depend on the interaction between the bootstrap approximation and the underlying GNN architecture, whose theoretical characterization remains an open research direction.

  2. Weakness: “Uncertain validity of graph resampling: Appendix C reports substantial structural changes after bootstrapping on some real-world graphs. For example, in CiteSeer, it is unclear whether such changes reflect genuine sampling variability or distortions introduced by the bootstrap procedure.”
    Related question: “How do the substantial changes in graph statistics after resampling affect the uncertainty estimates? Can the authors provide additional evidence that the bootstrap distribution adequately approximates sampling variability under the underlying DGP?”
    Answer: Our local graph bootstrap (Jeong & Donnat, 2025) was developed for graphon models, and its application to real-world graphs outside this family it may introduce structural distortions beyond the sampling variability of the unknown underlying DGP, potentially affecting the learned predictive distributions and the resulting uncertainty estimates.

    Importantly, our real-world experiments do not investigate uncertainty under information growth. Instead, they evaluate the discriminative performance of total, aleatoric, and epistemic uncertainty scores in OOD detection tasks. These scores should therefore not be interpreted as uncertainty estimates whose consistency has been established under our information-growth criterion.

    Our normalized Wasserstein analysis on synthetic graphons directly addresses the fidelity of the bootstrap approximation by comparing the second-order predictive distributions induced by GB-Ens with those obtained through independent resampling from the true DGP. However, because the underlying DGP is unknown for real-world benchmarks, an analogous comparison is not available. Thus, our synthetic experiments provide controlled evidence regarding bootstrap approximation quality. However, to the best of our knowledge, no consistency results have been established for graph bootstrap-based estimators in the context of node classification, and their validity for real-world graph sampling processes remains an open question for future work.

AuthorsOpenReview ↗

Response to Reviewer U45f (3/5)

  1. This question raises several points, which we address separately.
    (a) Weakness: “Limited methodological novelty [...]: GB-Ens combines existing bootstrap and deep ensemble techniques, making its algorithmic novelty relatively limited.”
    Answer: We acknowledge that GB-Ens builds on established bootstrap and deep ensemble techniques. Indeed, bootstrap ensembles inherently combine bootstrap resampling with ensemble learning. However, methodological novelty can arise from adapting and systematically investigating established methods in substantially different learning settings, such as graph learning. To the best of our knowledge, graph ensembles remain understudied, with Vieira et al. (2026) providing the only theoretical investigation, and no prior work has investigated graph bootstrap ensembles under information growth or systematically compared them with graph deep ensembles in this setting. Moreover, bootstrap methods have well-established theoretical foundations and consistency results in i.i.d. supervised learning, making their investigation in graph learning particularly relevant, especially given the limited understanding of analogous guarantees in this setting.

    (b) Weakness: “[...] Comparison fairness: Furthermore, the standard deep ensemble baseline uses 10 models, whereas GB-Ens uses 100, motivating comparisons under matched computational budgets and additional ablation studies.”
    Related question: “Fair comparisons and ablations: Could the authors compare GB-Ens against standard deep ensembles using the same number of models or a matched computational budget? How sensitive are the results to the number of bootstrap samples, random seeds, and neighborhood size k?”
    Answer: Our 10-member G-Ens baseline follows Vieira et al. (2026), who ran a sensitivity analysis and found that increasing the number of ensemble members did not improve predictive accuracy or NLL. We therefore compare GB-Ens against this established graph ensemble baseline rather than an unnecessarily enlarged configuration.

    Moreover, comparing the 10 members of G-Ens with the 100 members of GB-Ens overlooks their fundamentally different sampling designs. G-Ens uses 10 random seeds on a single graph, whereas GB-Ens uses 4 seeds per graph across 25 bootstrap resamples. Thus, the two methods already employ a comparable number of seeds per graph, while the additional members of GB-Ens arise from the bootstrap dimension, which captures an additional source of epistemic uncertainty. Increasing the number of G-Ens members would improve the Monte Carlo approximation of seed-based EU but would not introduce bootstrap-based EU, leaving the fundamental methodological distinction between the approaches unchanged. For these reasons, we retain the established 10-member G-Ens configuration.

    We believe that assessing the sensitivity of GB-Ens to its sampling design provides a more informative evaluation than enforcing an identical number of ensemble members. We selected the 25×425\times 4 decomposition (bootstrap resamples ×\times random seeds) as a compromise between estimating the two EU components and computational cost, informed by previous work (Jiménez et al., (2026) who use a 20×1020\times 10 decomposition). To assess sensitivity to this choice, we will provide an additional ablation study of GB-Ens by the end of the rebuttal period.

    Regarding the neighborhood size, the work by Jeong & Donnat (2025) already includes a sensitivity analysis examining how kk affects the structural statistics of bootstrap-resampled graphs relative to the original graphon. Following their work, we set k=20k=20 and observe good agreement between the structural statistics of the original and bootstrapped graphs, as reported in Appendix C, particularly as the graphon size increases.

    From a theoretical perspective, Jeong & Donnat (2025) further establish consistency of the edge-probability estimator under known latent variables when kk grows at an appropriate sublinear rate with graph size, providing theoretical motivation for increasing kk with nn to improve bootstrap estimates. However, implementing such an asymptotic prescription is impractical in our experiments. We therefore followed Jeong & Donnat (2025) in using a fixed kk, without claiming that this choice satisfies the theoretical consistency conditions.

    While kk may affect bootstrap approximation quality and, consequently, the resulting EU estimates, we believe that, given the observed agreement between the structural statistics in the original and bootstrapped graphs, repeating the sensitivity analysis of the underlying bootstrap procedure would offer limited additional insight into the behavior of GB-Ens under graph information growth.

Reviewer_aG55OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

Epistemic uncertainty should shrink as a model sees more data, but UQ methods for graphs are mostly judged on detecting OOD nodes, that doesnt test it. This paper asks what "more data" means for node classification, where nodes are connected and a bigger graph is not just more independent samples. It grows a sequence of nested synthetic graphs from the same random recipe and asks that a method's uncertainty fall as the graph grows and settle on the best possible predictor. It argues that graph evidential models fail this test because their training settings fix how much uncertainty they report, and proposes ensembles trained on resampled copies of the graph (GB-Ens) instead. All of the growth evidence comes from two synthetic recipes, and the real benchmarks appear only in OOD tables.

Critical strengths
  1. Studying this on graphs is interesting. Growing nested graphs from one recipe is a reasonable way to define "more data" when nodes are connected. The test itself is just the definition of epistemic uncertainty and has been argued for in the i.i.d. setting, so the contribution is carrying it over to graphs.
  2. Crossing resampled graphs with training seeds is a nice experimental design choice. It splits epistemic uncertainty into a part from the data (disagreement across resampled graphs) and a part from training randomness (disagreement across seeds), and it is easy to reuse with other resampling schemes.
  3. The paper is reasonably well written. The test a method has to pass is stated precisely before any experiment, which makes the claims easy to check.
Critical weaknesses
  1. The ideas are validated on smaller/easier problems but never shown to work on real benchmarks. The growth experiment is on a dense synthetic graph with more than a thousand neighbors per node at ten thousand nodes, against roughly three to thirty-six on the real benchmarks. There, the resampling step picks each node's similar nodes using the hidden variable that generated the graph, which is also what generates the labels. This is not realistic for applications, so the method falls back on neighbor overlap (Jaccard similarity). GB-Ens is then less accurate than a plain deep ensemble in vast majority of dataset and backbone pairs.. The version that shows shrinking uncertainty can't be run on a real graph, and the version that can be run does worse. I'm not sure why the synthetic experiments were not rerun with the Jaccard version, or why growing subsets of OGBN-arXiv, or a larger graph like OGBN-Products, could not give a real growth sequence? The baselines are also narrow. Single-model epistemic methods for GNNs are not run through the growth protocol: G-ΔUQ (Trivedi et al., ICLR 2024) gets ensemble-like spread from one model by randomly shifting its inputs and is evaluated under graph-size shift, and GEBM (Fuchsgruber et al., 2024) adds an uncertainty score to an already trained GNN. Graph Gaussian processes (Ng et al., NeurIPS 2018) are also missing. If any of these also shrinks as the graph grows, the case for a hundred-model bootstrap ensemble is much weaker.

  2. On real graphs the resampling changes what the model sees. Each node keeps its label but gets a neighborhood borrowed from its most similar nodes. With neighbor overlap as the similarity, this cuts label homophily on CiteSeer from about 0.71 to 0.33 and lowers it on every real graph in table 5. The label is still correct, but the input that predicts it is noisier. That should inflate the ensemble's aleatoric uncertainty and lower its accuracy, consistent with the result in the table. The paper concedes the bootstrap loses fidelity on real graphs but does not connect this to either. The labeled set is also fixed across replicates, so uncertainty from which nodes happened to be labeled is never captured.

  3. The experiments check that uncertainty shrinks, but not that the model ends up on the right answer, though the paper's own test asks for both. On the synthetic graphs the best possible predictor and the true aleatoric uncertainty are both known exactly, and neither is compared against. The paper makes this argument against one of the evidential baselines but never applies it to GB-Ens. An ensemble that becomes confident in the wrong answer would pass every test reported here, and the reported leveling-off of aleatoric uncertainty could sit at the wrong value. The one related check, a distance to resampling from the true recipe, stays flat or grows as the graph grows, and I could not find how that reference is built.

  4. From what I could tell, the theory is not novel. As the paper itself says, it carries known i.i.d. results over to graphs: the main theorem is Shen et al. (NeurIPS 2024) with the graph in place of the inputs, and non-vanishing evidential uncertainty was shown by Bengs et al. (NeurIPS 2022) and Juergens et al. (ICML 2024). The "settles on the right answer" half of the test is posterior consistency, which is not cited.

Questions for authors

added a few above

14 comments
AuthorsOpenReview ↗

Response to Reviewer aG55 (1/8)

We thank the reviewer for their careful assessment and constructive feedback, as well as for recognizing the soundness and clarity of our work. We address the concerns raised below.

  1. The first question raised by the reviewer contains several distinct subquestions, which we address separately here.
    (a) Question: “I'm not sure why [...] growing subsets of OGBN-arXiv, or a larger graph like OGBN-Products, could not give a real growth sequence?”
    Answer: Standard node-classification benchmarks such as CoraML, CiteSeer, PubMed, AmazonPhotos, AmazonComputers, CoauthorCS, CoauthorPhysics, OGBN-Products, and OGBN-ArXiv are not directly suitable for instantiating our information-growth experimental protocol. The latter requires a well-defined graph sampling process, whose induced distributions are consistent under marginalization (projectibility; Shalizi & Rinaldo, 2013). Arbitrarily extracting nested subsets of a single observed graph does not establish that these subsets follow such a process.

    One alternative is to reconstruct an observed graph-growth sequence, but the benchmarks considered, except OGBN-ArXiv, do not provide sufficient information for this through their features or metadata. Although OGBN-ArXiv provides temporal metadata that could support reconstructing an observed growth sequence, this does not establish that the underlying DGP is projective, and additional methodological challenges remain. In particular, not all of its classes are represented in the earliest years, conflicting with our fixed-class assumption. Moreover, the benchmark's public temporal splits do not define nested learning problems and would need to be redesigned. The limited number of per-class observations in many early years further requires selecting an appropriate starting year to avoid unstable training and evaluation. These choices substantially alter the original benchmark and require careful justification.

    Consequently, constructing and validating an appropriate benchmark for real-world information-growth experiments warrants a dedicated research effort beyond simply extracting growing subsets of existing graphs. We will clarify this point in the paper.

    (b) Question: “The ideas are validated on smaller/easier problems but never shown to work on real benchmarks.” and “The growth experiment is on a dense synthetic graph with more than a thousand neighbors per node at ten thousand nodes, against roughly three to thirty-six on the real benchmarks.”
    Answer: We kindly disagree with the characterization of the synthetic benchmarks as inherently smaller or easier, as their size is comparable in terms of nodes, while their higher density implies substantially more edges and does not inherently make the learning task easier. Although their density differs substantially from that of real-world benchmarks, this distinction is orthogonal to our primary objective: investigating epistemic uncertainty under information growth. Accordingly, our synthetic benchmarks are designed to provide a controlled setting based on a projective DGP, rather than to reproduce the structural properties of real-world graphs.

AuthorsOpenReview ↗

Respose to Reviewer aG55 (2/8)

  1. The first question raised by the reviewer contains several distinct subquestions, which we address separately here.

    (c) Question: “There, the resampling step picks each node's similar nodes using the hidden variable that generated the graph, which is also what generates the labels. This is not realistic for applications, so the method falls back on neighbor overlap (Jaccard similarity). GB-Ens is then less accurate than a plain deep ensemble in vast majority of dataset and backbone pairs.. The version that shows shrinking uncertainty can't be run on a real graph, and the version that can be run does worse.”
    Answer: While GB-Ens generally achieves slightly lower ID accuracy than standard graph deep ensembles (G-Ens) on the OOD benchmarks, the differences remain relatively limited: on all datasets except OGBN-ArXiv, at least one GB-Ens backbone achieves ID accuracy within 3 percentage points of its G-Ens counterpart. On OGBN-ArXiv, the smallest gap is 5.8 percentage points.

    Nevertheless, accuracy alone does not determine the quality of epistemic uncertainty estimates: a highly accurate model may still fail to identify predictions for which its knowledge is insufficient. Reliable epistemic uncertainty quantification is essential for identifying when additional information or corrective actions are needed (Hullermeier & Waegeman, 2021). We therefore focus on assessing the quality of epistemic uncertainty estimates rather than maximizing predictive accuracy alone. In particular, our results show that G-Ens fails to exhibit epistemic uncertainty contraction under our information-growth protocol and does not capture an important source of epistemic uncertainty: parameter uncertainty arising from limited training data (Jimenez et al., 2026).

    Importantly, we emphasise the distinction between our controlled information growth experiments, which investigate the statistical behavior of epistemic uncertainty estimates, and our real-world node classification benchmarks, where uncertainty scores are evaluated for OOD detection. The latter do not provide a controlled information-growth setting in which contraction can be assessed, and OOD detection performance does not directly establish the quality of epistemic uncertainty estimation under our statistical framework.

    (d) Question: “I'm not sure why the synthetic experiments were not rerun with the Jaccard version”
    Answer: Since the synthetic experiments provide access to the latent variables, we chose to exploit this information to avoid introducing additional approximation error from estimating node similarity through Jaccard overlap. This allows us to investigate the epistemic behavior of GB-Ens under controlled information growth while limiting potential confounding factors, particularly given that the consistency of the resulting epistemic uncertainty estimators has not yet been established. We hypothesize that Jaccard-based GB-Ens exhibits similar epistemic behavior, although confirming this on synthetic DGPs would not establish that such behavior extends to real-world graph-growth sequences. Nevertheless, we acknowledge that this comparison provides a useful robustness assessment. We will provide the corresponding ablation by the end of the rebuttal period.

AuthorsOpenReview ↗

Response to Reviewer aG55 (3/8)

  1. The first question raised by the reviewer contains several distinct subquestions, which we address separately here.

    (e) Question: “The baselines are also narrow. Single-model epistemic methods for GNNs are not run through the growth protocol: G-ΔUQ (Trivedi et al., ICLR 2024) gets ensemble-like spread from one model by randomly shifting its inputs and is evaluated under graph-size shift, and GEBM (Fuchsgruber et al., 2024) adds an uncertainty score to an already trained GNN. Graph Gaussian processes (Ng et al., NeurIPS 2018) are also missing. If any of these also shrinks as the graph grows, the case for a hundred-model bootstrap ensemble is much weaker.”
    Answer: We would like to clarify the rationale behind our baseline selection. To the best of our knowledge, our baselines provide comprehensive coverage of the existing graph evidential deep learning (EDL) literature. This selection is deliberate: our paper does not aim to exhaustively evaluate all graph uncertainty quantification methods under information growth, but rather to provide a focused investigation of graph EDL approaches. These methods have played a central role in establishing widely adopted principles for the propagation of epistemic uncertainty through graph structure, instantiated through its reducibility with increasing feature and structural support and its reducibility or irreducibility under neighborhood conflict (Stadler et al., 2021; Damke & Hullermeier 2024a;b).

    While broader empirical comparisons are valuable, the suggested methods do not all address epistemic uncertainty estimation in the same sense. G-ΔUQ (Trivedi et al., 2024) primarily targets calibration under distribution shift rather than explicitly quantifying aleatoric and epistemic uncertainty. GEBM (Fuchsgruber et al., 2024) belongs to the broader family of energy-based models (EBMs), whose learning objectives have been theoretically connected to those of EDL, revealing shared limitations (Shen et al., 2024). This suggests that EBMs may also exhibit the limitations of EDL methods identified in our study, including their failure to appropriately represent epistemic uncertainty under information growth. A systematic characterization of these relationships and their implications for graph epistemic uncertainty estimation represents an interesting direction for future work. Finally, graph Gaussian Processes (Ng et al., 2018) represent a Bayesian approach, although the original work does not investigate the decomposition of predictive uncertainty into aleatoric and epistemic components. Thus, the cited works do not establish that the suggested methods exhibit the statistical properties investigated in our framework.

    Moreover, our focus is not solely on uncertainty contraction, but also on the representation and sources of epistemic uncertainty. Our contribution is not to establish that GB-Ens is the only estimator capable of uncertainty contraction, but to investigate graph resampling as an alternative to existing uncertainty representations. In particular, while evidential methods often rely on Bayesian-inspired principles, such as evidence pseudo-counts, that are not derived from the sampling variability of the training data (Stadler et al., 2021; Damke & Hullermeier, 2024a;b), bootstrap-based approaches explicitly account for this variability and have been advocated as a means of capturing sources of epistemic uncertainty beyond those represented by EDL models (Shen et al., 2024) and standard deep ensembles (Jain & Bates, 2026; Jimenez et al., 2026). This motivates investigating GB-Ens as a frequentist alternative to EDL, since uncertainty contraction alone does not establish that different estimators capture the same sources of epistemic uncertainty. We will make this motivation more explicit in the revised manuscript.

    Importantly, another main contribution of our paper is to establish a statistical framework for epistemic uncertainty under information growth on graphs, which can be reused and extended to investigate other uncertainty quantification methods, including those suggested by the reviewer. Our focused investigation of EDL also provides a foundation for extending this analysis to graph EBMs.

    Finally, we thank the reviewer for these additional suggestions. We acknowledge that the absence of a dedicated Related Work section in the original submission may have made the scope of our investigation and its relationship to the broader literature less clear. We will address this by including a dedicated Related Work section in the revised manuscript.

Comments on the paper

2 comments
AuthorsOpenReview ↗

Summary of the discussion (2/2)

Status of the discussion. Following the Jaccard-based ablation and correction of the OOD results, Reviewer aG55 acknowledged the encouraging results; their final comments focused on the relationship between EU trends, predictive accuracy, calibration, and asymptotic consistency. Reviewer 3WGG considered the focus on EDL methods and evaluation on synthetic graphs justifiable, while maintaining reservations about the breadth of the study. Reviewer U45f accepted our explanations of the uncertainty and predictive-performance trends, accepted consistency and bootstrap validity on real graphs as explicit limitations, and confirmed that their experimental and theoretical concerns were resolved, subsequently raising their score. These explanations and limitations are now reflected in the revised manuscript.

We believe the revised manuscript strengthens our central contribution: a principled statistical framework for studying epistemic uncertainty under information growth on graphs, applied to characterize graph EDL methods and investigate bootstrap ensembles as a complementary frequentist alternative.

We thank the reviewers and Area Chairs for their time and consideration.

AuthorsOpenReview ↗

Summary of the discussion (1/2)

We sincerely thank all three reviewers for their careful assessments, constructive feedback, and continued engagement throughout the discussion period. We particularly appreciate the recognition of the contributions of our work and the positive feedback on the additional experiments and clarifications provided during the rebuttal.

Main contributions recognized by the reviewers. Across the reviews, several important strengths of our paper were acknowledged:

  • Identification of a meaningful research gap: The importance of evaluating epistemic uncertainty under information growth, rather than relying exclusively on surrogate tasks such as OOD detection, which do not directly assess its reducibility, and the challenges of defining a principled information-growth process for graph-structured data.
  • Principled theoretical formulation: The introduction of a rigorous statistical framework for characterizing epistemic uncertainty and its coherence under information growth in graph node classification, based on projective graph data-generating processes.
  • Theoretical contributions to graph EDL: The meaningful extension of theoretical results from the i.i.d. setting to characterize the behavior of graph EDL methods under information growth, including mathematical explanations for their non-vanishing epistemic uncertainty.
  • Systematic experimental investigation: The controlled evaluation of epistemic uncertainty under information growth using graph sequences sampled from projective DGPs, enabling a principled comparison of uncertainty estimation methods.
  • Graph Bootstrap Ensembles (GB-Ens): The promising empirical results of GB-Ens as a frequentist approach to epistemic uncertainty estimation under information growth, together with their informative decomposition of epistemic uncertainty into graph-resampling and training-randomness components.
  • Clarity and soundness: The clear formulation of the evaluation criteria, the overall clarity of the manuscript, and the soundness of the investigation.

Additional experiments and results. In response to the reviewers' suggestions, we extended the experimental evaluation:

  • Jaccard-bootstrap ablation: We evaluated GB-Ens using bootstrap node similarity estimated exclusively from the observed graph, without access to latent coordinates. The results confirm EU contraction under information growth and show predictive quality comparable to latent-based GB-Ens.
  • Bootstrap and seed sensitivity analysis: We investigated the sensitivity of GB-Ens to the number of graph bootstrap replicates and training seeds, providing additional evidence on the robustness of its uncertainty estimates to the ensemble sampling design.
  • Predictive performance under information growth: We added size-wise accuracy, Brier scores, and confidence ECE for G-Ens and GB-Ens across the graphon sequences and GNN architectures, providing a complementary evaluation of predictive probability quality.
  • Corrected OOD results: We updated the OOD detection results using the corrected ensemble evaluation implementation.

Improvements to the manuscript. Beyond the additional experiments, we revised and clarified several aspects of the paper:

  • Scope and motivation: We strengthened the rationale for studying EDL and frequentist ensemble methods, clarified the sources of uncertainty they represent, and explained their relationship to the broader graph UQ literature and existing critiques of EDL and deep ensembles in the i.i.d. setting.
  • Challenges of real-world information-growth experiments: We explained the role of projectibility, how synthetic graph DGPs satisfy this requirement, and why arbitrarily extracting growing subsets of existing graph benchmarks does not establish a valid information-growth process.
  • Interpretation of uncertainty and predictive performance: We clarified why EU contraction alone does not establish convergence to the Bayes posterior predictive distribution, or improvements in accuracy and calibration. We also clarified how EU, accuracy, Brier score, and calibration can exhibit different, architecture-dependent trends under information growth, explaining why decreasing EU can coexist with seemingly counterintuitive trends in predictive performance and calibration.
  • Statistical distinctions between EDL and GB-Ens: We distinguished vanishing EU induced by graph-size-dependent regularization in EDL from contraction in bootstrap ensembles, emphasizing differences in their learning objectives and the sources of uncertainty they represent.
  • Mathematical accessibility: We clarified the statistical formulation of information growth, including nested graph sequences, projection operators, and projectibility, and made the connection between the theoretical framework and the synthetic graph DGPs more explicit and accessible to a broader audience.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.