Credal Graph Neural Networks

Matteo Tolloso & Davide Bacciu · 2025

Read Credal Graph Neural Networks by Matteo Tolloso & Davide Bacciu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-02722.txt.

Introduction

Matteo Tolloso and Davide Bacciu give graph neural networks a new way to express doubt. Such networks learn from linked data, and honest uncertainty is essential before trusting them in practice. Most current tools rely on Bayesian inference or on ensembles of models.

Their credal graph neural networks output sets of plausible predictions instead of one fixed answer. A credal set shows the range the model still finds credible. Set valued answers can warn users when a graph based system, used in science or medicine, is guessing beyond its evidence. A set of live picks is a more honest brief than one pick dressed up as sure fact for a board.

Catalog record

CREATORMatteo Tolloso & Davide Bacciu
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE43 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2512-02722

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Credal Graph Neural Networks Matteo Tolloso & Davide Bacciu Abstract Uncertainty quantification is essential for deploying reliable Graph Neural Networks (GNNs), where existing approaches primarily rely on Bayesian inference or ensembles. In this paper, we introduce the first credal graph neural networks (CGNNs), which extend credal learning to the graph domain by training GNNs to output set-valued predictions in the form of credal sets. To account for the distinctive nature of message passing in GNNs, we develop a complementary approach to credal learning that leverages different aspects of layer-wise information propagation. We assess our approach on uncertainty quantification in node classification under out-of-distribution conditions. Our analysis highlights the critical role of the graph homophily assumption in shaping the effectiveness of uncertainty estimates. Extensive experiments demonstrate that CGNNs deliver more reliable representations of epistemic uncertainty and achieve state-of-the-art performance under distributional shift on heterophilic graphs. 1 Introduction In safety-critical applications, a machine learning (ML) model must not only be accurate but also aware of its own limitations. The central challenge in making ML models reliable for real-world deployment is particularly acute for Graph Neural Networks (GNNs) ( 3 ) , where the inherent dependencies between data points violate the standard i.i.d. assumption. In a classical ML model, its confidence is often conflated into a single predictive probability, which fails to distinguish different sources of uncertainty ( 11 ) . This lack of specificity is critical on graphs, where a model can be uncertain about a node’s class either because its local neighborhood is genuinely ambiguous (a property of the data) or because the node and its connections are entirely novel and outside the training distribution (a property of the model’s knowledge) ( 22 ; 20 ) . To build more robust systems, we must formally disentangle the two primary sources of uncertainty: aleatoric uncertainty , the inherent and often irreducible randomness in the data-generating process, and epistemic uncertainty , which stems from the model’s limited knowledge and is potentially reducible with additional data or improved models ( 10 ; 44 ) . This decomposition underpins many modern approaches for uncertainty-aware learning and OOD detection ( 22 ) . Despite the progress of existing approaches (see Appendix B ), a critical gap remains. Most current frameworks, particularly those based on message passing or uncertainty diffusion, implicitly assume graph homophily, i.e., that connected nodes tend to share similar features or labels ( 31 ) . As a result, their performance and the reliability of their uncertainty estimates deteriorate significantly in heterophilic settings, a challenge only recently beginning to be systematically addressed ( 8 ) . This highlights the need for new, robust uncertainty quantification frameworks that do not rely on homophily and can operate effectively across diverse graph structures. Main Contributions. We address the problem of uncertainty estimation in graph learning task, by proposing an approach based on credal learning, and assessing specifically the underlooked aspect of graph heterophily. Our main contributions are: (i) we introduce Credal Graph Neural Networks (CGNNs) , the first framework that extends credal learning to the graph domain; (ii) we develop a credal graph learning architecture that leverages layer-wise message passing to provide more faithful uncertainty representations; and (iii) we conduct extensive experiments on both homophilic and heterophilic benchmarks, showing that CGNNs achieve state-of-the-art performance in out-of-distribution detection and highlight the critical role of graph structure in shaping uncertainty estimates. The repository, which includes the implementation of our proposed Credal GNN and all other benchmarked models, can be accessed at the following anonymous link: https://anonymous.4open.science/r/CGNN-EIML25 . 2 Credal Graph Neural Networks This section introduces our Credal Graph Neural Network (CGNN) framework. We begin by outlining the principles of credal learning, which models uncertainty using sets of probability distributions to disentangle its aleatoric and epistemic sources. We then present our novel architecture for Credal Graph Learning by discussing on how the credal layer can be applied to graphs. Credal Learning. We begin by providing the basics of definitions behind our credal-based approach to uncertainty in graph learning. Credal learning has been proposed to address the limitations of BNNs and Ensemble-based approaches by explicitly modeling uncertainty as a convex set of probability distributions, known as a credal set \mathcal{P} ( 6 ) . In practice, the model constructs this set by outputting a probability interval for each class, with each interval being defined by a lower and an upper bound. Figure 1 provides a visual example for 3-class classification task. The shaded area represents the credal set, which can be interpreted as the region of the hypothesis that is coherent with the training data. Figure 1: Visualization of aleatoric uncertainty (AU) and epistemic uncertainty (EU) for a 3-class classification problem. The top row shows a Bayesian continuous representation, while the bottom row shows the corresponding credal set representation. (a) Low AU and low EU: the model is confident in its prediction. (b) High AU, low EU: the model attributes uncertainty to noisy data. (c) High AU and high EU: the model faces out-of-distribution data. (d) Low AU, high EU: the model encounters novel data and attributes uncertainty to its parameters rather than to noise. In the credal set representation (bottom row), the shaded regions inside the simplex correspond to lower and upper probability bounds for each class. Instead of averaging distributions, as needed by Bayesian Model Averaging or Ensembles (details in Appendix G ), uncertainty can be defined by the size and location of \mathcal{P} inside the simplex. Similarly to 47 , we quantify this using generalized entropy, which defines the total uncertainty TU and the aleatoric uncertainty AU as the maximum and minimum possible Shannon entropy for any distribution p within the credal set ( 2 ) : \text{TU}:=\overline{H}(\mathcal{P})=\max_{\boldsymbol{p}\in\mathcal{P}}H(\boldsymbol{p}),\quad\text{AU}:=\underline{H}(\mathcal{P})=\min_{\boldsymbol{p}\in\mathcal{P}}H(\boldsymbol{p}). (1) The epistemic uncertainty is the difference, EU :=\overline{H}(\mathcal{P})-\underline{H}(\mathcal{P}) , which intuitively depends on the volume of the credal set and on its position inside the simplex. A confident prediction (Figure 1 (a)) corresponds to a small set near a vertex. High data uncertainty (Figure 1 (b)) is a small set near the center. High epistemic uncertainty is a large set covering a significant portion of the simplex (Figure 1 (c and d)), indicating that many different probability distributions are considered plausible. Credal graph layer. To move beyond single-point probability predictions, we build on the Credal Layer proposed by 46 as a replacement for the classification layer of a GNN. Let \boldsymbol{z_{v}} be a generic embedding of node v (as computed by some layer of a GNN), the Credal Layer would then take \boldsymbol{z_{v}} as input and, for each of the C classes, output two values: an interval midpoint m^{c}_{v} and a half-length h^{c}_{v}\geq 0 . Collecting these for all classes gives two vectors \boldsymbol{m_{v}}=(m^{1}_{v},\dots,m^{C}_{v}) and \boldsymbol{h_{v}}=(h^{1}_{v},\dots,h^{C}_{v}) , each of length C . This is achieved using the transformation: \boldsymbol{m_{v}}=g({W}\times\boldsymbol{z_{v}}+\boldsymbol{b}),\quad\boldsymbol{h_{v}}=g^{\prime}({W^{\prime}}\times\boldsymbol{z_{v}}+\boldsymbol{b^{\prime}}), (2) where g and g^{\prime} are activation functions, with g^{\prime}\geq 0 . These values define an interval for each class, [\boldsymbol{a^{L}_{v}},\boldsymbol{a^{U}_{v}}]:=[\boldsymbol{m_{v}}-\boldsymbol{h_{v}},\boldsymbol{m_{v}}+\boldsymbol{h_{v}}] . To transform these into valid lower and upper probability bounds, [\boldsymbol{q^{L}_{v}},\boldsymbol{q^{U}_{v}}] , that satisfy the necessary convexity conditions, a specialized Interval SoftMax activation ( 48 ) is applied: q^{L_{i}}_{v}=\frac{\exp(a^{L_{i}}_{v})}{\exp(a^{L_{i}}_{v})+\sum_{k\neq i}\exp(a^{U_{k}}_{v})},\quad q^{U_{i}}_{v}=\frac{\exp(a^{U_{i}}_{v})}{\exp(a^{U_{i}}_{v})+\sum_{k\neq i}\exp(a^{L_{k}}_{v})}. (3) The resulting probability intervals define a credal set \mathcal{P}_{v}=\{\mathbf{q}|q^{i}\in[q^{L_{i}}_{v},q^{U_{i}}_{v}],\sum_{i=1}^{C}q^{i}=1\} , which constitutes the final credal

Read the complete text