Uncertainty Estimation for Heterophilic Graphs Through the Lens of Information Theory

We thank the reviewer for their thorough review. We want to distinguish our contributions from related work.

Performance improvement through Heterophily

Our 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.

To clarify this misunderstanding, we change the paper:

• Changed section title 4.2 from Information in MPNNs: A Data Processing Equality to Information for Interdependence: A Data Processing Equalty
• We changed the caption of Figure 3 to: Probabilistic model of how the information is processed in MPNNs given the interdependent data...
• 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.

Discussion of related work

Heterophily is advantageous: Luan et al. (2022) propose a novel homophily metric through post-aggregation node similarity and develop a novel, powerful GNN: ACM. Luan 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.

While 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.

Using Multiple Layers Yang et al. (2021) use the difference between embeddings of the previous layer and the current one to mitigate oversmoothing. Zhang 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.

In 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.

However, 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:

Zhang 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.

In contrast, our work examines the inductive biases of GNNs from an information-theoretic perspective in the context of uncertainty estimation.
We 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.

Conclusion

We 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.

We thank the reviewer for their thorough review and suggestions. We want to address their points with the following revisions of our paper:

• 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. 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.

• 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.

• 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.

• 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.

• 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.

We 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.

References:

• Das, Siddhartha Shankar, et al. "SGS-GNN: A Supervised Graph Sparsification method for Graph Neural Networks." arXiv preprint arXiv:2502.10208 (2025).
• Stadler, Maximilian, et al. "Graph posterior network: Bayesian predictive uncertainty for node classification." Advances in Neural Information Processing Systems 34 (2021): 18033-18048.
• Fuchsgruber, Dominik, et. al. "Energy-based Epistemic Uncertainty for Graph Neural Networks." arXiv preprint arXiv:2406.04043 (2024).

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.

1. 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.

2. 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.

We 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!

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.

Connection between Theory and Method

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.

Uncertainty Calibration Experiment

That is a great idea! We conducted this experiment (Figure 1, link above). For 5 of 6 datasets, JLDE's uncertainty correlates well with accuracy.

Writing

1. We mention the KNN-based realization of JLDE in L.44 and provide pseudocode in Algorithm 1 (link above).
2. We elaborate on Equation 3 (see below) and Equation 6 and an intuition for MI in L.83.
3. We introduce the acronym JLDE in L.42.
4. We defer the first paragraph of Section 3 to the Appendix to shorten Related Work.

Conciseness of Theory: We agree that Prop. 4.2 does not directly relate to uncertainty quantification and we move it to the Appendix.

Questions

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.

The 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.

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.

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.

We 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.