Uncertainty Estimation for Heterophilic Graphs Through the Lens of Information Theory

Dominik Fuchsgruber, Tom Wollschläger, Johannes Bordne, Stephan Günnemann
Proceedings of the 42nd International Conference on Machine Learning, PMLR 267:17928-17959, 2025.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v267-fuchsgruber25a, title = {Uncertainty Estimation for Heterophilic Graphs Through the Lens of Information Theory}, author = {Fuchsgruber, Dominik and Wollschl\"{a}ger, Tom and Bordne, Johannes and G\"{u}nnemann, Stephan}, booktitle = {Proceedings of the 42nd International Conference on Machine Learning}, pages = {17928--17959}, year = {2025}, editor = {Singh, Aarti and Fazel, Maryam and Hsu, Daniel and Lacoste-Julien, Simon and Berkenkamp, Felix and Maharaj, Tegan and Wagstaff, Kiri and Zhu, Jerry}, volume = {267}, series = {Proceedings of Machine Learning Research}, month = {13--19 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v267/main/assets/fuchsgruber25a/fuchsgruber25a.pdf}, url = {https://proceedings.mlr.press/v267/fuchsgruber25a.html}, 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.} }
Endnote
%0 Conference Paper %T Uncertainty Estimation for Heterophilic Graphs Through the Lens of Information Theory %A Dominik Fuchsgruber %A Tom Wollschläger %A Johannes Bordne %A Stephan Günnemann %B Proceedings of the 42nd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2025 %E Aarti Singh %E Maryam Fazel %E Daniel Hsu %E Simon Lacoste-Julien %E Felix Berkenkamp %E Tegan Maharaj %E Kiri Wagstaff %E Jerry Zhu %F pmlr-v267-fuchsgruber25a %I PMLR %P 17928--17959 %U https://proceedings.mlr.press/v267/fuchsgruber25a.html %V 267 %X 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.
APA
Fuchsgruber, D., Wollschläger, T., Bordne, J. & Günnemann, S.. (2025). Uncertainty Estimation for Heterophilic Graphs Through the Lens of Information Theory. Proceedings of the 42nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 267:17928-17959 Available from https://proceedings.mlr.press/v267/fuchsgruber25a.html.

Related Material