Year: 2019

Abstract:
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 the class probabilities to minimize risk increasing misclassification under uncertainty in real life. In this work, we propose a Subjective Bayesian deep learning framework reflecting various types of uncertainties for classification predictions by leveraging the powerful modeling and learning capabilities of GNNs. We considered multiple uncertainty types in both deep learning (DL) and belief/evidence theory domains. We treat the predictions of a Subjective Bayesian GNN (S-BGNN) as nodes’ multinomial subjective opinions in a graph based on Dirichlet distributions where each belief mass is a belief probability of each class. By collecting evidence from the given labels of training nodes, the S-BGNN model is designed for accurately predicting probabilities of each class and detecting out-of-distribution. We validated the outperformance of the proposed S-BGNN, compared to the state-of-the-art counterparts in terms of the accuracy of node classification prediction and out-ofdistribution detection based on six real network datasets.

heading: 1 INTRODUCTION
text: Inherent uncertainties introduced by different root causes have emerged 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) (Kipf & Welling, 2016; Veličković et al., 2018) have gained tremendous attention in the data science community. Despite their superior performance in semi-supervised node classification and/or regression, they didn’t allow to deal with various types of uncertainties. Predictive uncertainty estimation (Malinin & Gales, 2018) using Bayesian NNs (BNNs) has been explored for classification prediction or regression in the computer vision applications, with wellknown uncertainties, aleatoric and epistemic uncertainties. Aleatoric uncertainty only considers data uncertainty derived from statistical randomness (e.g., inherent noises in observations) while epistemic uncertainty indicates model uncertainty due to limited knowledge or ignorance in collected data. On the other hand, in the belief or evidence theory, Subjective Logic (SL) (Josang et al., 2018) considered vacuity (or lack of evidence) as uncertainty in an subjective opinion. Recently other uncertainties such as dissonance, consonance, vagueness, and monosonance (Josang et al., 2018) are also introduced. This work is the first that considers multidimensional uncertainty types in both DL and belief theory domains to predict node classification and out-of-distribution (OOD) detection. To this end, we incorporate the multidimensional uncertainty, including vacuity, dissonance, aleatoric uncertainty, and epistemic uncertainty in selecting test nodes for Bayesian DL in GNNs. We perform semi-supervised node classification and OOD detection based on GNNs. By leveraging the modeling and learning capability of GNNs and considering multidimensional uncertainties in SL, we propose a Bayesian DL framework that allows simultaneous estimation of different uncertainty types associated with the predicted class probabilities of the test nodes generated by GNNs. We treat the predictions of a Subjective Bayesian GNN (S-BGNN) as nodes’ subjective opinions in a graph modeled as Dirichlet distributions on the class probabilities, and learn the S-BGNN model by collecting the evidence from the given labels of the training nodes (see Figure 1). This work has the following key contributions: • A Subjective Bayesian framework to predictive uncertainty estimation for GNNs. Our pro-
posed framework directly predicts subjective multinomial opinions of the test nodes in a graph,
with the opinions following Dirichlet distributions with each belief probability as a class probability. Our proposed framework is a generative model, so it cal be highly applicable across all GNNs and allows simultaneously estimating different types of associated uncertainties with the class probabilities. • Efficient approximate inference algorithms: We propose a Graph-based Kernel Dirichlet distribution Estimation (GKDE) method to reduce error in predicting Dirichlet distribution. We designed an iterative knowledge distillation algorithm that treats a deterministic GNN as a teacher network while considering our proposed Subjective Bayesian GNN model (a realization of our proposed framework for a specific GNN) as a distilled network. This allows the expected class probabilities based on the predicted Dirichlet distributions (i.e., outputs of our trained Bayesian model) to match the predicted class probabilities of the deterministic GNN model, along with uncertainty estimated in the predictions. • Comprehensive experiments for the validation of the performance of our proposed framework. Based on six real graph datasets, we compared the performance of our propose framework with that of other competitive DL algorithms. For a fair comparison, we tweaked the DL algorithms to consider various uncertainty types in predicted decisions.

heading: 2 RELATED WORK
text: Epistemic Uncertainty in Bayesian Deep Learning (BDL): Machine/deep learning (M/DL) research 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) (Gal, 2016). A BDL framework was presented to estimate both AU and DU simultaneously in regression settings (e.g., depth regression) and classification settings (e.g., semantic segmentation) (Kendall & Gal, 2017). Later, a new type of uncertainty, called distributional uncertainty (DU), is defined based on distributional mismatch between the test and training data distributions (Malinin & Gales, 2018). Dropout variational inference (Gal & Ghahramani, 2016) is used as one of key approximate inference techniques in BNNs. Other methods (Eswaran et al., 2017; Zhang et al., 2018) measure overall uncertainty in node classification but didn’t consider uncertainty decomposition and GNNs. Uncertainty Quantification in Belief/Evidence Theory: In the belief/evidence theory domain, uncertainty reasoning has been substantially explored, such as Fuzzy Logic (De Silva, 2018), DempsterShafer Theory (DST) (Sentz et al., 2002), or Subjective Logic (SL) (Jøsang, 2016). Belief theory focuses on reasoning of inherent uncertainty in information resulting from unreliable, incomplete, deceptive, and/or conflicting evidence. SL considered uncertainty in subjective opinions in terms of vacuity (i.e., lack of evidence) and vagueness (i.e., failing in discriminating a belief state) (Jøsang, 2016). Recently, other uncertainty types have been studied, such as dissonance (due to conflicting evidence) and consonance (due to evidence supporting composite states) (Josang et al., 2018). In deep NNs, SL is considered to train a deterministic NN for supervised classification in computer vision applications (Sensoy et al., 2018). However, they didn’t consider a generic way of estimating multidimensional uncertainty using Bayesian DL for GNNs used for the applications in graph data.

heading: 3 PROPOSED APPROACH
text: Now we define the problem of uncertainty-aware semi-supervised node classification and then present a Bayesian GNN framework to address the problem.

heading: 3.1 PROBLEM DEFINITION
text: Given an input graph G = (V,E, r,yL), where V = {1, · · · , N} is a ground set of nodes, E ⊆ V×V is a ground set of edges, r = [r1, · · · , rN ]T ∈ RN×d is a node-level feature matrix, ri ∈ Rd is the feature vector of node i, yL = {yi | i ∈ L} are the labels of the training nodes L ⊂ V, and yi ∈ {1, . . . ,K} is the class label of node i. We aim to predict: (1) the class probabilities of the testing nodes: pV\L = {pi ∈ [0, 1]K | i ∈ V \ L}; and (2) the associated multidimensional uncertainty estimates introduced by different root causes: uV\L = {ui ∈ [0, 1]m | i ∈ V \ L}, where pi,k is the probability that the class label yi = k and m is the total number of uncertainty types.

heading: 3.2 MULTIDIMENSIONAL UNCERTAINTY QUANTIFICATION
text: Multiple uncertainty types may be estimated, such as aleatoric uncertainty, epistemic uncertainty, vacuity, dissonance, among others. The estimation of the first two types of uncertainty relies on the design of an appropriate Bayesian DL model with parameters, θ. Following (Gal, 2016), node i’s aleatoric uncertainty is: Aleatoric[pi] = EProb(θ|G) [ H(yi|r;θ) ] , where H(·) is Shannon’s entropy of Prob(pi|r;θ). The epistemic uncertainty of node i is estimated by: Epistemic[pi] = H [ EProb(θ|G)[(yi|r;θ)] ] − EProb(θ|G) [ H(yi|r;θ) ] (1)
where the first term indicates entropy (or total uncertainty). Vacuity and dissonance can be estimated based on the subjective opinion for each testing node i (Josang et al., 2018). Denote i’s subjective opinion as [bi1, · · · , biK , vi], where bik(≥ 0) is the belief mass of the k-th category, vi(≥ 0) is the uncertainty mass (i.e., vacuity), and K is the total number of categories, where ∑K k=1 bik + vi = 1. i’s dissonance is obtained by:
ω(bi) = K∑ k=1 (bik∑Kj=1,j 6=k bijBal(bij , bik)∑K j=1,j 6=k bij ) , (2)
where the relative mass balance between a pair of belief masses bij and bik is expressed by Bal(bij , bik) = 1 − |bij − bik|/(bij + bik). To develop a Bayesian GNNs framework that predicts multiple types of uncertainty, we estimate vacuity and dissonance using a Bayesian model. In SL, a multinomial opinion follows a Dirichlet distribution, Dir(pi|αi), where αi ∈ [1,∞]K represents the distribution parameters. Given Si = ∑K k=1 αik, belief mass bi and uncertainty mass vi can be obtained by bik = (αik − 1)/Si and vi = K/Si.

heading: 3.3 PROPOSED BAYESIAN DEEP LEARNING FRAMEWORK
text: Let p = [p1, . . . ,pN ]> ∈ RN×K denote the class probabilities of the node in V, where pi = [pi1, . . . , piK ]
> refers to the class probabilities of a specific node i. As shown in Figure 1, our proposed Bayesian GNN framework can be described by the generative process: • Sample θ from a predefined prior distribution, i.e., N (0, I). • For each node i ∈ V: (1) Sample the class probabilities pi from a Dirichlet distribution: Dir(pi|αi),
where αi = fi(r;θ) is parameterized by a GNN network α = f(r;θ) : RN×d → [1,∞]N×K that takes the attribute matrix r as input and directly outputs all the node-level Dirichlet parameters α = [α1, · · · ,αN ], and θ refer to the hyper-parameters of the GNN network; and (2) Sample yi ∼ Cat(yi|pi), a categorical distribution on pi.
In this design, the graph dependencies among the class labels in yL and yV\L are modeled via the GNN network f(r;θ). Our proposed framework is different from the traditional Bayesian GNN network (Zhang et al., 2018) in that the output of the former are the parameters of node-level Dirichlet distributions (α), but the output of the latter are directly node-level class probabilities (p). The conditional probability of p, Prob(p|r;θ), can be obtained by:
Prob(p|r;θ) = ∏N
i=1 Dir(pi|αi), αi = fi(r;θ) (3)
where the Dirichlet probability function Dir(pi|αi) is defined by:
Dir(pi|αi) = Γ(Si)∏K
k=1 Γ(αik)
∏K k=1 pαik−1ik , Si = ∑K k=1 αik (4)
Based on the proposed Bayesian GNN framework, the joint probability of y conditioned on the input graph G and the node-level feature matrix r can be estimated by:
Prob(y|r;G) = ∫ ∫ Prob(y|p)Prob(p|r;θ)Prob(θ|G)dpdθ, (5)
where Prob(θ|G) is the posterior probability of the parameters θ conditioned on the input graph G, which are estimated in Sections 3.4 and 3.6. The aleatoric uncertainty and the epistemic uncertainty can be estimated using the equations described in Section 3.2. The vacuity associated with the class probabilities (pi) of node i can be estimated by: Vacuity(pi) = EProb(θ|G)[vi] = EProb(θ|G) [ K/ ∑K k=1 αik ] . The dissonance of node i
is estimated as: Disso.[pi] = EProb(θ|G) [ ω(bi) ] , where ω(bi) is defined in Eq. (2).

heading: 3.4 BAYESIAN INFERENCE WITH DROPOUT
text: The marginalization in Eq. (5) is generally intractable. A dropout technique is used to obtain an approximate solution and use samples from the posterior distribution of models (Gal & Ghahramani, 2016). Due to this reason, we adopt a dropout technique in (Gal & Ghahramani, 2015) for variational inference in Bayesian CNNs 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 identify a posterior distribution over the network’s weights, given the input graph G and observed labels yL by Prob(θ | G), where θ = {W1, . . . ,WL, b1, ..., bL}, L is the total number of layers and Wi refers to the GNN’s weight matrices of dimensions Pi × Pi−1, and bi is a bias vector of dimensions Pi for layer i = 1, · · · , L. Since the posterior distribution is intractable, we use 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:
min γ
KL(q(θ,γ)‖Prob(θ|G)) (6)
where γ = {M1, . . . ,ML,m1, . . . ,mL} are the variational parameters, where Mi ∈ RPi×Pi−1 and mi ∈ RPi . We define Wi in q(θ,γ) by:
Wi = Midiag([zij ]Pij=1), zij ∼ Bernoulli(di) for i = 1, . . . , L, j = 1, . . . , Pi−1 (7)
where 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 (Gal & Ghahramani, 2015). The dropout probabilities, di’s, can be optimized or fixed (Kendall et al., 2015). For simplicity, we fix di’s in our experiments, as it is beyond the scope of our study. In (Gal & Ghahramani, 2015), the minimization of the cross entropy (or square error) loss function is proven to minimize the KL-divergence (see Eq. (6)). 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 a GNN model with dropout before every weight layer and dropout at test time to sample from the approximate posterior (i.e., stochastic forward passes, a.k.a. Monte Carlo dropout; see Eq. (8)). At the test stage, we infer the joint probability Eq. (5) by:
Prob(y|r;G) ≈ 1 M ∑M m=1 ∫ Prob(y|p)Prob(p|r;θ(m))dp, θ(m) ∼ q(θ), (8)
which can infer the Dirichlet parameters α as: α ≈ 1M ∑M m=1 f(r,θ
(m)), θ(m) ∼ q(θ). As our model is a generative model to predict Dirichlet distribution parameters, we use a loss function to compute its Bayes risk with respect to the sum of squares loss ‖y− p‖22 by:
L(γ) = ∑
i∈L
∫ ‖yi − pi‖22 · Prob(pi|r;γ)dpi = ∑ i∈L ∑K j=1 ( yij − E[pij ] )2 + Var(pij) (9)
Eq. (9) aims to minimize the prediction error and variance, leading to maximizing classification accuracy of each training node by removing excessive misleading evidence (Sensoy et al., 2018).

heading: 3.5 GRAPH-BASED KERNEL DIRICHLET DISTRIBUTION ESTIMATION
text: To better learn the Dirichlet distribution from our Bayesian GNN framework, we proposed a GraphBased Kernel Dirichlet Distribution Estimation (GKDE). The key idea of GKDE is estimating prior Dirichlet distribution parameters for each node based on training nodes (see Figure 1 (b)). And then, we leave prior Dirichlet distribution in the training process to learn two trends: (i) nodes with high vacuity (due to lack of evidence) will be shown far from training nodes; and (ii) nodes with high dissonance (due to conflicting evidence) will be shown in the class boundary. Based on SL, let each training node represent one evidence for its class label. Denote the contribution of evidence estimation for target node j from node i by h(yi, dis(i, j)) = [h1, . . . , hk, . . . , hK ] ∈ [0, 1]K and hk(yi, dis(i, j)) is obtained by:
hk(yi, dis(i, j)) = { 0 yi 6= k σ √ 2π · g(dis(i, j)) yi = k (10)
where g(dis(i, j)) = 1 σ √ 2π e−
dis(i,j)2
2σ2 is the Gaussian kernel function to estimate the distribution effect between nodes i and j, and dis(i, j) means the node distance (shortest path between nodes i and j), and σ is the bandwidth parameter. The prior evidence estimation based GKDE: êj =∑ i∈L h(yi, dis(i, j)), and the prior Dirichlet distribution α̂j = êj + 1. During training process, we minimize the KL-divergence between model predictions of Dirichlet distribution and prior distribution: min KL[Dir(α)‖Dir(α̂)].

heading: 3.6 A TEACHER NETWORK FOR REFINED INFERENCE
text: Our key contribution is that the proposed Bayesian GNN model is capable of estimating various uncertainty types to predict existing GNNs. As one of the preferred features, the expected class probabilities generated by our Bayesian GNNs model should be consistent with the predicted class probabilities of the GNN model. In addition, our Bayesian GNN model is a generative model and may not necessarily always outperform GNN models (i.e., discriminative models) for the task of node classification prediction when uncertainty-based prediction is not fully benefited. To refine the inference of our proposed model, we leverage the principles of Knowledge Distillation in DL (Hinton et al., 2015). In particular, we consider our proposed model as a distilled model and a deterministic GNN model as a teacher model, as shown in Figure 1 (c). The key idea is to train our proposed model to imitate the outputs of the teacher network on the class probabilities while minimizing the loss function of our proposed model. We observed that the modeling of data uncertainty in our proposed model provides useful information to further improve the accuracy of the deterministic GNN model. Therefore, we consider propagating the useful information back to the teacher model to help train itself. Let us denote Prob(y | r;β) as the joint probability of class labels via a deterministic GNN model, where β refers to model parameters. The probability function Prob(y | r;γ,G) is estimated based on Eq. (8) using the variational parameters γ. We measure the closeness between Prob(y | r;β) and Prob(y | r;γ,G) with KL-divergence to be minimized while minimizing their own loss functions based on the labeled nodes. This leads to solving the following optimization problem:
minγ,β L(γ) + L(β) + λ · ( KL[Prob(y | r;γ,G) ‖ Prob(y | r;β)] + KL[Dir(α)‖Dir(α̂)] ) (11)
where L(β) is the loss function (i.e., cross entropy) of the deterministic GNN model and λ is a trade-off parameter. Our inference algorithm using backpropagation is detailed in the Appendix.

heading: 4 EXPERIMENTS
text: In this section, we describe our experimental settings and demonstrate the performance of our proposed model based on semi-supervised node classification. For the performance comparison and analysis of our model and other existing counterparts, we demonstrate and analyze the obtained results in terms of the overall classification accuracy.

heading: 4.1 DATASETS
text: We use six datasets, including three citation network datasets (Sen et al., 2008) (i.e., Cora, Citeseer, Pubmed) and three new datasets (Shchur et al., 2018) (i.e., Coauthor Physics, Amazon Computer, and Amazon Photo). We summarize the description and experimental setup of the used datasets in Table 1. 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 (Yang et al., 2016) 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 (Shchur et al., 2018) for Coauthor Physics, Amazon Computer, and Amazon Photo datasets, for fair comparison.

heading: 4.2 COMPARING SCHEMES
text: We conduct the extensive comparative performance analysis based on our proposed models and a number of other state-of-the-art counterparts. Our proposed Subjective GNN models are: (1) S-GNN (Subjective GNN) with vacuity and dissonance estimation, which outputs subjective opinion (Dirichlet distribution) instead of softmax probability; (2) S-BGNN (Subjective Bayesian GNN), Subjective Graph Neural Network with Bayesian framework with multiple type uncertainty estimation; (3) S-BGNN-T (S-BGNN with Teacher network), help improve the expected class probability estimation; (4) S-BGNN-T-K (S-BGNN-T with GKDE), help improve the Dirichlet distribution estimation. Here we use two popular GNN models: GCN (Kipf & Welling, 2016) and GAT (Veličković et al., 2018).
Our proposed models are compared against a number of the state-of-the-art counterparts. For evaluating three citation datasets (i.e., Cora, Citeseer, Pubmed), we compared our models with: (1) GCN (Kipf & Welling, 2016); (2) GAT (Veličković et al., 2018); (3) nonparametric Bayesian GCNN (BGCNN) (Pal et al., 2019); (4) Bayesian GCN (Zhang et al., 2019); (5) MC-dropout for Bayesian GNN (GCN-Drop, GAT-Drop) (Ryu et al., 2019); (6) skip-gram based graph embeddings (DeepWalk) (Perozzi et al., 2014); (7) iterative classification algorithm (ICA) (Lu & Getoor, 2003); and (8) Planetoid (Yang et al., 2016). We selected these for the comparison with our models based on (Veličković et al., 2018) for fair comparison with the latest comparable models. Using Coauthor Physics, Amazon Computer, and Amazon Photo, we compared the performance of our models with that of GCN and GAT(Shchur et al., 2018), we can not show SGAT (S-BGAT) due to memory limited, More details of model setup refer to the Appendix A.

heading: 4.3 EXPERIMENTAL RESULTS & ANALYSIS
text: In Table 2, we summarized the mean percentage of classification accuracy with a standard deviation of each model compared in this experiment. The results prove that our model achieves the best accuracy result across all datasets except Citeseer. To be specific, our proposed S-BGCN-T is able to improve over GCN by a margin of 0.7%, 1.2%, 0.2%, 0.2%, 4.5% and 0.7% on Cora, Citeseer, Pumbed, Coauthor Physics, Amazon Computer, and Amazon Photo, respectively. In addition, our proposed S-BGAT-T model improves 0.8% for both Cora and Citeseer datasets over GAT. Notice that S-BGNN-T even outperforms S-BGNN particularly on the Cora and Citeseer dataset (i.e., 1% - 1.3% increase). These results prove that the teacher network can prevent overfitting, leading to a further improvement in classification prediction.

heading: 5 UNCERTAINTY EXPERIMENT AND ANALYSIS
text: In Section 4, we showed that our S-BGNN-T improves prediction performance. In this section, we study the effectiveness of prediction based on different types of uncertainty. We studied the different types of uncertainty-aware node classification and out-of-distribution in terms of the area under the ROC (AUROC) and Precision-Recall (AUPR) curves in both experiments as in (Hendrycks & Gimpel, 2016) for three citation network datasets. For the OOD detection, we randomly selected 1-3 categories as OOD categories and trained the models only based on training nodes of the other categories. Due to the space constraint, we summarize the description of datasets and experimental setup for the OOD detection in the Appendix. To better evaluate our multiple uncertainties, we compare our model with two baseline models: (1) GCN which uses GCN (Kipf & Welling, 2016) with the softmax probability entropy measuring uncertainty; and (2) GCN-Drop, where one of the two uncertainty types (i.e., aleatoric, or epistemic uncertainty) adapts Monte-Carlo Dropout (Gal & Ghahramani, 2016) into the GCN model (Ryu et al., 2019). In the OOD, we also consider Distributional uncertainty (Malinin & Gales, 2018).

heading: 5.1 QUALITY OF UNCERTAINTY METRICS
text: In Figure 2, we used S-BGCN-T-K to predict node classification when test nodes are selected based on the lowest uncertainty for a given type. First of all, all uncertainty types show decreasing precision as recall increases. This implies that all uncertainty types are to some extent the indicators of prediction accuracy because low uncertainty increases prediction accuracy. In Figure 2, we can observe almost 100% performance of precision when recall is close to zero on Cora and over 95% on Pubmed. Further, the outperformance of Dissonance uncer-
tainty is obvious among all. This indicates that low uncertainty with few conflicting evidence is the most critical factor to enhance classification prediction accuracy, compared to low extent of other uncertainty types. In addition, although epistemic uncertainty was very low, epistemic uncertainty performs the worst among all. This also indicates that epistemic uncertainty is not necessarily helpful to enhance prediction accuracy in semi-supervised node classification. Lastly, we found that vacuity is not as important as dissonance because accurate prediction is not necessarily dependent upon a large amount of information, but is more affected by less conflicting (or more agreeing) evidence to support a single class. In Table 3, although all BGCN-T models with the five different uncertainty types do not necessarily outperform all the existing models (i.e., GCN Entropy and variants of GCN-Drop.), the outperformance of Dissonance is fairly impressive. This result confirmed that low uncertainty caused by dissonance is the key to maximize node classification prediction accuracy. When compare S-BGCN-T and S-BGCN-T-K, we found GKDE can only help improve performance a little. To better understand different uncertainty types, we used t-SNE (Maaten & Hinton, 2008) to represent the computed
feature representations of a pre-trained S-BGCN-T-K model’s first hidden layer on the Cora dataset in Figure 3.

heading: 5.2 OUT-OF-DISTRIBUTION DETECTION
text: In this section, we discuss how different uncertainty types can prove the performance in the outof-distribution (ODD) detection. In Table 4, we considered 6 uncertainties with 3 models for our performance comparison. Note that Distributional uncertainty is the the most recent model showing the best performance in the OOD detection. Across the three citation network datasets, particularly SBGCN-T-K Vacuity showed significantly better performance, strikingly outperforming Distributional uncertainty. Notice that S-BGCN-T-K outperforms S-BGCN-T (i.e., 4% - 7% increase), especially the improvement of vacuity. These result prove that the GKDE can improve the Dirichlet distribution estimation, leading to a better uncertainty estimation.

heading: 6 CONCLUSION
text: In this work, we proposed a Subjective Bayesian GNNs framework for uncertainty-aware semisupervised node classification and out-of-distribution (OOD) detection for GNNs. Our proposed framework provides an effective, efficient way of predicting node classification and detecting OOD considering multiple uncertainty types. We leveraged the estimation of various types of uncertainty from both DL and evidence/belief theory domains. In addition, We leveraged the Teacher network to help refine the classification probability and GKDE to accuractly estimate Dirichlet distribution. The key findings from this study include: • For the overall classification prediction, our proposed S-BGNN-T outperformed the competitive
baselines on most datasets. The key role to improve the accuracy is Teacher Network. • For the node classification prediction considering various uncertainty types, we found that disso-
nance (i.e., uncertainty derived from conflicting evidence) played a significant role to improve classification prediction accuracy. • For the OOD detection, vacuity uncertainty played a key role when S-BGCN-T-K is used to detect OOD. This means that less information and/or more randomness (or less predictability) enables detecting OOD more effectively. More impressively, GKDE can indeed help to estimate Dirichlet distribution accurately so that enhance the vacuity performance. Also vacuity outperformed the most recent counterpart, Distributional uncertainty.

heading: A APPENDIX

heading: A.1 SOURCE CODE
text: For review purpose, the source code and datasets are accessible at https://www.dropbox. com/sh/cs5gs2i1umdx4b6/AAC-r_EYRw9lryk95giqW8-Fa?dl=0

heading: DESCRIPTION OF DATASETS
text: Cora, Citeseer, and Pubmed (Sen et al., 2008): These are citation network datasets, where a network is a directed network where 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.
Coauthor Physics, Amazon Computers, and Amazon Photo (Shchur et al., 2018): Coauthor Physics is the dataset for co-authorship graphs based on the Microsoft Academic Graph from the KDD Cup 2016 Challenge1. 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 (McAuley et al., 2015), 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.
In semi-supervised node classification task,the training and test nodes are selected based on (Sen et al., 2008) for the citation network datasets and are randomly selected for the Coauthor Physics, Amazon Computers, and Amazon Photo.

heading: A.2 EXPERIMENTAL SETUP FOR OUT-OF-DISTRIBUTION (OOD) DETECTION
text: For OOD detection, we summarize the experiment setup for the use of the three citation network datasets (i.e., Cora, Citeseer, and Pubmed) in Table 5. In this setting, we still focus on the semisupervised node classification task, but only part of node categories are not using for training. Hence, we suppose that our model only outputs partial categories (as we don’t know the OOD category). For example, Cora dataset, we train 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.

heading: A.3 CALCULATION OF AUPR AND AUROC
text: For the calculation of precision, recall, TPR, and FPR, we select a certain φ % of nodes out of test nodes to label them as positive (correct) based on the extent of uncertainty, the lowest uncertainty for classification prediction and the highest uncertainty for OOD detection. And the remaining test nodes (i.e., 100− φ %) are labeled as negative. Each test node’s prediction is checked with its ground truth to derive AUPR and AUROC.
1KDD Cup 2016 Dataset: Online Available at https://kddcup2016.azurewebsites.net/

heading: TIME COMPLEXITY ANALYZE
text: BGCN has a similar time complexity with GCN while BGCN-T has the double complexity of GCN. In the revised paper, we will add a table showing Big-O complexity of all schemes considered. 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, and F is the number of features for the output layer, the complexity of the compared schemes are: O(|E|CF ) for GCN, O(|E|CF ) for S-BCGN, O(2|E|CF ) for S-BCGB-T and S-BCGB-T-K,O(|V|CF+ |E|F ) for GAT, andO(2|V|CF+2|E|F ) for S-BGAT-T and S-BGAT-T-K.

heading: A.4 MODEL SETUPS FOR SEMI-SUPERVISED NODE CLASSIFICATION
text: Our models are initialized using Glorot initialization (Glorot & Bengio, 2010) and trained to minimize loss using the Adam SGD optimizer (Kingma & Ba, 2014). As our proposed models (i.e., S-BGCNT-K, S-BGAT-T-K) need a discriminative model to refine inference, we use standard GCN and GAT models as teacher networks for S-BGCN-T-K and S-BGAT-T-K, respectively. For the S-BGCN-T-K model, we use the early stopping strategy (Shchur et al., 2018) on Coauthor Physics, Amazon Computer and Amazon Photo datasets while non-early stopping strategy is used in citation datasets (i.e., Cora, Citeseer and Pubmed). We set bandwidth σ = 1 for all datasets in GKDE, and set trade off parameters λ = min(1, t/200) (where t is the index of a current training epoch); and other hyperparameter configurations are summarized in Table 6. The S-BGAT-T-K model has two dropout probabilities, which are a dropout on features and a dropout on attention coefficients, as showed in Table 7. 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 (Veličković et al., 2018). Note that lack of memory (we used one Titan X GPU, 12 GB memory), we could not obtain the result for GAT (also S-BGAT) on Coauthor Physics, Amazon Computer and Amazon Photo, which are very dense datasets.
For semi-supervised node classification, we use 50 random weight initialization for our models on Citation network datasets. For Coauthor Physics, Amazon Computer and Amazon Photo datasets, we report the result based on 10 random train/validation/test splits. In both effect of uncertainty on classification prediction accuracy and the OOD detection, we report 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 use the same hyperparameter configurations as in Table 6, except S-BGCN-T-K Epistemic using 20,000 epochs to obtain the best result. For baseline models, GCN-Drop. models use the same hyperparameters as in Table 6 to achieve the best performance, also using 20,000 training epochs for GCN-Drop. Epistemic. GCN Entropy uses the same hyperparameter configurations in (Kipf & Welling, 2016).

heading: A.5 ALGORITHM FOR OUR ALGORITHM
text: Algorithm 1: S-BGNN-T-K with jointly train for Teacher network Input: G = (V,E, r) and yL Output: pV\L, uV\L
1 ` = 0; 2 Set hyper-parameters; 3 Initialize the parameters γ, β; 4 Calculate the prior Dirichlet distribution Dir(α̂); 5 repeat 6 Forward pass to compute α, Prob(pi|r;G), Prob(yi|r;β) for i ∈ V; 7 Compute joint probability Prob(y|r;G), Prob(y|r;β); 8 Backward pass via the chain-rule the calculate the sub-gradient gradient: g(`) = ∇ΘL(Θ) 9 Update parameters using step size η via Θ(`+1) = Θ(`) − η · g(`)
10 ` = `+ 1; 11 until convergence 12 Calculate pV\L, uV\L 13 return pV\L, uV\L
Algorithm 2: S-BGNN-T-K with pre-train for Teacher network Input: G = (V,E, r) and yL Output: pV\L, uV\L
1 ` = 0; 2 Set hyper-parameters; 3 Initialize the parameters γ, β; 4 Calculate the prior Dirichlet distribution Dir(α̂); 5 Pre-train the Teacher Network to get Prob(y|r;β) 6 repeat 7 Forward pass to compute α, Prob(pi|r;G) for i ∈ V; 8 Compute joint probability Prob(y|r;G); 9 Backward pass via the chain-rule the calculate the sub-gradient gradient: g(`) = ∇ΘL(Θ)
10 Update parameters using step size η via Θ(`+1) = Θ(`) − η · g(`) 11 ` = `+ 1; 12 until convergence 13 Calculate pV\L, uV\L 14 return pV\L, uV\L

heading: B ADDITIONAL EXPERIMENT RESULTS
text: Further experiment have been run in addition to the uncertainty analysis in section 5. First, we show the ablation experiment for each compents we proposed. Second, we show more uncertainty visualization result in network node classification for Citeseer dataset. To better understand the performance of uncertainty quality clearly for each uncertainty, we show the AUROC and AUPR curves for all models and uncertainties.

heading: B.1 ABLATION EXPERIMENTS
text: We conducted an additional experiment to ensure the benefit of the teacher network. We anticipate that the graph kernel prior will improve the estimation accuracy of Dirichlet distribution. However, due to the space constraint, we didn’t show the classification results without using the graph kernel prior. In the revised version, we added a detailed ablation study in the revised paper in order to clearly demonstrate the contribution 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 2); and (2) GKDE (graph kernel prior) using the uncertainty estimates can enhance OOD detection (i.e., 4% - 7% increase, as shown in Table 9).

heading: B.2 GRAPH EMBEDDING REPRESENTATIONS OF DIFFERENT UNCERTAINTY TYPES
text: To better understand different uncertainty types, we used t-SNE (t-Distributed Stochastic Neighbor Embedding (Maaten & Hinton, 2008)) to represent the computed feature representations of a pretrained BGCN-T model’s first hidden layer on the Citeseer dataset.
Six Classes on Citeseer Dataset: In Figure 4 (a), a node’s color denotes a class on the Citeseer dataset where 6 different classes are shown in different colors. Figure 4 (b) is our prediction result.
For Figures 4 (c)-(f), the extent of uncertainty is presented where a blue color refers to the lowest uncertainty (i.e., minimum uncertainty) while a red color indicates the highest uncertainty (i.e., maximum uncertainty) based on the presented color bar. 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 4 (c), although most training nodes show low uncertainty, we observe majority of test nodes in the mid cluster show high uncertainty as appeared in red.
Dissonance: In Figure 4 (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 4 (e), a lot of nodes show high uncertainty with larger than 0.5 except a small amount of training nodes with low uncertainty. High aleatoric uncertainty positively affects, showing high performance in OOD detection.
Epistemic uncertainty: In Figure 4 (f), most nodes show very low epistemic uncertainty because uncertainty derived from model parameters can disappear as they are trained well. Therefore, nondistinctive low uncertainty for most nodes do not help much to select good test nodes to improve performance in node classification.

heading: B.3 PR AND ROC CURVES
text: AUPRC for the OOD Detection: Figure 6 shows the AUPRC for the OOD detection when S-BGCNT-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), S-BGCN-T-K Epistemic even performed worse than the baseline (i.e., S-BGCN-T-K Random). This is because epistemic uncertainty cannot distinguish the flat Dirichlet distribution (α = (1, . . . , 1)) from sharp Dirichlet distribution (α = (10, . . . , 10)), which leads to no effective selection of test nodes for improving the performance in OOD detection. In addition, unlike AUPR in node classification prediction, which showed the best performance in S-BGCN-T-K Dissonance (see Figure 5), 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 observe Vacuity performs the best among all while S-BGCN-T-K Entropy also performs fairly well as the third best. From this finding, we can claim that to improve OOD detection, more randomness with high aleatoric uncertainty and less information with high vacuity can help boost the accuracy of the OOD detection. Although the uncertainty level observed from aleatoric uncertainty and entropy was quite similar, the performance in OOD detection is not necessarily similar, as shown in Figures 6 (b) and (c) on Citeseer and Pubmed. The reason is that BCGN-T Aleatoric provides test nodes with more distinctive uncertainty levels while BCGN-T Entropy doesn’t. This is because BCGN-T Entropy combines the aleatoric and epistemic uncertainty where epistemic uncertainty is mostly highly low, ultimately leading to poor distinctions of nodes based on different uncertainty levels.
AUROC for the OOD Detection: First, we investigated the performance of our proposed S-BGCNT-K models when test nodes are selected based on seven different criteria (i.e., 6 uncertainties and random). Like AUPR in Figure 5, based on S-BGCN-T-K, we considered a baseline by selecting
test nodes randomly while five different uncertainty types are used to select test nodes based on the order of high uncertainty. For AUROC in Figure 7, we observed much better performance in most S-BGCN-T-K models with all uncertainty types except epistemic uncertainty. Although epistemic uncertainty is known to be effective to improve OOD detection (Kendall & Gal, 2017) in computer vision applications, our result showed fairly poor performance compared to the case other uncertainty types are used. This is because our experiment is conducted with a very small of training nodes (i.e., 3% on Cora, 2% on Citeseer, 0.2% on Pubmed) which is highly challenging to observe high performance particularly with epistemic uncertainty. Recall that we used 200 epochs to train nodes for all models except BCGN-T Epistemic which was trained with 20,000 epochs. In this experiment, even S-BGCN-T-K Vacuity performed the best although S-BGCN-T-K Dissonance, S-BGCN-T-K Aleatoric, or S-BGCN-T-K Entropy performs comparably. But on Citeseer and Pubmed datasets, we also observed relatively low performance with S-BGCN-T-K Dissonance. This finding is also well aligned with what we observed in Table 4 (in paper). S-BGCN-T-K Vacuity performs the best on all three datesets. Obviously S-BGCN-T-K Vacuity outperform S-BGCN-T-K Distributional in OOD detection.

heading: B.4 ANALYZE FOR EPISTEMIC IN OOD DETECTION
text: In OOD detection, epistemic uncertainty performed the worst because it cannot distinguish the flat Dirichlet distribution (α = (1, . . . , 1)) from sharp Dirichlet distribution (α = (10, . . . , 10)), resulting poor performance in OOD detection. Unlike AUPR in node classification prediction with outperformance in S-BGCN-T-K Dissonance (see Figure 2), S-BGCN-T-K Dissonance showed the second worst performance among the proposed S-BGCN-T-K models with other uncertainty types. This implies that less conclusive belief mass does not help OOD detection.
Although epistemic uncertainty is known to be effective to improve OOD detection (Kendall & Gal, 2017) in computer vision applications, our result showed fairly poor performance compared to the case other uncertainty types are used. This is because our experiment is conducted with a very small of training nodes (i.e., 3% on Cora, 2% on Citeseer, 0.2% on Pubmed) which is highly challenging to observe high performance particularly with epistemic uncertainty.

heading: C DERIVATIONS FOR UNCERTAINTY MEASURES AND KL DIVERGENCE
text: This appendix provides the derivations and shows how calculate the uncertainty measures discussed in section 3 for BGCN. Additionally, it describes how to calculate the joint probability, Dirichlet parameters and KL-divergence between Prob(y|r;β) and Prob(y|r;γ,G).

heading: C.1 UNCERTAINTY MEASURES
text: Vacuity uncertainty of Bayesian Graph neural networks for node i:
Vacuity[pi] = EProb(θ|G)[vi]
= EProb(θ|G) [ K/ K∑ k=1 αik ] ≈ Eq(θ) [ K/
K∑ k=1 αik ] ≈ 1
M M∑ m=1 [ K/ K∑ k=1 α (m) ik ] , α(m) = f(r,θ(m)), θ(m) ∼ q(θ)
Dissonance uncertainty of Bayesian Graph neural networks for node i: Disso.[pi] = EProb(θ|G) [ ω(bi) ] ≈ Eq(θ) [ ω(bi)
] ≈ 1
M M∑ m=1 [ ω(bi) ] , θ(m) ∼ q(θ)
and
ω(bi) = K∑ k=1 (bik∑Kj=1,j 6=k bijBal(bij , bik)∑K j=1,j 6=k bij ) ,
where the relative mass balance between a pair of belief masses bij and bik is expressed by Bal(bij , bik) = 1− |bij − bik|/(bij + bik). Aleatoric uncertainty of Bayesian Graph neural networks for node i, followed (Malinin & Gales, 2018):
Aleatoric[pi] = EProb(θ|G) [ H(yi|r;θ) ] ≈ Eq(θ) [ H(yi|r;θ)
] ≈ 1
M M∑ m=1 H [ (yi|r;θ(m)) ] , θ(m) ∼ q(θ)
≈ 1 M M∑ m=1 K∑ j=1 Prob(yi = j|r;θ(m)) log ( Prob(yi = j|r;θ(m)) ) , θ(m) ∼ q(θ)
Epistemic uncertainty of Bayesian Graph neural networks for node i, followed (Gal, 2016): Epistemic[pi] = H [ EProb(θ|G)[(yi|r;θ)] ] − EProb(θ|G) [ H(yi|r;θ) ] ≈ H [ Eq(θ)[(yi|r;θ)] ] − Eq(θ) [ H(yi|r;θ)
] ≈ H
[ 1 M M∑ m=1 Prob(yi|r;θ(m)) ] − 1 M M∑ m=1 H [ (yi|r;θ(m)) ] , θ(m) ∼ q(θ)

heading: C.2 JOINT PROBABILITY
text: At the test stage, we infer the joint probability by: p(y|r;G) = ∫ ∫ Prob(y|p)Prob(p|r;θ)Prob(θ|G)dpdθ
≈ ∫ ∫ Prob(y|p)Prob(p|r;θ)q(θ)dpdθ
≈ 1 M M∑ m=1 ∫ Prob(y|p)Prob(p|r;θ(m))dp, θ(m) ∼ q(θ)
≈ 1 M M∑ m=1 ∫ N∑ i=1 Prob(yi|pi)Prob(pi|r;θ(m))dpi, θ(m) ∼ q(θ)
≈ 1 M M∑ m=1 N∑ i=1 ∫ Prob(yi|pi)Prob(pi|r;θ(m))dpi, θ(m) ∼ q(θ)
≈ 1 M M∑ m=1 N∏ i=1 ∫ Prob(yi|pi)Dir(pi|α (m) i )dpi, α (m) = f(r,θ(m)), q θ(m) ∼ q(θ)
where the posterior over class label p will be given by the mean of the Dirichlet: Prob(yi = p|θ(m)) = ∫ Prob(yi = p|pi)Prob(pi|r;θ(m))dpi = α (m) ip∑K
k=1 α (m) ik
The probabilistic form for a specific node i by using marginal probability, Prob(yi|r;G) = ∑ y\yi Prob(y|r;G)
= ∑ y\yi ∫ ∫ N∏ j=1 Prob(yj |pj)Prob(pj |r;θ)Prob(θ|G)dpdθ
≈ ∑ y\yi ∫ ∫ N∏ j=1 Prob(yj |pj)Prob(pj |r;θ)q(θ)dpdθ
≈ M∑ m=1 ∑ y\yi ∫ N∏ j=1 Prob(yj |pj)Prob(pj |r;θ(m))dp, θ(m) ∼ q(θ)
≈ M∑ m=1 [∑ y\yi ∫ N∏ j=1 Prob(yj |pj)Prob(pj |r;θ(m))dpj ] , θ(m) ∼ q(θ)
≈ M∑ m=1 [∑ y\yi N∏ j=1,j 6=i Prob(yj |rj ;θ(m)) ] Prob(yi|r;θ(m)), θ(m) ∼ q(θ)
≈ M∑ m=1 ∫ Prob(yi|pi)Prob(pi|r;θ(m))dpi, θ(m) ∼ q(θ)
specifically for probability of label p,
Prob(yi = p|r;G) ≈ 1
M M∑ m=1 α (m) ip∑K k=1 α (m) ik , α(m) = f(r,θ(m)), θ(m) ∼ q(θ)

heading: C.3 KL-DIVERGENCE
text: KL-divergence between Prob(y|r;β) and Prob(y|r;γ,G): KL[Prob(y|r;G)||Prob(y|r;β))] = EProb(y|r;G) [
log Prob(y|r;G) Prob(y|r;β) ] ≈ EProb(y|r;G) [ log
∏N i=1 Prob(yi|r;G)∏N i=1 Prob(yi|r;β) ] ≈ EProb(y|r;G)
[ N∑ i=1 log Prob(yi|r;G) Prob(yi|r;β) ] ≈
N∑ i=1 EProb(y|r;G) [ log Prob(yi|r;G) Prob(yi|r;β) ] ≈
N∑ i=1 K∑ j=1 Prob(yi = j|r;G) ( log Prob(yi = j|r;G) Prob(yi = j|r;β) ) The KL divergence between two Dirichlet distributions Dir(α) and Dir(α̂) can be obtained in closed form as follows:
KL[Dir(α)‖Dir(α̂)] = ln Γ(S)− ln Γ(Ŝ) + K∑ c=1 ( ln Γ(α̂c)− ln Γ(αc) ) + K∑ c=1 (αc − α̂c)(ψ(αc)− ψ(S))
where S = ∑K c=1 αc and Ŝ = ∑K c=1 α̂c

Review summaries:
This paper proposes to model various uncertainty measures in Graph Convolutional Networks (GCN) by Bayesian MC Dropout. Compared to existing Bayesian GCN methods, this work stands out in two aspects: 1) in terms of prediction, it considers multiple uncertainty measures including aleatoric, epistemic, vacuity and dissonance (see paper for definitions); 2) in terms of generative modeling, the GCN first predicts the parameters of a Dirichlet distribution, and then the class probabilities are sampled from the Dirichlet. Training/inference roughly follows MC Dropout, with two additional priors/teachers: 1) the prediction task is guided by a deterministic teacher network (via KL(model || teacher)), and 2) the Dirichlet parameters are guided by a kernel-based prior (via KL(model || prior)). Experiments on six datasets showed superior performance in terms of the end prediction task, as well as better uncertainty modeling in terms of out-of-distribution detection.

The authors proposed a Bayesian graph neural network framework for node classification. The proposed models outperformed the baselines in six node classification tasks. The main contribution is to evaluate various uncertainty measures for the uncertainty analysis of Bayesian graph neural networks. The authors show that vacuity and aleatoric measure are important to detect out-of-distribution and the dissonance uncertainty plays a key role for improving performance.