{'fraction_non_alphanumeric': 0.04486344600957781, 'fraction_numerical': 0.00989841104454285, 'mean_word_length': 4.7332567489948305, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 13, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 11, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Uncertainty Aware Semi-Supervised Learning on Graph Data

Thanks to graph neural networks (GNNs), semi-supervised node classification has shown the state-of-the-art performance in graph data. However, GNNs have not considered different types of uncertainties associated with class probabilities to minimize risk of increasing misclassification under uncertainty in real life. In this work, we propose a multi-source uncertainty framework using a GNN that reflects various types of predictive uncertainties in both deep learning and belief/evidence theory domains for node classification predictions. By collecting evidence from the given labels of training nodes, the Graph-based Kernel Dirichlet distribution Estimation (GKDE) method is designed for accurately predicting node-level Dirichlet distributions and detecting out-of-distribution (OOD) nodes. We validated the outperformance of our proposed model compared to the state-of-the-art counterparts in terms of misclassification detection and OOD detection based on six real network datasets. We found that dissonance-based detection yielded the best results on misclassification detection while vacuity-based detection was the best for OOD detection. To clarify the reasons behind the results, we provided the theoretical proof that explains the relationships between different types of uncertainties considered in this work.


Introduction
Inherent uncertainties derived from different root causes have realized as serious hurdles to find effective solutions for real world problems. Critical safety concerns have been brought due to lack of considering diverse causes of uncertainties, resulting in high risk due to misinterpretation of uncertainties (e.g., misdetection or misclassification of an object by an autonomous vehicle). Graph neural networks (GNNs) [16,32] have received tremendous attention in the data science community. Despite their superior performance in semi-supervised node classification and regression, they didn't consider various types of uncertainties in the their decision process. Predictive uncertainty estimation [14] using Bayesian NNs (BNNs) has been explored for classification prediction and regression in the computer vision applications, based on aleatoric uncertainty (AU) and epistemic uncertainty (EU). AU refers to data uncertainty from statistical randomness (e.g., inherent noises in observations) while EU indicates model uncertainty due to limited knowledge (e.g., ignorance) in collected data. In the belief or evidence theory domain, Subjective Logic (SL) [12] considered vacuity (or a lack of evidence or ignorance) as uncertainty in a subjective opinion. Recently other uncertainty types, such as dissonance, consonance, vagueness, and monosonance [12], have been discussed based on SL to measure them based on their different root causes. We first considered multidimensional uncertainty types in both deep learning (DL) and belief and evidence theory domains for node-level classification, misclassification detection, and out-of-distribution (OOD) detection tasks. By leveraging the learning capability of GNNs and considering multidimensional uncertainties, we propose a uncertainty-aware estimation framework by quantifying 34th Conference on Neural Information Processing Systems (NeurIPS 2020), Vancouver, Canada. arXiv:2010.12783v1 [cs.LG] 24 Oct 2020 different uncertainty types associated with the predicted class probabilities. In this work, we made the following key contributions: • A multi-source uncertainty framework for GNNs. Our proposed framework first provides the estimation of various types of uncertainty from both DL and evidence/belief theory domains, such as dissonance (derived from conflicting evidence) and vacuity (derived from lack of evidence). In addition, we designed a Graph-based Kernel Dirichlet distribution Estimation (GKDE) method to reduce errors in quantifying predictive uncertainties. • Theoretical analysis: Our work is the first that provides a theoretical analysis about the relationships between different types of uncertainties considered in this work. We demonstrate via a theoretical analysis that an OOD node may have a high predictive uncertainty under GKDE. • Comprehensive experiments for validating the performance of our proposed framework: Based on the six real graph datasets, we compared the performance of our proposed framework with that of other competitive counterparts. We found that the dissonance-based detection yielded the best results in misclassification detection while vacuity-based detection best performed in OOD detection.
Note that we use the term 'predictive uncertainty' in order to mean uncertainty estimated to solve prediction problems.

Related Work
DL research has mainly considered aleatoric uncertainty (AU) and epistemic uncertainty (EU) using BNNs for computer vision applications. AU consists of homoscedastic uncertainty (i.e., constant errors for different inputs) and heteroscedastic uncertainty (i.e., different errors for different inputs) [5]. A Bayesian DL framework was presented to simultaneously estimate both AU and EU in regression (e.g., depth regression) and classification (e.g., semantic segmentation) tasks [14]. Later, distributional uncertainty was defined based on distributional mismatch between testing and training data distributions [20]. Dropout variational inference [7] was used for an approximate inference in BNNs using epistemic uncertainty, similar to DropEdge [24]. Other algorithms have considered overall uncertainty in node classification [3,18,34]. However, no prior work has considered uncertainty decomposition in GNNs.
In the belief (or evidence) theory domain, uncertainty reasoning has been substantially explored, such as Fuzzy Logic [1], Dempster-Shafer Theory (DST) [28], or Subjective Logic (SL) [11]. Belief theory focuses on reasoning inherent uncertainty in information caused by unreliable, incomplete, deceptive, or conflicting evidence. SL considered predictive uncertainty in subjective opinions in terms of vacuity (i.e., a lack of evidence) and vagueness (i.e., failing in discriminating a belief state) [11]. Recently, other uncertainty types have been studied, such as dissonance caused by conflicting evidence [12]. In the deep NNs, [27] proposed evidential deep learning (EDL) model, using SL to train a deterministic NN for supervised classification in computer vision based on the sum of squared loss. However, EDL didn't consider a general method of estimating multidimensional uncertainty or graph structure.

Multidimensional Uncertainty and Subjective Logic
This section provides the overview of SL and discusses SL-based multiple types of uncertainties, called evidential uncertainty, with the measures of vacuity and dissonance. In addition, we give a brief overview of probabilistic uncertainty, discussing the measures of aleatoric and epistemic.

Subjective Logic
SL offers the formulation of a subjective opinion based on both probabilistic logic (PL) [23] and belief theory (BT) [29] with two unique extensions. First, SL explicitly represents uncertainty by introducing vacuity of evidence (or uncertainty mass) in its opinion representation. This addresses the limitations of PL by modeling a lack of confidence in probabilities. Second, SL extends the traditional BT by incorporating base rates as the prior probabilities in Bayesian theory. The Bayesian nature of SL allows it to use second-order uncertainty to express and reason the uncertainty mass, where second-order uncertainty is represented by a probability density function (PDF) over first-order probabilities [11]. For multi-class problems, we use a multinomial distribution (i.e., first-order uncertainty) to model class probabilities and a Dirichlet PDF (i.e., second-order uncertainty) to model the distribution of class probabilities. Second-order uncertainty enriches uncertainty representation with evidence information, playing a key role in distinguish OOD from conflicting prediction as detailed later.
Opinions are the arguments in SL. In the multi-class setting, the multinomial opinion of a random variable y in domain Y = {1, ..., K} is given by a triplet as: where b = (b 1 , . . . , b K ) T , u, and a = (a 1 , . . . , a K ) T denote the belief mass distribution over Y, uncertainty mass representing vacuity of evidence, and base rate distribution over Y, respectively, and ∀k, a k ≥ 0, b k ≥ 0, u ≥ 0. The probability that y is assigned to the k-class is given by P (y = k) = b k + a k u, which combines the belief mass with the uncertain mass using the base rates.
In the multi-class setting, a k can be regarded as the prior preference over the k-th class. When no specific preference is given, we assign all the base rates as 1/K.

Evidential Uncertainty
In this section, we explain how the second order uncertainty (evidential uncertainty) is derived from the first order uncertainty as a Dirichlet PDF. Given a set of random variables p = (p 1 , ..., p K ) T , where p is distributed on a simplex of dimensionality K − 1, a conditional distribution P (y = k|p) = p k can be represented by the marginal distribution, P (y) = P (y|p)p(p)dp. We define p(p) as a Dirichlet PDF over p: Dir(p|α), where α = (α 1 , . . . , α K ) T is a K-dimensional strength vector, with α k ≥ 0 denoting the effective number of observations of the k-th class. SL explicitly introduces uncertain evidence through a weight W representing non-informative evidence and redefines the strength parameter as: α k = e k + a k W, with e k ≥ 0, ∀k ∈ Y, where e k is the amount of evidence (or the number of observations) to support the k-th class and W is usually set to K, i.e., the number of classes. Given the new definition of the strength parameter, the expectation of the class probabilities p = (p 1 , . . . , p K ) T is given by: where a k = 1/K. By marginalizing out p, we can derive an evidence-based expression of belief mass and uncertainty mass: SL categorizes uncertainty into two primary sources [11]: (1) basic belief uncertainty derived from single belief masses, and (2) intra-belief uncertainty based on the relationships between different belief masses. These two sources of uncertainty can be boiled down to vacuity and dissonance, respectively, that correspond to vacuous belief and contradicting beliefs. In particular, vacuity of an opinion ω is captured by uncertainty mass u v in (3) while dissonance of an opinion [12] is formulated by: where Bal(b j , b k ) is the relative mass balance function between two belief masses. The belief dissonance of an opinion is measured based on how much belief supports individual classes. Consider a binary classification example with a binomial opinion given by (b 1 , b 2 , u, a) = (0.49, 0.49, 0.02, a). Based on (4), it has a dissonance value of 0.98. In this case, although the vacuity is close to zero, a high dissonance indicates that one cannot make a clear decision because both two classes have the same amount of supporting both beliefs, which reveals strong conflict within the opinion.

Probabilistic Uncertainty
For classification, the estimation of the probabilistic uncertainty relies on the design of an appropriate Bayesian DL model with parameters θ. Given input x and dataset G, we estimate a class probability by P (y|x) = P (y|x; θ)P (θ|G)dθ, and obtain epistemic uncertainty estimated by mutual information [2,20]: where H(·) is Shannon's entropy of a probability distribution. The first term indicates entropy that represents the total uncertainty while the second term is aleatoric that indicates data uncertainty. By computing the difference between entropy and aleatoric uncertainties, we obtain epistemic uncertainty, which refers to uncertainty from model parameters. We use the shorthand notations u v , u diss , u alea , u epis , and u en to represent vacuity, dissonance, aleatoric, epistemic, and entropy, respectively.

Relationships Between Multiple Uncertainties
To interpret multiple types of uncertainty, we show three prediction scenarios of 3-class classification in Figure 1, in each of which the strength parameters α = [α 1 , α 2 , α 3 ] are known. To make a prediction with high confidence, the subjective multinomial opinion, following a Dirichlet distribution, will yield a sharp distribution on one corner of the simplex (see Figure 1 (a)). For a prediction with conflicting evidence, called a conflicting prediction (CP), the multinomial opinion should yield a central distribution, representing confidence to predict a flat categorical distribution over class labels (see Figure 1 (b)). For an OOD scenario with α = [1, 1, 1], the multinomial opinion would yield a flat distribution over the simplex (Figure 1 (c)), indicating high uncertainty due to the lack of evidence. The first technical contribution of this work is as follows. Theorem 1. We consider a simplified scenario, where a multinomial random variable y follows a K-class categorical distribution: y ∼ Cal(p), the class probabilities p follow a Dirichlet distribution: p ∼ Dir(α), and α refer to the Dirichlet parameters. Given a total Dirichlet strength S = K i=1 α i , for any opinion ω on a multinomial random variable y, we have 1. General relations on all prediction scenarios.
2. Special relations on the OOD and the CP.
(a) For an OOD sample with a uniform prediction (i.e., α = [1, . . . , 1]), we have For an in-distribution sample with a conflicting prediction (i.e., α = [α 1 , . . . , α K ] with α 1 = α 2 = · · · = α K , if S → ∞), we have The proof of Theorem 1 can be found in Appendix A.1. As demonstrated in Theorem 1 and Figure 1, entropy cannot distinguish OOD (see Figure 1 (c)) and conflicting predictions (see Figure 1 (b)) because entropy is high for both cases. Similarly, neither aleatoric uncertainty nor epistemic uncertainty can distinguish OOD from conflicting predictions. In both cases, aleatoric uncertainty is high while epistemic uncertainty is low. On the other hand, vacuity and dissonance can clearly distinguish OOD from a conflicting prediction. For example, OOD objects typically show high vacuity with low dissonance while conflicting predictions exhibit low vacuity with high dissonance. This observation is confirmed through the empirical validation via our extensive experiments in terms of misclassification and OOD detection tasks.

Uncertainty-Aware Semi-Supervised Learning
In this section, we describe our proposed uncertainty framework based on semi-supervised node classification problem. The overall description of the framework is shown in Figure 2.

Problem Definition
Given an input graph G = (V, E, r, y L ), where V = {1, . . . , N } is a ground set of nodes, E ⊆ V × V is a ground set of edges, r = [r 1 , · · · , r N ] T ∈ R N ×d is a node-level feature matrix, r i ∈ R d is the feature vector of node i, y L = {y i | i ∈ L} are the labels of the training nodes L ⊂ V, and y i ∈ {1, . . . , K} is the class label of node i. We aim to predict: (1) the class probabilities of the testing nodes: (2) the associated multidimensional uncertainty estimates introduced by different root causes: where p i,k is the probability that the class label y i = k and m is the total number of uncertainty types.

Proposed Uncertainty Framework
Learning evidential uncertainty. As discussed in Section 3.1, evidential uncertainty can be derived from multinomial opinions or equivalently Dirichlet distributions to model a probability distribution for the class probabilities. Therefore, we design a Subjective GNN (S-GNN) f to form their multinomial opinions for the node-level Dirichlet distribution Dir(p i |α i ) of a given node i. Then, the conditional probability P (p|A, r; θ) can be obtained by: where f i is the output of S-GNN for node i, θ is the model parameters, and A is an adjacency matrix. The Dirichlet probability function Dir(p i |α i ) is defined by: Note that S-GNN is similar to classical GNN, except that we use an activation layer (e.g., ReLU) instead of the softmax layer (only outputs class probabilities). This ensures that S-GNN would output non-negative values, which are taken as the parameters for the predicted Dirichlet distribution.
Learning probabilistic uncertainty. Since probabilistic uncertainty relies on a Bayesian framework, we proposed a Subjective Bayesian GNN (S-BGNN) that adapts S-GNN to a Bayesian framework, with the model parameters θ following a prior distribution. The joint class probability of y can be estimated by: where P (θ|G) is the posterior, estimated via dropout inference, that provides an approximate solution of posterior q(θ) and taking samples from the posterior distribution of models [7]. Thanks to the benefit of dropout inference, training a DL model directly by minimizing the cross entropy (or square error) loss function can effectively minimize the KL-divergence between the approximated distribution and the full posterior (i.e., KL[q(θ) P (θ|G)]) in variational inference [7,13]. For interested readers, please refer to more detail in Appendix B.8.
Therefore, training S-GNN with stochastic gradient descent enables learning of an approximated distribution of weights, which can provide good explainability of data and prevent overfitting. We use a loss function to compute its Bayes risk with respect to the sum of squares loss y − p 2 2 by: where y i is an one-hot vector encoding the ground-truth class with y ij = 1 and y ik = for all k = j and j is a class label. Eq. (9) aims to minimize the prediction error and variance, leading to maximizing the classification accuracy of each training node by removing excessive misleading evidence. The loss function in Eq. (9) is designed to measure the sum of squared loss based on class labels of training nodes. However, it does not directly measure the quality of the predicted node-level Dirichlet distributions. To address this limitation, we proposed Graph-based Kernel Dirichlet distribution Estimation (GKDE) to better estimate nodelevel Dirichlet distributions by using graph structure information. The key idea of the GKDE is to estimate prior Dirichlet distribution parameters for each node based on the class labels of training nodes (see Figure 3). Then, we use the estimated prior Dirichlet distribution in the training process to learn the following patterns: (i) nodes with a high vacuity will be shown far from training nodes; and (ii) nodes with a high dissonance will be shown near the boundaries of classes. Based on SL, let each training node represent one evidence for its class label. Denote the contribution of evidence estimation for node j from training node i by

Graph-based Kernel Dirichlet distribution Estimation (GKDE)
2σ 2 ) is the Gaussian kernel function used to estimate the distribution effect between nodes i and j, and d ij means the node-level distance (a shortest path between nodes i and j), and σ is the bandwidth parameter. The prior evidence is estimated based GKDE:ê j = i∈L h(y i , d ij ), where L is a set of training nodes and the prior Dirichlet distributionα j =ê j + 1. During the training process, we minimize the KL-divergence between model predictions of Dirichlet distribution and prior distribution: min KL[Dir(α) Dir(α)]. This process can prioritize the extent of data relevance based on the estimated evidential uncertainty, which is proven effective based on the proposition below. Proposition 1. Given L training nodes, for any testing nodes i and j, let d i = [d i1 , . . . , d iL ] be the vector of graph distances from nodes i to training nodes and d j = [d j1 , . . . , d jL ] be the graph distances from nodes j to training nodes, where d il is the node-level distance between nodes i and l. If for all l ∈ {1, . . . , L}, d il ≥ d jl , then we havê whereû vi andû vj refer to vacuity uncertainties of nodes i and j estimated based on GKDE.
The proof for this proposition can be found in Appendix A.2. The above proposition shows that if a testing node is too far from training nodes, the vacuity will increase, implying that an OOD node is expected to have a high vacuity.
In addition, we designed a simple iterative knowledge distillation method [10] (i.e., Teacher Network) to refine the node-level classification probabilities. The key idea is to train our proposed model (Student) to imitate the outputs of a pre-train a vanilla GNN (Teacher) by adding a regularization term of KL-divergence. This leads to solving the following optimization problem: wherep is the vanilla GNN's (Teacher) output and λ 1 and λ 2 are trade-off parameters.

Experiments
In this section, we conduct experiments on the tasks of misclassification and OOD detections to answer the following questions for semi-supervised node classification: Q1. Misclassification Detection: What type of uncertainty is the most promising indicator of high confidence in node classification predictions? Q2. OOD Detection: What type of uncertainty is a key indicator of accurate detection of OOD nodes? Q3. GKDE with Uncertainty Estimates: How can GKDE help enhance prediction tasks with what types of uncertainty estimates?
Through extensive experiments, we found the following answers for the above questions: A1. Dissonance (i.e., uncertainty due to conflicting evidence) is more effective than other uncertainty estimates in misclassification detection. A2. Vacuity (i.e., uncertainty due to lack of confidence) is more effective than other uncertainty estimates in OOD detection. A3. GKDE can indeed help improve the estimation quality of node-level Dirichlet distributions, resulting in a higher OOD detection.

Experiment Setup Datasets:
We used six datasets, including three citation network datasets [26] (i.e., Cora, Citeseer, Pubmed) and three new datasets [30] (i.e., Coauthor Physics, Amazon Computer, and Amazon Photo). We summarized the description and experimental setup of the used datasets in Appendix B.2 1 .
Comparing Schemes: We conducted the extensive comparative performance analysis based on our proposed models and several state-of-the-art competitive counterparts. We implemented all models based on the most popular GNN model, GCN [16]. We compared our model (S-BGCN-T-K) against: (1) Softmax-based GCN [16] with uncertainty measured based on entropy; and (2) Drop-GCN that adapts the Monte-Carlo Dropout [7,25] into the GCN model to learn probabilistic uncertainty; (3) EDL-GCN that adapts the EDL model [27] with GCN to estimate evidential uncertainty; (4) DPN-GCN that adapts the DPN [20] method with GCN to estimate probabilistic uncertainty. We evaluated the performance of all models considered using the area under the ROC (AUROC) curve and area under the Precision-Recall (AUPR) curve in both experiments [9].

Results
Misclassification Detection. The misclassification detection experiment involves detecting whether a given prediction is incorrect using an uncertainty estimate. Table 1 shows that S-BGCN-T-K outperforms all baseline models under the AUROC and AUPR for misclassification detection. The outperformance of dissonance-based detection is fairly impressive. This confirms that low dissonance (a small amount of conflicting evidence) is the key to maximize the accuracy of node classification prediction. We observe the following performance order: Dissonance > Entropy ≈ Aleatoric > Vacuity ≈ Epistemic, which is aligned with our conjecture: higher dissonance with conflicting prediction leads to higher misclassification detection. We also conducted experiments on additional three datasets and observed similar trends of the results, as demonstrated in Appendix C. OOD Detection. This experiment involves detecting whether an input example is out-of-distribution (OOD) given an estimate of uncertainty. For semi-supervised node classification, we randomly selected one to four categories as OOD categories and trained the models based on training nodes of the other categories. Due to the space constraint, the experimental setup for the OOD detection is detailed in Appendix B.3. In Table 2, across six network datasets, our vacuity-based detection significantly outperformed the other competitive methods, exceeding the performance of the epistemic uncertainty and other type of uncertainties. This demonstrates that vacuity-based model is more effective than other uncertainty estimates-based counterparts in increasing OOD detection. We observed the following performance order: Vacuity > Entropy ≈ Aleatoric > Epistemic ≈ Dissonance, which is consistent with the theoretical results as shown in Theorem 1. Ablation Study. We conducted additional experiments (see Table 3) in order to demonstrate the contributions of the key technical components, including GKDE, Teacher Network, and subjective  Bayesian framework. The key findings obtained from this experiment are: (1) GKDE can enhance the OOD detection (i.e., 30% increase with vacuity), which is consistent with our theoretical proof about the outperformance of GKDE in uncertainty estimation, i.e., OOD nodes have a higher vacuity than other nodes; and (2) the Teacher Network can further improve the node classification accuracy.

Why is Epistemic Uncertainty Less Effective than Vacuity?
Although epistemic uncertainty is known to be effective to improve OOD detection [7,14] in computer vision applications, our results demonstrate it is less effective than our vacuity-based approach. The first potential reason is that epistemic uncertainty is always smaller than vacuity (From Theorem 1), which potentially indicates that epistemic may capture less information related to OOD. Another potential reason is that the previous success of epistemic uncertainty for OOD detection is limited to supervised learning in computer vision applications, but its effectiveness for OOD detection was not sufficiently validated in semi-supervised learning tasks. Recall that epistemic uncertainty (i.e., model uncertainty) is calculated based on mutual information (see Eq. (5)). In a semi-supervised setting, the features of unlabeled nodes are also fed to a model for training process to provide the model with a high confidence on its output. For example, the model output P (y|A, r; θ) would not change too much even with differently sampled parameters θ, i.e., P (y|A, r; θ (i) ) ≈ P (y|A, r; θ (j) ), which result in a low epistemic uncertainty. We also designed a semi-supervised learning experiment for image classification and observed a consistent pattern with the results demonstrated in Appendix C.6.

Conclusion
In this work, we proposed a multi-source uncertainty framework of GNNs for semi-supervised node classification. Our proposed framework provides an effective way of predicting node classification and out-of-distribution detection considering multiple types of uncertainty. We leveraged various types of uncertainty estimates from both DL and evidence/belief theory domains. Through our extensive experiments, we found that dissonance-based detection yielded the best performance on misclassification detection while vacuity-based detection performed the best for OOD detection, compared to other competitive counterparts. In particular, it was noticeable that applying GKDE and the Teacher network further enhanced the accuracy in node classification and uncertainty estimates.

Broader Impact
In this paper, we propose a uncertainty-aware semi-supervised learning framework of GNN for predicting multi-dimensional uncertainties for the task of semi-supervised node classification. Our proposed framework can be applied to a wide range of applications, including computer vision, natural language processing, recommendation systems, traffic prediction, generative models and many more [35]. Our proposed framework can be applied to predict multiple uncertainties of different roots for GNNs in these applications, improving the understanding of individual decisions, as well as the underlying models. While there will be important impacts resulting from the use of GNNs in general, our focus in this work is on investigating the impact of using our method to predict multisource uncertainties for such systems. The additional benefits of this method include improvement of safety and transparency in decision-critical applications to avoid overconfident prediction, which can easily lead to misclassification.
We see promising research opportunities that can adopt our uncertainty framework, such as investigating whether this uncertainty framework can further enhance misclassification detection or OOD detection. To mitigate the risk from different types of uncertainties, we encourage future research to understand the impacts of this proposed uncertainty framework to solve other real world problems.

Appendix A Proofs
A.1 Theorem 1's Proof Theorem 1. We consider a simplified scenario, where a multinomial random variable y follows a K-class categorical distribution: y ∼ Cal(p), the class probabilities p follow a Dirichlet distribution: p ∼ Dir(α), and α refer to the Dirichlet parameters. Given a total Dirichlet strength S = K i=1 αi, for any opinion ω on a multinomial random variable y, we have 1. General relations on all prediction scenarios.
2. Special relations on the OOD and the CP. with uen > u alea > u diss > uv > uepis.
Interpretation. Theorem 1.1 (a) implies that increases in both uncertainty types may not happen at the same time. A higher vacuity leads to a lower dissonance, and vice versa (a higher dissonance leads to a lower vacuity). This indicates that a high dissonance only occurs only when a large amount of evidence is available and the vacuity is low. Theorem 1.1 (b) shows relationships between vacuity and epistemic uncertainty in which vacuity is an upper bound of epistemic uncertainty. Although some existing approaches [11,27] treat epistemic uncertainty the same as vacuity, it is not necessarily true except for an extreme case where a sufficiently large amount of evidence available, making vacuity close to zero. Theorem 1.2 (a) and (b) explain how entropy differs from vacuity and/or dissonance. We observe that entropy is 1 when either vacuity or dissonance is 0. This implies that entropy cannot distinguish different types of uncertainty due to different root causes. For example, a high entropy is observed when an example is an either OOD or misclassified example. Similarly, a high aleatoric uncertainty value and a low epistemic uncertainty value are observed under both cases. However, vacuity and dissonance can capture different causes of uncertainty due to lack of information and knowledge and to conflicting evidence, respectively. For example, an OOD objects typically show a high vacuity value and a low dissonance value while a conflicting prediction exhibits a low vacuity and a high dissonance.
Proof. 1. (a) Let the opinion ω = [b1, . . . , bK , uv], where K is the number of classes, bi is the belief for class i, uv is the uncertainty mass (vacuity), and K i=1 bi + uv = 1. Dissonance has a upper bound with where Bal(bi, bj) is the relative mass balance, then we have 1. (b) For the multinomial random variable y, we have where Cal(p) is the categorical distribution and Dir(α) is Dirichlet distribution. Then we have Prob(y|α) = Prob(y|p)Prob(p|α)dp, (15) and the epistemic uncertainty is estimated by mutual information, Now we consider another measure of ensemble diversity: Expected Pairwise KL-Divergence between each model in the ensemble. Here the expected pairwise KL-Divergence between two independent distributions, including P (y|p 1 ) and P (y|p 2 ), where p 1 and p 2 are two independent samples from Prob(p|α), can be computed, where S = K i=1 αi and ψ(·) is the digamma Function, which is the derivative of the natural logarithm of the gamma function. Now we obtain the relations between vacuity and epistemic, 2. (a) For an out-of-distribution sample, α = [1, . . . , 1], the vacuity can be calculated as and the belief mass bi = (αi − 1)/ K i=1 αi = 0, we estimate dissonance, Given the expected probabilityp = [1/K, . . . , 1/K] , the entropy is calculated based on log K , where H(·) is the entropy. Based on Dirichlet distribution, the aleatoric uncertainty refers to the expected entropy, . . , pK ] , and K ≥ 2 is the number of category. The epistemic uncertainty can be calculated via the mutual information, To compare aleatoric uncertainty with epistemic uncertainty, we first prove that aleatoric uncertainty (Eq. (24)) is monotonically increasing and converging to 1 as K increases. Based on Lemma 1, we have Based on Eq. (25) and Eq. (24), we prove that aleatoric uncertainty is monotonically increasing with respect to K. So the minimum aleatoric can be shown to be 1 ln 2 1 2 , when K = 2. Similarly, for epistemic uncertainty, which is monotonically decreasing as K increases based on Lemma 1, the maximum epistemic can be shown to be 1 − 1 ln 2 1 2 when K = 2. Then we have, Therefore, we prove that 1 = uv = uen > u alea > uepis > u diss = 0.
Proof. We will prove by induction that, for all integer N ≥ 2, Denote that g(x) = (x + 1) ln( x+1 x ) with x > 2. We get its derivative, g (x) = ln(1 + 1 x ) − 1 x < 0, such that g(x) is monotonically decreasing, which results in g(K) > g(K + 1). Based on Eq. (35) we have, Thus, Eq. (34) holds for N = K + 1, and the proof of the induction step is complete. Interpretation. From the above proposition, if a testing node is too distant (far away) from training nodes, the vacuity increases, indicating that an OOD node is expected to have a high vacuity value.
Proof. Let y = [y1, . . . , yL] be the label vector for training nodes. Based on GKDE, the evidence contribution for the node i and a training node l ∈ {1, . . . , L|} is h(y l , d il ) = [h1(y l , d il ), . . . , hK (y l , d il )], where and the prior evidence can be estimated based GKDE: whereêi = [ei1, ..., eiK ]. Since each training node only contributes the same evidence based on its label based on Eq. (37), the total evidence is estimated by all the contributing evidence as where the vacuity values for node i and node j based on GKDE are,

B.1 Source code
The source code and datasets are accessible at https://github.com/zxj32/uncertainty-GNN Cora, Citeseer, and Pubmed [26]: These are citation network datasets, where each network is a directed network in which a node represents a document and an edge is a citation link, meaning that there exists an edge when A document cites B document, or vice-versa with a direction. Each node's feature vector contains a bag-of-words representation of a document. For simplicity, we don't discriminate the direction of links and treat citation links as undirected edges and construct a binary, symmetric adjacency matrix A. Each node is labeled with the class to which it belongs.

B.2 Description of Datasets
Coauthor Physics, Amazon Computers, and Amazon Photo [30]: Coauthor Physics is the dataset for coauthorship graphs based on the Microsoft Academic Graph from the KDD Cup 2016 Challenge 2 . In the graphs, a node is an author and an edge exists when two authors co-author a paper. A node's features represent the keywords of its papers and the node's class label indicates its most active field of study. Amazon Computers and Amazon Photo are the segments of an Amazon co-purchase graph [21], where a node is a good (i.e., product), an edge exists when two goods are frequently bought together. A node's features are bag-of-words representation of product reviews and the node's class label is the product category.
For all the used datasets, we deal with undirected graphs with 20 training nodes for each category. We chose the same dataset splits as in [33] with an additional validation node set of 500 labeled examples for the hyperparameter obtained from the citation datasets, and followed the same dataset splits in [30] for Coauthor Physics, Amazon Computer, and Amazon Photo datasets, for the fair comparison 3 .
Metric: We used the following metrics for our experiments: • Area Under Receiver Operating Characteristics (AUROC): AUROC shows the area under the curve where FPR (false positive rate) is in x-axis and TPR (true positive rate) is in y-axis. It can be interpreted as the probability that a positive example is assigned a higher detection score than a negative example [4]. A perfect detector corresponds to an AUROC score of 100%.
• Area Under Precision-Prediction Curve (AUPR): The PR curve is a graph showing the precision=TP/(TP+FP) and recall=TP/(TP+FN) against each other,and AUPR denotes the area under the precision-recall curve. The ideal case is when Precision is 1 and Recall is 1.

B.3 Experimental Setup for Out-of-Distribution (OOD) Detection
For OOD detection on semi-supervised node classification, we randomly selected 1-4 categories as OOD categories and trained the models only based on training nodes of the other categories. In this setting, we still trained a model for semi-supervised node classification task, but only part of node categories were not used for training. Hence, we suppose that our model only outputs partial categories (as we don't know the OOD category), see Table 5. For example, Cora dataset, we trained the model with 80 nodes (20 nodes for each category) with the predictions of 4 categories. Positive ratio is the ratio of out-of-distribution nodes among on all test nodes.

B.4 Baseline Setting
In experiment part, we considered 4 baselines. For GCN, we used the same hyper-parameters as [16]. For EDL-GCN, we used the same hyper-parameters as GCN, and replaced softmax layer to activation layer (Relu) with squares loss [27]. For DPN-GCN, we used the same hyper-parameters as GCN, and changed the softmax layer to activation layer (exponential). Note that as we can not generate OOD node, we only used in-distribution loss of (see Eq.12 in [20]) and ignored the OOD part loss. For Drop-GCN, we used the same hyper-parameters as GCN, and set Monte Carlo sampling times M = 100, dropout rate equal to 0.5.

B.5 Time Complexity Analysis
S-BGCN has a similar time complexity with GCN while S-BGCN-T has the double complexity of GCN. For a given network where |V| is the number of nodes, |E| is the number of edges, C is the number of dimensions of the input feature vector for every node, F is the number of features for the output layer, and M is Monte Carlo sampling times.

B.6 Model Setups for semi-supervised node classification
Our models were initialized using Glorot initialization [8] and trained to minimize loss using the Adam SGD optimizer [15]. For the S-BGCN-T-K model, we used the early stopping strategy [30] on Coauthor Physics, Amazon Computer and Amazon Photo datasets while non-early stopping strategy was used in citation datasets (i.e., Cora, Citeseer and Pubmed). We set bandwidth σ = 1 for all datasets in GKDE, and set trade off parameters λ1 = 0.001 for misclassification detection, λ1 = 0.1 for OOD detection and λ2 = min(1, t/200) (where t is the index of a current training epoch) for both task; other hyperparameter configurations are summarized in Table 7.
For semi-supervised node classification, we used 50 random weight initialization for our models on Citation network datasets. For Coauthor Physics, Amazon Computer and Amazon Photo datasets, we reported the result based on 10 random train/validation/test splits. In both effect of uncertainty on misclassification and the OOD detection, we reported the AUPR and AUROC results in percent averaged over 50 times of randomly chosen 1000 test nodes in all of test sets (except training or validation set) for all models tested on the citation datasets. For S-BGCN-T-K model in these tasks, we used the same hyperparameter configurations as in Table 7, except S-BGCN-T-K Epistemic using 10,000 epochs to obtain the best result.

B.8 Bayesian Inference with Dropout
The marginalization in Eq.(8) (in main paper) is generally intractable. A dropout technique is used to obtain an approximate solution and use samples from the posterior distribution of models [7]. Hence, we adopted a dropout technique in [6] for variational inference in Bayesian convolutional neural networks where Bernoulli distributions are assumed over the network's weights. This dropout technique allows us to perform probabilistic inference over our Bayesian DL framework using GNNs. For Bayesian inference, we identified a posterior distribution over the network's weights, given the input graph D and observed labels y L by Prob(θ|D), where θ = {W1, . . . , WL, b1, ..., bL}, L is the total number of layers and Wi refers to the GNN's weight matrices of dimensions Di × Di−1, and bi is a bias vector of dimensions Di for layer i = 1, · · · , L. Since the posterior distribution is intractable, we used a variational inference to learn q(θ), a distribution over matrices whose columns are randomly set to zero, approximating the intractable posterior by minimizing the Kullback-Leibler (KL)-divergence between this approximated distribution and the full posterior, which is given by: KL(q(θ) Prob(θ|D)) (43) We define Wi in q(θ) by: where γ = {M1, . . . , ML, m1, . . . , mL} are the variational parameters, Mi ∈ R D i ×D i−1 , mi ∈ R D i , and d = {d1, . . . , dL} is the dropout probabilities with zij of Bernoulli distributed random variables. The binary variable zij = 0 corresponds to unit j in layer i − 1 being dropped out as an input to layer i. We can obtain the approximate model of the Gaussian process from [6]. The dropout probabilities, di's, can be optimized or fixed [13]. For simplicity, we fixed di's in our experiments, as it is beyond the scope of our study. In [6], the minimization of the cross entropy (or square error) loss function is proven to minimize the KL-divergence (see Eq. (43)). Therefore, training the GNN model with stochastic gradient descent enables learning of an approximated distribution of weights, which provides good explainability of data and prevents overfitting.
For the dropout inference, we performed training on a DL model with dropout before every weight layer and dropout at a test time to sample from the approximate posterior (i.e., stochastic forward passes, a.k.a. Monte Carlo dropout; see Eq. (45)). At the test stage, we infer the joint probability by: where M is Monte Carlo sampling times. We can also infer the Dirichlet parameters α as:

C Additional Experimental Results
In addition to the uncertainty analysis in Section 5, we also conducted additional experiments. First, we conducted an ablation experiment for each component (such as GKDE, Teacher network, Subjective framework and Bayesian framework) we proposed. Second, we provide additional uncertainty visualization results in network node classifications for Citeseer dataset. To clearly understand the effect of different types of uncertainty in classification accuracy and OOD, we used the AUROC and AUPR curves for all types of models considered in this work.

C.1 Ablation Experiments
We conducted an additional experiments in order to clearly demonstrate the contributions of the key technical components, including a teacher Network, Graph kernel Dirichlet Estimation (GKDE) and subjective Bayesian framework. The key findings obtained from this experiment are: (1) The teacher Network can further improve node classification accuracy (i.e., 0.2% -1.5% increase, as shown in Table 8); and (2) GKDE (Graph-Based Kernel Dirichlet Distribution Estimation) using the uncertainty estimates can enhance OOD detection (i.e., 4% -30% increase, as shown in Table 9).

C.2 Experiment based on GAT model
We also conducted the semi-supervised node classification based on GAT model [32]).Model setup: The S-BGAT-T-K model has two dropout probabilities, which are a dropout on features and a dropout on attention coefficients, as shown in Table 10. We changed the dropout on attention coefficients to 0.4 at the test stage and set trade off parameters λ = min(1, t/50), using the same early stopping strategy [32]. The result are shown in Table 11.

C.3 Misclassification Detection
For Amazon Photo, Amazon Computer and Coauthor Physics dataset, the misclassification detection results are shown in Tabel 12.

C.4 Graph Embedding Representations of Different Uncertainty Types
To better understand different uncertainty types, we used t-SNE (t-Distributed Stochastic Neighbor Embedding [19]) to represent the computed feature representations of a pre-trained BGCN-T model's first hidden layer on the Cora dataset and the Citeseer dataset.
Seven Classes on Cora Dataset: In Figure 4, (a) shows the representation of seven different classes, (b) shows our model prediction and (c)-(f) present the extent of uncertainty for respective uncertainty types, including vacuity, dissonance, and aleatoric uncertainty, respectively.
Six Classes on Citeseer Dataset: In Figure 5 (a), a node's color denotes a class on the Citeseer dataset where 6 different classes are shown in different colors. Figure 5 (b) is our prediction result.     Eight Classes on Amazon Photo Dataset: In Figure 6, a node's color denotes vacuity uncertainty value, and the big node represent training node. These results are based on OOD detection experiment. Compare Figure 6 (a) and (b), we found that GKDE can indeed improve the OOD detection. To examine the trends of the extent of uncertainty depending on either training nodes or test nodes, we draw training nodes as bigger circles than test nodes. Overall we notice that most training nodes (shown as bigger circles) have low uncertainty (i.e., blue), which is reasonable because the training nodes are the ones that are already observed. Now we discuss the extent of uncertainty under each uncertainty type.
Vacuity: In Figure 6 (b), most training nodes show low uncertainty, we observe majority of OOD nodes in the button cluster show high uncertainty as appeared in red.
Dissonance: In Figure 5 (d), similar to vacuity, training nodes have low uncertainty. But unlike vacuity, test nodes are much less uncertain. Recall that dissonance represents the degree of conflicting evidence (i.e., discrepancy between each class probability). However, in this dataset, we observe a fairly low level of dissonance and the obvious outperformance of Dissonance in node classification prediction.
Aleatoric uncertainty: In Figure 5 (e), a lot of nodes show high uncertainty with larger than 0.5 except a small amount of training nodes with low uncertainty.
Epistemic uncertainty: In Figure 5 (f), most nodes show very low epistemic uncertainty values because uncertainty derived from model parameters can disappear as they are trained well.

C.5 PR and ROC Curves
AUPR for the OOD Detection: Figure 8 shows the AUPRC for the OOD detection when S-BGCN-T-K is used to detect OOD in which test nodes are considered based on their high uncertainty level, given a different uncertainty type, such as vacuity, dissonance, aleatoric, epistemic, or entropy (or total uncertainty). Also to check the performance of the proposed models with a baseline model, we added S-BGCN-T-K with test nodes randomly selected (i.e., Random).
Obviously, in Random baseline, precision was not sensitive to increasing recall while in S-BGCN-T-K (with test nodes being selected based on high uncertainty) precision decreases as recall increases. But although most S-BGCN-T-K models with various uncertainty types used to select test nodes shows sensitive precision to increasing recall (i.e., proving uncertainty being an indicator of improving OOD detection). In addition, unlike AUPR in misclassification detection, which showed the best performance in S-BGCN-T-K Dissonance (see Figure 7), S-BGCN-T-K Dissonance showed the second worst performance among the proposed S-BGCN-T-K models with other uncertainty types. This means that less conflicting information does not help OOD detection. On the other hand, overall we observed Vacuity performs the best among all. From this finding, we can claim that to improve OOD detection, less information with a high vacuity value can help boost the accuracy of the OOD detection.
AUROC for the OOD Detection: First, we investigated the performance of our proposed S-BGCN-T-K models when test nodes are selected based on seven different criteria (i.e., uncertainty measures). For AUROC in Figure 9, we observed much better performance in most S-BGCN-T-K models with all uncertainty types except epistemic uncertainty.

C.6 Analysis for Epistemic Uncertainty in OOD Detection
Although epistemic uncertainty is known to be effective to improve OOD detection [7,14] in computer vision applications, our results demonstrate it is less effective than our vacuity-based approach. One potential reason is that the previous success of epistemic in computer vision applications are only applied in supervised learning, but they are not sufficiently validated in semi-supervised learning.
To back up our conclusion, designe a image classification experiment based on MC-Drop [7] method to do the following experiment: 1) supervised learning on MNIST dataset with 50 labeled images; 2) semi-supervised learning (SSL) on MNIST dataset with 50 labeled images and 49950 unlabeled images, while there are 50% OOD images (24975 FashionMNIST images) in unlabeled set. For both experiment, we test the epistemic uncertainty on 49950 unlabeled set (50% In-distribution (ID) images and 50% OOD images). We conduct the experiment the experiment based on three popular SSL methods, VAT [22], Mean Teacher [31] and pseudo label [17]. Table 13  shows the average epistemic uncertainty value for in-distribution samples and OOD samples. The result shows the same pattern with [14,13] in a supervised setting, but an opposite pattern in a semi-supervised setting that low epistemic of OOD samples, which is less effective top detect OOD. Note that the SSL setting is similar to our semi-supervised node classification setting, which feed the unlabeled sample to train the model.