Research map / Graph learning / GNN architectures
Uncertainty Estimation for Heterophilic Graphs Through the Lens of Information Theory
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Derives an MPNN analog of the data processing inequality and proposes JLDE, a post-hoc KNN density estimator on concatenated layer embeddings, for epistemic uncertainty on heterophilic graphs.
Problem
Uncertainty estimation for node classification degrades on heterophilic graphs because existing methods rely on homophily (smoothing/diffusion of uncertainty).
Approach
An information-theoretic DPI-style decomposition for MPNNs shows information about the label can increase with depth under heterophily, so epistemic uncertainty should be estimated jointly from all layer embeddings; a simple KNN density on the concatenated embeddings (JLDE) implements this post-hoc.
Key results
- On Roman Empire under far-feature perturbations, JLDE reaches 100.0 epistemic AUC-ROC on the Res-GCN backbone versus 92.0 for the best baseline (EBM).
- On Amazon Ratings under leave-out-class shift, JLDE epistemic AUC-ROC is 61.2 vs. 57.9 for the best baseline (Ensemble).
- JLDE matches prior work on homophilic CoraML (e.g., 95.7 vs. 93.5 for EBM under far-feature shift) without graph diffusion post-processing.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use joint density estimation over all layer representations rather than estimating density from one layer at a time (ablation) | JLDE on Res-GCN · Amazon Ratings and Roman Empire, LoC | AUC-ROC | Helped |
| use joint density estimation over all layer representations rather than estimating density from one layer at a time (ablation) | JLDE on Res-GCN · CoraML | AUC-ROC | No clear effect |
| concatenate all layer representations rather than estimate each layer's density independently and average uncertainty scores (ablation) | JLDE on Res-GCN · Amazon Ratings and Roman Empire, LoC | AUC-ROC | Helped |
| concatenate only the first and last layer representations instead of all layer representations (ablation) | JLDE on Res-GCN · heterophilic graphs, LoC | AUC-ROC | Hurt |
| apply JLDE instead of the strongest reported epistemic baseline | Res-GCN · Roman Empire LoC, Near-Features, and Far-Features | AUC-ROC: 76.2 -> 76.9; 87.9 -> 93.8; 92.0 -> 100.0 | Helped |
| apply JLDE instead of the strongest reported epistemic baseline | Res-GCN · Amazon Ratings LoC, Near-Features, and Far-Features | AUC-ROC: 57.9 -> 61.2; 70.0 -> 65.4; 94.4 -> 99.2 | Mixed |
| apply JLDE instead of the strongest reported epistemic baseline | Res-GCN · CoraML LoC, Near-Features, and Far-Features | AUC-ROC: 87.4 -> 80.8; 76.0 -> 54.9; 93.5 -> 95.7 | Mixed |
Surprising findings
- Information about the label can increase with model depth on heterophilic graphs, contrary to the standard DPI.
- Aleatoric (softmax) uncertainty is better than epistemic uncertainty for misclassification detection, as in prior work.
Limitations
- Only the simplest KNN density estimator is used; more sophisticated density models are not explored.
- Focuses on node classification; does not improve aleatoric uncertainty or calibration.
- Results on LoC and near-feature shifts are mixed; e.g., on Roman Empire near-feature, Ensemble/GPRGNN are competitive on AUC-ROC.
Experimental setup
Datasets: Roman Empire Amazon Ratings Chameleon Squirrel CoraML PubMed
Benchmarks: Roman Empire Amazon Ratings Chameleon Squirrel CoraML PubMed
Metrics: AUC-ROC AUC-PR accuracy ECE rank
Baselines: GPN SGCN BGCN Ensemble MC Dropout EBM GNNSafe GEBM
Builds on: Information Bottleneck (Tishby) Deep Deterministic Uncertainty / feature collapse analysis Graph Posterior Network GNNSafe GPRGNN
Closest papers by meaning
- Energy-based Epistemic Uncertainty for Graph Neural Networks (NeurIPS 2024 · similarity 0.91)
- Accurate and Scalable Estimation of Epistemic Uncertainty for Graph Neural Networks (ICLR 2024 · similarity 0.90)
- A Unified Uncertainty Representation for Graph Neural Networks via Doubly-Spectral Stochastic Expansion (NeurIPS 2026 · similarity 0.90)
- Uncertainty Estimation on Graphs with Structure Informed Stochastic Partial Differential Equations (NeurIPS 2025 · similarity 0.89)
- Learning Latent Graph Structures and their Uncertainty (ICML 2025 · similarity 0.88)
- Uncertainty Modeling in Graph Neural Networks via Stochastic Differential Equations (ICLR 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.