Graph Posterior Network: Bayesian Predictive Uncertainty for Node Classification
Authors: Maximilian Stadler
Bertrand Charpentier
Simon Geisler
Daniel Zügner
Stephan Günnemann
Venue: NeurIPS 2021 Poster (2021)
Keywords: Uncertainty
Bayesian rule
Posterior
Graph
Classification

Abstract: The interdependence between nodes in graphs is key to improve class prediction on nodes, utilized in approaches like Label Probagation (LP) or in Graph Neural Networks (GNNs). Nonetheless, uncertainty estimation for non-independent node-level predictions is under-explored.  In this work, we explore uncertainty quantification for node classification in three ways: (1) We derive three axioms explicitly characterizing the expected predictive uncertainty behavior in homophilic attributed graphs.(2) We propose a new model Graph Posterior Network (GPN) which explicitly performs Bayesian posterior updates for predictions on interdependent nodes. GPN provably obeys the proposed axioms. (3) We extensively evaluate GPN and a strong set of baselines on semi-supervised node classification including detection of anomalous features, and detection of left-out classes. GPN outperforms existing approaches for uncertainty estimation in the experiments.

Graph Posterior Network: Bayesian Predictive Uncertainty for Node Classification
Maximilian Stadler; Bertrand Charpentier; Simon Geisler, Daniel Zügner,
Stephan Günnemann Department of Informatics
Technical University of Munich, Germany
{stadlmax, charpent, geisler, zuegnerd, guennemann tum de
Abstract
The interdependence between nodes in graphs key to improve class predictions nodes and utilized in approaches like Label Propagation (LP) or in Graph Neu- ral Networks (GNNs). Nonetheless, uncertainty estimation for non-independent node-level predictions is under-explored. In this work, we explore uncertainty quantification for node classification three ways: (1) We derive three axioms explicitly characterizing the expected predictive uncertainty behavior in homophilic attributed graphs. (2) We propose new model Graph Posterior Network (GPN) which explicitly performs Bayesian posterior updates for predictions interde- pendent nodes. GPN provably obeys the proposed axioms. (3) We extensively evaluate GPN and strong set of baselines semi-supervised node classification including detection of anomalous features, and detection of left-out classes. GPN outperforms existing approaches for uncertainty estimation in the experiments.
1 Introduction
Accurate and rigorous uncertainty estimation is key for reliable machine learning models in safety- critical domains (67]. It quantifies the confidence of machine learning models, thus allowing them to validate knowledgeable predictions or flag predictions on unknown input domains. Uncertainty is commonly divided in aleatoric and epistemic uncertainty (28). The aleatoric uncertainty accounts for irreducible uncertainty (e.g., due to inherent sensor noise). The epistemic uncertainty accounts for a lack of information for accurate prediction (e.g., test data significantly different from training data).
Traditionally, machine learning models assume i.i.d. inputs, thus performing predictions based on input features only, For uncertainty estimation on i.i.d. inputs, a large class of definitions, models and evaluation methods have been introduced 228 62 3 78 [0]. Further, uncertainty estimation has been successfully applied to different tasks e.g. duitt--dist (OOD) shift detection (78), active
learning [75 (5], continual learning or reinforcement learning [18].
In contrast, uncertainty estimation on interdependent nodes is more complex than on i.i.d. inputs and under-explored 3 A node an attributed graph characterized by two types of information: its features and its neighborhood. While the feature information indicates the node position in the feature space similarly to i.i.d. inputs -, the neighborhood information indicates the additional node position in the network space. To leverage the neighborhood information, recent graph neural networks (GNNs) successfully proposed to enrich and correct the possibly noisy information of the features of single node by aggregating them with the features of its neighborhood [46] 92 48 It naturally leads to the distinction between predictions without network effects based exclusively on their own node feature representation, and predictions with network effects based on neighborhood
equal contribution
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

p
plo
plo)
p/
ais
ala
p
p
p
(a) AU w/o network
(b) AU w/ network
(c) EU w/o network
(d) EU w/ network
Figure| 1: Illustration of aleatoric uncertainty (AU) and epistemic uncertainty (EU) without and with network effects (i.e. i.i.d. inputs vs interdependent inputs). Nodes have the same features in all cases. Network effects are visualized through edges between nodes which change the predicted distributions.
The aleatoric uncertainty high if the categorical distribution g(() Cat(p(")) is flat. The epistemic uncertainty high if the Dirichlet distribution ((*) (ir(a(")) is spread out. We refer the reader to Section 3.2 for formal definitions of those distributions.
aggregation. The aggregation step commonly assumes network homophily which states that nodes with similar properties tend to connect to each other more densely, thus violating the i..dd assumption between node features given their neighborhood.
The core motivation of our work is transfer some of the existing uncertainty estimation definitions, models and evaluations from i.i.d. inputs to interdependent node inputs by leveraging both the feature and the neighborhood information. In particular, we aim at an accurate quantification of the aleatoric and epistemic uncertainty without and with network effect under network homophily (see Fig. D
Our contribution. In this work, consider uncertainty estimation semi-supervised node classi- fication. First, we derive three axioms which materialize reasonable uncertainty for non-independent inputs. These axioms cover the traditional notions of alcatoric and epistemic uncertainty and distin- guish between the uncertainty with and without network effects. Second, we propose Graph Posterior Network (GPN for uncertainty estimation for node classification and prove formally that it follows the axiom requirements contrary to popular GNNs. Third, we build an extensive evaluation setup for uncertainty estimation which relies on the assessment of uncertainty estimation quality of OOD de- tection and robustness against shifts of the attributed graph properties. Both OOD data and attributed graph shifts distinguish between attribute and structure anomalies. The theoretical properties of GPN manifest in these experiments where it outperforms all other baselines on uncertainty evaluation.
2 Related Work
In this section, cover the related work for predictive uncertainty estimation for i.i.d. inputs and for graphs. To this end, we review the commonly accepted axioms defining the desired uncertainty estimation under different circumstances, the methods capable of consistent uncertainty quantification and the evaluation validating the quality of the uncertainty estimates in practice.
Uncertainty for i.i.d. inputs The related work for uncertainty quantification on i.i.d. inputs is rich as for example shown in recent survey [. Axioms: Far from ID data, the predicted uncertainty is expected to be high [66 15 [1 [0) Close to ID data, the desired uncertainty is more complicated.
Indeed, while some works expected models to be robust to small dataset shifts 78 89, other works expected to detect near OOD classes based on uncertainty 198] 550 13] Methods: Many methods already exist for uncertainty quantification for i.i.d. inputs like images or tabular data. first family of models quantifies uncertainty by aggregating statistics (c.g. mean, variance entropy) from sub-networks with different weights. Important examples are ensemble [52] 96 97 38), dropout (88)
or Bayesian Neural Networks (BNN) [9] 20 59 24 21.. Most of these approaches require multiple passes for uncertainty quantification. Further, dropout and BNN may have other pitfalls regarding their limited applicability to more complex tasks (77 41 34 27 A second family quantifies uncertainty by using the logit information. Important examples are temperature scaling which rescale the logits after training 35 (56) and energy-based models which interpret the logits as energy scores [5 33 A third family of model quantifies uncertainty based on deep Gaussian Processes (GP). Important examples use GP at activation-level (68 (last) layer-level 53 51
g. Finally, last
Prroject page including code at httpps: :/t::::wwawttee in, tum. de/ wwa.mdd/graphl het///aahhposseee

---

family of models quantifies uncertainty by directly parameterizing a conjugate prior distribution over the target variable. Important examples explicitly parameterize prior distributions [6
63
60, 6 or
posterior distributions [1] 15] Methods based on GP and conjugate prior usually have the advantage of deterministic and fast inference. Evaluation: Previous works have already proposed empirical evaluation of uncertainty estimation by looking at accuracy, calibration or OOD detection metrics under dataset shifts or adversarial perturbations for i.i.d. inputs [78] 50]. In contrast with all these approaches, this work studies uncertainty quantification for classification of interdependent nodes.
Uncertainty for graphs Notably, the recent survey points out that there only a limited number of studies on uncertainty quantification on GNN and semi-supervised learning. Moreover, they recommend proposing new methods. Axioms: To the best of our knowledge, only [23] proposed explicit axioms for node classification for non non-attributed graphs. They expect disconnected nodes to recover prior predictions and nodes with higher beliefs to more convincing. this work, we clarify the desired uncertainty estimation for node classification on attributed graphs based on motivated and explicit axioms. Methods: The largest family of models for uncertainty for graphs are dropout- or Bayesian-based methods. Important examples propose to drop or assign probabilities to edges Further works proposed to combine the uncertainty on the graph structure with uncertainty on the transformation weights similarly to BNN 122
83
16 37 19
10T 79 [0]. Importantly, these
models do not directly quantify uncertainty on the prediction. Similarly to the i.i.d. case, a second family of models focuses on deterministic uncertainty quantification. Important examples mostly use Graph Gaussian Processes, which do not easily scale to large graphs [74] [03] 58) [2]. Only [102] explicitly parameterized a Dirichlet conjugate prior. They combined it with multiple components (Graph-Based Kernel, dropout, Teacher Network, loss regularizations) which cannot easily distinguish between uncertainty without and with network effects. In contrast, GPN is simple approach based on conjugate prior parametrization and disentangles uncertainty with and without network effects. Evaluation: The evaluation of most of those methods was not focused on the quality of the uncertainty estimates but on the target task metrics (e.g. accuracy for classification, distance to ground truth for regression). Some methods focus on robustness of the target task metries against adversarial perturbations (36] 107 [06]. Other methods only relied on uncertainty quantification to build more robust models [004 25 For node classification, only few works evaluated uncertainty by using
Left-Out classes or detection of missclassified samples [102], active learning [74] or visualization
[12. Note that proposed uncertainty evaluations on molecules at graph level [100] 84
5 40 90) is
an orthogonal problem. In this work, we propose a sound and extensive evaluation for uncertainty
in node classification. It distinguishes between OOD nodes w.r.t. features and structure, and graph
dataset shifts w.r.t. the percentage of perturbed node features and the percentage of perturbed edges.
3 Uncertainty Quantification for Node Classification
We consider the task of )uni-ssperrvsee) node classification on an attributed graph g = (A, X) with adjacency matrix A E {0, 1 and node attribute matrix X E R N We aim at inferring the labels y ( (1, C) plus the the aleatoric uncertainty (1)) and the epistemic uncertainty Vepist
(e) of unlabeled nodes v E T given a set of labelled nodes u E l in the graph where V = T Uu
denotes the set of vertices.
3.1 Axioms
Uncertainty estimation in the setting of interdependent inputs is not well-studied. It often leaves the expected behavior and interpretations for uncertainty estimation unclear. Thus, we need well- grounded axioms to derive meaningful models. In this section, we aim at specifying the desired uncertainty predictions under various circumstances in homophilic attributed graphs. To this end, we propose three axioms which are based on the two following distinctions. The first distinction differentiates between aleatoric and epistemic uncertainty which are commonly used concepts under the i.i.d. assumptions 22 62). The second distinction differentiates between uncertainty without and with network effects which are motivated by the concepts of attribute and structure anomalies used in the attributed graph setting [II]. These new axioms cover all possible combinations encountered by these distinctions and extend the axioms proposed by (23 for non-attributed graphs. We designed the axioms to be informal and generic so that they are application independent, model-agnostic and do not require complex mathematical notations similarly to 223 76). In practice, formal definitions need to instantiate general concepts like alcatoric/epistemic uncertainty and with/without network effects
3

---

noting that some definitions might be more convenient depending on the task. The first axiom deals with (epistemic and aleatoric) uncertainty estimation without network effects (see Fig. la Icl.:
Axiom 3.1. A node's 's prediction in the absence of network effects should only depend on its own fea- fures. A node with features more different from truining features should be assigned higher uncertainty.
Axiom 3.1 states that if a node y has no neighbors, then the final prediction p(*) should only depend on its own node features xx()), Further, for anomalous features the model should fall back to safe prior predictions, indicating high aleatoric and epistemic uncertainty. This aligns with [23] which expects to recover prior predictions for non-attributed nodes without network effect, and [66, [5] which expect to recover prior predictions far from training data for i..d. inputs. The second axiom deals with epistemic uncertainty estimation with network effects (see Fig. Ic Id
Axiom 3.2. All else being equal, if node's 's prediction in the absence of network effects is more epistemically certain, then its neighbors' predictions in the presence of network effects should become more epistemically certain.
Axiom 3.2 states that node e with confident feature predictions (x()) is expected to be convincing and make its neighbors E (u) more confident. Conversely, node with anomalous features is expected to make its neighborhood less confident. This axiom materializes the network homophily assumption at the epistemic level i.e. connected nodes have similar epistemic uncertainty estimates. For non-attributed graphs. [23] similarly expects a more confident node to have more influence on direct neighbor. The third axiom deals with aleatoric uncertainty estimation with network effects (see Fig. 1a Tb):
Axiom 3.3. All else being equal, a node's 's prediction in the presence of network effects should have higher aleatoric uncertainty its neighbors' predictions in the absence of network effects have high aleatoric uncertainty. Further, a node prediction in the presence network effects should have higher aleatoric uncertainty if its neighbors' predictions in the absence network effects are more confticting.
Axiom 3.3 states that no clear classification decision should be made for a node v if no clear classification decisions can be made for its neighbors. Further, the classification decision becomes less certain if a neighbor has a conflicting classification decision. Note that this axiom is more subtle than the direct application of network homophily the aleatoric level. Indeed node can have high aleatoric uncertainty contrary to its neighbors which predict different classes with low alcatoric uncertainty. This aligns with the intuition that conflicting information from the neighborhood provides an irreducible uncertainty to the considered node.
3.2 Graph Posterior Network
The Bayesian update rule is a key component of GPN to model uncertainty on the predicted categorical distribution. For a single categorical distribution y ~ Cat(p). the standard Bayesian update is straightforward. A natural choice for a prior distribution over the parameters p is its conjugate prior i.e. the Dirichlet distribution y/.),...,yf (N), the Bayesian update then consists in applying the Bayes' theorem
(P(p) = Dir(a with a E C Given the observations
P (1l
15=1 &
P
Lv O
1 (p) x Pp))
(I)
producing the posterior distribution P(p ty ( = Doa( where post= = = + 3 are the parameters of the posterior and 3. = Eg = 1 y0 are the class counts. This framework naturally disentangles the aleatoric and epistemic uncertainty by defining the Dirichlet mean p ao the total evidence count ag = Σ. at.. Indeed, the alcatoric uncertainty is commonly measured by the entropy of the categorical distribution i.c. Malca H [Cat(p)) 662 14 [5) and the epistemic uncertainty can be measured by the total evidence count ogg of observations i.c. Mepist = -a0 [4] Alternatively, the epistemic uncertainty can also be measured with the Dirichlet differential entropy 662] Note that the reparameterization using p and ag can apply to any class counts including the prior counts prior, the class counts /3 and the posterior counts post
and
For classification, the predicted categorical distribution j(()) ~ Cal(p(o)) additionally depends on the specific input v. Hence, the input-dependent Bayesian rule [1 15 extends the Bayesian treatment of a single categorical distribution to classification by predicting an individual posterior update for any possible input. Specifically, it first introduces a fixed Dirichlet prior over the categorical

---

NF pialc 1,45
(a(m))
x: (1)
2(x)
NP pisle 0.4)
-00 22
greett)
PPR with TM
Figure 2: Overview of Graph Posterior Network: (1) node-level pseudo computed by the feature encoder in the orange box, (2) UPR-based message passing visualized between the curly braces, and (3) input-dependent Bayesian update illustrated with the Dirichlet triangles on the right.
distribution p(*) ~ Dir Dir(a))oor) where oetor E R4 is usually set to 1, and second predicts the input-dependent update g(e) which forms the posterior distribution pl)) (ir(( where the posterior parameters are equal to
post = prior + +33())
(2)
The variable 3(()) can be interpreted as learned class pseudo-counts and its parametrization is crucial. For i.i.d. inputs, PostNet [14] models the pseudo-counts 30(0) in two main steps. (1)
maps the inputs features xx()) onto a low-dimensional latent vector (0)) = fx((()) E IR (2),
fits one conditional probability density (C2 Φ) per class on this latent space with normalizing flows. The final pseudo count for class e is set proportional to its respective conditional density i.e.
3( N (22(((1) |c; Φ) P(c) where N is total certainty budget and P(c) C for balanced classes. Note that this implies og = N (=)((())((()
(()) This architecture has the advantage of decreasing the evidence outside the known distribution when increasing the evidence inside the known distribution, thus leading to consistent uncertainty estimation far from training data.
Bayesian Update for Interdependent Inputs. We propose simple yet efficient modification for parameterizing (( to extend the input-dependent Bayesian update for interdependent attributed nodes. The core idea is first predict the feature class pseudo-counts (tt(1)) based on independent node features only, and then diffuse them form the aggregated class pseudo-counts gees.(v) based on neighborhood features. Hence, the feature class pseudo-counts gh,(() intuitively act as uncertainty estimates without network effects while the aggregated class pseudo-counts (ee).()) intuitively act as uncertainty estimates with network effects.
To this end, GPN performs three main steps (see Fig. 2 (1) A (feature) encoder maps the features of e onto a tow-dimensional latent representation z i.c. (v)
fo( " In practice, we use a simple MLP encoder in our experiments similarly to APPNP AS (2) One conditional probability
x (P(2(() C; (.)). Note that the density per class (=2(1) c; (. E. 3e. gfl.(v) and the parameter p (*) = gh /ag.e)) are only based the total feature evidence ag
used to compute (. i.
on node features and can be seen as epistemic and aleatoric uncertainty measures without network effects. In practice, we used radial normalizing flows for density estimation similarly to [14] and scaled the certainty N budget w.r.t. the latent dimension H similarly to [5]. (3) Personalized
Page Rank (PPR) message passing scheme is used to diffuse the feature class pseudo-counts, 3 (v) and form the aggregated class pseudo-counts S (e) i.e.
(uyg.(u)
Σ KEV
H (1) D,a
where 11PPT are the dense PPR scores implicitly reflecting the importance of node u on v. We approx- imate the dense PPR scores using power iteration similarly to [4] The aggregated pseudo-coum gges.(v) is then used in the input-dependent Bayesian update (see Eq. (2. Remark that the scores 3e
Iepe define valid conditional distribution over all nodes associated to the PPR random walk (i.e.
E. Ieger = 1). It can be viewed as a soft neighborhood for accounting for all neighborhood hops through infinitely many message passing steps [88] Hence, on one hand, the PPR scores define prob- ability distribution over nodes using the node edges only. On the other hand, the quantity IP( P(2(4) c;; Φ)
equiv- defines probability distribution over nodes using the node features only. Therefore,
5

---

alently rewrite this step using probabilistic notations P(u| u) = Tig and P(u (c) = P(z(w) cc; Φ):
geee.tv) P(ulc)
Σ
P(e u P(ulc) c)
NEV
Interestingly, the quantity P(u|c) defines a valid distribution which normalizes over all node features and accounts for the soft neighborhood (i.e. f... [(u (tddz"))..d2("M = 1). Hence, the message passing step is a simple but efficient method to transform the feature distributions of a single node into a joint distributions over the soft neighborhood features. Finally, the evidence =E ( and the parameter p* /ua.(t) /a are based on neighborhood features and can be seen as epistemic and aleatoric uncertainty measures with network effects. Remark that, the sequential processing of the features (i.e. steps (1)+(2) and network information (i.e. step (3)) in GPN is key element to differentiate between the uncertainty without and with network effects and is a building block to provably obey the axioms.
ag aeg.tt)
GPN extends both APPNP [48] and PostNet [14] approaches. The key difference to APPNP is the density estimation modeling the epistemic uncertainty (i.e. steps (1)+(2) and the input-dependent Bayesian update allowing to recover the prior prediction (i.e. Eq. 2. The key difference to PostNet is the PPR diffusion which accounts for dependence between nodes (step (3)).
Optimization. We follow [1] and train GPN by minimizing the following Bayesian loss with two terms i.e.:
((w)
E guosstt) log ((y p p
A (u)oet.(v)
where À is a regularization factor. It can be computed quickly in closed- and provides theoretical guarantees for optimal solutions [14]. All parameters of GPN are trained jointly. Similarly to [15) we also observed that "warm-up" training for the normalizing flows is helpful.
3.3 Uncertainty Estimation Guarantees
In this section, we provide theoretical guarantees showing that GPN fulfills the three axioms under mild assumptions given the specific definitions of concepts of alcatoric/epistemii uncertainty and with/without network effects presented in Sec. 3.2] Throughout this section, we consider a GPN model parameterized with a (feature) encoder fe with piecewise ReLU activations, a PPR diffusion, and a (t)( w) with bounded derivatives. We present detailed proofs in appendix.
density estimator P (P(
The first theorem shows that GPN follows Ax. 3.1 and guarantees that GPN achieves reasonable uncertainty estimation extreme node features without network effects:
Theorem 1.
Lets consider a GPN model. Let fa()(")) v((z(() + ( be the piecewise affine rep- resentation of the ReLU network fo on the finite number of affine regions Q()) [Z]. Suppose that Vt)
have independent rows, thenfor any node and almost any x we have P( x x(1)) c: Φ) - 0.
Without network effects, it implies that gf.(o) (588 (D)
O.
80000
5-000
The proof relies on two main points: the equivalence of the GPN and PostNet architectures without network effects, and the uncertainty guarantees of PostNet far from training data similarly [15]. It intuitively states that, without network effects, GPN predict small evidence (i.e. (38x.(() se 0) far from training features (i.e. ||ō [= - oo) and thus recover the prior prediction (i.e. post. zs prior). Note that contrary to GPN, methods which do not account for node features (e.g. Label Propagation) or methods which only use ReLU activations 39 cannot validate Ax. 3.1 Further, methods which
perform aggregation steps in early layers (e.g. GCN (46) do not separate the processing of the feature and network information making unclear if they fulfill the Ax. 3.1 requirements.
The second theorem shows that GPN follows Ax. 3.2 and guarantees that a node v becomes more epistemically certain if its neighbors are more epistemically certain:
Theorem 2. Lets consider GPN model. Then, given node v, the aggregated feature evidence (e) is increasing if the feature evidence of (.(U)) of one of its neighbors u E NN(v) is increasing. 00
The proof directly relies on Eq. Intuitively, this theorem states that the epistemic uncertainty (2)
Vepsst -a 2e8. of node with network effects decreases if the epistemic uncertainty of the
neighboring nodes without network effects decreases. Note that contrary to GPN, methods which
do not model the epistemic uncertainty explicitly (e.g. GCN 46) GAT 92 or APPNP 48)
are not
guaranteed to fulfil Ax. 3.2

---

The third theorem shows that GPN follows Ax. 3.3 It guarantees that a node v becomes more aleatorically uncertain if its neighbors are more aleatorically uncertain, if a neighbor prediction disagrees more with the current node prediction:
Theorem 3.
Lets consider GPN model. Lets denote pess. (v) / /age /ag the diffused categorical prediction for node where et is its winning class. Further, lets denote p (w) [o the non- diffused categorical prediction for a node u E V. First, there exists normalized weights II such that E Ie H (Cat(pf.(e)) S H [Cat(puss [1)]. Second, if for any node u E V the probability of p.. decreases, then HI Cat(p [])]] increases.
The proof of the first part of the theorem is based on the entropy convexity. Intuitively, it states that of node with network effects is lower bounded by a weighted average of the aleatoric uncertainty without network effects its soft neighborhood. The second part of the theorem intuitively states that if the prediction of a neighboring node u without neighbor effects disagrees more with the current class prediction e* of the node v, then the aleatoric
(+) the aleatoric uncertainty Malea Hi
(*) uncertainty alca = H Caa(p"": [ with network effects becomes higher. Note that contrary to
GPN, methods which do not use edges (c.g. PostNet (14) cannot validate Ax. 3.3 and Ax. 3.2
3.4 Limitations & Impact
OOD data close to ID data. While GPN is guaranteed to provide consistent uncertainty estimates for nodes with extreme OOD features, it does not guarantee any specific uncertainty estimation behavior for OOD data close to ID data. Note that there exist two possible desired behaviors for OOD close
to ID data; being robust to small dataset shifts 77 89 or detect near OOD data 98| 50, [3. The
duality of these two views makes unclear what would be the desired behavior even for i.i.d. data.
Non-homophilie uncertainty. Our approach assumes that connected nodes are likely to have similar uncertainty estimates as defined in Ax. 3.2 and Ax. 3.3 Contrary to [105], we do not tackle the problem of heterophilic graphs where two neighboring nodes might reasonably have different uncertainty estimates.
Task-specific OOD. Density estimation is shown to be inappropriate for OOD detection when acting directly on raw images [72 [7 [71] or on arbitrarily transformed space (54). One of the reasons is that normalizing flows learn pixel correlations in images. This phenomena does not happen for tabular data with more semantic features (47). First note that, similarly to tabular data, semantic node features
less likely suffer from the same flaws. Second, following previous works [14 15 47
69 98),
GPN mitigates this issue by using density estimation on a latent space which is low-dimensional and task-specific. Nonetheless, we emphasize that GPN provides predictive uncertainty estimates which depends on the considered task i.e. OOD data w.r.t. features which are not useful for the specific task are likely not be encoded in the latent space, and thus not be detected.
Broader Impact. The Assessment List for Trustworthy AI (ALTAI) [ includes robustness, safety, and accountability. Uncertainty estimation is key element make AI systems follow these values. For example. an automated decision maker should know when it does not know. In this regard, GPN significantly improves the reliability of predictions on interdependent data under perturbations even though a user should not blindly rely on it. Further, ALTAI also mentions privacy and fairness. Therein, raise awareness the risk of using interconnected information which can amplify privacy or fairness violation in the presence of personal data.
Experiments
In this section, we provide extensive evaluation set-up for uncertainty quantification for node classification. It compares GPN to 13 baselines on 8 datasets and consists in two task types. First, we evaluate the detection of OOD nodes with features perturbations and Left-Out classes. Second, evaluate the robustness of accuracy, calibration and uncertainty metrics w.r.t. feature and edge shifts.
4.1 Set-up
Ablation. In the experiments, GPN uses MLP as feature encoder, radial normalizing flows {2 for the density estimation and certainty budget N which scales with respect to the latent dimension 15). We provide ablation study covering aleatoric uncertainty through APPNP, feature-level
7

---

estimates through PostNet, diffusing resulting pseudo-counts after training, and GPN with diffusion of log (3) instead of (e (see App. E.T). The complete GPN model outperforms the ablated models for uncertainty estimation. Further, we provide a hyper-parameter study covering for example different number of flow layers, latent dimensions, PPR teleport probabilities (see App. (.2))
Baselines. We used 13 baselines covering a wide variety of models for semi-supervised node classifi- cation and uncertainty estimation. We show the results of 5 baselines in the main paper and the full results in appendix. It contains two standard GNNs (i.e. Vanilla GCN VGCN 46 87 and APPNP
48) ). one robust GNN (i.e. RGCN (T04). one dropout- based method for GNN (i.e. DropEdge 83
two Graph Gaussian Processes methods (i.e. GGP (74 and Matern-GGP (2)., the Staph-baser
Kernel Dirichlet GCN method (i.e. GKDE-GCN [102] and two parameter- less methods (i.e. GKDE
[102] and Label Propagation LP see App.). Further, we also compared to direct adaptation of dropout
(i.e. VGCN-Dropout 29)., ensemble (i.e. VGCN-Ensemble ) BNN (i.e. VGCN-BNN ( and energy-based models (i.e. VGCN-Energy [57]) to vanilla GCNs. All models are trained using the same number of layers and similar number of hidden dimensions. We used early stopping and report the used hyperparameters in appendix. The results are averaged over 10 initialization seeds per split.
Further model details are given in appendix.
Datasets. We used 8 datasets with different properties summarized in appendix. We show the results of 3 datasets in the main paper and the full results in appendix. contains common citation network
datasets (i.e. CoraML 665| 32 31 [5). CiteSeer (1 85). Pub.Med (73), CoauthorPhysies [87]
CoauthorCS (87) and co- co-purchase datasets (i.e. AmazonPhotos 64 87 AmazonComputee /80%
[64]
). The results are averaged over 10 initialization splits with a train/val/test split of 3%/15% 1151155/////
using stratified sampling. Further, we evaluate on the large OGBN Arxiv dataset with 169, 343 nodes
and 2, 315, 598 edges [3 94]. Further dataset details are given in the appendix.
4.2 Results
OOD Detection. In this section, we evaluate uncertainty estimation for OOD detection. To this end, we use the Area Under Receiving Operator Characteristics Curve (AUC-ROC with aleatoric scores Vatea (Alea) and epistemic scores "egigi (Epist) similarly to [14 102
63 61 57). For GPN, differentiate between epistemic uncertainty scores without network effects (w/ Net.) and with network effects (w/ Net.). Further, we report results with the Area Under the Frecision-Recall Curve (AUC-PR) in appendix. The definition of OOD for nodes in the presence of feature and network information is more complex than for i.i.d. input features. Hence, we propose two types of OOD nodes: nodes with OOD feature perturbations and nodes from Left- Out classes. For feature perturbations, we compute the accuracy on the perturbed nodes (OOD-Ace) to evaluate if the model can correct anomalous features. For Left-Out -ut classes, we compute the accuracy on the observed classes (ID-Ace). We report the short results in Tab. [ We set threshold of 64 GiB and 12 hours per training run. We also exclude methods which do not use attributes for detection of OOD feature perturbations.
[e)
60
These perturbations aim at isolating the contribution of the node feature information on the model predictions. To this end, we randomly select a subset of the nodes. For each single node v, we perturb individually its features using a Bernoulli or a Normal distribution (i.e. x(") ~ (cr(0.5) and (()) ~ NO, 1)) keeping all other node features fixed. We then compare the uncertainty prediction on the perturbed and unperturbed node. On one hand, Bernoulli noise corresponds to small perturbations in the domain of discrete bag-of-words features. On the other hand, Normal noise corresponds extreme perturbations out of the domain of discrete bag-of words features. In practice, we expect out-of-domain perturbations to be easily detected [1] First, we remark that uncertainty estimates of GPN based on features achieves an absolute improvement of at least +15% and +29% for Bernoulli and Normal perturbations over all baselines using network effects. This shows that GPN disentangles well the uncertainty without and with network effects. Second, we remark that all uncertainty estimates with network effects achieve poor results. This is expected if models can recover the correct prediction after aggregation steps. Specifically, we observe that GPN achieves an accuracy improvement between +16% and +64% for Normal perturbations on perturbed nodes compared to baselines. It stresses that GPN performs a consistent evidence aggregation from neighborhood to recover from anomalous features. Further, note that GPN is still capable to detect those perturbed nodes almost perfectly using feature uncertainty. These remarks aligns with Ax. 3.1
Feature perturbations:
8

---

Left-Out Out classes: Detection of Left-Out classes involves both feature and neighborhood information. In this case, we remove the Left-Out classes from the training set but keep them in the graph similarly to 102. We observe that the uncertainty estimates with network effects of GPN achieves an absolute improvement between + +12% and + +16 compared to its uncertainty estimates without network effects. It highlights the benefit of incorporating network information for uncertainty predictions when OOD samples (i.e. samples from the Left-Out classes) are likely to be connected to each other. This remark aligns with Ax. 3.2 Further, GPN outperforms other baselines by +2% to +22% for LOC detection while maintaining a competitive accuracy on other classes.
Misclassified samples: In addition to the OOD scores, we also report the results for the detection of misclassiiid samples with aleatoric and epistemic uncertainty on several datasets and models in App. E.3 for the sake of completeness. GPN performs competitively with the baselines. Moreover, we observe that epistemic uncertainty is better for OOD detection and aleatoric uncertainty is better for misclassification detection as already observed e.g. in [022.
Model
ID-ACC OOD-AUC-ROC
OOD-ACC OOD-AUC-ROC af Bee(0.5)
OOD-ACC
OOD-AUC-ROC
Leave-Out Classes
~
Matern- GGP
87.03
88. 13 82.98 / n.a.
1.a.
T.a.
11.0.
G.G. 40.53
Propotr
89:08
81.27 71.65
77.76
62.06 / 50.38
18.28
(M.3/71106/10
ComMI.
EecCN-Eergy
89:60
81.70 183 13.115/1 mas.
78.90
G8 1 06, m..
18.37
9.34/ 0.32/ n... n.e.
VGCN-Ensemble
89.57
81.85 74.24/ n.a.
78.00
63.58/ / 56.81 r...
21.00
33.72 64.92 n.e.
GKDE-GCN
89.33
82.21 82.00/ /
76.40
61.74/ 63. 15
16.86
40.03/
1.42/ 96.56 100.00
GPN
88.51
83.2 866 28 80.95
80.30 98.98
99 / 56. 23/ 189-
81.53
65.96/
Maten-GGP
88.65
87. 26 16. n....
1..6.
VGCN-Dropout
n.a.
85 55. m...
22.29
66.71/
Amazzo Photos
VGCN-Energy
94.24
82.44 79.64 n.a.
53.91
57.91 7 50.07 ru...
21.40
31.07/ 6.42/ n....
94 228
82. 88.33 su...
84.40
67 86 / 01.01/ ma...
20.30
44.14 69.01 Fi.e.
GKDE-GON
89.81
73.65
73:17
588 00/ ru..
24.45/
GPN
94.01
82.72 91.98 76.57
87.47
56.25 / 60.52 75.24
88.29
51.89 61.89/ 100.00
Matem-GGP GGP
nt.f-
ft.f-
v.J.
PoCo-Dropout
75.47
65.35 61.21/
11.1 50.0000 61/ ra.s.
62 87 n....
OGBN Arxiv
VGCN-Eaergy
75.61
64.91
64.550 n.a.
65.70
46.16. 7 54 r.a.
51.30
53.83 53.33 n.o.
NGGN--Fnsemblee
76.12
60.933
70.77 / m....
67.00
45.99 / /47.4 mi...
49.00
59.94/
66. (4:44 i....
GKDE-GCN
68.8 08.81/ 72.44/ m.a.
65.20
98.98/18
53,91 /5.555555 28 n....
GPN
73.84
66.33 74. 62.17
65.50
51.49 / 55.82 /3.05
65.50
51.43 55.85 95.54
Table I: LOC and Feature Perturbations: Accuracy is reported on ID nodes for LOC experiments and on OOD nodes for feature perturbation experiments. OOD-AUC-ROC scores are given as [Alea w/ Net] / (Epist w/ Net] / [Epist w/o Net]. n.a. means either model or metric not applicable and f. means not finished within our constraints.
Attributed Graph Shifts. In this section, we focus on evaluating the robustness of the accuracy, calibration and the evolution of the uncertainty estimation under node feature shifts and edges shifts. This aligns with (78) which aims at evaluating the reliability of uncertainty estimates under dataset shifts for i.i.d. inputs. Specifically, we evaluates the evolution of the accuracy, the ECE (70 calibration score, the epistemic and the aleatoric uncertainty measures.
Feature shifts: We perturbed the features of fraction of the nodes using unit Gaussian perturbations. We report the short results in Fig. 3 and the full results in appendix. On one hand, we observe that GPN is significantly more robust to feature perturbations than all baselines. Indeed, the accuracy of GPN decreases by less than 5% even when 80% of the nodes are perturbed while the accuracy of other baselines decreases by more than 50% when only 20% of the nodes perturbed. Similarly, observed that GPN remains calibrated even when a high fraction of nodes are perturbed contrary to baselines. Hence, GPN intuitively discards uncertain features from perturbed nodes and only accounts for certain features from other nodes for more accurate predictions. On the other hand, we observe that, as desired, the average epistemic uncertainty of GPN consistently decreases when more nodes are perturbed. This remark aligns with Ax. 3.2 In contrast, baselines dangerously become more certain while achieving a poorer accuracy similarly to ReLU networks (39 Hence GPN predictions are significantly more reliable than basclines under feature shifts.
Edge shifts: For edge shifts, we perturbed fraction of edges at random. We report the results in appendix. As desired, we observe that the aleatoric uncertainty increases for all models including GPN. This aligns with Ax. 3.3 and the expectations that conflicting neighborhood should lead to more aleatorically uncertain predictions. Furthermore, the average epistemic uncertainty of GPN remains constant which is reasonable since the average evidence of node's neighborhood remains constant.
Qualitative Evaluation. We show the abstracts of the CoraMI. papers achieving the highest and the lowest epistemic uncertainty without network effects in Tab. 2 and in the appendix. Interestingly, we
9

---

Accuracy
ECE
Rel. Epis. Conf.
100000N
80%
0.8
10000%
60%
1000%
150%
40%
0.4
100%
20%
0.2
50%
20% 40%
80%
20% 40%
Perturbed Nodes (%]
Perturbed Nodes [%)
Perturbed Nodes (%)
APPNP VGCN
VGCN-Dropout VGCN-Energy
VGCN-Ensemble RGCN
GDK-GCN
GPN
Figure 3: Accuracy, ECF, and average epistemic confidence under feature shifts for CoraMI., We perturb features of different percentage of nodes using a Unit Gaussian noise.
observed that most uncertain papers corresponds short and unconventional abstracts which can be seen as anomalous features. Furthermore, we also ranked the nodes w.r.t. to their epistemic uncertainty with network effects. In this case, observed that 78/ /100 nodes with the highest uncertainty do not belong to the largest connected component of the CoraMI. dataset. We propose additional uncertainty visualizations for GPN in App. E.6
Inference & training time. We provide a comparison of inference and training times for most of the datasets and models under consideration in in App. E.7 GPN needs single pass for uncertainty estimation but requires the additional evaluation of one normalizing flow per class compared to APPNP. Hence, GPN brings small computational overhead for uncertainty estimation inference time. Furthermore, GPN is usually converging relatively fast during training and does not require pre- computing kernel values. In contrast, GKDE-GCN [I02] requires the computation of the underlying Graph Kernel with a complexity of (N2) where N is the number of nodes in the graph. Finally, GPN is significantly more efficient than dropout ensemble approaches it does not require training or evaluating multiple models.
Report
July
Report
Hortsthop
FAttit-Repprrt Org/Reporte/ar 36 Eretelle an: 21.06.91 Borrigiert an: 28. 05, 96 1889 0992-4137
really can talk about, and dieparage knoclodge that vo can't verbalize. [Doeling 1999, p. 252]
Keith Nathiax and Barrell Whieley Technical Report 0S-94-101 Jamurry 1994
Iuleigrid Q-Laarning Charl ax w. Anderson and Stewart Crauford-Hina Technical Report CS-94-121 Detober 11, 1994
Isternal Report 97-01
Learning Reault for Abstract
Table 2: A selection of abstracts from CoraML which are assigned low feature evidences by GPN,
Conclusion
We introduce a well-grounded framework for uncertainty estimation on interdependent nodes. First, we propose explicit and motivated axioms describing desired properties for aleatoric and epistemic uncertainty
absence or the presence of network effects. Second, we propose GPN, a GNN for uncertainty estimation which provably follows our axioms. GPN performs Bayesian update over the class predictions based on density estimation and diffusion. Third, we conduct extensive experiments to evaluate the uncertainty performances of a broad range of baselines for OOD detection and robustness against node feature or edge shifts. GPN outperforms baselines these experiments.
Acknowledgments and Disclosure of Funding
This research supported by the BMW AG, by the Helmholtz Association under the joint research school "Munich School for Data Science - MUDS", and by grant from Software Campus through the German Federal Ministry of Education and Research.
10

---

References
[1] The assessment list for trustworthy artificial intelligence (altai) for self assessment. European Commission, 2020.
[2] M. Abadi, A. Agarwal, P. Barham, E. Brevdo, Z. Chen, C. Citro, G. S. Corrado, A. Davis, J. Dean, M. Devin, S. Ghemawat, Goodfellow, A. Harp, G. Irving. M. Isard. Y. Jia, R. Joze- fowicz, L. Kaiser, M. Kudlur, J. Levenberg, D. Mané, R. Monga, S. Moore, D. Murray, C. Olah, M. Schuster, Shlens, B. Steiner, I. Sutskever, K. Talwar, P. Tucker, V. Vanhoucke, V. Va- sudevan, F. Viégas, O. Vinyals, P. Warden, M. Wattenberg, M. Wicke, Y. Yu, and X. Zheng. Large-scale machine learning on heterogeneous systems, 2015.
TensorFlow:
[3] M. Abdar, F. Pourpanah, S. Hussain, D. Rezazadegan, I.. Liu, M. Ghavamzadeh, P. Fieguth, A. Khosravi, U. R. Acharya, V. Makarenkov, al. A review of uncertainty quantification in deep learning: Techniques, applications and challenges. arXiv preprint Ttii:2011.06222.. 2020.
[4] H. Ahn, S. Cha, D. Lee, and T. Moon. Uncertainty-based continual learning with adaptive regularization. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Buc; E. Fox, and Garnett, editors, Advances in Neural Information Processing Systems, 2019.
[5] H. Akita, K. Nakago, T. Komatsu, Y. Sugawara, S.-i. Maeda, Y. Baba, and H. Kashima. Bayesgrad: Explaining predictions of graph convolutional networks. In Advances in Neural Information Processing Systems, 2018
[6] A. Amini, W. Schwarting, A. Soleimany, and D. Rus. Deep evidential regression. In Advances in Neural Information Processing Systems, 2020.
[7] R. Arora, A. Basu, P. Mianjy, and A. Mukherjee. Understanding deep neural networks with rectified linear units. In International Conference on Learning Representations, 2018.
[8] M. Biloš, B. Charpentier, and S. Günnemann. Uncertainty on asynchronous time event prediction. Advances in Neural Information Processing Systems, 2019.
[9] C. Blundell, J. Cornebise, K. Kavukcuoglu, and D. Wierstra. Weight uncertainty in neural network. In International Conference on Machine Learning. 2015.
[10] A. Bojehevski and S. Günnemann. Deep gaussian embedding of graphs: Unsupervised inductive learning via ranking. arXiv preprint arXiv:/707.038/5, 2017.
[11] A. Bojchevski and S. Günnemann. Bayesian robust attributed graph clustering: Joint learning of partial anomalies and group structure. AAAI Conference on Artificial Intelligence, 2018.
[12] V. Borovitskiy, I. Azangulov, A. Terenin, P. Mostowsky, M. Deisenroth, and N. Durrande. Matérn Gaussian Processes on Graphs. In International Conference on Artificial Intelligence and Statistics, 2021.
[13] N. Carlini and D. Wagner. Adversarial examples are not easily detected: Bypassing ten detection methods. Computing Research Repository, 2017.
[14] B. Charpentier, D. Zügner, and S. Günnemannn Posterior network: Uncertainty estimation without ood samples via density-based pseudo-counts. Advances in Neural Information Processing Systems, 2020.
[15] B. Charpentier, O. Borchert, D. Zügner, S. Geisler, and S. Günnemann. Natural posterior network: Deep bayesian predictive uncertainty for exponential family distributions, 2021.
[16] J. Chen, T. Ma, and C. Xiao. Fastgen: fast learning with graph convolutional networks via
importance sampling. arXiv preprini arXiv: 10.44 2018.
[17] H. Choi, E. Jang, and A. A. Alemi, Generative ensembles for robust anomaly detection. In International Conference on Learning Representations, 2019.
[18] W. R. Clements, B. Delft, B.-M. Robaglia, R. B. Slaoui, and S. Toth. Estimating risk and uncertainty in deep reinforcement learning, 2019.

---

[19] M. Dallachiesa, C. Aggarwal, and T. Palpanas. Node classification in uncertain graphs. In Proceedings of the 26th international conference on scientific and statistical database munagement, pages 1-4, 2014.
[20] S. Depeweg, J.-M. Hernandez-Lobate F. Doshi Velez, and S. Udluft. Decomposition of uncertainty in bayesian deep learning for efficient and sensitevee learning. In International Conference on Machine Learning, 2018.
[21] M. W. Dusenberry, G. Jerfel, Y. Wen, Y.-A. Ma, J. Snoek, K. Heller, B. Lakshminarayanan, and D. Tran. Efficient and scalable bayesian neural nets with rank-1 factors. In International Conference on Machine Learning, 2020.
[22] P. Elinas, E. V. Bonilla, and L. Tiao. Variational inference for graph convolutional networks in the absence of graph data and adversarial settings. Advances in Neural Information Processing Systems, 2020.
[23] D. Eswaran, S. Günnemann, and C. Faloutsos. The power of certainty: A dirichlet-multinomiill model for belief propagation. In Proceedings of the 2017 SIAM International Conference on Data Mining, 2017.
[24] S. Farquhar, L. Smith, and Y. Gal. Liberty or depth: Deep bayesian neural nets do not need complex weight posterior approximations. In Advances in Neural Information Processing Systems, 2020.
[25] B. Feng, Y. Wang, Z. Wang, and Y. Ding. Uncertainty-aware attention graph neural network for defending adversarial attacks. arXiv preprint 2000:::000.2/233333 2020.
[26] M. Fey and J. E. Lenssen. Fast graph representation learning with Py PyToch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
[27] A. Y. Foong, D. R. Burt, Y. Li, and E. Turner. On the expressiveness of approximate inference in bayesian neural networks. arXiv preprint arXiv:1909.0077 2019.
[28] Y. Gal. Uncertainty in Deep Learning. 2016
[29] Y. Gal and Z. Ghahramani. Dropout as bayesian approximation: Representing model uncertainty in deep learning. In International Conference on Machine Learning, 2016.
[30] Y. Gal and L. Smith. Sufficient conditions for idcalised models to have adversarial examples: a theoretical and empirical study with bayesian neural networks, 2018
[31] L. Getoor. Link-based classification. In Advanced methods for knowledge discovery from complex data. Springer, 2005.
[32] C. L. Giles, K. D. Bollacker, and S. Lawrence. Citeseer: An automatic citation indexing system. In Proceedings of the third ACM conference on Digital libruries, pages 89-98, 1998.
[33] W. Grathwohl, K.-C. Wang. J.-H. Jacobsen, D. Duvenaud, M. Norouzi, and K. Swersky. Your classifier is secretly an energy based model and you should treat it like one. arXiv preprint 1rXiv:1912.0326: 2019.
[34] A. Graves. Practical variational inference for neural networks. In Advances in Neural Information Processing Systems. Citeseer, 2011.
[35] C. Guo, G. Pleiss, Y. Sun, and K. Q. Weinberger. On calibration of modern neural networks. In International Conference on Machine Learning, 2017.
[36] S. Günnemann. Graph neural networks: Adversarial robustness. In L. Wu, P. Cui, J. Pei, and L. Zhao, editors, Graph Neural Networks: Foundations, Frontiers, and Applications, chapter pages 149-176. Springer, Singapore, 2021.
[37] A. Hasanzadeh, E. Hajiramezanali, S. Boluki, M. Zhou, N. Duffield, K. Narayanan, and X. Qian. Bayesian graph neural networks with adaptive connection sampling. International Conference on Machine Learning, 2020.
12

---

[38] M. Havasi, R. Jenatton, S. Fort, J. Z. Liu, J. Snoek, B. Lakshminarayanan, A. M. Dai, and D. Tran. Training independent subnetworks for robust prediction. In International Conference on Learning Representations, 2021.
[39] M. Hein, M. Andriushchenko, and J. Bitterwolf. Why relu networks yield high-confidence predictions far away from the training data and how to mitigate the problem. Computer Vision and Pattern Recognition, 2019.
[40] L. Hirschfeld, K. Swanson, K. Yang, R. Barzilay, and C. W. Coley. Uncertainty quantification using neural networks for molecular property prediction, 2020.
[41] J. Hron, A. Matthews, and Z. Ghahramani. Variational bayesian dropout: pitfalls and fixes. In International Conference on Machine Learning, 2018.
[42] J. Hu, R. Cheng, Z. Huang, Y. Fang, and S. Luo. On embedding uncertain graphs. In Information and Knowledge Management, 2017.
[43] W. Hu, M. Fey, M. Zitnik, Y. Dong, H. Ren, B. Liu, M. Catasta, and Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint arXiv:2005.00687, 2020.
[44] Q. Huang, H. He, A. Singh. S.-N. Lim, and A. R. Benson. Combining label propagation and simple models out- out-performs graph neural networks. arXiv preprint arXiv:2010.13993 2020.
[45] D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6640 2014.
[46] T. N. Kipf and M. Welling, Semi-Supervised Classification with Graph Convolutional Net- works, International Conference on Learning Representations, 2016.
[47] P. Kirichenko, P. Izmailov, and A. G. Wilson. Why normalizing flows fail to detect out-of- distribution data. arXiv preprint arXiv:2006. 08545, 2020.
[48] J. Klicpera, A. Bojchevski, and S. Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. arXiv preprint 1oXiv:1810..533 2018.
[49] J. Klicpera, S. Weilsenberger, and S. Günnemann. Diffusion improves graph learning, arXiv preprint arXiv:1911.05445 2019.
[50] A. Kopetzki, B. Charpentier, D. Zügner, S. Giri, and S. Günneeannn Evaluating robustness of predictive uncertainty estimation: Are dirichlet-based models reliable? Computing Research Repository, 2020.
[51] A. Kristiadi, M. Hein, and P. Hennig. Being bayesian, even just bit, fixes overconfidence in relu networks, 2020.
[52] B. Lakshminarayanan, A. Pritzel, and C. Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. In Proceedingy of the 31 International Conference on Neural Information Processing Systems, pages 6405-6416 2017.
[53] B. Lakshminarayanan, D. Tran, J. Liu, S. Padhy, T. Medrax-Weiss and Z. Lin. Simple and principled uncertainty estimation with deterministic deep learning via distance awareness. In Advances in Neural Information Processing Systems, 2020.
[54] C. Lan and Dinh. Perfect density models cannot guarantee anomaly detection. arXiv preprint arXiv:2012.03800 2020.
[55] H. B. Lee, H. Lee, D. Na. S. Kim, M. Park, E. Yang, and S. J. Hwang. Learning to balance: Bayesian meta-learning for imbalanced and out-of-distribution tasks, 2020.
[56] S. Liang, Y. Li, and R. Srikant. Enhancing the reliability of out-of-distribbtioo image detection in neural networks. arXiv preprint arXiv:1706 02690, 2017.
[57] W. Liu, X. Wang, Owens, and Li. Energy-based aatto--distriuution detection. Advances in Neural Information Processing Systems, 2020.
13

---

[58] Z.-Y. Liu, Li, S. Chen, Y. Hu, and S.-J. Huang. Uncertainty aware graph gaussian process for semi- -upeerupee learning. In AAAI Conference on Artificial Intelligence, volume 34, pages 4957-4964, 2020.
[59] W. J. Maddox, P. Izmailov, T. Garipov, D. P. Vetrov, and A. G. Wilson. A simple baseline for bayesian uncertainty in deep learning. In Advances in Neural Information Processing Systems, 2019.
[60] A. Malinin and M. Gales. Predictive uncertainty estimation via prior networks. arXiv preprint X8v: 10501, 2018.
[61] Malinin and M. Gales. Reverse kl-divergence training of prior networks: Improved uncer- tainty and adversarial robustness. arXiv preprint arXiv: (905: 2019.
[62] A. Malinin, A. Ragni, K. Knill, and M. Gales. Incorporating uncertainty into deep learning for spoken language assessment. In Annual Meeting of the Association for Computational Linguistics, 2017.
[63] A. Malinin, B. Mlodozeniec, and M. Gales, Ensemble distribution distillation. arXiv preprint arXiv:1905.0000 2019.
[64] J. McAuley, C. Targett, Q. Shi, and Van Den Hengel. Image-based recommendations on styles and substitutes. In Research and Development in Information Retrieval, 2015.
[65] A. K. McCallum, K. Nigam, J. Rennie, and K. Seymore. Automating the construction of internet portals with machine learning. Information Retrieval, 2000.
[66] Meinke and M. Hein. Towards neural networks that provably know when they don't 't know. In International Conference on Learning Representations, 2020.
[67] C. Molnar. Interpretable machine learning, 2020. URL.Ittps://christppph wtt.tttooopmiiit........... io/
interpretable-m1-Be
[68] P. Morales-Alvarez, D. Hernández-Lobato, R. Molina, and M. Hernandez-Lobate Activation- level uncertainty in deep neural networks. In International Conference on Learning Represen- tations, 2021.
[69] W. R. Morningstar, C. Ham, A. G. Gallagher, Lakshminarayanan, A. A. Alemi, and J. V. Dillon. Density of states estimation for out-of-distribution detection. arXiv preprint TTti:20000092773 2020.
[70] M. P. Naeini, G. Cooper, and M. Hauskrecht. Obtaining well calibrated probabilities using bayesian binning. In AAAI Conference on Artificial Intelligence, volume 29, 2015.
[71] E. Nalisnick, A. Matsukawa, Y. W. Teh, D. Gorur, and B. Lakshminarayanan. Do deep generative models know what they don't 't know? International Conference on Learning Representations, 2019.
[72] E. Nalisnick, A. Matsukawa, Y. W. Teh, and B. Lakshminarayanan. Detecting out-of- distribution inputs to deep generative models using typicality. arXiv preprint arXiv: 1906.02994 2020.
[73] G. Namata, B. London, L. Getoor, B. Huang, and U. M. D. EDU. Query-driven active surveying for collective classification. In 10th International Workshop on Mining and Learning with Graphs, 2012.
[74] Y. C. Ng. N. Colombo, and R. Silva. Bayesian semi-supervised learning with graph gaussian processes. arXiv preprint N0Xiv:8800003333 2018
[75] C. Nguyen, T.-T. Do, and G. Cameiro. Uncertainty in model-agnostic meta-learning using variational inference, 2019.
[76] M. Orbach and K. Crammer. Graph-based transduction with confidence. In P. A. Flach, T. De Bie, and N. Cristianini, editors, Machine Learning and Knowledge Discovery in Databases, 2012.
14

---

[77] I. Osband. Risk versus uncertainty in deep learning: Bayes, bootstrap and the dangers of dropout. In NeurIPS Workshop on Bayesian Deep Learning. 2016.
[78] Y. Ovadia, E. Fertig, J. Ren, Z. Nado, D. Sculley, S. Nowozin, J. V. Dillon, B. Lakshmi- narayanan, and J. Snoek. Can you trust your model's uncertainty? evaluating predictive uncertainty under dataset shift. arXiv preprint
2019.
[79] S. Pal, F. Regol, and M. Coates. Bayesian graph convolutional neural networks using node copying. arXiv preprini 191 1.04965, 2019.
[80] S. Pal, F. Regol, and M. Coates. Bayesian graph convolutional neural networks using non- parametric graph learning. arXiv preprint 1IXv:1910.121122, 2019.
[81] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Kopf, E. Yang. Z. DeVito, M. Raison, A. Te- jani, S. Chilamkurthy, B. Steiner, L. Fang, J. Bai, and S. Chintala. Pytorch: An imperative style. begh--erformacce deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer,
F. d'Alché-Bue E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems. 2019.
[82] D. Rezende and S. Mohamed. Variational inference with normalizing flows. In International Conference on Machine Learning, 2015.
[83] Y. Rong. W. Huang, T. Xu, and J. Huang. Dropedge: Towards deep graph convolutional networks on node classification. arXiv preprint arXiv: 1907. 2019.
[84] S. Ryu, Y. Kwon, and W. Y. Kim. Uncertainty quantification of molecular property prediction with bayesian neural networks. arXiv preprint 1903:::903.088. 2019.
[85] P. Sen, G. Namata, M. Bilgic, L. Getoor, B. Galligher, and T. Eliassi-Rad Collective classifi- cation in network data. Al magazine, 29(3):93-9) 2008
[86] M. Sensoy, L. Kaplan, and M. Kandemir. Evidential deep learning to quantify classification uncertainty. In Advances in Neural Information Processing Systems, 2018
[87] O. Shchur, M. Mumme, A. Bojchevski, and S. Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint 1rXiv:1811.0586 2018.
[88] N. Srivastava, G. Hinton, A. Krizhevsky, Sutskever, and R. Salakhutdinov. Dropout: simple way to prevent neural networks from overfitting. The journal of machine learning research, 2014.
[89] D. Stutz, M. Hein, and B. Schiele. Confidence-calirrae adversarial training: Generalizing to unseen attacks. In H. D. III and A. Singh, editors, International Conference Machine Learning, Proceedings of Machine Learning Research, 2020.
[90] K. Tran, W. Neiswanger, J. Yoon, Q. Zhang, E. Xing, and Z. W. Ulissi. Methods for comparing uncertainty quantifications for material property predictions, 2020.
[91] J. van Amersfoort, L. Smith, Y. W. Teh, and Y. Gal. Uncertainty estimation using single deep deterministic neural network, 2020.
[92] P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Lio, and Y. Bengio. Graph attention networks. arXiv preprint 1700:/7110.1003 2017.
[93] H. Wang and J. Leskovec. Unifying graph convolutional neural networks and label propagation. arXiv preprint arXiv:2002.06755, 2020.
[94] K. Wang. Z. Shen, C. Huang, C.-H. Wu, Y. Dong, and A. Kanakia. Microsoft academic graph: When experts not enough. Quantitative Science Studies, 2020.
[95] M. Waniek, T. P. Michalak, M. J. Wooldridge, and T. Rahwan. Hiding individuals and communities in social network. Nature Human Behaviour, 2018.
15

---

[96] Y. Wen, D. Tran, and J. Ba. Batchensemble: an alternative approach to efficient ensemble and lifelong learning. International Conference on Learning Representations, 2020.
[97] F. Wenzel, J. Snock, D. Tran, and R. Jenatton. Hyperparameter ensembles for robustness and uncertainty quantification. Advances in Neural Information Processing Systems, 2020.
[98] J. Winkens, R. Bunel, A. Guha Roy, R. Stanforth, V. Natarajan, J. R. Ledsam, P. Mac P. Kohli, A. Karthikesalingam, S. Kohl, T. Cemgil, S. M. A. Eslami, and O. Ronneberger. Con- trastive training for improved outtof-distribution detection. arXiv preprint arXiv:2007.05566. 2020.
[99] H. Zhan and X. Pei. I-gen: Robust graph convolutional network via influence mechanism. arXiv preprint arXiv:2012.06110, 2020.
[100] Y. Zhang and Others. Bayesian semi-supervised learning for uncertainty-calibraeee prediction of molecular properties and active learning. Chemical science, 2019.
[101] Y. Zhang, S. Pal, M. Coates, and D. Ustebay. Bayesian graph convolutional neural networks for semi-supervised classification. In AAAI Conference on Artificial Intelligence, 2019.
[102] X. Zhao, F. Chen, S. Hu, and J.-H. Cho. Uncertainty aware semi-supervised learning on graph data. Advances in Neural Information Processing Systems, 2020.
[103] Y--. Zhi, Y. C. Ng, and Dong. Gaussian processes on graphs via spectral kernel learning. arXiv preprint arXiv:2006. 0e0-20066.7361, 2020.
[104) D. Zhu, 7. Zhang, P. Cui, and W. Zhu. Robust graph convolutional networks against adversarial attacks. In SIGKDD International Conference on Knowledge Discovery & Data Mining, 2019.
[105] J. Zhu, Y. Yan, L. Zhao, M. Heimann, L. Akoglu, and D. Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. In H. Larochelle, M. Ranzato, Hadsell, M. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, 2020.
[106] D. Züggner and S. Günnemann. Adversarial attacks on graph neural networks via meta learning. In ICLR, 2019.
[107] D. Zügner, A. Akbarnejad. and S. Günnemann. Adversarial attacks on neural networks for graph data, In SIGKDD, 2018.
16


Reviews:
[{"review_id": "wALGhSGTkIO", "reviewer": "Reviewer_fvEX", "summary": "The paper makes three contributions: (i) three axioms are specified to characterize the requirements of predictive uncertainty behaviour in homophilic attributed graphs; (ii) a new inference model is proposed and theorems are provided that demonstrate how the model behaves with respect to its characterization of uncertainty; and (iii) via numerical experiments, it is demonstrated that the proposed model achieves better uncertainty estimation performance.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper contains some very interesting ideas and the proposed model is well-constructed. The experiments are thorough, with comparison to multiple baselines across 8 datasets. These experiments demonstrate that the proposed model significantly outperforms existing methods in terms of its uncertainty quantification for the task of node classification. \n\nOn the negative side, the paper is very difficult to read, and there needs to be considerably more care with definitions of terms and explanations of concepts. \n\n(1) The axioms are imprecisely stated and contain important elements that are not defined. \nThe figures used to explain the axioms introduce concepts and variables that are not defined or explained until later in Section 3.2. For example, it is not clear what Dirichlet distribution is being referred to. \n\nIn Axiom 3.1 it is written “A node with features more different from training features should be assigned higher uncertainty”. This sentence raises several questions. How is “different” defined or measured? What does it mean to “assign a node higher uncertainty”? When the axiom is imprecise in this way, it is very difficult to claim that a particular model obeys it. The authors claim that “The first theorem shows that GPN follows Ax. 3.1” but it actually shows something that is much more specific. It only characterizes the behaviour of the prediction as the distance (measured in any way) approaches infinity. It does not establish that for one node with “more different” features than another the uncertainty in the prediction will be higher (for some definition of “different” and some definition of “uncertainty”).  \n\nAxiom 3.2 states that “a node’s prediction… should have higher aleatoric uncertainty”. At this stage of the paper, there is no quantitative definition of aleatoric or epistemic uncertainty. The approaches to quantitatively assess these are only made clear in Section 3.2. \n\nThe text after Axiom 3.2 is confusing: “a node $v$ with confident feature predictions $x^{(v)}$. Above $x^{(v)}$ are specified as node features. Now they are node feature “predictions”?  \n\nIn a similar vein, “more conflicting” in Axiom 3.3. is not defined. \n \nAre the axioms supposed to relate to only a predictive model under a specific framework for uncertainty characterization? Or do we need to provide definitions and metrics for of all of these concepts – “uncertainty”, “aleatoric uncertainty”, “epistemic uncertainty”, “different”, “conflicting” – as well as the predictive model?\n\n(2) It is extremely difficult to understand the proposed method and model from Section 3.2 alone. There is too much reliance on material from [14, 15]. While it is fine to refer a reader to other papers for further information and detail, the main method should be clear for a reader without it being essential to refer to other work. For example, phrases like “the epistemic uncertainty can be measured by the pseudo-count $\\alpha_0$ of fictitious observations” are very hard to understand when “fictitious observations” have not been defined or introduced.  \n\nOverall, I would like to recommend the paper for acceptance based on its technical content, but I think the axioms and the presentation need major improvement.\n\n***\nAfter author response: I acknowledge that the authors have provided a thorough commentary regarding my criticisms and they can all be addressed by modifying the text (although I view these changes as being important, since I think some of the claims about the theoretical results are not strictly correct as they stand and the axioms are vague). I have raised my overall score.\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours"}, "extra_text": {}}, {"review_id": "Xl8nYfaDbfu", "reviewer": "Reviewer_H3WY", "summary": "In this paper, the authors proposed a graph posterior network based on the uncertainty theory to enhance the node classification in graph learning. The uncertainty estimation based on the interdependent node inputs instead of assuming i.i.d inputs is interesting. Through theoretical analysis and experiments on 8 data sets, they claim that the proposed framework has advantages in node classification and OOD detection.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "In general, the node classification based on uncertainty is not a new problem. However, the proposed method study the influence of the interdependent inputs on GNN is new. Furthermore, the proposed Graph Posterior Network is a combination of two existing methods. One is APPNP [47], the other is PostNet [14]. It is good to see that the authors discussed the key difference between this paper and the above two papers. The authors provide relatively comprehensive related works from two perspectives (Uncertainty for i.i.d. inputs and Uncertainty for graphs).  \n\nThis submission is technically sound. Most claims are well supported by theoretical analysis and experiments. The proposed method theoretically proves the appropriateness of the fusion of the two known methods. Furthermore, the authors also discussed the limitations of their approach, which is good for understanding the applicability of their method in real-world tasks. This work is complete.\n\nThe paper is well-written in several sections. However, the Axioms and Theorems in Section 3 seem too dense. I suggest the authors can draw a figure to show the relationships between each Axiom and each theorem. The authors had provided many experiment details in the Appendix to reproduce the results in the main paper.\n\nThe results shown in this paper seem important. The researchers or practitioners may like to use the ideas from this paper in their research works. According to the experiment results, this paper advances the state of the art in a demonstrable way. The proposed method is tested on several existing data. There are no unique data, unique theoretical, and unique experimental approaches.\n\nMy major comments are as follows,\n\n1. In table 1, why baseline methods do not have values in [Epist w/o Net]? What is the meaning of '_'?\n\n2. It is hard to see the efficiency of the proposed methods compared to the baseline methods. \n\nMy minor comments are as follows,\n\n1. In line 359, Tab.3 should be Figure 3.\n\n2. In line 375, Tab.10 should be Table 2.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors discussed the limitations of the proposed method.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "HikOL_DflVt", "reviewer": "Reviewer_jUVU", "summary": "This paper introduced a well-grounded framework for uncertainty estimation on interdependent nodes. This paper first proposed explicit and motivated axioms describing desired properties for aleatoric and epistemic uncertainty in the absence or in the presence of network effects. Then it proposed GPN, a GNN for uncertainty estimation which provably follows our axioms. Furthermore, extensive experiments was conducted to evaluate the uncertainty performances of a broad range of baselines for OOD detection and robustness against node features or edge shifts. GPN outperforms all baselines in these experiments.", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper is well written and pertinent to the NeurIPS. The related work is extensive and impressive, I like the Axioms style. But I have some concerns about the experiment part.\n\n1. Since GPN was designed based on APPNP and PostNet, it is necessary to do an ablation study to analyze the contribution of each component. \n\n2. It might be necessary to add one important baseline, PostNet (ignore graph) or PostNet+GCN (simply combine PostNet and GCN), to show the advantage of GPN over PostNet in graph data.\n\n3. For baseline GKD-GCN, it should be evaluated based on vacuity uncertainty, which is naturally designed to detect OOD. Note that GKD-GCN was proposed to improve the estimation of vacuity.\n\n4. It is better to evaluate the proposed method in the misclassification detection task, which is an important task in uncertainty estimation [1] [2]. And this paper also discussed aleatoric uncertainty, which is not appropriate for OOD detection but is suitable for misclassification detection.\n\n5. Why was GPN robust to feature perturbations, especially for accuracy? Which component supports this observation?\n\nSome minor issues:\n\n1. The indexes (1), (2), (3) are missing in Figure 2.\n2. Typo in Table 1, “GDK-GCN” → “GKD-GCN”.\n3. Typo in Line-358, “Tab. 3” → “Figure 3”\n\n[1] Hendrycks, Dan, and Kevin Gimpel. \"A baseline for detecting misclassified and out-of-distribution examples in neural networks.\" ICLR 2017.\n\n[2] Malinin, Andrey, and Mark Gales. \"Predictive uncertainty estimation via prior networks.\" NeurIPS 2018.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes,  the authors adequately addressed the limitations and potential negative societal impact of this work.", "review_text": "", "extra_scores": {"ethical_concerns": "No Ethical Concerns", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper first proposes axioms describing desired properties of uncertainty in the absence or in the presence of network effects. It then  introduces a novel framework for uncertainty estimation in the graph setting (graph posterior networks). The problem of uncertainty estimation in the graph setting is interesting and relevant and has received much less attention than more standard supervised learning settings. The approach is technically correct. AN extensive set of the experiments includes the assessment of uncertainty estimation quality for OOD detection as well as the assessment of robustness against shifts in attributed graph properties. The proposed approach shows promising performance in these experiments. Following the author response and discussion, the reviewers were in agreement that the paper should be accepted. One concern raised in several of the reviews was that the paper could benefit from reducing the density of the exposition and the reliance on reader familiarity with results from prior works. The authors have committed to addressing these issues in the revised manuscript. 
Decision: Accept (Poster)