Uncertainty in Graph Neural Networks: A Survey
Authors: Fangxin Wang
Yuqing Liu
Kay Liu
Yibo Wang
Sourav Medya
Philip S. Yu
Venue: Accepted by TMLR ()

Abstract: Graph Neural Networks (GNNs) have been extensively used in various real-world applications. However, the predictive uncertainty of GNNs stemming from diverse sources such as inherent randomness in data and model training errors can lead to unstable and erroneous predictions. Therefore, identifying, quantifying, and utilizing uncertainty are essential to enhance the performance of the model for the downstream tasks as well as the reliability of the GNN predictions. This survey aims to provide a comprehensive overview of the GNNs from the perspective of uncertainty with an emphasis on its integration in graph learning. We compare and summarize existing graph uncertainty theory and methods, alongside the corresponding downstream tasks. Thereby, we bridge the gap between theory and practice, meanwhile connecting different GNN communities. Moreover, our work provides valuable insights into promising directions in this field.

Published in Transactions on Machine Learning Research (11/2024)
Uncertainty in Graph Neural Networks: A Survey
Fangxin Wang, Yuqing Liu, Kay Liu, Yibo Wang, Sourav Medya, Philip S. Yu (fwang51. yliu363, zliu234, ywang633, medya, psyu/ @ edc
Department of Computer Science, University of Illinois Chicago
Reviewed on OpenReview: https://pppaareee....////ouotttd
Abstract
Graph Neural Networks (GNNS) have been extensively used in various real-world applications. However, the predictive uncertainty of GNNS stemming from diverse sources such inherent ran- domness in data and model training errors can lead to unstable and erroneous predictions. There- fore, identifying, quantifying, and utilizing uncertainty are essential to enhance the performance of the model for the downstream tasks as well as the reliability of the GNN predictions. This survey aims to provide a comprehensive overview of the GNNS from the perspective of uncertainty with an emphasis on its integration in graph learning. We compare and summarize existing graph uncer- tainty theory and methods, alongside the corresponding downstream tasks. Thereby. we bridge the gap between theory and practice, meanwhile connecting different GNN communities. Moreover, our work provides valuable insights into promising directions in this field.
1 Introduction
Graph Neural Networks (GNNS) have been widely employed in important real-world applications, including outlier de- tection (Liu et al. 2022b), molecular property prediction (Wollschläger et al. 2023). and traffic regularization (Zhuang al. 2022). Within these domains, GNNS inevitably present uncertainty towards their predictions, leading to unstable and erroneous prediction results. Uncertainty in GNNS arises from multiple sources, for example, inherent random- in data, error in GNN training, and unknown test data from other distributions. To mitigate the adverse impact of predictive uncertainty on GNN predictions, it is crucial to systematically identify, quantify, and utilize uncertainty. Uncertainty in GNNs plays a vital role in prevalent graph-based tasks, such as selecting nodes to label in graph ac- tive learning (Cai et al., (017)) and indicating the likelihood of a node being out-of-diitribution (OOD) (Zhao et al. 2020). Furthermore, this practice enhances the predictive performance of GNNS (Vashishth et al. 2019). and bolsters their reliability for decision makinng such as making GNNS robust to attacks (Feng et al. 2021 and explains which components of the graphs influence GNN predictions (Ying et al. 2019).
Several challenges need to be addressed to boost GNNS with uncertainty. Firstly, different sources of uncertainties in GNNS need to be identified, as uncertainty may stem from multiple stages including data acquisition, GNN construc- tion, and inference (Gawlikowski et al.) 2023). Secondly, different categories of uncertainties should be matched with corresponding tasks. For instance, distributional uncertainty should be applied to graph OOD detection (Gui et al. 2022). Thirdly, uncertainties in GNNS are difficult to quantify correctly due to the lack of ground truth and unified evaluation metrics. Lastly, quantified uncertainty may adapted and combined with the other components to bet- ter serve the task, e.g., graph active learning (Zhang et al. 2021a). Multiple studies have endeavored solve these challenges in specific tasks. In this paper, we provide a holistic view of these tasks through the lens of uncertainty.
To the best of our knowledge, existing surveys or benchmarks either focus broader field, i.c., uncertainty in Deep Neural Networks (Abdar et al., 2021 Hüllermeier & Waegeman 2021 Gawlikowski et al. 2023) and trustworthy
GNN (Wu et al. 2022). or on narrower topics, e.g., uncertainty in spatio-temporal GNNS (Wu et al. 2022 Wang et al. 2023). Besides, these surveys mainly discuss how to estimate and measure uncertainty, missing concrete and practical guidance on how quantified uncertainties can be applied toward the final downstream task. Our survey aims to bridge these gaps by conducting systematic review of GNNS from the perspective of uncertainty, with a special focus on incorporating uncertainty into graph learning. Furthermore, our survey contributes to the broader GNN community by

---

Published in Transactions on Machine Learning Research (11/2024)
Uncertainty Sources (S2)
Uncertainty Quantification (S3)
Downstream Tasks (S4)
AU
Uncertainty Quantification Models
Evaluating Uncertainty Quantification Models
Node Selection
?
PU
MU
Abnormality Detection
GNN Modeling
DU
^
Trustworthy GNN
Single Deterministic Model (S3.1)
Single Model with Random Parameters (S3.2) (e.g.. Bayesian GNN)
Other Methods (S3.3) (e.g., Ensemble Models)
(e.g.. Direct Estimation)
Figure Overall Framework: (I) identifying sources of uncertainty (Section 2 (2) quantifying uncertainty (Section 3 and (3) utilizing uncertainty for downstream tasks (Section 4 In the first subfigure, 'PU' refers to predictive/total uncertainty. "AU' represents aleatoriccdattasstaittiaaa uncertainty. "EU" is in short for epistemic uncertainty. 'MU' and 'DU' represent model and distributional uncertainty, respectively.
reviewing the trends of the current studies to approach uncertainty from distinct sub-communities, particularly across different downstream tasks. Our goal is to present a comprehensive framework that clarifies ambiguous terminologies, connects several communities, as well as offers valuable insights and directions to advance the overall development of GNN uncertainty and related fields.
In this paper, we organize the literature of uncertainty in GNNS into three-stage framework, illustrated in Figure Consequently, we introduce real-world applications utilizing GNN uncertainty in Section [ Finally, in Section discuss significant and promising avenues for future research in this field. For further related background, we encourage readers to investigate Wu et al. (2020b) for detailed introduction to GNNs, and Abdar et al.) (2021):
Hüllermeier & Waegeman 2021 Gawlikowski et al. (2023) for uncertainty in deep learning.
2 Identifying Sources of Uncertainty in GNNS
In machine learning, (total) uncertainty generally equals predictive uncertainty (PU), defined as the uncertainty propagated into the prediction results. For accurate estimation and application of uncertainty, it is necessary to first identify different sources of uncertainty. Predictive uncertainty is commonly divided into aleatoric and epistemic ones based on their inherent different sources (Hüllermeier & Waegeman 202T).
Aleatoric uncertainty (AU), Aleatoric uncertainty- known as data or statistical uncertainty-reffers variability in the outcome of an experiment which is due to inherent random effects. This often arises during the pre-processing stage. where data collection may lack sufficient information contain noise and emrors. As an example, collecting more data from the same graph distribution does not reduce aleatoric uncertainty; however, incorporating additional node features with non-overlapping information can reduce the inherent randomness. Unlike Munikoti et al. (2023), we align with the prevailing theory that aleatoric uncertainty can be estimated but non-reducible through improvements in GNN (Hüllermeier & Waegeman 202T), using it as the primary criterion to categorize existing literature.
Epistemic uncertainty (EU). In contrast, epistemic uncertainty-Knoow as systemic uncertainty-reffrs the uncer- tainty caused by the lack of knowledge of the GNN, thus reducible. It arises in the procedure of GNN modeling, further classified as model uncertainty (MU). On one hand, model uncertainty comes from the choice of model structure. For instance, the shallow network structure may lead to the under-confidence of GNNs (Wang et al.) 2022). On the other hand, the training process of GNN also introduces model uncertainty in the selection of parameters, for example, learning rate, epoch number, batch size, and techniques (e.g., weight initialization). Introduced by Malinin Gales (2018), another type of epistemic uncertainty distributional uncertainty (DU), which arises when GNN has false assumption about the problem setting and data generation process. This is common for inductive inference, where GNN is trained graph and applied to another graph for prediction tasks, such that the training and test sets do
2

---

Published in Transactions on Machine Learning Research (11/2024)
not come from the same distribution. While applying the trained GNN to the test data for inference, the distribution shift contributes to the uncertainty of prediction.
Note that since EU = MU + DU, and PU = AU + EU, then PU = AU + MU + DU. This relationship is illustrated in In most settings, prediction results are typically considered to have no distributional
the middle subfigure Figure 2 uncertainty, DU=0, thus EU SUU=MU+0=MP To avoid confusion of terms, we will use epistemic uncertainty (EU) at most time in Sections 4 and distributional uncertainty (DU) is explicitly stated, such in tasks like OOD, we will use MU and DU.
Besides these frequently classified types, GNN uncertainty can also be classified from subjective viewpoints, e.g., vacuity (conflicting evidence) and dissonance (lack of evidence) (Zhao et al. (020).
In general, the goal for GNN modeling should be to reduce EU, including delicate design of model structures and parameters, along with enhanced robustness and generalization to diverse distributions. On the contrary. since AU can only be quantified but not reduced, separating it from the epistemic uncertainty would provide a more reliable illustration of GNN performance.
3 Quantifying Uncertainty in GNNS
In this section, we classify existing GNN uncertainty quantification methods into three classes according to the number of models and whether model parameters are random variables. Following this classification,, we present evaluation metrics for different quantification methods. In Table T we summarize and compare attributes of these methods.
Table I: Comparisons of different families of GNN uncertainty quantification methods.
Single Deterministic Model
Single Model with Parameters Being Random Variables
Properties
Ensemble Model
Direct
Bayesian-based
Frequentist-basee
Number Model(s)
>1
Deterministic Parameters
Yes
No, purameters with perturbation
No, different parameters
Bayesian/requentiss
Neither
Bayesian
Frequentist
Bayesian
Either
Parameter Sensitivity
High
Lower
Lower
Low, affected by prior selection
Low
Modeled DU
No
Yes
No
No
No
Separation AU EU
No
Yes
Yes
Modifications of Model
No
Yes
No
Yes
Yes
Cost of Training
Low
Higher
High
Cost of Inference
Low
Hlgh
High
3.1 Single Deterministic Model
This family of methods consists of a single model with deterministic parameters, i.e., each repetition of the method produces the same result. We classify them into direct, Bayesian-basede and Frequentist-based estimation methods.
Direct estimation. The most commonly used uncertainty estimation method is through the softmax probability of prediction outcomes, including maximum softmax probability (Wang et al.] 2021) and entropy (Cai et al. 2017). Other heuristic measures, such as the distance of the sample to each class the representation space (Xu et al., 2023) are also used to quantify uncertainty. Direct estimation methods integrate uncertainty estimation with prediction and do not require modifications of the original model.
However, it has been shown that GNN tends to be under-confident (Wang al. 2021). which leads to inaccurate estimation of confidence and entropy. Confidence is an indication of how likely (probability) the predictions of machine learning algorithm are correct, often computed as the maximum softmax class probability. Under-confidence, in other words, refers to that confidence, as the indication of accuracy, falls below the true prediction accuracy. To mitigate the issue of under-confidence, a well-calibrated GNN should produce predicted probabilities that accurately reflect the true likelihood of the predicted outcomes. This is usually evaluated with smaller Expected Calibration Error (ECE) (Guo et al., 2017). To provide faithful uncertainty estimation, Wang al. (2021) add regularizer in
3

---

Published in Transactions on Machine Learning Research (11/2024)
the GNN optimization objective, which penalizes the probabilities of the incorrect nodes and encourages the correct nodes to be more confident. [Luu et al. (2022d) employ classical post-processing methods to calibrate GNN confidence, including histogram binning, isotonic regression, and Bayesian binning into quantiles. Similarly, Hsu et al. (2022b) propose a post hoc calibration method tailored for GNNS. Compared with uncalibrated direct estimation, the current calibration methods can effectively reduces ECE, but require additional calibration samples.
In addition, the inherent problem with estimated uncertainty is that the softmax output only reflects the total predic- tive uncertainty instead of the model uncertainty, leading to false estimation under the distribution shift. Therefore, direct estimation is simple and casy-to-apply choice only when computation and data efficiency is preferable over estimation accuracy.
Bayesian-based estimation is a family of Bayesian- based deterministic models. Compared to direct estimation, the model fulfills the dual objectives of prediction and uncertainty estimation using Bayesian statistical principles. These methods typically utilize the Dirichlet distribution, which serves as the conjugate prior distribution of the categorical distribution in Bayesian inference. Dirichlet distribution is advantageous in directly reflecting higher distributional uncertainty with flatter (less variant) logits over all categories. Therefore, it is utilized in GNN uncertainty estimation approaches such as Evidential neural networks (Zhao et al.) 2020; Stadler et al.) 2021 Bazhenov et al. 2023). Zhao et al. (2020) first apply Dirichlet-based methods to GNNS, which incorporates information about the local neighbor- hood through the shortest path distances and the node labels. [Stadler et al. (202T) better model the network effects through diffusing Dirichlet parameters in graph propagation. As the training loss are modified for both prediction accuracy and uncertainty quantification, especially for DU, these methods are more suitable for specific tasks, e.g.,
OOD detection, but may not produce the best performance in other tasks, e.g., node classification (Bazhenov et al. 2023). For the same reason, another disadvantage of existing methods is that they can not be directly applied already trained GNNS post-hoc.
Frequentist-based estimation. This is recently adverted family of methods to achieve trustworthy uncertainty es- timation. Frequentist methods are typically model-agnostic and estimate uncertainty through post-processing. This implies that they do not alter the model or directly offer uncertainty estimation alongside prediction. In contrast to Bayesian- based approaches, they exhibit computational efficiency with fewer additional parameters, and their estima- tion is distribution-fiee and more robust compared to the direct methods.
Kang et al. 2022) estimate uncertainty through the length of confidence bands, constructed with jackknife (leave- one-out) sampling (Efron] 1982) on training data and influence function to estimate the change in GNN parameters. Though this idea is similar to MC dropout in Section 3.2 it leaves out samples and modifies model parameters in a Frequentist manner, not assuming a prior distribution of model components. Early works (Báäw) 2022 Clarkson 2023) employing conformal prediction framework to GNNS provide guaranteed uncertainty estimation with the size of prediction sets under different settings, but involve less specific designs for GNNS. Recent works (Huang et al. 2023a Zargarbashi et al., (023) focus on optimizing for smaller set sizes (i.e., better efficiency) while covering the true labels in sets with guaranteed high probability. To achieve this goal, Zargarbashi et al. (2023) propagate node labels in the calibration set, and Huang et al. (2023a) directly use the inefficiency of the calibration set as the optimization objective.
However, existing Frequentist- tween AU and EU, as opposed to the belief that they only quantify AU (Qian et al., 2023). is also noteworthy that all these methods are built on the data exchangeability assumption. To satisfy this assumption, current methods split the data in fixed modes, mostly via random sampling. Lunde et al. (2023) provide some other general sampling methods in graphs where exchangeability assumption is not violated. However, in these cases, some specific graph properties are required. The validity of methods using non-random data splits, c.g., inductive settings, rely on nonexchangeable conformal prediction techniques, especially weighted conformal prediction (Barber et al.) 2023). This area of research still has ample space for further exploration, particularly regarding how to optimally choose the weights. In practice. exchangeability assumption is believed to be satisfied if the coverage rate meets the pre-determined level in the exper- iments. Though this is not a sufficient condition to support the assumption, this practice is reasonable as guaranteed coverage rate is part of the method's goal and evaluation metric. Furthermore, in current graph conformal prediction methods, the guarantee of uncertainty quantification is marginal coverage the total test data or conditional on some specific groups Conditioning on each sample requires uniform unconformity scores (Einbinder et al., 2022), which are nearly impossible. This hinders the application of conformal methods on most downstream tasks in Section
methods quantify total predictive uncertainty and do not explicitly distinguish be-
4

---

Published in Transactions on Machine Learning Research (11/2024)
3.2 Single Model with Parameters Being Random Variables
Models with parameters being random variables, mostly Bayesian GNNS, are another widely used family of GNN uncertainty quantification methods. A vast majority of these methods rely on Monte Carlo (MC) dropout to sample weights for variational inference. Zhang et al. (2019b) first develop Bayesian neural network framework for graphs depending on the graph topology. where the observed graph is viewed as a realization from a parametric family of random graphs. [Haaanzadhh et al. (2020) point out that the graph dropout techniques (Rong et al., 2019) can be utilized the test time for uncertainty estimation, and advance /Zhang et al. (2019b) by considering node features and adaptive connection sampling. Cha et al. (2023) discover that under the conformal prediction framework, Bayesian GNN with tempered posterior can improve the efficiency of predictions. Markov Chain Monte Carlo (MCMC) sampling methods are another family of Bayesian methods that represent uncertainty without parametric model. However, these models are rarely used in graphs due to their expensive computational costs (Wu et al. 2021).
Bayesian GNNS can separate AU and EU through metries introduced in Section 3.4 Nevertheless, existing research in this domain primarily concentrates on enhancing uncertainty awareness and minimizing predictive uncertainty, Despite their effectiveness in enhancing prediction accuracy and providing uncertainty estimates, Bayesian GNNS often encounter challenges in devising meaningful priors for graphs and efficiently estimating uncertainty through repeated sampling during inference. Additionally, these models typically do not account for the distributional uncertainty (DU),
3.3 Other Methods
Different from the Bayesian GNNS that perturb parameters around a single optimal model, ensemble models derive the final prediction based on the predictions from a set of independent models with different parameters or even with different model structures. Ensemble GNNS have been shown to provide more accurate prediction and reliable estimation than the single models (Bazhenov et al., 2022 Wang et al. 2023 Gawlikowski et al., 2023). Meanwhile, ensemble GNNS offer an intuitive means of expressing predictive uncertainty by assessing the diversity among the predictions of the ensemble members. AU and EU could also be differentiated similarly as in Bayesian GNN methods. Despite their wide applications, most GNN ensemble models follow the deep ensemble framework (Lakshminarayanan et al. 2017) without specific modifications for both graphs and uncertainty quantification purposes. Compared with the two families above, ensemble methods are less used in GNNS mainly due to their high computational cost.
Test-time data augmentation, another type of uncertainty quantification method, has been widely used in other fields, e.g., computer vision (Ayhan & Berens, 2022). It involves augmenting multiple samples for each test sample and applying the model to all samples to compute the distribution of predictions. Then, AU is estimated with the entropy of the model prediction distribution for a test sample and its augmentations, and EU can also be estimated in the same way as Bayesian GNN methods. However, in GNNS, test-time augmentation has only been utilized for other purposes. Jin et al. (2022) first propose to modify the node feature and the graph topology at the test time for better OOD generalization. Similarly, Ju et al. (2024) use test time augmentation to mitigate the bias of GNN towards achieving better performance on high-degree nodes. However, test-time augmentation has not yet been explicitly applied for graph uncertainty quantification and thus, is not included in our primary framework. Nevertheless, its potential adaptation for graph uncertainty quantification warrants exploration. Given its post hoc nature, it requires no additional data and shows better computational efficiency during training compared to ensemble and Bayesian GNNS.
3.4 Evaluating Quantification Models
We discuss the evaluation measures to assess the quality of GNN uncertainty quantification models. As in Figure 2 evaluations are not limited specific type of quantification model but to each targeted uncertainty source. This is because model can quantify multiple sources of uncertainty, and models can only be evaluated regarding specific uncertainty source. Given the challenge of acquiring ground truth uncertainty, various metrics have been proposed, and there is no consensus on a unified metric (Lakshminarayanan et al. 2017 Gawlikowski et al. 2023).
Predictive (Total) uncertainty. As discussed above (Liu et al. 2022a Zhao et al. 2020), maximum softmax prob- ability (referred to as confidence in this paper) and entropy are widely applied to quantify the predictive uncertainty in the classification problems. They are also utilized as uncertainty measures of predictive uncertainty [Smith & Gal (2018). Notably, entropy is often used as measure of aleatoric uncertainty when applied on labeled dataset, e.g.. in decision tree. However, entropy in GNNS is calculated on the predicted probability of each sample. We believe it
5

---

Published in Transactions on Machine Learning Research (11/2024)
Uncertainty Quantification Models ($3.1-3.3)
Uncertainty Sources (S2)
Evaluating Uncertainty Quantification Models (S3.4)
Confidence
Predictive Uncertainty
Direct Estimation"
Predictive Uncartainty
Entropy
Single Deteministic Model (S3.1)
Bayesian-basee based Estimation?
Epistenic Uncertainty
Aleatonic/Data Uncertainty
MWPI
Mutual Information
Frequantst-basee Estimation!
Data
Single Random Parameters ($3.2)'
Model Uncertainty
Distributional Uncertainty
Uncertainty
Variance
Divergence
Ensemble Models (S3.3/5
Conventional Clessification Metrics
Uncertainty
Wang et al.
[002]]
Cai et al. [2017]: Guo et al. [2017]
Hsu al. (2022b)
Xu et 20233
2.
Zhao et al.
(2020)
Stadler et al. (2021) Bazhenov et al.
2023
3.
Kang et al.
2022 Efron (1982]: ; Huang al. [2033a]; Zargarbashi al. 2023
4.
Zhang al.
(2019b)
Hasanzadeh et al. (2020) Rong al. (2019): Cha et al.
2023
Wu et al. 2021
5.
Bazhenov al.
(2022 Wang al. 2023) Gawlikowski
al. (2033
Bridge uncertainty quantification models and evaluation methods by uncertainty sources. The diamond shape represents the separation of uncertainty sources. Quantification models linked any diamond indicate their ability to separate the correspond- ing uncertainty source. We merge "Model Uncertainty" and "Data Uncertainty" in evaluation as they are complementary and share similar evaluation metrics in cases.
Figure 2:
should be considered to represent predictive uncertainty, opposed to aleatoric uncertainty evaluation metrics as in Gawlikowski et al.] (2023). As mentioned in Section 3.1 these two metrics are vulnerable to distribution shifts and need calibration.
In regression problems, the mean width of prediction intervals (MWPI) (Kang et al., 2022 Huang al., 2023a can be used for evaluation. The coverage rate-the portion of ground-truth labels falling into these intervals verified to ensure the validity of this metric. Notably, efficiency is the same notion as MWPI in conformal regression, while in conformal classification, it refers to the average prediction set size under given coverage rate. In some works (Zargarbashi et al., 2023), this metric is accompanied by singleton hit rate. i.c., the prediction accuracy of prediction sets of size one. This joint use of both metrics satisfies the need for both prediction quality and uncertainty quantification. However, MWPI estimates the predictive uncertainty over set of data but not on individual samples.
Model & Aleatoric uncertainty. The model uncertainty is commonly measured through mutual information (MI) to evaluate quantification models. MI is minimal when information in prediction does not increase with additional model knowledge. It is calculated as the difference between the entropy of the expected distribution (predictive uncertainty) and the expected entropy (aleatoric uncertainty) (Malinin & Gales 2018 Zhao et al. 2020). Notably, MI is also referred to as information gain in some papers (Liu et al.) 2022a). For Bayesian and ensemble GNNS, the predictive variance of sampled outputs is another option to interpret model uncertainty (Zhang et al.) 2019a Gal & Ghahramani 2016). Furthermore, employed as one of the optimization objectives in some quantification methods (Liu al, 2020 Zhao et al., 2020), the expected Kullback-Leibler (KL) divergence between approximated distribution and the posterior distribution can also evaluate model uncertainty. Given no distributional uncertainty, model uncertainty equals epistemic uncertainty. In this case, aleatoric uncertainty, namely data uncertainty, can be measured the difference between the total uncertainty and model uncertainty; otherwise, the metric will be no longer meaningful.
Distributional uncertainty. It is believed that quantification of distributional uncertainty will be able to separate in-distribution (ID) and out-of-distribution (OOD) samples Malinin & Gales (2018). popular approach to measure total distributional uncertainty is through classifying test samples. Samples with distributional uncertainty surpassing given threshold are categorized OOD samples, while those below the threshold are considered ID samples. In this, conventional classification metrics, e.g., Receiver Operating Characteristic (ROC) curve and Area Under Receiver

---

Published in Transactions on Machine Learning Research (11/2024)
Single Model with Parameters Being Random Variables
Y
Bayesian-base based Estimation
Efficiency (E) or Robustness (R)?
Model DU?
Ensemble Model
N
Separate AU/EU?
Direct Estimation
N
Individual (1) or Population (P)?
Trequentist-based Estimation
Figure 3: Flowchart illustrating recommended quantification methods for various conditions. Diamond shapes represent conditions, while rectangular shapes indicate the recommended methods.
Operating Curve (AUROC) (Zaao et al. 2020 Song & Wang 2022 Gui et al. 2022), can be applied to measure the distributional uncertainty. However, this evaluation depends on the selection of test samples and threshold.
In conclusion, the effectiveness of existing metrics remains under exploration. As an alternative, many studies di- rectly employ specific downstream tasks for evaluation to obtain reliable and straightforward measures. Nonetheless, depending on demands under different circumstances, we recommend diverse methods quantification methods ac- cording to their properties, shown in Figure 3 First, is crucial identify the specific source uncertainty being targeted. To our knowledge. only Bayesian- based estimation methods explicitly quantify distributional uncertainty. Subsequently, one must consider the necessity of separating aleatoric and epistemic uncertainty. If this separation is deemed necessary, two categories of methods are available: ensemble models, which consist of different member models, and single models with parameters treated as random variables. For computational efficiency, we recommend single models with parameters as random variables. However, for improved prediction performance and robustness across different distributions, ensemble models are preferable. some cases, the separation of aleatoric and epistemic uncertainty does not yield significant benefits. For practitioners seeking highly computationally efficient methods for individual examples (e.g., nodes links), direct estimation is adequate. Conversely, for distribution-fee and statistically guaranteed estimation of the overall test population, Frequentist-based estimation is recommended.
4 Utilizing Uncertainty in GNN Tasks
This section introduces four types of GNN tasks utilizing uncertainty, as diguribJescribes. In addition to determining the type of uncertainty and how it is captured, we also focus on how uncertainty contributes to the task goal.
4.1 Uncertainty-based Node Selection
Node selection in graph learning refers to the process of selecting subset of nodes from a graph that collectively contributes to specific tasks analyses. Graph active learning and self-training two common tasks involving node selection, where a collection of unlabeled data is labeled to improve the performance of the model (e.g., a GNN). Uncertainty is widely used as a criterion for node selection in these tasks.
Active learning. In graph active learning tasks, uncertainty and representativeness (diversity) are prevalent criteria for node selection (Ren et al.] (00TT. Uncertainty often measured by the entropy of the prediction probabili- ties on the nodes. Cai et al. (2017) first propose a graph active learning framework, which uses combination of mecsuuedd uncertainty, information density, and node centrality select nodes. Zhang al. (221a) estimate ensembled uncertainty using the variation of prediction generated by committee models, which is more robust and reliable than entropy single deterministic model. The method selects top k nodes to maximize the effective recep- tion field using the topological information of the graph, excluding nodes that are less uncertain and less informative. Unlike the previous two methods, which select the most uncertain nodes independently, Zhang et al. (20216) consider label propagation and select subset of nodes with maximized uncertainty (entropy) reduction include diversity. Labeled nodes can propagate their label information based on the graph distance and the node feature similarity, and then reduce the uncertainty of adjacent unlabeled nodes. Additionally, in multi-task manner, Chang et al. (0244)
7

---

Published in Transactions on Machine Learning Research (11/2024)
Uncertainty-based Node Selection (S4.1)
Uncertainty-based Abnormality Detection (S4.2)
Active learning
Self-training
OOD
Outlier
Misclassification
train
test
labeled
unlabeled
selected to label
detected abnormality
+/- prediction
Uncertainty-aware GNN Modeling (S4.3)
Uncertainty for Trustworthy GNN (S4.4)
Node-level
Edge-level
Subgraphs/nodes with maximal mutual information have the greatest impact on the results.
Explainability:
+
^
deterministic vector
dropped edges
Graph-level
Neighbors with higher uncertainty have smaller weights for aggregation.
Robustness:
X+
sample
8.B
Figure 4: Illustration of representative usage of uncertainty in GNN tasks. The darker the color, the greater the uncertainty/weight.
estimate the confidence difference between the node classification task and anomaly detection task for node selection in graph active learning. Notably, in most cases, graph active learning methods that select nodes with only uncertainty can hardly outperform the ones with combination of uncertainty and other measures.
To achieve dynamic and adaptive node labeling, reinforcement learning (RL) has been applied to graph active learning. Gao et al. (2018) uses the combination of the measures in Cai et af. (2017) to select nodes, but dynamically adjusts the combination weights based on a multi-armed bandit framework. Instead of measuring nodes independently, Hu et al.] (2020) formulates the active learning problem as sequential decision process on the graph considering the interconnections between nodes. Uncertainty is still measured with entropy but concatenated with other features, e.g., the divergence between node's ' predicted label distribution and its neighbor's, form the state representation of each node. The reward is the model performance on hold-out data updated with a trajectory of selected nodes. However, the RL-based active learning methods are significantly time-consuming to train.
Self-training In graph self-training, i.e., the labeled set with top K confident nodes, quantified through maximal softmax probabilities. Considering that GNN is ineffective in propagating label information under the few-label setting, [Sun al. (2020) iteratively select and label the top K confident nodes. Drawing upon the concept of ensembling to robustly select and label nodes, Yang al.) (2021) employs multiple diverse GNNS. Nodes are selected with confidence surpassing pre-determined threshold and ensuring consistent prediction for labels across all models. Wang et al. (202T) is the first work to point out that the under-confidence of GNNS leads to biased uncertainty estimation, deteriorating the performance of uncertainty-baase self-training node selection. With the calibrated confidence, they improve the performance of the self- self-training method ZZaao layer GNN for uncertainty estimation.
Li al. (2018) propose one of the initial works that expand
introduced by et al. (2018). In consideration of graph structure information, /hho et al. (202T) propose to compute entropy for each node, and add an antropy-aggregaii
Similar graph active learning, recent self- training methods (Liu et al. 2022a Li al. 2023b) consider combining uncertainty with representativeness. but from different perspectives. Liu et al. (002a)) believe the common self- training practice that only selects high-confidene nodes leads to the distribution shift from the original labeled node distribution to the expanded node distribution. Therefore, they follow the common practice that selects high-confidence nodes as pseudo-labels but decreases the weight of the nodes with low information gain in the training loss. Interest- ingly, the dropout technique employed to compute information gain is often interpreted as the model uncertainty, as introduced Section Similarly, Li al. (2023b) also rely on the fact that the high-confidence nodes convey over- lapping information, causing information redundancy in pseudo-labeled nodes. The representativeness of node is
8

---

Published in Transactions on Machine Learning Research (11/2024)
computed with the mutual information between the node and its neighborhood aggregation. Pseudo-labeled nodes are selected based on the representativeness and confidence scores exceeding predefined thresholds, with less confident nodes assigned lower weights in the gradient descent process. Further, WWang et al. (2024) reformulates the goal of selecting pseudo-labeled nodes as to reduce the uncertainty over all unlabeled nodes, and consider node selection in combinatorial manner. This method can optimize the student model with more global approach and reduces the correlation of selected nodes, improving representativeness and effectiveness of node selection in graph self-training.
Quantifying uncertainty accurately during the iteration process remains significant challenge in both graph active learning and self-training tasks. One key issue is that the distribution of newly added pseudo-labeled data often di- verges from the original training data distribution, making uncertainty estimates derived from the existing training data uncalibrated and noisy. In self-training, where teacher models frequently make inaccurate predictions, pseudo-labels can further introduce noise into uncertainty estimation. While limiting predictions to labeled data can reduce noise in some scenarios, it fails to capture the evolving uncertainty of updated models throughout the self-training iterations. Graph calibration models, as discussed in Section 3.1 offer potential solution to this challenge by recalibrating un- certainty estimates. However, these models require sufficient amount of labeled calibration data and typically involve longer training times. Moreover, in graph active learning, uncertainty serves primarily for node selection. By con- trast, in self-training, it also represents the degree of noise in pseudo-labels. Unfortunately, inaccurate pseudo-labels can undermine the effective use of uncertainty, as even predictions with low uncertainty may contain incorrect labels, potentially leading to model misdirection during retraining.
In summary, uncertainty plays a crucial role in node selection tasks. Most of the existing methods rely on single deterministic models for estimating uncertainty directly, favoring computational efficiency in iterative training. For non-i.i.d. graph structures, node uncertainty is calculated alongside the influence of neighboring nodes and is of- ten combined with other performance-enhancingg metrics. Despite its widespread application, researchers should be cautious when estimating and applying uncertainty, particularly in graph self- self-training scenarios.
4.2 Uncertainty-based Abnormality Detection
Abnormality detection is a pivotal task in graph machine learning for safety and security. In this section, we define general abnormality detection as the task that identifies irregular patterns that deviate from the established norms. Uncertainty can serve as both a metric of abnormality and a tool for abnormality detection. Depending on the specific definition of abnormality, the application of uncertainty in abnormality detection can be systematically categorized into three distinet types: ouito--distiibuttin detection, outlier detection, and misclassification detection.
OOD detection. To begin with, out-of-distribbtion (OOD) detection focuses on identifying instances that diverge from the training data distribution fin-disribbttion. OOD detection involves identifying samples from unknown classes and preventing models from making wrong decisions with overconfidence. In some literature (Wu et al., 2020a). OOD detection is integrated with the task of classification for in-distribution data and formulated as an open-world clas- sification. Open- world classifiers recognize predefined classes seen during training and identify instances from new classes. For OOD detection, Wu et al. (2020a) maximize an entropy-based uncertainty loss for unlabeled nodes during training, such that the instances of unseen classes have a low and balanced predictive probability over the already seen classes. During inference, if the maximal class probability of instance is lower than a predefined threshold, the instance is regarded as OOD. In addition, Zhao et al. (2020) propose to quantify various types of uncertainty with graph-based Dirichlet distribution, and point out that vacuity uncertainty, derived from a lack of evidence or knowl- edge, is the most effective in OOD detection among other uncertainties. Furthermore, considering the non-i.i.d. nature of graph data, [taaler et al. 202T) perform Bayesian posterior updates for predictions on interdependent nodes through diffusing Dirichlet parameters. Epistemic uncertainty without network effects is shown effective in detecting random OOD nodes with perturbed features, while epistemic uncertainty with network effects performs better in identifying nodes from the left-out class not present in the training data.
data,[Stadler
Outlier detection. Apart from OOD detection, outlier detection (also known as anomaly detection) is another prevail- ing task that effectively leverages uncertainty in graph learning. Outlier detection refers to the identification of data that exhibit significantly different behaviors or characteristics compared to the majority of the graph. Different from the OOD data, outliers can also exist in the training data. [Ray et al. (202T) directly estimate the predictive uncertainty with deviation from the distribution for interpretable anomalous behavior detection on multivariate time series. Notwith- standing conventional uncertainty quantification methods, Liu et al. (2022c) interpret the graph anomaly scores using

---

Published in Transactions on Machine Learning Research (11/2024)
Bayesian approach (Perini al. 2020). which converts the anomaly score into the confidence level of the GNN in its outlier prediction for each example. The key idea of this conversion is to align the likelihood of an example being an outlier with its position in anomaly score distribution.
Misclassification defection. Moreover, uncertainty can also be utilized to identify instances with incorrect model pre- diction, known as misclassification detection. (Zhao et al. (2020) attempt various types of uncertainty, and concludes that dissonance (i.e., uncertainty due conflicting evidence) is the most effective in misclassification detection. Be- sides detecting OOD nodes, [Stadler al. (202T) also utilize their proposed method to detect misclassified nodes, In most experiments, alcatoric uncertainty achieved the best performance, rather than epistemie uncertainty in OOD detection. This observation supports the necessity to separate and utilize task-specific sources of uncertainty.
In summary, recent studies emphasize the importance of uncertainty in graph-based anomaly detection, although there is inconsistency in the type of uncertainty utilized for the same purpose. For instance, both predictive uncertainty (Wul et al. 2020a), epistemic uncertainty (Stadler et al., (20TT), and vacuity uncertainty (Zhao et al. (002) have been applied to detect OOD nodes. There is lack of a systematic framework for selecting quantification methods and applying estimated uncertainty in abnormality detection. Establishing such framework would be advantageous for both the theoretical exploration and the practical application of abnormality detection.
4.3
Uncertainty-aware GNN Modeling
Graphs serve as powerful representations of complex relationships and structures, but their structural uncertainty poses challenges for effective learning and inference tasks. Fortunately, GNN can improve its prediction performance through uncertaint--awareneee Based on addressing uncertainty from different components of graph structure, related works can be divided into three categories: (1) node-level, (2) edge-level, and (3) graph-level.
Node-level. In graphs, nodes often exhibit confficting or contradictory characteristies, such as belonging differ- ent communities revealing contradictory underlying patterns (Bojchevski & Günnemann 2017). This discrepancy should be reflected in the uncertainty of node embeddings. highlighting the need to account for uncertainty at the node-level in GNN structures. Hajiramezanali et al.] (2019) incorporate stochastic latent variables by combining a Graph Recurrent Neural Network (GRNN) with a Variational Graph Autoencoder (VGAF) (Kipf & Welling, 2016). The proposed variational GRNN is designed to capture the temporal dependencies in dynamic graphs. Moreover, it aims to represent each node by modeling its distribution in the latent space rather than assigning it a deterministic vector in low-dimensional space, thus enhancing its ability to represent the uncertainty associated with node la- tent representations. Vashishth et al. (019) propose ConfGCN, which introduces confidence (inversely proportional to uncertainty) estimation for the label scores nodes to enhance label predictions. More specifically, ConfGCN assumes a fixed uncertainty for input labels and defines an influence score of each node as a parameter that can be optimized jointly with the network parameters through back-propagatie the co-variance matrix-based symmetric Mahalanobis distance between two nodes in the graph. Sun et al. (202T) gen- erate stochastic representations using a hyperbolic VGAE, combining temporal GNN to model graph dynamics and its uncertainty in hyperbolic space. Xu et al. (2022) introduce a Bayesian uncertainty propagation method and embeds GNNS in Bayesian modeling framework. This approach uses Bayesian confidence of predictive probability based message uncertainty to quantify predictive uncertainty in node classification. The proposed uncertainty-orient oriented loss penalizes the predictions with high uncertainty during the learning process, enabling GNNS to improve prediction reli- ability and OOD detection ability. Liu et al. (2022e) introduce the concept of a mixture of homophily and heterophily at the node-level, revealing that GNNS may exhibit relatively high epistemic uncertainty for heterophilous nodes. To address this issue, the paper proposes an Uncertainty-aware Debiasing framework, which estimates uncertainty in Bayesian GNN output to identify heterophilous nodes and then trains debiased GNN by pruning biased parameters and retraining the pruned parameters on nodes with high uncertainty.
The influence score here is the inverse of
Edge-level. To better consider the inter-dependencies in the graph structure, some methods also explore uncertainty beyond the node-level. While Veličković et (2018) has applied similar dropout technique on edge attentions, Rong al. (2019) first formally presented the formulation of DropEdgee It randomly removes a specified number of edges from the graph by drawing independent Bernoulli random variables (with a constant during each training iteration. Rong et al. (2019) theoretically and empirically show that DropEdge, as a data augmenter and a message-passine reducer, can alleviates the problems of over-fitting and over-smoothing. [ssu et al. (202aa) propose two edgewise metrics for graph uncertainty estimation: (1) edgewise expected calibration error (ECH) is designed to estimate the
10

---

Published in Transactions on Machine Learning Research (11/2024)
general quality of the predicted edge marginals, utilizing graph structure and considering confidence calibration of edgewise marginals; (2) agree/disagree ECEs extend the idea of edgewise ECE by distinguishing homophilous and heterophilous edges.
Graph-level. Some works address uncertainty in the overall structure or properties of the entire graph. Zhang et al. (2019h) is the first work to develop the Bayesian neural network framework tailored for graphs, treating the observed graph as a realization from parametric family of random graphs. The joint posterior distribution of the random graph parameters and the node labels are then targeted for inference. However, besides the considerable computation cost, Bayesian GNN relies on the selection of the random graph model, which may vary across different problems and datasets. Hasanzadeh et al.] (2020) introduce Graph DropConnect (GDC), general stochastic regularization technique for GNNS through adaptive connection sampling, which yields a mathematically equivalent approximation of Bayesian GNNS training. This unified framework mitigates over-fitting and over-smoothing issues of deep GNNs, while also prompting uncertainty-awar learning. While both Bayesian GNN and GDC are aware of graph-level uncertainty, the current implementation of posterior inference in Bayesian GNN solely relies on the graph topology and neglects the node features. In contrast, GDC involves a free parameter that allows adjustment of the binary mask for edges, nodes, and channels, thereby facilitating flexible connection sampling and addressing uncertainty from various levels of graph structure. Therefore, GDC can be viewed as an extension and generalization of DropEdge, which only focuses on edge-level. Moreover, unlike stochastic regularization methods relying on fixed sampling rates or manual hyperparameter tuning (e.g., Dro,Edge), GDC enables joint training of drop rate and GNN parameters. Liu et al. (2200) propose an Uncertainty-aware Graph Gaussian Process (UaGGP) approach to address uncertainty issues in graph structures, especially when edges connect nodes with different labels, leading to predictive uncertainty. The work employs graph structural information for the feature aggregation and the Laplacian graph regularization. Leveraging the randomness modeled in the Gaussian Process, UaGGP introduces graph Laplacian regularization based Gaussian Process inferences and symmetric Mahalanobis distance to tackle structural uncertainty.
To address the uncertainty in graph structure, many studies leverage Bayesian inference to capture uncertainty and estimate model parameters. Some approaches can handle over-smoothing and over-fitting phenomena in GNN simul- taneously. In addition, we find these often hold the assumption that edges connecting nodes with different labels would result in misleading neighbors and causing uncertainty in the predictions. Although this assumption is shown valid and effective, we believe it is not the only factor causing uncertainty in graph structure, and this hypothesis is also not suitable for heterogeneous graphs. It would be interesting to design methods that treat structural uncertainty from other geometric information from the graph, e.g., nodes connecting to different communities (Huang et al., 2023b). Furthermore, while existing works primarily aim to develop uncertainty-awart GNNS to enhance prediction perfor- mance, a few explicitly (1) evaluate the reduction of uncertainty in GNNS compared to prior network structures, and (2) validate as well as explain how the reduction of uncertainty contributes to improving prediction accuracy. Finally, the methods in this domain rarely compare against each other as baselines, lacking a universal benchmark.
4.4 Uncertainty for Trustworthy GNN
Trustworthy GNNS aims to provide explainability of decisions made by GNNS and be robust to noise and adversarial attacks to ensure the integrity and security of the model. Uncertainty can serve as a tool to build algorithms for the interpretation of GNNS decisions. Additionally, considering uncertainty during the aggregation mechanisms in GNNS can enhance robustness. Thus, uncertainty quantification can be an effective approach to achieving trustworthy GNNS.
Explainability. Uncertainty quantification provides insights for the reliability and confidence of GNN decisions. Specifically, mutual information explains the relationship between the GNNS predictions and the components that impact GNNS predictions. |Ying et al. (2019) propose GNNEXPLAINER which identifies a subgraph and/or node fea- tures that maximize mutual information with the prediction, to explain which components of the graph have the most impact the prediction results. Mutual information is nonparametric and does not require prior knowledge and assumptions on models. Thus, it is model-agnostic and suitable for providing interpretable explanations for any GNN- based models. Besides, uncertainty quantification can also be used to explain predictions of automated GNNS. Yang et al. 2202)) propose HyperU-GCN, which combines hyperparameter optimization with uncertainty quantification, to explain the selection of hyperparameters. It quantifies hyperparameter uncertainty as the mutual information between the model prediction and hyperparameters using probabilistic hypernetwork. HyperU-GCN employs a concept akin to Bayesian GNNS for computing this mutual information, which marginalizes hyperparameters rather than model parameters. Unlike GNN AINER, HyperU-GCN requires model hyperparameter priors (e.g. normal distribution).
11

---

Published in Transactions on Machine Learning Research (11/2024)
yet leveraging Bayesian GNNS enables it to better calibrate model predictions. There are many other methods to inter- pret GNNS besides using uncertainty, and we refer readers to Kakkad et al. (2023) for comprehensive overview. For example, GraphLIME (Huang et al. 2202) samples neighbors and finds the most representative features as GNN local explanations based on an Automated Concept-based Explanation approach (Ghorbani et al. 2019), which maps node representations to the concept space, to extract important concepts as global GNN explanations.
Independence Criterion Lasso; GCExplainer (Magister et al. 2021) applies
Robustness. GNNS are vulnerable to adversarial attacks, i.e., small perturbations in graph structures and node at- tributes could lead to performance degradation. Incorporating uncertainty in graph learning empowers GNNS with robustness against such attacks. Zhhu et al. (2019) propose Robust GCN (RGCN), which adopts Gaussian distributions as the hidden representations of nodes instead of certain vectors. By introducing Gaussian distributions, RGCN can automatically absorb the effects of abnormal adversarial changes and enhance its robustness. Besides, RGCN utilizes a pariance-based attention mechanism, which assigns different weights to node neighborhoods according to their vari- ances to reduce the propagated adversarial effects from neighbors. Though RGCN can model epistemic uncertainty in GNNS by Gaussian distribution variances, it does not consider aleatoric uncertainty and uncertainty from graph topology. Thus, Feng al. (2021) propose quantifying uncertainties from graph topology features, measuring both epistemic and aleatoric (i.e., data) uncertainties. This paper utilizes the Bayesian GNN to estimate epistemic uncer- tainty and node diversity, which is intrinsic to the graph topology and defined as the number of different labels in the node's k-hop neighbors, to estimate aleatoric uncertainty. Another disadvantage of RGCN is that it relies on prior distributions and the uncertainties are not well-calibrated. Therefore, Shanthamallu et al. (2021) propose UM-GNN, which utilizes Bayesian GNNS with Monte Carlo dropout estimate epistemic uncertainty of a standard GNN and assigns low uncertainty nodes with high attention. UM-GNN also utilizes an uncertainty- matthiin strategy align prediction results between the standard GNN and structure-free surrogate model to avoid simple prior assumptions structural uncertainties. Besides, UM-GNN uses a label smoothing regularization to calibrate uncertainties. (Zhang] et al. (2021c) propose a multi-view confidence-calibraiee GNN encoder (MCCG) module, which utilizes Dirichlet dis- tribution to calibrate the prediction confidence for noisy or adversarial samples and utilizes the estimated uncertainty scores to control information propagation. Although these defense methods apply different quantification methods for different sources of uncertainty, they use the same key idea that increasing the weights of low-uncertainty nodes reduces the impact of the adversarial attack. Besides, although it not explicitly stated that uncertainty quantification methods were used, some works have employed uncertainty-relle GNNS. For example, (Bojchevsi & Günnemann (2019) uses the minimum worst-case margin between the predicted or ground-truth node label and other labels under perturbations of graph structures to verify whether the node is robust, By intercepting messages from perturbed Modes,,Scholtee et al. (2022) uses whether the perturbed prediction is consis- tent with its neighbors regarding the majority vote to certify the robustness of GNNS. Both works perturb the original input graphs and measure the robustness with the variability of predictions under perturbations. This idea is similar to Bayesian GNNS, where uncertainty is measured with the variance of prediction with randomized GNN parameters. In this way, robust GNNS are expected preserve consistent and certain predictions with noisy data. Sun et al. (0222) provides more GNNS robustness studies.
approaches to verify the certifiable robustness of
In conclusion, uncertainty can enhance the trustworthiness of GNNS from both explainability and robustness, with a consensus on how to utilize uncertainty. Other interesting directions are also worth exploring. For example, instead of increasing the weight of certain nodes, the robustness of GNN may also be improved by training with perturbations obtained by maximizing the model's estimated uncertainty (Pagliardini et al., [022].
5 Uncertainty in GNNS: Real-world Applications
Traffic. GNNS have been widely used to model network traffic, especially traffic demand forecasting. Uncertainty arises in traffic systems both spatially and temporally, e.g., travel demand may increase on game days around the stadiums. Wu et al. (202I) compare six different Bayesian and brsquentist-based uncertainty quantification methods for road network traffic prediction problems, regarding computational efficiency, asymptotic consistency, etc. ZZuang et al. (2022) specifically focus on sparse travel demand and proposes STZINB-GNN, where a spatial-temporal em- bedding is designed with an additional sparsity parameter to learn the likelihood of inputs being zero. The probability layer in the embedding allows for prediction with a level of confidence and thus, quantifying the demand uncertainty. Wang et al.) (2023) propos a framework of probabilistic GNNS, Prob- GNN, to quantify spatiotemporal uncertainty of traffic demand. Besides different GNNS, different probabilistic distribution assumptions with different properties
12

---

Published in Transactions on Machine Learning Research (11/2024)
are compared, such Laplace and Gaussian distribution, well as single and ensembled Gaussian models. Prob- GNN can not only quantify spatiotemporal uncertainty but also generalize well under significant system disruption and identify abnormally large uncertainty. The experiment results show that the GNN performance is more impacted by probabilistic distribution assumptions than the selection of GNNS, underscoring the importance of incorporating randomness and uncertainty into the traffic prediction model. To quantify both aleatoric and epistemic spatiotemporal uncertainty, Qian et al. (2023) propose DeepSTUQ. which uses Bayesian dropout for pre-training and ensembling for re-training, and then calibrates the trained model with temperature scaling. In traffic applications, models are typically evaluated with point estimate error along with the mean prediction interval width (MPIW).
Drug discovery is a graph-level problem of identifying and developing new molecules with desired prop- erties, where each molecule is modeled as a graph. Zhang et al. (2019a) compare different Bayesian-based methods for accurate and reliable molccule property predictions in drug discovery. They reveal a few key aspects: (1) both epistemic and aleatoric uncertainty are correlated with error and improve the accuracy of selective prediction, thus, total uncertainty should be utilized for uncertainty estimation; (2) Bayesian uncertainty estimation could overcome the bias of the synthetic dataset by informing the user about the level of uncertainty; (3) the estimated uncertainty is also applied to guide active learning for drug discovery, showing better performance with initially diverse labeled classes. Similarly, Ryu et al. (2019) apply Bayesian GNN with Monte Carlo dropout to estimate uncertainty in activity and toxicity classification problems. Additionally, they use aleatoric uncertainty to evaluate the quality of the existing and synthetic datasets. To reduce overconfident mispredictions for drug discovery under distributional shift, Han et al. (2021) introduce Tox, a novel real-world OOD data benchmark with molecules annotated by Tanimoto graph distance and proposes distance awareness distance-awareness classifier, GNN-GP. Follow-up studies (Aouichaoui et al.] 2022 Kwon et al. 2022) also derive similar conclusions. In molecular force fields, GNNS have also shown promising performance for quantum mechanical calculations accelerate molecular dynamics trajectory simulations. Besides common con- cerns about prediction accuracy, uncertainty awareness, and computational costs. WWollschääger et al. (2023) propose meyysic--iffomme desiderata, including symmetry, energy conservation, and locality. In addition to evaluating previous uncertainty quantification methods, they propose Localized SVGP-DKL, which combines the Bayesian GNN with the localized neural kernel to satisfy the physics-related criteria.
Molecules.
Others. To segment images of complex geometry or topology, Gupta et al. (2023) employ GNNS to jointly reason about the structures (nodes) and capture the high-order spatial interactions (edges). A probabilistic model provides structure- wise uncertainty estimates, which could identify highly uncertain structures for human verification. In computational social systems. Zha et al. (2023) apply an uncertainty-aware graph encoder (UnGE) to represent job titles as Gaussian embeddings and capture uncertainties in real-world career mobility. In fault diagnosis, a Bayesian hierarchical GNN is proposed by Chen et al. (2023), where the total uncertainty is measured by the dropout. Using uncertainty as a weight, the loss encourages the feature of highly uncertain sample to be temporally consistent for robust feature learning. Uncertainty in GNN is also widely applied in diverse domains, including energy (Li el al. 2023a), robotics (Gao et al. 2023), and recommendation systems (Zhao al. 2023).
6 Future directions
Identifying fine-grained graph uncertainty. While current research on graph data has asserted their ability to differ- entiate between various types and sources of uncertainty (Section 2). only a few efforts have been made to identify and quantify uncertainty tailored specifically for graph components. For example, (Bojchevski & Günnemann 2017 7 Liu et al. 2022c) have assumed that heterophily, the conflict between two connected nodes, is correlated with uncertainty in node classification. These attempts demonstrate that fine-grained graph uncertainty is essential for downstream tasks. Therefore, it is promising to develop other unexplored fine-grained uncertainties that contribute such spe- cific tasks. For instance, researchers might seek to identify specific types of graph distribution shifts, such as shifts in graph node features, labels, and graph structure. Decomposing distributional uncertainty at a more granular level could aid in distinguishing and leveraging the corresponding shifts, thereby enhancing OOD detection and generaliza- tion. Furthermore, different forms of finer-grained graph uncertainty should be comparable in scale. By comparing their corresponding uncertainty measures, we can determine whether the distributional uncertainty arising from node feature or graph topology, or the GNN modeling is dominant. This contributes to uncertainty estimation with improved explainability by indicating how each component in graph data, GNN modeling, and inference process contributes to the final GNN predictive uncertainty.
13

---

Published in Transactions on Machine Learning Research (11/2024)
Constructing ground-truth datasets and unified evaluation metrics. The critical unresolved issue of the lack of ground-truth datasets and metries for evaluation, as discussed in Section 3.4 persists. While aleatoric and distribu- tional uncertainty can be artificially introduced into synthetic graph data with predefined underlying distributions or generating processes, synthetic data has difficulty in simulating complex real-world scenarios, with diverse and disen- tangled sources of uncertainty. Besides, is also challenging to obtain ground-truth values for model uncertainty, as it depends on the selection of models. On the other hand, though humans could be involved in evaluating ground-truth aleatoric uncertainty for real-world data, biases may still arise due to varying levels of human cognitive abilities. Ad- ditionally, the lack of unified evaluation metrics for different tasks, such as classification regression tasks, further complicates the evaluation process. Thus, uncertainty across different tasks is not directly comparable.
Currently, a feasible alternative is to assess whether uncertainty estimation enhances well-defined metrics for the final task performance rather than directly evaluating the quality of uncertainty estimation. However, there is a gap in understanding whether performance enhancements are solely due to the selection of quantification methods or if they ideally result from an appropriate match between quantification methods and corresponding uncertainty types, where the uncertainty type itself aids the task. Bridging this gap still requires further efforts.
Quantifying task-oriented uncertainty. The existing literature lack systematic investigation aimed at identifying the most effective uncertainty method for downstream tasks introduced in Section 4 This is partly attributable to the observation that researchers in a specific domain tend to follow a specific method to quantify uncertainty. For instance, in graph active learning, entropy is frequently used for uncertainty estimation without additional elucidation. It remains unclear whether alternative uncertainty measures, such as mutual information, either independently or in combination with other selection criteria, would yield superior performance. Another interesting direction is whether the separation of aleatoric and epistemic uncertainty is necessary. For instance, in other active learning tasks, epistemic uncertainty measures generally outperform total uncertainty ones, while aleatoric uncertainty generally excels in failure detection (Kahl et al.) 2024). However, in graph active learning and outlier detection, the common measures capture predictive uncertainty instead of separating it. Therefore, there is need for systematic validation of various uncertainty types, quantification methods, and evaluation techniques across a wide range of pertinent downstream tasks.
Designing better methods for real-world applications. In Section 3 we have introduced multiple categories of uncertainty quantification methods and showed their strengths and weaknesses. In real-world applications, several aspects need to be taken into primary consideration. First of all, whether methods effectively capture specific sources and types of uncertainty that are relevant to particular types of tasks. For example, Dirichlet-based methods directly model distributional uncertainty, thus showing superior performance over other methods in graph OOD de- tection. Secondly, computational efficiency and difficulty of application to existing prediction frameworks are also of vital importance. For instance, though ensemble models outperform most other methods in both model prediction and uncertainty estimation, they are rarely applied to real-world problems due to their high computational costs. One po- tential direction is to explore graph ensemble distillation (Zhang et al.) 2020) as a cost-efficient alternative, which uses smaller GNNS trained on sub-problems and teaches one student GNN to handle OOD and estimate uncertainty (Hinton et al., 2015). Lastly, one should explore whether the proposed methods
consistently achieve reliable performance across diverse settings. For example, the maximal softmax probability is widely applied in real-world problems due to time efficiency but suffers from under-confidence and is subject to the effect of distributional shifts. In conclusion, it is an exciting direction to develop more efficient, casy-to-apply, robust graph uncertainty quantification methods that can identify diverse fine-grained sources and types of uncertainty.
7 Conclusions
In this paper, we have categorized the existing methods into a novel schema and highlighted the importance of identi- fying, quantifying, and utilizing uncertainty in GNNS for various downstream tasks. Specifically, we have emphasized the need to identify fine-grained uncertainty, especially graph-related uncertainty, and construct ground-truth datasets and unified evaluation metrics. Being the first survey to systematically review GNN uncertainty, we call for the de- velopment of more efficient, easy-to-apply, and robust uncertainty quantification methods, along with systematic investigation and benchmark into existing methods on popular downstream tasks.
14

---

Published in Transactions on Machine Learning Research (11/2024)
Acknowledgments
This work is supported in part by NSF under grants III-2106758, and POSE-2346158.
References
Moloud Abdar, Farhad Pourpanah, Sadiq Hussain, Dana Rezazadegan, Li Liu, Mohammad Ghavamzadeh, Paul Fieguth, Xiaochun Cao, Abbas Khosravi, U Rajendra Acharya, et al. A review of uncertainty quantification in deep learning: Techniques, applications and challenges. Information fusion, 76:243-297 2021.
Adem RN Aouichaoui, Seyed Soheil Mansouri, Jens Abildskov, and Gürkan Sin. Uncertainty estimation in deep learning-based property models: Graph neural networks applied to the critical properties. AIChE Journal, 68(6); e17696, 2022.
Murat Seckin Ayhan and Philipp Berens.
Test-time data augmentation for estimation of heteroscedastic aleatoric uncertainty in deep neural networks. In Medical Imaging with Deep Learning, 2022.
Albin Bäåw. Reliable graph predictions: Conformal prediction for graph neural networks, 2022.
Rina Foygel Barber, Emmanuel J Candes, Aaditya Ramdas, and Ryan Tibshirani. Conformal prediction beyond exchangeability. The Annals of Statistics, 51(2):116-84 2023.
Gleb Bazhenov, Sergei Ivanov, Maxim Panov, Alexey Zaytsev, and Evgeny Burnaev, Towards ood detection in graph classification from uncertainty estimation perspective. arXiv preprint (XXi::200.1169)) 2022.
Gleb Bazhenov, Denis Kuznedelev, Andrey Malinin, Artem Babenko, and Liudmila Prokhorenkova. Revisiting un- certainty estimation for node classification: New benchmark and insights, 2023. URL https://opennevieew.ccc nee// DB33m
Aleksandar Bojchevski and Stephan Günnemann. Deep gaussian embedding of graphs: Unsupervised inductive learn ing via ranking. arXiv preprint arXiv: 1707.0387, 2017.
Aleksandar Bojchevski and Stephan Günnemann. Certifiable robustness to graph perturbations. Advances in Neural Information Processing Systems, 32, 2019.
Hongyun Cai, Vincent W Zheng, and Kevin Chen-Chuan Chang. Active learning for graph embedding. arXiv preprint arXiv:1705.05085 2017.
Scohyeon Cha, Honggu Kang, and Joonhyuk Kang. On the temperature of bayesian graph neural networks for con- formal prediction. In Advances in Neural Information Processing Systems 2023 Workshop: New Frontiers in Graph Learning, 2023.
Wenjing Chang, Kay Liu, Kaize Ding, Philip S Yu, and Jianjun Yu. Multitask active learning for graph anomaly detection. arXiv preprint arXiv:2401.13210 2024.
Dongyue Chen, Zongxia Xie, Ruonan Liu, Wenlong Yu, Qinghua Hu, Xianling Li, and Steven X Ding. Bayesian hierarchical graph neural networks with uncertainty feedback for trustworthy fault diagnosis of industrial processes. IEEE Transactions on Neural Networks and Learning Systems, 2023.
Jase Clarkson. Distribution free prediction sets for node classification. International Conference on Machine Learning, pp. 6268-6278, PMLR, 2023.
Bradley Efron. The jackknife, the bootstrap and other resampling plans. SIAM, 1982.
Bat-Sheva Einbinder, Yaniv Romano, Matteo Sesia, and Yanfei Zhou. Training uncertainty-aware classifiers with conformalized deep learning, Advances in Neural Information Processing Systems, 35:22380-22395, 2022.
Boyuan Feng, Yuke Wang, and Yufei Ding. Uag: Uncertainty-awan attention graph neural network for defending adversarial attacks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 7404-7412, 2021.
15

---

Published in Transactions on Machine Learning Research (11/2024)
Yarin Gal and Zoubin Ghahramani. Dropout as a bayesian approximation: Representing model uncertainty in deep learning. In international conference on machine learning, pp. 1050-1059. PMLR, 2016.
Li Gao, Hong Yang, Chuan Zhou, Jia Wu, Shirui Pan, and Yue Hu. Active discriminative network representation learning. In ICAI International Joint Conference on Artificial Intelligence, 2018.
Peng Gao, Qingzhao Zhu, and Hao Zhang. Uncertainty-awant correspondence identification for collaborative percep- tion. Aulonomous Robots, pp. 1-14, 2023.
Jakob Gawlikowski, Cedrique Rovile Njieutcheu Tassi, Mohsin Ali, Jongseok Lee, Matthias Humt, Jianxiang Feng. Anna Kruspe, Rudolph Triebel, Peter Jung, Ribana Roscher, et al. A survey of uncertainty in deep neural networks. Artificial Intelligence Review, pp. 1-77, 2023.
Amirata Ghorbani, James Wexler, James Y Zou, and Been Kim. Towards automatic concept-based explanations. Advances in neural information processing systems, 32, 2019.
Shurui Gui, Xiner Li, Limei Wang, and Shuiwang Ji. Good: A graph out-of-distribution benchmark. Advances in Neural Information Processing Systems, 35:2059-2073, 2022.
Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger. On calibration of modern neural networks. In Interna- tional conference machine learning, pp- 1321-1330. PMLR, 2017.
Saumya Gupta, Yikai Zhang, Xiaoling Hu, Prateek Prasanna, and Chao Chen. Topology-aware uncertainty for image segmentation. In Thirty-seventh Conference on Neural Information Processing Systems, 2023. URL
Ehsan Hajiramezanali, Arman Hasanzadeh, Krishna Narayanan, Nick Duffield, Mingyuan Zhou, and Xiaoning Qian. Variational graph recurrent neural networks. Advances in neural information processing systems, 32, 2019.
Kehang Han, Balaji Lakshminarayanan, and Jeremiah Zhe Liu. Reliable graph neural networks for drug discovery under distributional shift. NeurlPS 202/ Workshop on Distribution Shifts: Connecting Methods and Applications, 2021.
Arman Hasanzadeh, Ehsan Hajiramezanali, Shahin Boluki, Mingyuan Zhou, Nick Duffield, Krishna Narayanan, and Xiaoning Qian. Bayesian graph neural networks with adaptive connection sampling. In International conference on machine learning, pp. 4104, 2020.
Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge in a neural network. stat, 1050:9, 2015.
Hans Hao-Hsun Hsu, Yuesong Shen, and Daniel Cremers. A graph is more than its nodes: Towards structured uncertainty-awerr aware learning on graphs. Advances in Neural Information Processing Systems 2023 Workshop: New Frontiers in Graph Learning. 2022a.
Hans Hao-Hsun Hsu, Yuesong Shen, Christian Tomani, and Daniel Cremers. What makes graph neural networks miscalibrated? Advances Neural Information Processing Systems, 35:13775-- 2022b.
Shengding Hu, Zheng Xiong, Meng Qu, Xingdi Yuan, Marc-Alexandre Côté. Zhiyuan Liu, and Jian Tang. Graph policy network for transferable active learning on graphs. Advances in Neural Information Processing Systems, 33: 10174-10185, 2020.
Kexin Huang, Ying Jin, Emmanuel Candes, and Jure Leskovec. Uncertainty quantification over graph with confor- malized graph neural networks, Advances in Neural Information Processing Systems, 2023a.
Qiang Huang, Makoto Yamada, Yuan Tian, Dinesh Singh, and Yi Chang. Graphlime: Local interpretable model explanations for graph neural networks. IEEE Transactions on Knowledge and Data Engineering, 2022.
Yihong Huang, Liping Wang, Fan Zhang, and Xuemin Lin. Unsupervised graph outlier detection: Problem revisit, new insight, and superior method. In 2023 IEEE 39th International Conference on Data Engineering (ICDE), pp. 2565-2578. IEFE, 2023b.
16

---

Published in Transactions on Machine Learning Research (11/2024)
Eyke Hüllermeier and Willem Waegeman. Aleatoric and epistemic uncertainty in machine learning: An introduction to concepts and methods. Machine Learning, 110:457-506, 2021.
Wei Jin, Tong Zhao, Jiayuan Ding, Yozen Liu, Jiliang Tang, and Neil Shah. Empowering graph representation learning with test-time graph transformation. In The Eleventh International Conference on Learning Representations, 2022.
Mingxuan Ju, Tong Zhao, Wenhao Yu, Neil Shah, and Yanfang Ye. Graphpatcher: Mitigating degree bias for graph neural networks via test-time augmentation. Advances in Neural Information Processing Systems, 36, 2024.
Kim-Celine Kahl, Carsten T Lüth, Maximilian Zenk, Klaus Maier-Hein, and Paul F Jaeger. Values: A framework for systematic validation of uncertainty estimation in semantic segmentation. International Conference Learning Reprexentations, 2024.
Jaykumar Kakkad, Jaspal Jannu, Kartik Sharma, Charu Aggarwal, and Sourav Medya. survey on explainability of graph neural networks. Bulletin of the IEEE Computer Society Technical Committee on Data Engineering, 2023.
Jian Kang, Qinghai Zhou, and Hanghang Tong. Jurygen: quantifying jackknife uncertainty on graph convolutional networks. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 742-752, 2022.
Thomas N Kipf and Max Welling. Variational graph auto-encoders. arXiv preprint arXiv:1611.07300 2016.
Youngchun Kwon, Dongseon Lee, Youn-Suk Choi, and Scokho Kang. Uncertainty-aware prediction of chemical reaction yields with graph neural networks. Journal of Cheminformutics, 14:1-10, 2022.
Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and scalable predictive uncertainty esti- mation using deep ensembles. Advances in neural information processing systems, 30, 2017.
Jinxing Li, Tianyuan Liu, Guangya Zhu, Yunzhu Li, and Yonghui Xie. Uncertainty quantification and aerodynamic robust optimization of turbomachinery based graph learning methods. Energy, 273:127289, 2023a.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018.
Yayong Li, Jie Yin, and Ling Chen. Informative pseudo-labeling for graph neural networks with few labels. Data Mining and Knowledge Discovery, pp. 228-254-24 2023b.
Hongrui Liu, Binbin Hu, Xiao Wang, Chuan Shi, Zhiqiang Zhang, and Jun Zhou. Confidence may cheat: Self-training on graph neural networks under distribution shift. In Proceedings of the ACM Web Conference, 2022a.
Kay Liu, Yingtong Dou, Yue Zhao, Xueying Ding, Xiyang Hu, Ruitong Zhang, Kaize Ding, Canyu Chen, Hao Peng, Kai Shu, et al. Bond: Benchmarking unsupervised outlier node detection on static attributed graphs. Advances in Neural Information Processing Systems, 35:27021-27083 2022b.
Kay Liu, Yingtong Dou, Yue Zhao, Xueying Ding, Xiyang Hu, Ruitong Zhang, Kaize Ding, Canyu Chen, Hao Peng, Kai Shu, et al. Pygod: A python library for graph outlier detection. arXiv preprint arXiv:2204. 220.22224410055, 2022c.
Tong Liu, Yushan Liu, Marcel Hildebrandt, Mitchell Joblin, Hang Li, and Volker Tresp. On calibration of graph neural networks for node classification. In International Joint Conference on Neural Networks, pp. 1-8. IEEE, 2022d.
Yang Liu, Xiang Ao, Fuli Feng, and Qing He. Ud-gnn: Uncertainty- debiased training on semi-homophilout graphs. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp.
1131-1140, 2022e.
Zhao- Yang Liu, Shao- Yuan Li. Songcan Chen, Yao Hu, and Sheng-Jun Huang. Uncertainty aware graph gaussian process for semi-supervised learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 4957-4964, 2020.
Zhao-Yang
Robert Lunde, Elizaveta Levina, and Ji Zhu. Conformal prediction for network assiisted regression. arXiv preprint 2002: 2023.
17

---

Published in Transactions on Machine Learning Research (11/2024)
Lucie Charlotte Magister, Dmitry Kazhdan, Vikash Singh, and Pietro Liò. Gcexplainer: Human- in-the-loop concept- based explanations for graph neural networks. arXiv preprini arXiv:2107. 1889, 2021.
Andrey Malinin and Mark Gales. Predictive uncertainty estimation siaprrr Advances in Neural Information Processing Systems, 31, 2018.
Sai Munikoti, Deepesh Agarwal, Laya Das, and Balasubramaniam Natarajan. A general framework for quantifying aleatoric and epistemic uncertainty in graph neural networks. Neurocomputing, 521:1-10, 20233.
Matteo Pagliardini, Gilberto Manunza, Martin Jaggi, Michael I Jordan, and Tatjana Chavdarova. Improving general- ization via uncertainty driven perturbations. arXiv preprint arXiv:2202.057737 2022.
Lorenzo Perini, Vincent Vereruyssen, and Jesse Davis. Quantifying the confidence of anomaly detectors in their example-wise predictions. In Joint European Conference Machine Learning and Knowledge Discovery in Databuses, pp. 227-243. Springer, 2020.
Weizhu Qian, Dalin Zhang, Yan Zhao, Kai Zheng, and JQ James. Uncertainty quantification for traffic forecasting: A unified approach. In 2023 IEEE 39th International Conference on Data Engineering (ICDE), pp. 992-1004. IEEE, 2023.
Saswati Ray, Sana Lakdawala, Mononito Goswami, and Chufan Gao. Learning graph neural networks for multivariate time series anomaly detection. arXiv preprint urXiv:2111.08082, 2021.
Pengzhen Ren, Yun Xiao, Xiaojun Chang, Po- Yao Huang, Zhihui Li, Brij В Gupta, Xiaojiang Chen, and Xin Wang. A survey of deep active learning, ACM computing surveys (CSUR), 54(9): 2021.
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks node classification. In International Conference Learning Representations, 2019.
Seongok Ryu, Yongchan Kwon, and Woo Youn Kim. A bayesian graph convolutional network for reliable prediction of molecular properties with uncertainty quantification. Chemical science, 10(36)8843-8844 2019.
Yan Scholten, Jan Schuchardt, Simon Geisler, Aleksandar Bojchevski, and Stephan Günnemann. Randomized message-interceptionn smoothing: Gray-box certificates for graph neural networks. Advances in Neural Informa- tion Processing Systems, 35:33144 14-33158, 2022.
Uday Shankar Shanthamallu, Jayaraman J Thiagarajan, and Andreas Spanias. Uncertainty matthiinn graph neural net- works to defend against poisoning attacks. In Proceedings of the Proceedings of the AAAI Conference on Artificial Intelligence Conference on Artificial Intelligence, volume 35, pp. 9532-9532, 2021.
Lewis Smith and Yarin Gal. Understanding measures of uncertainty for adversarial example detection. arXiv preprint 18X33v1803.088 085333, 2018.
Yu Song and Donglin Wang. Learning on graphs with out-of-distribution nodes. Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 1635-1645, 2022.
Maximilian Stadler, Bertrand Charpentier, Simon Geisler, Daniel Zügner, and Stephan Günnemann. Graph poste- rior network: Bayesian predictive uncertainty for node classification. Advances in Neural Information Processing Systems, 14:18033-18043 2021.
Ke Sun, Zhouchen Lin, and Zhanxing Zhu. Multi-stage self-supervised learning for graph convolutional networks on graphs with few labeled nodes. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pp. 5892-5899, 2020.
Li Sun, Zhongbao Zhang, Jiawei Zhang, Feiyang Wang, Hao Peng, Sen Su, and S Yu Philip. Hyperbolic variational graph neural network for modeling dynamic graphs. In Proceedings of the AAAI Conference on Artificial Intelli- 4373-4383, gence, volume 35. pp. 4375 4383, 2021.
Lichao Sun, Yingtong Dou, Carl Yang, Kai Zhang, Wang. S Yu Philip, Lifang He, and Bo Li. Adversarial attack and defense graph data: A survey. IEEE Transactions on Knowledge and Data Engineering, 2022.
18

---

Published in Transactions on Machine Learning Research (11/2024)
Shikhar Vashishth, Prateek Yadav, Manik Bhandari, and Partha Talukdar. Confidence-basee graph convolutional net- works for semi-supervised learning. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1792-1801. PMLR, 2019.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
Fangxin Wang, Kay Liu, Sourav Medya, and Philip S Yu. Bangs: Game-theoretic node selection for graph self- training. arXiv preprint arXiv:2410.09348, 2024.
Min Wang, Hao Yang, and Qing Cheng. Gel: Graph calibration loss for trustworthy graph neural network. In Proceedings of the 30th ACM International Conference on Multimedia, pp. 988 988-996, 2022.
Qingyi Wang. Shenhao Wang. Dingyi Zhuang, Haris Koutsopoulos, and Jinhua Zhao. Uncertainty quantification of spatiotemporal travel demand with probabilistic graph neural networks. arXiv preprint arXiv:2303.040400 2023.
Xiao Wang, Hongrui Liu, Chuan Shi, and Cheng Yang. Be confident! towards trustworthy graph neural networks via confidence calibration. Advances in Neural Information Processing Systems, 34:23768-23777 2021.
Tom Wollschläger, Nicholas Gao, Bertrand Charpentier, Mohamed Amine Ketata, and Stephan Günnemann. Uncer- tainty estimation for molecules: Desiderata and methods. In International conference machine learning, pp. 37133-37156. PMLR, 2023.
Bingzhe Wu, Jintang Li, Junchi Yu, Yatao Bian, Hengtong Zhang, CHaochao Chen, Chengbin Hou, Guoji Fu, Liang Chen, Tingyang Xu, et al. A survey of trustworthy graph learning: Reliability, explainability, and privacy protection. arXiv preprint arXiv:2205. 10014, 2022.
Dongxia Wu, Liyao Gao, Matteo Chinazzi, Xinyue Xiong, Alessandro Vespignani, Yi-An Ma, and Rose Yu. Quan- tifying uncertainty in deep spatiotemporal forecasting, In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pp. 1841-1851, 2021.
Man Wu, Shirui Pan, and Xingquan Zhu. Openwgl: Open-world graph learning. In 2020 IEEE international confer- ence data mining (icdm), pp. 681-698 IEEE, 2020a.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. IEEE transactions on neural networks and learning systems, 32(1):4 2:4,24, 2020b.
Hui Xu, Liyao Xiang, Junjie Ou, Yuting Weng, Xinbing Wang, and Chenghu Zhou. Open-world graph active learning for node classification. ACM Transactions on Knowledge Discovery from Data, 18(2):1-20, 2023.
Zhao Xu, Carolin Lawrence, Ammar Shaker, and Raman Siarheyeu. Uncertainty propagation in node classification. In 2022 IEEE International Conference on Data Mining (ICDM), pp. 1275-1280. IEEE, 2022.
Han Yang, Xiao Yan, Xinyan Dai, Yongqiang Chen, and James Cheng. Self-enhanced gnn: Improving graph neural networks using model outputs. In International Joint Conference on Neural Networks, pp. 1-8. IEEE, 2021.
Xueying Yang, Jiamian Wang, Xujiang Zhao, Sheng Li, and Zhiqiang Tao. Calibrate automated graph neural net- work via hyperparameter uncertainty. In Proceedings of the 31 ACM International Conference on Information & Knowledge Management, pp. 4640-4644, 2022.
Zhitao Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. Gnnexplainer: Generating explana- tions for graph neural networks. Advances in neural information processing systems, 32, 2019.
Soroush H Zargarbashi, Simone Antonelli, and Aleksandar Bojchevski. Conformal prediction sets for graph neural networks. In International Conference on Machine Learning, pp. 12292-12318. PMLR, 2023.
Rui Zha, Chuan Qin, Le Zhang, Dazhong Shen, Tong Xu, Hengshu Zhu, and Enhong Chen. Career mobility analysis with uncertainty-awe aware graph autoencoders: A job title transition perspective. IEEE Transactions on Computational Social Systems, 2023.
19

---

Published in Transactions on Machine Learning Research (11/2024)
Wentao Zhang, Xupeng Miao, Yingxia Shao, Jiawei Jiang, Lei Chen, Olivier Ruas, and Bin Cui. Reliable data distillation on graph convolutional network. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, pp. 1399-1414, 2020.
Wentao Zhang, Yu Shen, Yang Li, Lei Chen, Zhi Yang, and Bin Cui. Alg: Fast and accurate active learning framework for graph convolutional networks. In Proceedings of the 2021 International Conference on Management of Data, pp. 2366-2374, 2021a.
Wentao Zhang, Yexin Wang, Zhenbang You, Meng Cao, Ping Huang, Jiulong Shan, Zhi Yang, and CUI Bin. Informa- tion gain propagation: a new way graph active learning with soft labels. In International Conference on Learning Reprexentations, 2021b.
Xu Zhang, Liang Zhang, Bo Jin, and Xinjiang Lu. multi-view confidence-calibrated framework for fair and stable graph representation learning. In 202/ IEEE International Conference on Data Mining (ICDM), pp. 1493-1498. IEEE, 2021c.
Yao Zhang et al. Bayesian semi-supervised learning for uncertainty--allbraaee prediction of molecular properties and active learning. Chemical science, (555):815-88133 2019a.
Yingxue Zhang, Soumyasundar Pal, Mark Coates, and Deniz Ustebay. Bayesian graph convolutional neural networks for semi-superviss classification. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pp. 5829-5836, 2019b.
Gongpei Zhao, Tao Wang, Yidong Li, Yi Jin, and Congyan Lang. Entropy-aware self-training for graph convolutional networks. Neurocomputing, 464:394-407, 2021.
Xujiang Zhao, Feng Chen, Shu Hu, and Jin-Hee Cho. Uncertainty aware semi-supervised learning on graph data. Advances Neural Information Processing Systems, 33:12827-12836, 2020.
Yu Zhao, Qiang Xu, Ying Zou, and Wei Li. Modeling user reviews through bayesian graph attention networks for recommendation. ACM Transactions on Information Systems, 41(3):1-29, 2023.
Dingyuan Zhu, Ziwei Zhang, Peng Cui, and Wenwu Zhu. Robust graph convolutional networks against adversarial attacks. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 1399-1407, 2019.
Dingyi Zhuang. Shenhao Wang, Haris Koutsopoulos, and Jinhua Zhao. Uncertainty quantification of sparse travel de- mand prediction with spatial-temporal graph neural networks. In Proceedings of the 28th ACM SIGKDD Conference Knowledge Discovery and Data Mining, pp. 46394444444 (649, 2022.
20


Reviews:
[{"review_id": "9ioWKGRI5z", "reviewer": "Reviewer_s3gv", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n\n1. **Comprehensive Coverage:** The survey extensively covers the topic of uncertainty in GNNs, ranging from the identification of uncertainty sources to their implementation in real-world scenarios. This broad scope makes it an indispensable resource for researchers in the field.\n2. **Structured Framework and Organization:** The authors effectively structure a diverse range of literature into a coherent framework. This organization facilitates comprehension and allows readers to effortlessly navigate the complex aspects of GNN uncertainty.\n3. **Insightful Analysis and Future Directions:** The paper not only consolidates existing knowledge but also identifies critical research gaps and suggests potential future research directions, such as fine-grained uncertainty in graphs and task-specific uncertainty considerations. These insights are invaluable for propelling the field forward and steering future studies.\n\n**Areas for Improvement:**\n\n1. **Complexity for Novices:** The paper may pose challenges for newcomers to the field of uncertainty in GNNs. Including more foundational background information could help make the survey more accessible to a wider audience.\n2. **Need for Empirical Evidence:** While the survey is rich in discussions and general observations, incorporating empirical analyses or case studies could enhance its practical impact and provide concrete examples of the theories discussed.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper offers a detailed examination of uncertainty in graph neural networks (GNNs), focusing on its identification, quantification, and utilization to improve the reliability and effectiveness of GNNs across various applications. It adeptly compares and synthesizes existing theories and methods related to graph uncertainty, integrating this uncertainty into graph learning tasks. Furthermore, the paper bridges various sub-communities within the GNN field, laying a foundation for future research avenues.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See above", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "5wud7gkSZu", "reviewer": "Reviewer_65dG", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "On the surface level, I think that this work delivers what it promises: there is a survey of a sizeable number of publications relating to GNNs and uncertainty, these publications are reasonably organised in a structure imposed by the authors, and some avenues for future work in the area are identified.\n\nFrom that perspective, the effort invested by the authors could be considered worthy of a publication at TMLR.\n\nHowever, I also consider TMLR's criteria to place surveys in a bit of a gray area.\nI personally think the main utility from the surveys should come not only from an enumeration and organisation of a reference list, but also for conveying a useful opinion or argumentation that practitioners can follow when deciding which method to use.\n\nPresently, the survey does not meet this criterion in my mind. In a lot of cases, a paper is simply introduced, briefly summarised in isolation, and then the survey simply moves on to the next one. It is very rare that I see the authors' own opinions and anecdotal experiences introduced, and as a result this wouldn't necessarily be a survey that would give a lot of value beyond an organisational skeleton.\n\nAdditionally, I think that there are several places where additional references and contexts could have been provided to make the story more accurate and robust (see next section for suggestions).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents a survey on uncertainty estimation, quantification and utilisation in graph machine learning.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "A major requested change is to introduce more of the Authors' own opinions in this survey. Try to make a clear stand about which methods should be used in which circumstances, with some levels of argumentation. Additionally, it would be useful to make a stand about whether certain papers are able to properly defend their hypothesis, or more investigation may be needed.\n\nI think it might make sense to correct this attribution to DropEdge:\n\n> Rong et al. (2019) introduce DropEdge, which randomly removes a specified number of edges from the graph by drawing independent Bernoulli random variables (with a constant rate) during each training iteration.\n\nThis is not completely factually correct. Rong et al. are the first to _theoretically analyse_ edge dropout, but they are definitely not the first paper to attempt edge dropout as a regulariser. I'm not sure what's the first paper to do it, but for example, even the GAT paper (Veličković et al., ICLR'18) leverages such an operator (without theoretical motivation, of course).\n\nI also believe some sections would benefit from significantly more references being discussed.\nThe two sections that immediately come to mind as examples are **explainability** and **robustness**. \n\nPresently, the explainability discussion in the paper doesn't go far beyond GNNExplainer. While GNNExplainer was the landmark paper in this space, there's been _a lot_ of developments since then. Papers such as GraphLIME, or GCExplainer, for example, are worth discussing.\n\nSimilarly, the robustness section appears to largely neglect work on robustness certification from the folks at TUM (e.g. Simon Geisler or Aleksandar Bojchevski, et al.) which would likely also be worthy of inclusion here.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "tMmmntoRh5", "reviewer": "Reviewer_hKxZ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The strength of the paper lies mainly in the following aspects.\n1: It offers a thorough survey on many aspects of graph-uncertainty-related researches.\n2: For each point listed in the survey, some references are offered so researchers could further investigate.\n3: The paper also provides some potential future directions for graph-uncertainty-related researches.\n\nThe following points are the weaknesses of the paper.\n1: It has ambiguous definition of \"model with random parameters\". I guess the authors want to mean \"models with parameters being random variables\", but the expression is likely to be misunderstood as parameter themselves being randomly generated, which shall not be the case. Any ambiguity is a large weakness for survey papers.\n2: The paper uses two systems to classify different types of uncertainties, one system classifies by aleatoric uncertainty and epistemic uncertainty, where epistemic uncertainty includes model uncertainty and distributional uncertainty. Another system classifies by predictive uncertainty, model & data uncertainty and distributional uncertainty. The paper doesn't discuss the relationship between these two systems and it seems that the two systems introduced actually contradict with each other in definitions. For example, data uncertainty is put together with model uncertainty in system 2, but it shall act as part of the aleatoric uncertainty that belongs to different category as model uncertainty in system 1, causing ambiguity. \n3: The paper mentions abnormality detection, but doesn't discuss any graph attack and defense methods. The paper shall clarify the meaning of uncertainty and whether it includes the graph pertuabtion attacks and robustness-enhancement defense methods.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper surveys the source, measure and modeling regarding uncertainly in GNN. It summarizes uncertainly of GNNs in various aspects, categorizing sources of uncertainty in several ways. One way separates them to the aleatoric uncertainty and the epistemic uncertainly, the other divides them to predictive uncertainly, model & data uncertainly and the distributional uncertainly. The paper also discusses ways to estimate the certainly, including direct estimation, bayesian-based estimation and frequentist-based estimation, and \"models with random parameters\". The paper also introduces methods to handle the uncertainly in modeling including active learning, self-training, OOD detection, outlier detection and misclassification detection, as well as node level, edge level and graph level modeling and trustworthy GNN. The paper also mentions uncertainly induced by real-world application and future research directions, offering a survey.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1: The paper shall clarify the relationships between different categorization systems it uses in the paper. For example, which uncertainty belongs to aleatoric/epistemic uncertainty. \n2: The paper shall modify the ambiguous definitions like \"model with random parameters\" to reduce potential misunderstanding.\n3: The paper shall clarity the general definition of \"uncertainty\" and whether it includes graph attack/defense researches. Currently some methods like abnormalty detection are included but some others like robustness-enhanced models are not.", "broader_impact_concerns": "The publication of this paper is unlikely to introduce negative broader impacts.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The updated manuscript already address most of the reviewers' comments.
Decision: Accept (poster)