Uncertainty Estimation for Heterophilic Graphs Through the Lens of Information Theory
Authors: Dominik Fuchsgruber
Tom Wollschläger
Johannes Bordne
Stephan Günnemann
Venue: ICML 2025 poster (2025)
Keywords: Heterophilic Graphs
Uncertainty Estimation
Information Theory
Graph Neural Networks
Primary area: deep_learning->graph_neural_networks
TL;DR: Information theory based joint density estimatior on the hidden representations to quantify uncertainty for heterophilic graphs.

Abstract: While uncertainty estimation for graphs recently gained traction, most methods rely on homophily and deteriorate in heterophilic settings.
    We address this by analyzing message passing neural networks from an information-theoretic perspective and developing a suitable analog to data processing inequality to quantify information throughout the model's layers. In contrast to non-graph domains, information about the node-level prediction target can *increase* with model depth if a node's features are semantically different from its neighbors. 
    Therefore, on heterophilic graphs, the latent embeddings of an MPNN each provide different information about the data distribution - different from homophilic settings.
    This reveals that considering all node representations simultaneously is a key design principle for epistemic uncertainty estimation on graphs beyond homophily. 
    We empirically confirm this with a simple post-hoc density estimator on the joint node embedding space that provides state-of-the-art uncertainty on heterophilic graphs. At the same time, it matches prior work on homophilic graphs without explicitly exploiting homophily through post-processing.

Uncertainty Estimation for Heterophilic Graphs Through the Lens of Information Theory
Dominik Fuchsgruber" !
Tom Wollschläger
Johannes Bordne'
Stephan Günnemann
Abstract
like graphs gained traction (Stadler et al., 2021; Fuchsgru- ber et al., 2024b; Trivedi et al., 2024; Wang et al., 2024). Many approaches assume homophily - that nodes preferably connect to nodes of the same class either explicitly by us- ing graph diffusion (Stadler et al., 2021; Fuchsgruber et al., 2024a; Wu al., 2023) or implicitly through the chosen backhone model (Bazhenov et al., 2022).
While uncertainty estimation for graphs recently gained traction, most methods rely on homophily and deteriorate in heterophilic settings. We ad- dress this by analyzing message passing neural networks from an information-theoredd perspec- tive and developing a suitable analog to data processing inequality to quantify information throughout the model's layers. In contrast to non-graph domains, information about the node- level prediction target can increase with model depth if node's features are semantically differ- ent from its neighbors. Therefore, on heterophilic graphs, the latent embeddings of an MPNN each provide different information about the data distri- bution - different from homophilic settings. This reveals that considering all node representations simultaneously is a key design principle for epis- temic uncertainty estimation homophily. We empirically confirm this with a simple post-hoc density estimator on the joint node embedding space that provides state-of-the- art uncertainty on heterophilic graphs. At the same time, it matches prior work on homophilic graphs without explicitly exploiting homophily through protesrocs...ng
In heterophilic settings, when nodes primarily connect to nodes of a different class, these methods and their uncer- tainty estimates deteriorate. One reason that they often ex- plicitly rely on smoothing to propagate (un)certainty within clusters the graph. This can be beneficial when links exist predominantly between semantically similar nodes but less justified on heterophilic graphs.
In this work, we approach uncertainty estimation from an information-theorrtic perspective. Taking inspiration from Tishby & Zaslavsky (2015), we study Message Passing Neural Networks (MPNNs) in terms of the information its latent node representations provide about the target vari- able. By formulating suitable graphical model, we derive analog to the Data Processing Inequality (DPI) that ap- plies to settings with independent and identically distributed (i.i.d)) data. It enables us to propose novel definition of homophily based on the semantically relevant information a node's neighbors provide that is different from its own. We prove that in homophilic graphs where the information of adjacent nodes is similar node's own features, the information gained through considering deeper layers di- minishes. In heterophilic graphs, adjacent nodes exhibit different semantics that are captured by representations at different layers. This reveals a key principle for uncertainty quantification in MPNNs under heterophily: They should jointly consider all node representations.
graphs beyond
1. Introduction
Trusting machine learning model is critical for rorldworld use, especially in high-risk application domains (Xu & Salch, 2021; Rabe et al., 2021). While most uncertainty modeling focuses on computer vision models (Gawlikowski et al., 2023), recently, also interdependent data modalities
We realize this design principle through Joint Latent Density Estimation (JLDE) on the embeddings in an MPNN using simple KNN-based estimator. We are the first to study uncertainty estimation in node classification beyond ho- mophilic graphs and systematically compare our principle to established estimators on model architectures that per- form well on heterophilic data. provides sfate-of-the- epistemic uncertainty across different datasets, distribu- tion shifts, and MPNN backbones, confirming the validity
'Equal contribution 'School of Computation, Informa- tion& & Technology and Munich Data Science Institute. Tech- nical University of Munich. Correspondence Do- minik Fuchsgruber suffuchssruberr@uum..e Tom Wollschläger <t. <t.wollschlacgere @aanggrrrrtume.....
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Uncertainty Estimation for Heterophilic Graphs Through the Lens of Information Theory
Ego- Go
Heterophily
Homophoily
MPNN
MPNN
100D MimilI
Nata Processi ng Loss / Recovery
4 (643) (+)
Information Gain
Different information
Similar
(();Z(0)
1(Y
2())
each 2
6 O%
I(Y; (g (U:2)
JLDE: p(G,) & p(Z
Figure 1. Information propagation in MPNNs. In the i-th iteration, information about i-hop neighbors of the anchor node v is gained (A (9) while information about neighbors at smaller distances may be lost to processing (A (u:6-1) 1)), heterophilic graphs, the gl are
semantically different and each latent representation z often contains different information about the target Y. Therefore, density-
uncertainty must be estimated jointly from all ( to fully capture all available information about the data distribution.
and broad applicability of our findings. Our principle also matches the performance of other model-agnostic uncer- tainty estimates on homophilic graphs without explicitly facilitating homophily.
Ego Graphs. For each node u E V. we can define an ego-graph 9, centered this node. This ego-graph can be decomposed into disjoint subsets G, = u where the ego-graph of i-th order gl contains all nodes with shortest-path distance of i-hops to the center node v. Conse- quently, g( contains just the node v and features.
2. Background
Transductive Node Classification. We define a graph 9 (V,E,F) as a set of n vertices V that are connected by m undirected edges S {fu, eHu,, Ju. V} represented with symmetric adjacency matrix A {0, 1|nxn, Each node is associated with features F E Rn Nodes are assigned a label y E (1.....c) c)" and the task is to infer these labels from a subset of labeled nodes Virain-
Message Passing Neural Networks. Most popular Graph Neural Networks (GNNs) can be formalized as MPNNs (Kipf & Welling, 2017; ;; Hamilton et al., 2018; Veličković et al., 2018; Brody et al., 2022). They are closely related to the ego-graph perspective as they iteratively update node representations by first aggregating the representations of node v's neighbors N((w) and then combining them with their own representation Z..-
Mutual Information (MI) measures the dependence be- tween two random variables X. and is defined as:
(k) AGGREGATE( E (N()))
I(X: Y) = p(X. Y) log p(X, Y) pY)) dody-
(1)
(k) COMBINE 1--1 a (k)
1(X; Y) and non-negative I(;; Y) 0, with equality only if X and Y are independent. MI quantifies the difference between the joint distribution over two random variables is and the product distribution of their marginals. By conditioning on additional random variable(s) Z, I(X; Y Z) measures the information between and that is not already in Z. We use MI to track the information of a MPNN's embeddings regarding the label by representing its inputs, target, and hidden representations random variables similar to (Tishby & Zaslavsky, 2015).
is symmetric X(Y:X)
Therefore, the representation of a node e after iterations Z depends on the ego graphs up to i-th order (0:s)
Uncertainty in Machine Learning is often disentangled into aleatoric uncertainty =lea and epistemic uncertainty oi The former arises from irreducible sources inherent to the data (e.g. measurement noise). The latter is rooted in lack of knowledge and can be reduced, e.g. with additional data. It can be quantified as inverse to (an estimate of) the data distribution p(X)-1, as model should be confident near its training data (Qazaz, 1996).
Homophily and Heterophily describe how semantically similar adjacent nodes are. Many definitions measure simi- larity through class labels with some recent work also con- sidering node features (Luan et al., 2022), see Appendix C. Instead, in Section 4.3, we define homophily as the semanti- cally relevant mutual information between node's features and the features of its neighbors.
3. Related Work
Heterophilic Node Classification is sub-field of node classification specifically dealing with heterophilic graphs. While this problem has been studied exhaustively by pre- vious work (see Appendix B), a recent benchmark on het- crophilic node classification reveals that much the success of GNNs dedicated heterophilic graphs can be attributed
'e provide our code at cscci.um..ee/da//heeerphiii uncertainty/
2

---

Uncertainty Estimation for Heterophilic Graphs Through the Lens of Information Theory
to hyperparameter tuning and issues regarding dataset leak- age (Platonov al., 2023). In particular, their system- atic evaluation shows that many GNNs, like GCN (Kipf & Welling, 2017) or graph attention (Veličković et al., 2018; Brody et al., 2022; Mustafa & Burkholz, 2024) originally de- signed for homophilic settings, are highly effective and often outperform designated models in heterophilic classification problems. Importantly, Platonov et al. (2023) augment these homophilic GNNs accommodate for heterophily: They in- troduce residual connections, increase the model complexity through deep feature transformations, and use LayerNorm (details in Appendix C.2). We build on these insights and verify JLDE by applying it to these models as they are the most effective in heterophilic settings.
den representations especially in heterophilic problems, and confirm this insight with a simple post-hoe estimate.
Uncertainty in Homophilic Node Classification is re- cently emerging field. Many approaches transfer concepts from i.d.d. problems to the graph domain: DropEdge applies MCD to the edges (Rong et al., 2020; Hasanzadeh et al., 2020), Graph A-UQ (Trivedi al., 2024) uses Stochas- tie Centering in GNNs, and other methods propose GPs for graphs (Ng al., 2018; Zhi et al., 2023; Liu al., 2020c). Often, such approaches facilitate graph diffusion to improve uncertainty estimates. Graph Posterior Network (GPN) (Stadler et al., 2021) diffuses evidence using PageR- ank (Page, 1999), and graph EBMs like GNNSafe (Wu et al., 2023) or GEBM (Fuchsgruber et al., 2024b) employ label propagation. These diffission kernels exploit the homophily in the graph, which empirically transfers well to uncertainty estimates. Despite the popularity of non-homophilic classifi- cation in the literature, to the best of our knowledge, there is no work on uncertainty quantification that explicitly targets heterophilic graphs, or even deliberately abstains from using homophily. Furthermore, none of the aforementioned works studies how these estimators behave when their (often only implicitly stated) homophily assumptions are violated. Our work addresses this gap by studying uncertainty without as- suming homophily and empirically confirming that existing estimators are not well-suited for these problems.
Uncertainty in i.i.d. Classification can be estimated under different paradigms. A family of complinggbased Bayesian estimators uses an information-theorele
decomposition by approximating the posterior over the model weights (Hüllermeier & Waegeman, 2021) from which multiple sam- ples are drawn during inference. Here, epistemic uncertainty is quantified as the deviation of individual samples from their expectation. Bayesian Neural Networks (BNNs) (Blun- dell al., 2015; Dusenberry et al., 2020; Farquhar et al., 2020) explicitly model their weights normal distributions to sample from the posterior. Other approaches are training an ensemble (Lakshminarayanan et al., 2017; Wen et al., 2020), Stochastic Centering (Thiagarajan et al., 2022), using
Monte-Carlo dropout (MCD) Gal & Ghahramani (2016), or data augmentations during inference (Wang et al., 2019). Sampling- frree estimators are typically deterministic and can be computed with single forward pass. In evidential learning, epistemic uncertainty is estimated by predicting a second-order Dirichlet distribution (Sensoy et al., 2018: Malinin & Gales, 2018). Another method is to quantify epistemic uncertainty as distance from or similarity to the training data. Examples include Gaussian Processes (GPs) (Ng et al., 2018: Zhi et al., 2023) that measure similarity with kernel function, or methods that directly estimate the data density in distance-preserving models (Liu et al., 2020a; Mukhoti et al.. an masey interpretation of a classifier (EBM) that can be used for that purpose as well (Liu et al., 2020b). Pos- terior Networks (Charpentier et al., 2020) combine this with evidential learning by computing fistance-bbaed Bayesian evidence updates. Recently, an information-theoreticc per- spective on uncertainty estimation was proposed by Benkert et al. (2024). They argue that uncertainty estimation benefits from jointly considering all latent representations through- out a model to mitigate information loss. They introduce lin- ear classification heads at each layer that are trained jointly with the backbone classifier which prevents post-hoc uncer- tainty estimation. In contrast, we derive MPNN-based DPI to reveal the importance of jointly modeling all hid-
4. Uncertainty Estimation in MPNNs through Information Theory
We approach MPNNs from the perspective of information theory and track the informativeness of its latent representa- tions throughout the model.
4.1. Information in NNs for L.I.. Data
The seminal work of Tishby & Zaslavsky (2015) phrases training a NN to predict a target variable from an input representation as equivalent to finding a so-called suffi- cient statistic (X) that fully describes Y and at the same time retains minimal information about X:
Grathwohl et al. (2019) propose
I (X) arg min (=I(:)(X))=((xx))
T(X))
(3)
The optimal mapping f of Equation (3), therefore, is maxi- mally informative about the target while at the same time discarding all information contained in X that is uninforma- tive regarding the learning problem. In practice, the solution of Equation (3) is unattainable and methods instead realize trade-off between the informativeness of latent represen- tations about the target and the compression of the input representation I(X; ()). For example, NNs benefit from learning a maximally compressed representation that loses as little predictive information as possible.
3

---

Uncertainty Estimation for Heterophilic Graphs Through the Lens of Information Theory
The layer-wise processing of the input data by NN induces Markov Chain of hidden representations ( as depicted in Figure 2. Even though these transitions are deterministic, this perspective allows describing the information that each hidden representation z(4) retains about the true label Y (and input X) with the data processing inequality (DPI) (Cover, 1999): It states that processing a random variable can only decrease the information about its parents:
Further, we argue that on heterophilic graphs, each latent embedding contains different information about the target variable. We verify this with simple density-based uncer- tainty estimator on the joint representations of all layers that provides state-of-the-art epistemic uncertainty.
We track the information about each node e's representation throughout the model individually. To that end, we repre- sent the graph as an ego-graph Go with v as an anchor and analyze the informativeness of its representations regarding the label Y of this anchor node.
I(Y;Z I(Y;
(4)
< -I(Y;20)
For MPNNs, in each iteration, only the representations of u's direct neighbors NVv) propagate information to update e's hidden representation. It is therefore useful to decompose the input, each node in the ego-graph G.. into disjoint sets k according to their shortest-path distance to v.
The DPI Equation (4) holds with equality only if no infor- mation about Y is lost when the i + 1-th layer transforms z into Z ( This information loss is quantified by [() z((+1)). Intuitively, it measures the information about Y that is provided by z given Z (,+ This is exactly the information about that is described by ( but not anymore by 1)++1), A similar statement about information loss regarding X follows from the DPI as well.
The information about is not only encoded in v's repre- sentation but can also be retained in the latent representation of all other nodes in the graph. To represent this, also introduce random variables that correspond to the repre- sentations of all nodes in each g( We write 7 for the representations of the nodes in g(+²) after the i-th layer. The unprocessed information is denoted with G( Since g:! contains just itself, the random variables z track v's representation over the MPNN layers which we denote with z() for brevity and consistency with the DPI (Equation (4)).
Y
x
2(1)
X
2(++1)
Figure 2. NNs for i..d. data induce a Markov Chain of random variables ( that correspond to its hidden representations.
Benkert et al. (2024) link this information loss to problems with density-based based epistemic uncertainty estimators. These quantify uncertainty with an estimate of p(X) that often directly computed from NN representations the penulti- mate level Z (14-1) or from the logits (4) (Wu et al., 2023; Liu et al., 2020a). Because of the DPI, deep representations discard crucial information about both input and target. This is sometimes also referred to as feature collapse ( (Van Amers- foort et al., 2021). One remedy to this problem is enforcing distance preservation constraints on the NN (Mukhoti et al., 2021a; Liu et al., 2020a; Van Amersfoort et al., 2020). How- ever, this is restrictive regarding the model architecture, prevents post-hoc uncertainty estimation, and often comes at decreased performance (Benkert et al., 2024).
The resulting probabilistic model of MPNNs is depicted in Figure In contrast to the i.i.d. case, it is not Markov Chain. Nonetheless, its structure reflects intuitive properties about MPNNs that allow relating the information of the node representations z between subsequent layers to each other, similar to the DPI in Equation (4).
1. For any layer i, the label Y and the representation (Z(* are conditionally independent given G( Consequently, the mutual information I(Y; (((a))) = 0 and the sequence of random variables Y + G(Ox) + ( form a Markov Chain. Because of the (i.i.d)) DPI, information about Y that was present in G(0:6) may be lost in 7(0) through processing by the MPNN layers.
4.2. A Data Processing Equality for MPNNs
For problems on graphs, the input X is twofold as it con- tains both node features F as well as the graph structure E.
2. z and G(++1) are conditionally independent given G(O:.). Therefore, z(6) can not contain any additional information that the (i + 1)-hop neighbors gl of v provide and that was not already present in g(():))
Furthermore, node features and targets of individual nodes
depend on those of other nodes. Therefore, the information- theoretic analysis of (Tishby & Zaslavsky, 2015) does not apply MPNNS in general. We close this gap by devising suitable probabilistic model that tracks the information about a node's label Y in the hidden representations of an MPNN in general. Importantly, we do not make any as- sumptions about how the MPNN layers are realized. We then derive an analog to the DPI which reveals that the in- formation can also increase at deeper layers in the network.
3. In contrast to NNs for i.i.d. data, Z and G((:.) are not conditionally independent given ())-1) The same holds for z and Y. That means that information that is lost through previous layers can be recovered in deeper representations. Intuitively, the other nodes in the graph may retain this information and can transfer it back to u in subsequent MPNN iterations.
4

---

Uncertainty Estimation for Heterophilic Graphs Through the Lens of Information Theory
z(+ of the DPI in Equation (4). loss term I(Y;Z
2
2
2
2
Notably, the information from G( that is captured in e's representation does not necessarily have to decrease with depth, which contrasts the DPI. If e's neighbors recover more information than the i MPNN layer successively lose in e's embedding. A assumes a negative value, effec- tively resulting in information gain. This gain is naturally bounded by the information that all ((uaa) provide about Y.
Z
Proposition 4.1. Let Z z(t1), G! and Y be as in The- orem 4. The relative information about Y that (.6+1) and Z hold in terms of the information in G( is bounded by -IYY: Gua)-
2
(0:4 < <I(Y;G ((:)))
The information gain term ((+) (++1) has correspondence in the DPI. It reflects the increasing receptive field of the node v at deeper layers: With each additional layer, the representation ( also depends on G The resulting
Figure 3. Probabilistic model of how the information is processed in MPNNs. The i-th layer updates the representations of cach k-order ego graph + descrihed by random variables ((+)
additional information I(Y: G 1) G( that is not lost through the (i + 1) 1)-th is given as:
The graphical model in Figure 3 also allows condense these properties into a novel analog to the DPI for MPNNs. The difference in informativeness between latent representa- tions decomposes additively into: (i) A (0:i) the information
Definition 4.2. Let ()) . ((+1)) G! and Y be as in The- orem 4.1. The information gain about in z(+1) that is provided by G(1+1) is defined as:
loss loss/ recovery regarding (((a)), and (ii) (1+1) the realized information gain through v's extended receptive field in the (i+ 1)-th MPNN iteration.
A (++1) I(Y; G (())))) +
I(Y: I(Y:G. (+1) G(++1) G( z((1)).
Theorem 4.1 (Data Processing Equality for MPNNs), Let z be random variables corresponding to the hidden rep- resentations of node in an MPNN according to Equa- tion (2) after the i-th layer. Let G, = G. and Y random variables representing the corresponding ego-graph and label. The information the subsequent representation ((i+1) holds about Y decomposes additively into the information w.t.t ((Os), and
Intuitively, A (4+1) takes all available additional information in I(Y; ((Y; G(++) G(O:))) and subtracts what is lost through
processing this information into Z Similar to the DPI, this loss is described by T(Y; G[ 1(,+1)).
Therefore, the gain A (1-1) is trivially upper bounded I(Y:G.+1) G(O:)) exactly when no information is lost. In the worst case, all information is lost and consequently, the information gain is lower bounded by 0 (see Proposi- tion A.
(+)
in 20 their relative information A (0:3)
the information gain A (i+1)
(+) w.r.l. G ((+1) G(
= =
A (0:1) (1+1)
(5)
(+)
4.3. An Information-basen Definition of Homophily
First, we analyze A (0:1) It measures how much information from G(0:)) is lost through the (i + 1) MPNN layer while also accounting for the recovery of previously lost informa- tion retained in v's neighbors and transferred back to ((++))
We propose novel definition of homophily grounded in information theory that enables studying how homophily af- fects the information in the latent representations of MPNNs.
Definition 4.3. Let G. and Y be as in Theorem 4.1. We define the information homophily between the (i + 11)hhpp neighbors G(i++) and the i-th order ego graph G(O:i) as:
Definition 4.1. Let (00)) z((+1, G.9, and be as in Theo- rem 4.1. The relative information about between (()) and ( contained in ((::i) defined as:
A (i+1) = I(G((+)) (((()) I(G(+)); (0-)) Y).
(0:1)
T(Y; G(.:)) --)
((+ G(::).00)) 2().
((+1) measures how much semantically relevant infor- hp mation is shared between the (i + 1)-hop neighbors of
(0:i) can roughly be seen as an analog to the information
5

---

Uncertainty Estimation for Heterophilic Graphs Through the Lens of Information Theory
node and the ego-graphs up to distance i. The term (GG(+1))) Y) quantifies the shared information that is not described by the label Y and, therefore, irrelevant for the task. By subtracting this term, our definition of ho- mophily only considers the shared information that is also meaningful in terms of Y. For example, in image classifica- tion, an image's background color does not affect its class and therefore also does not contribute to the information homophily according to this definition.
provides different semantic information: I(Y; T( Effective density-based epistemie uncertainty should consider all Z jointly.
We confirm the validity of this insight by opting for the most simple realization: We quantify epistemic uncertainty using a KNN-based density (Loftsgaarden & Quesenberry, 1965) on the concatenated latent representations z(1), ((1)) (see Appendix C.2). While our primary goal is to empirically motivate the principle of Joint Latent Density Estimation (JLDE), we conjecture that future work can benefit from more sophisticated density models.
Other than existing notions of homophily (Appendix C.I), by (++1) describes per-node homophily at each distance indi- vidually. For example, I compares a node's own features to those of its neighbors similarly to other definitions. In- stead of quantifying homophily through node labels or fea- tures alone, it only concerns the similarity of node features that are semantically relevant to the label Y. As computing the mutual information between random variables requires access to their joint distribution or samples from it, infor- mation homophily can typically not be computed for real data. However, it directly affects the upper bound on the information gain ((+) (1++1) each Z (i+1) can realize over the previous MPNN embeddings:
|| 1=1
u (v) - log == - -log Po
(i)
(6)
L (11
Σ
(7)
WEK-NN( E. 2(0)
JLDE can be applied post-hoc to any MPNN and enables uncertainty quantification with a single forward pass. Impor- tantly, in contrast to prior work, it does not rely on assump- tions regarding homophily, for example by post-processing uncertainty using graph diffusion (Stadler et al., 2021; Wu et al., 2023; Fuchsgruber et al., 2024b).
Proposition 4.2. Let _ and Y be in Theorem 4.1. The attainable information gain A (+) decreases with ho- mophily he (
5. Experiments
(++1) < <I(Y;G ((+1) G((00) = I(Y; - h 1.
We evaluate JLDE by exposing it to distribution shifts pro- posed by previous work (Stadler et al., 2021; Wu et al., 2023; Fuchsgruber et al., 2024b), each of which corresponds to different kind of anomaly. Like Shchur et al. (2019) and Stadler et al. (2021), we average all results over 10 dataset splits with 10 model initializations each and report the stan- dard deviations in Appendix E.
Proposition 4.2 reveals that with increasing information ho- mophily, each subsequent hidden representation can realize less information gain about the label. Intuitively, the se- mantic similarity between ((0:)) and G(++1) prohibits the latent representation ( to contain information that is not already contained in ((0:)), The more heterophilic graph is, the more of the semantically relevant information I(Y; G(++)) is exclusive to the (i + 1)-hop neighbors and can only first be captured by ((++))
5.1. Setup
Datasets and Distribution Shifts. We consider these three distribution shifts:
4.4. Uncertainty Estimation in MPNNs Through Joint Latent Density Estimation (JI.D))
(i) Leave-Out- ClasS (LoC). We exclude nodes in a sub- set of classes from the training set Vi and treat them as out-of-distribution (o.o.d.) during inference.
Proposition 4.2 implies that in homophilic graphs, the infor- mation gain of deeper embeddings over more shallow ones diminishes as nodes are semantically similar to their neigh- bors. Therefore, it suffices to estimate the data density from single latent representation (Fuchsgruber et al., 2024b).
(ii) Near Feature Perturbations. We randomly sample a subset of designated o.o.d. nodes and replace their fea- tures with noise during inference. We emulate a distri- bution shift with semantics similar to the training data through Bernoulli noise for datasets with bag-of-word features (CoraMI., PubMed, Chamaleon and Squirrel) and Gaussian noise M(H, )) for graphs with continu- ous features (Amazon Ratings, Roman Empire). Mean I and diagonal covariance Σ are the maximum likeli- hood estimates from the dataset.
Our analysis is especially insightful for heterophilic graphs. Since nodes in the i-th order ego graph G(¹) preferably connect to nodes with different semantics, G G((+1) likely contains information about Y that is different from the infor- mation in G.9) and the information gain A (++1) can assume large values. Consequently, each hidden representation
(+)
6

---

Uncertainty Estimation for Heterophilic Graphs Through the Lens of Information Theory
(iii) Far Feature Perturbations are generated by replac- ing the features of designated o.o.d. nodes with noise from (O0, J). For bag-of-word features, this distribu- tion shift can be seen as out-of-domaij
5.2. Results
out-of-Distribution Detection. Table I shows the o.o.d. detection performance of different epistemic and aleatoric uncertainty estimators. Post-hoc methods are applied to Res-GCN backbone (full results in Table 7). On heterophilic data, JLDE has high efficacy on all distribution shifts. On the homophilic CoraML, it compares well against other model-agnostic estimates. This underlines that the principle of JLDE is especially effective for heterophilic graphs where the information of the latent node representation after each layer can vary significantly. At the same time, in homophilic settings, it provides high-quality uncertainty without resort- ing to proteprocss with (homophilic) smoothing kernels like GPN, Safe, or GEBM.
We build on the insights of Platonov et al. (2023) regarding GNN evaluation on heterophilic data by primarily focus- ing on the novel heterophilic Amazon Ratings and Roman Empire datasets. The three other heterophilic datasets are binary classification problems that do not permit a LoC dis- tribution shift. Additionally, we evaluate our method the revisions of the heterophilic Squirrel and Chameleon datasets. We also study the two homophilic citation net- works CoraML (Bandyopadhyay et al., 2005) and PubMed (Namata et al., 2012) to compare JLDD to uncertainty esti- mators that explicitly leverage the homophily in the data.
Table 1. O.o.d. detection using different uncertainty estimators (best and runner-up). On heterophilic graphs, we perform the best while being competitive with other model-agnostic estimates on homophilic data. Grey cells indicate numbers associated with JLDE.
Backbone Models. JLDE can be applied post-hoe to any MPNN backbone. Since uncertainty estimation improves with predictive performance (Fort et al., 2021), we study the best-performing architectures according to Platonov et al. (2023) and our benchmark (Appendix D): Augmented ver- sions of GCN (Res-GCN), GATv2 with explicit separation between the own representation of a node and an aggregate of information from its neighbors (Res--AT-SSep) GATE, and GPRGNN. Additionally we compare JLDE estimates on FAGCN, FSGNN as GNNs for heterophilic graphs. See Appendix C.2 for details.
Near- Featureauuus
Fur Featurauurs
Model
AUC-ROC:
Acc-T
AUC-ROC
Acc.f
AUC-ROC
Aoc.T
Rii.)
(Ales. FFj.))
(Alea. Fpi.)
GPN
60.3/44.0
48.6
50.9466.4 4
38.1
54.8/77.3
38.0
SGCN
60.0/56.5
58.3
55.7544.1
45.5
12.5/7.1
30.6
BGCN
54.9/50.7
53.0
58.1/16.2
12.4
38.3/73.6
28.8
Ronun Empire
GPRGNN
06.5/33.4
78.1
86.5/87.9
64.8
17.6/79.1
61.0
FSGNN
73.0/70.2
80.6
70.5/76.3
71.6
21.9/3.7
56.9
FAGCN
72.7/68.8
83.6
77 8785.6
08.0
25.9//122
44.3
Ens.
76.4/76.2
78.4/78/2 22
HM 99/22/66.0 9
MCD
76.3/7569 9
75.8/72.5
82,7/72.9
Safe
73.3/72.5
73.3661.
87.6
24.5/81.3
7 4
72.3
53. 11.00/110
$3.0/92.0
70.6
Uncertainty Estimators. We compare JLDE to different un- certainty estimators: GPN and SGCN quantify uncertainty using Evidential Learning. Bayesian GCNs (BGCNs) model the weights of a GCN as Gaussians. For other baselines, we use a logit-based EBM as epistemic uncertainty. Addi- tionally, compare to the following other model-agnostic methods: An ensemble of 10 (Ens.), Monte-Carlo Dropout (MCD), energy- based uncertainty from logits (EBM), as well as the graph-specific EBMs GNN-Safe and GEBM.
GEBM
73.3/53.6
74.5
83.0990.9
JLDE
73.3/76.9
74.5
83/0/1000
GPN
48. 1/.1
54.2
54.3452.4
46-8
52.6/58.5
47.0
SGCN
47.8/48.6
55.5
54.054.2
47.2
27.7/22.8
33.5
BGCN
52.7/19.0
51.4
54.1/16.6
61.2
41.5/72.1
33.5
Amuizoeo Ratings
GPRGNN
52.5/52.1 1
57.9
62.1/70.0
50.6
10.9M88.
34.1
FSGNN
54.4//53.6
58.8
45.1438.6 6
49.1
12.7/2.2
38.0
FAGON
53.1/53.3
58.1
30.8662.9 9
51.2
17.9/12.0
31.7
Ens.
51.4/57.9
60.3663.6
74.3/50.4
MCD
40.2/53.5
56.6/58.2
72.9/33.2
Safe
EBM
48.8/18.0
48.8/48.9 9
56.0
54.8455.3
$4.8/66.1
46.2
78.2/07.2
78.2 29.2//4.44
47.3
GEBM
48.8/19.9
54.8/17.1 1
78.2/58.0 9
JLDE
48-8/61.2
54.8665.4
78-2/99.2
Metrics. Like previous work (Stadler et al., 2021; Fuchs- gruber et al., 2024b), our main proxy for the quality of an uncertainty is o.o.d. detection. We report the AUC-ROC and AUC-PR metrics to the binary classification problem of distinguishing between in in-distribution (i.d.) and o.o.d. data. We supply how well an uncertainty estimator identifies erroneous predictions in Appendix E.3. Since JLDE is a post-hoc estimator it does not affect the backbone's 's (soft- max) predictions and the associated alcatoric uncertainty (quantified as the maximal softmax response) and its calibra- tion. Both are backbone-dependers and we report them only for completeness. While beyond the scope of this work, we remark that our framework permits other post-hoc improve- ments like temperature scaling (Guo et al., 2017). We report the Expected Calibration Error (ECE) (Nacini et al., 2015) of each backbone in Appendix E.4 for completeness.
GPN
82.8/11. 9
89.9
55.4653.8
80.9
40. 1/61 .4
81.1
SGCN
86.3/87.2
$9.4
63.7866. .9
82.0
16.8/12.2
34.4
BOCN
85.3/75.1
88.3
59.8457.7
81.3
28.5/34.3
31.1
GPRGNN
17.77
90.2
61.0765.9 9
84,1
17.590.
37.5
ESGNN
82 7/8188
87.6
63.5699.8 8
71.7
6.816
40.2
CoaMM
FAGCN
85.0/56
88.9
08, 777.7
81.4
11:2/1.2
40.4
Ens.
81.381.4
52,7552.8
94.7/78.4
MCD
79.0/78.1
54.8/55.1
88.0/61.0
Safe
EBM
76.9/76.0
76.9/50.7
88.3
$2.1/51.0
52.1/53.3
79.6
85.0993.5
85.0/72.0
77.1
GEBM
76.9/51.4
52.1/58.3
55.09801.
JLDE
763080088
52.1/54.9
85.095.77
Misclassification Detection. Like prior work (Stadler et al., 2021; Fuchsgruber et al., 2024b), we find that aleatoric un- certainty estimators are better equipped for misclassification detection than epistemic uncertainty (Tables 13 and 14). JL.DE performs similarly to other epistemic estimates.
7

---

Uncertainty Estimation for Heterophilic Graphs Through the Lens of Information Theory
Roman Empire
Amazon Ratings
CoraML
0.80
0.62
AUC-ROC
0.75
0.60
Density
Joint
0.70
0.58
0.60
Not Joint
Partial
0.65
0.55
[0]
11]
[3]
10.31
All (Cat)
[1]
[3]
10
IIV
All (Cat)
[0]
[2]
10.3)
All (Add)
All (Cat)
Layer
Layer
Layer
Figure 4. O.o.d. detection AUC-ROC (t) under leave-out-classee distribution shift when estimating the density from different layers of Res-GCN backhone. On heterophilic datasets (Amazon Ratings, Roman Empire), joint density estimation performs best as different layer representations provide different information.
5.3. Ablations
Table 2. O.o.d. detection rank of modcl- epistemic estima- tors averaged over all distribution shifts (best and runner-up).
Joint Density Estimation. We empirically verify anal-
Model
Amazon Ratings
Chameleon
Squirrel
CoraML
PubMed
ysis regarding the informativeness of latent node represen- tations in different MPNN layers by estimating the data density from (i) each latent representation (1)) individually, (ii) the concatenation of only the first and last represen- tations (1) and 2(4), (iii) each latent representation (e) independently and averaging the uncertainty estimates (All (Add)), and (iv) the concatenated latent representations of all layers in Equation (6) (All (Cat)).
Empire
Ens.
Res CCN
MCD
1.2
3.8
1.2
1.8
EBM
3.0
4.0
3.8
4.0
Safe
4.5
4.0
GEBM
5.8
4.5
2.8
2.5
JLDE
Ens.
1.8
2.8
5.5
2.8
2.8
2.5
Rey-GAT
4.0
EBM
3.2
3.8
3.5
4.2
4.2
Safe
4.2
3.5
5.0
3.8
GEBM
6.0
5.5
1.8
2.8
Figure 4 confirms the claims of Section 4.2: For heterophilic graphs, each latent representation (6) can contain different information originating from different k-hop neighborhoods of each node. The information can both decrease and also in-
JLDE
2.0
2.8
3.5
Ens:
2.8
MCD
4.0
4.2
4.0
3.8
4.5
4.8
Res-GATE
Safe
4.5
3.2
4.2
4.2
4.8
4.5
GEBM
5.5
5.5
2.0
3,0
crease with depth as (0:e) can assume negative and positive values. For heterophilic problems, only jointly considering all latent representations results in a faithful representation of the data density p(G.) and, consequently, high-quality uncertainty. The advantage in modeling a joint distribution aggregating per-layer density suggests an interplay be- tween the information contained in each z(i) that may be further exploited with more sophisticated methods to obtain even better approximations the data density.
JD
2.2
2.0
Ens.
3.2
2.8
5.2
3-5
5.2
GPRONN
EBM
3.8
4.5
4.2
4.2
3.5
3.8
5.2
4.0
4.8
GEBM
5.2
2.8
2.0
2.5
1.8
JLDE
122
1.8
3.2
detection performance of JLDE on different MPNN back- bones under different distribution shifts. JLDE outperforms other baselines in terms AUC-ROC, This is also summa- rized by Table 2 that shows the rank (4) of each estimator averaged over all three distribution shifts. Therefore, our theoretical analysis applies to broad range of MPNNs on which the concept of JLDD provides high-quality epistemic uncertainty for both heterophilic and homophilic graphs.
For the homophilic CoraML graph, we also confirm our hypothesis that each additional k-hop neighborhood tributes only information similar to the previous node rep- resentation z ((-1), Each MPNN iteration amplifies this information and there is no benefit in considering shallow representations as well. Similarly, JLDE's performance matches estimating epistemic uncertainty from the last layer only. This finding aligns well with the success of uncertainty estimators that are derived from deep layers like GEBM in homophilic problems. Nonetheless, including shallow rep- resentations in the density estimation does not notably harm the performance of JLDE's on homophilic graphs.
6. Limitations
We propose design principle for epistemic uncertainty heterophilic graphs but do not aim to improve aleatoric uncertainty or its calibration. To verify the applicability of this principle, we opt for the most simple realization of JLDE but conjecture that more sophisticated methods for combining hidden representations and estimating their den-
Backbones.
The principle JLDE can be applied post- hoc to any MPNN. In Tables 9 to II, we evaluate the o.o.d.
8

---

Uncertainty Estimation for Heterophilic Graphs Through the Lens of Information Theory
sity likely further improve the resulting uncertainty estimate. Also, we focus our evaluation node classification but the cetrmattion-thooetti perspective and its implications apply to regression problems and other non-i.idd domains that can be cast into graphs as well.
Brier, G. W. Verification of forecasts expressed in terms of
probability. Monthly weather review, 78(1):1-3, 1950.
Brody, S., Alon, U., and Yahav, How Attentive are Graph Attention Networks?, January 2022.
Charpentier, B., Zügner, D., and Günnemann, S. Posterior Network: Uncertainty Estimation without OOD Samples via Density- Counts. In Advances in Neural Information Processing Systems, volume 33, pp. 1356- 1367. Curran Associates, Inc., 2020.
7. Conclusion
We introduce JLDE design principle for uncertainty estimation on heterophilic graphs that is applicable to broad range of MPNNs. Through an information- theoreeti analysis of MPNNs, we derive an analog to the DPI that enables tracking the information over the layers of the net- work. reveals that in heterophilic graphs, each embed- ding provides unique information about the data distribution. Leveraging this insight even with a simple density estimator consistently outperforms existing approaches different datasets, distribution shifts, and backbones. We believe that our work provides the theoretical groundwork for advanc- ing uncertainty estimation on graphs beyond the homophily assumption of prior work.
Chien, E., Peng. J., Li, P., and Milenkovie, O. Adaptive Universal Generalized PageRank Graph Neural Network, October 2021.
Cover, T. M. Elements of information theory. John Wiley Sons, 1999.
Das, S. S., Arafat, N. A., Rahman, M., Ferdous, S., Pothen, A., and Halappanavar, M. M. Sgs-gmn: A supervised graph sparsification method for graph neural networks. arXiv preprint arXiv:2502. 10208, 2025.
Dusenberry, M., Jerfel, G., Wen, Y., Ma, Y., Snoek, J., Heller, K., Lakshminarayanann B., and Tran, D. Efficient and scalable bayesian neural nets with rank-1 factors. In International conference on machine learning, pp. 2782- 2792. PMLR, 2020.
Impact Statement
We conduct theoretical analysis of message--pssiingg neural networks and derive design principles for accurate uncer- tainty estimation on heterophilic graphs. This contributes to the advancement of reliable and trustworthy AI. Nonethe- less, we want to explicitly encourage researchers and practi- tioners who use or build on our insights to actively consider and evaluate our proposed uncertainty estimate, especially in high-risk domains.
Farquhar, S., Smith, L., and Gal, Y. Liberty or depth: Deep bayesian neural nets do not need complex weight pos- terior approximations. Advances in Neural Information Processing Systems, 33:4346 4357,,443,-44 2020.
Fey, M. and Lenssen, J. F. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Repre- sentation Learning on Graphs and Manifolds, 2019.
References
Bandyopadhyay, S., Maulik, U., Holder, L. B., Cook, D. J., and Getoor, L. Link-based classification. Advanced methods for knowledge discovery from complex data, pp. 189-207, 2005.
Fort, S., Ren, J., and Lakshminarayanan, B. Exploring the limits of out-of-distribution detection. Advances in Neural Information Processing Systems, 34:7068-7081, 2021.
Bazhenov, G., Ivanov, S., Panov, M., Zaytsev, A., and Bur- naev, E. Towards ood detection in graph classification from uncertainty estimation perspective, 2022. URL 10691.
Fuchsgruber, D.,, Wollschläger, T., Charpentier, B., Oroz, A., and Günnemann, S. Uncertainty for active learning on graphs. arXiv preprini 20XX::2005.01462., 2024a.
https: //ar:////axvv.. org. wttp:/i..rrg/ab/////eee
Fuchsgruber, D., Wollschläger, T., and Günnemann, Energy-based Epistemic Uncertainty for Graph Neural Networks, July 2024b.
Benkert, R., Prabhushankar, M., and AlRegib, G. Transi- tional Uncertainty with Layered Intermediate Predictions, June 2024.
Gal, Y. and Ghahramani, Z. Dropout as a bayesian approxi- mation: Representing model uncertainty in deep learning, 2016.
Blundell, C., Corneiise, J., Kavukcuoglu, K., and Wierstra, D. Weight Uncertainty in Neural Networks, May 2015.
Bo, D., Wang, X., Shi, C., and Shen, H. Beyond Low- frequency Information in Graph Convolutional Networks, January 2021.
Gasteiger, J., Bojchevski, A., and Günnnemann, S. Predict then Propagate: Graph Neural Networks meet Personal- ized PageRank, October 2018.

---

Uncertainty Estimation for Heterophilic Graphs Through the Lens of Information Theory
Gasteiger, J., Weißenberger, S., and Günnemann, S. Diffu- sion Improves Graph Learning, April 2022.
Liu, J., Lin, Z.., Padhy, S., Tran, D., Bedrax Weiss, T., and Lakshminarayanan, B. Simple and principled uncertainty estimation with deterministic deep learning via distance awareness. Advances in neural information processing systems, 43:7498-7512, 2020a.
Gawlikowski, J., Tassi, C. N., Ali, M., Lee, J., Humt, M., Feng, J., Kruspe, A., Triebel, R., Jung, P., Roscher, R., et al. A survey of uncertainty in deep neural networks. Artificial Intelligence Review, 56(Suppl 1):1513-1589, 2023.
Liu, W., Wang, X., Owens, J., and Li, Y. Energy-based out- of-distribution detection. Advances in neural information processing systems, 33:21464 21475, 2020b.
Grathwohl, W., Wang. K.-C.,, Jacobsen, J.-H., Duvenaud, D., Norouzi, M., and Swersky, K. Your classifier is secretly an energy based model and you should treat it like one. arXiv preprint arXiv: 1912. 2019.
Liu, Z.-Y., Li, S.-Y., Chen, S., Hu, Y., and Huang, S.- J. Uncertainty aware graph gaussian process for semi- supervised learning. Proceedings of the AAAI Confer- ence on Artificial Intelligence, volume 34, pp. 4957-4964, 2020c.
Guo, C., Pleiss, G., Sun, Y., and Weinberger, K. Q. On cali- bration of modern neural networks. In Precup, D. and Teh, Y. W. (eds.), Proceedings of the 34th International Confer- ence on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 1321-1330 PMLR, 06 ngs mmlr.
Loftsgaarden, D. O. and Quesenberry, C. A nonparametric estimate of multivariate density function. The Annals of Mathematical Statistics, 36(3):1049-101), 1965.
11 Aug 2017. URL htwps:ttp//ooc press/ /aass//7i0 /v70 0 hgt//ogollaaaammm
Luan, S., Hua, C., Lu, Q., Zhu, J., Zhao, M., Zhang, S., Chang, X.-W., and Precup, D. Revisiting Heterophily For Graph Neural Networks, October 2022.
Hamilton, W. L., Ying. R., and Leskovec. J. Inductive Representation Learning on Large Graphs, September 2018.
Luan, S., Hua, C.,, Xu, M., Lu, Q. Zhu, J., Chang, X.-W., Fu, J., Leskovec, J., and Precup. D. When do graph neural networks help with node classification? investigating the impact of homophily principle on node distinguishabil- ity, 2024. URL https: : arriv. org/ abs/ 2304. 14274.
Hasanzadeh, A., Hajiramezanali, E., Boluki, S., Zhou, M., Duffield, N., Narayanan, K., and Qian, X. Bayesian Graph Neural Networks with Adaptive Connection Sam- pling, June 2020.
Hüllermeier, E. and Waegeman, W. Aleatoric and Epistemic Uncertainty in Machine Learning: An Introduction to Concepts and Methods. Machine Learning, 110(3)4457- 506, March 2021. ISSN 0885-6125, 1573-0565. doi:
Malinin, A. and Gales, M. Predictive uncertainty estima- tion via prior networks. In Bengio, S., Wallach, H., Larochelle, H., Grauman, K., Cesa-Bianchi, N., and Garnett, R. (eds.), Advances in Neurul Information Processing Systems, volume 31. Curran Associates, Inc., neurips.
Jin, W., Derr, T., Wang, Y., Ma, Y., Liu, Z., and Tang, J. Node Similarity Preserving Graph Convolutional Net- works, March 2021.
2018. URL httpe//sssseppptt///////leele cc paper htep/aper_fileeeeeeee 3ea See2dd550es2ceeecceea00003333363 pdf.
Kingma, D. P. and Ba, J. Adam: A method for stochastic optimization. arXiv preprint arXiv: 2014.
Maurya, S. K., Liu, X., and Murata, T. Improving Graph Neural Networks with Simple Architecture Design, May 2021.
Kipf, T. N. and Welling, M. Semi-Supervised Classification with Graph Convolutional Networks, February 2017.
Lakshminarayanan, B., Pritzel, A., and Blundell, C. Simple and scalable predictive uncertainty estimation using deep ensembles, 2017.
Mukhoti, J., Kirsch, A., van Amersfoort, J., Torr, P. H., and Gal, Y. Deep deterministic uncertainty: A simple baseline. arXiv preprint 1rXiv:2102./1558 2021a.
Li, X., Zhu, R., Cheng, Y., Shan, C., Luo, S., Li, D., and Qian, W. Finding Global Homophily in Graph Neural Networks When Meeting Heterophily, May 2022.
Mukhoti, J., van Amersfoort, J., Torr, P. H., and Gal, Y. Deep deterministic uncertainty for semantic segmentation. arXiv preprint
2021b.
Lim, D., Hohne, F, Li, X., Huang, S. L., Gupta, V., Bhalerao, O., and Lim, S.-N. Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods, October 2021.
Mustafa, N. and Burkholz, R. GATE: sive neighbors. Salakhutdinov, R., Kolter, Z., Heller, K., Weller, A., Oliver, N., Scarlett, J., and Berkenkamp. F. (eds.), Proceedings of the 41st International Conference
How to keep out intru-
10

---

Uncertainty Estimation for Heterophilic Graphs Through the Lens of Information Theory
on Machine Learning, volume 235 of Proceedings of Ma- chine Learning Research, pp- 36990-37015. PMLR, 21- 27 Jul 2024. URL https: pttpp//ooocee...ee/eo/pp/. mllr. press/v235, http3////mmsaaaaaaaaaaaa html.
Sensoy, M., Kaplan, L.,, and Kandemir, M. Evidential deep learning quantify classification uncertainty. Advances in neural information processing systems, 31, 2018.
Shchur, O., Mumme, M., Bojchevski. A., and Günnemann, S. Pitfalls of Graph Neural Network Evaluation, June 2019.
Naeini, M. P., Cooper, G., and Hauskrecht, M. Obtaining well calibrated probabilities using bayesian binning. In Proceedings of the AAAI conference on artificial intelli- gence, volume 29, 2015.
Stadler, M., Charpentier, B., Geisler, S., Zügner, D., and Günneeann, S. Graph Posterior Network: Bayesian Pre- dictive Uncertainty for Node Classification. In Advances Neural Information Processing Systems, volume 34, pp. 18033-18048, Curran Associates, Inc., 2021.
Namata, G., London, B., Getoor, L.., Huang, B., and Edu, U. Query-driven active surveying for collective classification. In 10th international workshop on mining and learning with graphs, volume 8, pp. 1, 2012.
Thiagarajan, J., Amirudh, R., Narayanaswamy. V. S., and Bremer, T. Single model uncertainty estimation via stochastic data centering. Advances in Neural Informa- tion Processing Systems, 35:8662-8674, 2022.
Ng, Y. C., Colombo, N., and Silva, R. Bayesian semi- supervised learning with graph gaussian processes. Ad- vances in Neural Information Processing Systems, 31, 2018.
Tishby, N. and Zaslavsky, N. Deep Learning and the Infor- mation Bottleneck Principle, March 2015.
Page, I.. The pagerank citation ranking: Bringing order to the web. Technical report, Technical Report, 1999.
Trivedi, P., Heimann, M., Anirudh, R., Koutra, D., and Thiagarajan, Accurate and scalable estimation of epistemic uncertainty for graph neural networks. arXiv preprint arXiv:2401.03:: 2024.
Paszke, A., Gross, S., Chintala, S., Chanan, G., Yang, E., DeVito, Z., Lin, Z., Desmaison, A., Antiga, L., and Lerer, A. Automatic differentiation in pytorch. In NIPS-W, 2017.
Van Amersfoort, J., Smith, L., Tch, Y. W., and Gal, Y. Un- certainty estimation using a single deep deterministic neural network. In International conference on machine learning, pp. 9690-9700. PMLR, 2020.
Pei, H., Wei, B., Chang, K. C.-C., Lei, Y., and Yang, B. Geom-GCN: Geometric Graph Convolutional Networks, February 2020a.
Van Amersfoort, J., Smith, L., Jesson, A., Key, O., and Gal, Y. On feature collapse and deep kernel learn- ing for single forward pass uncertainty, arXiv preprint arXiv: 102. 1409, 2021.
Pei, H., Wei, B., Chang, K. C.-C., Lei, Y., and Yang, B. Geom-GCN: Geometric Graph Convolutional Networks, February 2020b.
Platonov, O., Kuznedelev, D., Diskin, M., Babenko, A., and Prokhorenkova, L. critical look the evalua- tion of GNNs under heterophily: Are we really making progress?, February 2023.
Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., and Bengio, Y. Graph Attention Networks, February 2018.
Wang, F., Liu, Y., Liu, K., Wang, Y., Medya, S., and Yu, P. S. Uncertainty in graph neural networks: A survey, 2024. URL https::////.. aatpaaxivvvv../.../..aa........a org wrro////// abs 20003 07185.
Platonov, O., Kuznedelev, D., Babenko, A., and Prokhorenkova, L. Characterizing Graph Datasets for Node Classification: Homophily--Heteropiiy Dichotomy and Beyond, March 2024.
Wang. G., Li, W., Aertsen, M.. Deprest, J., Ourselin, S., and Vercauteren, T. Alcatoric uncertainty estimation with test-time augmentation for medical image segmentation with convolutional neural networks. Nearocomputing, 338:34445, 2019.
Qazaz, C. S. Bayesian error bars for regression. 1996.
Rabe, M., Milz, S., and Mader, P. Development methodolo- gies for safety critical machine learning applications in the automotive domain: A survey. In Proceedings of the IEEF/CVF Conference on Computer Vision and Pattern Recognition, pp. 129-141, 2021.
Wen, Y., Tran, D., and Ba, J. Batchensemble: an alterna- tive approach efficient ensemble and lifelong learning, arXiv preprint arXiv:2002.06713: 2020.
Rong, Y., Huang, W., Xu, T., and Huang, J. DropEdge: Towards Deep Graph Convolutional Networks on Node Classification, March 2020.
Wu, Q., Chen, Y., Yang, C., and Yan, J. Energy- based out- of-distribution detection for graph neural networks. arXiv preprint arXiv:2302 302.:2390202444 2023.

---

Uncertainty Estimation for Heterophilic Graphs Through the Lens of Information Theory
Xu, Z. and Saleh, H. Machine learning for reliability engineering and safety applications: Review of current status and future opportunities. Reliability Engineering & System Safery, 211:107530, 2021.
Yang, L., Wang, C., Gu, Cao, X., and Niu, B. Why do attributes propagate in graph convolutional neural net- works?, 2021.
Zhang, M. and Li, P. Nested graph neural networks, 2021. URL https: //wxxxxxvvvoro/. org/ abs/ 1///22111111111
Zhao, X., Chen, F., Hu, S., and Cho. J.-H. Uncertainty Aware Semi-Supervised Learning on Graph Data. In Advances Neural Information Processing Systems, vol- ume 33, pp. 12827-12836. Curran Associates, Inc., 2020.
Zheng, Z., Bei, Y.. Zhou, S., Ma, Y., Gu, M., XU, H., Lai, C., Chen, J., and Bu, Revisiting the Message Passing in Heterophilous Graph Neural Networks, May 2024.
Zhi, Y.-C., Ng, Y. C., and Dong, X. Gaussian processes graphs via spectral kernel learning. IEEE Transactions Signal and Information Processing over Networks, 2023.
Zhu, J., Yan, Y., Zhao, L., Heimann, M., Akoglu, L., and Koutra, D. Beyond Homophily in Graph Neural Net- works: Current Limitations and Effective Designs. In Advances in Neural Information Processing Systems, vol- ume 33, pp. 7793-7804. Curran Associates, Inc., 2020.
Zhu, J., Rossi, R. A., Rao, A., Mai, T., Lipka, N., Ahmed, N. K., and Koutra, D. Graph Neural Networks with Heterophily, June 2021.
12

---

Uncertainty Estimation for Heterophilic Graphs Through the Lens of Information Theory
A. Proofs
Theorem 4.1 (Data Processing Equality for MPNNs), Let ( be random variables corresponding to the hidden representa- tions of a node v in an MPNN according to Equation (2) after the i-th layer. Let G, L. and Y random variables representing the corresponding ego- gro-graph and label. The information the subsequent representation Z holds about Y decomposes additively into the information in z their relative information A (0:i)
(-) w.r.. G( and the information gain
(1+1) w.r.I. G((+t) | ((
= (V;
A (0:4)
(-) + (++1)
(-)
(5)
Proof. First, we notice that that for each layer i, Y Y G/0u)) + (z() form a Markov Chain. Therefore, the Data Processing Inequality (Equation (4)) applies and we obtain:
I(Y; = I(Y: - I(Y; G! 1 +
(8)
[(Y:G.:0)) -(
G(Y: (0:4) 22(0)).
(9)
Similarly, when applied to (i+1)
((Y;2(+1))) I(Y; G. 1)++t)) IYY: (0:++)) [z(1+))
= I[YY: I(Y:G!!m)) ((00))) + +I(Y: | (0:0)) - I(Y; I(Y; ((0+++1) 2((+1))
-I( +I(Y;G.(.)) ( + IY; G G(u))) - I((:: (.0+t1))) 2((t)))
+ +[V;20))+((;G) ((.s)) ) +[Y; G((+1) G!
+
-I(Y:G!00:) -(Y;
G z(it1)
= =I(Y:Z(0) [[YY:G (0:00 (2((1)) - T(Y: (.:0) 22(0))
((:0))
+ +(T(Y:G(+ G(++1) | (( - T(Y; | G(O:) 2(t1))
First, we apply the DPI to T(Y; I(Y;Z(++1) similar to what is outlined in the proof for (Y;7("), Then, we apply the chain rule
of MI. Going from the second to the third line, we use the DPI applied to I(Y; ((::)). We then apply the chain rule again by splitting Ge (1+++) into G(O+)) and G(++1) Lastly, we regroup terms to obtain the definitions for A (6+1) and (0:3)
(+)
(-)
Proposition 4.1. Let (1), z(1+1), G and Y be as in Theorem 4.1. The relative information about Y that (++1) and Z hold in terms of the information in ((0x)) is bounded by -IYY; Go.)..
A (0:1)
(-) < I(Y:G((:1)
Proof.
- -4 (0:0) (-) = T(Y; T(Y;G(00)) (0:1)
( - TTY: ((:))) 1((+1)
< I(Y;G.! 2
I(Y: ( (())
< G(Y:)
First, we insert the definition of A (0:1) (-)- Then, we use that MI is nen-negative. We then apply the chain rule of MI and, lastly, the negativetissssss of the chain rule once more to obtain the desired bound.
13

---

Uncertainty Estimation for Heterophilic Graphs Through the Lens of Information Theory
Proposition 4.2. Let G and be as in Theorem 4. I. The attainable information gain A (6+1)
(+) decreases with homophily
fo (
A (1+1) 2 <I(Y;G! G! = I(Y:G!!t) - ((4+1)
-
Proof.
(+11 (+) Y, G I(G
v I(Y;G. G(
() I(
I(G Y) I(G Y) - G(
=IGGHt Y) [(G (( (G G(O.)) Y)
=I(Y; h (1+1)
The inequality follows directly from the definition of A (4+1) (+) and MI being non-negative. Then, we apply the chain rule of
mutual information twice and regroup the terms to obtain the definition of homophily proposed in Definition 4.3.
Proposition A.1. Let z z G( and Y be as in Theorem 4.1. The gain in information about Y by additionally considering G is non-negative.
A = I(Y; (
(++1) (+)
G(O.)) 2 0.
Proposition A.1 also reveals that the information gain can be expressed as the information ( 'that is not already contained in (0:)) and, thus, must have originated in ((++1)
Proof.
(++) ())
I(Y:
G((+)
((00) I(Y: G(++)++)))))))
( z(+1))
T(Y; T(Y: G(++)
(000) + +T(;2((+))
G T(Y; G G(++1) G z(tll)
I(Y;; G(++1
(())) +1(Y; (+1) ((+1)) ((:+)) I(Y; G (+1) ( ((it1))
-I(Y: G(+1
z
((+1) (. I[Y: G
(1+1)
G (Ua) ())
I(Y;Z(+))
((:0)) G(
((+1) ((0z)) ((+ I(Y;
G(Y:G!tt) (i+ G( ((itl)
-[YY; ((+;2(++1)
(((:))
2 0.
First, we insert the definition ( Then we use that ((Y;Z(++1)
(((x++1)) v
= 0 from the DPI. We then split G (0:++1))
into G(++1) and ((O+), The chain rule of MI yields the next line. Then, we use the chain rule again but condition on (++1))
Next, the last two terms cancel and we are left with a which is non-negative.
B. Related Work: GNNs for Heterophilic Graphs
Paradigms for Heterophilic Node Classification. Compared to the more frequently studied homophilic graphs, heterophily poses difficulties because there are no community structures that can be exploited with smoothing. Methods that extend GNNs towards heterophilic graphs can be grouped into either adjusting the graph structure or changing the model to adapt to the high-frequency information. The former class of models alters the structure of the original graph to recover a homophilic problem. Pei al. (2020b) facilitate a virtual neighborhood to aggregate information from nodes that are geometrically
14

---

Uncertainty Estimation for Heterophilic Graphs Through the Lens of Information Theory
similar. Other work constructs surrogate adjacency adjust the propagation of information (Jin et al., 2021; Zheng et al., 2024). Also, resorting fully connected graph has been proposed (Li al., 2022). The latter paradigm is to model the high-frequency patterns in the graph. While for homophilic problems, graph diffusion has proven effective (Gasteiger et al., 2018; 2022). smoothing neglects the high-frequency patterns in heterophilic graphs. Generalizing Page-Rank Rank-based diffusion to allow for learnable negative weights assigned to each k-hop neighhorhood accommodates non-smooth features and improves performance (Chien et al., 2021). Other work like FAGCN (Bo et al., 2021) instead uses gating mechanisms to simultaneously account for low and high-frequency information. It can also be explicitly modeled using the graph Laplacian (Luan al., 2022). Other work shows that separating the own features of a node from adjacent information can improve performance well (Zhu al., 2020). FSGNN (Maurya al., 2021) aggregates representations from all k-hop neighborhoods.
Modeling Graph Inductive Biases for Performance. Recent work has focused on better understanding and refining the inductive biases embedded in GNNs, particularly regarding the role of graph structure, neighborhood similarity, and information aggregation across layers. Luan et al. (2022) revisit GNN performance under heterophily, challenging traditional homophily-based assumptions and proposing adaptive channel mixing to enhance representation learning across diverse neighborhoods. Similarly, Luan et al. (2024) analyze when GNNs are beneficial for node classification by introducing new metrics based intra- and inter-class node distinguishability,, showing that homophily alone does not fully explain GNN effectiveness. On the architectural side, Zhang & Li (2021) propose Nested GNNs, which extend beyond rooted subtrees to capture richer local substructures, emphasizing the importance of localized graph context. Complementarily, Yang et al. (2021) investigate feature propagation in GCNs and propose using the difference between a layer's input and output to mitigate over-smoothing, but do not aggregate information across multiple layers.
In contrast, our work examines the inductive biases of GNNs from an information -theoorttie perspective. We formally prove the benefits of leveraging information from all layers rather than relying solely on the final one or the difference of two. Building this insight, we propose novel,
seneeiicalll-groundeee uncertainty estimator that achieves sate-of-the-an performance. We further demonstrate that our approach is especially effective in graphs with strong heterophily, where neighbor information is less reliable and global feature integration becomes more important.
C. Experimental Details
C.1. Datasets
We use four heterophilic datasets and two homophilic datasets. Our primary focus lies on the novel heterophilic graphs provided by Platonov al. (2023) as they are devised specifically for benchmarking heterophilic models. Out of the five datasets the authors develop, only two correspond to multi-class classification problems and permit a LoC distribution shift: Amazon Ratings and Roman Empire. We additionally consider the Chameleon and Squirrel dataset (Pei et al., 2020a) but use the filtered versions that Platonov et al. (2023) provide to counteract data leakage and incorrect data pre-processing. For comparison, we also include two popular homophilic graphs: CoraMI. (Bandyopadhyay et al., 2005) and PubMed (Namata et al., 2012). The statistics for all six datasets are reported in Table 3.
Table 3. Statistics of the datasets: Features are bag of words (BoW). TFADF weighted word frequencies (IF/ word embeddings (WE) and mean of word embeddings (-WE).
Feature Type
LoC
#Nodes
#Edges
#Features
#Clases
hg
by
he
hA
%LoC
#LoC
Type
Amazon Ratings
24,492
186,100
300
M-WE
5
0.38
0.38
0.13
0.14
0.13
2
last
Roman Empire
22,662
65,854
300
WE
0.05
0.05
0.02
-0.05
0.19
7
last
Chameleon
890
17,708
2,325
BoW
5
0.24
0.24
0.04
0.03
0.42
2
first
Squirrel
2,223
93,996
2,089
BoW
5
0.21
0.19
0.04
0.01
0.57
2
first
CoraML
2,995
16,316
2,879
BoW
7
0.79
0.81
0.74
0.75
0.45
3
last
PubMed
19,717
88,648
500
TFADD-WF
3
0.80
0.79
0.66
0.69
0.40
1
last
Homophily. We report different measures of homophily for these datasets that are frequently used in the literature (Lim et al., 2021; Luan et al., 2022; Platonov et al., 2024):
15

---

Uncertainty Estimation for Heterophilic Graphs Through the Lens of Information Theory
1. Edge Homophily bg quantifies the fraction of edges with endpoints of the same class:
3g [(u, 2) E [3
Yu = yo
(10)
2. Node Homophily by first computes how many neighbors of each node match e's label and averages this quantity over all nodes:
Hu EN(u) ya = yo
hv
(1I)
M
[[(e]
VEV
3. Class Homophily measures the excess homophily of the graph compared to randomly wired graph with the same number of nodes and edges and less sensitive to the number of classes and their respective sizes (Lim et al., 2021);
max (0, 0,
Evev Hu fu ((() yu yoll {u V y. = cJ
hC
(12)
C
EvEVy.=A (V())
4. Adjusted Homophily hA as proposed by Platonov et al. (2024).
For all measures, high values indicate high degree of homophily in the graph and low values represent heterophily. Additionally, we visualize the class compatibility matrices (Zhu et al., 2021) for each graph in Figure 5. These allow to analyze homophily for each class. Each entry represents the fraction of edges that are incoming to nodes of a certain class, grouped by the class of the corresponding neighbor it originates from.
0.4
0.25
0.3
0.3
1210
0.2
0.2
0.1
0.15
6
8
10
12
14
16
2
0.10
(a) Amazon Ratings
(b) Roman Empire
(c) Chameleon
0.24
0.8
0.8
0.22
0.6
0.6
0.20
0.4
0.4
0.18
0.2
0.2
2
2
(d) Squirrel
(e) CoraML
(I) PubMed
Figure 5. Compatibility matrices for each dataset.
Distribution Shifts. We study three distribution shifts assess the quality of uncertainty estimator.
1. Saavv--ot-Cllasse (LoC): We designate a subset of all classes as o.o.d. and remove all corresponding nodes from the training and validation set. At inference, these nodes are treated as o.o.d. To ensure that the left-out nodes are
16

---

Uncertainty Estimation for Heterophilic Graphs Through the Lens of Information Theory
semantically different from the i.d. nodes, such that the of o.o.d. classes are dissimilar from rows of i.d. classes. For most datasets, selecting the l-last classes according to the enumeration of the data source meets this requirement. For the Chameleon and Squirrel datasets, we designate the I-first classes o.o.d.
the compatibility matrix in Figure In particular, we select classes
2. Near Feature Perturbations: inference. For distribution shift that is semantically similar the training distribution, we match the data modality of the training set. That is, for datasets with Bag-of-Words (BoW) features, we use Bernoulli noise. For datasets with continuous features, use Gaussian noise. Its mean and variance are the maximum likelihood estimates obtained on the clean data.
We randomly sample nodes designated as o.o.d. and replace their features with noise at
3. Far Feature Perturbations: Similar to the near feature perturbation shift, we replace the features of o.o.d. nodes with noise. Here, we use standard normal noise increase dissimilarity from the training distribution.
C.2. Models
While there is plethora of advances in the development of models for heterophilic graphs, we base most of our evaluation on the recent study of Platonov et al. (2023). They find that under fair conditions regarding hyperparameter tuning, many architectures devised for heterophilic problems can not outperform GNNs for homophilic graphs. It is important to remark, however, that these homophilic baselines are only effective for heterophilic data when coupled with certain augmentations: (i) Both the input as well as the final node representations after L. layers are processed with additional 1-layer MLPs. (ii) The feature transformation after each aggregation step is realized with 2-layer MLPs instead of the commonly used affine transformations. (iii) Residual connections
implemented enable information flow irrespective of the aggregation steps. (iv) Layer norm is applied before each aggregation step. Therefore, we realize our backbones with the same architectural choices that importantly deviate from what the corresponding works that introduce them suggest. We ablate models with and without residual connections. The architecture of models without residual connections can be described as follows:
HO= XWo
Ho o (HH)
AG; AGGREGATE (H--1,
H COMBINE (HL-1,AG))
H: = (H))
= softmaxi H Wr)
The architecture of models with residual connections is described by:
H XWo
Ho = (HH)
...
H LayerNorm (H-1)
AG; AGGREGATE (H) A)
H' = COMBINE (H), AGI)
H H + H
HÅ LayerNorm
softmax HH'
We study the following models as baselines/backbones in our work: A GCN (Kipf & Welling, 2017) and a GATv2 (Veličković al., 2018: Brody et al., 2022) with the aforementioned augmentations and no residual connections. Graph Posterior
17

---

Uncertainty Estimation for Heterophilic Graphs Through the Lens of Information Theory
Network (GPN) (Stadler al., 2021) an evidential method that uses a homophilic smoothing kernel to diffuse uncertainty. SGCN that uses the GCN architecture (without augmentations) for evidential learning coupled with student-feacher learning (Zhao et al., 2020). A Bayesian GCN (without augmentations) with Gaussian weights (Blundell et al., 2015). We apply the augmentations regarding residual connections to the GCN architecture (Res-GCN), an attention network that separates the own representation of each node from the aggregate of its neighbors as used in Platonov et al. (2023) See-S),--S,),, and the recently proposed attention-baid based Res-GATE (Mustafa & Burkholz, 2024). For completeness, we also study three best-perforning GNNs for heterophilic data in the study of Platonov et al. (2023): GPRGNN that generalizes Page-Rank diffusion to enabling high-frequency filters (Chien al., 2021), FAGCN (Bo et al., 2021) that relies on a gating mechanism to account for low-fre uow-freuency and high-frequency data, and FSGNN that aggregates information from all k-hop neighborhoods (Maurya et al., 2021).
C.3. Experimental Setup
Hyperparamter Tuning. For fair comparison, we tune all models over the same hyperparameter grid (Table 4) and select the best contiguration in terms of validation accuracy for each model to conduct further experiments which we report in this work. If not stated otherwise, we use two layers in each model. The optimized configurations are supplied in our code.
Hidden Dimension
Dropout
Learning Rate
Weight Decay
{64, 512]
0..2.
(0.01,
{0.0, 0.00013
Table Hyperparameter search space for all models if not stated otherwise.
Training for both the hyperparameter optimization as well as in the experiments we report in this work is done follows: We average all results over 10 different dataset splits and 10 model initializations each. We use early stopping the validation accuracy with a patience of 200 epochs. We optimize model weights using the ADAM optimizer (Kingma & Ba, 2014). Models are implemented in PyTorch (Paszke et al., 2017) and PyTorch Geometric (Fey & Lenssen, 2019) and trained on these 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.
Uncertainty Estimation. We use the following proxies for uncertainty estimation that closely follow Stadler al. (2021):
Aleatorc uncertainty is, general, estimated from the maximal softmax score P.. each model predicts: walea
max. Pe-
For evidential models (GPN and SGCN), we estimate epistemic uncertainty from the overall evidence a: utri - -E. O..
For EBMs, we compute epistemic uncertainty from the logits I as: urr = -loo E. exp( For models that offer no explicit estimate of epistemic uncertainty (GCN, GATv2, FAGCN, FSGNN, GPRGNN), we report results regarding this estimator as a simple and highly applicable post-hoc proxy.
For sampling baaee methods (BGCN, Ensemble, MCD), we compute epistemic uncertainty from the variability of softmax scores (+); uP c-1 E. Varap!". (f) For ensembles, use 10 members. For BGCNs and MCD, draw 50 samples during inference.
For JLDE, we KNN-based density estimate (Loftsgaarden & Quesenberry, 1965). For stability, we first use PCA to downproject each latent embedding 20 such that at least 95% of the variance is preserved. We refer to these as g We then approximate the density from the k--nearest neighbors (N(()) (z) C Virnin in the training set for each node v. We select k = 5 and compute:
2
(ii
(11²00
u (v) logg(G.)) x log pe
1
Σ
2000
(2)
(13)
K
WEI-NN(II 2(0)
Algorithm algorithmically implements this KNN-based realization of JLDE.
18

---

Uncertainty Estimation for Heterophilic Graphs Through the Lens of Information Theory
Algorithm 1 KNN-based JLDE
Input: Trained MPNN fo, graph G = (V, E), node features X, set of training nodes, number of neighbors
Output: Epistemic uncertainty u(v) = log pe (v) + C' for node v V Vuain
1: H H fa(g, X) {Obtain latent node representations)
2: H fX
3: for all E (o..... : L do
4: H +- 9C () {Optional Dimensionality Reduction]
5: end for
6: Z
1 H
7: u(v)
8: for all (N(()((, Virain) do
9: u(v) t + Zell2 {Omit normalizer]
10: end for
11: return u(v)
The non-concatenated version we ablate is given by:
2
u (v) logp(G.) x0 -log po (2)
(1:L)
Σ WENN(")(E
(x(0)
(z("){2
(2
(14)
k
i=1
D. Benchmarking Heterophilic GNNs
We benchmark the models described in Appendix C.2 in terms of accuracy on all six datasets (without distribution shifts) and report results in Table 5. We confirm the trends observed by Platonov et al. (2023): Many of the GNNs designated for heterophilic graphs fall short of the augmented homophilic models. In particular, all residual GNN variants (Res-GCN, Res-GATE, (es--GA-Seep) consistently perform well across different datasets. GPRGNN is the most consistent model explicitly designed to accommodate heterophilic data. Consequently, we utilize these as backbones in our experiments.
Table Accuracy of different models clean data (best and runner-up).
Roman Empire
Amazon Ratings
Model
Chameleon
Squirrel
CoraML
PubMed
GCN
62.7 7 =0.
t0.1
41.6+s.
41.6+2a
78.7
85.8
GATv2
87. 1o.s
51.010.6
41.813
34.7
78.7aa2
85.2
GPN
40.8
47.4+0.7
37 +
34.6+1.
81.3+1.
84.8+0.5
FAGCN
74.9
52.3taa
39.5
40.6
82.5
86.420.3
FSGNN
79.7+0.s
51.4+o.a
36.9+2.
36.0+2.
75.3+1.2
85.7+o.4
GPRGNN
71.0=o.s
52.01a.7
37.443.
35.311a
84.621.4
86.620.3
SGCN
50.9=1.8
48.9+0.4
39.0+a.n
36.9
82.6+1.4
86.3+0.3
BGCN
46.6=0.6
44.9+1.
39.0+3.4
34.1+28
82.0+1.4
86.0+o.a
Res-GCN
80.7
49.810.5
41.813.
41.912.
80.411.
85.710.3
Res-GATE
87 87.2+0.6
52.440.7
37.7
34.2
81.3
86.340.3
Res-GAT-Sep
88.0
53.610.
34.91c.0
34.921.
79.3
85.510.
E. Additional Results
F. Runtime of JLDE
The computational cost of KNN- based JLDE is governed by KNN, which can be implemented O * dhiideen + Perain * *k). For smaller training sets that are typical in transductive node classification, this is negligible but can become prohibitive for large training sets. this case, JL.DE can be realized with more efficient density estimators. We opt for KNN due to
19

---

Uncertainty Estimation for Heterophilic Graphs Through the Lens of Information Theory
its simplicity and applicability estimating high dimensional density from little d. However, in general, any density estimator can be used. We measure the runtime of KNN-based JLDE in Table 6. For all datasets with small training sets (all but Amazon Ratings), the cost of JLDE is comparable to competitors. Using multiple layers effectively increases dhidden by a factor of L in terms of runtime complexity. This only incurs a small additional cost (see comparison to 1-layer KNN-based JLDE in Table 6.
The memory complexity is also determined by the density estimator (KNN) and amounts to keeping the embeddings the training set in the memory, (f d.idden). Since by default, these activations are kept memory for a forward pass unless explicitly deallocated, there is no overhead in practice.
Table 6. Runtime (s) for different uncertainty estimators averaged over 25 runs, including a variation of JLDE (ours) that estimates uncertainty from one layer only (JLDE-IL).
Roman Empire
Amazon Ratings
Chame- leon
Uncertainty
Squirrl
CoraML
PubMed
JLDE
1.50+a.o
5.32-c.0
0.17 +
0.28+a.1
0.27+
0.71+o.1
JLDE-IL IL
1.36
4.04_o.1
0.13
0.282a..
0.23
0.71
GEBM
0.73
5.96_0.1
0.70
1.08
0.66
1.38
MCD
163.83
4.95
11.84
5.89
15.61
Ensemble
1.21
47 41.
1.53
1.89
1.53
3. 3.04+o.3
Energy
0.08
5.13
0.21
0.34=0.0
0.15.0.0
0.41
GPN
0.32
1.50
0.4622.0
0.75
0.64
1.1220.2
BGCN
5.64+n.a
20.06+0.0
3.30
8.56=a.1
4. 4.10.
10.58+o.1
SGCN
0.07
0.54=..o
0.10
0.27
0. 0.14
0.32
E.2. Out-of-Distribution Detection
We report o.o.d. detection performance of all baselines and JLDE with a Res-GCN backbone for all datasets and distribution shifts in Tables 7 and 8. JLDE performs the best on the high-quality novel Roman Empire and Amazon Ratings datasets, and the most consistent post-hoc method for Squirrel and Chameleon, even though sometimes other methods outperform it on occasions. On homophilic data, JLDE performs comparable other post-hoc estimators but is outperformed by methods dedicated to homophily (e.g. GPN, SGCN) for the LoC and near feature perturbations shifts. On far feature perturbations, it benefits from a density-based estimate and performs best.
Backbones. We compare JLDE to other model-agnostic estimators on four different backbones that perform the best in terms of accuracy according to Appendix D: Res-GCN, Res-RRT------ GAT-Sep. Res-GATE, and GPRGNN. Tables to 11 show that JLDE is the only method that consistently performs well on all distribution shifts. This also reflected by its average rank among these estimators: In Tables 2 and 12 ranks all estimators per dataset and distribution shift and averages them over the three distribution shifts such that LoC and both feature perturbations are weighted equally (i.e. weights of 50%/25% 2255/22555 Table 12 shows the average rank (1) only among epistemic estimators and also the rank among both epistemic and aleatoric estimators. JLDE consistently achieves the best or second- -bst rank on heterophilic data and performs competitively on homophilic datasets.
E.3. Misclassification Detection
We report the misclassification AUC-ROC and AUC-PR metrics in Tables 13 and 14. Consistent with prior work (Stadler et al., 2021; Fuchsgruber et al., 2024b), we find that aleatoric uncertainty often is the better proxy to detect erroncous predictions. As remarked in Section 5.2, JLDE is a model-agnostic post-hoc estimator that leaves the softmax predictions of the backbone model unaltered, This permits improvements regarding aleatoric uncertainty which is, however, beyond the scope of this work. JLDE performs similarly to other epistemic estimators in terms of misclassification detection.
E.4. Calibration
We report the Expected Calibration Error (ECE) (L) (Nacini et al., 2015) and Brier Score (L) (Brier, 1950) to assess the calibration of the backbones on each dataset without any distribution shifts in Tables 15 and 16. Again, the calibration
20

---

Uncertainty Estimation for Heterophilic Graphs Through the Lens of Information Theory
depends the softmax prediction of the model which is unaltered by post-hoc methods like JLDE. Improving calibration is therefore orthogonal avenue for future work heterophilic graphs.
Like other epistemic uncertainty estimators (e.g. GPN (Stadler et al., 2021) or EBMs (Fuchsgruber et al., 2024b; Wu et al., 2023)), JLDE's epistemic uncertainty estimate is not normalized to [0, 1] which prohibits measures like ECE. Instead, we visualize how the confidence (i.e. the inverse uncertainty) of JLDE correlates with the model accuracy. To that end, we normalize the confidence of different runs [0, 1] and compute the average model accuracy on the test set over 20 bins.
Figure shows that except the Chameleon and Squirrel datasets, JLDE outputs confidence that is well aligned with predictive performance. We suspect that for the two datasets where this correlation is less pronounced, the poor model accuracy overall inhibits uncertainty calibration.
Roman Empire
Amazon Ratings
Chameleon
0.8
1.0
0.7
0.8
0.8
Accuracy
0.6
0.6
0.6
0.5
0.4
0.4
0.2
0.4
0.3
0.0
Squirrel
CoraMI
PubMed
1.0
1.0
1.0
0.8
0.9
Accuracy
0.8
0.6
0.7
0.8
0.4
0.6
0.2
0.5
0.0
0.4
Normalized Confidence
Normalized Confidence
Normalized Confidence
Figure 6. Average accuracy of the Res-GCN backbone binned by JLDE's (ours) epistemic confidence normalized to [0, 1].
E.5. Varying Degree of Homophily
We also study how the degree of homophily affects JLDE's performance compared to GEBM (Fuchsgruber et al., 2024b), an uncertainty estimator devised for homophilic data. To that end, we create synthetic data similar to Das et al. (2025). In addition to the two classes from the moons dataset, we create an additional anomalous class where node features are sampled independently from 2-dimensional normal at [1, 1]" with an isotropic diagonal variance of 0.1. The connectivity pattern follows the same procedure as Das al. (2025). We do not train the model on nodes from this anomalous class and report the o.o.d. detection AUC-ROC for JLDE and GEBM settings with varying node homophily h that measured the fraction of intra-class edges for each node.
Figure 7 shows that while the state-of-the-ard estimator for homophilic graph GEBM deteriorates under increasing heterophily, JLDE maintains its performance even for highly heterophilic graphs.
E.6. Ablations
We supply the ablation regarding the informativeness of individual latent representations ()) in Section 5.3 on the other backbones (Res-Gie GAs--G.TSep. Res-GATE, GPRGNN) in Figures 8 to 10. Similar to Figure 4, we find that on heterophilic graphs, different latent representations contain different information while on the homophilic CoraML, deeper layers amplify the information of more shallow representations. Consequently, JLDE provides better uncertainty on heterophilic graphs
21

---

Uncertainty Estimation for Heterophilic Graphs Through the Lens of Information Theory
0.8
0.7
AUC-ROC
0.6
0.5
Model
JLDE
GEBM
0.0
0.2
0.4
0.6
0.8
1.0
Homophily
Figure 7. Average o.o.d. detection AUC-ROC of JLDE (ours) and the best-performing uncertainty estimator for homophilic graphs (GEBM) at different degrees of label homophily on synthetic graphs and a lcave-out-classes distribution shift.
Figure O.o.d. detection AUC-ROC (f) under leave-out-claases distribution shift when estimating density from different layers Res-GAT-Sep backbone.
Roman Empire
Amazon Ratings
CoraML
0.80
0.80
AUC-ROC
0.60
0.75
0.70
Density
0.55
Joint
0.70
0.60
Not Joint
0.50
Partial
0.65
0.50
[0]
[1]
[3]
[0. [0.3]
All (Add)
All (Cat)
[1]
[3]
All (Add)
All (Cat)
[0]
[2]
10.
All (Add)
All (Cat)
Layer
Layer
Layer
through jointly considering all ( instead of relying on the final or penultimate representations. This holds over different backbone models, confirming the generality of analysis.
1. DENSITY ESTIMATORS
We also ablate JLDE using different density estimators in Table 17. In addition to KNN, we also ablate two other simple estimators: (i) A mixture of Gaussians (MoG) where the means and diagonal variances correspond to the maximum likelihood estimates for all concatenated node embeddings of each class in the training dataset separately. (ii) A RBF-based kernel density estimator (KDE) that is computed as the average RBF-distance to each concatenated training node embedding. KDE performs similarly to JLDE but MoG falls short some settings because of its limited expressiveness.
22

---

Uncertainty Estimation for Heterophilic Graphs Through the Lens of Information Theory
Figure O.o.d. detection AUC-ROC (1) under saave-out-classee distribution shift when estimating density from different layers
Bes- backbone.
Roman Empire
Amazon Ratings
CoraML
0.65
0.90
AUC-ROC
0.80
0.80
Density
0.60
0.70
Joint
0.70
Not Joint
0.55
0.60
Partial
[0]
111
12]
[3]
[0.3)
All (Add)
(Cal)
[0]
[1]
[2]
[3]
10.
All (Add))
All (Cat)
[0]
12]
[0.3]
All (Add)
(Cat)
11
Layer
Layer
Layer
Figure 10. O.o.d, detection AUC-ROC (f) under a leave-out-olasses distribution shift when estimating the density from different layers of a GPRGNN backbone.
Roman Empire
Amazon Ratings
CoraML
0.56
AUC-ROP CC-O
0.73
0.80
Density
0.54
0.70
Joint
0.68
0.52
0.70
Not Joint
Partial
[0] 0011213141510077811999999
X1I (Add)
All (Cat)
101121311411110711111
All (Add)
All (Cat)
[0]] [01
All XI1 (Add)
10
Layer
Layer
Layer
Table O.o.d. detection AUC for JLDE (ours) using different density estimators and GATE backbone for different distribution shifts (bold numbers indicate best performance and OOM out-of -ft-or-memory.
Density
LoC
Near-Features
Far-Features
Roman
Empire
KNN
81.5+a.9
88.8+a.9
100.0+o.a
MoG
74.620.
87.8 87.821.0
100.01o.0
KDE
81.620.9
89.5
100.04o.0
Amazon Ratings
KNN
62.1
63.512.0
93.910.9
MoG
57. 57.0+1.
58.3+1.4
100.0
KDE
63.5
OOM
OOM
Chame- leon
KNN
62.8
51.3+7.2
99.5+1.2
MoG
67.1 16.2
34.1
100.01o.0
KDE
62. 6za.
51.2=7.6
99.6+1.2
Squirrel
KNN
6
38.4
100.0
MoG
68.7 +a.8
25.3+a.0
100.0
KDE
62.1 12.1
38.41s.
100.0
PubMed CoraML
KNN
83.2
54.0=2.a
9
MoG
83.4
55,412.0
100.04o.0
KDE
83.3+2.0
54.1+2.3
95.7+2.2
KNN
63.3
75.0
99.92o.0
MoG
61 61.3+22
62.0=2.v
100,0+o.0
KDE
62.812.4
73.8
99.94o.0
23

---

Uncertainty Estimation for Heterophilic Graphs Through the Lens of Information Theory
Table 7. O.o.d. detection AUC-ROC using different uncertainty estimators and our method using a Res-GCN backbone.
LoC
Fearures
Model
AUC-ROC
Acc-T
AUC-ROC
Accit
AUC-ROC (Alex. (Ege)
Acc.7
(Alea. Bgg3
(Alcs. / Fpi.
GPN
48.0 28.
59.9 39.9a
38.1
877 Saro
38. 38.0
SOCN
60.0
58.3
55.7-Laf51.
45.5
12.5
30.6-
BOCN
5d. 60.
53.0axv
38.1ava/16.
42.
38.3 773.G.
28.8.r
Romant Empiice
GPRGNN
06.5 1.
78.1
80.5
17.6
61.0-.a
FSGNN
77.
88.6
30.
716
21.9
56.9
FAGCN
72.7
83.6
77.8:Lo/85.Goz.
68.0
20.9:s../11.2-.0
44.3-x
Fas.
76.4gr 277.2
7874
89.22a 1N6.9g
MCD
70.8
472.
FBM
73.3e1 2772.5
74.521 3
83.020
87.6
72.
70.
Safe
73.321 .64.8222
74.62 4/78/44/
83.02 Oax
GEBM
73.321 a/53.6
74.521 426
JLDE
73.321 ./76.9214
74.6s ./3..aa.
83.0a: /100.020
GPN
54.2a1
64.3ai 22224aaa
46.8
62.6. /68.521
SGCN
17.8 T7.8....666.....
53.5.uv
61.D 1.0....
47.2
27.7
33.5
12...x.d49.0-..
51.4-a
.4.2.ta
33.5-11
Amazonn Ratings
GPRGNN
25.5 Lise
57.9
62.1
770.00...
50.6
of.8
31.1
FSGNN
56.8...
45.1 138.1188........
12.7
FAGCN
53.1 453333
18.1
60.8e: //2.9ga>
$1.2
17.9sx
31.7
257.9
60.3er 6p
74.32.
MCD
49.2g v03.521
56.6g> 258.2211
72.9g 433.2g
78.2,s
56.0
48 2
47.3
Safe
48.8
o/48.D249
54.8a: 3g
78/2g 167 2go
140....
64.82:
78.2;=:18...rr
ILDE
48.821
d661.2g1
54.8a
./65.4ga
78/2g- 299.220
GPN
18.Gisa/71.6...
39.6
67.8:r./51......
37.0
58.3:../66.11...
37.0
SGCN
43.3 43
65.6ax./51.99
2..
217
25.2...
BOCN
45.4 43..
40.5
i5.2 9
27.1is/36.00us
26.9
GPRGNN
G1. Sar
36.8...
16.92x./7.88 Bass
30.5
Chumeleon
FSGNN
31..:ca/16...1
13.9
30.9
7.Lis./LLicc
30.5
FAGCN
42.1 2/3,,.5a
43.2
66.9
39.7
13.8:a
30.2-11
Ens.
34.4:a
55..:s
$1.2:a
MCD
35.6g1 1
56.0
EBM
47.8
54.8
40.7
J8.4
40.1
Safe
35.32+ a/36.
54.62ss/56.7g7
78.42
M88.6rr
GEBM
35 32s J66.42
54.62 3ate
78-4 .b5.9er
JLDE
35.32+ 3.51.5
54.6g31/51.127
78.4 29
GPN
51.5 v73.5 se4
41.1
51.7
31.5
51.9
162.0i.a
34.6..
SGUN
40.5zx 287.2224
47.
066.2x 325
28
BGCN
50.41../21.33 2/L.3.a
43.2.a
63.8 lisa
33.9
$2.2 /65.5.v
30.2
GPRGNN
48.3
40.9-1m
(5..
11.7.m./18.44mmm
ESGNN
31.3 31.31.. 852
45.1
56.7 Susa
36.1
8.11s. /6.2
33.9.2
Squirel
FAGCN
30.6:.../44.6.....
47.0
40.5
35.3-2r
Ens.
29.5
53.0i1w50..0w
71.0
02.0gz .37.
52.7at1/51.24
70.1...40.00.
FBM
29.821 22200220..00 3220
20.8.r
49.0
62.6gg 2/52.777
60.9..::62.44
69.924 780.77
40.5
GFBM
29.827 5.60.52s
32.62x
-96.6296 68
JLDE
29.8
22.62../8..11
/100000
GPN
82.81s 6811.888..8 Bass
88 9aso
55. 55.44z.588.81
80 Ma
18.1as./6l /6.s4.
Aus
81.1
SGCN
J87.
89. 1.
63.7
2
16.8.../12.2....
31.1
BOCN
85.31s 1/3.1a7
88. 3aan
80x.777777
8133
28.5ax. A44.3
34.1.29
GPRGNN
85.1:x:/87.Aiax
...2
(85.
$4.1.s
17.5
37.--2
FSGNN
a2.7
87.5.sa
63.5:s./69.813.
71.aa
6.8
40.2-se
FAGCN
95.0 18..616.
88.9
08.7
81.
11.21../1.2aa
10.1
Ens.
$1.3aa 4
52.7e>a/52.8pppa
$4.723-778442
MCD
78.6.../78.1.22
54.6-2:/55. 1es.
38.00.../8L.....
EBM
a/6.0.a
5/3,
88.3
70.6
77.1
Safe
76.9g: 7a0.
62.12>
86.021 w77.000
GEBM
76.9gz 4811.4277
JLDE
76.9g: 8a0.
86.0g. 798.72n
GPN
69.12a .18
84.5
84.5
SGCN
68.7 71s 168 Tazx
94.6
11.88..07..31..
85.7
21.3:. Gan
50.2...
.6. 168.1.8....
94.3-2a
65.6
65.7
22.7....90.0...
63.4-14
GPRGNN
69.91> .70.0
95.2.mm
86.0..
18 61. J8.5axa
51.5.a0
FSGNN
.6......66..0. .63.9
95.4
/8..3.2
82.
PulsMed
FAGCN
68.5 2/88. 4.a.
94.7
85.8
54.2
50.5 659.66 J59.
v81.
MCD)
56.32> #/56 9asa
63.3g .63.4ga
#/4.9g 85.32
61.9sa
a/8.5.
94.9asa
83.9
82.9
Safe
57.5g> 81008
61.9g o/44..0
81.0g> W66.as
GEBM
57.5as a/5 Daxe
61.9 lasa
ILDE
57.5g> w5004g
61 <644.3x
81.0g) 19944g01
24

---

Uncertainty Estimation for Heterophilic Graphs Through the Lens of Information Theory
Table 8. O.o.d, detection AUC-PR using different uncertainty estimators and our methad using a Res-GCN hackhone.
LoC
Seaturenature
Far- Far-ueatures
Model
AUC-PR
Ace.t
AUC-PR
Acc.t
AUC-PR
Acc.7
(Alea. (pp.
(Alea. Hlpl.
(Ales. (Epl.
GPN
26.4g> 5300
48.0
13.1
38.1
11 41. 4/0.0000000p.
38.0p1
SGCN
26.1 4mm
68.3
40.5a
6.62
30 30.621
BOCN
23.3 Saze
63.0....
14.3.
42.
7.6.u /29.4
28. 8..0
Roman Empire
GPRGNN
30.6...224.9
78.1
61.0..e
FSONN
35.21..
1.7.5....
86.6....
17.91 (1../22.....
7isa
71.6
6.8 6,81o//5,21aa
56 9..
FAGCN
35.6:..994.7..1
63.6
68.0
6.8
44.3-2x
Fins.
41.4g: 240.1:2 1/40.121
27.62)
62.6g: </36.7a**
MCD
40.4... Saro
23.2aL
33.d222/15.60
FRM
36.92 2/40
87.6
21.82: /305.
72.3
34.6g> 329
70.62.
Safe
36.. 2:1.
21.8 Gass
GEBM
30.9
21.8:ca/17.11
31.6/2a/77.1
ILDE
3/.9es./42...saa
21.8 a/63.9.
34.6sa 1/100.0...
GPN
12.9
S4.2
3:0
46.5
of.T.oo/12.77 1/1.7
47.0.01
SGCN
12.9gt a/12.
55.5
411.
7.3 1..30/8.. 28.8 Sata
33.5
BGON
61.4
11,22
44.22:
8.8
422
38.521
GPRGNN
14.2:a./141...om
67.9
12.72.2168..
50.6
9.3 lime
31.122
FSGNN
8.7
8.8..a
36.
FAGCN
of1.77
58.
51.2
7.9 4/7.4
31.7
Amazonn
12.3esa/15.770
26.3 a99
MCD
12..2)
25.4ga a/7.
EBM
13..2../13.2... 2
56.0....
11.3so/12.0aaa
48.2
30.81xo/71.1a.
47.3
Safe
13.0ss./13.1-11
30.8.au/16.91
GEBM
13.0s...13.....
11.3:r./:11....
30.8t..//4..a..
JLDE
13.0:c//17.2in
30.8.
GPN
41.5zz N44.449
39.6
14.8
37.0a1
37 07.0
SGON
43.3
14.2
38 2..
6.821 28.22..
26
BGCN
39.9g
40.5
38.321a
7.7
a/14.02e
26 92
GPRGNN
/41.8 36.8
166
37.1
6.32
30.5
Chamelon
FSONN
31.9
13.9
16.6::a/16.2...
36.9
5.9 1iz.
30 30.55...
FAGCN
38.8:s./99.7...
43.2
23.1.r./5..0vvs
30.2
Ens.
35.6.1./43.8....
13.8 1izs
46.2
2..2..a000000 /10.00-4
MCD
35.8
13.7
47.6 48842
ERM
47.8
13.62
40.7
39.821 1/7.33g
40.1
Safe
35.8
13.6st:/14..s...
39.8 /23.1
GEBM
15,8-
13.6-1./8.7i4a
39.8. 155.000
ILDE
35.8
13.6 4iws
39.8 M9.9..
GPN
50.8.. 87..../799..sa
41.1aaa
12.
34.5
34.621
SGCN
51.32>
/72.7g5
27
12.0g </16,725>
37.7
7.1 .8.92
28 2g5
BGON
38.33s
610
7.3 225.7am
30 30.2
GPRGNN
50.1g
/50 /50.9gm
4
35.4
6.3g 1.1.8.8
34.4g1
FSGNN
46.521
45.1asa
15.1ax//1:2ann
36.
33
Squiree
FAGCN
62.6::a/66.01
47.0
12.9:2o/11.66
10.5
5.8
35.3
456.3
110.::
o/18.228
MCD
48.2
11.5:a/10.799a
23.9-x.8.00pp
EBM
446.0.466.0a
49.0
A11
41.8
28.5. #64.0
40.5
Safe
403.777
11.62:/1144211
26.52a 3/1.3320
GEBM
46.4...669 2
16.
a/79.v.
JLDE
26.5-.
GPN
75.5
88.9
11.
80.9
10.3
81.1.1
SGCN
89.4..
363
82.0aa
7.0em
34.4.at
BGCN
80.4g 765.777
88.3.
14.2g: 2/1
81.3a
7-7g0 7142224
34.1
GPRGNN
.0.2...
3.
37 3:.
CoraML
FSONN
75.2
67.5
13.0
717
8.1
10.2
FAGON
79.91s
19.2as224.22aa
40
Ens.
74.8::./66.112
11.3 7
42
MCD
12.0g: /12
EBM
470.52
88.3
10.92
79.6
42.4 1/762r
77.1
476.9e
10.9g
GEBM
4764:)
10.9:
42 333.
JLDE
69.12..72.66
10.9 lius
12. o
GPN
55.7=:
91.2..:
13:3as//13772ss
84.5asa
11.0zna/22.
84.5
SGCN
35.1.2./54.44221
94.6...
16.1.a./16.9....
85.7
8.01max7..21aa
50.2-1e
BGCN
W4.3
94.3.a
/13
85.7
217.,
53.4
GPRGINN
57.2g> /57_3ga
95.2..
860
8-40 1214
51 b2
FSGNN
95.4..
37.22sa/82.1..
7.6
69
PulMeed
FAGCN
55.5 auy
91.7 in.
18.5 1isa
85.8
8.01
54.2
48.2
13.5
29.6 29.6i.../26.44
MCD
46.4
EBM
14.1 A.pa
28.2a: 261.1ar7
Safe
44.721
94.92
14.1a /110
83.
28 26.22: //17.0gaa
82 9gn
GEBM
16.2
14.1 at/l1./13...s
28.2.../30.44 ..30.41..
ILDE
44774444744000
14.1 a/13.55
28.221 /900.2
25

---

Uncertainty Estimation for Heterophilic Graphs Through the Lens of Information Theory
Acc.f
94.92m
05. lana
95.2gna
05.2
PubMed
59.5 1.050 .....
56.3 36.3= of..s pan
57.5 w5 Oan.
57.55n 260.8 8.
57.52n w/ w/6.0 1.5.0gn gnna
57.5 #50 4amo
64.4 a4.4 .63, 03.99... 9
62.3. s../22.2 2 usa
617 617-...00 7.-...11.77... 7
6177 363.3.333..
61. 7..7.//6..55 5
59.6. a..09999.. 1ea.
57.5. (. 1.
57.8. 2.n.66477 ana
57.8. a............ ...
71.5 a..772.0 ma.
08.5 2.007.3 a.a a.
09.9 09.9 2.700.0..
69 9ww. 1
69 wtw.:/22.55.. ss.
69.9 a.a666.8 ca.
Table O.o.d. detection AUC- AUC-ROK ROC using different uncertainty estimators for different GNN backbones for a leave-ouee out- classes distribution shift.
AUC-ROC
(Alea. /Egi.))
61.7 w...6.....
56. L..550000
57.8. 2...88885
Acc.f
88. 85.32
87 57.6.s.
88 a8.9
M..
CoraML
AUC-RO R-C
(Alea. /Fpi.)
31.33t../81.4 1/.1.41..
79.6 09. w/8...//8..... 178.1112 1a20
76.9 16.9ax./766. /77 10.0
76.9.a.//80 9..0/80.77 1..8/00. 2../80.75.. 7ana
76.9ga a/8 81.4gx
76.9 (0..0.08888..... 8ar.
81.4. 11.4.1../114. 4/814.1.
79.7. 19.721.// 1.t..9999.9..
75.9 2./4.//......
75.9 480.5..s
75.9 719 99.99....
75.9 w.tps///7...00.. /../77.0..0. .0.0
82.3 w/2.7
80.7 ./....3....
77.9 u..9.a. ./6.33
77.9 1/80.....
77.9 77.9. 1.8..118
77.9 77.9... ./33.2...
86.5. .. J71.9
85.2 a../T..2 (77.2
85.1 2.... v4a
85.1 85. 12 189,7
85. 1o w/8.
85.1 s.. 9.
Acc.
20.3
10.9.s
40 2.
49.
Squirel
AUC-ROC ROC
(Alea. Epp.))
29 S...ee.dl /44.9/99.......
32 De a .87.22na 2an.
29 8ey /29.2293 3
29 RaY 188.99
20 10..8ar//611 /61.55
20 8...:/55.77...
41.4s ./4..5
45.0 1/n.9 1..9... saa
44.4 44.40oaf4h 445. 7
44.4a0 445.44555 4asa
44.4 44.42..//7.44 17.4g.
44.4 466.//66....
6
43 1eo /49. 7...
41 1/7.2
41 11.5 /59,859..... 8
/62.5...
14. .81.7.1. 7.22a
0. us 555.8 saa
48.3 a.. //8. 1.440
48 3 24.2 se J62.0.s.
40.5 1..G.a 1/../8..
41 w/3.
656,
41.5.n.ff
48, 3 Le
Acc.f
47.8
37.5as
1/7.-11 39.9
36.8
Chamelcon
34.4 149.9999
35.3 -835777
35.3 1/36.664
35.3 2- =/666.4..
35.3 35.3 af6 1.1.5a
37.4 77.4 422.4as Aas
42.5 1... 16..9
41.7 o..55 a
o1.75x-/45.. 2
41.7 41.7ax.. 15..888111 158.188..... aan
40.9 A.8...5..
41.0. .49.111 Les
A/2.7
40.3 //9.9 aoo
40.3 ./62.8...
51.2 12..../M 716.7
53.3 7. /53.9
51.0 1...../AAA w.8. 8
1L..Gr.. .03 ..3.333..200 2
51.6g7 -.4.0 6.
AUC-ROC
(Alea. (Epi.)
51.6, 7 u/5..
35.0s 35..s--/40.0.
41.7 4
40.3
10.3
Acc.7
56.0 66.0go.
58.0 a2..
57.4
52.5 2.. a/52. 4 07.9
Amazon Ratings
AUC-RO ROC
(Alea. Fip..)
49.2 2o .5335
48.8 8a. a/48.9xxa
a a/18.0212
2. a/49.9
48. a. J/6 1.2a0
60.4 ao a/00 4.0.
57.2 a/57.77...
56. us 35.....0
56.1 as a553.444
des
56. as /50. 150.1...
1
56. aa J61 g.
61.8 w61 8
.5...5..
.50.33.
57.0 /57.88aa
57.0 .50..22.
57.0 17.0 .62
$2.9. a.9..aabi0 1/3.9...
52. 1s a/5.33
2.. a/51.
w/4..3
52.5 2/4.44..
57.5
57.0
f2.5...
Acc.f
87 G
91 4
78. 4
Roman Empire
76.4 206.76.22mm
16.3.../75.99. 9
13.3.1.//4.. 8/4.8
73.3 J7
Jans 75.5 722.0./
77.4 77.4 /77.0/77..000
75.5 4et4
75.5a w865 .
75.5 o/6 766, 9...
78,0 778.7
77.8. 8. 77.8..../77. //7.11.
733.7a20
1.2/71.114
M.../RR. 240
J88 1.5
1w.//09 2
m.a/57 m..557.2.... 1a.
06.5. www..33............ 4... a
06.3 3
06.3..../35 Aasa
06.3 w L.a
AUC- AUC-ROC ROC
(Alea. Fig..)
79.2.n.
75.8
75.8
75.8
75.8
06.8.
68.2
GEBM
GEBM
GEBM
GEBM
Model
Ebss
MCD
EBM
Safe
JLDE
Eins.
MCD
EBM
Safe
JLDE
MCD
EBM
Safe
JLDE
Ens.
MCD
EBM
Safe
ILDE
SPPRGNN N
26

---

Uncertainty Estimation for Heterophilic Graphs Through the Lens of Information Theory
Aoc.f
83.9
83.2gn
8133.3
86.0gn
PubMed
AUC-ROC
(Alca. EEpl
64 1/64.7 22.0
63 63.3a. 4/63, 4/63.4 Asaa
61 11.9 a/61.0ss-
61 11.9e a/54.0s>
s/62. 1an
a/64.33mm
w665.5asa
w/33 4aaa
65,0 164.2.ma
955.4a2.
65.0s 366688go
65.0ss o/76.1 776.1asa
66,5 sa..saal633... 2..
65 15.2 o655.8... 12.
61.6 u/63.9
64.6 64.6 u/51. 120
u/3.2.44
6 61.6aa d/5..0.4
1/6 10..0
147.8aa3
66.5 a/72.921.
66.5 af0. 22.-22...
66.5
61 11.9
61 11.9aa
06 00.6an
13 33,2pz
65 15.0
64 64.6
61 8..
66.5
Table 10. O.o.d. detection AUC- AUC-ROC ROC using different uncertainty estimators for different GNN backbones for a near features shift.
79. 19.6
78.1 1114
80.6 1.5
84.211
Acc.
CorMML
AUC-ROC (Alea. Epl.
52.7 22.7=2./000 sae.//22..8 8...
52.1 52.1 =2.//333/3333 3.2.
52.1 52.1 e/ 0e1.
52. an o/53
52. e54.9
53.6 453 4.
sa 455.55.....
53.3 35. 1.7
53. 75.. 7a.
53. 7 (00.9 gai
51.1 2..61.1s
52.7 1/53.l.s
a./52.0.s. e..
50.0 2./50.7 r2
30.9 10..0aa//2..cm 8
50.5 10.9 x//4..0a.
59.3 59.7 .45 445-3e4
61.02z a/65.9
11.02t.654.91 9.1
11.02t./76.222
61.0g1 663-337
53.3 23.7
56.8 ga
50.9 00.9.
41.8
34.8
31.a...
35, 45.4
Acc.
Squirel
AUC-ROC
(Alca. (Ep.))
w3.0zx.500.... 62n4
a5 25.5.1..2.. 2.44
52.6 (52..
52.6 a51 (51.66 6.
52.62s w/28 428.62n 6an
52.6 o/33 1eae
72.8 m. of Sar.
39.3 /52.5
65. 9 sa.. 270,,2
2
65 Se. .56.660.. 200.6ara
05. 9 9... 445, 45.42
65. 9 /40.7
53.5 53.5... a..55.60......
53.8 8.88. a../4.2....
53.5 8. 4..52.11. lss
53. 8...... J31.6.114
53.5 S u.. .88 4.0s
54.3 Gazo
53 Sea 1800 Agr
53.1 33.1s.n/7700.. 250
50. 53.1.46511 4gn4
53. 1..1144433..4 42m1
53.1 821
22.7
56.5 mf
Acc,1
40.7a39
34.
37.3.a.
37.1ase
Chameleon
65.2 153.88s
26.0 o/55
54.62n./5550 3/5.99ss
54.6 3/56.7e7
54.6 #87 da14
54.6 1.1.
18.0 1a
58.6g af3..3
58.7 1...8811.0 Lane
58.7 58.7= ww..55500000. 05.05 O.n.
58.7 af daveo
af33.22 2aiax
55.5 05.8 161.6
56.2. 16.
55.2 /.//6..3.s
55.2 =6/66.6....
65.2 a..6 0012
55.2 a/5 1..3
63.4 1..4-//83.00 5ex
Se :277-220
62.9g- 8/50.8
62.9g- -50. Gas
62.9g =/41 Aes
62.9g a/55. 200
AUC-ROC
(Alca. /Epi))
58.7 7 af33
Acc.
48 28.
50. 20
49.5.mo.
50.6
Amazun Ratings
60.3 30 3/63.662
56 66.6 6as 3/68.2.1
54.8 81.8en a/56. 3
54.8e: 3/65.3e24
54.8 .4771a11
54.8 3665,4g
163.0g
87.8 1
56.3 150.....
56.3 w58.221.
56.3 ./8.62..
56.33 1/79.1
61.7 1..7../66 1/63.0...
57.2 /51.
51.5 151.3.
51.5 2/6..4
54.5 3/4.22.1
a4.5 s/63.5
08.33 28..3../77 1/7.42m
62.32. J66.8827
an a/70.0g a
an 156.02a1
an J/9.77a1
en J47.8
AUC-ROC
(Alca. Epi.)
62.0 20.0 12..0o../3.00
74 w.3.5.7773.... T2.3en.
78.02na
77.5 aas
64...se
Acc.1
Rommn Empire
AUC-ROC (Alen. (Ep.))
78 477. T
75.8 San o72.521.
74.521 14.5:.666644 /66 w66-422 o
.81.8155. 5ama
81 1...1111111m anns ann
77.7.../77.8.. 77.7 Sa..
77.7 21.2777 am
2811.2000
779.7...
77.5 S. 11..8855.... 1.a
77.5 S. 178.78855... na
#04.222.. 22.
77.8 S.S... 888.8
87 /.2.//4222111
39.320 158.558.... 4
86 5.w 12
86.5 5.../43.66.4
w85.
62
81 81.62m 1....1881555
84
86 5.m
80.7 80.7...
77.5
Model
Eins.
MCD
EBM
Safe
GHBM
JLDE
Eiss.
MCD
EBM
Safe
GEBM
JLDE
MCD
EBM
Safe
GEBM
ILDE
MCD
EBM
Safe
GEBM
DE
GPRGNN
27

---

Uncertainty Estimation for Heterophilic Graphs Through the Lens of Information Theory
Acc.7
62.0
81.4 $1.4
83.6
51.5.x
PubMed
AUC-ROC
(Alia. Epi.)
$2.0 w81 4eos
85.3a: w/74 1.1.
81 31.0s. a888.
$1.0a: w/06 w/06.3
81 $1.0g: ./7.22an
81.0 .9999999 10.4....
S 31.6a0 a/S .loss
84.3 177./78.800 Ozns
7/84.3 Jans
79.4 1/64 x/64.77a 7
79.4 o/ 19.5
(999,88 o.
80.6aa o/79 4.n
84.0as a/75 a/75.7 7
70.5 w886, 3exe
79.5a. w164 w664.44.5
79.5 of a775.0 00..
79. 19...... 1999 9 ao.
70.7 of82. Gane
18.6 A.G o88 58.
18.6 J24.0213
18.617. 292.0 1..
18.6 18.6 .0.5
33 San of
71. An
79.
Table 11. O.o.d. detection AUC-RE ROC using different uncertainty estimators for different GNN backbones for far features shift.
Acc.1
77.1a18
75.0g
78.221
37.3aca
CoraML
84. J78 Sdd
888 D. a/64.02a
85, Ous a/9 393.
a/72.0z2
885. Das a880.5a
86. D.. Di J95.7
83. 7/6.77ax
87. 2ea 2/66.754
88. 35.M... ./22.221
83. 0. w/70.9
83 0v. J85.3
83. . J96.8
84. 7/78.7a1
//00.5e7 5ar
85 22 v/44.2am1
85. 22. d/f1.8
85. 2 JS0.5
85. 2. a J95.1
32 a/43.6623 143.6an
75. Bax J90-3an
17.5 8.0s
17.5as J18.7a:
17.5. J97.3
17.5 a 398.3
AUC ROC
(Alca. EEp.))
85. Das
80 Sas
Acc:f
40 Sa.
34.523
33.7 33.7a
34.4
Squirel
71 =00 lasse
70.1 70.1 = of Oue
69.00 09.0=. x186. 7
69.0- =/02 42
189 9t. 1
26.4 of 3ame
26 6..6 a 221 1..tam
26. 6.w. wf a2.. 5.s9
20.6a..... .95. 8an
60 a55 ....... 65. 65.0 w5 o666-44mmm
4aw
65.0 05.0g.m m...588....556 gmm
499 3
65 5. und 1000/0000.0000 100000000 On..
8.5 a.000a000.0 a/00 62
10.5 .999 8ans
14.7 a8 8 11.7...889.8 6.0.6.cc
14.7 16.767.9966.7... 12.
AUC-ROC
(Alea. Epp.)
69.9 0. 11000000000000000000000000000..0 .
14.6 0..4./51.. L.
21.6 2/9999999 9
82.4 2.. ./86.
05, Dass..
14.7
Acc.ft
40 40.lax
33 23.
36 m
30 10.5
Chameleon
$1 so w5 1000
$2.2aa s/11.1. 12m
78.4 78 a
78 4.x /68 Gate
78. 4.. 4885.9995 9
78. A.d..... 19999999 co
64.7 4.77. a0s8 Tees
60.0ats 8
64. 1...aw /78. 178.1 2mn
64. 1..Sammlil /66. 166. 1ana
64 S. mm 3/3,999......
71 1..3 9407
s/44.4ar
67. 77-7am /83.7amm
67.7an 466.9.m.
67.7 3/88,3...
67.7 .99..5
24. 2.12 ./5 Oenco
56.02t 403.1 183.1s4 1as4
15.9 15.9era/7.aar. w/7.0ara
15.9gv /26 S
15.0 15.9 .9..
AUC ALC-ROC
(Alca. Epp.)
61.8 in d98.2
15.9 1..9.v..944....
70.8
Accif
47.3
50.8 a
49 x
34.1227
Amazon Ratings
74.3 m50.554.... 4a..1
w/33..2... 2010
78.2 25. 494,4.1
78.2s .67.2a.a
78,2 2 199. mn
62.9 =62..5.. 2..
65. 05 o.4.33a
70.1 10 -80 2n
70. cs 666. 250r
w63..64.. 4
70. ./8.5 in.
63. den a54.555... o
68, cs a09 a099.3... Jaso
69.5 Sen 28007
69. S 1..7.44. 4
69.8 8 1.656.00... 2
69.8 S ./93999... 10.
60.7 7 7/78.99 Sano
10,9 of 6ama
10.9 /50.9saa a0
10.9 s.. 199.4.m
AUC-ROC (Alca. Epp.))
28. 158.9
10.9 109.a./100.00..
70. as w63
51.5 M08.
72.9
Acc.f
70.620.
79.3
76.4gm
61.0go
Roman Empire
AUC AUC-ROC ROC
(Alca. Epp.))
50.2 10.2xxm no e/50 500.7
82.7 22.7.0.0 w/72.0s1 a
83. D2.0 2.10
83.0 wf8 a
83.0a o80 Aana
83.0 of.0 of00 00000am Ohnn
e1.1 of 3.0
85.0 35.0aa =/70 4aia
82. D2 w888.8 S
82.0ss o81 O
82.0s. w//66/6655. Sa
82.0 D1. 99688
96. aa wis 3an
93.0 03 w/73 773.5a1 Sano
94. Da 799.7 200
94.9 (m0 J/0 390.
7an
94.9 94.9....500 <80 3.44
91.9 100.0
41.4a: w/S8 6an
87. 7a w999.3.m 2
17.0 2/7..11111... laoe
17.0a. 480.440 4an
17.6. 1888 1988.... in.s
17.6 17.6. 100.000
MCD
LBB
GEBM
JLDE
MCD
Н
GEBM
JLDE
MCD
EBM
GEBM
JLDE
MCD
EBM
GEBM
JLDE
Model
Safe
Safe
Safe
Safe
GPEGNN
28

---

Uncertainty Estimation for Heterophilic Graphs Through the Lens of Information Theory
Table 12. O.o.d. detection AUC-ROC rank of agnessag epistemic and aleatoric estimators averaged over all distribution shifts (best runner-up).
Roman Empire
Amazon Ratings
Model
Chameleon
Squirrel
CoraML
PubMed
Ens.
2.5 / 4.0
2.8 / 4.2
3.8/ 6.8
3.2/5.2
2.8/4.5
2.5 /.0
Res-GCN
MCD
4.2 4.2
3.8
4.2
4.8/7.8
4.2/6.8
4.8/9.0 /9.0
EBM
3.0/6.0
5.0
3.8/4.0
4.0/7.2
4.2
4.2 4.2
Safe
4.5/ 10.5
1.00
4.0/5.8
3.8/ 6.8
4.8/8.2
4.0/7.0
GEBM
5.8/113 11.8
4.0
2.8 4.2
2.5/4.0
2.8/4.5
2.8/4.8
JLDE
1.0 1.0
1.011.
2.5
2.5/4.0
2.2/288
2.8/3.2
Ens.
1.8/3.0
2.8
5.5/
2.0
2.8
2.5/38 /3.8
MCD
3.2/
3.8/ 6.0
4.0/7.0
4.0/5.5
4.0/6.2
/.5
Res-GAT-See
EBM
3.2/6.5
3.8/
3.5/4.8
4.2/5.8
4.2/7.5
4.0/6.2
Safe
4.8/9.8
4.2 8.5
3.5/5.0
5.0/
3.8/7.2
8.5
GEBM
6.0/ 12.0
5.5 11.2
1
2.8/
3.2/4.
2.5
JLDE
2.0/3.0
1.0/
2.8/4.2
2.273.8
3.0/
6.5
Ens.
2.8
2.8
4.5
3.8/5.2
3.2/5.0
3.2/5.5
Res-GATE
MCD
4.0/7.0
4.2
4.0/7.0
3.8/6.8
4.5/7.0
4.8 /9.0
EBM
3.2/6.5
4.2/8.8
4.0/4.0
4.2/6.0
4.5/7.8
4.0/6.0
Safe
4.5
3.2
4.2/7.2
4.2/7.2
4.8/8.8
4.5
GEBM
5.5/
5../
2.0/2.2
3.0
3.0/5.0
/.0
JLDE
1.0/ 1.0
1.0/
2.273.8
2.0/
1.0/
1.5
Ens.
3.2/4.8
2.8
5.2/10.0
3.0
5.2/10.0
3,5 /5,
GPRGNN
MCD
4.2/8.8
3.5/6.2
3,8/5.2
2.8
4.8/
4.8 /9.2
EBM
3.8/7.2
4.5/8.0
4.2/
4.2/6.8
3.5/5.0
3.8/5.8
Safe
3.2/5.0
1.2/
4.0
4.8/9.2
2.8/4.8
3.5 /.5
GEBM
5.2/9.8
2.8/
2.0
2.5
1.8/88
1.8 /30
JLDE
1.2/
2.273.8
1.8
3.2/4.8
3.0
3.8/8.0
29

---

Uncertainty Estimation for Heterophilic Graphs Through the Lens of Information Theory
Table 13. Misclassification detection AUC-ROC using different uncertainty estimators and our method using Res-GCN backhone.
LoC
Features
Fearures
Model
AUC-ROC (Alco. Rgk)
Acc.t
AUC-ROC
Accit
AUC-ROC
Acc.7
(Aloa. (8pl)
(Alox/ /Eje)
GPN
72.4
48.6
T1. a5.1
38. 3a.
70.4ss 7887
38. 0..
SOCN
156.3...558.8... a
38.3
45.5-L.
632.777
30.6-
BOCN
65.6.../61.1aa
53.0
66 /6.02vo/99.1..
42.
50.6as 467 Guse
28.8.r
Roman Empiire
GPRGNN
85.0
78.1
84.8 47.8. vea
64.
18.47
61.0-.a
FSGNN
86.6
63.02v
71.6ss
35.8.2
56.9
FAGCN
80.8-1./77.00 //7./..
83.6
81.2:oa78..0
68.0
48.0
44.3-x
Fas.
88.8g1 J88.32r
88.1 127
MCD
89.0 3/8.
$6.4:e..683.5.mn
FBM
87.0ga
83.2so 2.0.77
85.32a v83.7221
Safe
37.0.s./71...21
87.6
83.2 220 o/
72.3
86.31 075..60
70.6
GEBM
83 2.0 #500.
85.32+ v56.9gaa
JLDE
83 220 o83.66a2
86.31 .56.120
GPN
60.7a>.667
54.221
60.7 w56..6666..
86.8
60.7..
166.021
47 1
SGCN
60.7 60.7....59.77 k..
55.5
60.61.. 5
47.2
11.7...//77....
33.5
51.4
61.00...53.0.a
.4.2.ta
33.5-1a
Amazon Ratings
GPRGNN
63.5
16..5....61....
57.9
61.
50.6
18.7
15.7....611....
31.1
FSGNN
63.2
56.8
49.1
1/16...
38.0..x
FAGCN
24.2ga
18
64.6 161.
$1.2
47.9g>
244..iga
31.7
A33.9
68.621 463.9207
MCD
63.9ga W88 G2
64.1 #62.3a
64.5 4g1
63.8 2/8..//68..000 6
63.9g0 86
64.0.. 464.420
56.0as
48 2
47.
Safe
63.8g> >/00.72>>
63 920 022.022
64.02+ 262.6.0
63.8.>>440.7
63.9.. 152.
64.02. 251.
ILDE
63.8g> 228
63.920 761.7
64.02e w61 W61.5
GPN
39.6
66.7.s./12.33...
37.0
67.1../12.5....
37.0
SGCN
53.5.x./56.0a>
43.
64.6 Sass
38 2..
22. 25.2...
BOCN
s1.5 9
40.5
02.9
15.7
26.9
GPRGNN
52.4.x
86.8
02 32.66.../66..8
37.
/50.
30.5
Chumeleon
FSGNN
55.3 1.858.99... i
43.9
-x 68.41..55..1
30.9
30.5
FAGCN
57.9
43.2
66.3:
39.7
55.6 JS2.3..
30.2-11
Ens.
59.2.:
64100.../4.11m
02.4es.
MCD
58.42x 25
64.624 502.55211
6/2.888
EBM
56.9:s
47.8
(2.8s...64..4..
40.7
V63.8..
40.1
Safe
56.923 22...6...
62.8ar A00)
v/0...
GEBM
56.92s 4/99 3ar.
62 82r. //8 8ar
62.324 v61 Mas
JLDE
56.9g1 94
62.8az v88..as
62.3e+ 220
GPN
/3.2.s./39.00 9
41.1
17. 1i.1 61s.
31.5
47.6.../28.7 1/8.7/28..uu 7...
34.6..
SGUN
349
47.1
42.
d/22.asa
288
BGCN
43.2
.65.2 58.7 188.7....65.22
33.9
18.8
30.2
GPRGNN
50.3
1/9.777-
43.4
35.4..4
m2......
34.4-19
FSGNN
59.5
/59.3ix.
45.1
71.31.. .72.442
36.1
33.9.2
Squirel
FAGCN
58.9.r./57.55vv
47.0
07.9...
40.5
/5..0..
35.3-ar
Ens.
1/58.7
69.6
09.6:2..61..--aa
67.442../2.4..
4/2x
MCD
60.6.z 2/7.3324r
8::
66.8.a
FBM
58.923 4g0.
68.4g- J68.9226
25...s.55..4..
49.0
68.4.: 064.0aam
41.8
86.62a
40.5
GFBM
58.921 443.4ga
68-4g 2/1.1111
JLDE
58.92v 8
68 4.s 3a04
06.61s.//2...
GPN
87.3
88 Max
82.81. Bass
80 80.0
82.72 3as
81.1
SGCN
83.2:2../8.4.is.
89, 89.1
79.2 BaL.
62.0
15.8
31.4
BGCN
84.7 9/7
88.3
81.221
81.3
45.8
34.1.29
GPRGNN
85.2 Siss
.0.2
82.41../76.8.
$4.1.
/9.6:s.//7.6..a
373--x
FSGNN
81.6:2./78.1es
87.5
79.3
71.7aa
40.2-ae
CoraML
FAGCN
82.9 92.9:2./79.777
88.9
81.1i, iu
81.
15.3
10.1
Ens.
85.5g1 183
40.3 w/70.6
w/9.55
MCD
83.4-2./00.3-44
6/7.7777
78.9.s..78.4422
EBM
78.8
Safe
82.8gs 1/7
88.3g
78 88.829 2/78.220
70.62:
17.22:./88.3 3/88
77.1
GEBM
/81.71
79.2
JLDE
82.8 J82 Man
78.82s 779.77
79:2a) 7/8.5:
GPN
90.22a x/10-4g-
91. 2
80.1 M66.111
84.5
80.3as
24.5
SGCN
90.8... /90.6...
91.6
20.2
85.7
66.....
50.2...
91.7 ./9..8...
91.3
a0.5
65.7
15.6.../51.6.1
63.4-.
GPRGNN
90.2
.9..2...990.2...
95.2..m
30.3...77..7 Taa.
86.0...
65.6...
51.5.a0
FSGNN
92.33...
95.4
80.2
82.
19.5...//1.....
69.9-17
PulsMed
FAGCN
11. 19
94.7axa
w/3.
85.8
47.1s:::44.8..11
54.2.1
78.1s
79.3es./79.5.0m
MCDD
87.7 287.2gx
79.1 o78.7777
79.9gt 478 999e
78.0us 273.22ar
94.9asa
83.9
82.9
Safe
86.4g4 1/22.1e.
76.021 400.1gs
77.621 .70.3ax
GEBM
76.02) 470.444.
77..21
ILDE
88.4gx 2/44.2
76.0g1 208.223
77.6g) v7000zo
30

---

Uncertainty Estimation for Heterophilic Graphs Through the Lens of Information Theory
Table 14, Misclassification detection AUC-PR using different uncertainty estimators and our method using a Res-GCN backbone.
LoC
Near-
Far-Tretuurs
Model
ADC-PR
Acc-t
AUC-PR
Acc-T
AUC-PR
Acc.7
(Alea. / Eigi)
(Alca. /Eje)
(Ales. FFp)
GPN
451,7777
48.6
56.42c./11.1am
38.1
55.5 A221aaa
38. 38.0
SOCN
58.3
60.9....63....1
45.5-
2/.2.ua/22.2.1
30.6-
BOCN
06.7
53.0axv
56.9t..65244us
12.4
27 27.
/38.5asa
28.8.r
Roman Empiire
GPRGNN
95. 293.77
78.1
61.8-aa
69.8
61.0-.a
FSGNN
98.0gr 495.9
88.6
92.8sx
489,4.4
71.6
56.0ss 9444
56.9
FAGCN
97.1.c.2/9.....
83.6
92:41..//8.4400
68.0
39.8.
14.3-2x
Fas.
98.4gr 498,
94.7ax v994,4gn
95.3gn -95,0ga
MCD
28......
93.8:e..63....m.
24..
FBM
97.7ar 9a
90.0gx J51.33
83.52 1
Safe
97 7... 2a1e
87.6
93.0s. Jb7 Sa
22.3
93.02a 2/88 1
70.6
GEBM
77 aat
93.0gx 4
83.52 3/75.33'-
JLDE
97 72 J/97 Bana
98.0s. .03.0l20
83.0ga A/3..
GPN
54.2a1
56.2a> /51.7a1
46.8
06.421
47
SGCN
61.1 61.11./663.1 La
55.5.uv
56.
J5..77.
.
17.2.
32 32.6.u.s/1......
33.5
60.7 40.7 B.sa
51.4-a
/18.7.
44.2-1a
35.4-a
33.5-1
Amazon Ratings
GPRGNN
69.0 .6.00...67..8 Bais
57.9
68.61
50.6..v
33 33.0.u ./55.91x
31.1
FSGNN
66.7 J66.4
56.8...
60.8:../88.1...
19.1-aa
36 w/3.99.c
38.0
FAGCN
60.3 2218
18.1
63.62 vt0.92
51.2
30.0ga a/28/222
31.7
72.5.z
66.8..
66.02z -66.0
MCD
69. w/99 3a
63.0ge
.61.62
62. D2z 490.32
60.5 368.3
63.0ga -64.0
62.3 1
56.0
48.2
47.
Safe
69.52r
s/54-921
63.1gg v69.821
60.5 656.8
15..2./50..211
949..9
ILDE
69.52r e/63.121
v00.02ge 63.02
GPN
63.6.v.
39.6
52.3:...83.1..3
37.0
63.0
37.0
SGCN
18.02x
43.3 43
/2.12x./46.511
38 28.2
26, 4/26.
125 =
BOCN
45. /l..
10.5.
18.712./51.4isv
38.3
27.8:../28.5.vu
26.9
GPRGNN
6/1.777
36.8 36.8..
46.02..87.22 225
37.
33.0 J81.8818
30.5
Chumeleon
FSGNN
50.9 10.9...5501.....
13.9
60.3...//16.2...
36.9
33...
30.5
FAGCN
53.9 254,,2.
43.2
57.8:s
39.7-xm
33.7 /32.3aaa
30.2-11
Ens.
555.
62.6:../62.....
663.
MCD
55.8 225e
/59.6..
EBM
55.5 Busa
47.8
57.9:...80.443.
40.7 20.7
56.8 1/3.//.......
40.1
Safe
55.52x a
57.9gx 652.527
56.62s 2/11.ara
GEBM
56.52r J52 Dari
56.62z 2/64,7a7
JLDE
55.5ex 4
57.9gx
v50.77.
56.8gs 3/518
GPN
18..1..
41.1
87.8 87.8
J21..1..a
34.5
38.
1..1...11.......
34.6..
SGUN
J/8
47.
37.
25.7
128
BGCN
91. /52.77
43.2.a
12.8
33.9
30.1
//9.55...
30.2
GPRGNN
40.9-1m
/5.1
35.4-14
38.2 38.2-- J36.7
34.4-19
FSGNN
56.
J55.88885...c
45.1
68.1
36.1
35.1
v331.8
33.9.24
Squirel
FAGCN
15.. 47.0
60.0.r.554.7-..
10.5
36.4-
35.3-ar
Ens.
61.3
155.2..77.5iia
61.5:2./56.0..a.
MCD
60.02
63.1
59.9ga
FBM
59.52+ 26000
50.52..66.00.r.
49.0
63.6ga
63.62x 757.7
#64.0224
41.8
39.6.x
40.5
GRBM
59.52z d46.1246
63.6gz </6642
JLDE
59.5 69.5
63.61s 1/4.2...
59
GPN
98.02..//H.BB Bais
88 Paso
189.7x.89.772.
80.9
81.1
SGCN
89. 1..
99.7
12.0..
30.1:a./29.81..
31.1
BGCN
88. 3aan
94.3a 788.221
81.32
30.62a 1832.1as
34.1
GPRGNN
97.6 a777. i.
...
95.6.../91.....
84.1..s
35.8.s
37.3-
FSGNN
97.0.c. 6
87.5
71.7-t
35.0ss 6033.111
40.2-se
CoraML
FAGCN
a9..9...66...... cu
88.9
91.3
81.4
10.1
Ens.
97.7 a97 Aane
90.62s 4
92.9gn #M2.7asa
MCD
96.9 a6.9..../96...4
92.9...192.9.11
92.3-: 1/9.
EBM
96.8 a
91.9g1 2/11.2
88.3
79.6
77.
Safe
96.82: J06.3aa
92.621 //2.82.1
91 92: 1811.8a
GEBM
96.8 a/97
92.621 152.522
91.9g: 1/11.8
JLDEE
82) 0.6.
92.621 A23
91 92 (82.
GPN
98-72x J03. a
20001200
84.0
95.3go a
84.5
SGCN
99.41.. 3
9
95.41x. 483
85.7
49.6.1 /1..6.9....
50 50.2...
399
91.3-2a
98.6....8..1...
51.2-. 152,1
53.4-1
GPRGNN
99.41.
19.44...99.44. Azui
25.2.mm
86.0...
./9.77 7axi
51.5
FSGNN
99.6...
95.4
91....
82.
64.8- W02.5
69.9-.
PulsMed
FAGCN
99.4 999.44n
94.7
95.6Gx 283.6
85.8
50.9 3/48.7
54.2.1
99.4xr.200.11 J.0.
94.3a 5.9.5...
94.3== 3/94.4ara
MCD
99.02r a/20-
94.5ge a04 4gn
a8M4
99.0 99.0az a/0. Bat
992.3..
93.5 299..4ac.
94.9
83.9
82.9
Safe
99.0gr a
99.42x x611.6
83.5gn #811.4g
GEBM
O2. 0000 Dass
93-4ax /02.2221
93 52. 781.7a..
ILDE
99.0gr e200
98.4ge 1
83.52o 2f1..8ar
31

---

Uncertainty Estimation for Heterophilic Graphs Through the Lens of Information Theory
Table 15. Expected Calibration Error (ECE) (C) of different models clean data (hest and runner-up).
Roman Empire
Amazon Ratings
Model
Chameleon
Squirrel
CoraMI.
PubMed
GCN
7.0+1e
19.0
29.3
6.0
14.8
5.221.
GATv2
7.820.6
36.524.0
44.1a10.
29.5
15.42
7.222.
GPN
13.6+1.
9.8+1.1
12. ++4.2
6.4+s.o
23.3+7.1
6.7+1.9
FAGCN
3.6#1.1
22.9
25.9+7.0
6.3
8.944.2
1.7
FSGNN
7.5+
33. +2.3
8.4
7.6
11.9
11.9
GPRGNN
6.620.9
23. 23.022.0
10.9
8.613.
8.8
3.021.7
SGCN
23.3+1.7
9.2-2.6
8.6=2.6
8.5
31.8+5.6
10.9
BGCN
4.0
3.1
22.5
6.7a3.2
5.9
6.8
Res-GCN
11.8+10
37.9+4.7
31.2+14
12.4+7.9
12.9+3.9
10.2+a.e
Res-GATE
9.720.5
43.4
27. 27.4
10.8
12.4
9.7
Res-GAT-Sep
10.4
41.020.7
25.5214.4
29.6424.4
16.022.a
10.9
Table 16. Brier score (1) of different models clean data (best and runner-up).
Roman Empire
Amazon Ratings
Model
Chameleon
Squirrel
CoraML
PubMed
GCN
0.59
0.72+
0.80
0.80+
0.30+a.e
0.24+a.02
GATv2
0.19
0.68
0.80
0.8520.03
0.30
0.24
GPN
0.87
0. 0.76
0.83
0.87
0.36 0.52
FAGCN
0.404o.0r
2o.0
0.80 03
0.81 1
0.38
0.28
FSGNN
0.31+
+o.01
0.82+o.02
0.84+0.01
0.5 +0.02
0.40+a.08
GPRGNN
0.49 00..00
0.68
0.84:20.02
0.87 20.02
0.35 1..000
0.25
SGCN
0.84
0.75
0.83 oa
0.86
0.58
0.38
BGCN
0.78
1.79
0.81
0.87 20.01
0.36
0.34
Res-GCN
0.28 0..88
0.70+
0.79 #0.04
0.78+
0.29
0.22+to.01
Res-GATE
0.18
0.67 20.01
0.82+t.04
0..62
0.28 ta.04
0.21 to.02
Res-GAT-Sep
0.1720-01
0.65 20.01
0.84 o5
0.89 a.0
0.30 0..0.o..
0.22
32


Reviews:
[{"review_id": "oEMTZ9gGvy", "reviewer": "Reviewer_is3X", "summary": "The paper explores uncertainty quantification (specifically epistemic uncertainty) in graphs without homophily -- notably previous works in this direction assumed homophily as another source of information about the ground truth probability revealing information about similarity in the conditional label distribution; this assumption is invalid in heterophily. Here the authors adopting an information-theoretic perspective. While in an i.i.d. setting, mutual information decreases by increasing the model's depth, the graph structure introduces potential information gain through message passing (extending receptive field to other nodes). This is well illustrated in the probabilistic model shown in Fig. 3.\n\nAdditionally, the authors propose a KNN-based density estimation over all latent variables concatenated (i.e., embeddings from all layers) as a measure of epistemic uncertainty. They also conduct an extensive empirical study to support their approach.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their in-depth feedback and questions. We are happy they find our paper to provide novel insights into an interesting and untapped research area. We provide additional material [here](https://figshare.com/s/05c97f1c4314003ce379?file=53331224).\n\n## Connection between Theory and Method\n\n**Context of the Paper**: JLDE is intuitively motivated since, in heterophilic graphs, a node's neighbors are semantically different from itself which leads to diverse latent embeddings. While we agree that this method could have been proposed without formal justification, we believe that our analysis provides a theoretical basis that not only supports the intuition behind JLDE's effectiveness but is also valuable for further advancements in uncertainty quantification under heterophily. We utilize it to justify that for heterophilic graphs, each embedding provides different information. To that end, we develop an information-based framework for MPNNs that describes how the information in latent embeddings relates to each other (Theorem 4.1). The key insight that links this analysis to JLDE is discussed in L.295: The information gain is governed by the information that the k+1-th hop neighbors add that is not already contained in the $\\leq$k-hop neighbors. For heterophilic data, the semantic differences between adjacent nodes induce information gain while for homophilic graphs the *additional* information diminishes. Estimating a node's data density to quantify uncertainty therefore *must* rely on all hidden embeddings. While Theorem 4.1 marks a significant contribution by itself it does not explicitly target uncertainty quantification. We view this not as a limitation. It fits well into the paper as it justifies our main claim: Uncertainty quantification in heterophilic graphs greatly benefits from considering all hidden node representations as it utilizes the information gain term. We clarify this by revising L.161 to explain that we propose JLDE as an intuitive uncertainty quantification framework that we formally justify from an information-theoretic angle. Def 4.1 and 4.2 make Theorem 4.1 more digestible by separately discussing its components. \n\n## Uncertainty Calibration Experiment\n\nThat is a great idea! We conducted this experiment (Figure 1, link above). For 5 of 6 datasets, JLDE's uncertainty correlates well with accuracy.\n\n## Writing\n\n1. We mention the KNN-based realization of JLDE in L.44 and provide pseudocode in Algorithm 1 (link above). \n2. We elaborate on Equation 3 (see below) and Equation 6 and an intuition for MI in L.83. \n3. We introduce the acronym JLDE in L.42. \n4. We defer the first paragraph of Section 3 to the Appendix to shorten Related Work.\n\n**Conciseness of Theory**: We agree that Prop. 4.2 does not directly relate to uncertainty quantification and we move it to the Appendix. \n\n## Questions \n**Aleatoric Uncertainty** is quantified as $1 - max_c p_c$ (L.838) from the backbone MPNN and is the same for all post-hoc estimators. Like related work, we report it for completeness. We move its definition and this explanation to L.348. \n\nThe **ECE and Brier** metrics (Table 14, 15) depend only on the classifier. Therefore, we do not explicitly restate it for each post-hoc uncertainty estimator and report them only for completeness.\n\n**Equation 3** is directly taken from the seminal work of Tishby et. al. that established an information-theoretic perspective on NNs. It is referenced consistently throughout the literature. In practice, the optimal estimator of Eq. 3 is not attainable and methods instead optimize a trade-off between compression and predictive capabilities similar to the reviewer's min-max formulation. For example, the \"Deep Variational Bottleneck\", (Alemi et. al., 2016) proposes a varational optimization problem. Compression is necessary because making predictions from inputs that contain semantically irrelevant information is challenging (and hence, representation learning is used). We see how this can be difficult to understand without knowledge of the prior work on information theory and NNs and add an explanation to Section 4.1.\n\n**Homophilic Graphs**: Estimators like GPN, GEBM, or Safe explicitly exploit the homophily through homophilic graph diffusion to improve uncertainty. While JLDE is particularly useful for heterophily, it does not make structural assumptions and applies to homophilic and heterophilic graphs. As a drawback, it can not exploit the homophily in graphs directly and falls short of methods that do. Nonetheless, JLDE performs competitively to other post-hoc methods that do not use homophilic graph diffusion like EBMs or Ensembles. We believe that future work can optimize JLDE for homophilic graphs.\n\nWe again thank the reviewer for their thoughtful and in-depth feedback which helped us improve our manuscript and hope we adequately addressed their points. We are happy to discuss further open questions.", "claims_and_evidence": "In general yes! The information theoretic view of the problem helps to provide a clear intuition. However, maybe due to my limited understanding of some parts of the paper, I think the theory can be summarized further while preserving the concreteness of the arguments.\n\nThe chain of arguments which I understood is: (1) from Tishby & Zaslavsky (2015), and data processing inequality, we know that on i.i.d. data, model looses information across layers (2) despite i.i.d. data, in graphs we can gain information through message passing as we visit new node, and the information gain is provably non-negative. (3) To quantify epistemic uncertainty, we need to process all latent variable (4) we can use KNN density estimation over all latent values. \n    \nIf my understanding is correct, there are several parts of the paper, that although informative, they are not directly connected to the method. For example the information loss which is quantified in Def 4.1, and Prop 4.2.\n\nAlso: I can not connect the practical method and the theoretical discussion. For that please see \"Other Strengths And Weaknesses\".", "methods_and_evaluation_criteria": "The evaluation criteria covers some of the mostly used methods in UQ literature; however, I have the following question:\n\nWhat is the method to quantify aleatoric uncertainty? I can not understand aleatoric uncertainty results in the tables for o.o.d. detection. I also can not understand the results in Table 14, and 15? The authors argue that the calibration is over models, JLDE does not contribute to the ECE, or Brier score. However, one easy way to examine the reliability of the method is to draw a plot to compare the epistemic uncertainty of the nodes compare to the accuracy. Some plot like ECE instead of confidence, the x-axis shows the average epistemic uncertainty.\n\nAlso another question:\nDoes this method easily extend to graphs with homophily? I assume there is no bottleneck for the method to extend to homophily graphs, however I see that the method is outperformed by a significant margin (> 20% in Table 6 for CoraML) compared to SOTA. What is that? What is the intuitive reason behind it?", "theoretical_claims": "There are no special theorems in the paper requiring complicated and multi-step proofs. Many of the arguments are directly supported by one line proofs often taken form the information theory literature.\n\nAdditionally these are my other problems / questions:\n\n**About Eq. 3.** (1) is it even realistic to have this estimator? (2) is it what we need for prediction? For (1) I am unsure if the search space isn’t too restrictive. In other words, maybe even finding one example in that search space is quite difficult. Because the authors are searching over a space of functions such that inputs all possible information from $X$. Which means that a marginally (weighted average over the probability of the input), it should have the same correlation with the invisible ground truth label (or here generative) distribution. I believe this is even harder than having a perfectly calibrated classifier. For (2) if we have such a classifier, even if it includes additional unnecessary information about X from the perspective of uncertainty quantification still this is a very good classifier. Even I can argue that including more information about the generative distribution of X helps generalization.\n    1. I assume the questions I asked are maybe due to not completely understanding the goal of Eq. 3. Maybe if authors provide an intuitive explanation, it can help.\n    2. Maybe I would be more convinced if the search space was not restricted but the overall optimization was written in form of a min-max problem which maximizes the information about the labels and minimizes the unnecessary information about X.", "experimental_designs_or_analyses": "Please see \"Methods And Evaluation Criteria\". There I mentioned one experiment I expect from the authors to show the reliability of the epistemic uncertainty estimates.", "relation_to_broader_scientific_literature": "The paper tends to fill the gap in uncertainty quantification for graphs. Previous works in this area assume the graph has homophily -- the two endpoints of an edge are likely to have the same label. This is potentially used as a source of information helping to signal for higher uncertainty when the prediction is not following this rule.", "essential_references_not_discussed": "I think the literature review was comprehensive and covering. I did not find any problems in that area. However I would prefer to see a shorted \"related works\" section in the manuscript and the current version in the appendix as it shifts from the main storyline of the paper.", "other_strengths_and_weaknesses": "### Strength\n\n1. I believe this area (epistemic uncertainty over heterophilic graphs) is both interesting and untapped. Also I found the approach of the authors novel and interesting; they capture the amount of information collectable the receptive field. \n2. The results on heterophilic graphs look promising. Also the extensive empirical evaluations makes the paper stronger.\n3. The theoretical insights look correct and complete.\n\n### Weaknesses\n\n1. **Context of the paper is inconsistent.** To my perspective the paper looks like two possibly orthogonal directions concatenated. Up to line 317-left is a theoretical study showing that the information (for any general estimator) can possibly gain over increasing layers. Then suddenly it shifts to introducing an uncertainty estimator that is a KNN-density estimator over the concatenation of the latent values. Despite the discussion on the information theoretic point of view, there is no clear chain of arguments leading to the choice of the uncertainty estimator. \n    \n    In other words, one can easily follow another chain of argument leading to the same estimator. For instance: since we can not count on homophily as a supplementary modal to encode similarity in the ground truth $p(y\\mid x)$, we directly use the latent representation as the input of our uncertainty estimation algorithm. We concatenate the embeddings of all layers since each hierarchically they encode information about $k$-hop neighborhood of the node. \n    \n    To me both the example argument stated above and the information theoretic perspective are equally plausible for this estimator. \n    \n2. **Writing can be improved.** Several comments on writing: (1) One can not find any footprint of the method (KNN) from the introduction. Also there is no pseudocode that helps to deliver a quick, and at the same time concrete understanding the final practical method. (2) Although a basic understanding of the information theory is necessary for anyone reading ML papers, still I would prefer to see a better intuitive description over notations like conditional mutual information, etc. Specifically Eq. 3, and 6 need more intuitive explanation. (3)The term “JLDE”  (joint latent density estimation) should be mentioned the first time it is used which is line 42-right. (4) The long discussion on the models proposed for heterophilic graphs (related works section) detaches the reader from the main story of the paper. The proposed method is agnostic to the model’s structure, therefore I would suggest a succinct summary in the manuscript and a more detailed related work perhaps in appendix.", "other_comments_or_suggestions": "Please see \"Other Strengths And Weaknesses\".", "questions_for_authors": "While addressed in other parts, here I highlight my most important questions:\n\n1. Does this method easily extend to graphs with homophily? I assume there is no bottleneck for the method to extend to homophily graphs, however I see that the method is outperformed by a significant margin (> 20% in Table 6 for CoraML) compared to SOTA. What is that? What is the intuitive reason behind it?\n2. **About Eq. 3.** (1) is it even realistic to have this estimator? (2) is it what we need for prediction? For (1) I am unsure if the search space isn’t too restrictive. In other words, maybe even finding one example in that search space is quite difficult. Because the authors are searching over a space of functions such that inputs all possible information from $X$. Which means that a marginally (weighted average over the probability of the input), it should have the same correlation with the invisible ground truth label (or here generative) distribution. I believe this is even harder than having a perfectly calibrated classifier. For (2) if we have such a classifier, even if it includes additional unnecessary information about X from the perspective of uncertainty quantification still this is a very good classifier. Even I can argue that including more information about the generative distribution of X helps generalization.\n    1. I assume the questions I asked are maybe due to not completely understanding the goal of Eq. 3. Maybe if authors provide an intuitive explanation, it can help.\n    2. Maybe I would be more convinced if the search space was not restricted but the overall optimization was written in form of a min-max problem which maximizes the information about the labels and minimizes the unnecessary information about X.\n3. What is the method to quantify aleatoric uncertainty? I can not understand aleatoric uncertainty results in the tables for o.o.d. detection. I also can not understand the results in Table 14, and 15? The authors argue that the calibration is over models, JLDE does not contribute to the ECE, or Brier score. However, one easy way to examine the reliability of the method is to draw a plot to compare the epistemic uncertainty of the nodes compare to the accuracy. Some plot like ECE instead of confidence, the x-axis shows the average epistemic uncertainty.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "There are no concerns."}}, {"review_id": "USg7FiQOjy", "reviewer": "Reviewer_ejzC", "summary": "This paper proposes an uncertainty estimation method for heterophilic graphs, primarily through the utilization of multi-layer embeddings. The authors conduct comprehensive analyses, such as examining how information propagates through message passing in neural networks, to validate their claims. They introduce a simple method called Joint Latent Density Estimation (JLDE) that combines outputs from all layers to measure uncertainty. This approach achieves superior results on heterophilic graphs compared to existing methods while maintaining performance on standard graphs. Extensive experiments across multiple datasets demonstrate its effectiveness.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thorough review and questions and address them with the following revisions to our paper in addition to the additional experiments shown [here](https://figshare.com/s/05c97f1c4314003ce379?file=53331224).\n\n1. **Efficiency**: The computational cost of KNN-based JLDE is governed by KNN, which can be implemented in $\\mathcal{O}(n_{train} * d_{hidden} + n_{train} * k)$. For smaller training sets that are typical in transductive node classification, this is negligible but can become prohibitive for large training sets. In this case, JLDE can be realized with more efficient density estimators. We opt for KNN due to its simplicity and applicability to estimating a high dimensional density from little data. However, in general, any density estimator can be used (see below). We measure the runtime of KNN-based JLDE in Table 2 (link above). For all datasets with small training sets (all but Amazon Ratings), the cost of JLDE is comparable to competitors. Using multiple layers effectively increases $d_{hidden}$ by a factor of $L$ in terms of runtime complexity. This only incurs a small additional cost (see comparison to 1-layer KNN-based JLDE in Table 2 (link above). The memory complexity is also determined by the density estimator (KNN) and amounts to keeping the embeddings of the training set in the memory, $\\mathcal{O}(n_{train} * d_{hidden})$. Since by default, these activations are kept in memory for a forward pass unless explicitly deallocated, there is no overhead in practice. We add both this explanation and the runtime comparison to the Appendix of our paper.\n\n2. **Ablations**: (a) layer-wise uncertainty: Since the performance of uncertainty estimates is unaffected by monotonic transformations, uncertainty averaging effectively amounts to the same as adding the individual uncertainty estimated from each layer. This variant is already ablated in the paper in Figures 4 and 6-8 as \"All (cat)\". We will clarify this in the revised paper. (b) Estimating high-dimensional density from little data is challenging which is why we chose KNN to realize JLDE. We also provide ablations using i) an RBF-based Kernel-Density Estimator (KDE) and a Mixture of Gaussians with diagonal covariance (MoG) in Table 1. KDE performs similarly to JLDE but MoG falls short in some settings because of its limited expressiveness. We add this ablation to the revised paper. We also want to highlight that the core message of our paper is not that KNN should be used for uncertainty quantification. Instead, we argue for the merits of estimating the data density in the joint latent node embedding space with *some* suitable density estimator.\n\nWe again want to thank the reviewer for suggesting these experiments. We believe they enable a well-rounded assessment of JLDE. Should any other concerns or questions remain, we are happy to discuss them with the reviewer!", "claims_and_evidence": "Yes, the claims made in the submission are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "Yes, the proposed methods and evaluation criteria make sense for the problem at hand.", "theoretical_claims": "Yes, I check the correctness of any proofs for theoretical claims", "experimental_designs_or_analyses": "Yes I check the soundness/validity of any experimental designs or analyses. However, the ablation study can be refined.", "relation_to_broader_scientific_literature": "1. Heterophilic GNNs: Showing uncertainty estimation requires fundamentally new principles beyond homophily-based methods.\n2. Uncertainty in Graphs: Address heterophilic uncertainty, overcoming homophily assumptions in prior work. Introduces post-hoc JLDE, unlike architecture-bound i.i.d. methods.\n3. Information Theory: Explaining why deeper MPNN layers gain information in JLDE’s joint layer modeling.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Strengths:\n1. Rigorous theoretical analysis.\n2. Logical experiments (heterophilic/homophilic graphs, multiple backbones).\n3. Strong results (SOTA on heterophilic graphs).\n4. Clear writing.\n\nWeaknesses:\n\n1. Efficiency: No analysis of computational/memory costs from multi-layer embeddings.\n2. In ablation gaps:  it is unclear if gains stem from joint embeddings or KNN. Missing comparisons to (a) layer-wise uncertainty averaging, (b) alternative density estimators.", "other_comments_or_suggestions": "Please see the above weakness.", "questions_for_authors": "NA", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "VkwsGtcfci", "reviewer": "Reviewer_n5yN", "summary": "This work addresses the lack of epistemic uncertainty measures on heterophilic graphs by studying the uncertainty of GNNs through information theory. The main contribution is the development of a post-hoc estimate, Joint Latent Density Estimation (JLDE) as a measure of the density of latent embeddings which is useful for out-of-distribution (OOD) node detection for node classification tasks.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thorough review and suggestions. We want to address their points with the following revisions of our paper:\n\n- **Synthetic Experiments with varying Homophily**: That is a great idea! We investigate how JLDE compares to the state-of-the-art homophilic estimator GEBM on a synthetic graph in [Figure 1](https://figshare.com/s/05c97f1c4314003ce379?file=53331224). The synthetic setting is adapted directly from (Das et al., 2025) with an additional out-of-distribution cluster that the model is not trained on. We observe that while GEBM rapidly deteriorates in performance with increasing heterophily, JLDE is consistently effective in homophilic and heterophilic regimes.\n\n- **Source Code**: There seems to be a misunderstanding as we provide the source code in the supplementary material on OpenReview which is also acknowledged by other reviewers.\n\n- **Other Comments**: 1) We add an explanation of the acronym JLDE to L.43. 2) We fixed this typo, thank you. 3) We agree that the KNN-based realization of JLDE should be discussed more in the main text. In favor of deferring some related work to the Appendix (see response to reviewer is3X), we move Equation 12 to the main text. We also add an explanation and a short discussion about practical concerns like runtime and memory complexity (see feedback to reviewer ejzC). 4) We add verbose explanations for each proof that explain the transition between each line. 5) Ens indeed refers to Ensemble. We clarify this in the main text.\n\n- **Aleatoric Uncertainty**: We report the performance of the associated aleatoric uncertainty estimate for completeness purposes, similar to other work (Stadler et. al., 2021; Fuchsgruber et. al., 2024). This way, we can properly assess the performance of JLDE to *all* other possible uncertainty estimates. We add a clarification that the aleatoric estimate comes from the backbone GNN (see response to reviewer is3X). If the reviewer thinks that these numbers are distracting, we can also defer them completely to the Appendix.\n\n- **Table 1**: Bold-face numbers indicate the best accuracy of the backbone GNN for this dataset and distribution shift. Grey cells highlight values that are associated with JLDE (either accuracy or o.o.d.-detection performance). We update the captions accordingly to indicate this clearly.\n\nWe again want to thank the reviewer for their suggestions. We believe that the additional experiments and clarifications underline the merits of our framework and enhance the paper's clarity. If the reviewer has any remaining points that relate to their assessment of our paper we are very happy about additional input.\n\n## References:\n- Das, Siddhartha Shankar, et al. \"SGS-GNN: A Supervised Graph Sparsification method for Graph Neural Networks.\" arXiv preprint arXiv:2502.10208 (2025).\n- Stadler, Maximilian, et al. \"Graph posterior network: Bayesian predictive uncertainty for node classification.\" Advances in Neural Information Processing Systems 34 (2021): 18033-18048.\n- Fuchsgruber, Dominik, et. al. \"Energy-based Epistemic Uncertainty for Graph Neural Networks.\" arXiv preprint arXiv:2406.04043 (2024).", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Yes. No major issues, but the proof steps need more explanation.", "experimental_designs_or_analyses": "Mostly, ok. \nHowever, one important experimental analysis is missing, which is, studying the sensitivity of the post-hoc uncertainty estimate with respect to varying degrees of homophily ratio. The authors should create synthetic graphs with controlled but varying degrees of homophily ratio and verify if the OOD detection is still effective across various regimes of homophily ratio. See, for instance, [1] (Appendix B) for such an example dataset. \n\n[1] https://arxiv.org/abs/2502.10208", "relation_to_broader_scientific_literature": "The study carries significant interest to the GNN community as well as the uncertainty-estimation community.", "essential_references_not_discussed": "None, to the best of my knowledge.", "other_strengths_and_weaknesses": "There is a clear gap in the literature where the paper fits. The proposed uncertainty estimate is supported by theoretical motivation, intuition and empirical comparison with recent baselines. No significant weaknesses except those in Comments/Suggestions and Experimental Designs/Analyses.", "other_comments_or_suggestions": "1. Line 43, 2nd column => Please elaborate on what JLDE means, since this is the first appearance of this term.\n2. Line 135, 2nd column=> I.d.d. => i.i.d \n3. Section 4.1 should be shortened to facilitate more discussion on JLDE, in particular Equations 12, and 13 and the associated discussions in the Appendix should be in the main paper. \n4. Appendix A, The steps in proofs need to be justified with more supporting statements about known results and references. \n5. What is Ens? What do you mean by an “ensemble of 10” in line 346? This needs further clarification.", "questions_for_authors": "1. Since the focus of the paper is on Epistemic uncertainty, what value does reporting Aleatoric uncertainty in Table 1 add to the paper?\n2. In Table 1, what do the boldfaced entries indicate? What is the significance of the grey regions?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "a2fjUrfV3h", "reviewer": "Reviewer_wjj2", "summary": "This paper addresses the challenge of estimating epistemic uncertainty on graphs that do not follow the homophily assumption, where neighboring nodes often belong to different classes. The authors provide an information-theoretic analysis of Message Passing Neural Networks (MPNNs) and derive an analog to the data processing inequality that reveals how information can be both lost and (importantly) gained across layers", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thorough review. We want to distinguish our contributions from related work.\n\n## Performance improvement through Heterophily\nOur theory shows that, from an information perspective, the intermediate layers (i.e. aggregation) in GNNs can provide additional information. This contrasts results for i.i.d. data where information is only lost with network depth. These results explicitly only hold for **interdependent** data (and not the i.i.d. data model). Our analysis exploits that the information a GNN uses to represent a node only depends on its ego graph of a range equal to the GNN depth as can be seen in Figure 3: The latent representation of a node also depends on the features of its $\\leq$L-hop neighbors. Therefore, our analysis *explicitly* considers the interdependence and does not require an i.i.d. data model. Theorem 4.1 is valid for *any* MPNN according to the definition of Appendix B.2 without any other assumptions like i.i.d. data.\n\nTo clarify this misunderstanding, we change the paper:\n- Changed section title 4.2 from *Information in MPNNs: A Data Processing\nEquality* to *Information for Interdependence: A Data Processing Equalty*\n- We changed the caption of Figure 3 to: *Probabilistic model of how the information is processed in MPNNs given the interdependent data...*\n- The first sentence in 4.2 to: *For problems on graphs, where we deal with interdependent data, the input **X** is twofold as it contains both node features **F** and the graph structure **E**.*\n\n\n## Discussion of related work\n\n**Heterophily is advantageous:**\nLuan et al. (2022) propose a novel homophily metric through post-aggregation node similarity and develop a novel, powerful GNN: ACM.\nLuan et al. (2023) investigate performance for graphs with various degrees of homophily by studying how node distinguishability is linked to GNN performance and they provide a better performance metric.\n\nWhile these works are meaningful contributions to heterophilic graphs, we want to stress that our work's conclusion is fundamentally different from 'heterophily is advantageous'. We study how uncertainty can be estimated in heterophilic graphs. Our new theory applies to both homophilic and heterophilic graphs. Our claim is not that certain GNNs benefit from heterophily, but instead, uncertainty in heterophilic graphs can only be quantified when doing joint density estimation. This differs from the related work that uses heterophily to improve accuracy.\n\n**Using Multiple Layers**\nYang et al. (2021) use the difference between embeddings of the previous layer and the current one to mitigate oversmoothing.\nZhang and Li (2021) extract local ego-net subgraphs for each node, apply a GNN to those, and finally pool these subgraph representations to obtain node representations.\n\nIn contrast, we use an arbitrary MPNN and estimate density from all its latent embeddings to estimate model uncertainty. While other work also considers node representations obtained at different scales, it aims to improve predictive performance by changing the GNN architecture. We apply JLDE post-hoc to an already trained GNN and estimate uncertainty from all its embeddings which we justify both formally and empirically.\n\nHowever, we agree that it is important to stress the difference to related work and are thankful for these pointers that we discuss in a new paragraph:\n\n\n```Recent work has focused on refining the inductive biases embedded in GNNs, particularly regarding graph structure, neighborhood similarity, and information aggregation across layers. Luan et al. (2022) revisit GNN performance under heterophily, challenging traditional homophily-based assumptions and proposing adaptive channel mixing to enhance representation learning across diverse neighborhoods. Similarly, Luan et al. (2023) show that GNN performance can not be attributed to homophily alone by introducing the concepts of intra- and inter-class node distinguishability.\n\nZhang and Li (2021) propose Nested GNNs, which extend beyond rooted subtrees to capture richer local substructures, emphasizing the importance of localized graph context. Complementarily, Yang et al. (2021) avoid over-smoothing by using the difference between a layer's input and output.\n\nIn contrast, our work examines the inductive biases of GNNs from an information-theoretic perspective in the context of uncertainty estimation.\nWe show the benefits of leveraging information from *all* layers and propose a theoretically grounded uncertainty estimator that achieves state-of-the-art performance. We further demonstrate that heterophilic problems necessitate jointly considering all representations.\n```\n\n## Conclusion\nWe thank the reviewer for their time and effort to review our work. We hope that we addressed the reviewer's perceived weakness as our theory does not assume i.i.d. data and clarified that we arrive at conclusions that are fundamentally different from existing work and are happy to further discuss this.", "claims_and_evidence": "The paper grounds its approach in an information-theoretic analysis, deriving a novel data processing equality that captures both the loss and gain of information across layers", "methods_and_evaluation_criteria": "By jointly considering all layer representations, the method intuitively addresses the challenge of information heterogeneity in heterophilic graphs", "theoretical_claims": "The paper’s attempt to quantify both information loss and gain is commendable. However, some proofs assume certain conditional independence structures (e.g., ego-graph representations adequately capture all necessary dependencies) which might be too idealized for real-world graph data", "experimental_designs_or_analyses": "The authors test JLDE on multiple datasets and under various distribution shifts", "relation_to_broader_scientific_literature": "The paper effectively situates its contributions within the existing literature on uncertainty estimation in both standard neural networks", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strengths\n* The paper brings a new theoretical perspective to uncertainty estimation on graphs by incorporating ideas from information theory\n* The derivation of a data processing equality that accounts for both loss and gain of information is novel\n* The experiments are extensive, covering multiple datasets, distribution shifts, and network architectures\n\nWeaknesses\n* From Definition 4.1 to Proposition 4.2, the authors show that heterophily is advantageous for graph neural networks due to the resulting information gain. Although their proof analyzes this phenomenon using information theory, the conclusion is almost identical to that of [1, 2]\n  * [1] Revisiting heterophily for graph neural networks, NeurIPS '22\n  * [2] When Do Graph Neural Networks Help with Node Classification? Investigating the Impact of Homophily Principle on Node Distinguishability, NeurIPS '23\n* The authors insist that connections to nodes with different semantics (i.e., those providing substantial information) improve overall performance. However, this assumption only holds under the i.i.d. data model, which is neither tractable nor realistic for real-world datasets\n* As defined in Eq. 6, the authors propose using the outputs from all layers, a method that has been suggested by many recent studies [3, 4]\n  * [3]: Why Do Attributes Propagate in Graph Convolutional Neural Networks?, AAAI '21\n  * [4]: Nested graph neural networks, NeurIPS '21", "other_comments_or_suggestions": "N/A", "questions_for_authors": "Please see the above weaknesses", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper studies uncertainty estimation on heterophilic graphs. The key idea is to analyze MPNNs from information-theoretic perspective and to realize that embeddings provide information about data distribution. Then uncertainty quantification is done through density estimation which leads to the proposed method named JDLE. The main concerns from the reviewers were mainly about similar observations to existing works that analyze GNNs on heterophilic graphs, extensions to homophilic graphs, additional analysis/experiments on JDLE, as well as experimental details regarding aleatoric uncertainty quantification (as the main focus of this paper is on epistemic uncertainty). I appreciate the very engaging discussions between authors and reviewers. The authors have addressed these concerns, and all reviewers remain positive about this paper. Thus, I recommend acceptance.
Decision: Accept (poster)