Energy-based Epistemic Uncertainty for Graph Neural Networks

Authors: dominik  fuchsgruber
tom  wollschläger
stephan  günnemann
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 14:22:33

Abstract: In domains with interdependent data, such as graphs, quantifying the epistemic uncertainty of a Graph Neural Network (GNN) is challenging as uncertainty can arise at different structural scales. Existing techniques neglect this issue or only distinguish between structure-aware and structure-agnostic uncertainty without combining them into a single measure. We propose GEBM, an energy-based model (EBM) that provides high-quality uncertainty estimates by aggregating energy at different structural levels that naturally arise from graph diffusion. In contrast to logit-based EBMs, we provably induce an integrable density in the data space by regularizing the energy function. We introduce an evidential interpretation of our EBM that significantly improves the predictive robustness of the GNN. Our framework is a simple and effective post hoc method applicable to any pre-trained GNN that is sensitive to various distribution shifts. It consistently achieves the best separation of in-distribution and out-of-distribution data on 6 out of 7 anomaly types while having the best average rank over shifts on *all* datasets.

Main paper: 
 introduction: 
 Quantifying and understanding uncertainty is crucial to developing safe and reliable machine learning systems. Many applications such as Reinforcement Learning [42] , Active Learning [5, 31] or Outof-Distribution detection [60] benefit from disentangling different facets of uncertainty [54, 17, 46] . Typically, one distinguishes between an irreducible aleatoric component and reducible epistemic factors [29] . The former is inherent to the data, while the latter is rooted in a lack of knowledge. One way to quantify epistemic uncertainty is to define a classifier-dependent density over the data domain [55] . High values indicate similarity to the training data and thus imply low epistemic uncertainty. Energy-based models (EBMs) induce this density by defining an energy function that assumes low values near the training data [38] . A common choice is the logits of the classifier as their magnitude is supposed to correlate with the model confidence [40] . However, many architectures have been shown to produce arbitrarily overconfident predictions far from the training data [28] . The negative implications for logit-based EBMs are only scarcely discussed in the literature [35, 36] .While substantial effort has been directed toward uncertainty estimation for independent and identically distributed (i.i.d.) problems [1, 24, 49, 37, 6, 22] , graphs have only recently received attention within the community [71, 64, 67, 21] . There, uncertainty can arise at different structural scales, e.g., from only a single node, clusters, or global properties. Previous work only accounts for this implicitly by applying techniques from i.i.d. domains to Graph Neural Networks (GNNs) [67, 49] . A recent approach distinguishes only between structure-aware and structure-agnostic uncertainty [64] while not combining them into a single measure, which is often required in downstream applications [42, 54] . Consequently, estimates are often only sensitive to shifts that match their structural resolution. They may overfit certain anomaly types and not be reliable in general.Graph 𝒢 with Anomalies Figure 1 : Overview of the Graph Energy-based Model (GEBM). Graph-agnostic energy (uncertainty) of a trained GNN f θ (G) is first regularized to mitigate overconfidence and then aggregated at a local, cluster, and structure-independent scale by interleaving energy marginalization and graph diffusion. While group energy marginalizes before diffusion, local energy is fine-grained and can pick up conflicting evidence. GEBM assigns high uncertainty to several anomaly types simultaneously.We address these shortcomings and propose a novel graph-based EBM (GEBM) that is structureaware at different levels. The core idea behind GEBM is to define energy functions at different structural abstractions and facilitate the flexibility of the EBMs to aggregate them into a single, theoretically grounded measure. Interestingly, we find that interleaving a graph diffusion process with energy marginalization gives rise to energy functions that naturally capture patterns of different granularity. As depicted in Figure 1 , we utilize three energy types: (i) Group energy corresponds to evidence smoothing and emphasizes anomalies clusters within the graph while not distinguishing between their type locally. (ii) Local energy is more granular and sensitive to evidence disagreements in the neighborhood of a node. (iii) Independent energy is fully structure-agnostic and describes patterns that are limited to individual nodes. Aggregating them using soft maximum selection induces a single energy measure that assigns high uncertainty to anomalies at various scales. A Gaussian regularizer provably ensures that GEBM converges to low confidence far from the training data.We evaluate GEBM over an extensive suite of datasets, distribution shifts, and baselines 1 . It consistently exhibits state-of-the-art performance in detecting out-of-distribution (o.o.d.) instances, while other approaches are only effective in a subset of settings. On all datasets, GEBM ranks the best on average over all distribution shifts. Beyond o.o.d. detection, we discover a novel theoretical connection between EBMs and evidential models. This interpretation of GEBM enables the GNN backbone to provide accurate predictions even under severe distribution shifts.In summary, we tackle three main deficiencies of energy-based uncertainty for graphs by: 1. Proposing GEBM, an EBM that is aware of interdependence and provides a single uncertainty estimate incorporating different structural scales.2. Formally showing that a Gaussian regularizer mitigates the overconfidence problem of logit-based EBMs and enables GEBM to provably induce an integrable data density.3. Showing how to interpret GEBM as an evidential approach which considerably improves the predictive robustness of the classifier under distribution shifts. 
background: 
 Semi-Supervised Node Classification. We consider (semi-supervised) node classification on an attributed graph G = (A, X) with n nodes V and m edges E that is represented by an adjacency matrix A = {0, 1} n×n and a node feature matrix X ∈ R n×d . Each node has a label y i ∈ {1, . . . C}.Given the labels of training nodes, the task is to infer the labels of the remaining nodes. Lastly, we focus on homophilic graphs, i.e. edges are predominantly present between nodes of the same class.Uncertainty in Machine Learning. Usually, uncertainty regarding the prediction of a model is disentangled into aleatoric and epistemic factors u alea and u epi , respectively. The former encompasses irreducible sources of uncertainty like measurement noise and inherent ambiguities. The latter is commonly defined as the non-aleatoric components of the overall uncertainty and can in general, be reduced, for example by acquiring additional data.Energy-based Models. Epistemic uncertainty is commonly defined to be anti-correlated to a classifier-dependent density p θ (x) over the input space [55] . We study Energy-based Models (EBMs) [38] which define a joint energy E θ (x, y) over features and labels p θ (x, y) ∝ exp (-E θ (x, y))).Marginalization over the labels induces a feature density with normalizer Z θ .EQUATIONIntuitively, the energy E θ (x) = -log y exp (-E θ (x, y)) can be interpreted as a soft minimum of the joint energies. It is low in regions of high confidence and high elsewhere. The measure of epistemic uncertainty implied by an EBM therefore is: u epi (x) = -log p θ (x) = E θ (x) + const. We can also write the conditional class probabilities as:EQUATIONThis is exactly the softmax distribution applied to -E θ (x, y) which directly connects the logits f θ (x) ∈ R C predicted by a classifier to the joint energy by defining E θ (x, y) := -f θ (x) y [40] .Evidential Deep Learning. In contrast to first-order methods that directly predict p(y | x), evidential methods [62, 43] instead parameterize the corresponding second-order distribution from which firstorder distributions are sampled [32] . In classification, this second-order distribution is a Dirichlet distribution with parameters α > 0 called evidence. They indicate the confidence of the classifier.For inference, a first-order prediction can be obtained by taking the expectation:EQUATION3 Related Work Uncertainty Estimation for i.i.d. Data. Disentangling uncertainty has been approached from various perspectives. A family of sampling-based approaches uses a Bayesian Information-theoretic framework [29] that relies on stochastic predictions derived from a posterior over model weights.The total uncertainty is defined on the mean predictor, epistemic uncertainty as the deviation of each sample from that mean, and aleatoric uncertainty as the difference of both estimates [1] . The posterior can either be explicitly modeled by Bayesian Neural Networks (BNNs) [6, 13, 15, 18] , Monte-Carlo Dropout (MCD) [22] , or implicitly realized by ensemble methods [37, 77] . Test-time augmentation [72, 73] and Stochastic Centering [66] also provide samples from this posterior. Sampling-free approaches are deterministic and estimate uncertainty with a single forward pass. Evidential methods [62, 68] predict a second-order distribution from which epistemic uncertainty is derived. Distancebased approaches quantify epistemic uncertainty as similarity to the training data [46, 48, 20, 65] and are closely related to density-based uncertainty estimation. (Deep) Gaussian Processes (GPs) [52, 45, 39] use a kernel function to measure this similarity but do not disentangle epistemic and aleatoric uncertainty. Posterior Networks combine evidential and density-based approaches by predicting density-based updates to the evidence [11, 10] .Uncertainty Estimation for Graphs. Many of these approaches transfer to graphs: DropEdge [59] applies MCD to edges and GPs can utilize a structure-aware kernel [53, 83, 41, 60] . SGCN [82] proposes an evidential student-teacher approach while G-∆UQ [67] applies Stochastic Centering to a GNN and improves on calibration. Graph Posterior Network (GPN) [34] diffuses the densitybased evidence of a Posterior Network but provides separate measures for structure-aware and structure-agnostic uncertainty, each of which is only effective on some distribution shifts.Energy-based Models. EBMs [38, 3, 2] are typically employed in generative modelling [14] but have also been applied to uncertainty estimation [16] and anomaly detection [40, 81] . To address the overconfidence of logit-based EBMs far from training data, a Gaussian regularization term has recently been proposed [35] that we employ in our framework as well. While their work empirically validates this adjustment, we formally prove the overconfidence of logit-based EBMs to happen with high probability and Gaussian regularization to mitigate the issue. The HEAT framework [36] learns multiple corrected EBMs via stochastic gradient Langevin dynamics [76] and composes them into a single measure. In contrast, our approach does not require additional training and aggregates energy that emerges naturally at different scales in the graph from a single logit-based joint energy model. Lastly, GNNSafe [79] diffuses the logit-based energy of a GNN to improve its out-of-distribution detection. In contrast, our model considers energy beyond the cluster scale.Here, we show that local energy (Equation ( 5)) and group energy (Equation ( 6)) induce a valid probability density when using a linear diffusion operator P A and regularized energy according to Equation (8) . Note that independent energy (Equation ( 4)) is shown to induce a well-defined probability density as it is just a graph-independent regularized energy. Proposition A.2.1. For a linear diffusion operator P A (x) = αx + const, α > 0 and the regularized energy Êθ (x, y), the local energy ÊL (x) induces a well-defined density:X exp(-Êθ,L (x))dx < ∞ Proof.Êθ,L (x) = -logy exp P A -Êθ (x, y) = -log y exp -α Êθ (x, y) + const ≥ -log y exp -αx T Σ -1 x + const = αx T Σ -1 x + const + log C ≥ x T Σ ′ -1 *x Again, we absorbed the constant terms as well as α into the quadratic term for large enough ∥x∥ 2 and used the quadratic bound from Theorem 4.2. From here, it is straightforward that:X exp -Êθ,L (x) dx ≤ const + X exp -x T Σ ′ -1 * x dx < ∞ Proposition A.2.2.For a linear diffustion operator P A (x) = αx + const, α > 0 and the regularized energy Êθ (x, y), the group energy ÊG (x) induces a well-defined density:X exp(-Êθ,G (x))dx < ∞ Proof. Êθ,G (x) = P A Êθ (x) = α Êθ (x) + const ≥ αx T Σ -1 * x + const ≥ x T Σ ′ -1 * xAgain, we have used the quadratic bound of Theorem 4.2 and absorbed α > 0 for large enough ∥x∥ 2 .From there, it follows:X exp -Êθ,G (x) dx ≤ const + X exp -x T Σ ′ -1 * x dx < ∞Remark. We want to point out that most diffusion operations, especially the ones discussed in Appendix C.6 including the label-propagation smoothing used in our experiments, are of the form P A (x) = αx + const with α > 0. Since we only integrate over the features of a single node and keep all other features fixed, all of these diffusion processes can be expressed as a weighted sum over nodes in the graph. Since we consider unweighted graphs, there are no negative edge weights which ensures that α > 0 (as long as some sort of self-loop is included). Therefore, linear diffusion processes can be seen as positive affine transformations. Theorem 4.4. For a linear diffusion operator P A (x) = αx + const, α > 0 and the regularized energy Êθ (x, y), GEBM induces a well-defined density:X exp -Êθ,GEBM (x) dx < ∞ Proof.We previously established quadratic bounds on all three constituents of the aggregate energy for large enough ∥x∥ 2 :Êθ,I (x) ≥ x T Σ -1 I x Êθ,L (x) ≥ x T Σ -1 L x Êθ,G (x) ≥ x T Σ -1 G xHence, there must be oneΣ -1 * ∈ {Σ -1 I , Σ -1 L , Σ -1G } that bounds all three energy types. We now look at the GEBM model: Êθ,GEBM (x) = log exp Êθ,I (x) + exp Êθ,L (x) + exp Êθ,G (x)≥ log 3 * exp x T Σ -1 * x = x T Σ -1 * x + log 3 ≥ x T Σ ′ -1 * xAs before, this bounds the density induced by GEBM:X exp -Êθ,GEBM (x) dx ≤ const + X exp -x T Σ ′ -1 * x dx < ∞Remark. This directly imposes a restriction on which energies can be included in GEBM beyond the three naturally arising graph-specific terms we propose: As long as the energy term can be bounded by an energy that grows fast enough to ensure convergence, our framework accommodates it.We also can explicitly write out the (unnormalized) GEBM density p θ,GEBM (x) in terms of its constituents p θ,I (x), p θ,L (x) and p θ,G (x). We use eight datasets in this work that we expose to similar kinds of distribution shifts. For CoraML, we also create a version that uses continuous word embeddings instead of categorical bag-of-word features. We use the all-MiniLM-L6-v2 sentence transformer provided by Hugging Face [78] to embed the abstracts that are provided for each paper (node) in the citation network. All datasets are taken from PyTorch Geometric [19] . They are licensed as C.C.0 1.0 (CoraML, CoraML LLM), C.C. Attribution-NonCommercial-Share Alike 3.0 (Citeseer), OdbL 1.0 (PubMed).p θ,GEBM (x) ∝ 1 p θ,I (x) -1 + p θ,L (x) -1 + p θ,G (x) -1We expose each dataset to the same distribution shifts which can be categorized into three families:(i) Leave-out-Classes. We pre-select a subset of classes and designate them as out-of-distribution.That is, we remove them from the training set and train the GNN on the remaining set of nodes. We focus on an inductive setting, where we also remove all edges linking o.o.d. left-out-class nodes to the training graph, thus preventing information leakage. In the transductive setting, o.o.d. nodes still contribute to the training signal as they may be connected to i.d. nodes. This distribution shift can be seen as occurring on a cluster level, as we introduce anomalous nodes that are likely to cluster together. We distinguish between two kinds of selection processes for the classes to be left out: We either pick the last classes in the dataset (LoC (last)) or choose classes with the most heterophilic connection pattern, which distinguishes them even further from i.d. classes (LoC (hetero.)).(ii) Feature Perturbations. We select 50% of nodes at random to be o.o.d. and perturb their features by replacing them with random noise. We distinguish between three perturbation types that control the similarity of node features to training data: We generate features that are similar to i.d. data (near-o.o.d. in the following way: For each of the d features, we compute how frequent it occurs in the dataset. We then proceed to sample each of these features independently with the corresponding success probability p from a Bernoulli Ber( p). Instead, we can also set the success probability to p = 0.5 for each of the features and induce a more severe distribution shift within the bag-of-words domain of the dataset. Lastly, when sampling features according to a normal distribution N (0, 1 Remarks regarding Page Rank Shifts. We study the centrality-based shift (which heavily correlates with a degree-based shift) for completeness reasons as a similar generation process is used in [79] . However, to which extent methods should be expected to assign high uncertainty to low-degree nodes is questionable: First, centrality and/or degree are feature-irrespective quantities. In contrast to homophily (nodes of similar classes have similar features), the confidence of a classifier may not (and should not) depend on the node degree/centrality. Furthermore, many baselines use symmetric normalization (Appendix C.6) that inherently favors high-degree nodes. Therefore, an evaluation regarding node degree/centrality as a distribution shift will not test the quality of an uncertainty measure but instead favor all models that use appropriate diffusion processes for most baselines. Regardless of our concerns regarding a centrality-based shift, we report results regarding that shift as well in Appendix C. Note that while GEBM is not among the best-performing estimators in this setting, it still achieves the highest average o.o.d. detection rank overall, indicating that its merits in all other settings heavily outweigh its performance on the Page Rank shift. 
method: 
 We develop a simple yet effective Graph-Energy-Based Model (GEBM) for post hoc epistemic uncertainty that is sensitive to a variety of distribution shifts from any pre-trained GNN.Previous work either does not distinguish between uncertainty at different structural resolutions at all [79] or only disentangles structure-aware and structure-agnostic factors without combining them [64] . However, for many practical purposes, epistemic uncertainty must be quantified with a single measure [42, 5, 60] . We address these issues by proposing an EBM-based uncertainty that incorporates patterns on different natural abstractions of a graph. The density induced by GEBM, p θ (x), serves as a singular uncertainty measure that is sensitive to multiple distribution shifts simultaneously.Inspired by the success of graph diffusion [9, 23] , we propose energy on different structural levels: (i) Graph-agnostic, for node features in isolation. (ii) Based on the evidence in the local neighborhood of a node. (iii) Within clusters in the graph. Note that defining global energy on the whole graph induces no differences at the node level and therefore we do not consider it in this work. We point to appropriate measures for a potential extension of GEBM in the existing literature [84] .We make the intriguing observation that interleaving a diffusion process P A : R k → R k with the marginalization of structure-agnostic joint energy E θ (x, y) as in Equation (1) induces energy functions that describe the aforementioned natural abstraction levels. Based on this insight, we can derive definitions for three types of energy functions:Independent Energy. On the finest scale, we consider energy independent of structural effects by omitting the diffusion operator. This term captures uncertainty regarding node features in isolation.E θ,I (x) = -log y exp (-E θ (x, y))Local Energy. On a coarser scale, we diffuse the joint energy before marginalization. This retains local information like conflicting feature-based evidence within the neighborhood of a node as the class-specific information is marginalized after propagation:EQUATIONGroup Energy. By interchanging marginalization and diffusion, we effectively smooth the marginal evidence E θ (x). Therefore, energy gets propagated predominantly within clusters of the graph.EQUATIONSince marginalization is done before propagation, less local information is preserved: The energy of a node will increase when its cluster is anomalous, regardless of whether the type of anomaly matches its own. As can be seen exemplary in Figure 1 , this loss of local information comes at the benefit of being less exposed to local variability within coarser clustered patterns.Each energy type captures anomalies that affect the corresponding structural scale. We provide synthetic experiments in Appendix C.7 as an additional intuitive explanation for the aforementioned energy terms. In practice, GEBM enables practitioners to augment our framework with further, potentially task-specific, energy functions. We empirically find however that the combination of the three naturally arising energy terms already detects a broad range of distribution shifts.Following Equation (1) , EBMs imply a density over the data domain p θ (x) with normalization constant:EQUATIONWhen quantifying epistemic uncertainty with this density, the energy must be low in regions of the input feature space close to the training data, while high values should be assumed far away. To that end, p θ (x) must be integrable, that is, have a finite normalizer Z θ . However, previous work has shown that piecewise affine classifiers which are the backbone of modern GNNs will converge to overconfident logits far from training data [28] . We remark that previous studies found GNNs to be underconfident on in-distribution data [74, 75] while the aforementioned issue of overconfidence arises from high distance to training data induced by a distribution shift (see Appendix C.8). This overconfidence is problematic, as logit-based energy can suffer from the same issue and E θ (x) may assume arbitrarily small values far from the training data. This contradicts the aforementioned desideratum of low confidence and the implied uncertainty measure breaks under severe distribution shifts. The normalizer of the logit-based joint energy Z θ is not finite with a high probability and therefore the EBM can not induce an integrable density p θ (x). Proposition 4.1. Let f θ : R d → R C be a piecewise affine function and R h = L l Q l be the disjoint set of polytopes on which f θ is affine, i.e. f θ (x) = W (l) x + b (l) for x ∈ Q l . Assuming the direction of the rows of each W (l) to be uniformly distributed, the probability that Z θ converges decreases exponentially in the number of non-closed linear regions L ′ and classes C.Pr [Z θ < ∞] = (1/2) C•L ′We provide proofs for all claims in Appendix A. Intuitively, since f θ behaves like an affine function in the limit ∥x∥ 2 → ∞, its predicted logits may diverge toward ∞. If for any class the model produces overconfident predictions in one of its affine regions, the marginal energy E θ (x) will diverge toward maximal confidence. As classifiers are trained to output high values for one of the classes, we expect the actual probability of a well-behaved energy function to be even lower than our theoretical bound that assumes uniform weight directions. In practice, this pathological behavior of logit-based EBMs has been observed in previous work [64, 36, 35] . We mitigate this issue by augmenting the logit-based energy and we prove that this regularization induces an integrable density.Similarly to recent work on EBMs [35] , we employ a class-conditional Gaussian prior N (f θ (x) y | µ y , Σ y ) as a regularizer for the logit-based energy. We learn the parameters {µ y , Σ y } C y=1 as the maximum likelihood estimates from the training instances of each class.EQUATIONThe regularization strength γ > 0 and the choice of the diffusion operator P A are the only hyperparameters of GEBM. Each of them has an intuitive interpretation: γ controls the trade-off between the predictive dependency and distance-awareness of the EBM while P A encapsulates how information is propagated over G. Regularization ensures that the corresponding marginal density pθ (x) has a finite normalizer Ẑθ and is therefore integrable. Theorem 4.2. For a piecewise affine classifier f θ as in Proposition 4.1, pθ is well-defined.X y exp(-E θ (x, y)) N (f θ (x) y | µ y , Σ y ) γ dx < ∞ This regularized joint energy diverges toward maximal uncertainty in the limit. Consequently, its induced density provides an uncertainty estimator that is reliable even far away from the training data. We then combine the regularized energy Êθ (x, y) at different structural scales (Equations ( 4) to ( 6)).Êθ,GEBM (x) = log exp Êθ,I (x) + exp Êθ,L (x) + exp Êθ,G (x)Since energy is defined per node, most diffusion processes (Appendix C.6) act on individual nodes as an affine function with a positive coefficient (see Appendix A.2). Therefore, each individual energy and their aggregate, Êθ,GEBM , induce an integrable density when using a linear diffusion operator P A .Theorem 4.4. For a linear diffusion operator P A (x) = αx + const, α > 0 and the regularized energy Êθ (x, y), GEBM induces an integrable density:X exp -Êθ,GEBM (x) dx < ∞GEBM is lightweight and can be applied post hoc to any logit-based GNN without additional training. Its induced density is a proxy for epistemic uncertainty: u epi (x) = -log pθ (x) and we compute aleatoric uncertainty as the entropy of the predictive distribution of the GNN [29] . Following [79] , we realize the diffusion operator as a repeated application of a label-propagation scheme (see Appendix C.6). Intuitively, this operator is a smoothing process which is only appropriate when assuming the in-distribution data to be homophilic. In the case of non-smooth (heterophilic) training data, the proposed energy would be high for in-distribution data which is undesired behaviour for an EBM-based uncertainty estimator. To disentangle effects at different structural scales, we define each of GEBM's components on structure-agnostic regularized joint energies Êθ (x, y). To that end, we compute the outputs of the classifier by omitting the structure for the computation of Êθ only by evaluating f θ (I, X), i.e. setting A = I. These outputs depend only on the node features.Beyond using epistemic uncertainty to detect anomalies, we also show how the joint density induced by GEBM enables predictions that are robust against distribution shifts. First, we discover a correspondence between first-order predictions of logit-based classifiers (Equation ( 2)) and evidential predictions (Equation ( 3)). This connects the joint energy E θ (x, y) of an EBM to the evidence α:EQUATIONFor an integrable density p θ (x, y), the evidence α will vanish in the limit far away from training data. Previous work on Posterior Networks [11, 10] fits a normalizing flow to obtain class-conditional densities p θ (x | y) and uses them to compute a Bayesian update to a prior evidence α prior . Its extension to graphs, GPN [64] , diffuses these structure-agnostic updates with an operator P A . Similarly, our GEBM framework induces a normalized joint density pθ (x, y) through its regularized energy function at no additional cost. Therefore, it can also be interpreted as an evidential classifier that enables inference according to Equation (3).GPN [64] (Evidential)α post = α prior + P A (N * p θ (x, y)) GEBM (ours) α post = α prior + P A Z -1 θ * exp(-Êθ (x, y)Here, N is called an uncertainty budget and it roughly corresponds to the normalizer of the joint energy. This interpretation of EBMs recovers desirable properties of density-based evidential methods [11, 64] : Predictions will converge toward a prior α prior far from the training distribution. They will be less affected by anomalies in the neighborhood of a node and therefore be more robust against distribution shifts. We remark that while our framework enables this evidential inference scheme, it is also possible to instead use the backbone classifier as-is and preserve its predictive performance. 
experiments: 
 We evaluate the efficacy of GEBM by extending the evaluation proposed in [64] and expose it to a suite of 7 distribution shifts from three families that cover a broad range of anomaly types.Datasets and Distribution Shifts. We use seven common benchmark datasets for node classification:The five citation datasets CoraML [4] , CoraML-LLM [4, 78] [4] , Citeseer [61, 25] , PubMed [51] ,Coauthor-Physics and Coauthor-Computers [63] , and the co-purchase graphs Amazon Photos and Amazon Computers [44] . We expose all methods to three families of distribution shifts:(i) Structural. We select nodes with the lowest homophily as o.o.d. and train on homophilic nodes only. This induces a shift in the local connectivity pattern of the nodes. Furthermore, we include a setting in which nodes with low Page-Rank (PR) centrality [56] are considered o.o.d. (ii) Leave-out-Class. We withhold nodes belonging to a subset of classes during training and reintroduce them during inference. In practice, this might, for example, correspond to a new type of user joining a social network. We either select the held-out classes randomly or pick those with the lowest average homophily to make them more dissimilar to the retained classes. (iii) Feature Perturbations. We randomly choose a subset of nodes and perturb their features by replacing them with noise. Since most datasets have categorical bag-of-words features, we have fine-grained control over the severity of the shift in this setting. Model and Baselines. We compare GEBM to different baselines for (epistemic) uncertainty estimation: Ensembles (GCN-Ens), MC-dropout (GCN-MCD), DropEdge (GCN-DropEdge), a combination of MC-dropout and DropEdge (GCN-MCD+DropEdge) and a Bayesian GCN (BGCN) are sampling-based approaches. We also compare against the logit-based EBM (GCN-Energy), GNNSafe, and HEAT as EBM baselines. Lastly, we consider GPN and SGCN as evidential methods. For all models, including GEBM, we use the same backbone architecture (see Appendix B.2).Metrics. We evaluate epistemic uncertainty by detecting distribution shifts. That is, we report the AUC-ROC and AUC-PR metrics for the binary out-of-distribution detection problem of separating in-distribution (i.d.) from out-of-distribution (o.o.d.) nodes. Additionally, we report how well uncertainty correlates with erroneous (misclassification detection) in Appendix C.3. Since our proposed method does not alter the softmax predictions of the backbone model, it will affect neither the aleatoric estimates nor their calibration. Consequently, our framework is open to additional post hoc calibration methods such as temperature scaling [26] . For completeness, we report the Expected Calibration Error (ECE) [50] and the Brier score [7] in Appendix C.4 for the GNN backbone.Out-of-Distribution Detection. Table 1 shows the performance of different aleatoric and epistemic uncertainty methods on various distribution shifts (full results in Table 6 ). Across all datasets and distribution shifts, our model provides the best or second-best separation of o.o.d. data from i.d. data. In practice, an estimator that is effective on all distribution shifts simultaneously is desirable. Therefore, we rank (↓) all estimators individually for each shift and dataset and report its average rank over all distribution shifts for each dataset. To not favor one distribution shift family, we adjust the weight such that Leave-out-Class, structural shifts, and feature perturbations contribute the same amount. We rank all epistemic uncertainty proxies both against other epistemic measures and aleatoric uncertainty separately. In both cases, Tables 2 and 7 show that our proposed EBM-based epistemic uncertainty is the only estimator that is effective under different distribution shifts at the same time. On all datasets, GEBM improves the AUC-ROC scores by 5.8 to 10.9 percentage points on average (16%-32% relative improvement) over a vanilla EBM, the second best-ranked estimator (Appendix C.2). Since all EBM-based approaches (GCN-EBM, GCNSafe, GEBM) are post hoc methods, they share the aleatoric uncertainty and high predictive accuracy of the backbone.Out of all 7 distribution shifts, our framework is only less sensitive to the centrality shift. Many baselines only perform well because of their symmetric diffusion operator that biases any arbitrary GCN-GEBM 2.7 / 4.5 2.9 / 4.9 3. While this bias could be explicitly incorporated into GEBM by defining an additional energy term, the goal of our work is not to engineer our measure toward certain downstream settings. GEBM is already sensitive to many distribution shifts as-is. Even after accounting for this setting, our estimator achieves the best average rank over all shifts. We defer further discussion to Appendix B.Misclassification Detection. In alignment with previous work [64] , we observe aleatoric uncertainty to be more effective for misclassification detection than epistemic estimates. Our method performs competitively among other epistemic measures as shown in Table 16 . As previously discussed, improving aleatoric uncertainty for GNNs is beyond the scope of this work.Robust Evidential Inference. As described in Section 4.4, GEBM enables evidential inference. We expose our model to feature shifts sampled from N (0, 1) and increase the fraction of perturbed nodes.Figure 2 shows the predictive performance of the classifier induced by an evidential interpretation of the EBM at different regularization weights γ compared to a vanilla EBM and the evidential model, GPN. We maintain high accuracy like an evidential model, while the performance of the baselines rapidly deteriorates. The hyperparameter γ can be seen as interpolating between an unregularized overconfident logit-based EBM and an uncertainty-aware evidential method. While GPN requires explicit evidential training, our method enables robust inference at negligible additional cost from a pre-trained GNN. Furthermore, GPN notably sacrifices predictive capability on clean data, while GEBM enables more control over the trade-off between accuracy on clean and perturbed data. The advantage of this evidential perspective is that the evidence approaches zero under increasingly severe distribution shifts. Therefore, a fixed number of diffusion steps suffices to effectively counteract the influence of anomalous neighbors when making predictions for a node. In contrast, using diffusion at, for example, the predictive level is inadequate: As shown in Proposition 4.1, the energy is likely to diverge and, therefore, the number of diffusion steps necessary to mitigate arbitrarily severe distribution shifts is unbounded. Consequentially, we find that even compared to models like APPNP that heavily rely on graph diffusion at the predictive level, the evidential interpretation of GEBM notably improves robustness (see Figure 6 ). GEBM combines the benefits of energy at different scales and ranks best over splits.Energy at Different Scales. In Table 3 , we compare GEBM to energy at specific structural scales and a variant without regularization (γ = 0). Each of the former corresponds to one of the energies that the GEBM framework is composed of. Group energy is equivalent to a regularized logit-based EBM which is therefore also ablated implicitly. As expected, each component is sensitive to different shifts. This confirms that interleaving marginalization and diffusion captures patterns at different resolutions. As shown in Table 26 , a variant of the aggregate GEBM achieves the best rank on 7 of 8 datasets. This shows that scale-awareness is the key ingredient for effective uncertainty estimation on graphs which can be further improved with energy regularization. In far-o.o.d. settings, this regularization is crucial to obtain reliable estimates as it mitigates overconfidence issues. Energy Regularization. We also ablate the effect of regularizing the joint logit-based energy in Figure 3 . At increasing distance from the training data, logit-based energy becomes overconfident. In contrast, the regularized Êθ follows the logit-based energy near the training data and is dominated by the regularizer far away. This is reflected in the clear separation between perturbed and unperturbed nodes. When computing structure-aware energy, feature corruptions affect unperturbed nodes through the diffusion operation, making a clean separation difficult. This justifies our choice to compute structure-agnostic joint energy Êθ (x, y) and factor in the graph afterward by applying P A .Backbone Architecture. Our method can be applied post hoc to any logit-based GNN. [34] , GAT (v2) [70, 8] , GIN [80] and GraphSAGE [27] .Standard deviations and AUC-PR are reported in Appendix C.5. Over different distribution shifts, our proposed approach consistently outperforms the logit-based EBM and the graph-specific GNNSafe variation. This shows the broad applicability of our framework that enables reliable high-quality epistemic uncertainty estimation from a large family of logit-based GNNs. 
limitations and broader impact: 
 Limitations. As GEBM is a post hoc epistemic estimator, it does not improve aleatoric uncertainty or its calibration. In particular, the GCN backbone used in this work does not consistently achieve the strongest performance in both tasks. While the structural scales that arise naturally from graph diffusion cover many distribution shifts as-is, specific applications may require augmenting GEBM with additional energy terms, as we also observe for centrality-based shifts. While GEBM enables robust evidential inference, future work may build upon its paradigm of aggregating different structural scales in the graph for fully evidential methods. Lastly, we study homophilic node classification problems and leave an extension of GEBM beyond this setting to future work.Broader Impact. GEBM enables cheap and simple uncertainty quantification for GNNs which we believe to contribute to the development of more reliable AI. Nonetheless, we encourage practitioners to actively reevaluate our measure of uncertainty to mitigate risks in safety-critical domains. 
conclusion: 
 We propose GEBM, a simple and efficient EBM for post-hoc epistemic uncertainty estimation for GNNs. To the best of our knowledge, we are the first to consider uncertainty at different structural scales and address this gap by proposing a model that aggregates energy that naturally arises from graph diffusion. It consistently outperforms existing approaches over an extensive suite of datasets at detecting various distribution shifts. We formally and empirically confirm that logit-based EBMs suffer from overconfidence and prove that the regularized GEBM mitigates this issue by inducing an integrable data density. We exploit this property by discovering a link to evidential methods that enables the backbone to provide accurate predictions even under severe distribution shifts. 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] Justification: We do not believe that model has an increased risk for misuse. We encourage users for active evaluation of the uncertainty provided in Section 6. Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained? Answer: [NA] Justification: Our paper does not involve crowdsourcing nor research with human subjects. Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: A.1 EBMs for i.i.d. DataWe first consider proofs for formal statements regarding logit-based EBMs in general (i.e. for i.i.d. data).Proposition 4.1. Let f θ : R d → R C be a piecewise affine function and R h = L l Q l be the disjoint set of polytopes on which f θ is affine, i.e. f θ (x) = W (l) x + b (l) for x ∈ Q l . Assuming the direction of the rows of each W (l) to be uniformly distributed, the probability that Z θ converges decreases exponentially in the number of non-closed linear regions L ′ and classes C.Pr [Z θ < ∞] ≈ (1/2) C•L ′Proof. Consider an arbitrary direction x ∈ R d such that ∥x∥ = 1. As shown in [28] (Lemma 3.1), there exists some t and α 0 such that for all α > α 0 it holds that αx ∈ Q t . We have f θ (αx) = W (l) αx + b (l) , and therefore:-E θ (αx, y) = W (l) y αx + b (l) yWe now distinguish between two cases as α → ∞:If W (l)y x ≥ 0, we have:lim α→∞ αW (l) y x = ∞ lim α→∞ αW (l) y x + b (l) y = ∞ lim α→∞ E θ (αx, y) = -∞ And conversely if W (l)y x ≤ 0, we have:lim α→∞ E θ (αx, y) = ∞Since we assumed the direction of W (l) y to be uniformly distributed, both cases occur with probability 0.5. Now we consider the marginal energy assigned to αx:E θ (αx) = -log y exp (-E θ (αx, y)) ≤ α min y {-E θ (x, y)}We now analyze when the marginal energy E θ (αx) diverges toward ∞ and -∞ respectively. If for any y ∈ {1, . . . , C} we have that W (l) y x ≤ 0, then:lim α→∞ E θ (αx) ≤ lim α→∞ α min y {E θ (x, y)} = -∞ Since each W (l)y x > 0 with probability 1/2, the limit diverges toward -∞, with probability at most (1/2) C . Now consider some open set Q (l) with a non-zero measure for over which the classifier f θ is linear. With probability at least 1/2, for x ∈ Q (l) , f θ diverges toward ∞.We now can consider the integral over the unnormalized density implied by f θ :Z θ = R d exp(-E θ (x))dx = l Q (l) exp(-E θ (x))dxFor any open region Q (l) , the energy will diverge toward -∞ with probability (1/2) C and therefore:Q (l) exp(-E θ (x))dx = ∞For Z θ to be finite and well-defined, the integral over all L ′ open linear regions with non-zero measures need to converge simultaneously, each of which happens independently with probability (1/2) C . Therefore:Pr [Z θ < ∞] = (1/2) C•L ′Remark. Note that the assumption that the rows of each W (l) have a uniformly distributed direction is given when initializing the model from a normal distribution. When training a classifier with the commonly used cross-entropy objective, the training incentivizes the model to assign high logits to exactly one of the classes for each datapoint. Therefore, the model is intuitively encouraged to have at least one row of W (l) for which the x that are in the corresponding regionQ (l) have positive projection W (l) y x > 0.In practice, we expect that for a trained model the probability of any x to have a negative projection onto all rows of the corresponding W (l) to be lower than (1/2) C . Theorem 4.2. For a piecewise affine classifier f θ as in Proposition 4.1, pθ is well-defined.Ẑθ = X y exp(-E θ (x, y)) N (f θ (x) | µ y , Σ y ) γ dx < ∞Proof. We consider the corrected joint energy Êθ (αx, y) for some sufficiently large α > α 0 and an arbitrary direction x ∈ R d .Êθ (αx, y) = E θ (αx, y) -γ log N (f θ (αx) y | µ y , Σ y ) = -f θ (αx) y + γ 2 (f θ (αx) y -µ y ) T Σ -1 y (f θ (αx) y -µ y ) + const = -W (l) y αx -b (l) y + γ 2 (W (l) y αx + b (l) y -µ y ) T Σ -1 y (W (l) y αx + b (l) y -µ y ) + constFor large enough α 0 , the terms quadratic in αx will dominate linear terms and we can write for some c > 0:Êθ (αx, y) ≥ c * (W (l) y αx) T Σ -1 y (W (l) y αx) = α 2 ( √ cW (l) y x) T Σ -1 y ( √ cW (l) y x) ≥ x T Σ -1 * xHere, we pick Σ * such that the equation holds for all y ∈ {1, . . . , C). Note that this means that in the limit, each joint energy term is bounded by the logarithm of the same Gaussian log N (0, Σ * ). For the marginal energy it holds:Êθ (αx) = -log y exp -Êθ (αx, y) ≥ -log y exp -αx T Σ -1 * αx = αx T Σ -1 * αx -log C ≥ αx T Σ ′ -1 * αxHere, we absorb the constant log C into the quadratic term. Similar to the proof of Proposition 4.1, we now analyze the integral of the implied density for each linear region of the classifier Q (l) .Q (l) exp -Êθ (x) dx = Q (l) ∥x∥2≤α0 exp -Êθ (x) dx + Q (l) ∥x∥2>α0 exp -Êθ (x) dxThe first term is an integral of a finite function over a finite region, which therefore will also be finite:I (l) α≤α0 := Q (l) ∥x∥2≤α0 exp -Êθ (x) dx < ∞For the second term, we notice that it is bounded by the (finite) Gaussian integral:I (l) α>α0 := Q (l) ∥x∥2>α0 exp -Êθ (x) dx ≤ Q (l) ∥x∥2>α0 exp -x T Σ ′ -1 * x dx < ∞Lastly, since we can decompose R d into a finite set of linear regions over each of which the integral is finite, the entire integral is finite.R d exp -Êθ (x) dx = L l=1 Q (l) exp -Êθ (x) dx = L l=1 I (l) α≤α0 + I (l) α>α0 < ∞ Theorem A.1.1.For a piecewise affine classifier f θ as in Proposition 4.1, and a piecewise affine feature extractor g θ (x), pθ is integrable.Ẑθ = X y exp(-E θ (x, y)) N (g θ (x) | µ y , Σ y ) γ dx < ∞Proof. Note that both affine functions f θ and g θ partition the input space R d into a finite set of linear regions. Intersecting their boundaries again gives rise to a finite set of linear regions. For bounded regions, the integral over the induced density will be finite, so we discuss the unbounded regions here.For any such region Q (l) , we have f θ (x) = w T f x + b f and g θ (x) = W g x + b g .We now partition the R d ∩ Q (l) into four regions using the kernel spaces of w f and W g respectively, i.e.R d ∩ Q (l) = 0 f +g • ∪ 0 f -g • ∪ 0 g-f • ∪ I f +g , where we define 0 f +g := ker(w f ) ∩ ker(W g ) ∩ Q (l) , 0 f -g := ker(w f ) \ ker(W g ) ∩ Q (l) , 0 g-f := ker(W g ) \ ker(w f ) ∩ Q (l) and I f +g := im(w f ) ∩ im(W g ) ∩ Q (l) .We can now decompose the integral over Q (l) into integrals over all four regions. Note that of these sets, only I f +g has a non-zero measure (if the affine classifier is not the null function). Therefore, we only have to focus on this domain. For some α 0 and x ∈ I f +g , ∥x∥ 2 ≥ α 0 , we have:pθ (x) ∝ exp (-E θ (x, y)) N (g θ (x) | µ y , Σ y ) ∝ exp w T f x + b f exp -(W g x + b g ) T Σ -1 g (W g x + b g ) ≤ exp -x T Σ -1 * ,y xFor some Σ -1 * ,y that bounds the quadratic function in the exponential for ∥x∥ 2 ≥ α 0 . The integral over the region Q (l) now reduces to:I (l) = x∈Q (l) y const * exp (-E θ (x, y)) N (g θ (x) | µ y , Σ y )dx = const + Q (l) ∥x∥2≥α0 y const * exp (-E θ (x, y)) N (g θ (x) | µ y , Σ y )dx ≤ const + Q (l) ∥x∥2≥α0 y const * exp -x T Σ -1 * ,y x dx ≤ const + Q (l) ∥x∥2≥α0 const * exp -x T Σ -1 * x dx < ∞Here, we pick Σ * to bound the quadratic terms of all Σ y, * . As previously mentioned, the kernel spaces of w f and W g have zero measure and therefore do not contribute to the integral. As previously, the integral over the entire domain R d decomposes into finite integrals over all Q (l) .R y const * exp (-E θ (x, y)) N (g θ (x) | µ y , Σ y )dx = const + L l=1 I (l)< ∞ Corollary 4.3. For a piecewise affine classifier f θ as in Proposition 4.1, and any x ∈ R d almost surely:lim α→∞ pθ (αx) = 0Proof. As per the proof of Theorem 4.2, for sufficiently large α we have for some Σ -1 * :Êθ (αx) ≥ x T Σ -1 * xFrom there, it follows directly that:lim α→∞ pθ (αx) = lim α→∞ exp(-Êθ (αx)) = exp lim α→∞ -Êθ (αx) ≤ exp lim α→∞ -x T Σ -1 * x = 0 A.At the backbone of all models, we use the same GCN [34] architecture if not specified explicitly otherwise. We use one hidden layer of dimension 64, symmetric normalization Appendix C.6, and add self-loops to the undirected (symmetric) adjacency matrix. We use ReLU nonlinearities, enable the bias term, and use dropout at p = 0.5.All models are trained with the ADAM optimizer [33] with a learning rate of 10 -3 , weight decay of 10 -4 , and a cross-entropy objective. We use early stopping on the validation loss with a patience of 50, an absolute improvement threshold of 10 -1 , and select the model with the best validation loss. We implement our models in PyTorch [58] and PyTorch Geometric [19] and train on two types of machines: (i) Xeon E5-2630 v4 CPU @ 2.20GHz with a NVIDA GTX 1080TI GPU and 128 GB of RAM. (ii) AMD EPYC 7543 CPU @ 2.80GHz with a NVIDA A100 GPU and 128 GB of RAM .As the GCN backbone used in our experiments is lightweight, model training finishes within a few minutes and VRAM consumption is dominated by the datasets. Our post hoc method can be fitted and evaluated in negligible time (<1s).For MC-Dropout [22] , we use a dropout probability of p = 0.5 which we also use for DropEdge [59] .At inference, we evaluate 50 samples to compute uncertainty. For ensembles, we train 10 backbones from different weight initializations independently. The Bayesian GNN [6, 15, 18] also is evaluated with 50 samples during inference and uses a KL-loss with weight 10 -1 and is trained with learning rate 10 -2 and no weight-decay. We parametrize the weight distribution using a log transform and initialize the mean and log scale to 1.0 and -3.0 respectively. Weight distributions are regularized to follow a standard normal.For GPN [64] , we follow the hyperparameters suggested by the authors and use warmup training on the normalizing flow for 5 epochs with a learning rate of 1e -2, no weight decay during joint training and 1e -2 during warmup. The flow dimension is 16 and is composed of 10 radial layers. The cross-entropy regularization weight is 10 -4 . We use Page Rank propagation for 10 iterations at a teleport probability of 0.1.For SGCN [82] , we use the same GCN backbone and a GDK-prior at cutoff distance 10 and scale σ = 1.0. For teacher training, we use a learning rate of 10 -2 , weight decay of 5 * 10 -4 and a KL-loss weight of 10 -1 .For HEAT [36] , we use the hyperparameters suggested by the authors. In contrast to their study on the image domain, we do not have features with spatial extent and can not use standard deviation pooling on the volume. We set the temperature parameter of the combined HEAT model to -1, following the suggestion of the authors. Similar to their EBM backbone, we imitate the structure of the classifier and use a 2-layer MLP with a hidden dimension of 64 akin to the GCN backbone.Our GEBM framework regularizes logit-based joint energy at a strength γ. For downstream tasks, this parameter can, in general, be tuned. We find that an equal weighting of predictive energy and regularization performs well: We choose γ such that the 95% quantiles of both the training logits and the representations on which the Gaussian density model is fit are in the same range. Furthermore, recent work on deterministic uncertainty argues that density-based epistemic uncertainty should not be estimated directly from the logits [46] . We follow this advice and do not fit and evaluate the regularizer on the output layer (logits) of the GNN but instead on its penultimate layer representations. Note that for the ReLU networks we use, all formal proofs still hold in this setting as the penultimate representation of a node v is also described by a piecewise affine function [28] (see A.1.1. As a smoothing operator P A , we employ label-propagation smoothing with α = 0.5 for t = 10 iterations. Lastly, we found that aggregating the energy terms at different scales (Equation ( 9)) using a sum operation instead of logsumexp to perform better in practice and use it for our experiments.In our ablation regarding different model backbones, we use the default hyperparameters from the GCN backbone (e.g. number of hidden layers). For each model additional hyperparameters are set to the following values: For GATv2 [70, 8] we use 8 heads and use summation to aggregate them. For SAGE [27] , we use no normalization at the layers.For sampling-based approaches, we compute aleatoric and epistemic uncertainty as entropy and mutual information respectively according to [24] :u alea = E θ∼p(θ|D) [H [p(y | x)]] u epi = MI [θ, y | x, D] = H E θ∼p(θ|D) [p(y | x)] -E θ∼p(θ|D) [H [p(y | x)]]For evidential approaches, we follow [64] and use the maximum softmax response max c p(y = c | x) as aleatoric uncertainty and the total evidence c α c as an epistemic estimate. Since we want to compare single measures of epistemic uncertainty, we evaluate GPN's epistemic uncertainty in the presence of network effects. For deterministic models (that are at the backbone of EBM-based approaches), we use the predictive entropy as a measure of aleatoric uncertainty H [p(y | x)] and the energy E θ (x) as a measure of epistemic uncertainty. For all EBMs, we use a temperature of τ = 1.0.We report AUC-ROC and AUC-PR metrics for the o.o.d. detection problem in an inductive and transductive setting with corresponding standard deviations over all five splits and five model initializations each in Tables 6, 8 , 10 and 12. Again, we report the average performance ranks are in Tables 2, 9 , 11 and 13. As mentioned in Section 5.2, we consider a weighted average that does not favor any distribution shift family. That is, we assign a weight of 1/6 to structural and leave-out-class settings and factor in feature perturbations at a weight of 1/9 each.In an inductive setting, GEBM outperforms all other baselines and achieves the best rank regarding both AUC-ROC and AUC-PR metrics. In the transductive setting, the two evidential methods GPN and SGCN outperform GEBM on two datasets: We argue that this is due to feature leakage as o.o.d. data is present during training and evidential models are explicitly encouraged to assign low evidence to anomalous nodes. We want to point out that it is unrealistic to assume that o.o.d. data is available in practice and therefore strongly argue in favor of the inductive scenario as a more realistic benchmark. Nonetheless, GEBM is highly effective for transductive problems as well.We evaluate the improvement in AUC-ROC scores of GEBM over the estimator assigned the overall second-best rank. To that end, we average the model ranks not individually for each estimator and dataset, but instead compute an average over datasets and splits simultaneously. This way, we obtain a global rank (over datasets and shifts) for each epistemic estimate. Again, to not favor certain classes of shifts, we assign weights such that each distribution shift family has an equal contribution. Based on AUC-ROC scores listed in Table 6 , we list the rank of each model in Table 14 :While our approach, GEBM, also ranks the highest globally, a vanilla logit-based EBM is the next best approach. Therefore, we compute the improvement in AUC-ROC scores over this model achieved by GEBM in Table 15 . On all datasets, GEBM improves the AUC-ROC scores by 5.8 to 10.9 percentage points on average (16%-32% relative improvement) over the second-best ranked estimator.We report AUC-ROC and AUC-PR for misclassification detection in both an inductive and transductive setting with the corresponding standard deviations in Tables 16 to 19 . In alignment with previous work [64] , we observe that often aleatoric uncertainty is more suitable for misclassification detection than epistemic uncertainty. Overall, GEBM performs similar to other epistemic measures.We again want to point out that the scope of this work does not encompass improvements on aleatoric uncertainty. The results on misclassification detection obtained in our work and previous studies indicate that this problem may be more suitable as a benchmark for aleatoric uncertainty.Our framework, GEBM, is limited toward epistemic uncertainty estimation and leaves the aleatoric estimates and the classifier calibration unchanged. For completeness, we nonetheless report calibration for the GCN used at the backbone of our experiments. Note that since our model does not change the output of the classifier, the calibration could be further improved using post hoc methods like temperature scaling [26] . This, however, is beyond the scope of this work.Expected Calibration Error (ECE). The expected calibration error (↓) [50] measures how well the predicted probabilities that are normalized to the interval [0, 1] match the true predictive accuracy.To that end, we bin each prediction into B = 20 bins according to their confidence (i.e. maximum softmax response max c p(y = c | x). For each bin, we then compute the average accuracy and compute the ECE as the mean over all bins weighted by their size.ECE = k |B k | n |accuracy(B k ) -confidence(B k )|Brier Score. A similar metric is the Brier score [7] (↓) which computes the mean squared distance between the predicted probabilities and the one-hot encoded true labels.Brier = 1 n i ∥p(y | x i ) -y i ∥ 2 2We report ECE and Brier scores for inductive and transductive settings in Tables 20 to 23 . In terms of calibration metrics, none of the considered approaches consistently shows strong merits. We remark that work on GEBM and GNN calibration is somewhat orthogonal and our framework can be applied to any well-calibrated GNN backbone.We report AUC-ROC and AUC-PR for o.o.d. detection using GEBM and different GNN backbones with corresponding standard deviations in Tables 24 and 25 . GEBM is effective on all models and achieves the highest scores on most distribution shifts.At the core of many GNNs and also our GEBM framework lies a diffusion operator P A : R n → R n . Here, we discuss three typical realizations and the bias the introduce.Â = D -1/2 AD -1/2 . Here, D = diag(deg(v 1 ), • • • deg(v n )) is a diagonal matrix of node degrees.The symmetric diffusion operator has a dominant eigenvector that correlates with the node degree v max ∝ d 1/2 and therefore also centrality [12] . Repeated application of this diffusion process to any arbitrary signal will concentrate confidence at high degree nodes. Applying this diffusion to a confidence measure like the logits of GNN will therefore always favor high degree nodes. Random-Walk Diffusion. Random-walk diffusion normalizes the adjacency matrix as Â = D -1 A which can be seen as a stochastic transition matrix of random walk on the graph. A different interpretation is that each node distributes its information uniformly to its neighbours which in turn sum incoming signals. It, too, has a dominant eigenvector that correlates with the node degree: v max ∝ d [12] and also favors high degree nodes when applied to a confidence measure.Label-Propagation Diffusion. Diffusion used by Label Propagation [30] normalizes the adjacency matrix as Â = AD -1 and can be seen as a smoothing procedure: Each node will update its features based on the average of its neighbours. Obviously, it has a constant dominant eigenvector and therefore does not favor nodes based on structural information. We use a repeated convex combination of the identity and this diffusion process at the backbone of our GEBM framework:P A = (αI +(1-α)AD -1 ) t .The smoothing behaviour enforces a uniform distribution of confidence within clusters and therefore is suitable candidate for cluster-level anomaly detection.We motivate the three energy terms that we use to compose the energy measure of GEBM through synthetic experiments. All of them arise naturally from interleaving graph diffusion and energy Node-Level Anomalies. We study node level anomalies by generating synthetic CSBM graphs [57] (intra-edge probability 0.05, inter-edge probability 0.001, n = 1000, c = 7). We then generate c-dimensional logits (intuitively confidence scores) according to a standard normal distribution that is centered at l disp = 4 for the dimension of the true class label of a node and 0 otherwise. This roughly resembles the logits of a well-trained classifier which peak at the true unknown class. We then perturb a fraction p = 0.05 of the logits by replacing them with positive noise from a standard normal distribution that is rescaled by an increasing magnitude. For each magnitude, we compute all three energy terms for each node and compare the difference in energy to the corresponding unperturbed energy. Effectively, this monitors how the energy of a node changes under increasingly severe distribution shifts that affect the logits of a classifier. We visualize the median of the energy differences in Figure 4b : While all energies increase with higher magnitudes, the structure-agnostic energy term of GEBM is the most sensitive to anomalies that are located at individual nodes. It does not suffer from the smoothing of anomalous scores induced by graph diffusion.Cluster-Level Anomalies. We study anomalies that affect an entire cluster of nodes by iteratively introducing an anomalous cluster to the graph. To that end, we leave out k classes and train a GCN on the Amazon Photos dataset. At inference, we re-introduce nodes (and edges) of the left-out classes which can be seen as anomalous from the perspective of the classifier. Similar to the aforementioned node-level anomaly, we monitor how each energy type changes while iteratively introducing the entire cluster(s) of o.o.d. nodes into the graph. Again, we see that the cluster-level energy term of GEBM is the most sensitive to this distribution shift in Figure 4a . Table 10 : Out-of-Distribution detection AUC-PR (↑) using aleatoric or epistemic uncertainty (best and runner-up) in an inductive setting.Structural Anomalies. The last anomaly type we consider is creating structural anomalies: To that end, we generate synthetic CSBM graphs similar to the node anomaly experiment. However, we adapt the intra-and inter-class edge probabilities to accommodate varying degrees of homophily: We fix the intra-class connection probability at p = 0.05 and vary the signal-to-noise ratio σ SNR which implicitly defines the inter-class edge probability as p/σ SNR . We measure the degree of heterophily as -log σ SNR and again compare how individual node energies change for increasingly heterophilic graphs in Figure 4c . We find that the cluster-level energy of GEBM is the only energy term that is sensitive to structural anomalies.Overall, these experiments motivate the use of the three naturally arising energy terms in GEBM: Each energy is sensitive to a different family of distribution shifts that originate from anomalies at different structural scales on the graph: At the node level, with the local structure of a node and at the cluster-level.We disambiguate between previous studies on the underconfidence of GNNs [74, 75] and the overconfidence issue of piecewise affine networks tackled by our work. The former studies the calibration of GNNs on in-distribution data, and provides strong evidence for models to be underconfident. This does not conflict with our claim that with increasing distance from the training distribution, i.e. on out-of-distribution data, piece affine GNNs become overconfident. We empirically verify this in Figure 5 : Both the energy and the maximum softmax probability -confidence measures -of the GNN architectures visualized increase (or converge to their maximum) under more severe normal feature perturbations. Budget (%) Table 12 : Out-of-Distribution detection AUC-PR (↑) using aleatoric or epistemic uncertainty (best and runner-up) in a transductive setting.We apply GEBM to an APPNP model and expose it to increasingly severe feature perturbations. Even though APPNP uses the same number of diffusion steps as GEBM (t = 10), it suffers from deteriorating accuracy even when a small portion of node features is perturbed. Since logits and energy are unbounded and likely to diverge under strong enough distribution shifts (see Proposition 4.1), a fixed number of diffusion steps is insufficient to recover from perturbations. At the same time, the regularized energy of GEBM converges to zero and, therefore, a fixed number of diffusion steps can effectively maintain high robustness akin to evidential methods like GPN.The feature perturbation-based distribution shifts discussed in Section 5.1 replace node features with noise. We additionally study a feature-level distribution shift that partially corrupts the features of an instance. To that end, we vary the fraction p with which an individual node feature is perturbed and again measure how well uncertainty estimators can detect this distribution shift. In particular, we replace d • p uniformly and independently selected node feature x i with Gaussian noise and keep d -d • p features as-is. We compare the AUC-ROC of different uncertainty estimators while increasing the fraction of perturbed features for each o.o.d. node in Figure 7 . While both the softmax-level uncertainty of the vanilla GCN and the EBM again become overconfident, GEBM can reliably identify this distribution shift. This coincides with observations made for feature perturbations that affect all node features simultaneously and justifies focusing on that distribution shift for the bulk of our study.We report AUC-ROC and AUC-PR for o.o.d.-detection ablating GEBM in an inductive and transductive setting with standard deviations in Tables 26 to 29 . Additionally, we rank all variants of GEBM (i.e. energies at different structural scales) similar to the o.o.d. detection experiments in Section 5.2. We observe our proposed GEBM to consistently be the most effective over different shifts simultaneously. We can also confirm the effectiveness of the scale-specific energies at detecting distribution shifts that should be covered from their definition. Both the best and second-best ranking methods are GEBM and a variant that uses unregularized energy: This shows the efficacy of a scale-aware EBM for graph problems.We also ablate the diffusion operator P A and its hyperparameters, i.e. the type of diffusion process (see Appendix C.6), the number of diffusion steps t as well the teleport probability α, in Figure 8 . We evaluate the performance of GEBM on a representative of each distribution shift family. As expected, low t and high α aid node-level anomaly detection while the opposite holds for cluster and local shifts. Label-Propagation achieves satisfactory performance over the entire range of diffusion hyperparameters which justifes using it in our experiments. Table 16 : Misclassification detection AUC-ROC (↑) using aleatoric or epistemic uncertainty (best and runner-up) in an inductive setting.A recent line of work identifies feature collapse as a limitation in uncertainty estimation for deterministic models on i.i.d. data [46, 69] . Intuitively, feature collapse occurs when out-of-distribution data is mapped to the same regions of the model latent space as in-distribution data. Consequently, density-based uncertainty estimators such as the regularizer of GEBM can not separate both data distributions accurately and falsely attribute high confidence to out-of-distribution examples. To [46, 47] . We investigate if this regularization benefits GEBM as well in Appendix D. 3 .In contrast to work on i.i.d. data, we do not find spectral normalization consistently leading to improved out-of-distribution detection. We provide two possible explanations: First, feature collapse has not been observed to occur for graph problems. The diffusion process at the backbone of many GNNs may mitigate the issue. Second, spectral normalization enforces Lipschitz smoothness in terms of the L 2 norm of the input features of a node and its representation. This notion neglects the structural influence of other nodes and, therefore, may not be suitable to quantify feature collapse in non-i.i.d. domains such as graphs.Table 18 : Misclassification detection AUC-PR (↑) using aleatoric or epistemic uncertainty (best and runner-up) in an inductive setting. Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).Justification: Our research aims to improve reliability of GNNs. All datasets are commonly used benchmarks that are publicly available. Our paper fully conforms with the code of ethics.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.• The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 10. Broader Impacts Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? Answer: [Yes] Justification: We aim to contribute to making AI more reliable by improving on uncertainty quantification. We discuss the impact of our work beyond commonly known risks and concerns in research on AI in Section 6. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).We provide our code at cs.cit.tum.de/daml/gebm/ 


Decision: The paper proposes a simple and effective post hoc method applicable to any pre-trained GNN that is sensitive to various distribution shifts. The novelty of the proposed method has been recognized by all the reviewers. The paper also provides strong results on datasets with various distribution shifts. The results show the proposed method could improve the generalization performance of existing backbones. 

All the concerns from reviewers have been well-solved from the rebuttal. All reviewers support to accept the paper.

Reviews: review: paper_summary: paper_summary: This paper introduces a method for post-hoc epistemic uncertainty estimation in logit-based Graph Neural Networks (GNNs) by aggregating energy scores at different levels, including node, local, and group levels. Extensive experiments show the effectiveness of the proposed framework.
strength_weakness: strength_weakness: 1.	The paper lacks a detailed discussion on the selection of hyperparameters, especially for the diffusion module $P_A$. Specifics about the parameters $\alpha$ and $t$ mentioned in Appendix C are not sufficiently discussed. Including ablation studies on different graph diffusion architectures, such as label propagation referenced in the Appendix or APPNP used in the GPN paper, would enhance the paper.
2.	The paper states that common GNNs suffer from overconfidence due to their similarity to findings on ReLU neural networks[1]. However, literature [2] [3] suggests that predictions from shallow GNNs are typically under-confident. The paper will benefit from evidence on the over-confidence issue of GNNs. 
3.	Section 4.4 discusses the relationship between energy scores from logit-based classifiers and total evidence in evidential models. The paper lacks an explanation for why the proposed model outperforms evidential models in epistemic uncertainty prediction, particularly how it addresses the feature collapsing issue in density-based models [4].

[1] Matthias Hein, Maksym Andriushchenko, and Julian Bitterwolf. Why relu networks yield high-confidence predictions far away from the training data and how to mitigate the problem. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 41–50, 2019.

[2] Wang, Xiao, Hongrui Liu, Chuan Shi, and Cheng Yang. "Be confident! towards trustworthy graph neural networks via confidence calibration." Advances in Neural Information Processing Systems 34 (2021): 23768-23779.

[3] Wang, Min, Hao Yang, Jincai Huang, and Qing Cheng. 2024. “Moderate Message Passing Improves Calibration: A Universal Way to Mitigate Confidence Bias in Graph Neural Networks”. Proceedings of the AAAI Conference on Artificial Intelligence 38 (19):21681-89. https://doi.org/10.1609/aaai.v38i19.30167.

[4] Mukhoti, Jishnu, Andreas Kirsch, Joost van Amersfoort, Philip HS Torr, and Yarin Gal. "Deep deterministic uncertainty: A simple baseline." arXiv preprint arXiv:2102.11582 (2021).
questions: questions: 1.	How does the paper perform inductive training on the GCN backbone when OOD nodes and edges are excluded during the training phase? Does it use graph sampling or data augmentation techniques?
2.	In corollary 4.3, what is meant by ' any $x\in \mathbb{R}^d$ ’? Please provide a precise range for $x$ or probability. 
3.	In the Equation (9), the regularized energy from three structural scales equally contributes to the final energy score. Table 3 shows varying impacts of energy at these scales. Why was the decision made to use equal weighting?
4.	There are inconsistencies between some model names mentioned in Section 5.1 and those in the tables.
5.	What are the differences in distribution shifts used in this paper compared to those in GPN or GNNSafe, and why did the authors make these changes?
limitations: limitations: YES
paper_summary: paper_summary: The paper defines an integrable (regularized) energy function to capture epistemic uncertainty via energy a pretrained model. The energy function is a function of the logits so the method is a post-hoc model agnostic. The authors define a diffusion-based hierarchical energy propagation (structure agnostic + local diffusion + group diffusion) which both leads to quantification of uncertainty in graphs, and an evidential model prediction.
strength_weakness: strength_weakness: 1. The authors evaluate their method structurally (line 227) via leaving least homophilic nodes or low-page rank centrality as o.o.d. This seems like there is an implicit assumption of homophily in the graph which is not stated anywhere. In other words, I assumed that the propositions, or setup I should see an assumption of "homophily $\ge$ some constant on expectation...". I see that they referred to this assumption in the limitations, but it is better to be mentioned somewhere in other sections as well.

2. *Clearity:* However successful the method is, I do not see a clear intuition on why these three levels of propagation should be combined and why all are aggregated with weight = 1. For this, I expected an intuitive introductory experiment to clearly show what happens to a node before and after each certain diffusion. More importantly, I see theory to show that the regularization $\pm$ diffusion is integrable, or is not infinity anywhere, but I did not find any theory behind why the approach leads to a good uncertainty quantification in the end; like comparing it with an oracle or finding bounds on the distance from unseen ground truth probability. I also did not see any synthetic experiment in this direction which might help a lot.

3. *Experiments:* (1) I see that in scores like ECE and Brier score the method is not the best. Is there any intuitive explanation for why this is the case? I also strongly recommend the authors to mention that in the limitations of the paper. (2) I see the absence of study on models that have diffusion at the probability space; e.g. APPNP. If the GEBM can improve upon these methods then clearly there is some additional information passed in the energy domain.

4. *Minor Typos:* (1) Line 237 the term "fitted" is used twice. More important (2), in Line 163 there should be "for $\boldsymbol{x} \in {Q}_l$" added somewhere to show that the definition of $f(\boldsymbol{x})$ is limited to that polytope.
questions: questions: 1. Building on weaknesses no. 1. (*W1*), do you assume some homophily property like $\mathbb{P}_{v_i \sim v_j}[y_i = y_j] \ge p$? Is heterophily graph a theoretical limitation of your approach? If yes can you elaborate on the theoretical insight behind it? Note that I see the heterophily is mentioned as a limitation but mostly I can not find a sound explanation of why it is other than just leaving it as an assumption. 

2. In evaluation with feature perturbations, why didn't the authors use a random XOR shift instead of a total replacement of features? In that case, you have control over the magnitude shift; intuitively I expect the uncertainty to grow with a correlation to the perturbation probability, but here I can just see the endpoints of the experiment I just mentioned -- fully perturbed node and original node. In general, you can also define the feature shift by randomly selecting from the noise or the original features and controlling the randomness as the magnitude of the shift.

3. In Fig. 2. (robust evidential inference), I can not understand why the result is non-trivial. If the graph is homophily, a simple diffusion over predicted probabilities with a strong coefficient can have a significant denoising effect in the prediction. This is especially in case the perturbation is sparse. What is the model evaluated in Fig. 2? Does it have a similar enhancement in robustness for models that already have a diffusion step like APPNP?
limitations: limitations: I think the limitations are mentioned clearly.
paper_summary: paper_summary: This paper explores the challenges associated with quantifying uncertainty in Graph Neural Networks (GNNs), particularly in domains involving interconnected data such as graphs. The authors propose a novel method called GEBM, which aggregates energy at various structural levels. This approach enhances predictive robustness and improves performance in distinguishing between in-distribution and out-of-distribution data across different anomaly types and datasets.
strength_weakness: strength_weakness: 1. The experiments predominantly focus on node-level tasks. It would be beneficial to explore how the proposed method performs on graph-level tasks as well.
2. The paper lacks an ablation study specifically on different types of energy used in the GEBM model. Understanding which energy components are critical remains unclear.
questions: questions: 1. From the equations presented, it appears that this method is not limited to graphs. Are there potential challenges in applying this method to tasks beyond graph-related domains?
limitations: limitations: The limitations are discussed in this paper. GEBM is a post hoc epistemic estimator; it does not improve aleatoric uncertainty or its calibration.

Comments: title: Reply to the rebuttal
comment: We are glad that we could address the reviewer's concerns and believe that our paper benefits from additional experiments prompted by their feedback. Thank you for the very helpful review!
Thanks for the detailed reply. 

My concerns were partially addressed. With the informative reply from the authors, I find this paper an acceptable and strong study. This is why I increase my score.
We are happy that the reviewer finds the additional ablations and clarifications helpful and we, too, believe it makes the paper stronger. Thank you for the very useful input!
Thank you to the authors for their efforts in providing additional experiments and clarifications. They have addressed my concerns, and I have increased my score.

Additionally, I agree with most of the points raised in the rebuttal, particularly regarding feature collapsing and under/over-confidence scenarios. I am also interested in exploring the differences and commonalities between energy-based models and evidential-based models.
We are glad that we could resolve some concerns and want to thank the reviewer again for the time spent on the review, in particular for pointing out interesting directions for future work.
Thanks for your rebuttal. My concerns have been partially addressed. I would like to maintain the rating.