Title: UNCERTAINTY-AWARE PREDICTION FOR GRAPH NEU-RAL NETWORKS

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.
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), Dempster-Shafer 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.

1. INTRODUCTION:

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; Veličković 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 proposed framework directly predicts subjective multinomial opinions of the test nodes in a graph, 

3. PROPOSED APPROACH:

Now we define the problem of uncertainty-aware semi-supervised node classification and then present a Bayesian GNN framework to address the problem.

3.1. 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:

p V\L = {p i ∈ [0, 1] K | i ∈ V \ L}; and

(2) the associated multidimensional uncertainty estimates introduced by different root causes:

u V\L = {u i ∈ [0, 1] m | i ∈ V \ L},

where p i,k is the probability that the class label y i = k and m is the total number of uncertainty types. 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

[b i1 , • • • , b iK , v i ],

where b ik (≥ 0) is the belief mass of the k-th category, v i (≥ 0) is the uncertainty mass (i.e., vacuity), and K is the total number of categories, where

EQUATION

where the relative mass balance between a pair of belief masses b ij and b ik is expressed by

Bal(b ij , b ik ) = 1 -|b ij -b ik |/(b ij + b ik ).

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(p i |α i ), where α i ∈ [1, ∞] K represents the distribution parameters. Given S i = K k=1 α ik , belief mass b i and uncertainty mass v i can be obtained by b ik = (α ik -1)/S i and v i = K/S i .

3.3. PROPOSED BAYESIAN DEEP LEARNING FRAMEWORK:

Let p = [p 1 , . . . , p N ] ∈ R N ×K denote the class probabilities of the node in V, where p i = [p i1 , . . . , p iK ] 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 p i from a Dirichlet distribution: Dir(p i |α i ),

where

α i = f i (r; θ) is parameterized by a GNN network α = f (r; θ) : R N ×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 y i ∼ Cat(y i |p i ), a categorical distribution on p i . In this design, the graph dependencies among the class labels in y L and y V\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:

EQUATION

where the Dirichlet probability function Dir(p i |α i ) is defined by:

EQUATION

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θ,

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 (p i ) of node i can be estimated by: Vacuity

(p i ) = E Prob(θ|G) [v i ] = E Prob(θ|G) K/ K k=1 α ik . The dissonance of node i is estimated as: Disso.[p i ] = E Prob(θ|G) ω(b i ) , where ω(b i ) is defined in Eq. (2).

3.4. BAYESIAN INFERENCE WITH DROPOUT:

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 y L by Prob(θ | G), where θ = {W 1 , . . . , W L , b 1 , ..., b L }, L is the total number of layers and W i refers to the GNN's weight matrices of dimensions P i × P i-1 , and b i is a bias vector of dimensions P i 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:

EQUATION

where γ = {M 1 , . . . , M L , m 1 , . . . , m L } are the variational parameters, where M i ∈ R Pi×Pi-1 and m i ∈ R Pi . We define W i in q(θ, γ) by:

EQUATION

where d = {d 1 , . . . , d L } is the dropout probabilities with z ij of Bernoulli distributed random variables. The binary variable z ij = 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, d i 's, can be optimized or fixed (Kendall et al., 2015) .

For simplicity, we fix d i '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:

EQUATION

which can infer the Dirichlet parameters α as:

α ≈ 1 M 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 yp 2 2 by:

L(γ) = i∈L y i -p i 2 2 • Prob(p i |r; γ)dp i = i∈L K j=1 y ij -E[p ij ] 2 + Var(p ij ) (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) .

3.5. GRAPH-BASED KERNEL DIRICHLET DISTRIBUTION ESTIMATION:

To better learn the Dirichlet distribution from our Bayesian GNN framework, we proposed a Graph-Based 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(y i , dis(i, j))

= [h 1 , . . . , h k , . . . , h K ] ∈ [0, 1] K and h k (y i , dis(i, j)) is obtained by: h k (y i , dis(i, j)) = 0 y i = k σ √ 2π • g(dis(i, j)) y i = 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: êj = i∈L h(y i , dis(i, j)), and the prior Dirichlet distribution αj = êj + 1. During training process, we minimize the KL-divergence between model predictions of Dirichlet distribution and prior distribution: min KL[Dir(α) Dir( α)].

3.6. A TEACHER NETWORK FOR REFINED INFERENCE:

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:

EQUATION

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.

4. EXPERIMENTS:

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.

4.1. DATASETS:

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.

4.2. COMPARING SCHEMES:

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: (Lu & Getoor, 2003) ; and (8) Planetoid (Yang et al., 2016) . We selected these for the comparison with our models based on (Veličković 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 S-GAT (S-BGAT) due to memory limited, More details of model setup refer to the Appendix A.

4.3. EXPERIMENTAL RESULTS & ANALYSIS:

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. 

5. UNCERTAINTY EXPERIMENT AND ANALYSIS:

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) . 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 uncertainty 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.

5.1. QUALITY OF UNCERTAINTY METRICS:

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 Table 4 : AUROC and AUPR for the OOD detection.

A APPENDIX:

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

DESCRIPTION OF DATASETS:

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.

A.2 EXPERIMENTAL SETUP FOR OUT-OF-DISTRIBUTION (OOD) DETECTION:

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. Table 5 : Description of datasets and their experimental setup for the OOD detection.

A.3 CALCULATION OF AUPR AND AUROC:

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.

TIME COMPLEXITY ANALYZE:

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 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-BGCN-T-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 (Veličković 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) . 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-BGCN-T-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, 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.

C DERIVATIONS FOR UNCERTAINTY MEASURES AND KL DIVERGENCE:

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).

C.1 UNCERTAINTY MEASURES:

Vacuity uncertainty of Bayesian Graph neural networks for node i:

Vacuity[p i ] = E Prob(θ|G) [v i ] = E Prob(θ|G) K/ K k=1 α ik ≈ E q(θ) K/ K k=1 α ik ≈ 1 M M m=1 K/ K k=1 α (m) ik

, α (m) = f (r, θ (m) ), θ (m) ∼ q(θ)

:

KDD Cup

Dataset: Online Available at https://kddcup2016.azurewebsites.net/

Figures and Tables:

Figure 1: Method Overview. our proposed framework is based on (a) Subjective Bayesian GNN designed for estimating the different types of uncertainties including (e) vacuity, dissonance, aleatoric, and epistemic uncertainties for the applications in graph data. The loss function includes (d) square error to reduce bias and (b) (c) two KL components to reduce error in predicting uncertainty. 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.

(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(Veličković et al., 2018).

Figure 2: PR curves for Node Classification Prediction: S-BGCN-T-K is used to predict node classification where test nodes are selected based on the low extent of uncertainty. The PR curves of all compared models can be found in the Appendix.

Figure 3: Graph embedding representations of the Cora dataset for classes and the extent of uncertainty: (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, aleatoric, epistemic.

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, and O(2|V|CF +2|E|F ) for S-BGAT-T and S-BGAT-T-K. A.4 MODEL SETUPS FOR SEMI-SUPERVISED NODE CLASSIFICATION

Figure 4: Graph embedding representations of the Citeseer dataset for classes and the extent of uncertainty: (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.

Figure 6: PR cuves of OOD detection for all models and uncertainties.

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. B.4 ANALYZE FOR EPISTEMIC IN OOD DETECTION 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.

3.2 MULTIDIMENSIONAL UNCERTAINTY QUANTIFICATIONMultiple 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[p

Table content: <table/>

Description of datasets and their experimental setup for the node classification prediction.

Table content: <table><tr><td/><td>Cora</td><td>Citeseer</td><td>Pubmed</td><td>Co. Physics</td><td>Ama.Computer</td><td>Ama.Photo</td></tr><tr><td>#Nodes</td><td>2,708</td><td>3,327</td><td>19,717</td><td>34, 493</td><td>13, 381</td><td>7, 487</td></tr><tr><td>#Edges</td><td>5,429</td><td>4,732</td><td>44,338</td><td>282, 455</td><td>259, 159</td><td>126, 530</td></tr><tr><td>#Classes</td><td>7</td><td>6</td><td>3</td><td>5</td><td>10</td><td>8</td></tr><tr><td>#Features</td><td>1,433</td><td>3,703</td><td>500</td><td>8,415</td><td>767</td><td>745</td></tr><tr><td>#Training nodes</td><td>140</td><td>120</td><td>60</td><td>100</td><td>200</td><td>160</td></tr><tr><td>#Validation nodes</td><td>500</td><td>500</td><td>500</td><td>500</td><td>500</td><td>500</td></tr><tr><td>#Test nodes</td><td>1,000</td><td>1,000</td><td>1,000</td><td>1000</td><td>1,000</td><td>1000</td></tr></table>

Semi-supervised node classification accuracy.

Table content: <table><tr><td/><td>Cora</td><td>Citeseer</td><td>Pubmed</td></tr><tr><td>DeepWalk</td><td>67.2</td><td>43.2</td><td>65.3</td></tr><tr><td>ICA</td><td>75.1</td><td>69.1</td><td>73.9</td></tr><tr><td>Planetoid</td><td>75.7</td><td>64.7</td><td>77.2</td></tr><tr><td>GCN</td><td>81.5</td><td>70.3</td><td>79.0</td></tr><tr><td>Bayesian GCN</td><td>81.2 ± 0.8</td><td>72.2 ± 0.6</td><td>76.6 ± 0.7</td></tr><tr><td>BGCNN</td><td>80.3 ± 0.6</td><td>72.6 ± 0.6</td><td>79.2 ± 0.5</td></tr><tr><td>GCN-Drop</td><td>81.3 ± 0.7</td><td>70.9 ± 0.5</td><td>79.0 ± 0.3</td></tr><tr><td>S-GCN</td><td>81.5 ± 1.0</td><td>71.2 ± 0.6</td><td>79.0 ± 0.2</td></tr><tr><td>S-BGCN</td><td>81.2 ± 1.0</td><td>71.0 ± 0.6</td><td>79.0 ± 0.2</td></tr><tr><td>S-BGCN-T</td><td>82.2 ± 0.6</td><td>71.3 ± 0.6</td><td>79.2 ± 0.4</td></tr><tr><td>S-BGCN-T-K</td><td>82.0 ± 0.6</td><td>71.0 ± 0.6</td><td>79.3 ± 0.3</td></tr><tr><td>GAT</td><td>83.0 ± 0.7</td><td>72.5 ± 0.7</td><td>79.0 ± 0.3</td></tr><tr><td>GAT-Drop</td><td>82.8 ± 0.8</td><td>72.6 ± 0.7</td><td>79.0 ± 0.3</td></tr><tr><td>S-GAT</td><td>83.0 ± 0.7</td><td>72.6 ± 0.6</td><td>79.0 ± 0.3</td></tr><tr><td>S-BGAT</td><td>82.9 ± 0.7</td><td>72.4 ± 0.7</td><td>78.9 ± 0.3</td></tr><tr><td>S-BGAT-T</td><td>83.7 ± 0.6</td><td>73.2 ± 0.5</td><td>79.1 ± 0.2</td></tr><tr><td>S-BGAT-T-K</td><td>83.8 ± 0.7</td><td>73.0 ± 0.7</td><td>79.1 ± 0.2</td></tr><tr><td/><td>Co.Physics</td><td>Ama.Computer</td><td>Ama.Photo</td></tr><tr><td>GAT*</td><td>92.5 ± 0.9</td><td>78.0 ± 19.0</td><td>85.7 ± 20.3</td></tr><tr><td>GCN*</td><td>92.8 ± 1.0</td><td>82.6 ± 2.4</td><td>91.2 ± 1.2</td></tr><tr><td>GCN</td><td>93.0 ± 0.8</td><td>79.7 ± 1.3</td><td>91.6 ± 1.2</td></tr><tr><td>GCN-Drop</td><td>93.0 ± 0.7</td><td>79.6 ± 1.2</td><td>91.3 ± 1.0</td></tr><tr><td>S-GCN</td><td>93.1 ± 0.8</td><td>78.9 ± 1.6</td><td>90.4 ± 1.4</td></tr><tr><td>S-BGCN</td><td>93.1 ± 0.7</td><td>78.3 ± 1.6</td><td>90.2 ± 1.6</td></tr><tr><td>S-BGCN-T</td><td>93.2 ± 0.8</td><td>84.1 ± 1.3</td><td>92.3 ± 1.2</td></tr><tr><td>S-BGCN-T-K</td><td>93.0 ± 0.8</td><td>84.0 ± 1.2</td><td>92.0 ± 1.3</td></tr><tr><td colspan="4">GCN* and GAT* are implemented from (Shchur et al., 2018)</td></tr></table>

Node classification prediction in AUPR.

Table content: <table><tr><td>Data</td><td>Model</td><td>Va.</td><td>Dis.</td><td>AUPR Al.</td><td>Ep.</td><td>En.</td></tr><tr><td/><td>S-BGCN-T-K</td><td>90.4</td><td>95.4</td><td>92.6</td><td>88.0</td><td>93.4</td></tr><tr><td>Cora</td><td>S-BGCN-T GCN-Drop.</td><td>89.5 -</td><td>94.4 -</td><td>91.9 92.7</td><td>85.3 90.0</td><td>92.2 93.6</td></tr><tr><td/><td>GCN</td><td>-</td><td>-</td><td>-</td><td>-</td><td>94.1</td></tr><tr><td/><td>S-BGCN-T-K</td><td>79.8</td><td>85.6</td><td>82.2</td><td>75.2</td><td>83.5</td></tr><tr><td>Citeseer</td><td>S-BGCN-T GCN-Drop.</td><td>80.0 -</td><td>85.6 -</td><td>82.4 82.3</td><td>76.6 77.8</td><td>83.6 83.7</td></tr><tr><td/><td>GCN</td><td>-</td><td>-</td><td>-</td><td>-</td><td>83.2</td></tr><tr><td/><td>S-BGCN-T-K</td><td>85.6</td><td>90.9</td><td>88.9</td><td>86.0</td><td>89.3</td></tr><tr><td>Pubmed</td><td>S-BGCN-T GCN-Drop.</td><td>84.8 -</td><td>90.2 -</td><td>88.8 88.6</td><td>85.1 85.6</td><td>89.3 89.0</td></tr><tr><td/><td>GCN</td><td>-</td><td>-</td><td>-</td><td>-</td><td>89.2</td></tr><tr><td colspan="7">Va.: Vacuity, Dis.: Dissonance, Al.: Aleatoric, Ep.: Epistemic, En.: Entropy</td></tr></table>

Hyperparameter configurations of S-BGCN-T-K model.

Table content: <table/>

Peer review (iclr2020):
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. ** Introduction/Conclusion/Contribution - Applying MC dropout to graph neural networks is a bit old idea [1-5], it cannot be considered as the “contribution” of this study. - The authors should emphasize more on what’s the advancements over existing studies. ** Methodology - My understanding is the authors proposed to use multiple uncertainties (vacuity, dissonance, aleatoric, epstemic). Vacuity and dissonance measures can also be implemented with other Bayesian graph neural networks. - Ablation study is need to demonstrate the usefulness of each component in the objective function (equation 11). - Can “BGAT-T” be considered as the proposed method? It doesn*t use the proposed GNN framework but just an extension of original GAT with MC dropout and knowledge distillation. ** Experiments - Please provide the details of hyperparameter settings, e.g. optimizer, batch size, learning rates, … - The authors should perform experiments with varying numbers of labels per category (e.g. 5, 10, 20), because different methods show different behaviors under label scarcity. - There are a number of recently published papers that address node classification based on Bayesian graph neural networks, e.g., see references. They should be used as baselines if available. - I think the authors should evaluate BGAT-T with Co.Physics, Ama.Computer, and Ama.Photo datasets, because this method was overall superior to other methods on the first three datasets. - Experiments are insufficient in the uncertainty analysis (section 5). The authors can evaluate the performance of BGAT as well as other Bayesian graph neural networks in terms of uncertainty quantification performance. - Also, in order to evaluate uncertainty quantification performance, I would suggest to look at the trade-off between classification accuracy and classification rejection based on the uncertainty, like accuracy-rejection curve in [6] ** misc - Check the following sentence of subsection 3.6. “our key contribution is that the proposed Bayesian GNN model is capable of estimating various uncertainty types to predict existing GNNs.” References [1] Ryu, S., Kwon, Y., & Kim, W. Y. (2019). Uncertainty quantification of molecular property prediction with Bayesian neural networks. arXiv preprint arXiv:1903.08375. [2] Zhang, Y., & Lee, A. A. (2019). Bayesian semi-supervised learning for uncertainty-calibrated prediction of molecular properties and active learning. arXiv preprint arXiv:1902.00925. [3] Pal, S., Regol, F. L. O. R. E. N. C. E., & Coates, M. A. R. K. (2019). Bayesian graph convolutional neural networks using non-parametric graph learning. In Representation Learning on Graphs and Manifolds Workshop, Int. Conf. Learning Representations. [4] Akita, H., Nakago, K., Komatsu, T., Sugawara, Y., Maeda, S. I., Baba, Y., & Kashima, H. (2018, December). Bayesgrad: Explaining predictions of graph convolutional networks. In International Conference on Neural Information Processing (pp. 81-92). Springer, Cham. [5] Zhang, Y., Pal, S., Coates, M., & Ustebay, D. (2019, July). Bayesian graph convolutional neural networks for semi-supervised classification. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 33, pp. 5829-5836). [6] Nadeem, M. S. A., Zucker, J. D., & Hanczar, B. (2009, March). Accuracy-rejection curves (ARCs) for comparing classification methods with a reject option. In Machine Learning in Systems Biology (pp. 65-81).