- 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
Response to Reviewer 3WGG (2/3)
-
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.
-
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 , 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). -
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. -
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.
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.
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.
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′) denotes the larger graph observed at a subsequent stage, with V′ its node set and V⊂V′. We require that G is the subgraph of G′ induced by V, i.e., E={(u,v) ∈E′: u,v ∈V}. We will clarify this definition in the revised version of the paper.
Answer: The natural projection πB→A, for A⊂B, is the operation that maps an observation indexed by B to the corresponding observation indexed by A. For an attributed graph GB=(B, EB, XB, YB), this means retaining only the nodes in A, their attributes and labels, and the edges between them: πB→A(GB)=(GB[A], XB∣A, YB∣A), where GB[A] is the subgraph induced by A, and XB∣A, YB∣A denote the restrictions of node features and labels to A. We will clarify this definition in the revised version of the paper.
Answer: The notation πB→A−1 in Equation (7) denotes the preimage of a set under the projection, not an inverse function. Since πB→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 and χB denote the sample spaces of graph observations indexed by A and B, respectively. For any measurable set C⊆χA, πB→A−1(C)={GB∈XB:πB→A(GB)∈C}. In other words, the preimage contains all larger graphs whose restriction to A belongs to C. Consequently, Equation (7) PA,ϕ=PB,ϕ∘πB→A−1, means that PA,ϕ(C)=PB,ϕ(πB→A−1(C)) for every measurable C ⊆χA. This is precisely the projectibility condition: the distribution PA, ϕ coincides with the marginal distribution of PB,ϕ obtained by restricting the observations to the indices in A, for every A⊂B and ϕ∈Φ.
Answer: The parameter ϕ∈Φ indexes the underlying projective graph data-generating process, with GA∼PA,ϕ denoting the distribution of a graph generated on the node index set A. For example, in a graphon model, ϕ represents the parameters specifying the graphon function that governs graph generation. We will clarify its meaning in the revised version of the paper.
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.