Technical Summary: Uncertainty Estimation for Heterophilic Graphs Through the Lens of Information Theory

Problem Statement

Uncertainty estimation for graph neural networks (GNNs) has gained significant attention, yet most existing methods rely heavily on the assumption of homophily—the tendency of nodes to connect to others of the same class. These methods often employ graph diffusion or smoothing kernels to propagate uncertainty, which is effective when semantically similar nodes are connected. However, in heterophilic settings, where nodes primarily connect to neighbors of different classes, these approaches deteriorate. The reliance on smoothing to propagate (un)certainty is less justified in heterophilic graphs, leading to poor performance in out-of-distribution (O.O.D.) detection and uncertainty quantification. Furthermore, prior work has not systematically studied how uncertainty estimators behave when homophily assumptions are violated, nor has there been a dedicated approach for heterophilic graphs that avoids explicitly exploiting homophily.

Methodology

The authors approach the problem from an information-theoretic perspective, analyzing Message Passing Neural Networks (MPNNs) to understand how latent node representations evolve through layers.

1. Information-Theoretic Analysis of MPNNs

Drawing inspiration from the Information Bottleneck principle (Tishby & Zaslavsky, 2015), the authors model the flow of information in MPNNs. Unlike standard neural networks for independent and identically distributed (i.i.d.) data, where the Data Processing Inequality (DPI) dictates that information about a target variable can only decrease or stay constant through layers, the authors derive a Data Processing Equality (DPE) for MPNNs.

Key theoretical insights include:

• Information Recovery and Gain: In MPNNs, information about a node's label $Y$ is not solely contained in the node's own features but is distributed across the ego-graph. The authors define an ego-graph $G_v$ decomposed into disjoint sets $G_v^{(i)}$ based on hop distance.
• The Equality: The mutual information $I(Y; Z^{(i+1)})$ held by a representation at layer $i+1$ decomposes additively:
  $$I(Y; Z^{(i+1)}) = I(Y; Z^{(i)}) - \Delta_{(-)}^{(0:i)} + \Delta_{(+)}^{(i+1)}$$
  Here, $\Delta_{(-)}^{(0:i)}$ represents information loss (or recovery) regarding the existing ego-graph, and $\Delta_{(+)}^{(i+1)}$ represents the information gain from the new $i+1$-hop neighbors.
• Heterophily vs. Homophily:
  • In homophilic graphs, adjacent nodes share similar semantics. Consequently, the information gain $\Delta_{(+)}^{(i+1)}$ diminishes as depth increases because deeper layers do not provide new semantic information about the target.
  • In heterophilic graphs, adjacent nodes exhibit different semantics. The information gain $\Delta_{(+)}^{(i+1)}$ can be large and positive, meaning that deeper latent embeddings contain unique and distinct information about the data distribution that shallower embeddings miss.

2. Joint Latent Density Estimation (JLDE)

Based on the finding that heterophilic graphs require the joint consideration of all node representations to capture the full data distribution, the authors propose Joint Latent Density Estimation (JLDE).

• Mechanism: Instead of estimating density from a single final layer (as is common in i.i.d. settings) or using graph diffusion, JLDE concatenates the latent embeddings from all layers of the MPNN ($Z^{(0)}, Z^{(1)}, \dots, Z^{(L)}$).
• Implementation: A simple post-hoc K-Nearest Neighbors (KNN) density estimator is applied to this concatenated joint embedding space. The epistemic uncertainty $u_{epi}(v)$ is calculated as the negative log-likelihood of the node's joint representation within the training distribution.
• Design Principle: This approach does not explicitly exploit homophily through post-processing (e.g., smoothing) and is applicable to any MPNN backbone.

Key Contributions

1. Theoretical Framework: The paper derives a novel analog to the Data Processing Inequality for MPNNs, proving that information can increase with model depth in heterophilic settings due to the unique semantic information provided by neighbors at different distances.
2. Information-Based Homophily Definition: The authors introduce a definition of homophily grounded in mutual information, distinguishing between shared information that is relevant to the target label and irrelevant noise.
3. JLDE Method: They propose Joint Latent Density Estimation, a simple, post-hoc design principle that jointly models all latent representations. This method is the first to explicitly target uncertainty quantification in heterophilic graphs without relying on homophily assumptions.
4. Empirical Validation: The method is evaluated across multiple datasets, distribution shifts, and backbone architectures, demonstrating state-of-the-art performance.

Experimental Results

The authors evaluate JLDE on six datasets (four heterophilic: Amazon Ratings, Roman Empire, Chameleon, Squirrel; two homophilic: CoraML, PubMed) under three types of distribution shifts: Leave-Out-Class (LoC), Near Feature Perturbations, and Far Feature Perturbations.

• Heterophilic Performance: On heterophilic datasets, JLDE consistently achieves state-of-the-art epistemic uncertainty (measured by O.O.D. detection AUC-ROC and AUC-PR). It significantly outperforms methods that rely on graph diffusion (e.g., GPN, GEBM) or standard ensemble methods, particularly in scenarios where information from deeper layers is critical.
• Homophilic Performance: On homophilic datasets, JLDE performs competitively with other model-agnostic estimators and matches the performance of methods explicitly designed for homophily, despite not using homophily-exploiting post-processing.
• Ablation Studies: Experiments confirm that for heterophilic graphs, using only the final layer or averaging layer-wise densities yields inferior results compared to the joint concatenation of all layers. Conversely, on homophilic graphs, the joint approach performs as well as using only the final layer, validating the theory that deeper layers add no new information in those settings.
• Backbone Agnosticism: The method is applied post-hoc to various backbones (Res-GCN, Res-GAT-Sep, Res-GATE, GPRGNN), consistently ranking as the top or runner-up estimator across different architectures.

Significance and Claims

The paper claims to provide the theoretical groundwork for advancing uncertainty estimation on graphs beyond the homophily assumption. By revealing that in heterophilic graphs, each embedding layer provides unique information about the data distribution, the authors establish a key design principle: uncertainty estimation must jointly consider all node representations.

The authors emphasize that their work:

• Addresses a gap in the literature where no prior work explicitly targets heterophilic graphs for uncertainty quantification.
• Demonstrates that existing estimators often fail when homophily assumptions are violated.
• Offers a simple, effective, and model-agnostic solution (JLDE) that achieves state-of-the-art results without requiring complex architectural changes or explicit homophily exploitation.
• Contributes to the development of reliable and trustworthy AI, particularly in high-risk domains where understanding model uncertainty in non-homophilic data is critical.

The authors remain modest regarding the scope, noting that while JLDE improves epistemic uncertainty, it does not inherently improve aleatoric uncertainty or model calibration, which remain orthogonal avenues for future work. They also conjecture that more sophisticated density models could further improve upon their simple KNN-based realization.