Improvements on Uncertainty Quantification for Node Classification via Distance Based Regularization
Authors: Russell Alan Hart
Linlin Yu
Yifei Lou
Feng Chen
Venue: NeurIPS 2023 poster (2023)
Keywords: Uncertainty Quantification
Graph Posterior Network
Bayesian
TL;DR: Distance minimization improves out distribution detection

Abstract: Deep neural networks have achieved significant success in the last decades, but they are not well-calibrated and often produce unreliable predictions. A large number of literature relies on uncertainty quantification to evaluate the reliability of a learning model, which is particularly important for applications of out-of-distribution (OOD) detection and misclassification detection. We are interested in uncertainty quantification for interdependent node-level classification. We start our analysis based on graph posterior networks (GPNs) that optimize the uncertainty cross-entropy (UCE)-based loss function. We describe the theoretical limitations of the widely-used UCE loss. To alleviate the identified drawbacks, we propose a distance-based regularization that encourages clustered OOD nodes to remain clustered in the latent space. We conduct extensive comparison experiments on eight standard datasets and demonstrate that the proposed regularization outperforms the state-of-the-art in both OOD detection and misclassification detection.

Improvements on Uncertainty Quantification for Node Classification via Distance-Based Regularization
Russell Alan Hart The University of Texas at Dallas rahl50030eutdallll
Linlin Yu The University of Texas at Dallas linlin, yu@utdallas. edu
Yifei Lou
Feng Chen
University of North Carolina Chapel Hill yflou@unc.edt
The University of Texas at Dallas feng. wwwe@utdaallleeeeeccmccocc edu
Abstract
Deep neural networks have achieved significant success in the last decades, but they not well-calibrated and often produce unreliable predictions. A large number of literature relies on uncertainty quantification to evaluate the reliability of learning model, which is particularly important for applications of out-of- distribution (OOD) detection and misclassification detection. We are interested uncertainty quantification for interdependent node-level classification. We start analysis based on graph posterior networks (GPNs) that optimize the uncertainty cross-entropy (UCE)-based loss function. We describe the theoretical limitations of the widely-used UCE loss. To alleviate the identified drawbacks, we propose a distance-based regularization that encourages clustered OOD nodes remain clus- tered in the latent space. We conduct extensive comparison experiments on eight standard datasets and demonstrate that the proposed regularization outperforms the state-of-ae of-the-art art in both OOD detection and misclassification detection.
Introduction
In recent years, deep neural networks (DNNs) have been widely used in various fields 10
28
However, some neural networks provide under-confident (36) or over-confident [14] predictions, limiting their practical applications in risk-constrained and safety-critical fields, such drug discovery 38). autonomous driving (30), and medical diagnosis example. Uncertainty estimation the reliability of model predictions helps support molecular reasoning and experimental design by saving considerable time and resources
(2). Take autonomous drug design for an
[23]. It is important to
estimate the predictive uncertainty of a DNN, i.e., indicating when its predictions are likely incorrect. There are two main types of uncertainty: epistemic uncertainty (knowledge uncertainty) and aleatoric uncertainty (data uncertainty) [ Epistemic uncertainty due to the lack of knowledge about unseen data. Aleatoric uncertainty is caused by the inherent complexity of the data, which cannot be reduced by increasing the training data, including sources of noise such as homoscedastic or heteroscedastic noise [17]. These two uncertainty types are typically used for out-of-distribuite (OOD) and misclassification detection, respectively.
Most models have been introduced for uncertainty estimation on i.i.d. inputs, such as image and tabular data. However, the uncertainty estimation for classifying interdependent nodes in attributed graph data, such as social networks and citation networks, is under-explored. This work focuses on the node classification tasks with great potential to generalize others with interdependent inputs.
corresponding author
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Among various graph neural networks (GNNs) for processing graph data structures [8 graph posterior network (GPN) has been developed for superviiee node classification tasks that achieves state-of-the-art results in uncertainty estimation.
35 13
g
The major contributions of this paper are three-fold: (1) We theoretically analyze the limitations of GPN at OOD detection when minimizing uncertainty cross-entropy (UCE), a widely used loss function for uncertainty estimation. (2) Motivated by the aforementioned limitations, we propose
distance-based regularization that considers the prior knowledge that OOD-specific features are useful for learning representational space mappings. (3) We conduct extensive experiments comparing our proposed model with five state-of- of-the--rt art baselines on eight graph datasets for two uncertainty quantification tasks: OOD detection and misclassification detection tasks. The results demonstrate that our proposed regularization can improve the quality of uncertainty quantification.
2 Related Work
This section reviews existing uncertainty estimation methods for i.i.d data and graph data.
Uncertainty Quantification for i..d inputs There is plentiful research uncertainty quantifi- cation on i.i.d. inputs as discussed in a recent survey [. The first family quantifies the predictive uncertainty of a DNN via multiple forward passes, such as deep ensembles and stopout-based Bayesian neural networks (BNNs). Deep ensembles [19] intuitively sample multiple predictions by training an ensemble of deep neural networks and aggregate the results. propout-based methods 11 utilize multiple stochastic forward passes implemented with different dropout initializations to approximate the posterior distribution of network weights. However, the substantial memory and computational demands required for training and testing make it impractical for real-time applications. The second family quantifies uncertainty using deterministic single forward-pass neural networks, including density-based methods and distribution-base methods. The density-based approaches
typically fit a distribution (e.g.. class-wise Gaussian distribution B 20 34)
the representation space of pre-trained or fine-tuned DNN, followed by the associated PDF function to quantify different uncertainty types. The distribution- based methods train deterministic neural network that directly predicts the conjugate prior distribution of the class probabilities of the input feature vector, called Dirichlet distribution, for uncertainty quantification. The predicted Dirichlet distribution can be interpreted as an approximation of the posterior distribution of class probabilities conditioned on the input feature vector. Popular distribution- based models are prior networks networks [29]. and posterior networks (PN) 77, all using UCE as the loss function with different regularizations to improve the quality of uncertainty quantification.
[22], evidential
Uncertainty Quantification for Graphs As pointed out in the survey M. uncertainty quantification on GNNs and cemi-supervised learning is ender-explored. Most existing models for uncertainty quantification on graphs are either dropout-basee or BNN-based methods that typically drop or assign probabilities to edges. There are two approaches using deterministic single-pass GNNs to quantify uncertainty. One is called graph-based kernel Dirichlet distribution estimation (GKDE) 39, which consists of evidential GCN, sraph-based kernel, teacher network, dropout, and loss regularization. Another method is the GPN model that combines PN and personalized page rank (PPR) message passing to disentangle uncertainty with and without network effects. In addition, a recent method 37 used standard classification loss for OOD detection on graphs together with an energy function that is directly extracted from GNN, however, is limited to OOD detection, not generally on the topic of uncertainty quantification.
3 Preliminary
We discuss the problem setting of uncertainty quantification on the task of semi-supervised node classification Section 3.1 In particular, we use a deep neural network to predict the multinomial uncertainty for each node and evaluate the aleatoric uncertainty and epistemic uncertainty by the prediction result. In Section 3.2] we give brief review of the GPN model [32], which serves as a fundamental framework for our analysis and motivation for the proposed approach.
2

---

3.1 Problem Setting
We define a graph with attributed node-level features G (V, ; X, YL), where V a set of nodes on the graph with cardinality N and & C V x V denotes a set of graph edges that can be represented by an adjacency matrix W. A feature matrix denoted by X each x, IRd is feature vector of node with dimension d. Under the semi-supervised learning setting, a set of labels is available, denoted by YL {36 i E L) where L C V and Vi E {I....,K] K}
xv|" RNxd in which
for K classes.
Our goal is to design and learn a deterministic GNN based on G that takes the feature matrix X and the adjacency matrix W as INPUT and predicts the parameters of Dirichlet distribution for each node E V as OUTPUT, denoted as a, which is often referred to as the concentration parameters. Therefore, the network function Fe can be expressed as: A = Fe W), where A := ja,liev is matrix and @ refers to network parameters. The statistical relations between the class label yı. the vector of class probabilities pi, and the Dirichlet parameters a; can be represented
Pt Cat(p:), Paa, Dir(a.), [au]evv (X W).
(I)
Based on the predictions of A, the expected vector of class probabilities p: == F[p:|oo] =
/0.1/a0,,.. ... /ax//uz0 where 0: = =EA= Oik is called the Dirichlet strength. The aleatoric and epistemic uncertainties about the classification of each node i can be calculated as:
qt max (pa. . and ui -Q40+
(2)
respectively. The aleatoric uncertainty is measured by the negative of the largest class probability in D;- This uncertainty is higher when the largest class probability in P; is lower, which implies that the model is less confident and the probabilities are more evenly spread across classes. On the other hand, the epistemic uncertainty is measured by the negative of the Dirichlet strength ago, whose value is higher when the Dirichlet strength is lower, meaning that the model is unfamiliar with the feature vector of node and the predicted Dirichlet distribution is less concentrated around a specific point or set of points not indicate a high epistemic uncertainty and vice versa. For example, two evidence parameters a; = [I.... have the same projected class probabilities; but their epistemic uncertainties differ drastically: K versus 1000K, Please refer to 32 33 for rationales of aleatoric and epistemic uncertainties in (2).
the probability simplex (22) We note that high aleatoric uncertainty may
and a [1000,- ... 1000] have the same aleatoric uncertainty: 1//K, since they
3.2 Graph Posterior Network
which extends posterior network (PN) 77] to semi-supervised node classification. GPN consists of three main steps. First, feature encoder maps the original features onto a low-dimensional latent space with a simple two-layer multi-layer perception (MLP) encoder. Second, a radial normalizing flow (27] estimates the density of the latent space per class. Lastly, a personalized page rank message passing scheme [13] diffuses the pseudo counts (density multiplied by the number of training nodes) by taking the graph structure into account. We summarize the three steps with notations as follows,
Our framework based on graph posterior network (GPN) 32
1. Multi-layer perceptron for representation learning: z; = (x;; 0) or So in short.
2. Normalizing flow for density estimation: 9+ for short, and more specifically
g6 (z:)) N2 WVP-Pz,,kk:- (k:
where N₂ is the number of training nodes belonging to the class k. z, is the embedding vector of node obtained via the first step, ((z:|k: Φ) is the conditional density per class k estimated by a normalizing flow module, and @ denotes the parameters of this module. GPN also includes the evidence computed prior to the graph aggregation, defined by
(4) 3. Personalized page rank (PPR) for evidence diffusion: 3 = EjEy 16 (2,) where II refer to the dense PPR scores implicitly reflecting the importance of node j from the perspective of node i. Then we can get the predicted concentrate parameters a with a uniform prior I for non-degenerated Dirichlet distribution, i.e.,
a
feat
g (2:) + 1.
Q4
88 + 1.
(5)
3

---

As opposed to GPN, PN is designed for uncertainty estimation for i.idd. inputs, which only considers the first two steps to predict the Dirichlet distribution Dir(a
Given the labels of training nodes: Y = {ys | E L), GPN trained by minimizing the following Bayesian loss:
L (CY
Σ
H[Dr(aa))]
(6)
iEL
The first term in (6. called uncertainty cross entropy (UCE) [5], is defined by
UCE(A,Y) = P.--Di( |- log ((ul):)))
Σ
Σ
(ix(V(as)) - Vi (as+)),
(7)
RELL
FEL AETK]
where Y [yI]IENN. y, {0, is the one-hot encoded ground-truth class of the node and
V is the digamma function, in terms of the Gamma function by: (x) r(x)- Minimizing UCE
(a
known increase confidence in classifying observed data (training nodes in this context). The second term in (6) is based on the entropy of cach node-level Dirichlet distribution Dir(a:) that favors smooth distributions. For more details on GPN, please refer to Appendix
Our Contributions
This section provides series of theoretical analyses relating to the UCE loss term and the GPN model for detecting the OOD nodes, followed by a partial remedy to derived issues via two distance-based regularizations. Specifically, we prove in Theorem I that under certain conditions, UCE can be made arbitrarily small with the limiting case of UCE equal to zero in Corollary 3 Theorem 4 gives construction to make the UCE to be zero. As UCE does not involve the OOD nodes. Theorem [ and Corollary elucidate scenarios for possibly detecting the OOD nodes. Lastly, Theorem 8 presents a special situation where GPN fails detect the OOD nodes.
7
4.1 Theoretical analysis
The loss function plays pivotal role in learning effective representation functions and density estimations. In this context, we establish several theorems (Theorems [nd 4 to describe some demanding assumptions on fe and 96 that achieve the minimum UCE loss. We then describe limitation UCE in separating ID and OOD nodes in Theorem 6 and Corollary [ for PN, which means that we only consider the first two steps in GPN. The main conclusion of our analysis is that the UCE loss function alone is insufficient to learn a representation space that separates OOD from ID nodes. We take graph connectivity into account in Theorem [ to study some scenarios where GPN is ineffective for OOD detection. Although our theorems do not completely characterize graph learning, they provide some insights into the behavior of the network parameters in PN/GPN when minimizing the UCE loss.
Theorem 1.
If the underlying distribution feature vectors belonging to class k2 denoted by Xx, is disjoint to each other and both the MLP module (Jo) and the normalizing flow module (ha) can be arbitrarily complex, then Ve > 0 there exists configuration of f'o and 9o, such that UCE(A, Y) < <.
For the proofs, please refer Appendix B Here, we elaborate on the ideal configuration that satisfies the conclusion of Theorem [ We assume the MLP function fo is arbitrarily complex such that it maps x; E X's into a bounded ball in the representational space, i.e.,
{f((x:) E [N] and x; E X C ((z,,
where each ball (zz,, rk) centered point 2 and bounded in size with rk for positive value r. Furthermore, we choose the normalizing flow to be
go (z; k) = vol(B(ee.r))
if d(z, 22) < T otherwise,
(8)
where Vol(.) refers to the volume the ball. The conclusion in Theorem 1 states that for every e, there exists suitable upper bound of all the balls such that CCE(A, Y)

---

An implication of Theorem Dis that UCE is not sufficient to separate OOD from ID nodes. Example illustrates a scenario that OOD nodes can be close to ID nodes in the learned representation space even though they can be separated in the feature space based on OOD- unfortunately discarded. In other words, the learned representation space by GPN based on the UCE loss is not guaranteed to preserve the distance between OOD and ID nodes in its representation learning step.
features, which are
Example 2 (Lost Features). Suppose two ID classes in citation network contain bags of words for SVM and neural networks papers respectively. Additionally, the OOD nodes contain bags of words from reinforcement learning papers. Note that frequencies of keywords are used to discriminate different classes. Then the keywords, "actor critic" and "policy network" " are able to separate OOD nodes from ID nodes, but are irrelevant features for discrininating between the two ID classes. UCE, as a discriminatory loss, is only applied on ID nodes, and hence it is almost impossible to learn representations that respect the OOD-specific features such as "actor-critic" and "policy networks".
Limitations and discussions- The first assumption in Theorem reegarding the distinct class-specific distributions of feature vectors might not be realistic in practice since certain ID classes may not be clearly distinguishable due to noise in features or class labels. Nevertheless, our intuition suggests that if the UCE loss is inadequate for separating OOD from ID nodes in situations where they are separable, it is even more likely to falter in the more complex, non-separable cases. As for the second assumption in Theorem 1 it is true that arbitrary complexity of so and ge does not fully respect the inductive bias [24] of the network design, such as the MLP layers with ReLU for the feature encoder fx;; 9), our analysis remains insightful and informative about the structures these networks are likely to exhibit. For example, we may expect from Theorem [ that the representation of each class may favor an embedded space that compresses OOD-specific features, while density estimation Io tends to have higher peaks over smaller volumes as the model consolidates the representation space.
We note that in (7] Theorem 1] and (32 Theorem], the authors demonstrated that PN/GPN is able to achieve reasonable uncertainty estimation when the feature encoder is a ReLU network and PPR diffusion is removed to disregard network effects. Unfortunately, the analysis is based extreme node features, specifically as δ + DC,
(f x,; 0) k; Φ) + 0, and
O,
for any node i with high probability. Moreover, Theorem in the GPN paper 32 holds even when the supports of disjoint ID and OOD classes in the latent space overlap. In other words, this result does not prevent distant nodes from having similar representations. In summary, the analysis based on extreme node features may provide limited insights about the issues of GPN studied in this section. See Appendix for detailed discussions.
By taking + O, Theorem |
reduces to Corollary 3 where UCE is equal to O.
Corollary 3. In the ideal case, where the representation function fo maps the support of each class,
Nz. to a countable sel (with measure zero), Zg and there exists a normalizing flow that has infinite density on the point set for every class, one achieves UCE(A,Y) O.
Next, we aim for the construction of a specific case to make UCE equal to zero. As it is challenging to analyze the joint minimization optimally. For this purpose, we consider a simplified problem where the true density function is assumed to be known for given @ and hence it can be used replace the learning of the normalizing flow. As a result, the problem reduces to the learning of the representation network 0.
I and o, assume that the normalizing flow can be chosen
Theorem 4. Let Xx be the true distributions for class-k in the original feature space. Suppose the normalizing flow module 96 obtains the true analytic solution. If the true distributions {Xr} are disjoint, then the fg that minimizes the UCE loss projects the support of each class in the original space to a disjoint point set Zt, where Zg is defined by the projection of Xx to the representation space, i.e,, 2x = fo(.)).
Notice that the true analytical solution & in Theorem 4 is function of f, i.e., -= ((0). is possible to know an analytical form of @(8). For example, If the data points belonging to each class are sampled from known Gaussian distribution in the original feature space and the representation network is linear projection function, then the true density of the projected data points belonging to each class can be derived based on any configuration of the known Gaussian distribution in the original feature space.
5

---

Feature Space
forOOD
Latent Space
Near OOD
B(ak. 16.
Nt
(o
Figure 1: Illustration of the representation mapping in Theorem with the conditions to detect far OOD nodes (Theorem 6) and near OOD nodes (Corollary 7
Before discussing OOD detection, we start with the definition of OOD nodes. Definition 5. We define out-of-distribuue (OOD) nodes be the nodes that do not belong any of the K in-distribution (ID) classes. We denote all the ID distribution supports by X[K] - Nx.
In order to detect the OOD nodes, we need good representation, e.g., fo o fo( However, it possible that - - (Zx) X, which implies that any OOD node in the feature space is mapped to the same distribution of an ID class in the representation space. To this end, we require the preimage, f/ to be well-behaved in the sense that fo (2x) must be contained within bounded region near the support of the true distribution Xs. Explicitly, we require there exists constant 0 such that d(x, x) < 6, VX E fo (Zx) and Vx Xr for each k. The choice of 8 depends on additional information about the dataset. An excessively large causes overlap between classes, thus increasing the likelihood of improperly identifying the OOD nodes as ID, On the other hand, a relatively small 5 forces the model to overfit, which labels the non-training nodes as OOD.
R.
We characterize in Theorem 6 that under certain conditions, OOD can be detected correctly if they are far away from the ID distribution. One such condition is that the function fe is well-fit, meaning that it maps the support of X₂ inside B (z ri)) for every k in [K]. We denote a set of all well-fit functions by T. Please refer to Figure [ for a geometric illustration of these relevant quantities.
Theorem (Far OOD). Under the same assumptions in Theorem Aand two additional assumptions: (i) Xs is bounded and for any & E 1o (2) with z E Zx, there exists X E X2 such that d(xx, 8) < 6, if the true distribution of OOD) nodes does not overlap with the region User Up Uzyez, (So 1-11 (2k)). then minimizing UCE can learn representation projection of fo that detect all the 0OD points farther than 5 from Xx-
Corollary 7 (Near OOD). Following Theorem if E User Uk Uziez, ( follows the distribution of OOD nodes, then the classification of depends the choice of 0 T.
The main purpose of Theorem 6 is to show a desired behavior for OOD detection is induced by point-wise effects. In practice, suggest the careful construction of fø 's topology coupled with proper regularization terms to achieve the point-wise effect.
Lastly, consider the setting of GPN to use graph layer after the feature- evidence predictions.
Theorem 8. Under the following conditions: (1) The features of some class 0 and OOD nodes belong S: (2) The OOD nodes are only connected to class and themselves; (3) Other nodes belong to other regions i.e. x E X - S if & X, U NOoD: (4) Other nodes' features are non-degenerate in their associated region; and (5) the endowed graph neural network layer must produce evidence for each node between the highest and lowest feature evidence found among its neighbors. A graph with arbitrary homophily can achieve global minimum on UCE with the associated OOD nodes achieving arbitrurily large evidence, while simultaneously having perfect accuracy.
we provide a special situation where the GPN archi- tecture may fail to detect OOD nodes by predicting large evidence values for belonging to class addition, we show in Appendix B that if GPN has bad initial feature predictions, even ideal graph construction coupled with ideal graph neural network (with homophily degree 1.0) fails to
Limitations and Diseussions. Theorem g

---

prevent the OOD nodes from being misclassified as ID nodes, For homophily graphs with degrees less than 1.0, the majority of nodes for each class have similar evidence values after graph diffusion layers, except that the nodes between some pairs of classes may have different evidence values.
4.2 Distance-Based Regularization
As discussed in Section 4.1 the UCE loss function alone insufficient to learn a representation space that separates OOD from ID nodes using the GPN model. We propose heuristic remedy that enforces distance minimization on the graph. Ideally, we should design a distance formula that can preserve the distance relationship among all the feature vectors. However, distance preservation likely increases variation in the latent space as we cannot compress the classes' support in the representation space be arbitrarily small, while simultaneously preserving distances.
Instead, we consider distance minimization, as it helps prevent the model from discarding relevant features while decreasing variation between nodes in the representation space. Here give two formulations directly. The simpler, latent space,
term, is the distance regularization on the
(=(f((X):))= = (lfo(x.) - fxl
(9)
iJEE
The regularization encourages nearby points in the graph representation to remain nearby the latent space. In other words, this regularization (9) discourages the overlap (o( fo X(x)).
We also minimize the "distance" on the produced evidence through divergence- based regularization,
(a foat, 9) = Σ
divala, feat .x
a divula feat feo a
(10)
(U))E
where divai refers to the -ulbback-Leibler Leibler divergence and two symmetric terms are considered. This divergence-basee based formulation likely decreases the variation in evidence between neighboring nodes, because high variation in the latent space between neighboring nodes need not be mapped similar evidence.
In summary, augment the GPN mode with either one of the proposed regularization terms in (9) and (00), thus leading to the objective function as follows,
L UCE(A,Y) > Σ H(Dir((a)) + R(o(()):))
(11)
proposed regularizer
entropy regularizer
with two positive parameters Àι, A2. The first term is the standard UCE loss function. The second term regarded by GPN as an entropy regularizer. The last term, R, is chosen to be either Rp or R., decision implemented through hyperparameter tuning. We have included theoretical result in Appendix B that provides a rationale for the proposed distance regularizations.
Experiments
In this section, we conduct extensive experiments on two tasks of OOD detection and misclassification detection. We compare the proposed framework (TT) for uncertainty estimation of semi-supervised node classification using 8 datasets with comparison to baseline methods. The code is available at https//ghhabb.ommmoouuu///uppppp PorrrppppppPPstrrroooeetttttt
5.1 Experiment Setup
Datasets We use three citation networks (i.e. CoraML, CiteSeer, Pubmed) 4 two co-purchase
datasets [3I] (i.e. AmazonComputers, AmazonPhotos), two coauthor datasets B1 (i.e. CoauthorCS
and CoauthorPhysics) and large dataset OGBN Arxiv [16]. A detailed description of these datasets
in Appendix [E] We show the result of three citation datasets in the main paper and the remaining results in Appendix F.
7

---

Baselines We present the results for uncertainty estimation using five baseline methods, Among these, two evidence collection models, namely graph kernel density estimation (GKDE) 39 and label propagation (I.P) 32 assuming that OOD nodes are located far away from the training nodes, while easily misclassified nodes reside near the boundaries between classes. We compare to a modified GCN model, referred to as VGCN-
[21], Bayesian- model, called GKDE-GCN (39], and GPN [32] as baselines in our evaluation. We also introduce a Graph Neural Network called APPNP 12] as one baseline for the misclassification detection task and report the ROC score. Details of these baselines can be found in Appendix D
Metries To assess the classification performance of ID nodes, we rely the metric ID-ACC, which calculates the fraction of correct predictions among all predictions. As for evaluating uncertainty estimation, employ the metrics AUC-ROC and AUC-PR as evaluation measures. The rankings are based on the scores of epistemic or aleatoric uncertainty. OOD detection is treated as a binary classification task, where the positive class corresponds to OOD nodes and the negative class pertains to ID nodes. Please refer to (2) for the calculation of aleatoric uncertainty and epistemic uncertainty. For the Dirichlet-based models, the epistemic uncertainty has similar practical interpretation to vacuity in the belief theory, assessed using AUC scores. On the other hand, in VGCN-Energy. the u, opis energy. The misclassification detection task is also a binary classification problem, where the positive cases correspond to wrongly classified nodes and the negative cases represent correctly classified nodes. The calculation of uncertainty for misclassification detection is performed the same manner as OOD) detection except that u, = max; a.. Prior studies 33 39 has indicated that aleatoric uncertainty is generally more effective for identifying misclassifications, whereas epistemic uncertainty is more appropriate for detecting out-of-distribun instances.
calculation of epistemic uncertainty is based on the energy value and is represented as
Model Setup For all the baseline methods, we maintain consistency by employing the same set of model hyperparameters as provided by GPN. Specifically for some model hyperparameters such as latent dimension and weight decay, we adopt the same settings as GPN. Inspired by (26). we explore multiple choices of activation functions in the representation networks. In addition to the default ReLU used in GPN, experiment with Sigmoid and GELU activation functions. Through empirical evaluation, we discover that the choice of activation function significantly impacts the performance of certain datasets, which is demonstrated in Appendix E.4. Besides, hyperparameters that we tune include entropy regularization weight, distance- based regularization format (whether R or R.)., and weighting parameters (A1. A2), which are optimized based on the validation cross- cross-entropy for each specific dataset. For a comprehensive overview of the hyperparameter configuration and ablation study, please refer to Appendix D
5.2 Results
OOD Detection OOD detection aims to detect whether an input example is OOD given the predicted uncertainty estimation. For the semi-supervised node classification, we adopt the Left-Out- Classes setting where we assume several categories as OOD (details can be found in Appendix D) Different from the independent input setting, we retain the OOD nodes in the graph but exclude their labels from the training and validation sets. This implies that the loss function does not involve OOD labels, but the model has encountered the OOD node features during the training phase. Similarly to [2], we also remove the last graph propagation layer for comparison as "w/o network" where the final result only depends on the node features and no graph structure involved. This configuration, referred to as the "w/o network" setting, results in a final output that solely relies on the node fcatures, with no involvement of the graph structure.
as considered in 7 39
The results on CoraML, Citeseer, and PubMed are presented in Table and the results on the other 5 datasets are shown Table Appendix Our model achieves the best ID accuracy for four datasets and demonstrates comparable performance to GPN for the remaining four datasets Furthermore, we observe an improvement the ROC (Receiver Operating Characteristic) rankings based on predicted epistemic uncertainty with propagation, ranging from +1% to +8% compared to GPN. Consistent with previous studies 32. our results demonstrate that prediction models incorporating evidence propagation consistently outperform those without propagation across all datasets. This observation highlights the significant impact of graph structure on uncertainty estimation. Moreover, when comparing alcatoric uncertainty and epistemic uncertainty ranking scores, we find that epistemic
8

---

uncertainty outperforms aleatoric uncertainty in the OOD detection task. This finding aligns with literature 39 32 and emphasizes the superiority of epistemic uncertainty for OOD detection.
Table 1: AUROC and AUPR for the OOD Detection
AUROC
Dara
Model
ID-ACC
Alca w/
Epi w/
Epi w/o
Alca w/
Epi w/
Epi w/o
86.40
83.78
80. 86
n...
74.80
71.15
n.a.
GKDE
83.02
74.46
71.86
66. 19
64.05
VGCN-Energy
89.66
81.70
83.15
n.a.
75.67
78.44
n.a.
CoraML
GKDE-GCN
n.a.
75.88
n.a.
GPN
88.51
83.25
86. 28
80.95
75.79
79.97
72.81
Ours
90.06
83.94
87.20
76.12
76.26
80.36
63.32
LP
57.34
67.54
48.12
48.59
GKDE
49.62
63.75
63.91
n.a.
56.74
56.79
R.S..
VGCN Energy
76.08
n.S.
n...
Ciseseer
GKDE-GCN
70.76
73.34
76.19
54.25
59.07
GPN
69.79
72.46
70.74
66.65
$5.14
50.52
44,93
Ours
72.51
75.22
78.98
73.21
62.30
58.63
52.73
LP
89.18
80.32
79.64
n.a.
71.01
72.98
R.a.
GKDE
n.a.
n.a.
VGCN-Energy Energy
94.77
72:58
72.63
60.54
60.63
n.a.
PubMed
GKDE-GCN
94.66
73.53
74.47
n.3.
61.36
61.96
n.a.
GPN
94.08
71.84
73.91
71.2
57.92
67.19
59.72
Ques
93.84
75.23
81.76
77.79
60.75
78.16
69.19
Alca: Alcatoric, Epi.: Epistemic, w/: propagation, without propagation
given OOD detection based on different uncertainty metrics, where (Alea w/| the alcatoric score with propagation layer. [łipi w//l is the epistemic score with propugation layer [Eii w/a] the epistemic without progagation.
AUROC and AUPR for OOD Detection: ID-ACC means the accuracy on ID nodes. AUROC and AUPR
either
applicable.
Misclassification Detection In addition to OOD detection, we conduct misclassification detection on the clean graph for evaluating the predictive uncertainty estimation. presents the results for three datasets, while Table 7 in Appendix Djss for the other 5 datasets. We observe significant improvement ranging from + 12% to +50% in our model's AUC-PR scores. While it is true that our method performs worse than the best of the baselines in terms of AUROC, the differences are within approximately 3% for six of the eight datasets.: Amazon Computers, Amazon Photos, Coauthor CS, Coauthor Physics, and ODBG Arxiv, and PubMed. Despite having a lower AUROC compared to the best of the baselines, our method exhibits higher AUPR. This suggests that our method may excel at identifying true positives among the top-ranked nodes when compared to GPN, while the best baselines may be more effective at distinguishing between true positives and negatives among the dower-ranked nodes.
Table 2: AUROC and AUPR for the Misclassification Detection
Data
Model
Alea w/
Epi w/
Alca w/
Epi w/
APPNP
83.64
n.a
48.39
11.0
Energy
CoraML
GKDE GCN
80.80
76.83
49.61
45.87
Ours
75.8
69.85
89.95
88.20
APPNP
73.55
n.a.
$1.70
n.a.
VGCN-Energy
74.64
48.30
CiteSeer
GKDE GCN
75.45
73,83
54.78
$3.57
74.16
Ours
69.15
68.62
72.67
72.36
APPNP
80.98
T.S.
37.79
n.a.
VGCN-Energy
81.16
38.24
PubMed
GKDE-GCN
80.95
73.99
39.64
33.19
75.38
35.11
Ours
80.13
72.87
95.41
92.79
Alca: Alcatoric, Epi.: Epistemic, w/: with propagation, w/o: without propagation
scores are given misclassificatin detection on uncortainty metrics, where [Alea w/] is the aleatoric score with propagation layer, [Epi w/] the epistemic score with propagation layer and [Epi w/o) the opistemic score without propagation. n.a. means either model metric not applicable
AUROC misclussification detection: AUROC
5.3
Ablation Study
Our proposed model differs from the GPN model in three main aspects. First, we use validation cross entropy (CE) instead of hold-out datasets to select hyperparameters. Second, we consider the

---

activation function for the MLP layers as one of the hyperparameters for selection. We expect feature value rescaling through non-linear activation of feature values affect the density predictions. Third, we incorporate one of the proposed distance-based regularization terms to the loss function used in GPN.We We conduct an ablation study to demonstrate the contribution of these three components. The results for CiteSeer and PubMed are shown in Table []
and the remaining datasets are included in Appendix [ Hyperparameter tuning using validation cross-entropy improves GPN's performance, especially in cases where the choice of activation function has a significant impact specific datasets. Additionally, we consistently observe performance enhancements from the distance- regularization in both datasets, demonstrating the effectiveness of the proposed distance awareness regularization term.
Table 3: Ablation Study with OOD Detection task
Data
Model
IDACCC
Alea w/
AUROC
Epi
Epi wlo
Egii
AUPR
Eppi w/o
GPN
69.79
72:46
70.74
66.65
55.14
50.52
44.93
GPN CE
70.9%
74.20
73.75
68.41
58.12
53.55
46.60
Citeseer
GPN-CE-ACT
71.96
77.97
72.28
60.41
56.04
50.73
GPN CED-CE-G
72.51
75.22
78.98
73.21
62.30
58.63
52.73
GPN
94.08
71.84
73.91
71.2
57.93
67.19
59.72
PubMed
GPN-CH
93.84
74.19
78.32
74.50
59.85
74.11
64.55
GPN CE-ACT ACT
93.84
74.19
78.32
74.50
59.85
74.11
64.55
GPN-CE-GD
93.84
75.23
81.76
77.79
60.75
78.16
69.19
Alea: Aleatoric, Fpi.: Egistemic, w/: with propagation
GPN refers to the original GPN paper with its default hyperparameeeers and ReLU as the middle activation function, GPN-CE is the validation cross entropy; CE original
original model tuned Dirichlet entrupy regularization weight
GPN model with re-tuned entropy regularization weight and activation function based on cross-entropy; CPN.CF-GD((Oum adds the distance-based rogularization term while tuning the two weights and activation fanction.
Limitations
Our theoretical analyses mainly study the limitations of the UCE loss function when separating OOD from ID nodes in the learned representation space. If we include the entropy-based regularization term in Equation 66) with a sufficiently large weight X, some of our theoretical findings may not remain applicable. However, the entropy-based regularization term is designed to favor smooth Dirichlet distributions but not to preserve the distance between OOD and ID nodes. We conjecture that the resulting loss function is still insufficient to learn a representation space that separates OOD from ID nodes, even though they are separable in the original feature space. In addition, our proposed regularization terms in Section 4.2 are more effective for homophily graphs than heterophily graphs, as neighhoring nodes are less likely to belong to the same class heterophily graph than those in homophily graph.
7 Conclusion
This paper contributed a better understanding of uncertainty quantification for node classification. We investigated the limitations of the widely used UCE loss function. Motivated by the theoretical analysis, we proposed a distance-based regularization that helps learn representation network that more effective for the uncertainty quantification task. Experimentallyy we demonstrated our approach outperforms the state-of-the- in two specific applications of uncertainty quantification for node classification: OOD detection and misclassification detection.
8
Acknowledgments
This work supported by the National Science Foundation (NSF) under Grant No #2220574, #2107449, #1 #1846690, and #1750911. The work of Feng Chen is also supported by the Intelligence Advanced Research Projects Activity (IARPA) via Department of Interior/Interior Business Center (DOI/IBC) contract number 140D0423C0026. The US Govermment is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright annotation thereon. Disclaimer: The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of IARPA DOI/IBC or the U.S. Government.
10

---

References
[1] M. Abdar, F. Pourpanah. S. Hussain, D. Rezazadegan, L. Liu, M. Chavamzadeh, P. Fieguth, X. Cao. A. Khosravi, U. R. Acharya, et A review of uncertainty quantification in deep learning: Techniques. applications and challenges. Information Fusion, 76:243-297, 2021.
[2] E. Begoli, T. Bhattacharya, and D. Kusnezov. The need for uncertainty quantification in machine-assisted medical decision making. Nature Machine Intelligence, 1(1):20 23, 2019.
[3] M. Bilos, B. Charpentier, and S, Günnemann, Uncertainty on asynchromous time event prediction. Advances in Neural Information Processing Systems, 32, 2019.
[4] A. Bojchevski and S. Günneeann. Deep gaussian embedding of graphs: Unsupervised inductive learning via ranking. arXiv preprint arXiv:1707.03338 03815, 2017.
[5] B. Charpentier, M. Bilos, and S. Günnemann, Uncertainty on asynchronous time event prediction. Advances in neural information processing systems, 32: 12841- 2019.
[6] B. Charpentier, O. Borchert, D. Zügner, S. Geisler, and Günnemann. Natural posterior network: Deep bayesian predictive uncertainty for exponential family distributions. In International Conference on Learning Representations, 2022.
[7] B. Charpentier, D. Zügner, and S. Günnemann. Posterior network: Uncertainty estimation without ood samples via density- pseudo-counts. Advances in Neural Information Processing Systems, 1367, 2020.
[8] P. de Haan, T. S. Cohen, and M. Welling. Natural graph networks, Advances neural information processing systems, 33:3636-366 3646, 2020.
[9] A. Der Kiureghian and O. Ditlevsen. Alcatory or epistemic? does it matter? Structural safety, 31(2):105- 112, 2009.
[10] A. Filos, P. Tigkas, R. McAllister, N. Rhinehart, S. Levine, and Y. Gal. Can autonomous vehicles identify, recover from, and adapt to distribution shifts? In International Conference Machine Learning, pages 3 3145-3153. PMLR, 2020.
[11] Y. Gal and Z. Ghahramani. Dropout as bayesian approximation: Representing model uncertainty in deep learning. international conference on machine learning, pages 1050-1059, PMLR, 2016.
[12] Gasteiger, A. Bojchevski, and S. Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. arXiv preprint
2018.
[13] J. Gasteiger, A. Bojchevski, and S. Günnemann. Combining neural networks with personalized pagerank for classification on graphs. In International Conference Learning Representations, 2019.
[14] C. Guo, G. Pleiss, Y. Sun, and K. Q Weinberger. On calibration of modern neural networks. In International conference machine learning, pages 1130.. PMLR, 2017.
[15] 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. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 41 41-50, 2019.
[16] Hu, M. Fey, M. Zitnik, Y. Dong, H. Ren, Liu, M. Catasta, and Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 33:221 18- 22133, 2020.
[17] A. Kendall and Y. Gal. What uncertainties do we need in bayesian deep learning for computer vision? Advances in neural information processing systems, 30, 2017.
[18] T. N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations. 2017.
[19] B. Lakshminarayanan, A. Pritzel, and Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. Advances in neural information processing systems, 30, 2017.
[20] J. Liu, Z. Lin, S. Padhy, D. Tran, T. Bedrax Weiss, and B. Lakshminarayanan. Simple and principled uncertainty estimation with deterministic deep learning via distance awareness. Advances in Neural Information Processing Systems, 1177498-71222 2020.

---

[21] W. Liu, X. Wang, J. Owens, and Y. Li. Energy-based out-of-distribution detection. Advances in neural information processing systems, 33:21464-21475, 2020.
[22] A. Malinin and M. Gales. Predictive uncertainty estimation via prior networks. Advonces in neural information processing systems, 31, 2018.
[23] L. H. Mervin, S. Johansson, E. Semenova, K. A. Giblin, and O. Engkvist. Uncertainty quantification in drug design. Drug discovery today, 26(2):774-48) 2021.
[24] T. M. Mitchell. The need for biases in learning generalizations. 1980.
[25] E. Nalismick, A. Matsukawa, Y. W. Teh, and B. Lakshminarayanan. Detecting out-of-distribution inputs to deep generative models using typicality. arXiv preprint arXiv: 110.v:9906.02994 2019.
[26] P. Ramachandran, B. Zoph, and Q. V. Lc. Scarching for activation functions. arXiv: 1oX.vv/710.059411 2017.
arXiv preprint
[27] D. Rezende and S. Mohamed. Variational inference with normalizing flows. In International conference machine learning, pages 1530-1538. PMLR, 2015.
[28] A. G. Roy, J. Ren, S. Azizi, A. Loh, V. Natarajan, B. Mustafa, N. Pawlowski, J. Freyberg. Y. Liu, Z. Beaver, et al. Does your dermatology classifier know what it doesn't know? detecting the long-tail of unseen conditions. Medical Image Analysis, 15:102274, 2022.
[29] M. Sensoy, L. Kaplan, and M. Kandemir. Evidential deep learning to quantify classification uncertainty. Advances neural information processing systems, 31, 2018.
[30] S. Shafaci, S. Kugele, M. H. Osman, and A. Knoll. Uncertainty in machine learning: A safety perspective autonomous driving. In Computer Safety, Reliahility, and Security: SAFECOMP 2018 Workshops, ASSURE, DECSoS, SASSUR, STRIVE, and WAISE, Västerãs, Sweden, September 18, 2018, Proceedings 37, pages 458-464. Springer, 2018.
[31] O. Shehur, M. Mumme, A. Bojchevski, and S. Günnemann, Pitfalls graph neural network evaluation. arXiv preprint 1811vv:811.05860 2018.
[32] M. Stadler, B. Charpentier, S. Geisler, Zügner, and S. Günnemann. Graph posterior network: Bayesian predictive uncertainty for node classification. Advances in Neural Information Processing Systems, 34: 14:18033-18048 2021.
[33] D. Ulmer, C. Hardmeier, and J. Frellsen. Prior and posterior networks: A survey on evidential deep learning methods for uncertainty estimation. Transactions on Machine Learning Research, 2023.
[34] J. Van Amersfoort, L. Smith, Y. W. Teh, and Y. Gal. Uncertainty estimation using a single deep deterministic neural network. In International conference on machine learning, pages 9690-9700, PMLR, 2020.
[35] P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
[36] X. Wang, H. Liu, C. Shi, and C. Yang. Be confident! towards trustworthy graph neural networks via
confidence calibration. Advances in Neural Information Processing Systems, 34:23768-23779, 2021.
[37] Q. Wu, Y. Chen, C. Yang, and J. Yan. Energy-based out-of-distribution detection for graph neural networks. arXiv preprint 200202230..02914, 2023.
[38] J. Yu, D. Wang, and M. Zheng. Uncertainty quantification: Can we trust artificial intelligence in drug
discovery? Iscience, page 104814, 2022.
[39] X. Zhao, F. Chen, S. Hu, and J. Cho. Uncertainty aware semi semi-supervised learning on graph data. Advances in Neural Information Processing Systems, 33:12827- 111222222226,2,.1111111111118881 2020.
12

---

The supplementary materials are organized as follows. Appendix A provides the background knowledge on the Dirichlet distribution. In Appendix B we review the architecture of the graph posterior network (GPN) [32] together with our discussion on oversight [32 Theorem 1J. Appendix C details and corollarics discussed in the main paper. We provide detailed descriptions of baseline models, datasets, and hyperparameter tuning for the experiments in Appendix D. Lastly, Appendix E includes more experimental results that unable to fit into the paper.
proofs of theorems
A Dirichlet Distribution
non-degenerate Dirichlet distribution, denoted by Dir(ax), , is parameterized by the concentration parameters with cx > 1 for & E [K] More specifically, the Dirichlet distribution with parameters on1 ak has a probability density function (pdf) given by
[an,... _xx]" "
pdf(p: a) B(x)
1I Pk
(12)
where {p=) belongs to the standard probability simplex, thus Et= ph and pa [0, 1], E [K], and the normalizing constant B(a)) expressed terms of the Gamma function I'()) i.e.
IL I(ax) B(a)= I (Exaa))
(13)
Under the semi-supervised learning setting, set of labels available, denoted by C V. For á 1, the class lahel y/ E {1,.... K} can be converted into a one-hot vector y, with Yik = 1 the sample helongs to the k-th class and yij 0 for o k. By arranging a and y: into matrices A [oc]ken and Y == [ysket, the UCE
loss function is defined
UCE(A,Y)
Σ
Σ
Mek (Vss) (ax)),
(14)
FELL KE[K]
where 0:00 = Exm k Oik and V is the digamma function given by
(x() T(x)
T (I)
B Detailed Framework of GPN
this section, we review the architecture GPN, followed by two examples that reveal a limitation Theorem I in the GPN paper 32
Multi-layer Perceptron (MLP). Instead of deep convolution layers used in many neural networks designed for image classification task 77. GPN utilizes two simple perceptron layers with ReLU activation function as the encoding network, which maps high dimensional data to latent space with much smaller dimension, avoiding
the curse of dimensionality for the density estimation on (mapped) latent representation 25). As each node
independent of the others this step, the encoding map only considers the node features without any graph structure involved. Mathematically, the mapping can be expressed by
2; f(x:; 0) W2o(Wier æ;
1'b.) + 17b2,
where (Wi, W2, bi, b.) denotes set of learning parameters. For simplicity we use the notation 2: = fo(x:).
Normalizing Flow. Normalizing flow is used to estimate the density P(z [k; Φ) for le E [K] and learning
parameters Φ as an invertible transformation q(:; k) of a base distribution, c.g. Normal distribution, which denotes the distribution of class & in the latent space. The default flow in GPN is the radial flow (27) given by
3(z Zu)
g(2; k)
7 12 zo
0g
(-:k)
P( le 3) p=(g (z.; k))
Oz
where Zo is reference point and p=(-) ~ (O. 1). After estimating the density of node belonging to specific class k, the pseudo evidence counts scaled to the probability, i.c., 8tt (2;jk; Φ), GPN sets
s g (z:)2 Nv P(zikk; Φ),
where N; is the number of training nodes that belong the class k.
13

---

Personalized Page Rank. GPN applies personalized page rank (PPR) module to diffuse the evidence among neighboring nodes. It is motivated by the work of Approximate Personalized Propagation of Neural Predictions (APPNP) [12 that is designed to decouple encoding network and propagate with a personalized page rank (PPR) module (only based on edge information). In particular, PPR provides personalized influence score matrix for each node that considers L hop of neighbors without involving any new parameters learn and L is hyperparameter:
prediction (only based on node features) with any
g(++1) (1 - - A) + x3(())
where 7 hyper- parameter relating to the teleport probability, Å denotes the symmetrically normalized graph adjacency matrix with added self-loops (i.c., A == D D- AD 1/2 with the standard adjacency matrix A), and / denotes the layer index with ( obtained after the normalizing flow. The output of PPR a set of concentration parameters, denoted by a h, ).
Collectively for MLP, normalizing flow, and PPR, the network GPN can be expressed by
as + (Fo
(15)
for each node i, where the addition of guarantees that the concentration parameter strictly positive. In addition, an entropy regularization was considered by GPN defined by,
H(Dir(a.)) = log B(o.) + (aw ())((
Σ (a.a [(am
1)
(16)
where 04:0
Ek=1 Olik.
Next, we provide two examples describe oversight [6] Theorem 1J and B2 Theorem 1] in sense that both theorems assume an impossibility. Particularly the assumption is that a two-layer ReLU network can be represented by set of affine mappings, cach being full rank, from finite set of regions to the latent space. However, we construct Example Paneegaan and Example show this assumption is impossible.
Example 9, We start with simple case where a two-layer ReLU network with input, hidden layer, and output of a scalar ( (-ddimnnsional) is considered for an easier interpretation of the results. One simple example of two-layer ReI. network is expressed by
fa(x) = 1. L-auvl 0) O.
(17)
Following 15). we split the latent space into two affine regions, i.e.
x if 20)
= 0
if (-x,00
(18)
labeled by ((0)
o0) and Q() = (-oo, 0J. We see the associated ( = and (11) = 0 in the affine 17 that certainly do not have independent rowx, as required by 16 Theorem 1].
representation
Example I0 extends the ID case in Example innto higher d-dimension, showing that there is always least one affine region that produces single value, i.c. fe(Q("") ) = {v} when mapped into ReLU network fe. Example 10. We consider the ReLU network.
fo(x) = CareLu
(19)
where B, C E paxd are matrices of full rank. Denote xj be the solution to the equation,
e,-- Bx,
(20)
where ej the jth Euclidean standard basis. As B is assumed to be full rank, there is the unique solution of the corresponding Xz.
Notice that the polytope.
Σ ajxa 03 2
2
(21)
has non-zero measure in RR Note the ReLU network constant by construction, as dRav( (e;) = 0. In other words, we have for x E S that
z= = fo(x) = Caraw ( (x) = C'O = 0.
(22)
As in the previous example, the existence of S means that there exists some v() Da,a which contradicts the assumption that all Vs have independent rows. Under this setting, the density does not approach zero, which is the conclusion of Theorem in (32).
14

---

C Proofs
In this section. we provide the proof of all the theorems and corollaries. Note that until Theorem 8 We ignore the graph component fi and focus solely the representational layer fa and normalizing flow layer ga.
As fo is arbitrary by assumption, we choose it in such a way that it maps a point in 2 point inside the ball centered at n₁ with radius Tk, denoted by BZz,, Tk).
Proof of Theorem and Corollary 3
fo 2x Zx B(z,.Tk):
(23)
where Ze E Z with minimal distance R. between any two of them, i.e., d(zx, km) > R. Vk, m [K], and we define r > Tk, Vk E [K]. We then choose the normalizing flow to be,
VoI(B((L if E B(ZE,T)). 0, otherwise.
go k:) =1 1 No.
(24)
We add the value of in the normalizing flow to produce valid evidence measures. We also assume that Na p(ta) > O, where μ the Lebesgue measure function.
The global minimum of UCE occurs when UCE is cqual for every class. Recall that
Σ UCE ())
Σ
Σ
gm
(((x(z))
dp.
(25)
k K
RE[A]
En
mE[K]
Using
we consider upper bound of the right-hand side by integrating over the larger region, that is,
(
Σ kE
Σ
sm((e)
((x
du,
(26)
B(Heirr)
mej
Σ
Vol(B(Z),
(v
KK+
NR Vol(B(ze, rx))
11
No Vol r2))
(27)
kE(K]
According the recurrence relation of the digamma function: v0 + =xxxx) + 1/2, we readily derive that,
N₂ K m + Vol(B(ze, ra)) Σ
Σ (
Σ
Vol(B(ze.ra))
(28)
KE[K]
ME[A]
Taking the limit of the right-hand side yields
N2 Vol(B(ze, rx))
lim
Vol(B(zi,
K m +
(29)
kE[R]
N₂ Vol(B(za, r2))
lim Vol(B(zi, rk))
lim
K m
(30)
F% +0
kc|K]
is straightforward for the following two limits to hold,
lim Vol(B(ze, rx)) =0 O,
(31)
The
N2 K m + Vol(Bi2z, rx))
lim
= 0,
(32)
thus leading to
lim P-10
Bol(B(zz,Ta)) rk)) Σ
K m + Vol( rx))
N
= 0.
(33)
RE[M]
On the other hand, as V (/ x Ie (2)) (2)) 2 0. we have
05 Σ
Σ (m) m
(or(
Σ UCE (CE()(Z))))) Y), KE
(34)
RE [4]
which implies that UCE + O. For
UCE is equal to zero, which leads Corollary 3
L
15

---

We denote the parameters of da that represent the true analytic solution & = x0)). Note that this is function with respect the choice of 0, that is, the true distribution is dependent the representational mapping. this proof, we focus on finding value of s.t.,
Proef of Theorem 4
i arg min (C .), Y) arg min UCE(((0, o())),
(35)
0
As the true distribution is dependent the representational mapping. we should consider joint minimization problem with respect both the representation map and density distribution.
We will separate the proof into Z3 mapped by fo from X3 has non-zero measure, then the global minimizer UCE not he achieved. We then prove Case 2, under the assumption that a true analytical solution may achieve density evidence at a point, by showing that we may achieve the global minimizer on point set.
Specifically, prove Case 1 contradiction, showing that if the set
Case 1:
Non-Zero Measure. Suppose the true distribution this set is non-degenerate distribution. As the natural definitions of probability distribution -= du, the UCE loss be expressed by
Σ UCE (s((z), KE|R]
Σ KETRI Zu
E
(
|E 9m((2) mE[R]
)
(e (z))
du(z)).
(36)
In order for the measure of Zx have density of there exists subset of Z& with non-zero measure 8 > O, denoted z Using similar techniques as the proof of Theorem in reverse, we obtain.
Σ UCEE((ZZ).
Σ KE[K]
( (K N&c) V01 + N&e)) du,
KE[K]
2n
then for some & [K] there exists some Z
UCE (o(Zz),))
(V + Nac) - W1 + N2c)) du,
KE[K]
2%
= = (V (K + Nkē) - (1 + N₂c)).
As V is strictly increasing, then d2 1 (K + NAc) - 41 Nuc) 0, which implies that
Σ UCE (2(22)))
Σ 62 0.
REJA]
KE[K]
Therefore, we prove that if fo maps measurable set, the UCE loss is necessarily non-zero.
Case 2: Zero Measure Sets. Corollary 3 shows that the zero UCE is achicvable. Case fails, then we can conclude that only on disjoint set Zg with measure 0 for each is permissible achieve UCE be The exact choice of this set depends on the precise definitions of the probability distributions on point set and their ability to achieve infinite densities. Here we constrain these possibilities by requiring the range of fo to have non zero measure to be point set if having measure
Iy E Xr see that for any fo where E I we have that x is necessarily not mapped to n5 E Z (if it were mapped in Z then the preimage would contain it and thus we would have d(x, xx) < 6, which is contradiction with our selection of æ). Recall that the density for any point mapped
Proof of Theorem Ø Pick x E X' s.l. d(x, xx.)
infinite. That the density of the associated points mapped to the point set necessarily infinite and the density points mapped elsewhere is necessarily smaller, namely 0, with the associated evidence 1. Our selected x then has no evidence in favor belonging to a class while any point X E Xx must have infinite evidence by our choice of well-fit 0.
Prouf of Corollary
Notice that can choose two types of such 0.
Case
Let for class chosen such that,
Zz if Xt.
f(x)
(37)
10 otherwise.
"We choose that the cardinality of the sero-measure set (a(e to be finite (rather than countably infinite) as we do not want to detail precise topological arguments (like compactness and boundedness) about the pointsets and their respective preimages.
16

---

Case 2
Zu. if d(xx, x) < for any & Ah.
[())
(38)
otherwise.
If E 22 is mapped zą then is endowed with infinite density, moreover, it is believed be ID node belonging to class k. Thus, the nearby OOD being detected these UCE minimizers is determined by arbitrary choice.
Proof of Theorem 8 First note that the ID nodes are mapped to have infinite evidence achieved at the points in the latent space Zz. As the representations of the OOD nodes are in 2x they also endowed with infinite evidence. That is graph layers can only help separate nodes by pulling them towards the center of their own classes w.r.t. to representation space this is only helpful their representations are separate to begin with.
Lastly, we give a toy example showing heuristically that the proposed regularization yields a better separation of the OOD nodes from IDs, compared to the original GPN model without the restance-based regularization.
Example 11. Consider two ID classes (Class and Class 2) and OOD class with the following construction:
All nodes belonging to Class have feature values sampled from x ()) = [1, 0,
2. All nodes belonging to Class 2 have feature values sampled from x = [-1,0,0]
3. All nodes belonging to the OOD class 2 have feature values sampled from x ( [0, 1, w).
sample u from the uniform distribution U(- independently for each sample in each class.
5. All nodes are connected every node within their own class, leading to graph of homophily I.
6. Suppose the density function is true density distribution
7. Denote the PPR layer by that uses the right normalized adjacency matrix AD symmetrically normalized 1/2 AD-1/2 used in APPNP.
rather than
W11
W12
Suppose fe is a linear function (i.e. no activation function) explicitly,
Wz1
W22
Wai
W32
Then GPN with our regularization can learn an embedding that makes it possible to separate classes 2, and 0OD nodes. Without regularization, OOD nodes lie between ID classes the latent space.
Proof. A simple calculation for the project leads to
for class nodes for class nodes [W21 + WW... W12 + eWsi] for OOD nodes.
Wi1, W12]
= [XW],
[ Ww,: W12]
(39)
Clearly, the values of Ws and W32 would be smaller with the distance mininization term applied than without, is selected randomly. Moreover neither Ws1 nor W32 affects the model's ability to separate the two classes as desired. We explicitly calculate both UCE and the distance-based regularization in the objective function, while ignoring the Dirichlet regularization, thus leading to the following objective function,
L(Z, a, Y; UCE((((s Y) R(Z:9).
(40)
First, we explicitly work out the distance- regularization term
R(Z:))=
Σ ||z 2
(RJ)EE
Σ
I[[,,, Wiz] W1. W12]
Σ (K,))82
[[[- WWz] - [-W1,,, -Wi2]l
(
Σ
WWs WaI, Wea ( (We o We2 + , (.5
(NJ)EEnoo
Σ
- -06) Wszl
[(000)
17

---

which is minimized when W31, Wss go zero.
Next, we consider the UCE loss portion. See that as estimate the true density using we will have no overlap
W11
W12
between the two distributions 21, Zz. We are left with W
W21
W22
0
0
Wi1, W1a for class nodes
Z - [XW]==
| W11, W12 for class 2 nodes
(41)
[W21, W2a] for OOD nodes,
W is to remain full rank this will necessarily require either W21 or W22 to be non-zero. Thus OOD nodes will be mapped as see in [4] to some distinct values which can be separated after the application of APPNP as expect APPNP only average the values within each class.
D
Additional Experimental Details
D.1 Descriptions of Baselines
Based the high homophily property most graphs (neighboring nodes tend to share the same class label), GKDE derives the evidence with the help of the node-level distances (shortest path the graph) with training nodes belonging to the same class.
Graph-based Kernel Dirichlet distribution Estimation (GKDE)
39
Label Propagation (LP) 33 of labeled nodes in neighborhoods rather than distance. An initial condition per class is defined and then Personalized Page Rank is used as the diffusion.
Following the idea of GKDE, LP collects the evidence by relying on the density
VGCN-Enery 21:
It GCN- based model with energy node to single, non- non-ooonnneeeee probabilistic scalar called the energy. The energy score can be calculated as follows
the uncertainty estimation which maps cach
energy
-T log
exp
where is the predicted logits of neural network and lemperature parameter T =
GKDE-GCN [3 GKDE-GCN utilizes GCN network estimate the multisource uncertainty by Dirichlet distribution and then sample probability as well the class prediction. The evidence derived from the aforemen- tioned GKDE as a teacher of concentration parameters of Dirichlet Distribution, and another deterministic GCN predicting the probability is used as teacher for sampled probability. The overall loss is composed of the KL divergence between these two teachers with the corresponding distribution and Bayes risk with respect to the squared loss of sampled class prediction.
Given that message passing neural network suffers from the over-smoothing problem that limits the depth of neural network, APPNP proposed to decouple prediction and propagation where the prediction depends on the node features and propagation depends on interactions between nodes through edges. APPNP first uses any kind of neural network to embed the input space and diffuses information with personalized page rank. For large graphs, they power iteration approximate topic-sensitive page rank.
APPNP [2]
GPN 32 GPN applies normalizing flow estimate the density of each class in the latent space embedded with encoding network and then propagates the scaled density the evidence.
D.2
Description Datasets
We use three citation networks, labelled by CoraML, CiteSeer, Pubmed 4. two co-purchase Amazon datasets
[II, labeled by Computers and Photos, two coauthor datasets [3I]. labeled by CoauthorCS and Physics, and large dataset OGBN Arxiv [16]. We the same train/val/test split of 5/15/80
B2
The details of the graphs
and setups for the OOD detection are provided Table 4
Table 4: Dataset Description
CoraML
CiteSeer
PubMed
Computers
Photos
Coauthor CS
Conuthor Physies
OGBN-ArRiv
inodes
2,995
4,230
19.717
13,752
7,650
18,333
34,493
169,343
Hodges
88.648
163,788
495,924
2,315,598
#fcatures
2879
602
500
767
745
6,805
8.415
128
Aclasses
5
40
# loft-out-classes
3
2
18

---

D.3
tuning
follow the same setting with 32 In detail, we use the Adam optimizer with a learning rate 0.01. VGCN-Fnergy, we use a temperature of 7 = 1.0. We carefully tune three hyperparameters: the distance-based regularization weight, Dirichlet entropy weight, and activation functions. We select the hest parameters for each dataset separately that returns the highest validation cross-entropy. The detailed hyperparameters configuration as Table
Table 5: Hyperparameter configurations of proposed model
Dirihhet Entropy Reg. Weight
Graph Distance Reg. Weight
Activation Function
CoraMI.
0
10
GELJ
CiteSeer
10
10
9.5
LogSigmoid
PubMed
10
RELU
Computers
10-5
10-4
Photos
RELU
Coauthor CS
0
10
RELU
Coauthor Physics
10m4
10
LogSigmoid
OGBN-Arxiv
10-3
RELU
We also consider the following activation functions in the encoding network with element-wise operations,
TRELU (ar) max(0, x),
LogSigmoid (Ir) = log ((1 exp(-x))
(GeLU (z) = =CDFx(2)
-1,x <-
O'Hudtiah (2x) =
x, -
1,8>1
ReLU is the most popular activation function used in the hidden layer of neural networks, which brings efficient computation by only activating neurons with positive outputs. Sigmoid is popularly used for probability prediction because output is always in range (0.1) with a smooth gradient. GeLU better nonlinearity and widely used in Natural Language processing and computer vision. HardTanh is more computation-effin -fffiicinn version of Tanh.
E
Additional Experiments
E.
Additional Experiments: OOD Detection
For Amazon Photos, Amazon Computers, Coauthor CS, Coauthor Physics, and OGBN Arxiv dataset, the OOD Detection results are shown in Table 6
E.2
Additional Experiments Misclassification Detection
For Amazon Photos, Amazon Computers, Coauthor CS, Coauthor Physics, and OGBN Arxiv dataset, the Misclassification Detection results are shown in Table
E.3
Graph Distance Minimization
We plot the (SNE visualization of latent space with different distance-based regularization weights and symbol sizes denote the total evidence. We plot for coraML in Figure CiteSeer in Figure Coauthor CS Figure Coauthor Physics in Figure With increasing weight, it tends to have more separable latent representation for different categories while degenerate mappings occur when distance minimization too large.
19

---

Table OOD Detection (Cont.)
AUROC
AUPR
Data
Model
ID.ACC
Fipi w/
Egi
Egi
Fipi
LP
63,28
86.74
83.88
67.10
63.08
GKDE
71.41
75. 14
73.58
nha.
49.21
47.68
n.a.
VGCN- Energy
88.95
82.76
83,43
57.49
60.64
Computers
Amazon
GKDE-GCN
82.73
77.03
70.32
1L.
49.81
45.92
0.a
87.63
Ours
89.88
83.56
89.26
71.82
58.51
71.06
43.35
I.P
89.27
94.24
90.26
T...
90.24
85.55
n.a.
GKDE
85.94
76.51
60.83
66.72
Amazon Photos
VGCN-Energy
GKDE-GCN
94.24
82.44
79.64
TLA.
72.60
71.71
ILA.
GPN
94.10
82,72
91.98
76.57
74.55
86.29
64.00
Ours
94.40
83.51
92.30
78.10
77.65
87.36
65.39
LP
83.78
80.86
71.13
GKDE
78.84
79.52
77.59
ILS.
66.30
64.69
R.S.
Coauthor
VGCN Energy
n.a.
CS
GKDE-GCN
93.13
85.02
84.45
80.15
77.90
n.a.
GPN
88.21
92.90
88.84
90,28
86,
Ours
89.24
12
92.37
91,38
56.20
91.17
90.45
LP
95.39
91.78
90.03
ILS.L
70.58
69.63
n.S.
GKDE
n.a.
n.a.
Coauthor Physies
VGCN-Fnergy
97.96
90.29
91 1.00
63.63
69.41
GKDE-GCN
97.95
87,38
84.62
n.a.
57.97
56,30
n.a.
GPN
97.40
85.20
94.51
89.63
61.89
83.73
66.44
Ours
97.44
83.28
94.42
90.36
62.80
83.61
70.62
n.a.
GKDE
51.51
68.
65. 80
47.22
45.23
OGBN Arsiv
VGCN-Energy
GKDE-GCR
75.61
73.89
68.84
64.91
72.44
64.50
n.3.
49.71
42.72
52.23
42.41
n.a
GPN
73.84
66.33
74,82
62.17
46.35
58.71
43.01
Ours
71.30
74.52
62.75
47.48
56.97
41.48
Alea: Alcatoric, Epi.: Epistemic, w/: with propagation, w/o: without propagation
Table 7: AUROC and AUPR for the Misclassification Detection (Cont.)
AUROC
AUPR
Data
Model
Alca w/
Epi w/
Alca w/
Epi w/
n.a.
n.a.
VGCN-Ennrgy
82.08
45.53
GKDE-GCN
79.66
73.66
63.26
56.93
Computers
GPN
82.20
77.58
Ours
80.75
74.87
93.12
90.11
n.a.
37.00
n.n.
VGCN-Eoergy
87.94
n.a.
48.35
GKDE-GON
84.11
75.07
54.35
.3
Photos
GPN
83.38
Ours
84.42
81.61
96.89
96.70
APPNP
89.92
n.a.
37.98
D.8.
Coauthor
VGCN-Energy
89.46
38.86
CS
GKDE GCN
89.24
80.98
39.30
30.52
GPN
85.72
81.56
12
38.98
Ours
86.21
83,94
97.34
96.80
APPNP
93.27
n.a.
38.14
B.S..
Comuthor Physics
VGCN-Energy
92.86
37.19
GKDE GCN
92.77
86.12
37.08
13
GPN
91.14
89.63
41.43
Ours
89.93
88.83
99.14
99.10
APPNP
77.55
n.S.
54,57
B.S.
VGCN-Energy
77.89
54.87
OGBN Arxiv
GKDE GCN
77.47
77.55
61.62
62.33
GPN
75.44
72.71
55.64
$2.99
Ours
75.30
72.85
83.95
81.54
Alca: Alcatoric, Epi.: Epistemic, w/: propagation
20

---

CoraML
(a) 0
(b) 10
(c) 10
(d) 10 2
Figure 2: latent representation for CoraML
CiteSeer
(a)
(b) 10-6
(c) 10
(d) 10-2
Figure 3: latent representation for CiteSeer
21

---

CoauthorCS
(a) 0
(b) 10
(c) 10
(d) 10
Figure 4: latent representation for Coauthor CS
CoasthorPhysics
(a)
(b) 10-6
(c) 10
(d) 10
Figure 5: latent representation for Coauthor Physics
E.4 Graph Activation
In this subsection, we present the 1-SNE visualizations of the learned representational space for various datasets in the following figures, without applying distance regularization. Instead, introduce different activation functions. It is worth noting the notable distinction in quality when using the LogSigmoid activation function, which appears
the smoothest among the activation functions employed on CiteSeer and Amazon Computers datasets. Once again, the size of each node corresponds to the square root of the learned evidence. Additionally, the color black indicates out-of different classes.
out-of-distribution distribution (OOD) instances across all datasets, while distinct colors represent
22

---

CoraML
Cle
Cbes
Coe
000
000
000
CiteSeer
PubMed
(a) RELU
(b) LogSigmoid
(c) HardTanh
Figure 6: Latent representation for CoraML, CiteSeer and PubMed on different graph activation functions: RELU, LogSigmoid, and HardTanh.
23

---

AmazonPhotos
S
Cle
Class
Cow
903
AmazonComputers
CoauthorCS
Coauthor Physics
Clao
Clax
Clea
(a) RELU
(b) LogSigmoid
(c) HardTanh
Figure 7: Latent representation for AmazonPhotoo AmazonComputers, CoauthorCS and Coauthor- Physics on different graph activation functions: RELU, LogSigmoid, and HardTanh.
24

---

E,5 Ablation Study
We show the full ablation study on three datasets: CoraMI, CiteSeer and PubMed in Table S
Table 8: Ablation Study with OOD Detection task (cont.)
AUROC
AUPR
Data
Model
ID-ACC
Aleu
Epi
Epii w/d
Alea
Epi w/
Egi
GPN
88.51
83,25
86.28
80.95
75.79
79.97
72.81
CoraML
82.58
76.54
77.60
GPN-CE-ACT
89.87
83,34
86,96
75.60
74.96
79.74
62.73
GPN-CE-ACT-GI
90.06
83.94
87.20
76.12
76.26
80.36
63.32
GPN
69.79
72.46
70.74
66.63
55.14
50.52
44,93
GPN-CE
70.98
74.20
73.75
68.41
58.12
53.55
46.60
Citeseer
GPN-CE-ACT
74.72
77.97
72.28
60.41
56.04
50.73
GPN-CE-ACT-GD
72.51
75.22
78.98
73.21
62.30
58.63
52.73
GPN
94,08
71.84
73.91
71.2
57.92
67.19
59.72
PubMcd
GPN-CE
74.19
74.50
GPN-CE-ACT
93.84
74.19
78.32
74.50
59.85
74.11
64.55
Alea: Aleatoric, Eip.: Eppistemic, w/t with propugation
GPN the original results from the GPN paper with default hyperparameters and ReLU as the middle activation lunction. GPN CE the original GPN model with re re-tuned dirichlet entropy regularization weight: GPN-CE-ACT the original GPN model with tuned entropy regularization weight and activation function; GPN CE-ACT DEEAAC--DDION GD((Ou)) add the distance- based regularization term and tuned the two weights and activation function.
25


Reviews:
[{"review_id": "djg0ptlW2t", "reviewer": "Reviewer_Spkg", "summary": "## Post Rebuttal Update \n\nI have engaged with the authors for the rebuttal, and found their responses informative, prompting me to increase my score from a 7 to an 8.\n\n## Original Review \nThe paper proposes theoretical results for Graph Posterior Networks (GPNs) that use the uncertainty cross-entropy loss (UCE), and shows that it is possible to trivially set the uCE loss to zero under certain conditions. The paper then proposes a way to regularise the UCE loss using distance, ensuring that OOD nodes that are clustered together are clustered together in latent space.", "questions": "In Table 2, it seems like the regularisation consistently gives lower AUROC but higher AUPR compared to the GPN baseline. Can you explain why this might be the case?", "limitations": "N/A.", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I like the theoretical analysis section of this paper. It constructs a way of obtaining zero UCE for a pathological example, showing that there are improvements required to be made to the GPN+UCE framework. Furthermore, it incorporates the fact that OOD points are not explicitly modeled in the UCE framework, and suggests ways to incorporate this. I also find the baselines considered pretty comprehensive, and the authors have done a good job covering a range of techniques. I also like the further ablations the paper has, such as selecting activation functions as well, using a validation CE loss, and I like that this has been properly ablated against. In general, I found the paper well motivated and written. I went through the proofs of Theorem 1-6 and found them accurate to my admittedly limited knowledge.", "weaknesses": "I have a few criticisms of the paper that I would like to get addressed - \n\n1. I would like a thorough description of all the assumptions made for Theorem 1, and where these assumptions would be violated or not, maybe with a toy example. For example, I'm not sure how strict the assumption \"If the underlying distribution of feature vectors belonging to class k, denoted by $X_k$ disjoint to each other,\" is, and would like a discussion of the drawbacks/limitations of the assumptions made in Theorem 1.\n2. Is the ball $B\\left(\\mathbf{z}_k, r_k\\right)$ guaranteed to have finite volume necessarily? There are pathological behaviours in neural networks that use ReLU activations, where it is possible to obtain high softmax scores (i.e. class probabilities) arbitrarily far from the training manifold [1], and this would make the volume of the ball very large potentially in some cases. \n\n\n[1] https://arxiv.org/abs/1812.05720", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Weakness 1 (W1). \n\nWe have two assumptions in Theorem 1: (1) the underlying distribution of feature vectors belonging to class $k$, denoted by $X_k$,  is disjoint to each other; (2) the multi-layer perception (MLP) module, $f_\\theta$,  and the normalizing flow module, $h_\\phi$, in the posterior network, can be arbitrarily complex. The first assumption means that the supports of the in-distribution (ID) classes are separable in the feature space, where the support of a class is defined as the region in the feature space that has non-zero density for this class. The second assumption means that the posterior network defined based on $f_\\theta$ and $h_\\phi$ is a universal approximator. The universal approximation theorem for MLP with a single hidden layer has been studied in the literature (e.g., Pinkus’1919) and used in the theoretical analysis of graph neural networks and other deep learning models (e.g., Loukas’2020). \n\nAn implication of Theorem 1 is that the UCE loss is insufficient to separate OOD from ID nodes. We present Example 2 to discuss this implication (lines 152 to 158). We discussed the limitations based on our second assumption in lines 159 to 165 and gave an example to show that our analysis is still informative about the shape these networks are likely to take. Our first assumption may not hold in datasets where some ID classes are not separable due to noises on features and/or class labels. However, our intuition is that if the UCE loss is insufficient to separate OOD from OOD nodes in the separable case, this loss function will more likely fail in the more challenging non-separable case. We will consider the theoretical analysis based on the relaxation of the two assumptions in our future work. For example, we may get similar results in Theorem 1 by allowing a certain level of noise on class labels. \n\nW2 (part 1)\n\nYes, here we assume that f is arbitrarily complex (no requirements on it being a ReLU-based MLP) so we choose the ball to have a finite volume. The theoretical evaluations will be more challenging when the support regions are not bounded. For this reason, some papers related to OOD analysis (e.g., Karthik et al. 2021) directly assume that the support regions are bounded.\n\nW2 (part 2)\n\nWe mainly look at the misclassification results using aleatoric uncertainty, which is the most effective uncertainty measure for misclassification detection. There are three datasets examined in Table 2, and 5 additional datasets in Table 4 in the complementary material. It is true that our method gives lower AUROC, but we think our results are comparable to GPN for five out of the eight datasets in the sense that the differences are between 0.14\\% and 1.5\\%. For the remaining three datasets, i.e., CoraML, Citeseer, and Amazon Photos, the differences are a bit larger, between 2.8\\% and 6.7\\%. On the other hand, our method achieves much higher AUPR scores than GPN for seven of the eight datasets: the improvements are between 28.31\\% and 54.67\\% with an average of 43.18\\% improvement. For the  Citeseer dataset, our method is better than GPN for 11.89\\%. \n\nFirst, we would like to point out that the GPN paper reported a similar behavior for comparison to their baseline models in that it gives lower AUROC but higher AUPR; please refer to the misclassification detection results in Table 10 and Table 11 of the GPN paper. For example, Table 10 of the GPN paper shows that the GKDE-GCN method has the highest AUPR (49.61\\%) but has a lower AUROC (80.80\\%) than six of the seven baselines for the CiteSeer dataset. For the PubMed dataset, GPN has the highest AUPR (40.74\\%) but has a lower AUROC (80.46\\%) than six of the seven baselines. \n\nSecond, we explain why it makes sense to have higher AUPR but lower AUROC. These two metrics offer different perspectives to measure the quality of a ranking on data points for separating positives and negatives. A lower AUROC but a higher AUPR for our method, compared to GPN, indicates that our method produces more true positives among the top-ranked nodes than GPN, while GPN can separate true positives and negatives better than our method among the lower-ranked nodes. We note that a high AUPR is important for applications where human experts want to manually verify the top-ranked misclassified nodes or anomalies. Due to the high cost of manual verification, it is important to ensure a high rate of true positives among the top-ranked data points, and in this case, AUPR may be a better metric than AUROC. \n\nLastly, not just for misclassification detection, this empirical behavior also exists for classification tasks as well. For example, Jesse and Goadric pointed out in their 2006 ICML paper that algorithms that optimize AUROC are not guaranteed to optimize AUPR and vice versa. In addition, a recent arXiv’23 paper by Yuan et al. reports similar empirical observations for classification tasks. For example, some learned classifiers had the highest AUPR (4\\% to 10\\% higher than the other methods) but the lowest AUROC (8\\% to 10\\% lower than the other methods) in the SOAP dataset (See Table 2 and the second paragraph from the last in Section 4.1 of the arXiv’23 paper).\n\nReferences: \n\n[1] Pinkus, Allan. \"Approximation theory of the MLP model in neural networks.\" Acta numerica 8 (1999): 143-195. \n\n[2] Loukas, Andreas. \"How hard is to distinguish graphs with graph neural networks?.\" NeurIPS (2020): 3465-3476.\n\n[3] Ahuja, Kartik, et al. \"Invariance principle meets information bottleneck for out-of-distribution generalization.\" NeurIPS (2021): 3438-3450.\n\n[4] Davis, Jesse, and Mark Goadrich. \"The relationship between Precision-Recall and ROC curves.\" ICML (2006): 233-240. \n\n[5] Yuan, Zhuoning, Dixian Zhu, Zi-Hao Qiu, Gang Li, Xuanhui Wang, and Tianbao Yang. \"Libauc: A deep learning library for x-risk optimization.\" arXiv preprint arXiv:2306.03065 (2023).\n"}, {"review_id": "GbbR2WQQTd", "reviewer": "Reviewer_nRfd", "summary": "The paper proposes a distance-based regularization to improve the OOD detection and misclassification detection tasks on the graph node classification. The regularization enforces the clustered OOD nodes to be close in the latent space. ", "questions": "The authors should improve writing in the revision by providing more contexts on the claims and definitions. It is also questionable on the results in the Table 2. I hope the author can clarify that. ", "limitations": "Yes, the authors addresses limitations in the theoretic analysis.", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 1, "contribution": 3, "strengths": "- The paper includes comprehensive experiments on multiple commonly used benchmark dataset and detailed ablation study. \n\n- The paper provides theoretic analysis on the limitation of the GPN.", "weaknesses": "- Equation 2 defines aleatoric and epistemic uncertainty. Why are they defined in this way? Is there any reference or reason?\n\n- The writing is not clear. In section 4.1, there are a lot of theorems, but a sentence is missing to summarize what is the limitation of the UCE. Although at the beginning of section 4, there is a summary of those theorems, but it fails to present the overall idea of what the limitation is. Also, it is hard to connect Section 4.1 to 4.2. Why would the limitation of UCE loss mentioned in section 4.1 motivate the distance minimization on the graph?\n\n- The proposed model improves AUPRC but has worse AUROC. It is not easy to tell whether the model is better. How does the model manage to improve AUPRC by 50% while remaining AUROC unchanged in Table 2? How could a model with 95% AUPRC has only 80% AUROC? Could the authors plot out the ROC and PR curves? ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Weakness 1 (W1). \n\nThe aleatoric and epistemic uncertainty measures defined in Equation 2 are the same measures used in the PN and GPN papers. Please refer to Section 2 of the PN paper and Section 3.3 in the recent TMLR’23 survey paper by Ulmer et al. for more detailed discussions on these Dirichlet-based uncertainty measures. In the following, we summarize some main advantages of these uncertainty measures over the alternative ones. \n\nFirst, the Dirichlet-based epistemic uncertainty measure can be interpreted as the spread of the Dirichlet distribution about the class probability vectors that are predicted by different model parameters ( $\\theta$ ) sampled from the posterior $p(\\theta|D)$, where $D$ refers to the training data. GPN and PN directly predict the Dirichlet distribution for each given input x in a deterministic way without explicitly estimating the posterior $p(\\theta|D)$. If the spread is large ($u_i^{epis}$ is large), it means the model (epistemic) uncertainty is high (the input sample is distant from the training samples in the feature space).  \n\nSecond, the aleatoric uncertainty measure ( $u_i^{alea}$ ) is the largest projected class probability (multiplied by -1). If this uncertainty measure is high, it indicates that all the class probabilities are low (the input sample is ambiguous). \n\nThird, the Dirichlet-based aleatoric and epistemic uncertainty measures in Definition 1 can be calculated via a single forward pass. In comparison, other aleatoric measures based on samples of the posterior p(|D), such as dropout-based and deep ensemble-based, require multiple forward passes and are unsuitable for real-time applications. \n\nWe will include the aforementioned details of these two uncertainty measures in our revised version to make our paper self-contained.\n\nReferences:\n\nUlmer, Dennis, Christian Hardmeier, and Jes Frellsen. \"Prior and posterior networks: A survey on evidential deep learning methods for uncertainty estimation.\" Transactions on Machine Learning Research (2023).\n\nW2.  \n\nThe overall idea about the limitations of the UCE loss is that this loss function alone is insufficient to learn a representation space that separates OOD from ID nodes using the GPN model. We discussed the motivation for the distance minimization on the graph based on the limitations of the UCE loss in the first two paragraphs of Section 4.2 on page 6. We used Example 2 on Page 4 to illustrate that when OOD nodes are separable from the ID nodes in the feature space based on OOD-specific features, they can be close in the learned representation space, as OOD-specific features are discarded. In other words, the learned representation space by GPN based on the UCE loss is not guaranteed to preserve the distance between OOD and ID nodes in its representation learning step. We consider distance regularization proposed in Section 4.2, as it helps prevent the model from discarding relevant OOD-specific events while decreasing variation between nodes in the representation space. \n\nWe will improve the writing of Section 4 with implications of each theorem and connections among these theorems in our revised version. \n\nW3. \n\n(1) Table 2 reports the empirical results on misclassification detection. We want to highlight that our main contributions are on OOD detection but not misclassification detection. As stated at the end of Section 1 (Introduction), our first contribution is theoretical evaluations of the limitations of the UCE loss for OOD detection. Our second contribution is our distance-based regularization which helps prevent the model from discarding relevant OOD-specific features. In the third contribution, our empirical comparisons on eight datasets, as shown in Table 1 (three datasets) in the main paper and Table 3 (five datasets) in the complementary material, have well demonstrated that our method outperformed the GPN baseline and four other baselines in the majority of the settings on both the AUROC and AUPR metrics. \n\nSimilarly, the main contributions of the GPN paper are also OOD detection but not misclassification detection. For example, the results in Table 10 and Table 11 in the complementary material of the GPN paper demonstrated that for the misclassification detection task,  GPN performed worse than the best of the baselines for seven of the eight datasets in the range between 0.5\\% and 3.7\\% of the AUROC metric. GPN performed worse than the best of the baselines for four of the eight datasets in the range between 0.1\\% and 21.7\\% based on the AUPR metric. \n\n(2) For misclassification detection, our empirical results demonstrate that our method outperformed the baselines for all the datasets based on the AUPR with large percentages. Based on the AUROC metric, our method performed worse than the best of the baselines, but the differences are within around 3\\% for six of the eight datasets: Amazon Computers, Amazon Photos, Coauthor CS, Coauthor Physics, and ODBG Arxiv, and PubMed. \n\nSee our response to W2 of Reviewer Spkg for more details for two related clarifications: (a) the GPN (the main competitor in our paper) has the same empirical behavior compared to their baselines as reported in the GPN paper. (b) Some papers report similar empirical behavior in classification tasks, and we gave interpretations for this empirical behavior. \n\n(3) About our model learned based on the PubMed dataset that has 95\\% AUPR but only 80\\% AUROC, we have plotted out the ROC and PR curves of our method for this dataset and two other datasets: CoraML and CiteSeer, which can be referred to the pdf in the global rebuttal. \n\nQuestions. \n\nThanks for your suggestions. We will improve our presentation with more context on assumptions, definitions, and implications.\n\nWe have explained the results in Table 2 with more details to clarify the potential confusion (e.g., the observation that our method gives higher AUPR but lower AUROC for misclassification detection). We will add these details in the revision. "}, {"review_id": "Z8AjlC8Eow", "reviewer": "Reviewer_dzMP", "summary": "This manuscript studies the uncertainty quantification for the non-independent node-level prediction problem. The proposed framework is built upon the graph posterior network (GPN) with minimizing uncertainty cross-entropy as the main loss function. A distance-based regularization technique is further proposed to learn representational space mappings in order to handle OOD samples. ", "questions": "1. How can Eq. (1) and (2) derive the aleatoric uncertainty and epistemic uncertainty? The authors do not mention the rationale behind this derivation, which makes it hard to understand the whole process.  ", "limitations": "I am not seeing major drawbacks.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The topic of quantifying the uncertainty of GNN predictions is timely and interesting. The overall presentation is easy to follow.\n\nI checked the overall theoretical contributions and haven't found major flaws. \n\nThe proposed two regularization terms are validated by extensive experiments. ", "weaknesses": "I am not seeing major drawbacks, except there are some points related to the problem definition.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Weakness 1 (W1): How can Eq. (1) and (2) derive the aleatoric uncertainty and epistemic uncertainty? The authors do not mention the rationale behind this derivation, which makes it hard to understand the whole process.\n\nThe aleatoric and epistemic uncertainty measures defined in Equation 2 are the same measures used in the PN and GPN papers. Please refer to Section 2 of the PN paper and Section 3.3 in the recent TMLR’23 survey paper by Ulmer et al. for more detailed discussions on these Dirichlet-based uncertainty measures. In the following, we summarize some main advantages of these uncertainty measures over the alternative ones. \n\nFirst, the Dirichlet-based epistemic uncertainty measure can be interpreted as the spread of the Dirichlet distribution about the class probability vectors that are predicted by different model parameters ($\\theta$) sampled from the posterior $p(\\theta|D)$, where $D$ refers to the training data. GPN and PN directly predict the Dirichlet distribution for each given input $x$ in a deterministic way without explicitly estimating the posterior $p(\\theta|D)$. If the spread is large ($u_i^{epis}$ is large), it means the model (epistemic) uncertainty is high (the input sample is distant from the training samples in the feature space).  \n\nSecond, the aleatoric uncertainty measure ($u_i^{alea}$) is the largest projected class probability (multiplied by -1). If this uncertainty measure is high, it indicates that all the class probabilities are low (the input sample is ambiguous). \n\nThird, the Dirichlet-based aleatoric and epistemic uncertainty measures in Definition 1 can be calculated via a single forward pass. In comparison, other aleatoric measures based on samples of the posterior $p(\\theta|D)$, such as dropout-based and deep ensemble-based, require multiple forward passes and are unsuitable for real-time applications. \n\nWe will include the aforementioned details of these two uncertainty measures in our revised version to make our paper self-contained.\n\nReferences:\n\n[1] Ulmer, Dennis, Christian Hardmeier, and Jes Frellsen. \"Prior and posterior networks: A survey on evidential deep learning methods for uncertainty estimation.\" Transactions on Machine Learning Research (2023).\n\n[2] Charpentier, Bertrand, Daniel Zügner, and Stephan Günnemann. \"Posterior network: Uncertainty estimation without ood samples via density-based pseudo-counts.\" Advances in Neural Information Processing Systems 33 (2020): 1356-1367.\n\n[3] Stadler, Maximilian, et al. \"Graph posterior network: Bayesian predictive uncertainty for node classification.\" Advances in Neural Information Processing Systems 34 (2021): 18033-18048."}, {"review_id": "9oLB9Op2t3", "reviewer": "Reviewer_XBDF", "summary": "This paper focuses on uncertainty quantification in node classification. The authors examine the drawbacks of UCE. Inspired by our theoretical analysis, they introduced a distance-based regularization technique to obtain a better representation network for the uncertainty quantification. Experimental results show the superior performance of the proposed approach compared to the current state-of-the-art methods in out-of-distribution (OOD) detection and misclassification detection.\n", "questions": "The authors should better discuss the limitation of their work.", "limitations": "N/A", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. This paper is well motivated, it discusses the limitations of GPN model on semi-supervised node classification tasks, and it provides detailed theoretical analysis to reveal the limitations of GPN for detecting OOD nodes\n\n2. This paper proposes a distance regularizer to overcome the above limitation.\n\n3. This paper provides extensive experimental results that demonstrate that the proposed method can achieve state-of-the-art performance on both out-of-distribution (OOD) detection and misclassification detection.", "weaknesses": "This paper is not in my area, I'm not familiar with existing work about both node classification and uncertainty qualification. So I cannot assess the contribution of this work reliably.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Questions: The authors should better discuss the limitation of their work.\n\nWe discussed the limitations of Theorem 1 in lines 159 to 165 on Page 4 and the limitations of Theorem 8 in lines 226-234 on Page 6. In addition, our proposed regularization terms proposed in Section 4.2 are most effective for homophily graphs than heterophily graphs. All eight benchmark datasets used are homophily graphs. We will add a section to summarize these limitations when it comes to revision. "}]

Author rebuttal:
We append the ROC-PR curves for our model related to Table 2 in the attached pdf. 

Meta-review: The paper presents theoretical results on Graph Posterior Networks (GPNs) with uncertainty cross-entropy loss (UCE) and highlights its limitations. To address these limitations, a distance-based regularization is introduced to ensure that clustered OOD nodes remain close in the latent space. This is argued to improve OOD detection and graph node classification.

### Strengths:

- Strong theoretical foundation with an analysis that reveals the limitations of the GPN+UCE framework.
- Proposes a method to address the fact that OOD points are not explicitly modeled in the UCE framework.
- Comprehensive experimentation on multiple benchmark datasets with detailed ablation studies.
- Demonstrates state-of-the-art performance on OOD detection and misclassification detection tasks.

### Weaknesses:

- Multiple reviewers found the writing unclear, particularly regarding 1. the linkage between sections and the overall presentation of theorems; and 2. the derivation of aleatoric and epistemic uncertainties (Eqs. 1-2).
- Concerns were raised about certain assumptions made in Theorem 1, specifically their limitations or instances where they might be violated.
- Questions were raised regarding the results in Table 2, especially the inconsistency between AUROC and AUPR scores. The model manages to improve AUPRC significantly while keeping AUROC largely unchanged.

Weighting the strengths and weaknesses, the majority of reviewers find value in the presented work. Given the significance of the work, I recommend accept. It is essential for the authors to address the raised concerns during the revision process.
Decision: Accept (poster)