Uncertainty Estimation for Heterophilic Graphs Through the Lens of Information Theory

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.

Previous uncertainty estimation methods for Graph Neural Networks (GNNs) heavily rely on homophily which means that edges predominantly exist between semantically similar nodes. We investigate how uncertainty can be quantified for heterophilic graphs where nodes with different semantics are connected.We use Mutual Information (MI) to measure and track the informativeness of a node's features and those of nodes it connects to. This way, we derive an analog to the well-known Data Processing Inequality that applies to all Message Passing Neural Networks (MPNNs), a broad family of GNNs. In contrast to domains with independent data, our analysis shows that a node's embedding in the MPNN can get more informative the deeper it is in the MPNN. The amount of additional information is governed by how heterophilic the node's neighbors are. This motivates estimating uncertainty on these graphs from jointly considering all embeddings of a node the GNN provides. In practice, this strategy outperforms existing methods for heterophilic graphs and is competitive on homophilic graphs.Our research provides an information-theoretic background for MPNNs and uses this to bridge the gap between reliable Machine Learning and non-homophilic graphs.