Multidimensional Uncertainty Quantification for Deep Neural Networks
Deep neural networks (DNNs) have received tremendous attention and achieved
great success in various applications, such as image and video analysis,
natural language processing, recommendation systems, and drug discovery.
However, inherent uncertainties derived from different root causes have been
realized as serious hurdles for DNNs to find robust and trustworthy solutions
for real-world problems. A lack of consideration of such uncertainties may lead
to unnecessary risk. For example, a self-driving autonomous car can misdetect a
human on the road. A deep learning-based medical assistant may misdiagnose
cancer as a benign tumor.
  In this work, we study how to measure different uncertainty causes for DNNs
and use them to solve diverse decision-making problems more effectively. In the
first part of this thesis, we develop a general learning framework to quantify
multiple types of uncertainties caused by different root causes, such as
vacuity (i.e., uncertainty due to a lack of evidence) and dissonance (i.e.,
uncertainty due to conflicting evidence), for graph neural networks. We provide
a theoretical analysis of the relationships between different uncertainty
types. We further demonstrate that dissonance is most effective for
misclassification detection and vacuity is most effective for
Out-of-Distribution (OOD) detection. In the second part of the thesis, we study
the significant impact of OOD objects on semi-supervised learning (SSL) for
DNNs and develop a novel framework to improve the robustness of existing SSL
algorithms against OODs. In the last part of the thesis, we create a general
learning framework to quantity multiple uncertainty types for multi-label
temporal neural networks. We further develop novel uncertainty fusion operators
to quantify the fused uncertainty of a subsequence for early event detection.
Xujiang Zhao
# Multidimensional Uncertainty Quantification for

###### Abstract

We present a new method for computing the uncertainty quantification for the uncertainty quantification of the uncertainty quantification for the uncertainty quantification of the uncertainty quantification for the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification quantification of the uncertainty quantification of the uncertainty quantification quantification of the uncertainty quantification quantification of the uncertainty quantification quantification of the uncertainty quantification of the uncertainty quantification of the uncertainty quantification quantification of the uncertainty quantification quantification of the uncertainty quantification of the uncertainty quantification quantification of the uncertainty quantification quantification of the uncertainty quantification quantification of the uncertainty quantification quantification of the uncertainty quantification quantification of the uncertainty quantification quantification of the uncertainty quantification quantification of the uncertainty quantification quantification of the uncertainty quantification quantification of the uncertainty quantification quantification of the uncertainty quantification quantification of the uncertainty quantification quantification of the uncertainty quantification quantification of the uncertainty quantification quantification of the uncertainty quantification quantification of the uncertainty quantification quantification of the uncertainty quantification quantification of the uncertainty quantification quantification of the uncertainty quantification quantification of the uncertainty quantification quantification of the uncertainty quantification quantification of the uncertainty quantification quantification of the uncertainty quantification quantification of the uncertainty quantification quantification of the uncertainty quantification quantification of the uncertainty quantification quantification quantification of the uncertainty quantification quantification of the uncertainty quantification quantification of the uncertainty quantification quantification of the uncertainty quantification quantification of the uncertainty quantification quantification of the uncertainty quantification quantification of the uncertainty quantification quantification of the uncertainty quantification quantification of the uncertainty quantification quantification of the uncertainty quantification quantification of the uncertainty quantification quantification of the uncertainty quantification quantification quantification of the uncertainty quantification quantification quantification of the uncertainty quantification quantification quantification of the uncertainty quantification quantification quantification of the uncertainty quantification quantification quantification of the uncertainty quantification quantification quantification of the uncertainty quantification quantification quantification of the uncertainty quantification quantification quantification of the uncertainty quantification quantification quantification of the uncertainty quantification quantification quantification of the uncertainty quantification quantification quantification of the uncertainty quantification quantification quantification of the uncertainty quantification quantification quantification of the uncertainty quantification quantification quantification of the uncertainty quantification quantification quantification quantification of the uncertainty quantification quantification quantification quantification of the uncertainty quantification quantification quantification quantification of the uncertainty quantification quantification quantification quantification of the uncertainty quantification quantification quantification quantification of the uncertainty quantification quantification quantification quantification of the uncertainty quantification quantification quantification quantification of the uncertainty quantification quantification quantification quantification of the uncertainty quantification quantification quantification quantification of the uncertainty quantification quantification quantification quantification of the uncertainty quantification quantification quantification quantification of the uncertainty quantification quantification quantification quantification of the uncertainty quantification quantification quantification quantification of the uncertainty quantification quantification quantification quantification quantification of the uncertainty quantification quantification quantification quantification quantification of the uncertainty quantification quantification quantification quantification quantification of the uncertainty quantification quantification quantification quantification quantification of the uncertainty quantification quantification quantification quantification quantification of the uncertainty quantification quantification quantification quantification quantification of the uncertainty quantification quantification quantification quantification quantification of the uncertainty
## Chapter 4 Conclusions

In this thesis we have presented a new method for computing the energy of a system of coupled systems. We have presented a new method for computing the energy of a system of coupled systems.
MULTIDIMENSIONAL UNCERTAINTY QUANTIFICATION FOR DEEP NEURAL NETWORKS

by

XUJIANG ZHAO

DISSERTATION

Presented to the Faculty of

The University of Texas at Dallas

in Partial Fulfillment

of the Requirements

for the Degree of

DOCTOR OF PHILOSOPHY IN COMPUTER SCIENCE

THE UNIVERSITY OF TEXAS AT DALLAS

August 2022
###### Acknowledgements.

 I am tremendously grateful to my advisor, Professor Feng Chen, for his excellent advice, encouragement, and support over the years. He brought my attention to machine learning, data mining, and other exciting research topics at the early stage of my PhD program. During my studies at UAlbany and UT Dallas, he was always willing to help me with suggestions for my research. His excellent research personality profoundly influences me.

I want to thank my committee members, Professor Gopal Gupta, Professor Rishabh Iyer, and Professor Chung Hwan Kim, for their willingness to serve as my committee members. I would also like to thank my Examining Committee Chair, Professor Justin Ruths, for his valuable time. I got invaluable help and great feedback from them. Their many critically important comments helped me to improve this dissertation significantly.

I am grateful to Professor Jin-Hee Cho, Professor Rishabh Iyer, and Professor Qi Yu for their care and generous help, especially in the early stage of my PhD career. They gave me detailed instructions and support.

I received tremendous help from friends and colleagues: Professor Zhiqiang Tao, Dr. Chen Zhao, Dr. Baojian Zhou, Dr. Fei Jie, Dr. Adil Alim, Chunpai Wang, Changbin Li, Haoliang Wang, Yuzhe Ou, Linlin Yu, Yibo Hu, Zhuoyi Wang, and Junfeng Guo. I also had two fantastic summer internships at _Alibaba Damo Academy_ and _NEC Laboratories America_ in the summer of 2019 and 2021, advised by great team members Dr. Hongxia Yang and Dr. Xuhcao Zhang.

I would also like to express my sincere gratitude to my parents, sister, and brother for their unconditional love.
Finally, this dissertation is dedicated to my wife, Chongchong, and my son, Shuhuan. I want to thank my wife and my son for their love and support.

June 2022
## Chapter 1 Multidimensional Uncertainty Quantification for

Deep neural networks (DNNs) have received tremendous attention and achieved great success in various applications, such as image and video analysis, natural language processing, recommendation systems, and drug discovery. However, inherent uncertainties derived from different root causes have been realized as serious hurdles for DNNs to find robust and trustworthy solutions for real-world problems. A lack of consideration of such uncertainties may lead to unnecessary risk. For example, a self-driving autonomous car can misdetect a human on the road. A deep learning-based medical assistant may misdiagnose cancer as a benign tumor.

In this work, we study how to measure different uncertainty causes for DNNs and use them to solve diverse decision-making problems more effectively. In the first part of this thesis, we develop a general learning framework to quantify multiple types of uncertainties caused by different root causes, such as vacuity (i.e., uncertainty due to a lack of evidence) and dissonance (i.e., uncertainty due to conflicting evidence), for graph neural networks. We provide a theoretical analysis of the relationships between different uncertainty types. We further demonstrate that dissonance is most effective for misclassification detection and vacuity is most effective for Out-of-Distribution (OOD) detection. In the second part of the thesis, we study the significant impact of OOD objects on semi-supervised learning (SSL) for
DNNs and develop a novel framework to improve the robustness of existing SSL algorithms against OODs. In the last part of the thesis, we create a general learning framework to quantity multiple uncertainty types for multi-label temporal neural networks. We further develop novel uncertainty fusion operators to quantify the fused uncertainty of a subsequence for early event detection.
TABLE OF CONTENTS

ACKNOWLEDGMENTS

ABSTRACT

LIST OF FIGURES

LIST OF TABLES

CHAPTER 1 INTRODUCTION

iv

1.1 Motivations

1.2 Summary of Main Contributions

1.3 Outline

CHAPTER 2 UNCERTAINTY AWARE SEMI-SUPERVISED LEARNING ON GRAPH DATA

2.1 Introduction

2.2 Related Work

2.3 Multidimensional Uncertainty and Subjective Logic

2.3.1 Notations

2.3.2 Subjective Logic

2.3.3 Evidential Uncertainty

2.3.4 Probabilistic Uncertainty

2.4 Relationships Between Multiple Uncertainties

2.5 Uncertainty-Aware Semi-Supervised Learning

2.5.1 Problem Definition

2.5.2 Proposed Uncertainty Framework

2.5.3 Graph-based Kernel Dirichlet distribution Estimation (GKDE)

2.6 Experiments

2.6.1 Experiment Setup

2.6.2 Results

2.6.3 Why is Epistemic Uncertainty Less Effective than Vacuity?

2.6.4 Graph Embedding Representations of Different Uncertainty Types

2.7 Conclusion
* 3 UNCERTAINTY-AWARE ROBUST SEMI-SUPERVISED LEARNING WITH OUT OF DISTRIBUTION DATA
	* 3.1 Introduction
	* 3.2 Semi-Supervised Learning (SSL)
		* 3.2.1 Notations
	* 3.3 Impact of OOD on SSL Performance
	* 3.4 Methodology
		* 3.4.1 Uncertainty-Aware Robust SSL Framework
		* 3.4.2 Bi-level Optimization Approximation
		* 3.4.3 Weighted Batch Normalization
		* 3.4.4 Additional Implementation Details:
	* 3.5 Experiment
		* 3.5.1 Evaluation on Synthetic Dataset
		* 3.5.2 Real-world Dataset Details
		* 3.5.3 Performance with different real-world OOD datasets
		* 3.5.4 Efficiency Analysis
		* 3.5.5 Additional Analysis
	* 3.6 Conclusion
* 4 MULTI-LABEL TEMPORAL EVIDENTIAL NEURAL NETWORKS FOR EARLY EVENT DETECTION
	* 4.1 Introduction
	* 4.2 Related Work
	* 4.3 Preliminaries
		* 4.3.1 Notations
		* 4.3.2 Evidential neural networks
		* 4.3.3 Multi-label classification
	* 4.4 Problem Formulation
	* 4.5 Multi-Label Temporal Evidential Neural Networks
		* 4.5.1 MTENN Framework
		* 4.5.2 Loss
#### 4.5.3 Theoretical Analysis
	* 4.6 Multi-label Sequential Uncertainty Quantittation
		* 4.6.1 Weighted Binomial Comultiplication
		* 4.6.2 Uncertainty mean scan statistics.
	* 4.7 Experiments
		* 4.7.1 Experiment Details
		* 4.7.2 Results and Analysis
	* 4.8 Conclusion
* 5 CONCLUSION AND FUTURE WORK
	* 5.1 Conclusion of Completed Work
	* 5.2 Future Work
		* 5.2.1 Quantification of multidimensional uncertainty
		* 5.2.2 Interpretation of Multidimensional Uncertainty
	* 6.1 PROOFS OF THE PROPOSED THEOREMS
	* 6.1 Proof of Theorem 1
	* 6.2 Derivations for Joint Probability and KL Divergence
		* 6.2.1 Joint Probability
		* 6.2.2 KL-Divergence
	* 6.3 Proof of Theorem 2
	* 6.4 Proof of Proposition 2
	* 6.5 Proof of Proposition 3
* 6.2.3 BIOGRAPHICAL SKETCH CURRICULUM VITAE
List of Figures
* 2.1 Multiple uncertainties of different predictions. Let \(\mathbf{u}=[u_{v},u_{diss},u_{alea},u_{epis},u_{en}]\).
* 2.2 Uncertainty Framework Overview. Subjective Bayesian GNN (a) is designed for estimating the different types of uncertainties. The loss function includes a square error (d) to reduce bias, GKDE (b) to reduce errors in uncertainty estimation, and teacher network (c) to refine class probability.
* 2.3 Illustration of GKDE. Estimate prior Dirichlet distribution \(\text{Dir}(\hat{\alpha})\) for node \(j\) (red) based on training nodes (blue) and graph structure information.
* 2.4 Graph embedding representations of the Cora dataset for classes and the extent of uncertainty: (a) shows the representation of seven different classes; (b) shows our model prediction; and (c)-(f) present the extent of uncertainty for respective uncertainty types, including vacuity, dissonance, aleatoric, epistemic.
* 2.5 Graph embedding representations of the Citeseer dataset for classes and the extent of uncertainty: (a) shows the representation of seven different classes, (b) shows our model prediction, and (c)-(f) present the extent of uncertainty for respective uncertainty types, including vacuity, dissonance, and aleatoric uncertainty, respectively.
* 2.6 Graph embedding representations of the Amazon Photo dataset for the extent of vacuity uncertainty based on OOD detection experiment.
* 3.1 (a) Traditional SSL. (b) SSL with OODs.
* 3.2 SSL performance with different type OODs in synthetic datasets.
* 3.3 SSL performance with different type OODs in real world datasets.
* 3.4 Main flowchart of the proposed Weighted Robust SSL algorithm.
* 3.5 Additional experiments on the synthetic dataset.
* 3.6 Classification accuracy with varying OOD ratio on MNIST. (a)-(b) consider faraway OODs with batch normalization; (c)-(d) consider boundary OODs without batch normalization. Shaded regions indicate standard deviation.
* 3.7 Classification accuracy with varying OOD ratio on CIFAR10. We use _WRN-28-2_ (contains BN module) as the backbone. Shaded regions indicate standard deviation.
* 3.8 Running time results. (a)-(b) show our proposed approaches are only \(1.7\times\) to \(1.8\times\) slower compared to base SSL algorithms, while other robust SSL methods are \(3\times\) slower. (c) shows that the running time of our method would increase with \(J\) (inner loop gradients steps) and \(P\) (inverse Hessian approximation) increase. (d)-(e) show the running time of our strategies with different combinations of tricks viz; last layer updates and updating weights every \(L\) iterations. Note that by using only last layer updates, our strategies are around \(2\times\) slower. With \(L=5\) and last layer updates, we are around \(1.7\times\) to \(1.8\times\) slower with comparable test accuracy.
(a) shows that our method learns optimal weights for ID and OOD samples; (b) shows that our method is stable even for a small validation set containing 25 images.
* 3.10 (a) shows that WBN and CRW (or L1 regularization) are critical in retaining the performance gains of reweighting; (b)-(c) demonstrate that the performance of our approach would increase with (inner loop gradients steps) and inverse Hessian approximation) increase due to high-order approximation.
* 4.1 How many frames do we need to detect smoke and watch actions reliably? Can we even detect these actions before they finish? Existing event detectors are trained to recognize complete events only; they require seeing the entire event for a reliable decision, preventing early detection. We propose a learning formulation to recognize partial events, enabling early detection.
* 4.2 Illustration of overconfidence prediction. (Left) The occurrence of the event is falsely detected at the pre-event stage prior to its starting. This indicates that predicted probabilities are not reliable due to insufficient evidence. (Right) Instead of probabilities, subjective opinions (_e.g.,_ belief, disbelief, uncertainty) are used in the proposed method for early event detection.
* 4.3 **Framework Overview.** Given the streaming data, (b) MTENN is able to quality predictive uncertainty due to a lack of evidence for multi-label classifications at each time stamp based on belief/evidence theory. Specifically, (a) at each time step with data segment \(x^{t}\), MTENN is able to predict Beta distribution for each class, which can be equivalent transfer to subjective opinion \(\omega_{t}\); (c) based on a sliding window, two novel fusion operators (weighted binomial comultiplication and uncertainty mean scan statistics) are introduced to quantify the fused uncertainty of a sub-sequence for an early event.
* 4.4 Uncertainty distribution changed at the ongoing event early stage
* 4.5 Sensitive Analysis of uncertainty threshold. There is a tradeoff between detection delay and detection accuracy. The higher uncertainty threshold increase, the more overconfidence predictions.
* 4.6 Sensitive Analysis of sliding window size. When the sliding window size increases, the detection delay continuously decreases, and detection F1 increases until the sliding window size is large enough.
* 4.7 Per-Class Evaluation on Audio (Engine) dataset.
List of Tables
* 2.1 Important notations and corresponding descriptions.
* 2.2 Description of datasets and their experimental setup for the node classification prediction.
* 2.3 Hyperparameter configurations of S-BGCN-T-K model
* 2.4 Description of datasets and their experimental setup for the OOD detection.
* 2.5 AUROC and AUPR for the Misclassification Detection.
* 2.6 AUROC and AUPR for the OOD Detection.
* 2.7 Ablation experiment on AUROC and AUPR for the Misclassification Detection.
* 2.8 Big-O time complexity of our method and baseline GCN.
* 2.9 Ablation experiment on AUROC and AUPR for the OOD Detection.
* 2.10 Compare with DropEdge on Misclassification Detection
* 2.11 Epistemic uncertainty for semi-supervised image classification.
* 3.1 Important notations and corresponding descriptions.
* 3.2 Uncertainty for different type OODs based on MNIST.
* 3.3 Uncertainty for different type OODs based on CIFAR10.
* 3.4 Test accuracies for the two moons dataset (\(P=10,J=3\) for R-SSL-IFT and \(J=1\) for R-SSL-Meta).
* 3.5 Test accuracies for different \(P\) at OOD ratio = 50% on the synthetic dataset.
* 3.6 Hyperparameter settings used in MNIST experiments for four representative SSL. All robust SSL methods (e.g., ours (WR-SSL), DS3L, and UASD) are developed based on these representative SSL methods.
* 3.7 SVHN-Extra (VAT) with different OOD ratios.
* 3.8 CIFAR100 (MT) with different OOD ratios.
* 3.9 Test accuracies for different numbers of clusters \(K\) on the MNIST dataset with 50% Mean MNIST as OODs
* 4.1 Important notations and corresponding descriptions.
* 4.2 Description of datasets and their experimental setup for the early event detection.
* 4.3 Early sound event detection performance on Audio datasets.
* 4.4 Early human action detection performance on AVA datasets with different segment lengths (ST).
* 4.5
* 4.5 Ablation study. MTENN-BC: a variant of MTENN-WBC that uses binomial comultiplication instead of weighted binomial comultiplication; MTENN (Phase I): only consider phase I to predict event without any sequential uncertainty head; MTENN w/o MTENN loss: a variant of MTENN (Phase I) that consider BCE loss.
* 4.6 Compare inference time with different methods.
## Chapter 1 Introduction

### 1 Motivations

Deep neural networks have reached almost every field of science in the last decade and have become an essential component of a wide range of real-world applications (Szegedy et al., 2015; Graves, 2013; Wang et al., 2021; Dong et al., 2022). Because of the increasing spread, confidence in neural network predictions became increasingly important. However, basic neural networks do not provide certainty estimates and suffer from over-confidence or under-confidence, indicating poor calibration. For instance, given several cat breeds images as training data to train a neural network, the model should return a prediction with relatively high confidence when a test sample is a similar cat breed image. However, when the test sample is a dog image, is the neural network able to recognize the test sample coming from a different data distribution (_out of distribution_ test data) (Gal and Ghahramani, 2016; Wang et al., 2022)? Ideally, we hope the neural networks can say "I do not know" when the test sample is an out-of-distribution sample. Unfortunately, the answer is "NO" because the model was trained with images of different kinds of cats and has hopefully learned to recognize them. But the model has never seen a dog before, and an image of a dog would be outside of the data distribution the model was trained on. Even more critically, in high-risk fields, such as medical image analysis with a diagnostics system that has never been observed before or scenes that a self-driving system has never been trained to handle (Kendall and Gal, 2017).

A possible desired behavior of a model in such cases would be to return a prediction with the additional information that the test sample lies outside the data distribution. In other words, we hope our model can quantity a high level of uncertainty (alternatively, low confidence) with such out-of-distribution inputs. In addition to the out-of-distribution
situation, other scenarios may lead to uncertainty. One scenario is noisy data, such as the label noise due to the measurement imprecision (Kendall and Gal, 2017) causes aleatoric uncertainty and conflicting evidence due to dissonance uncertainty (Josang et al., 2018). Another scenario is the uncertainty in model parameters that best explain the observed (training) data (Gal and Ghahramani, 2015).

Many researchers have been working on understanding and quantifying uncertainty in a neural network's prediction to overcome over or under-confidence prediction issues. As a result, different types and sources of uncertainty have been identified, and various approaches to measure and quantify uncertainty in neural networks have been proposed (Guo et al., 2022). Predictive uncertainty quantification in the deep learning research domain has been mainly explored based on two uncertainty types: aleatoric and epistemic uncertainty. Aleatoric uncertainty refers to inherent ambiguity in outputs for a given input and cannot be reduced due to randomness in the data. Aleatoric uncertainty can be estimated by probabilistic neural networks, such as mixture density networks (MacKay and Gibbs, 1999). Epistemic uncertainty indicates uncertainty about the model parameters estimated based on the training data. This uncertainty measures how well the model is matched to the data and can be reduced through the collection of additional data. Epistemic uncertainty can be estimated based on Bayesian neural networks (BNNs) that can learn a posterior distribution over parameters. The accuracy of uncertainty estimation depends on the choice of the prior distribution and the accuracy of the approximate posterior distribution, as the exact posterior is often infeasible to compute. Recent developments of approximate Bayesian approaches include \(L\) Laplace approximation (MacKay, 1992), variational inference (Graves, 2011), dropout-based variational inference (Gal and Ghahramani, 2016), expectation propagation (Hernandez-Lobato and Adams, 2015) and stochastic gradient Markov chain Monte Carlo (MCMC) (Welling and Teh, 2011).

In the belief (or evidence) theory domain, uncertainty reasoning has been substantially explored, such as Fuzzy Logic (De Silva, 2018), Dempster-Shafer Theory (DST) (Sentz et al.,
2002), or Subjective Logic (SL) (Josang, 2016). Belief theory focuses on reasoning inherent uncertainty in information caused by unreliable, incomplete, deceptive, or conflicting evidence. SL considered predictive uncertainty in subjective opinions in terms of _vacuity_ (i.e., a lack of evidence) (Zhao et al., 2018; Xu et al., 2021; Alim et al., 2019) and _vagueness_ (i.e., failing in discriminating a belief state) (Josang, 2016). Recently, other uncertainty types have been studied, such as _dissonance_ caused by conflicting evidence(Josang et al., 2018; Zhao et al., 2019; Shi et al., 2020).

However, inherent uncertainties derived from different root causes have been realized as serious hurdles for DNNs to find robust and trustworthy solutions for real-world problems. A lack of consideration of such uncertainties may lead to unnecessary risk. For example, a self-driving autonomous car can misdetect a human on the road. A deep learning-based medical assistant may misdiagnose cancer as a benign tumor. In this work, we study how to measure different uncertainty causes for DNNs and use them to solve diverse decision-making problems more effectively.

(1) _Uncertainty-aware semi-supervised learning on graph data_. We study the multidimensional uncertainty quantification for graph neural networks(GNNs) (Kipf and Welling, 2017; Velickovic et al., 2018), which have received tremendous attention in the data science community. Despite their superior performance in semi-supervised node classification and regression, they did not consider various uncertainties in their decision process. Although many methods (Zhao et al., 2018; Liu et al., 2020; Zhang et al., 2018; Zhao et al., 2018) have been proposed to estimate uncertainty for GNNs, no prior work has considered uncertainty decomposition in GNNs. To address the challenge of uncertainty decomposition in GNNs, we propose the research question: _can we quantify multidimensional uncertainty types in both deep learning and belief and evidence theory domains for node-level classification, misclassification detection, and out-of-distribution detection tasks on graph data?_

(2) _Uncertainty-aware robust semi-supervised learning_. Recent Semi-supervised learning works show significant improvement in semi-supervised learning algorithms' performance
using better-unlabeled data representations. However, recent work (Oliver et al., 2018) shows that the SSL algorithm's performance could degrade when the unlabeled set has out-of-distribution examples. To address the challenge of out-of-distribution issues in semi-supervised learning, we first propose the research questions: _How out-of-distribution data hurt semi-supervised learning performance?_ and _Can we develop an efficient and effective uncertainty-based approach for robust semi-supervised learning with out of distribution data?_

(3) _Uncertainty-aware early event detection with multi-labels_. Early event detection aims to detect event even before the event is complete. To achieve the earliness of event detection, existing approaches can be broadly divided into several major categories. Prefix-based techniques (Gupta et al., 2020, 2020, 2019, 2019) aim to learn a minimum prefix length of the time series using the training instances and utilize it to classify a testing time series. Shapelet-based approaches (Yan et al., 2020; Zhao et al., 2019; Yao et al., 2019) focus on obtaining a set of key shapelets from the training dataset and utilizing them as class discriminatory features. Model-based methods for event early detection (Mori et al., 2019; Lv et al., 2019) are proposed to obtain conditional probabilities by either fitting a discriminative classifier or using generative classifiers on training. Although these approaches address the importance of early detection, they primarily focus on an event with a single label but fail to be applied to cases with multiple labels. Another non-negligible issue for early event detection is a prediction with overconfidence (Zhao et al., 2020; Sensoy et al., 2018) due to high vacuity uncertainty exists in the early time series, which refers to a lack of evidence. It results in an over-confidence estimation and hence unreliable predictions. To address the aforementioned issues, we propose the research questions: _How to quantify the uncertainty for multi-label time series classification?_ and _How to make a reliable prediction for early event detection?_

In this dissertation, we aim to solve the challenges mentioned above. Therefore, a general question we want to ask is: How can we design effective and efficient uncertainty methods for deep neural networks under different problem settings?
### Summary of Main Contributions

To answer the above question, we propose a novel approach for each challenge by studying an effective and efficient algorithm that is followed by a detailed theoretic analysis. The main contributions are list out as follows.

(1) _Semi-supervised learning on graph data_. We proposed a multi-source uncertainty framework for GNNs. The proposed framework first provides the estimation of various types of uncertainty from both deep learning and evidence/belief theory domains, such as dissonance (derived from conflicting evidence) and vacuity (derived from lack of evidence). In addition, we designed a Graph-based Kernel Dirichlet distribution Estimation (GKDE) method to reduce errors in quantifying predictive uncertainties. Furthermore, we first provided a theoretical analysis of the relationships between different types of uncertainties considered in this work. We demonstrate via a theoretical analysis that an OOD node may have a high predictive uncertainty under GKDE. Based on the six real graph datasets, we compared the performance of our proposed framework with that of other competitive counterparts. We found that dissonance-based detection yielded the best results in misclassification detection, while vacuity-based detection performed best in OOD detection. The main results are from (Zhao et al., 2020)

(2) _Semi-supervised learning with OODs setting_. To answer the question of "_How out-of-distribution data hurt semi-supervised learning performance?_", we first study the critical causes of OOD's negative impact on SSL algorithms. In particular, we found that 1) certain kinds of OOD data instances close to the decision boundary have a more significant impact on performance than those far away, and 2) Batch Normalization (BN), a popular module, could degrade the performance instead of improving the performance when the unlabeled set contains OODs. To address the above causes, we proposed a novel unified weighted robust SSL framework that can be easily extended to many existing SSL algorithms and improve their robustness against OODs. To address the limitation of low-order approximations in
bi-level optimization, we developed an efficient hyper-parameter optimization algorithm that considers high-order approximations of the objective and is scalable to a higher number of inner optimization steps to learn a massive amount of weight parameters. In addition, we conduct a theoretical analysis of the impact of faraway OODs in the BN step and propose weighted batch normalization (WBN) to carry the weights over in the BN step. We also discuss the connection between our approach and low-order approximation approaches. Finally, we address a critical issue of the existing bi-level optimization-based reweighting schemes, which is that they are much slower (close to 3\(\times\)) compared to the original learning (SSL) algorithms - we show that several simple tricks like just considering the last layer in the inner loop and doing the weight updates every few epochs enable us to have a run-time comparable to the base SSL while maintaining the accuracy gains of reweighting. Extensive experiments on synthetic and real-world datasets prove that our proposed approach significantly improves the robustness of four representative SSL algorithms against OODs compared with four state-of-the-art robust SSL approaches. The main content is from (Zhao et al., 2020).

(3) _Early event detection with multi-label setting_. We first introduce a novel problem, namely _early event detection with multiple labels_. A temporal event with multiple labels that occurs sequentially along the timeline is considered in this problem setting. This work aims to accurately detect all classes at the ongoing stage of an event within the least amount of time. To this end, technically, we propose a novel framework, Multi-Label Temporal Evidential Neural Network (MTENN), for early event detection in temporal data. MTENN is able to quality predictive uncertainty due to the lack of evidence for multi-label classifications at each time stamp based on belief/evidence theory. In addition, we introduce two novel uncertainty estimation heads (weighted binomial comultiplication (WBC) and uncertainty mena scan statistics(UMSS)) to quantify the fused uncertainty of a sub-sequence for early event detection. We demonstrate that WBC is effective for detection accuracy and
UMSS is effective for detection delay. We validate the performance of our approach with state-of-the-art techniques on real-world audio and video datasets. Theoretic analysis and empirical studies demonstrate the effectiveness and efficiency of the proposed framework in both detection delay and accuracy. The results have been accepted in (Zhao et al., 2022).

### Outline

The rest of the dissertation is organized as follows. In Chapter 2, We present our first research on multidimensional uncertainty quantification for GNNs. In Chapter 3, we study an uncertainty-based robust semi-supervised learning framework via bi-level optimization. In Chapter 4, we further quantify the multi-label uncertainty and sequential uncertainty for early event detection. We finally conclude the dissertation in Chapter 5.
## Chapter 2 Uncertainty Aware Semi-Supervised Learning on Graph Data

### 2.1 Introduction

Inherent uncertainties derived from different root causes have realized as serious hurdles to find effective solutions for real-world problems. Critical safety concerns have been brought due to lack of considering diverse causes of uncertainties, resulting in high risk due to misinterpretation of uncertainties (e.g., misdetection or misclassification of an object by an autonomous vehicle). Graph neural networks (GNNs) (Kipf and Welling, 2017; Velickovic et al., 2018) have received tremendous attention in the data science community. Despite their superior performance in semi-supervised node classification and regression, they didn't consider various types of uncertainties in the their decision process. Predictive uncertainty estimation (Kendall and Gal, 2017) using Bayesian NNs (BNNs) has been explored for classification prediction and regression in the computer vision applications, based on aleatoric uncertainty (AU) and epistemic uncertainty (EU). AU refers to data uncertainty from statistical randomness (e.g., inherent noises in observations) while EU indicates model uncertainty due to limited knowledge (e.g., ignorance) in collected data. In the belief or evidence theory domain, Subjective Logic (SL) (Josang et al., 2018) considered vacuity (or a lack of evidence or ignorance) as uncertainty in a subjective opinion. Recently other uncertainty types, such as dissonance, consonance, vagueness, and monosonance (Josang et al., 2018), have been discussed based on SL to measure them based on their different root causes.

We first considered multidimensional uncertainty types in both deep learning (DL) and belief and evidence theory domains for node-level classification, misclassification detection,
and out-of-distribution (OOD) detection tasks. By leveraging the learning capability of GNNs and considering multidimensional uncertainties, we propose an uncertainty-aware estimation framework by quantifying different uncertainty types associated with the predicted class probabilities. In this work, we made the following **key contributions**:

* **A multi-source uncertainty framework for GNNs**. Our proposed framework first provides the estimation of various types of uncertainty from both DL and evidence/belief theory domains, such as dissonance (derived from conflicting evidence) and vacuity (derived from lack of evidence). In addition, we designed a Graph-based Kernel Dirichlet distribution Estimation (GKDE) method to reduce errors in quantifying predictive uncertainties.
* **Theoretical analysis**: Our work is the first that provides a theoretical analysis about the relationships between different types of uncertainties considered in this work. We demonstrate via a theoretical analysis that an OOD node may have a high predictive uncertainty under GKDE.
* **Comprehensive experiments for validating the performance of our proposed framework**: Based on the six real graph datasets, we compared the performance of our proposed framework with that of other competitive counterparts. We found that dissonance-based detection yielded the best results in misclassification detection while vacuity-based detection best performed in OOD detection.

Note that we use the term 'predictive uncertainty' in order to mean uncertainty estimated to solve prediction problems.

### Related Work

DL research has mainly considered _aleatoric_ uncertainty (AU) and _epistemic_ uncertainty (EU) using BNNs for computer vision applications. AU consists of homoscedastic uncer
tainty (i.e., constant errors for different inputs) and heteroscedastic uncertainty (i.e., different errors for different inputs) (Gal, 2016). A Bayesian DL framework was presented to simultaneously estimate both AU and EU in regression (e.g., depth regression) and classification (e.g., semantic segmentation) tasks (Kendall and Gal, 2017). Later, _distributional uncertainty_ was defined based on distributional mismatch between testing and training data distributions (Malinin and Gales, 2018). _Dropout variational inference_(Gal and Ghahramani, 2016) was used for approximate inference in BNNs using epistemic uncertainty, similar to _DropEdge_(Rong et al., 2019). Other algorithms have considered overall uncertainty in node classification (Eswaran et al., 2017; Liu et al., 2020; Zhang et al., 2019). However, no prior work has considered uncertainty decomposition in GNNs.

In the belief (or evidence) theory domain, uncertainty reasoning has been substantially explored, such as Fuzzy Logic (De Silva, 2018), Dempster-Shafer Theory (DST) (Sentz et al., 2002), or Subjective Logic (SL) (Josang, 2016). Belief theory focuses on reasoning inherent uncertainty in information caused by unreliable, incomplete, deceptive, or conflicting evidence. SL considered predictive uncertainty in subjective opinions in terms of _vacuity_ (i.e., a lack of evidence) and _vagueness_ (i.e., failing in discriminating a belief state) (Josang, 2016). Recently, other uncertainty types have been studied, such as _dissonance_ caused by conflicting evidence(Josang et al., 2018). In the deep NNs, (Sensoy et al., 2018) proposed evidential deep learning (EDL) model, using SL to train a deterministic NN for supervised classification in computer vision based on the sum of squared loss. However, EDL didn't consider a general method of estimating multidimensional uncertainty or graph structure.

### Multidimensional Uncertainty and Subjective Logic

This section provides an overview of SL and discusses multiple types of uncertainties estimated based on SL, called _evidential uncertainty_, with the measures of _vacuity_ and _dis
sonance_. In addition, we give a brief overview of _probabilistic uncertainty_, discussing the measures of _aleatoric_ uncertainty and _epistemic_ uncertainty.

#### Notations

Vectors are denoted by lower case bold face letters, _e.g._, belief vector \(\mathbf{b}\in[0,1]^{K}\) and class probability \(\mathbf{p}\in[0,1]^{K}\) where their \(i\)-th entries are \(b_{i},p_{i}\). Scalars are denoted by lowercase italic letters, _e.g._\(u\in[0,1]\). Matrices are denoted by capital italic letters. \(\omega\) denotes the subjective opinion. Some important notations are listed in Table 2.1

\begin{table}
\begin{tabular}{l|l} \hline \hline
**Notations** & **Descriptions** \\ \hline \(\mathcal{G}\) & Graph dataset \\ \(\mathbb{V}\) & A ground set of nodes \\ \(\mathbb{L}\) & Training nodes \\ \(\mathbb{E}\) & A ground set of edges \\ \(\mathbf{R}\) & Node-level feature matrix \\ \(y_{i}\) & Class label of node \(i\) \\ \(\mathbf{p}_{i}\) & Class probability of node \(i\) \\ \(\mathbf{\theta}\) & model parameters \\ \(\omega\) & Subjective opinion \\ \(\mathbf{b}\) & Belief mass distribution \\ \(\mathbf{\alpha}\) & Dirichlet distribution parameters \\ \(u\) & Vacuity uncertainty \\ \(K\) & Number of classes \\ \(S\) & Dirichlet strength (summation of \(\mathbf{\alpha}\)) \\ \(\mathbf{e}\) & Evidence vector \\ \(diss(\omega)\) & Dissonance uncertainty based on opinion \(\omega\) \\ \(I(\cdot)\) & Mutual information \\ \(H(\cdot)\) & Entropy function \\ \(f(\cdot)\) & GNNs model function \\ \hline \hline \end{tabular}
\end{table}
Table 2.1: Important notations and corresponding descriptions.
#### 2.3.2 Subjective Logic

A multinomial opinion of a random variable \(y\) is represented by \(\omega=(\mathbf{b},u,\mathbf{a})\) where a domain is \(\mathbb{Y}\equiv\{1,\cdots,K\}\) and the additivity requirement of \(\omega\) is given as \(\sum_{k\in\mathbb{Y}}b_{k}+u=1\). To be specific, each parameter indicates,

* \(\mathbf{b}\): _belief mass distribution_ over \(\mathbb{Y}\) and \(\mathbf{b}=[b_{1},\ldots,b_{K}]^{T}\);
* \(u\): _uncertainty mass_ representing _vacuity of evidence_;
* \(\mathbf{a}\): _base rate distribution_ over \(\mathbb{Y}\) and \(\mathbf{a}=[a_{1},\ldots,a_{K}]^{T}\).

The projected probability distribution of a multinomial opinion can be calculated as:

\[P(y=k)=b_{k}+a_{k}u,\;\;\;\forall k\in\mathbb{Y}. \tag{2.1}\]

A multinomial opinion \(\omega\) defined above can be equivalently represented by a \(K\)-dimensional Dirichlet probability density function (PDF), where the special case with \(K=2\) is the Beta PDF as a binomial opinion. Let \(\mathbf{\alpha}\) be a strength vector over the singletons (or classes) in \(\mathbb{Y}\) and \(\mathbf{p}=[p_{1},\cdots,p_{K}]^{T}\) be a probability distribution over \(\mathbb{Y}\). The Dirichlet PDF with \(\mathbf{p}\) as a random vector \(K\)-dimensional variables is defined by:

\[\text{Dir}(\mathbf{p}|\mathbf{\alpha})=\frac{1}{B(\mathbf{\alpha})}\prod\nolimits_{k\in \mathbb{Y}}p_{k}^{(\alpha_{k}-1)}, \tag{2.2}\]

where \(\frac{1}{B(\mathbf{\alpha})}=\frac{\Gamma(\sum_{k\in\mathbb{Y}}\alpha_{k})}{\prod _{k\in\mathbb{Y}}(\alpha_{k})}\), \(\alpha_{k}\geq 0\), and \(p_{k}\neq 0\), if \(\alpha_{k}<1\).

The term _evidence_ is introduced as a measure of the amount of supporting observations collected from data that a sample should be classified into a certain class. Let \(e_{k}\) be the evidence derived for the class \(k\in\mathbb{Y}\). The total strength \(\alpha_{k}\) for the belief of each class \(k\in\mathbb{Y}\) can be calculated as: \(\alpha_{k}=e_{k}+a_{k}W\), where \(e_{k}\geq 0,\forall k\in\mathbb{Y}\), and \(W\) refers to a non-informative weight representing the amount of uncertain evidence. Given the Dirichlet PDF as defined above, the expected probability distribution over \(\mathbb{Y}\) can be calculated as:

\[\mathbb{E}[p_{k}]=\frac{\alpha_{k}}{\sum_{k=1}^{K}\alpha_{k}}=\frac{e_{k}+a_{k }W}{W+\sum_{k=1}^{K}e_{k}}. \tag{2.3}\]
The observed evidence in a Dirichlet PDF can be mapped to a multinomial opinion as follows:

\[b_{k}=\frac{e_{k}}{S},\ u=\frac{W}{S}, \tag{2.4}\]

where \(S=\sum_{k=1}^{K}\alpha_{k}\) refers to the Dirichlet strength. Without loss of generality, we set \(a_{k}=\frac{1}{K}\) and the non-informative prior weight (i.e., \(W=K\)), which indicates that \(a_{k}\cdot W=1\) for each \(k\in\mathbb{Y}\).

#### 2.3.3 Evidential Uncertainty

In (Josang et al., 2018), we discussed a number of multidimensional uncertainty dimensions of a subjective opinion based on the formalism of SL, such as singularity, vagueness, vacuity, dissonance, consonance, and monosonance. These uncertainty dimensions can be observed from binomial, multinomial, or hyper opinions depending on their characteristics (e.g., the vagueness uncertainty is only observed in hyper opinions to deal with composite beliefs). In this work, we discuss two main uncertainty types that can be estimated in a multinomial opinion, which are _vacuity_ and _dissonance_.

The main cause of vacuity is derived from a lack of evidence or knowledge, which corresponds to the uncertainty mass, \(u\), of a multinomial opinion in SL as: \(vac(\omega)\equiv u=K/S\), as estimated in Eq. (2.4). This uncertainty exists because the analyst may have insufficient information or knowledge to analyze the uncertainty. The _dissonance_ of a multinomial opinion can be derived from the same amount of conflicting evidence and can be estimated based on the difference between singleton belief masses (e.g., class labels), which leads to 'inconclusiveness' in decision-making applications. For example, a four-state multinomial opinion is given as \((b_{1},b_{2},b_{3},b_{4},u,a)=(0.25,0.25,0.25,0.25,0.0,a)\) based on Eq. (2.4), although the vacuity \(u\) is zero, a decision can not be made if there are the same amounts of beliefs supporting respective beliefs. Given a multinomial opinion with non-zero belief masses, the measure of
dissonance can be calculated as:

\[diss(\omega)=\sum_{i=1}^{K}\Big{(}\frac{b_{i}\sum_{j\neq i}b_{j}\text{ Bal}(b_{j},b_{i})}{\sum_{j\neq i}b_{j}}\Big{)}, \tag{2.5}\]

where the relative mass balance between a pair of belief masses \(b_{j}\) and \(b_{i}\) is defined as \(\text{Bal}(b_{j},b_{i})=1-|b_{j}-b_{i}|/(b_{j}+b_{i})\). We note that the dissonance is measured only when the belief mass is non-zero. If all belief masses equal to zero with vacuity being 1 (i.e., \(u=1\)), the dissonance will be set to zero.

#### 2.3.4 Probabilistic Uncertainty

For classification, the estimation of the probabilistic uncertainty relies on the design of an appropriate Bayesian DL model with parameters \(\mathbf{\theta}\). Given input \(x\) and dataset \(\mathcal{G}\), we estimate a class probability by \(P(y|x)=\int P(y|x;\mathbf{\theta})P(\mathbf{\theta}|\mathcal{G})d\mathbf{\theta}\), and obtain _epistemic uncertainty_ estimated by mutual information (Depeweg et al., 2018; Malinin and Gales, 2018):

\[\underbrace{I(y,\mathbf{\theta}|x,\mathcal{G})}_{\mathbf{Epistemic}}=\underbrace{ \mathcal{H}\big{[}\mathbb{E}_{P(\mathbf{\theta}|\mathcal{G})}[P(y|x;\mathbf{\theta}) ]\big{]}}_{\mathbf{Entropy}}-\underbrace{\mathbb{E}_{P(\mathbf{\theta}|\mathcal{G})} \big{[}\mathcal{H}[P(y|x;\mathbf{\theta})]\big{]}}_{\mathbf{Aleatoric}}, \tag{2.6}\]

where \(\mathcal{H}(\cdot)\) is Shannon's entropy of a probability distribution. The first term indicates _entropy_ that represents the total uncertainty while the second term is _aleatoric_ that indicates data uncertainty. By computing the difference between entropy and aleatoric uncertainties, we obtain epistemic uncertainty, which refers to uncertainty from model parameters.

### Relationships Between Multiple Uncertainties

We use the shorthand notations \(u_{v}\), \(u_{diss}\), \(u_{alea}\), \(u_{epis}\), and \(u_{en}\) to represent vacuity, dissonance, aleatoric, epistemic, and entropy, respectively.

To interpret multiple types of uncertainty, we show three prediction scenarios of 3-class classification in Figure 2.1, in each of which the strength parameters \(\alpha=[\alpha_{1},\alpha_{2},\alpha_{3}]\) are known. To make a prediction with high confidence, the subjective multinomial opinion,
following a Dirichlet distribution, will yield a sharp distribution on one corner of the simplex (see Figure 2.1 (a)). For a prediction with conflicting evidence, called a conflicting prediction (CP), the multinomial opinion should yield a central distribution, representing confidence to predict a flat categorical distribution over class labels (see Figure 2.1 (b)). For an OOD scenario with \(\alpha=[1,1,1]\), the multinomial opinion would yield a flat distribution over the simplex (Figure 2.1 (c)), indicating high uncertainty due to the lack of evidence. The first technical contribution of this work is as follows.

**Theorem 1**.: _We consider a simplified scenario, where a multinomial random variable \(y\) follows a K-class categorical distribution: \(y\sim\text{Cal}(\textbf{p})\), the class probabilities **p** follow a Dirichlet distribution: \(\textbf{p}\sim\text{Dir}(\boldsymbol{\alpha})\), and \(\boldsymbol{\alpha}\) refer to the Dirichlet parameters. Given a total Dirichlet strength \(S=\sum_{i=1}^{K}\alpha_{i}\), for any opinion \(\omega\) on a multinomial random variable \(y\), we have_

1. _General relations on all prediction scenarios._ _(a)_ \(u_{v}+u_{diss}\leq 1\)_; (b)_ \(u_{v}>u_{epis}\)_._

Figure 2.1: Multiple uncertainties of different predictions. Let \(\textbf{u}=[u_{v},u_{diss},u_{alea},u_{epis},u_{en}]\).
2. _Special relations on the OOD and the CP._ 1. _For an OOD sample with a uniform prediction (i.e.,_ \(\alpha=[1,\ldots,1]\)_), we have_ \[1=u_{v}=u_{en}>u_{alea}>u_{epis}>u_{diss}=0\] 2. _For an in-distribution sample with a conflicting prediction (i.e.,_ \(\alpha=[\alpha_{1},\ldots,\alpha_{K}]\) _with_ \(\alpha_{1}=\alpha_{2}=\cdots=\alpha_{K}\)_, if_ \(S\rightarrow\infty\)_), we have_ \[u_{en}=1,\lim_{S\rightarrow\infty}u_{diss}=\lim_{S\rightarrow\infty}u_{alea}=1,\lim_{S\rightarrow\infty}u_{v}=\lim_{S\rightarrow\infty}u_{epis}=0\] _with_ \(u_{en}>u_{alea}>u_{diss}>u_{v}>u_{epis}\)_._

The proof of Theorem 1 can be found in Appendix A.1. As demonstrated in Theorem 1 and Figure 2.1, entropy cannot distinguish OOD (see Figure 2.1 (c)) and conflicting predictions (see Figure 2.1 (b)) because entropy is high for both cases. Similarly, neither aleatoric uncertainty nor epistemic uncertainty can distinguish OOD from conflicting predictions. In both cases, aleatoric uncertainty is high while epistemic uncertainty is low. On the other hand, vacuity and dissonance can clearly distinguish OOD from a conflicting prediction. For example, OOD objects typically show high vacuity with low dissonance while conflicting predictions exhibit low vacuity with high dissonance. This observation is confirmed through the empirical validation via our extensive experiments in terms of misclassification and OOD detection tasks.

### Uncertainty-Aware Semi-Supervised Learning

In this section, we describe our proposed uncertainty framework based on semi-supervised node classification problem. It is designed to predict the subjective opinions about the classification of testing nodes, such that a variety of uncertainty types, such as vacuity,
dissonance, aleatoric uncertainty, and epistemic uncertainty, can be quantified based on the estimated subjective opinions and posterior of model parameters. As a subjective opinion can be equivalently represented by a Dirichlet distribution about the class probabilities, we proposed a way to predict the node-level subjective opinions in the form of node-level Dirichlet distributions. The overall description of the framework is shown in Figure 2.2.

#### Problem Definition

Given an input graph \(\mathcal{G}=(\mathbb{V},\mathbb{E},\mathbf{r},\mathbf{y}_{\mathbb{L}})\), where \(\mathbb{V}=\{1,\ldots,N\}\) is a ground set of nodes, \(\mathbb{E}\subseteq\mathbb{V}\times\mathbb{V}\) is a ground set of edges, \(\mathbf{r}=[\mathbf{r}_{1},\cdots,\mathbf{r}_{N}]^{T}\in\mathbb{R}^{N\times d}\) is a node-level feature matrix, \(\mathbf{r}_{i}\in\mathbb{R}^{d}\) is the feature vector of node \(i\), \(\mathbf{y}_{\mathbb{L}}=\{y_{i}\mid i\in\mathbb{L}\}\) are the labels of the training nodes \(\mathbb{L}\subset\mathbb{V}\), and \(y_{i}\in\{1,\ldots,K\}\) is the class label of node \(i\). **We aim to predict**: (1) the **class probabilities** of the testing nodes: \(\mathbf{p}_{\mathbb{V}\setminus\mathbb{L}}=\{\mathbf{p}_{i}\in[0,1]^{K}\mid i \in\mathbb{V}\setminus\mathbb{L}\}\); and (2) the **associated multidimensional uncertainty estimates** introduced by different root causes: \(\mathbf{u}_{\mathbb{V}\setminus\mathbb{L}}=\{\mathbf{u}_{i}\in[0,1]^{m}\mid i \in\mathbb{V}\setminus\mathbb{L}\}\), where \(p_{i,k}\) is the probability that the class label \(y_{i}=k\) and \(m\) is the total number of uncertainty types.

Figure 2.2: Uncertainty Framework Overview. Subjective Bayesian GNN (a) is designed for estimating the different types of uncertainties. The loss function includes a square error (d) to reduce bias, GKDE (b) to reduce errors in uncertainty estimation, and teacher network (c) to refine class probability.
#### 2.5.2 Proposed Uncertainty Framework

**Learning evidential uncertainty.** As discussed in Section 2.3.2, evidential uncertainty can be derived from multinomial opinions or equivalently Dirichlet distributions to model a probability distribution for the class probabilities. Therefore, we design a Subjective GNN (S-GNN) \(f\) to form their multinomial opinions for the node-level Dirichlet distribution \(\text{Dir}(\mathbf{p}_{i}|\boldsymbol{\alpha}_{i})\) of a given node \(i\). Then, the conditional probability \(P(\mathbf{p}|A,\mathbf{r};\boldsymbol{\theta})\) can be obtained by:

\[P(\mathbf{p}|A,\mathbf{r};\boldsymbol{\theta})=\prod\nolimits_{i=1}^{N}\text{ Dir}(\mathbf{p}_{i}|\boldsymbol{\alpha}_{i}),\ \boldsymbol{\alpha}_{i}=f_{i}(A,\mathbf{r};\boldsymbol{\theta}), \tag{2.7}\]

where \(f_{i}\) is the output of S-GNN for node \(i\), \(\boldsymbol{\theta}\) is the model parameters, and \(A\) is an adjacency matrix. The Dirichlet probability function \(\text{Dir}(\mathbf{p}_{i}|\boldsymbol{\alpha}_{i})\) is defined by Eq. (2.2).

Note that S-GNN is similar to classical GNN, except that we use an activation layer (e.g., \(ReLU\)) instead of the _softmax_ layer (only outputs class probabilities). This ensures that S-GNN would output non-negative values, which are taken as the parameters for the predicted Dirichlet distribution.

**Learning probabilistic uncertainty.** Since probabilistic uncertainty relies on a Bayesian framework, we proposed a Subjective Bayesian GNN (S-BGNN) that adapts S-GNN to a Bayesian framework, with the model parameters \(\boldsymbol{\theta}\) following a prior distribution. The joint class probability of \(\mathbf{y}\) can be estimated by:

\[P(\mathbf{y}|A,\mathbf{r};\mathcal{G}) = \int\int P(\mathbf{y}|\mathbf{p})P(\mathbf{p}|A,\mathbf{r}; \boldsymbol{\theta})P(\boldsymbol{\theta}|\mathcal{G})d\mathbf{p}d\boldsymbol{\theta} \tag{2.8}\] \[\approx \frac{1}{M}\sum_{m=1}^{M}\sum_{i=1}^{N}\int P(\mathbf{y}_{i}| \mathbf{p}_{i})P(\mathbf{p}_{i}|A,\mathbf{r};\boldsymbol{\theta}^{(m)})d \mathbf{p}_{i},\quad\boldsymbol{\theta}^{(m)}\sim q(\boldsymbol{\theta})\]

where \(P(\boldsymbol{\theta}|\mathcal{G})\) is the posterior, estimated via dropout inference, that provides an approximate solution of posterior \(q(\boldsymbol{\theta})\) and taking samples from the posterior distribution of models (Gal and Ghahramani, 2016). Thanks to the benefit of dropout inference, training a DL model
directly by minimizing the cross entropy (or square error) loss function can effectively minimize the KL-divergence between the approximated distribution and the full posterior (i.e., \(\text{KL}[q(\mathbf{\theta})\|P(\theta|\mathcal{G})]\)) in variational inference (Gal and Ghahramani, 2016; Kendall et al., 2015). For interested readers, please refer to more detail in Appendix B.8.

Therefore, training S-GNN with stochastic gradient descent enables learning of an approximated distribution of weights, which can provide good explainability of data and prevent overfitting. We use a _loss function_ to compute its Bayes risk with respect to the sum of squares loss \(\|\mathbf{y}-\mathbf{p}\|_{2}^{2}\) by:

\[\mathcal{L}(\mathbf{\theta}) = \sum\nolimits_{i\in\mathbb{L}}\int\|\mathbf{y}_{i}-\mathbf{p}_{i }\|_{2}^{2}\cdot P(\mathbf{p}_{i}|A,\mathbf{r};\mathbf{\theta})d\mathbf{p}_{i} \tag{2.9}\] \[= \sum\nolimits_{i\in\mathbb{L}}\sum\nolimits_{k=1}^{K}\big{(}y_{ ik}-\mathbb{E}[p_{ik}]\big{)}^{2}+\text{Var}(p_{ik}),\]

where \(\mathbf{y}_{i}\) is an one-hot vector encoding the ground-truth class with \(y_{ij}=1\) and \(y_{ik}\neq\) for all \(k\neq j\) and \(j\) is a class label. Eq. (2.9) aims to minimize the prediction error and variance, leading to maximizing the classification accuracy of each training node by removing excessive misleading evidence.

#### Graph-based Kernel Dirichlet distribution Estimation (GKDE)

The loss function in Eq. (2.9) is designed to measure the sum of squared loss based on class labels of training nodes. However, it does not directly measure the quality of the predicted node-level Dirichlet distributions (Zhao et al., 2019; 1). To address this limitation, we proposed _Graph-based Kernel Dirichlet distribution Estimation_ (GKDE) to better estimate node-level Dirichlet distributions by using graph structure information. The key idea of the GKDE is to estimate prior Dirichlet distribution parameters for each node based on the class labels of training nodes (see Figure 2.3). Then, we use the estimated prior Dirichlet distribution in the training process to learn the following patterns: (i) nodes with a high
cavity will be shown far from training nodes; and (ii) nodes with a high dissonance will be shown near the boundaries of classes.

Based on SL, let each training node represent one evidence for its class label. Denote the contribution of evidence estimation for node \(j\) from training node \(i\) by \(\mathbf{h}(y_{i},d_{ij})=[h_{1},\ldots,h_{k},\ldots,h_{K}]\in[0,1]^{K}\), where \(h_{k}(y_{i},d_{ij})\) is obtained by:

\[h_{k}(y_{i},d_{ij})=\begin{cases}0&y_{i}\neq k\\ g(d_{ij})&y_{i}=k,\end{cases} \tag{2.10}\]

\(g(d_{ij})=\frac{1}{\sigma\sqrt{2\pi}}\exp(-\frac{d_{ij}^{2}}{2\sigma^{2}})\) is the Gaussian kernel function used to estimate the distribution effect between nodes \(i\) and \(j\), and \(d_{ij}\) means the **node-level distance** (**the shortest path between nodes \(i\) and \(j\)**), and \(\sigma\) is the bandwidth parameter. The prior evidence is estimated based GKDE: \(\hat{\mathbf{e}}_{j}=\sum_{i\in\mathbb{L}}\mathbf{h}(y_{i},d_{ij})\), where \(\mathbb{L}\) is a set of training nodes and the prior Dirichlet distribution \(\hat{\mathbf{\alpha}}_{j}=\hat{\mathbf{e}}_{j}+\mathbf{1}\). During the training process, we minimize the KL-divergence between model predictions of Dirichlet distribution and prior distribution: \(\min\text{KL}[\text{Dir}(\mathbf{\alpha})\|\text{Dir}(\hat{\mathbf{\alpha}})]\). This process can prioritize the extent of data relevance based on the estimated evidential uncertainty, which is proven effective based on the proposition below.

Figure 2.3: Illustration of GKDE. Estimate prior Dirichlet distribution \(\text{Dir}(\hat{\alpha})\) for node \(j\) (red) based on training nodes (blue) and graph structure information.
**Proposition 1**.: _Given \(L\) training nodes, for any testing nodes \(i\) and \(j\), let \(\mathbf{d}_{i}=[d_{i1},\ldots,d_{iL}]\) be the vector of graph distances from nodes \(i\) to training nodes and \(\mathbf{d}_{j}=[d_{j1},\ldots,d_{jL}]\) be the graph distances from nodes \(j\) to training nodes, where \(d_{il}\) is the node-level distance between nodes \(i\) and \(l\). If for all \(l\in\{1,\ldots,L\}\), \(d_{il}\geq d_{jl}\), then we have_

\[\hat{u}_{v_{i}}\geq\hat{u}_{v_{j}},\]

_where \(\hat{u}_{v_{i}}\) and \(\hat{u}_{v_{j}}\) refer to vacuity uncertainties of nodes \(i\) and \(j\) estimated based on GKDE._

Proof.: Let \(\mathbf{y}=[y_{1},\ldots,y_{L}]\) be the label vector for training nodes. Based on GKDE, the evidence contribution for the node \(i\) and a training node \(l\in\{1,\ldots,L|\}\) is \(\mathbf{h}(y_{l},d_{il})=[h_{1}(y_{l},d_{il}),\ldots,h_{K}(y_{l},d_{il})]\), where

\[h_{k}(y_{l},d_{il})=\begin{cases}0&y_{l}\neq k\\ g(d_{il})=\frac{1}{\sigma\sqrt{2\pi}}\exp(-\frac{d_{il}{}^{2}}{2\sigma^{2}})&y_ {l}=k\end{cases}, \tag{2.11}\]

and the prior evidence can be estimated based GKDE:

\[\hat{\mathbf{e}}_{i}=\sum_{m=1}^{L}\sum_{k=1}^{K}h_{k}(y_{l},d_{il}), \tag{2.12}\]

where \(\hat{\mathbf{e}}_{i}=[e_{i1},...,e_{iK}]\). Since each training node only contributes the same evidence based on its label based on Eq. (2.11), the total evidence is estimated by all the contributing evidence as

\[\sum_{k=1}^{K}e_{ik}=\sum_{m=1}^{L}\frac{1}{\sigma\sqrt{2\pi}}\exp(-\frac{{d_ {il}}^{2}}{2\sigma^{2}}),\quad\sum_{k=1}^{K}e_{jk}=\sum_{m=1}^{L}\frac{1}{ \sigma\sqrt{2\pi}}\exp(-\frac{{d_{jl}}^{2}}{2\sigma^{2}}), \tag{2.13}\]

where the vacuity values for node \(i\) and node \(j\) based on GKDE are,

\[\hat{u}_{v_{i}}=\frac{K}{\sum_{k=1}^{K}e_{ik}+K},\quad\hat{u}_{v_{j}}=\frac{K} {\sum_{k=1}^{K}e_{jk}+K}. \tag{2.14}\]
Now, we prove Eq. (2.14) above. If \(d_{il}\geq d_{jl}\) for \(\forall l\in\{1,\ldots,L\}\), we have

\[\sum_{k=1}^{K}e_{ik} = \sum_{m=1}^{L}\frac{1}{\sigma\sqrt{2\pi}}\exp(-\frac{{d_{il}}^{2}} {2\sigma^{2}})\] \[\leq \sum_{m=1}^{L}\frac{1}{\sigma\sqrt{2\pi}}\exp(-\frac{{d_{jl}}^{2} }{2\sigma^{2}})\] \[= \sum_{k=1}^{K}e_{jk},\]

such that

\[\hat{u}_{v_{i}}=\frac{K}{\sum_{k=1}^{K}e_{ik}+K}\geq\frac{K}{\sum_{k=1}^{K}e_{ jk}+K}=\hat{u}_{v_{j}}. \tag{2.16}\]

The above proposition shows that if a testing node is too far from training nodes, the vacuity will increase, implying that an OOD node is expected to have a high vacuity.

In addition, we designed a simple iterative knowledge distillation method (Hinton et al., 2015) (i.e., Teacher Network) to refine the node-level classification probabilities. The key idea is to train our proposed model (Student) to imitate the outputs of a pre-train vanilla GNN (Teacher) by adding a regularization term of KL-divergence. This leads to solving the following optimization problem:

\[\min_{\boldsymbol{\theta}}\mathcal{L}(\boldsymbol{\theta})+\lambda_{1}\text{ KL}[\text{Dir}(\boldsymbol{\alpha})\|\text{Dir}(\hat{\boldsymbol{\alpha}})]+ \lambda_{2}\text{KL}[P(\mathbf{y}\mid A,\mathbf{r};\mathcal{G})\ \|\ P(\mathbf{y}|\hat{\mathbf{p}})], \tag{2.17}\]
where \(\hat{\mathbf{p}}\) is the vanilla GNN's (Teacher) output and \(\lambda_{1}\) and \(\lambda_{2}\) are trade-off parameters.

```
Input:\(\mathbb{G}=(\mathbb{V},\mathbb{E},\mathbf{r})\) and \(\mathbf{y}_{\mathbb{L}}\) Output:\(\mathbf{p}_{\mathbb{V}\backslash\mathbb{L}}\), \(\mathbf{u}_{\mathbb{V}\backslash\mathbb{L}}\)
1\(\ell=0\);
2 Set hyper-parameters \(\eta,\lambda_{1},\lambda_{2}\);
3 Initialize the parameters \(\gamma,\beta\);
4 Calculate the prior Dirichlet distribution \(\text{Dir}(\hat{\alpha})\);
5 Pretrain the teacher network to get \(\text{Prob}(\mathbf{y}|\hat{\mathbf{p}})\);
6repeat
7 Forward pass to compute \(\boldsymbol{\alpha}\), \(\text{Prob}(\mathbf{p}_{i}|A,\mathbf{r};\mathcal{G})\) for \(i\in\mathbb{V}\);
8 Compute joint probability \(\text{Prob}(\mathbf{y}|A,\mathbf{r};\mathcal{G})\);
9 Backward pass via the chain-rule the calculate the sub-gradient gradient: \(g^{(\ell)}=\nabla_{\Theta}\mathcal{L}(\Theta)\)
10 Update parameters using step size \(\eta\) via \(\Theta^{(\ell+1)}=\Theta^{(\ell)}-\eta\cdot g^{(\ell)}\)
11\(\ell=\ell+1\);
12
13untilconvergence
14 Calculate \(\mathbf{p}_{\mathbb{V}\backslash\mathbb{L}}\), \(\mathbf{u}_{\mathbb{V}\backslash\mathbb{L}}\) return\(\boldsymbol{p}_{\mathbb{V}\backslash\mathbb{L}}\), \(\boldsymbol{u}_{\mathbb{V}\backslash\mathbb{L}}\)
```

**Algorithm 1**S-BGCN-T-K

### Experiments

In this section, we conduct experiments on the tasks of misclassification and OOD detections to answer the following questions for semi-supervised node classification:

**Q1. Misclassification Detection:** What type of uncertainty is the most promising indicator of high confidence in node classification predictions?
**Q2. OOD Detection:** What type of uncertainty is a key indicator of accurate detection of OOD nodes?

**Q3. GKDE with Uncertainty Estimates:** How can GKDE help enhance prediction tasks with what types of uncertainty estimates?

Through extensive experiments, we found the following answers to the above questions:

**A1.** Dissonance (i.e., uncertainty due to conflicting evidence) is more effective than other uncertainty estimates in misclassification detection.

**A2.** Vacuity (i.e., uncertainty due to lack of confidence) is more effective than other uncertainty estimates in OOD detection.

**A3.** GKDE can indeed help improve the estimation quality of node-level Dirichlet distributions, resulting in a higher OOD detection.

#### Experiment Setup

**Datasets**: We used six datasets, including three citation network datasets (Sen et al., 2008) (i.e., Cora, Citeseer, Pubmed) and three new datasets (Shchur et al., 2018) (i.e., Coauthor Physics, Amazon Computer, and Amazon Photo). We summarized the description and experimental setup of the used datasets as follows.

**Cora, Citeseer, and Pubmed** (Sen et al., 2008): These are citation network datasets, where each network is a directed network in which a node represents a document and an edge

\begin{table}
\begin{tabular}{l c c c c c c} \hline \hline  & **Cora** & **Citeseer** & **Pubmed** & **Co. Physics** & **Ama.Computer** & **Ama.Photo** \\ \hline
**\#Nodes** & 2,708 & 3,327 & 19,717 & 34, 493 & 13, 381 & 7, 487 \\
**\#Edges** & 5,429 & 4,732 & 44,338 & 282, 455 & 259, 159 & 126, 530 \\
**\#Classes** & 7 & 6 & 3 & 5 & 10 & 8 \\
**\#Features** & 1,433 & 3,703 & 500 & 8,415 & 767 & 745 \\
**\#Training nodes** & 140 & 120 & 60 & 100 & 200 & 160 \\
**\#Validation nodes** & 500 & 500 & 500 & 500 & 500 & 500 \\
**\#Test nodes** & 1,000 & 1,000 & 1,000 & 1000 & 1,000 & 1000 \\ \hline \hline \end{tabular}
\end{table}
Table 2.2: Description of datasets and their experimental setup for the node classification prediction.
is a citation link, meaning that there exists an edge when \(A\) document cites \(B\) document, or vice-versa with a direction. Each node's feature vector contains a bag-of-words representation of a document. For simplicity, we don't discriminate the direction of links and treat citation links as undirected edges and construct a binary, symmetric adjacency matrix \(\mathbf{A}\). Each node is labeled with the class to which it belongs.

**Coauthor Physics, Amazon Computers, and Amazon Photo** (Shchur et al., 2018): Coauthor Physics is the dataset for co-authorship graphs based on the Microsoft Academic Graph from the KDD Cup 2016 Challenge1. In the graphs, a node is an author and an edge exists when two authors co-author a paper. A node's features represent the keywords of its papers and the node's class label indicates its most active field of study. Amazon Computers and Amazon Photo are the segments of an Amazon co-purchase graph (McAuley et al., 2015), where a node is a good (i.e., product), and an edge exists when two goods are frequently bought together. A node's features are the bag-of-words representation of product reviews and the node's class label is the product category.

Footnote 1: KDD Cup 2016 Dataset: Online Available at [https://kddcup2016.azurewebsites.net/](https://kddcup2016.azurewebsites.net/)

For all the used datasets, we deal with undirected graphs with 20 training nodes for each category. We chose the same dataset splits as in (Yang et al., 2016) with an additional validation node set of 500 labeled examples for the hyperparameter obtained from the citation datasets, and followed the same dataset splits in (Shchur et al., 2018) for Coauthor Physics, Amazon Computer, and Amazon Photo datasets, for the fair comparison2.

Footnote 2: The source code and datasets are accessible at [https://github.com/zxj32/uncertainty-GNN](https://github.com/zxj32/uncertainty-GNN)

**Metric**: We used the following metrics for our experiments:

* _Area Under Receiver Operating Characteristics (AUROC)_: AUROC shows the area under the curve where FPR (false positive rate) is in \(x\)-axis and TPR (true positive rate) is in \(y\)-axis. It can be interpreted as the probability that a positive example is assigned a higher
detection score than a negative example(Fawcett, 2006). A perfect detector corresponds to an AUROC score of 100%.
* _Area Under Precision-Prediction Curve (AUPR)_: The PR curve is a graph showing the precision=TP/(TP+FP) and recall=TP/(TP+FN) against each other,and AUPR denotes the area under the precision-recall curve. The ideal case is when Precision is 1 and Recall is 1.

**Comparing Schemes**: We conducted an extensive comparative performance analysis based on our proposed models and several state-of-the-art competitive counterparts. We implemented all models based on the most popular GNN model, GCN (Kipf and Welling, 2017). We compared our model (S-BGCN-T-K) against (1) Softmax-based GCN (Kipf and Welling, 2017) with uncertainty measured based on entropy; and (2) Drop-GCN that adapts the Monte-Carlo Dropout (Gal and Ghahramani, 2016; Ryu et al., 2019) into the GCN model to learn probabilistic uncertainty; (3) EDL-GCN that adapts the EDL model (Sensoy et al., 2018) with GCN to estimate evidential uncertainty; (4) DPN-GCN that adapts the DPN (Malinin and Gales, 2018) method with GCN to estimate probabilistic uncertainty. We evaluated the performance of all models considered using the area under the ROC (AUROC) curve and area under the Precision-Recall (AUPR) curve in both experiments (Hendrycks and Gimpel, 2017).

**Model Setups for semi-supervised node classification**. Our models were initialized using Glorot initialization (Glorot and Bengio, 2010) and trained to minimize loss using the Adam SGD optimizer (Kingma and Ba, 2014). For the S-BGCN-T-K model, we used the _early stopping strategy_(Shchur et al., 2018) on Coauthor Physics, Amazon Computer, and Amazon Photo datasets while _non-early stopping strategy_ was used in citation datasets (i.e., Cora, Citeseer and Pubmed). We set bandwidth \(\sigma=1\) for all datasets in GKDE, and set trade-off parameters \(\lambda_{1}=0.001\) for misclassification detection, \(\lambda_{1}=0.1\) for OOD detection
and \(\lambda_{2}=\min(1,t/200)\) (where \(t\) is the index of a current training epoch) for both task; other hyperparameter configurations are summarized in Table 2.3.

For semi-supervised node classification, we used 50 random weight initialization for our models on Citation network datasets. For Coauthor Physics, Amazon Computer, and Amazon Photo datasets, we reported the result based on 10 random train/validation/test splits. In both effects of uncertainty on misclassification and the OOD detection, we reported the AUPR and AUROC results in percent averaged over 50 times of randomly chosen 1000 test nodes in all of the test sets (except training or validation set) for all models tested on the citation datasets. For S-BGCN-T-K model in these tasks, we used the same hyperparameter configurations as in Table 2.3, except S-BGCN-T-K Epistemic using 10,000 epochs to obtain the best result.

**Baseline Setting**. In the experiment part, we considered 4 baselines. For GCN, we used the same hyper-parameters as (Kipf and Welling, 2016). For EDL-GCN, we used the same hyper-parameters as GCN, and replaced softmax layer to activation layer (Relu) with squares loss (Sensoy et al., 2018). For DPN-GCN, we used the same hyper-parameters as GCN, and changed the softmax layer to activation layer (exponential). Note that as we can not generate OOD node, we only used in-distribution loss of (see Eq.12 in (Malinin and Gales, 2018)) and ignored the OOD part loss. For Drop-GCN, we used the same hyper-parameters as GCN, and set Monte Carlo sampling times \(M=100\), dropout rate equal to 0.5.

**Experimental Setup for Out-of-Distribution (OOD) Detection** For OOD detection on semi-supervised node classification, we randomly selected 1-4 categories as OOD cate

\begin{table}
\begin{tabular}{l c c c c c c} \hline \hline  & **Cora** & **Citeseer** & **Pubmed** & **Co.Physics** & **Ama.Computer** & **Ama.Photo** \\ \hline
**Hidden units** & 16 & 16 & 16 & 64 & 64 & 64 \\
**Learning rate** & 0.01 & 0.01 & 0.01 & 0.01 & 0.01 & 0.01 \\
**Dropout** & 0.5 & 0.5 & 0.5 & 0.1 & 0.2 & 0.2 \\ \(L_{2}\) **reg-strength** & 0.0005 & 0.0005 & 0.0005 & 0.001 & 0.0001 & 0.0001 \\
**Monte-Carlo samples** & 100 & 100 & 100 & 100 & 100 & 100 \\
**Max epoch** & 200 & 200 & 200 & 100000 & 100000 & 100000 \\ \hline \hline \end{tabular}
\end{table}
Table 2.3: Hyperparameter configurations of S-BGCN-T-K model
gories and trained the models only based on training nodes of the other categories. In this setting, we still trained a model for the semi-supervised node classification task, but only part of node categories were not used for training. Hence, we suppose that our model only outputs partial categories (as we don't know the OOD category), see Table 2.4. For example, Cora dataset, we trained the model with 80 nodes (20 nodes for each category) with the predictions of 4 categories. The positive ratio is the ratio of out-of-distribution nodes among on all test nodes.

#### Results

**Misclassification Detection.** The misclassification detection experiment involves detecting whether a given prediction is incorrect using an uncertainty estimate. Table 2.5 shows that S-BGCN-T-K outperforms all baseline models under the AUROC and AUPR for misclassification detection. The outperformance of dissonance-based detection is fairly impressive. This confirms that low dissonance (a small amount of conflicting evidence) is the key to maximizing the accuracy of node classification prediction. We observe the following performance order: \(\texttt{Dissonance}>\texttt{Entropy}\approx\texttt{Aleatoric}>\texttt{Vacuity} \approx\texttt{Epistemic}\), which is aligned with our conjecture: higher dissonance with conflicting prediction leads to higher misclassification detection. We also conducted experiments on additional three datasets and observed similar trends of the results, as demonstrated in Appendix C.

**OOD Detection.** This experiment involves detecting whether an input example is out-of-distribution (OOD) given an estimate of uncertainty. For semi-supervised node classification, we randomly selected one to four categories as OOD categories and trained the models based

\begin{table}
\begin{tabular}{l c c c c c c} \hline \hline Dataset & **Cora** & **Citeseer** & **Pubmed** & **Co.Physics** & **Ama.Computer** & **Ama.Photo** \\ \hline
**Number of training categories** & 4 & 3 & 2 & 3 & 5 & 4 \\
**Training nodes** & 80 & 60 & 40 & 60 & 100 & 80 \\
**Test nodes** & 1000 & 1000 & 1000 & 1000 & 1000 & 1000 \\
**Positive ratio** & 38\% & 55\% & 40.4\% & 45.1\% & 48.1\% & 51.1\% \\ \hline \hline \end{tabular}
\end{table}
Table 2.4: Description of datasets and their experimental setup for the OOD detection.
on training nodes of the other categories. Due to the space constraint, the experimental setup for the OOD detection is detailed in Appendix B.3.

In Table 2.6, across six network datasets, our vacuity-based detection significantly outperformed the other competitive methods, exceeding the performance of the epistemic uncertainty and other type of uncertainties. This demonstrates that the vacuity-based model is more effective than other uncertainty estimates-based counterparts in increasing OOD detection. We observed the following performance order: \(\texttt{Vacuity}>\texttt{Entropy}\approx\texttt{Aleatoric}>\texttt{Aleatoric}>\)

\begin{table}
\begin{tabular}{c||c|c c c c|c c c c c|c} \hline \hline \multirow{2}{*}{Data} & \multirow{2}{*}{Model} & \multicolumn{5}{c|}{AUROC} & \multicolumn{5}{c}{AUPR} & \multirow{2}{*}{Acc} \\  & & Va. & Dis. & Al. & Ep. & En. & Va. & Dis. & Al. & Ep. & En. & Acc \\ \hline \multirow{5}{*}{Cora} & S-BGCN-T-K & 70.6 & **82.4** & 75.3 & 68.8 & 77.7 & 90.3 & **95.4** & 92.4 & 87.8 & 93.4 & **82.0** \\  & EDL-GCN & 70.2 & 81.5 & - & - & 76.9 & 90.0 & 94.6 & - & - & 93.6 & 81.5 \\  & DPN-GCN & - & - & 78.3 & 75.5 & 77.3 & - & - & 92.4 & 92.0 & 92.4 & 80.8 \\  & Drop-GCN & - & - & 73.9 & 66.7 & 76.9 & - & - & 92.7 & 90.0 & 93.6 & 81.3 \\  & GCN & - & - & - & - & 79.6 & - & - & - & - & 94.1 & 81.5 \\ \hline \multirow{5}{*}{Citeseer} & S-BGCN-T-K & 65.4 & **74.0** & 67.2 & 60.7 & 70.0 & 79.8 & **85.6** & 82.2 & 75.2 & 83.5 & **71.0** \\  & EDL-GCN & 64.9 & 73.6 & - & - & 69.6 & 79.2 & 84.6 & - & - & 82.9 & 70.2 \\  & DPN-GCN & - & - & 66.0 & 64.9 & 65.5 & - & - & 78.7 & 77.6 & 78.1 & 68.1 \\  & Drop-GCN & - & - & 66.4 & 60.8 & 69.8 & - & - & 82.3 & 77.8 & 83.7 & 70.9 \\  & GCN & - & - & - & - & 71.4 & - & - & - & - & 83.2 & 70.3 \\ \hline \multirow{5}{*}{Pubmed} & S-BGCN-T-K & 64.1 & **73.3** & 69.3 & 64.2 & 70.7 & 85.6 & **90.8** & 88.8 & 86.1 & 89.2 & **79.3** \\  & EDL-GCN & 62.6 & 69.0 & - & - & 67.2 & 84.6 & 88.9 & - & - & 81.7 & 79.0 \\  & DPN-GCN & - & - & 72.7 & 69.2 & 72.5 & - & - & 87.8 & 86.8 & 87.7 & 77.1 \\  & Drop-GCN & - & - & 67.3 & 66.1 & 67.2 & - & - & 88.6 & 85.6 & 89.0 & 79.0 \\  & GCN & - & - & - & - & 68.5 & - & - & - & - & 89.2 & 79.0 \\ \hline \multirow{5}{*}{Amazon Photo} & S-BGCN-T-K & 66.0 & **89.3** & 83.0 & 83.4 & 83.2 & 95.4 & **98.9** & 98.4 & 98.1 & 98.4 & **92.0** \\  & EDL-GCN & 65.1 & 88.5 & - & - & 82.2 & 94.6 & 98.1 & - & - & 98.0 & 91.2 \\  & DPN-GCN & - & - & 84.6 & 84.2 & 84.3 & - & - & 98.4 & 98.3 & 98.3 & 92.0 \\  & Drop-GCN & - & - & 84.5 & 84.4 & 84.6 & - & - & 98.2 & 98.1 & 98.2 & 91.3 \\  & GCN & - & - & - & - & 86.8 & - & - & - & - & 98.5 & 91.2 \\ \hline \multirow{5}{*}{Amazon Computer} & S-BGCN-T-K & 65.0 & **87.8** & 83.3 & 79.6 & 83.6 & 89.4 & **96.3** & 95.0 & 94.2 & 95.0 & **84.0** \\  & EDL-GCN & 64.1 & 86.5 & - & - & 82.2 & 93.6 & 97.1 & - & - & 97.0 & 79.7 \\ \cline{1-1}  & DPN-GCN & - & - & 82.0 & 81.7 & 81.8 & - & - & 95.8 & 95.7 & 95.8 & 85.2 \\ \cline{1-1}  & Drop-GCN & - & - & 79.1 & 75.9 & 79.2 & - & - & 95.1 & 94.5 & 95.1 & 79.6 \\ \cline{1-1}  & GCN & - & - & - & - & 81.7 & - & - & - & - & 95.4 & 79.7 \\ \hline \multirow{5}{*}{Coauthor Physics} & S-BGCN-T-K & 80.2 & **91.4** & 87.5 & 81.7 & 87.6 & 98.3 & **99.4** & 99.0 & 98.4 & 98.9 & **93.0** \\ \cline{1-1}  & EDL-GCN & 78.8 & 89.5 & - & - & 86.2 & 96.6 & 97.2 & - & - & 97.0 & 92.7 \\ \cline{1-1}  & DPN-GCN & - & - & 90.0 & 89.9 & 90.0 & - & - & 99.3 & 99.3 & 99.3 & 92.5 \\ \cline{1-1}  & Drop-GCN & - & - & 87.6 & 84.1 & 87.7 & - & - & 98.9 & 98.6 & 98.9 & 93.0 \\ \cline{1-1}  & GCN & - & - & - & - & 88.7 & - & - & - & - & 99.0 & 92.8 \\ \hline \hline \end{tabular}

* Va.: Vacuity, Dis.: Dissonance, Al.: Aleatoric, Ep.: Epistemic, En.: Entropy

\end{table}
Table 2.5: AUROC and AUPR for the Misclassification Detection.
Epistemic\(\approx\)Dissonance, which is consistent with the theoretical results as shown in Theorem 1.

**Ablation Study.** We conducted additional experiments (see Table 2.7 and Table 2.9) in order to demonstrate the contributions of the key technical components, including GKDE, Teacher Network, and subjective Bayesian framework. The key findings obtained from this experiment are: (1) GKDE can enhance the OOD detection (i.e., 30% increase with vacuity), which is consistent with our theoretical proof about the outperformance of GKDE in

\begin{table}
\begin{tabular}{c||c|c c c c c|c c c c} \hline \hline \multirow{2}{*}{Data} & \multirow{2}{*}{Model} & \multicolumn{5}{c|}{AUROC} & \multicolumn{5}{c}{AUPR} \\  & & Va. & Dis. & Al. & Ep. & En. & Va. & Dis. & Al. & Ep. & En. \\ \hline \multirow{5}{*}{Cora} & S-BGCN-T-K & **87.6** & 75.5 & 85.5 & 70.8 & 84.8 & **78.4** & 49.0 & 75.3 & 44.5 & 73.1 \\  & EDL-GCN & 84.5 & 81.0 & & - & 83.3 & 74.2 & 53.2 & - & - & 71.4 \\  & DPN-GCN & - & - & 77.3 & 78.9 & 78.3 & - & - & 58.5 & 62.8 & 63.0 \\  & Drop-GCN & - & - & 81.9 & 70.5 & 80.9 & - & - & 69.7 & 44.2 & 67.2 \\  & GCN & - & - & - & - & 80.7 & - & - & - & - & 66.9 \\ \hline \multirow{5}{*}{Citeseer} & S-BGCN-T-K & **84.8** & 55.2 & 78.4 & 55.1 & 74.0 & **86.8** & 54.1 & 80.8 & 55.8 & 74.0 \\  & EDL-GCN & 78.4 & 59.4 & - & - & 69.1 & 79.8 & 57.3 & - & - & 69.0 \\  & DPN-GCN & - & - & 68.3 & 72.2 & 69.5 & - & - & 68.5 & 72.1 & 70.3 \\  & Drop-GCN & - & - & 72.3 & 61.4 & 70.6 & - & - & 73.5 & 60.8 & 70.0 \\  & GCN & - & - & - & - & 70.8 & - & - & - & - & 70.2 \\ \hline \multirow{5}{*}{Pubmed} & S-BGCN-T-K & **74.6** & 67.9 & 71.8 & 59.2 & 72.2 & **69.6** & 52.9 & 63.6 & 44.0 & 56.5 \\  & EDL-GCN & 71.5 & 68.2 & - & - & 70.5 & 65.3 & 53.1 & - & - & 55.0 \\  & DPN-GCN & - & - & 63.5 & 63.7 & 63.5 & - & - & 50.7 & 53.9 & 51.1 \\  & Drop-GCN & - & - & 68.7 & 60.8 & 66.7 & - & - & 59.7 & 46.7 & 54.8 \\  & GCN & - & - & - & - & 68.3 & - & - & - & - & 55.3 \\ \hline \multirow{5}{*}{Amazon Photo} & S-BGCN-T-K & **93.4** & 76.4 & 91.4 & 32.2 & 91.4 & **94.8** & 68.0 & 92.3 & 42.3 & 92.5 \\  & EDL-GCN & 63.4 & 78.1 & - & - & 79.2 & 66.2 & 74.8 & - & - & 81.2 \\  & DPN-GCN & - & - & 83.6 & 83.6 & 83.6 & - & - & 82.6 & 82.4 & 82.5 \\  & Drop-GCN & - & - & 84.5 & 58.7 & 84.3 & - & - & 87.0 & 57.7 & 86.9 \\  & GCN & - & - & - & - & 84.4 & - & - & - & - & 87.0 \\ \hline \multirow{5}{*}{Amazon Computer} & S-BGCN-T-K & **82.3** & 76.6 & 80.9 & 55.4 & 80.9 & **70.5** & 52.8 & 60.9 & 35.9 & 60.6 \\  & EDL-GCN & 53.2 & 70.1 & - & - & 70.0 & 33.2 & 43.9 & - & - & 45.7 \\ \cline{1-1}  & DPN-GCN & - & - & 77.6 & 77.7 & 77.7 & - & - & 50.8 & 51.2 & 51.0 \\ \cline{1-1}  & Drop-GCN & - & - & 74.4 & 70.5 & 74.3 & - & - & 50.0 & 46.7 & 49.8 \\ \cline{1-1}  & GCN & - & - & - & - & 74.0 & - & - & - & - & 48.7 \\ \hline \multirow{5}{*}{Coauthor Physics} & S-BGCN-T-K & **91.3** & 87.6 & 89.7 & 61.8 & 89.8 & **72.2** & 56.6 & 68.1 & 25.9 & 67.9 \\  & EDL-GCN & 88.2 & 85.8 & - & - & 87.6 & 67.1 & 51.2 & - & - & 62.1 \\ \cline{1-1}  & DPN-GCN & - & - & 85.5 & 85.6 & 85.5 & - & - & 59.8 & 60.2 & 59.8 \\ \cline{1-1}  & Drop-GCN & - & - & 89.2 & 78.4 & 89.3 & - & - & 66.6 & 37.1 & 66.5 \\ \cline{1-1}  & GCN & - & - & - & - & 89.1 & - & - & - & - & 64.0 \\ \hline \hline \end{tabular}

* Va.: Vacuity, Dis.: Dissonance, Al.: Aleatoric, Ep.: Epistemic, En.: Entropy

\end{table}
Table 2.6: AUROC and AUPR for the OOD Detection.
uncertainty estimation, i.e., OOD nodes have a higher vacuity than other nodes; and (2) the Teacher Network can further improve the node classification accuracy.

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

**Compare with Bayesian GCN baseline**. Compare with a (Bayesian) GCN baseline, Dropout+DropEdge (Rong et al., 2019). As shown in the table 2.10 below, our proposed

\begin{table}
\begin{tabular}{c||c|c c c c|c c c c c|c} \hline \multirow{2}{*}{Data} & \multirow{2}{*}{Model} & \multicolumn{5}{c|}{AUROC} & \multicolumn{5}{c}{AUPR} \\  & & Va. & Dis. & Al. & Ep. & En. & Va. & Dis. & Al. & Ep. & En. & Acc \\ \hline \multirow{4}{*}{Cora} & S-BGCN-T-K & 70.6 & 82.4 & 75.3 & 68.8 & 77.7 & 90.3 & **95.4** & 92.4 & 87.8 & 93.4 & 82.0 \\  & S-BGCN-T & 70.8 & **82.5** & 75.3 & 68.9 & 77.8 & 90.4 & **95.4** & 92.6 & 88.0 & 93.4 & **82.2** \\  & S-BGCN & 69.8 & 81.4 & 73.9 & 66.7 & 76.9 & 89.4 & 94.3 & 92.3 & 88.0 & 93.1 & 81.2 \\  & S-GCN & 70.2 & 81.5 & - & - & 76.9 & 90.0 & 94.6 & - & - & 93.6 & 81.5 \\ \hline \multirow{4}{*}{Citeseer} & S-BGCN-T-K & 65.4 & **74.0** & 67.2 & 60.7 & 70.0 & 79.8 & **85.6** & 82.2 & 75.2 & 83.5 & 71.0 \\  & S-BGCN-T & 65.4 & 73.9 & 67.1 & 60.7 & 70.1 & 79.6 & 85.5 & 82.1 & 75.2 & 83.5 & **71.3** \\  & S-BGCN & 63.9 & 72.1 & 66.1 & 58.9 & 69.2 & 78.4 & 83.8 & 80.6 & 75.6 & 82.3 & 70.6 \\  & S-GCN & 64.9 & 71.9 & - & - & 69.4 & 79.5 & 84.2 & - & - & 82.5 & 71.0 \\ \hline \multirow{4}{*}{Pubmed} & S-BGCN-T-K & 63.1 & **69.9** & 66.5 & 65.3 & 68.1 & 85.6 & 90.8 & 88.8 & 86.1 & 89.2 & **79.3** \\  & S-BGCN-T & 63.2 & **69.9** & 66.6 & 65.3 & 64.8 & 85.6 & **90.9** & 88.9 & 86.0 & 89.3 & 79.2 \\  & S-BGCN & 62.7 & 68.1 & 66.1 & 64.4 & 68.0 & 85.4 & 90.5 & 88.6 & 85.6 & 89.2 & 78.8 \\  & S-GCN & 62.9 & 69.5 & - & - & 68.0 & 85.3 & 90.4 & - & - & 89.2 & 79.1 \\ \hline \multirow{4}{*}{Amazon Photo} & S-BGCN-T-K & 66.0 & 89.3 & 83.0 & 83.4 & 83.2 & 95.4 & **98.9** & 98.4 & 98.1 & 98.4 & 92.0 \\  & S-BGCN-T & 66.1 & 89.3 & 83.1 & 83.5 & 83.3 & 95.6 & 99.0 & 98.4 & 98.2 & 98.4 & **92.3** \\  & S-BGCN & 68.6 & **93.6** & 90.6 & 83.6 & 90.6 & 90.4 & 98.1 & 97.3 & 95.8 & 97.3 & 81.0 \\  & S-GCN & - & - & - & - & 86.7 & - & - & - & - & - & 98.4 \\ \hline \multirow{4}{*}{Amazon Computer} & S-BGCN-T-K & 65.0 & 87.8 & 83.3 & 79.6 & 83.6 & 89.4 & 96.3 & 95.0 & 94.2 & 95.0 & 84.0 \\  & S-BGCN-T & 65.2 & 88.0 & 83.4 & 79.7 & 83.6 & 89.4 & **96.5** & 95.0 & 94.5 & 95.1 & **84.1** \\  & S-BGCN & 63.7 & **89.1** & 84.3 & 76.1 & 84.4 & 84.9 & 95.7 & 93.9 & 91.4 & 93.9 & 76.1 \\  & S-GCN & - & - & - & - & 81.5 & - & - & - & - & - & 95.2 \\ \hline \multirow{4}{*}{Coauthor Physics} & S-BGCN-T-K & 80.2 & 91.4 & 87.5 & 81.7 & 87.6 & 98.3 & **99.4** & 99.0 & 98.4 & 98.9 & 93.0 \\  & S-BGCN-T & 80.4 & **91.5** & 87.6 & 81.7 & 87.6 & 98.3 & **99.4** & 99.0 & 98.6 & 99.0 & **93.2** \\ \cline{1-1}  & S-BGCN & 79.6 & 90.5 & 86.3 & 81.2 & 86.4 & 98.0 & 99.2 & 98.8 & 98.3 & 98.8 & 92.9 \\ \cline{1-1}  & S-GCN & 89.1 & 89.0 & - & - & 89.2 & 99.0 & 99.0 & - & - & 99.0 & 92.9 \\ \hline \end{tabular} Va.: Vacuity, Dis.: Dissonance, Al.: Aleatoric, Ep.: Epistemic, En.: Entropy

\end{table}
Table 2.7: Ablation experiment on AUROC and AUPR for the Misclassification Detection.
method performed better than Dropout+DropEdge on the Cora and Citeer datasets for misclassificaiton detection. A similar trend was observed for OOD detection.

#### Why is Epistemic Uncertainty Less Effective than Vacuity?

Although epistemic uncertainty is known to be effective to improve OOD detection (Gal and Ghahramani, 2016; Kendall and Gal, 2017) in computer vision applications, our results

\begin{table}
\begin{tabular}{l c c c c c|c c c c c} \hline \hline \multirow{2}{*}{Data} & \multirow{2}{*}{Model} & \multicolumn{6}{c|}{AUROC} & \multicolumn{6}{c}{AUPR} \\  & & Va. & Dis. & Al. & Ep. & En. & Va. & Dis. & Al. & Ep. & En. \\ \hline \multirow{4}{*}{Cora} & S-BGCN-T-K & **87.6** & 75.5 & 85.5 & 70.8 & 84.8 & **78.4** & 49.0 & 75.3 & 44.5 & 73.1 \\  & S-BGCN-T & 84.5 & 81.2 & 83.5 & 71.8 & 83.5 & 74.4 & 53.4 & 75.8 & 46.8 & 71.7 \\  & S-BGCN & 76.3 & 79.3 & 81.5 & 70.5 & 80.6 & 61.3 & 55.8 & 68.9 & 44.2 & 65.3 \\  & S-GCN & 75.0 & 78.2 & - & - & 79.4 & 60.1 & 54.5 & - & - & 65.3 \\ \hline \multirow{4}{*}{Citeseer} & S-BGCN-T-K & **84.8** & 55.2 & 78.4 & 55.1 & 74.0 & **86.8** & 54.1 & 80.8 & 55.8 & 74.0 \\  & S-BGCN-T & 78.6 & 59.6 & 73.9 & 56.1 & 69.3 & 79.8 & 57.4 & 76.4 & 57.8 & 69.3 \\  & S-BGCN & 72.7 & 63.9 & 72.4 & 61.4 & 70.5 & 73.0 & 62.7 & 74.5 & 60.8 & 71.6 \\  & SGCN & 72.0 & 62.8 & - & - & 70.0 & 71.4 & 61.3 & - & - & 70.5 \\ \hline \multirow{4}{*}{Pubmed} & S-BGCN-T-K & **74.6** & 67.9 & 71.8 & 59.2 & 72.2 & **69.6** & 52.9 & 63.6 & 44.0 & 56.5 \\  & S-BGCN-T & 71.8 & 68.6 & 70.0 & 60.1 & 70.8 & 65.7 & 53.9 & 61.8 & 46.0 & 55.1 \\  & S-BGCN & 70.8 & 68.2 & 70.3 & 60.8 & 68.0 & 65.4 & 53.2 & 62.8 & 46.7 & 55.4 \\  & S-GCN & 71.4 & 68.8 & - & - & 69.7 & 66.3 & 54.9 & - & - & 57.5 \\ \hline \multirow{4}{*}{Amazon} & S-BGCN-T-K & **93.4** & 76.4 & 91.4 & 32.2 & 91.4 & **94.8** & 68.0 & 92.3 & 42.3 & 92.5 \\  & S-BGCN-T & 64.0 & 77.5 & 79.9 & 52.6 & 79.8 & 67.0 & 75.3 & 82.0 & 53.7 & 81.9 \\ \cline{1-1}  & S-BGCN & 63.0 & 76.6 & 79.8 & 52.7 & 79.7 & 66.5 & 75.1 & 82.1 & 53.9 & 81.7 \\ \cline{1-1}  & S-GCN & 64.0 & 77.1 & - & - & 79.6 & 67.0 & 74.9 & - & - & 81.6 \\ \hline \multirow{4}{*}{Amazon} & S-BGCN-T-K & **82.3** & 76.6 & 80.9 & 55.4 & 80.9 & **70.5** & 52.8 & 60.9 & 35.9 & 60.6 \\ \cline{1-1}  & S-BGCN-T & 53.7 & 70.5 & 70.4 & 69.9 & 70.1 & 33.6 & 43.9 & 46.0 & 46.8 & 45.9 \\ \cline{1-1}  & S-BGCN & 56.9 & 75.3 & 74.1 & 73.7 & 74.1 & 33.7 & 46.2 & 48.3 & 45.6 & 48.3 \\ \cline{1-1}  & S-GCN & 56.9 & 75.3 & - & - & 74.2 & 33.7 & 46.2 & - & - & 48.3 \\ \hline \multirow{4}{*}{Coauthor} & S-BGCN-T-K & **91.3** & 87.6 & 89.7 & 61.8 & 89.8 & **72.2** & 56.6 & 68.1 & 25.9 & 67.9 \\ \cline{1-1}  & S-BGCN-T & 88.7 & 86.0 & 87.9 & 70.2 & 87.8 & 67.4 & 51.9 & 64.6 & 29.4 & 62.4 \\ \cline{1-1}  & S-BGCN & 89.1 & 87.1 & 89.5 & 78.3 & 89.5 & 66.1 & 49.2 & 64.6 & 35.6 & 64.3 \\ \cline{1-1}  & S-GCN & 89.1 & 87.0 & - & - & 89.4 & -66.2 & 49.2 & - & - & 64.3 \\ \hline \multicolumn{11}{c}{Va.: Vacuity, Dis.: Dissonance, Al.: Aleatoric, Ep.: Epistemic, D.En.: Differential Entropy, En.: Entropy} \\ \end{tabular}
\end{table}
Table 2.8: Big-O time complexity of our method and baseline GCN.

\begin{table}
\begin{tabular}{l c c c c|c c c c c} \hline \hline Dataset & GCN & S-GCN & S-BGCN & S-BGCN & S-BGCN-T & S-BGCN-T-K \\ \hline Time Complexity (Train) & \(O(|\mathbb{E}|CF)\) & \(O(|\mathbb{E}|CF)\) & \(O(2|\mathbb{E}|CF)\) & \(O(2|\mathbb{E}|CF)\) & \(O(2|\mathbb{E}|CF)\) & \(O(2|\mathbb{E}|CF)\) \\ Time Complexity (Test) & \(O(|\mathbb{E}|CF)\) & \(O(|\mathbb{E}|CF)\) & \(O(M|\mathbb{E}|CF)\) & \(O(M|\mathbb{E}|CF)\) & \(O(M|\mathbb{E}|CF)\) & \(O(M|\mathbb{E}|CF)\) \\ \hline \hline \end{tabular}
\end{table}
Table 2.9: Ablation experiment on AUROC and AUPR for the OOD Detection.
demonstrate it is less effective than our vacuity-based approach. The first potential reason is that epistemic uncertainty is always smaller than vacuity (From Theorem 1), which potentially indicates that epistemic may capture less information related to OOD. Another potential reason is that the previous success of epistemic uncertainty for OOD detection is limited to supervised learning in computer vision applications, but its effectiveness for OOD detection was not sufficiently validated in semi-supervised learning tasks. Recall that epistemic uncertainty (i.e., model uncertainty) is calculated based on mutual information (see Eq. (2.6)). In a semi-supervised setting, the features of unlabeled nodes are also fed to a model for the training process to provide the model with high confidence in its output. For example, the model output \(P(\mathbf{y}|A,\mathbf{r};\theta)\) would not change too much even with differently sampled parameters \(\mathbf{\theta}\), i.e., \(P(\mathbf{y}|A,\mathbf{r};\theta^{(i)})\approx P(\mathbf{y}|A,\mathbf{r}; \theta^{(j)})\), which result in a low epistemic uncertainty.

To back up our conclusion, design an image classification experiment based on MCDrop(Gal and Ghahramani, 2016) method to do the following experiment: 1) supervised learning on the MNIST dataset with 50 labeled images; 2) semi-supervised learning (SSL) on the MNIST dataset with 50 labeled images and 49950 unlabeled images, while there are 50% OOD images (24975 FashionMNIST images) in the unlabeled set. For both experiments, we test the epistemic uncertainty on 49950 unlabeled set (50% In-distribution (ID) images and 50% OOD images). We conduct the experiment based on three popular SSL methods, VAT (Miyato et al., 2018), Mean Teacher (Tarvainen and Valpola, 2017), and pseudo label (Lee, 2013). Table 2.11 shows the average epistemic uncertainty value for in-distribution

\begin{table}
\begin{tabular}{c||c|c c c c c|c c c c c} \hline \multirow{2}{*}{Dataset} & \multirow{2}{*}{Model} & \multicolumn{4}{c|}{AUROC} & \multicolumn{4}{c}{AUPR} \\  & & Va. & Dis. & Al. & Ep. & En. & Va. & Dis. & Al. & Ep. & En. \\ \hline \multirow{2}{*}{Cora} & S-BGCN-T-K & 70.6 & **82.4** & 75.3 & 68.8 & 77.7 & 90.3 & **95.4** & 92.4 & 87.8 & 93.4 \\  & DropEdge & - & - & 76.6 & 56.1 & 76.6 & - & - & 93.2 & 85.4 & 93.2 \\ \hline \multirow{2}{*}{Citeseer} & S-BGCN-T-K & 65.4 & **74.0** & 67.2 & 60.7 & 70.0 & 79.8 & **85.6** & 82.2 & 75.2 & 83.5 \\  & DropEdge & - & - & 71.1 & 51.2 & 71.1 & - & - & 84.0 & 70.3 & 84.0 \\ \hline \end{tabular} Va.: Vacuity, Dis.: Dissonance, Al.: Aleatoric, Ep.: Epistemic, En.: Entropy

\end{table}
Table 2.10: Compare with DropEdge on Misclassification Detection.
samples and OOD samples. The result shows the same pattern with (Kendall and Gal, 2017; Kendall et al., 2015) in a supervised setting, but an opposite pattern in a semi-supervised setting that low epistemic of OOD samples, which is less effective top detect OOD. Note that the SSL setting is similar to our semi-supervised node classification setting, which feed the unlabeled sample to train the model.

#### Graph Embedding Representations of Different Uncertainty Types

\begin{table}
\begin{tabular}{l c c c c} \hline \hline Epistemic & **Supervised** & **VAT** & **Mean Teacher** & **Pseudo Label** \\ \hline
**In-Distribution** & 0.140 & **0.116** & **0.105** & **0.041** \\
**Out-of-Distribution** & **0.249** & 0.049 & 0.076 & 0.020 \\ \hline \hline \end{tabular}
\end{table}
Table 2.11: Epistemic uncertainty for semi-supervised image classification.

Figure 2.4: Graph embedding representations of the Cora dataset for classes and the extent of uncertainty: (a) shows the representation of seven different classes; (b) shows our model prediction; and (c)-(f) present the extent of uncertainty for respective uncertainty types, including vacuity, dissonance, aleatoric, epistemic.
To better understand different uncertainty types, we used \(t\)-SNE (\(t\)-Distributed Stochastic Neighbor Embedding (Maaten and Hinton, 2008)) to represent the computed feature representations of a pre-trained BGCN-T model's first hidden layer on the Cora dataset and the Citeseer dataset.

**Seven Classes on Cora Dataset**: In Figure 2.4, (a) shows the representation of seven different classes, (b) shows our model prediction, and (c)-(f) present the extent of uncertainty for respective uncertainty types, including vacuity, dissonance, and aleatoric uncertainty, respectively.

Figure 2.5: Graph embedding representations of the Citeseer dataset for classes and the extent of uncertainty: (a) shows the representation of seven different classes, (b) shows our model prediction, and (c)-(f) present the extent of uncertainty for respective uncertainty types, including vacuity, dissonance, and aleatoric uncertainty, respectively.
#### Six Classes on Citeseer Dataset

In Figure 2.5 (a), a node's color denotes a class on the Citeseer dataset where 6 different classes are shown in different colors. Figure 2.5 (b) is our prediction result.

**Eight Classes on Amazon Photo Dataset**: In Figure 2.6, a node's color denotes vacuity uncertainty value, and the big node represents the training node. These results are based on the OOD detection experiment. Comparing Figure 2.6 (a) and (b), we found that GKDE can indeed improve OOD detection.

For Figures 2.5 (c)-(f), the extent of uncertainty is presented where a blue color refers to the lowest uncertainty (i.e., minimum uncertainty) while a red color indicates the highest uncertainty (i.e., maximum uncertainty) based on the presented color bar. To examine the trends of the extent of uncertainty depending on either training nodes or test nodes, we draw training nodes as bigger circles than test nodes. Overall we notice that most training nodes (shown as bigger circles) have low uncertainty (i.e., blue), which is reasonable because

Figure 2.6: Graph embedding representations of the Amazon Photo dataset for the extent of vacuity uncertainty based on OOD detection experiment.
the training nodes are the ones that are already observed. Now we discuss the extent of uncertainty under each uncertainty type.

**Vacuity**: In Figure 2.6 (b), most training nodes show low uncertainty, we observe the majority of OOD nodes in the button cluster show high uncertainty as appeared in red.

**Dissonance**: In Figure 2.5 (d), similar to vacuity, training nodes have low uncertainty. But unlike vacuity, test nodes are much less uncertain. Recall that dissonance represents the degree of conflicting evidence (i.e., a discrepancy between each class probability). However, in this dataset, we observe a fairly low level of dissonance and the obvious outperformance of Dissonance in node classification prediction.

**Aleatoric uncertainty**: In Figure 2.5 (e), a lot of nodes show high uncertainty larger than 0.5 except for a small number of training nodes with low uncertainty.

**Epistemic uncertainty**: In Figure 2.5 (f), most nodes show very low epistemic uncertainty values because uncertainty derived from model parameters can disappear as they are trained well.

### 2.7 Conclusion

In this work, we proposed a multi-source uncertainty framework of GNNs for semi-supervised node classification. Our proposed framework provides an effective way of predicting node classification and out-of-distribution detection considering multiple types of uncertainty. We leveraged various types of uncertainty estimates from both DL and evidence/belief theory domains. Through our extensive experiments, we found that dissonance-based detection yielded the best performance on misclassification detection while vacuity-based detection performed the best for OOD detection, compared to other competitive counterparts. In particular, it was noticeable that applying GKDE and the Teacher network further enhanced the accuracy of node classification and uncertainty estimates.
Although our method introduced in this Chapter achieves good performance in semi-supervised node classification, especially in an out-of-distribution setting where part of unlabeled nodes (_e.g._, OODs) does not belong to training (in-distribution) classes. However, we found that the OODs nodes may hurt the semi-supervised node classification performance for in-distribution nodes. A similar issue also occurs in transitional semi-supervised learning (SSL) problems. Semi-supervised learning algorithm's performance could degrade when the unlabeled set has out-of-distribution examples. To this end, in the following Chapter, we first study the impact of OOD data on SSL algorithms and propose a novel unified uncertainty-aware robust SSL framework to solve this issue.
## Chapter 3 Uncertainty-Aware Robust Semi-Supervised Learning With Out of Distribution Data

### 3.1 Introduction

Deep learning approaches have been shown to be successful on several supervised learning tasks, such as computer vision (Szegedy et al., 2015), natural language processing (Graves, 2013), and speech recognition (Graves et al., 2013). However, these deep learning models are data-hungry and often require massive amounts of labeled examples to obtain good performance. Obtaining high-quality labeled examples can be very time-consuming and expensive, particularly where specialized skills are required in labeling (for example, in cancer detection on X-ray or CT-scan images). As a result, semi-supervised learning (SSL) (Zhu, 2005) has emerged as a very promising direction, where the learning algorithms try to effectively utilize the large unlabeled set (in conjunction) with a relatively small labeled set. Several recent SSL algorithms have been proposed for deep learning and have shown great promise empirically. These include Entropy Minimization (Grandvalet and Bengio, 2005), pseudo-label based methods (Lee, 2013; Arazo et al., 2019; Berthelot et al., 2019) and consistency based methods (Sajjadi et al., 2016; Laine and Aila, 2016; Tarvainen and Valpola, 2017; Miyato et al., 2018) to name a few.

Despite the positive results of the above SSL methods, they are designed with the assumption that both labeled and unlabeled sets have the same distribution. Fig 3.1 (a) shows an example of this. However, this assumption may not hold in many real-world applications, such as web classification (Yang et al., 2011) and medical diagnosis (Yang et al., 2015),
where some unlabeled examples are from novel classes unseen in the labeled data. For example, Fig 3.1 (b) illustrates an image classification scenario with out-of-distribution data, where the unlabeled dataset contains two novel classes (bicycle and clock) compared to the in-distribution classes (flower and beetle) in the labeled dataset. When the unlabeled set contains OOD examples (OODs), deep SSL performance can degrade substantially and is sometimes even worse than simple supervised learning (SL) approaches (Oliver et al., 2018). Moreover, it is unreasonable to expect a human to go through and clean a large and massive unlabeled set in such cases.

A general approach to robust SSL against OODs is to assign a weight to each unlabeled example based on some criteria and minimize a weighted training or validation loss. In particular, (Yan et al., 2016) applied a set of weak annotators to approximate the ground-truth labels as pseudo-labels to learn a robust SSL model. (Chen et al., 2019) proposed a distributionally robust model that estimates a parametric weight function based on both the discrepancy and the consistency between the labeled data and the unlabeled data. (Chen et al., 2020) (UASD) proposed to weigh the unlabeled examples based on an estimation of predictive uncertainty for each unlabeled example. The goal of UASD is to discard the potentially irrelevant samples having low confidence scores and estimate the parameters by optimizing a regularized training loss. A state-of-the-art method (Guo et al., 2020), called DS3L, considers a shallow neural network to predict the weights of unlabeled examples and estimate the parameters of the neural network based on a clean labeled set via bi-level optimization. It is common to obtain a dataset composed of two parts, including a relatively

Figure 3.1: (a) Traditional SSL. (b) SSL with OODs.
small but accurately labeled set and a large but coarsely labeled set from inexpensive crowd-sourcing services or other noisy sources.

There are three **main limitations** of DS3L and other methods as reviewed above. First, it lacks a study of the potential causes of the impact of OODs on SSL, and as a result, the interpretation of robust SSL methods becomes difficult. Second, existing robust SSL methods did not consider the negative impact of OODs on the utilization of BN in neural networks, and as a result, their robustness against OODs degrades significantly when a neural network includes BN layers. The utilization of BNs for deep SSL has an implicit assumption that the labeled and unlabeled examples follow a single or similar distribution, which is problematic when the unlabeled examples include OODs (Ioffe and Szegedy, 2015). Third, the bi-level learning algorithm developed in DS3L relies on low-order approximations of the objective in the inner loop due to vanishing gradients or memory constraints. As a result of not using the high-order loss information, the learning performance of DS3L could be significantly degraded in some applications, as demonstrated in our experiments. Our main technical contributions over existing methods are summarized as follows:

**The effect of OOD data points.** The first critical contribution of our work (Sec. 3.3) is to analyze what kind of OOD unlabeled data points affect the performance of SSL algorithms. In particular, we observe that OOD samples lying close to the decision boundary have more influence on SSL performance than those far from the boundary. Furthermore, we observe that the OOD instances far from the decision-boundary (faraway OODs) can degrade SSL performance substantially if the model contains a batch normalization (BN) layer. The last observation makes sense logically as well since the batch normalization heavily depends on the mean and variance of each batch's data points, which can be significantly different for OOD points that came from very different distributions. We find these observations about OOD points consistent across experiments on several synthetic and real-world datasets.

**Uncertainty-Aware Robust SSL Framework.** To address the above causes, we first proposed a simple modification to BN, called weighted batch normalization (WBN), to improve
BN's robustness against OODs. We demonstrate that W-BN can learn a better representation with good statistics estimation via a theoretical analysis. Finally, we proposed a unified, uncertainty-aware robust SSL approach to improve many existing SSL algorithms' robustness by learning to assign weights to unlabeled examples based on their meta-gradient directions derived from a loss function on a clean validation set. Different from safe SSL (Guo et al., 2020), we directly treat the weights as hyperparameters instead of the output of a parametric function. The effectiveness of this strategy has been well demonstrated in robust supervised learning problems against noise labels (Ren et al., 2018). Furthermore, treating the weights as hyperparameters enables the use of an implicit differentiation-based approach in addition to the meta-approximation algorithm considered in (Guo et al., 2020). In addition, we proposed two efficient bi-level algorithms for our proposed robust SSL approach, including meta-approximation and implicit-differentiation based, that have different tradeoffs on computational efficiency and accuracy. We designed the first algorithm based on lower-order approximations of the objective in the meta optimization's inner loop. We designed the second algorithm based on higher-order approximations of the objective and is scalable to a higher number of inner optimization steps to learn a massive amount of weight parameters, but is less efficient than the first algorithm.

**Speeding up the re-weighting algorithms.** A critical issue with the current approaches (Ren et al., 2018; Shu et al., 2019; Guo et al., 2020) for bi-level optimization is that they are around 3x slower (even after using a one-step gradient approximation) compared to the original training(in this case, the base SSL algorithm). Whereas more fancy and higher-order approaches like implicit differentiation (Lorraine et al., 2020) are even slower. We show that by adopting some simple tricks like just considering the last layer of the network in the inner one-step optimization (while updating the hyper-parameters) and performing the weight update step, only every \(L\) epochs can significantly speedup the reweighting while not significantly losing on its gains. In particular, we see that _we can bring down the run
time from \(3\times\) to \(1.2\times\), thereby significantly improving the experimental turn around times and reducing cost, energy, and time requirements of the reweighting algorithms._

**Comprehensive experiments.** We conduct extensive experiments on synthetic and real-world datasets. The results demonstrate that our weighted robust SSL approach significantly outperforms existing robust approaches (L2RW, MWN, Safe-SSL, and UASD) on four representative SSL algorithms. We also perform an ablation study to demonstrate which components of our approach are most important for its success. Finally, we show the effect of using last layer gradients and infrequent weight updates on both accuracy and time speedups.

### Semi-Supervised Learning (SSL)

#### 3.2.1 Notations

Given a training set with a labeled set of examples \(\mathcal{D}=\{\mathbf{x}_{i},y_{i}\}_{i=1}^{n}\) and an unlabeled set of examples \(\mathcal{U}=\{\mathbf{x}_{j}\}_{j=1}^{m}\). Vectors are denoted by lower case bold face letters, _e.g._, weight vector \(\mathbf{w}\in[0,1]^{|\mathcal{U}|}\) and uncertainty vector \(\mathbf{u}\in[0,1]^{|\mathcal{U}|}\) where their _i_-th entries are \(w_{i},u_{i}\). Scalars are denoted by lowercase italic letters, _e.g._, trade-off parameter \(\lambda\in\mathbb{R}\). Matrices are denoted by capital italic letters. Some important notations are listed in Table 3.1

Given a training set with a labeled set of examples \(\mathcal{D}=\{\mathbf{x}_{i},y_{i}\}_{i=1}^{n}\) and an unlabeled set of examples \(\mathcal{U}=\{\mathbf{x}_{j}\}_{j=1}^{m}\). For any classifier model \(f(\mathbf{x},\theta)\) used in SSL, where \(\mathbf{x}\in\mathbb{R}^{C}\) is the input data, and \(\theta\) refers to the parameters of the classifier model. The loss functions of many existing methods can be formulated in the following general form:

\[\sum\nolimits_{(\mathbf{x}_{i},y_{i})\in\mathcal{D}}l(f(\mathbf{x}_{i},\theta),y_{i})+\sum\nolimits_{x_{j}\in\mathcal{U}}r(f(\mathbf{x}_{j},\theta)), \tag{3.1}\]

where \(l(\cdot)\) is the loss function for labeled data (such as cross-entropy), and \(r(\cdot)\) is the loss function (regularization function) on the unlabeled set. The goal of SSL methods is to design an efficient regularization function to leverage the model performance information
on the unlabeled dataset for effective training. Pseudo-labeling (Lee, 2013) uses a standard supervised loss function on an unlabeled dataset using "pseudo-labels" as a target label as a regularizer. \(\Pi\)-Model (Laine and Aila, 2017; Sajjadi et al., 2016) designed a consistency-based regularization function that pushes the distance between the prediction for an unlabeled sample and its stochastic perturbation (e.g., data augmentation or dropout (Srivastava et al., 2014)) to a small value. Mean Teacher (Tarvainen and Valpola, 2017) proposed to obtain a more stable target output \(f(x,\theta)\) for unlabeled set by setting the target via an exponential moving average of parameters from previous training steps. Instead of designing a stochastic \(f(x,\theta)\), Virtual Adversarial Training (VAT) (Miyato et al., 2018) proposed to approximate a tiny perturbation to unlabeled samples that affect the output of the prediction function most. MixMatch (Berthelot et al., 2019), UDA (Xie et al., 2019), and Fix-Match (Sohn et al., 2020) choose the pseudo-labels based on predictions of augmented samples, such as shifts, cropping, image flipping, weak and strong augmentation, and mix-up (Zhang et al., 2017) to design the regularization functions. However, the performance of most existing SSL

\begin{table}
\begin{tabular}{l|l} \hline \hline
**Notations** & **Descriptions** \\ \hline \(\mathcal{D}\) & Labeled set \\ \(\mathcal{U}\) & Unlabeled set \\ \(\mathcal{V}\) & Validation set (labeled) \\ \(\mathbf{x}_{i}\) & Feature vector of sample \(i\) \\ \(y_{i}\) & Class label of sample \(i\) \\ \(\boldsymbol{\theta}\) & model parameters \\ \(f(\cdot)\) & semi-supervised learning model function \\ \(\mathcal{L}_{V}(\cdot)\) & Validation loss \\ \(\mathcal{L}_{T}(\cdot)\) & Training loss \\ \(l(\cdot)\) & Loss function for labeled data \\ \(r(\cdot)\) & Loss function for unlabeled data \\ \(\text{Un}(\cdot)\) & Uncertainty regularization term \\ \(J\) & Inner loop gradient steps \\ \(P\) & Neumann series approximation parameters \\ \hline \hline \end{tabular}
\end{table}
Table 3.1: Important notations and corresponding descriptions.
can degrade substantially when the unlabeled dataset contains OOD examples (Oliver et al., 2018).

### Impact of OOD on SSL Performance

In this section, we provide a systematic analysis of the impact of OODs for many popular SSL algorithms, such as Pseudo-Label(PL) (Lee, 2013), \(\Pi\)-Model (Laine and Aila, 2016), Mean Teacher(MT) (Tarvainen and Valpola, 2017), and Virtual Adversarial Training (VAT) (Miyato et al., 2018). We illustrate the discoveries using the following synthetic and real-world datasets. While we mainly focus on VAT as the choice of the SSL algorithm, the observations extend to other SSL algorithms as well.

**Synthetic dataset.** We considered two moons dataset (red points are labeled data, gray circle points are in-distribution (ID) unlabeled data) with OOD (yellow triangle points) points in three different scenarios that can exist in real-world, 1) Faraway OOD scenario where the OOD points exist far from decision boundary; 2) Boundary OOD scenario where the OOD points occur close to decision boundary; 3) Mixed OOD scenario where OOD points exist both far and close to the decision boundary, as shown in Fig 3.2.

**Real-world dataset.** We consider MNIST as ID data with three types of OODs to account for plausible real-world scenarios. 1)Faraway OOD: We used Fashion MNIST (F-MNIST)

Figure 3.2: SSL performance with different type OODs in synthetic datasets.
dataset, which contains fashion images as the Faraway OOD dataset as it inherently has different patterns compared to the MNIST dataset; 2) Boundary OOD: We used EMNIST dataset, which contains handwritten character digits as Boundary OOD dataset as it has similar patterns compared to MNIST dataset; In addition to EMNIST, we also considered Mean MNIST (M-MNIST) as a boundary OOD dataset, which was generated by averaging MNIST images from two different classes (usage of M-MNIST as boundary OOD is also considered in (Guo et al., 2019)); 4) Mixed OOD: For Mixed OOD dataset, we combined both Fashion MNIST and EMNIST together. To justify the usage of the above-mentioned datasets as Faraway, Boundary, and Mixed datasets, we use the vacuity uncertainty (Zhao et al., 2020) values as an estimate of their distance to the decision boundary. Table 3.2 shows the average vacuity uncertainty for each type of OODs; the results indicate that Fashion MNIST has larger vacuity uncertainty compared to MNIST, whereas vacuity uncertainties of EMNIST and M-MNIST are closer to MNIST. For more details, refer to the supplementary material. We also conducted a similar experiment in Sec. 3 based on CIFAR10 dataset. We adapt CIFAR10 to a 6-class classification task, using 400 labels per class (from the 6 classes), the ID classes are: "bird", "cat", "deer", "dog", "frog", "horse", and OOD data are from classes: "airline", "automobile", "ship", "truck"), we regard this type of OODs as boundary OODs, named CIFAR-4. Besides, we use the sample from the SVHN dataset as faraway OODs and consider mixed OODs that combined both SVHN and CIFAR-4. Table 3.3 showed the vacuity uncertainty for each dataset and got a similar pattern. Note that we use WRN-28-2 as the backbone for the CIFAR10 experiment such that we can not remove the BN layer (the SSL performance would significantly decrease when removing BN from WRN-28-2), so we only show "SSL-BN" and "SSL-FBN" in this case. The results are shown in Fig 3.3 (b), which shows a similar pattern made on the MNIST dataset.

For all experiments in this section, we used a multilayer perceptron neural network (MLP) with three layers as a backbone architecture for the synthetic dataset and LeNet (LeCun
et al., 1989) as a backbone for the real-world datasets. We consider the following models in the experiments: 1) _SSL-NBN_: MLP or LeNet model without Batch Normalization; 2) _SSL-BN_: MLP or LeNet model with Batch Normalization; 3) _SSL-FBN_: MLP or LeNet model where we freeze the batch normalization layers for the unlabeled instances. Freezing BN (FBN) (Oliver et al., 2018) is a common trick to improve the SSL model robustness where we freeze batch normalization layers by not updating _running_mean_ and _running_variance_ in the training phase.

The following are the main observations. First, from Fig 3.2, we see that with BN (i.e., SSL-BN), there is a significant impact on model performance and learned decision boundaries in the presence of OOD. This performance degradation is even more pronounced

\begin{table}
\begin{tabular}{c c c c} \hline _SVHN_ & _CIFAR-4_ & _Mixed_ & _CIFAR(ID)_ \\ \hline
0.27 & 0.18 & 0.22 & 0.15 \\ \hline \end{tabular}
\end{table}
Table 3.3: Uncertainty for different type OODs based on CIFAR10.

Figure 3.3: SSL performance with different type OODs in real world datasets.
in Faraway OOD since the BN statistics, like the running mean/variance can be significantly changed by faraway OOD points. Secondly, when we do not use BN (i.e., SSL-NBN), the impact of the Faraway OOD and mixed OOD data is reduced. However, in the case of boundary OOD (Fig 3.2 (b) and EMNIST/M-MNIST case of Fig 3.3), we still see significant performance degradation compared to the skyline. However, BN is a crucial component in more complicated models (Eg: ResNet family), and we expect OOD instances to play a significant role there. Finally, when freezing the BN layers for the unlabeled data (i.e., SSL-FBN), we see that the Faraway and Mixed OODs' effect is alleviated; but SSL-FBN still performs worse than the SSL-NBN in Faraway and Mixed OODs (and there is a big scope of improvement w.r.t the skyline). Finally, both SSL-NBN and SSL-FBN fail to efficiently mitigate the performance degradation caused by boundary OOD data points. In the supplementary material, we also show similar observations made on the CIFAR-10 dataset.

The main takeaways of the synthetic and real data experiments are as follows: 1) OOD instances close to the decision boundary (Boundary OODs) hurt SSL performance irrespective of the use of batch normalization; 2) OOD instances far from the decision boundary (Faraway OODs) hurt the SSL performance if the model involves BN. Freezing BN can reduce some impact of OOD to some extent but not entirely; 3) OOD instances far from the decision boundary will not hurt SSL performance if there is no BN in the model. In the next section, we propose a robust SSL reweighting framework to address above mentioned issues caused by OOD data points.

### Methodology

In this section, we first proposed the uncertainty-aware robust SSL framework, and then introduce two efficient bi-level algorithms to train the robust SSL approach. More impor
tantly, we proposed Weighted Batch Normalization (WBN) to improve the robustness of our robust SSL framework against OODs.

#### Uncertainty-Aware Robust SSL Framework

. **Reweighting the unlabeled data.** Consider the semi-supervised classification problem with training data (labeled \(\mathcal{D}\) and unlabeled \(\mathcal{U}\)) and classifier \(f(x;\theta)\). Generally, the optimal classifier parameter \(\theta\) can be extracted by minimizing the SSL loss (Eq. (3.1)) calculated on the training set. In the presence of unlabeled OOD data, sample reweighting methods enhance the robustness of training by imposing weight \(w_{j}\) on the \(j\)-th unlabeled sample loss,

\[\mathcal{L}_{T}(\theta,\mathbf{w})=\sum_{(\mathbf{x}_{i},y_{i})\in\mathcal{D }}l(f(\mathbf{x}_{i};\theta),y_{i})+\sum_{x_{j}\in\mathcal{U}}w_{j}r(f( \mathbf{x}_{j};\theta)),\]

where we denote \(\mathcal{L}_{U}\) is the robust unlabeled loss, and we treat weight \(\mathbf{w}\) as hyperparameter. Our goal is to learn a sample weight vector \(\mathbf{w}\) such that \(\mathbf{w}=0\) for OODs, \(\mathbf{w}=1\) for In-distribution (ID) sample.

Denote \(\mathcal{L}_{V}(\theta^{*}(\mathbf{w}),\mathbf{w})=\mathcal{L}_{V}(\theta^{*} (\mathbf{w}))+\lambda\cdot\text{Reg}(\mathbf{w})\) as the validation loss with a regularization term over the validation dataset, where \(\text{Reg}(\mathbf{w})\) is the regularization term, \(\lambda\) is the regularization coefficient, and \(\mathcal{L}_{V}(\theta^{*}(\mathbf{w}))\triangleq\sum_{(\mathbf{x}_{i},y_{i} )\in\mathcal{V}}l(f(\mathbf{x}_{i},\theta^{*}(\mathbf{w})),y_{i})\). This labeled set could either be a held-out validation set, or the original labeled set \(\mathcal{D}\). Intuitively, the problem given in Eq. (3.2) aims to choose weights of unlabeled samples \(\mathbf{w}\) that minimize the super

Figure 3.4: Main flowchart of the proposed Weighted Robust SSL algorithm.
vised loss evaluated on the validation set when the model parameters \(\theta^{*}(\mathbf{w})\) are optimized by minimizing the weighted SSL loss \(\mathcal{L}_{T}(\theta,\mathbf{w})\).

**Uncertainty-aware bi-level optimization objective.** Since manual tuning and grid-search for each \(w_{i}\) is intractable, we pose the weights optimization problem described above as a _bi-level_ optimization problem.

\[\min_{\mathbf{w}} \mathcal{L}_{V}(\theta^{*}(\mathbf{w}),\mathbf{w}),\] \[\text{s.t.} \theta^{*}(\mathbf{w})=\operatorname*{arg\,min}_{\theta} \mathcal{L}_{T}(\theta,\mathbf{w}). \tag{3.2}\]

where \(\mathcal{L}_{V}(\theta^{*}(\mathbf{w}),\mathbf{w})\) is the objective to optimize \(\mathbf{w}\). Based on the observation from Sec 3.3, we find that OOD data usually holds high vacuity uncertainty. Therefore, we design the inner loop objective function with an uncertainty regularization term,

\[\mathcal{L}_{V}(\theta^{*}(\mathbf{w}),\mathbf{w})=\mathcal{L}_{V}(\theta^{*} (\mathbf{w}))+\lambda\cdot\text{Un}(\mathbf{w},\mathbf{u}) \tag{3.3}\]

where \(\text{Un}(\mathbf{w},\mathbf{u})=\mathbf{u}(1-\mathbf{w})^{2}\) is the uncertainty regularization term, and \(\lambda\) is the regularization coefficient. Based on this design, the objective function will push the OOD sample with a large weight and push the in-distribution sample with a small weight.

Calculating the optimal \(\theta^{*}\) and \(\mathbf{w}\) requires two nested loops of optimization, which is expensive and intractable to obtain the exact solution (Franceschi et al., 2018), especially when optimization involves deep learning model and large datasets. Since gradient-based methods like Stochastic Gradient Descent (SGD) have shown to be very effective for machine learning and deep learning problems (Bengio, 2000), we adapt both high-order approximation and meta approximation strategies, as described in Sec 3.4.2.

#### 3.4.2 Bi-level Optimization Approximation

In this section, We developed two efficient bi-level algorithms that have different tradeoffs in computational efficiency and accuracy.
**Implicit Differentiation.** Directly calculate the weight gradient \(\frac{\partial\mathcal{L}_{V}(\theta^{*}(\mathbf{w}),\mathbf{w})}{\partial\mathbf{ w}}\) by chain rule:

\[\frac{\partial\mathcal{L}_{V}(\theta^{*}(\mathbf{w}),\mathbf{w})}{\partial \mathbf{w}}=\underbrace{\frac{\partial\mathcal{L}_{V}}{\partial\mathbf{w}}}_{(a )}+\underbrace{\frac{\partial\mathcal{L}_{V}}{\partial\theta^{*}(\mathbf{w})}}_ {(b)}\times\underbrace{\frac{\partial\theta^{*}(\mathbf{w})}{\partial \mathbf{w}}}_{(c)} \tag{3.4}\]

where (a) is the weight direct gradient (e.g., gradient from regularization term, \(\text{Reg}(\mathbf{w})\)), (b) is the parameter direct gradient, which is easy to compute. The difficult part is the term (c) (best-response Jacobian). We approximate (c) by using the Implicit function theorem (Lorraine et al., 2020),

\[\frac{\partial\theta^{*}(\mathbf{w})}{\mathbf{w}}=-\underbrace{\Big{[}\frac{ \partial\mathcal{L}_{T}}{\partial\theta\partial\theta^{T}}\Big{]}^{-1}}_{(d)} \times\underbrace{\frac{\partial\mathcal{L}_{T}}{\partial\mathbf{w}\partial \theta^{T}}}_{(e)} \tag{3.5}\]

However, computing Eq. (3.5) is challenging when using deep nets because it requires inverting a high dimensional Hessian (term (d)), which often requires \(\mathcal{O}(m^{3})\) operations. Therefore, we give the Neumann series approximations (Lorraine et al., 2020) of the term (d) which we empirically found to be effective for SSL,

\[\Big{[}\frac{\partial\mathcal{L}_{T}}{\partial\theta\partial\theta^{T}}\Big{]} ^{-1}\approx\lim_{P\rightarrow\infty}\sum_{p=0}^{P}\Big{[}I-\frac{\partial \mathcal{L}_{T}}{\partial\theta\partial\theta^{T}}\Big{]}^{p} \tag{3.6}\]

where \(I\) is the identity matrix.

Since the algorithm mentioned in (Lorraine et al., 2020) utilizes the Neumann series approximation and efficient Hessian vector product to compute the Hessian inverse product, it can efficiently compute the Hessian-inverse product even when a larger number of weight hyperparameters are present. We should also note that the implicit function theorem's assumption \(\frac{\partial\mathcal{L}_{T}}{\partial\theta}=0\) needs to be satisfied to accurately calculate the Hessian inverse product. However in practice, we only approximate \(\theta^{*}\), and simultaneously train both \(\mathbf{w}\) and \(\theta\) by alternatively optimizing \(\theta\) using \(\mathcal{L}_{T}\) and \(\mathbf{w}\) using \(\mathcal{L}_{V}\).

**Meta approximation.** Here we proposed the meta-approximation method to jointly update both network parameters \(\theta\) and hyperparameter \(\mathbf{w}\) in an iterative manner. At iteration
step \(t\), we approximate \(\theta_{t}^{*}\approx\theta_{t}^{J}\) on training set via low order approximation, where \(J\) is inner loop gradient steps, Eq. (3.7) shows each gradient step update,

\[\theta_{t}^{j}(\mathbf{w}_{t})=\theta_{t}^{j-1}-\alpha\nabla_{\theta}\mathcal{L }_{T}(\theta_{t}^{j-1},\mathbf{w}_{t}) \tag{3.7}\]

then we update hyperparameter \(\mathbf{w}_{t+1}\) on the basis of the net parameter \(\theta_{t}^{*}\) and weight \(\mathbf{w}_{t}\) obtained in the last iteration. To guarantee efficiency and general feasibility, the outer loop optimization to update weight is employed by one gradient step on the validation set \(\mathcal{V}\),

\[\mathbf{w}_{t+1}=\mathbf{w}_{t}-\beta\nabla_{\mathbf{w}}\mathcal{L}_{V}( \theta_{t}^{*},\mathbf{w}_{t}) \tag{3.8}\]

We analyze the convergence of the meta-approximation method and derive the following theorem.

**Theorem 2**.: _Suppose the validation function is Lipschitz smooth with constant \(L\), and the supervised loss and unsupervised loss have \(\gamma\)-bounded gradients, let the step size \(\alpha\) for \(\theta\) satisfies \(\alpha=\min\{1,\frac{k}{T}\}\) for some constant \(k>0\) such that \(\frac{k}{T}<1\) and \(\beta=\min\{\frac{1}{L},\frac{C}{\sqrt{T}}\}\) for some constant \(C>0\) such that \(\frac{\sqrt{T}}{C}\leq L\). Then, the meta approximation algorithm can achieve \(\mathbb{E}[\|\nabla_{\mathbf{w}}\mathcal{L}_{V}(\theta_{t})\|_{2}^{2}]\leq\epsilon\) in \(\mathcal{O}(1/\epsilon^{2})\) And more specifically,_

\[\min_{0\leq t\leq T}\mathbb{E}[\|\nabla_{\mathbf{w}}\mathcal{L}_{V}(\theta_{t} )\|_{2}^{2}]\leq\mathcal{O}(\frac{C}{\sqrt{T}}) \tag{3.9}\]

_where \(C\) is some constant independent to the convergence process._

Proof.: See Appendix A.3. 

**Complexity.** Compared with regular optimization on a the single-level problem, our robust SSL requires \(J\) extra forward and backward passes of the classifier network. To compute the weight gradient via bi-level optimization, Meta approximation requires extra forward and backward passes. Therefore, compared with the regular training procedures of SSL, our robust SSL with Meta approximation needs approximately \((2+J)\times\) training time. For
Implicit Differentiation, the training time is complex to estimate, we show the running time in Fig 3.9 (c) on the experiment part.

**Connections between implicit-differentiation and meta-approximation.**

**Proposition 2**.: _Suppose that the Hessian inverse of training loss \(\mathcal{L}_{T}\) with the model parameters \(\theta\) is equal to the identity matrix \(\frac{\partial^{2}\mathcal{L}_{T}}{\partial\theta\partial\theta^{T}}=\mathbf{I}\) (i.e.,\(P=0\) for implicit differentiation approach). Suppose the model parameters are optimized using single-step gradient descent (i.e., \(J=1\) for the low-order approximation approach), and the model learning rate is equal to one. Then, the weight update step in both implicit differentiation and low-order approximation approach is equal._

Proof.: See Appendix A.4. 

Proposition 2 shows that the weight gradient from implicit differentiation is the same as the weight gradient from the meta approximation method. Hence, the meta-approximation is the same as the Implicit differentiation method when \(P=0\). This also signifies that using larger \(P\) values for inverse Hessian estimations will use higher-order information and is more accurate. We designed these two efficient hyper-parameter optimization algorithms that have different trade-offs on computational efficiency and accuracy. Meta approximation was designed based on lower-order approximations of the objective in the inner loop of meta optimization due to vanishing gradients or memory constraints. Implicit Differentiation was designed based on higher-order approximations of the objective is more accurate than Meta approximation while at the same time being computationally more expensive.

#### 3.4.3 Weighted Batch Normalization

In practice, most deep SSL models would use deep CNN. While BN usually serves as an essential component for many deep CNN models (He et al., 2016; Huang et al., 2017). Specifically, BN normalizes input features by the mean and variance computed within each
mini-batch. At the same time, OODs would indeed affect the SSL performance due to BN (discussed this issue in Sec. 3.3). To address this issue, we proposed a _Weighted Batch Normalization_ (WBN) that performs the normalization for each training mini-batch with sample weights \(\mathbf{w}\). We present the WBN in Algorithm 2, where \(\epsilon\) is a constant added to the mini-batch variance for numerical stability.

**Proposition 3**.: _Give in-distribution mini-batch \(\mathcal{I}=\{\mathbf{x}_{i}\}_{i=1}^{m}\), OOD mini-batch \(\mathcal{O}=\{\hat{\mathbf{x}}_{i}\}_{i=1}^{m}\), and the mixed mini-batch \(\mathcal{IO}=\mathcal{I}\cup\mathcal{O}\). Denote \(\mu_{\mathcal{M}}\) is the mini-batch mean of \(\mathcal{M}\) (either \(\mathcal{O},\mathcal{I}\) or \(\mathcal{IO}\)). With faraway OOD: \(\|\mu_{\mathcal{O}}-\mu_{\mathcal{I}}\|_{2}>L\), where \(L\) is large (\(L\gg 0\)), we have:_

1. \(\|\mu_{\mathcal{IO}}-\mu_{\mathcal{I}}\|_{2}>\frac{L}{2}\) _and_ \(BN_{\mathcal{I}}(\mathbf{x}_{i})\neq BN_{\mathcal{IO}}(\mathbf{x}_{i})\)_;_
2. _Given perfect weights_ \(\mathbf{w}=\mathbf{w}_{\mathcal{I}}\cup\mathbf{w}_{\mathcal{O}}\)_, where_ \(\mathbf{w}_{\mathcal{I}}=\mathbf{1}\) _for mini-batch_ \(\mathcal{I}\) _and_ \(\mathbf{w}_{\mathcal{O}}=\mathbf{0}\) _for mini-batch_ \(\mathcal{O}\)_, then_ \(\mu_{\mathcal{I}}=\mu_{\mathcal{IO}}^{\mathbf{w}}\) _and_ \(BN_{\mathcal{I}}(\mathbf{x}_{i})=WBN_{\mathcal{IO}}(\mathbf{x}_{i},\mathbf{w})\)__

_where \(\mu_{\mathcal{IO}}^{\mathbf{w}}\) is the weighted mini-batch mean of \(\mathcal{IO}\), \(BN_{\mathcal{M}}(\mathbf{x}_{i})\) is traditional batch normalizing transform based on mini-batch from \(\mathcal{M}\) (either \(\mathcal{I}\) or \(\mathcal{IO}\)) and \(WBN_{\mathcal{IO}}(\mathbf{x}_{i},\mathbf{w})\) is weighted batch normalizing transform based on the set \(\mathcal{IO}\) with weights \(\mathbf{w}\)._

Proof.: See Appendix A.5. 

Proposition 3 shows that when an unlabeled set contains OODs, the traditional BN behavior could be problematic, therefore resulting in incorrect statistics estimation. e.g., the output of BN for mixed mini-bath \(BN_{\mathcal{IO}}(\mathbf{x}_{i})\approx\gamma\frac{\mathbf{x}_{i}-\mu_{\mathcal{O}} }{\|\mu_{\mathcal{O}}-\mu_{\mathcal{I}}\|_{2}}+\beta\), which is not our expected result (\(BN_{\mathcal{I}}(\mathbf{x}_{i})=\gamma\frac{\mathbf{x}_{i}-\mu_{\mathcal{I}}}{\sqrt {\sigma_{2}^{2}+\epsilon}}+\beta\)). While our proposed weighted batch normalization (WBN) can reduce the OOD effect and get the expected result. Therefore, our uncertainty-aware robust SSL framework uses WBN instead of BN if the model includes a BN layer. Ablation studies in Sec. 3.5 demonstrate that such our approach with WBN can improve performance further. Finally, our uncertainty-aware robust SSL framework is detailed in Algorithm 3.
#### 3.4.4 Additional Implementation Details:

In this subsection, we discuss additional implementational and practical tricks to make our weighted robust SSL scalable and efficient.

**Last-layer gradients.** Computing the gradients over deep models is time-consuming due to the enormous number of parameters in the model. To address this issue, we adopt a last-layer gradient approximation similar to (Ash et al., 2019; Killamsetty et al., 2021,?) by only considering the last classification layer gradients of the classifier model in inner loop optimization (step 10 in algorithm 3). By simply using the last-layer gradients, we achieve significant speedups in weighted robust SSL.

**Infrequent update w.** We update the weight parameters every \(L\) iterations (\(L>2\)). In our experiments, we see that we can set \(L=5\) without a significant loss in accuracy. For MNIST experiments, we can be even more aggressive and set \(L=20\).

**Weight Sharing and Regularization.** Considering the entire weight vector \(\mathbf{w}\) (overall unlabeled points) is not practical for large datasets and easily overfits (see ablation study
experiments), we propose two ways to fix this. The first is weight sharing via clustering, which we call Cluster Re-weight (CRW) method. Specifically, we use an unsupervised cluster algorithm (e.g., K-means algorithm) to embed unlabeled samples into \(K\) clusters and assign a weight to each cluster such that we can reduce the dimensionality of \(\mathbf{w}\) from \(|M|\) to \(|K|\), where \(|K|\ll|M|\). In practice, for high dimensional data, we may use a pre-trained model to calculate embedding for each point before applying the cluster method. In cases where we do not have an effective pre-trained model for embedding, we consider another variant that applies weights to every unlabeled point but considers an L1 regularization in Eq (3.2) for sparsity in \(\mathbf{w}\). We show that both these tricks effectively improve the performance of reweighting and prevent overfitting on the validation set.
### Experiment

To corroborate our algorithm, we conduct extensive experiments comparing our approaches (R-Meta and R-IFT) with some popular baseline methods. We aim to answer the following questions:

**Question 1:** Can our approach achieve better performance on both different types of OODs with varying OOD ratios compared with baseline methods?

**Question 2:** How does our approach compare in terms of running times compared with baseline methods?

**Question 3:** What is the effect of each of the components of our approach (e.g., WBN, clustering/regularization, inverse Hessian approximation, inner loop gradient steps)?

#### 3.5.1 Evaluation on Synthetic Dataset

We designed a synthetic experiment to illustrate how OODs affect SSL performance. The experimental setting is the same as the setting used in the section "Impact of OOD on SSL Performance". We used the Two Moons dataset with six labeled points and 2000 unlabeled (in-distribution) points and considered two OOD types, including faraway OODs and boundary OODs. We conducted the experiments with OOD ratio = \(\{25\%,50\%,75\%\}\) and reported the averaged accuracy rate with mean and standard deviation over ten runs. Table 3.4 shows that our robust SSL (named R-SSL-IFT (Implicit Differentiation) and R-SSL-Meta (Meta approximation)) is more effective than the four baselines on test accuracy. We also conducted experiments on additional synthetic datasets and observed similar trends of the results, as shown in Fig 3.5.

#### 3.5.2 Real-world Dataset Details

**Datasets.** We consider four image classification benchmark datasets. (1) **MNIST**: a handwritten digit classification dataset, with 50,000/ 10,000/ 10,000 training/validation/test sam
\begin{table}
\begin{tabular}{c|c c c} \hline \multirow{2}{*}{Model} & \multicolumn{3}{c}{_Faraway OODs_} \\  & 25\% & 50\% & 75\% \\ \hline Supervised & 84.4\(\pm\) 0.3 & 84.4\(\pm\) 0.3 & 84.4\(\pm\) 0.3 \\ SSL-NBN & 100.0\(\pm\) 0.0 & 100.0\(\pm\) 0.0 & 100.0\(\pm\) 0.0 \\ SSL-BN & 60.7\(\pm\) 1.5 & 50.0\(\pm\) 0.0 & 50.0\(\pm\) 0.0 \\ SSL-FBN & 89.7\(\pm\) 0.7 & 87.0\(\pm\) 1.1 & 81.0\(\pm\) 1.7 \\
**R-SSL-IFT** & **100.0\(\pm\) 0.0** & **100.0\(\pm\) 0.0** & **100.0\(\pm\) 0.0** \\
**R-SSL-Meta** & **100.0\(\pm\) 0.0** & **100.0\(\pm\) 0.0** & **100.0\(\pm\) 0.0** \\ \hline \multicolumn{4}{c}{_Boundary OODs_} \\  & 25\% & 50\% & 75\% \\ \hline Supervised & 84.4\(\pm\) 0.3 & 84.4\(\pm\) 0.3 & 84.4\(\pm\) 0.3 \\ SSL-NBN & 87.3\(\pm\) 0.3 & 83.4\(\pm\) 0.4 & 82.4\(\pm\) 0.5 \\ SSL-BN & 84.7\(\pm\) 0.4 & 82.3\(\pm\) 0.3 & 80.4\(\pm\) 0.5 \\ SSL-FBN & 89.7\(\pm\) 0.7 & 87.0\(\pm\) 1.1 & 81.0\(\pm\) 1.7 \\
**R-SSL-IFT** & **100.0\(\pm\) 0.0** & **100.0\(\pm\) 0.0** & **100.0\(\pm\) 0.0** \\
**R-SSL-Meta** & **100.0\(\pm\) 0.0** & **100.0\(\pm\) 0.0** & **100.0\(\pm\) 0.0** \\ \hline \end{tabular}
\end{table}
Table 3.4: Test accuracies for the two moons dataset (\(P=10,J=3\) for R-SSL-IFT and \(J=1\) for R-SSL-Meta).

Figure 3.5: Additional experiments on the synthetic dataset.
ples, with training data, split into two groups - labeled and unlabeled in-distribution (ID) images (labeled data has ten images per class), and with two types of OODs: a) Fashion MNIST, b) Mean MNIST (where the OOD instances are mean images of two classes, more details refer to see Appendix D); (2) **CIFAR10**: a natural image dataset with 45,000/ 5,000/ 10,000 training/validation/test samples from 10 object classes, and following (Oliver et al., 2018), we adapt CIFAR10 to a 6-class classification task, using 400 labels per class (from the 6 classes) and rest of the classes OOD (ID classes are "bird", "cat", "deer", "dog", "frog", "horse", and OOD data are from classes: "airline", "automobile", "ship", "truck"); (3) **CIFAR100**: another natural image dataset with 45,000/5000/10,000 training/validation/test images, similar to CIFAR10, we adapt CIFAR100 to a 50-class classification task, with 40 labels per class - the ID classes are the first 50 classes, and OOD data corresponds to the last 50 classes; (4) **SVHN-extra**: This is SVHN dataset with 531,131 additional digit images (Tarvainen and Valpola, 2017), and we adapt SVHN-extra to a 5-class classification task, using 400 labels per class. The ID classes are the first five classes, and OOD data corresponds to the last five classes.

**Comparing Methods.** To evaluate the effectiveness of our proposed weighted robust SSL approaches, we compare with five state-of-the-art robust SSL approaches, including UASD (Chen et al., 2020), DS3L (DS3L) (Guo et al., 2020), L2RW (Ren et al., 2018), and MWN (Shu et al., 2019). The last two approaches L2RW and MWN, were originally designed for robust supervised learning (SL), and we adapted them to robust SSL by replacing the supervised learning loss function with an SSL loss function. We compare these robust approaches on four representative SSL methods, including Pseudo-Label (PL) (Lee, 2013),

\begin{table}
\begin{tabular}{c|c c} \hline Model & _Faraway OODs_ & _Boundary OODs_ \\ \hline R-SSL-IFT P=1 & 55.0\(\pm\) 2.1 & 83.9\(\pm\) 0.7 \\ R-SSL-IFT P=5 & 91.0\(\pm\) 3.1 & 93.9\(\pm\) 0.9 \\ R-SSL-IFT P=10 & 100.0\(\pm\) 0.0 & **100.0\(\pm\) 0.0** \\ \hline \end{tabular}
\end{table}
Table 3.5: Test accuracies for different \(P\) at OOD ratio = 50% on the synthetic dataset.
\(\Pi\)-Model (PI) (Laine and Aila, 2016; Sajjadi et al., 2016), Mean Teacher (MT) (Tarvainen and Valpola, 2017), and Virtual Adversarial Training (VAT) (Miyato et al., 2018). One additional baseline is the supervised learning method, named "Sup," which ignored all the unlabeled examples during training. All the compared methods (except UASD (Chen et al., 2020)) were built upon the open-source Pytorch implementation1 by (Oliver et al., 2018). As UASD has not released its implementation, we implemented UASD by ourselves. For DS3L, we implemented it based on the released code 2. For L2RW (Ren et al., 2018), we used the open-source Pytorch implementation3and adapted it to the SSL settings. For MWN (Shu et al., 2019), we used the authors' implementation4 and adapt to SSL.

Footnote 1: [https://github.com/perrying/realistic-ssl-evaluation-pytorch](https://github.com/perrying/realistic-ssl-evaluation-pytorch)

Footnote 2: [https://github.com/guolz-ml/DS3L](https://github.com/guolz-ml/DS3L)

Footnote 3: [https://github.com/danieltan07/learning-to-reweight-examples](https://github.com/danieltan07/learning-to-reweight-examples)

Footnote 4: [https://github.com/xjtushujun/meta-weight-net](https://github.com/xjtushujun/meta-weight-net)

**Setup.** In our experiments, we implement our approaches (Ours-SSL) for four representative SSL methods, including Pseudo-Label (PL), \(\Pi\)-Model (PI), Mean Teacher (MT), and Virtual Adversarial Training (VAT). The term "SSL" in Ours-SSL represents the SSL method, e.g., (Ours-VAT denotes our weighted robust SSL algorithm implemented based on VAT. We used the standard LeNet model as the backbone for the MNIST experiment and used _WRN-28-2_(Zagoruyko and Komodakis, 2016) as the backbone for CIFAR10, CIFAR100, and SVHN experiments. For a comprehensive and fair comparison of the CIFAR10 experiment, we followed the same experiment setting of (Oliver et al., 2018). All the compared methods were built upon the open-source Pytorch implementation by (Oliver et al., 2018). The code and datasets are temporarily available for reviewing purposes at here5. Our code and datasets are also submitted as supplementary material.

Footnote 5: [https://anonymous.4open.science/r/WR-SSL-406F/README.md](https://anonymous.4open.science/r/WR-SSL-406F/README.md)
**Hyperparameter setting.** For our WR-SSL approach, we update the weights only using last layer for the inner optimization, we set \(J=3\) (for inner loop gradient steps), \(P=5\) (for inverse Hessian approximation), \(K=20\) (for CRW), \(\lambda=10^{-7}\) (for L1), and \(L=5\) (for infrequent update) for all experiments. We trained all the networks for 2,000 updates with a batch size of 100 for MNIST experiments, and 500,000 updates with a batch size of 100 for CIFAR10, CIFAR100, and SVHN experiments. We did not use any form of early stopping but instead continuously monitored the validation set performance and reported test errors at the point of the lowest validation error. We show the specific hyperparameters used with four representative SSL methods on MNIST experiments in Table 3.6. For CIFAR10, we

\begin{table}
\begin{tabular}{l c} \hline \hline \multicolumn{1}{c}{**Shared**} \\ \hline Learning decayed by a factor of & 0.2 \\ at training iteration & 1,000 \\ coefficient = 1 (Do not use warmup) & \\ \hline \multicolumn{1}{c}{**Supervised**} \\ \hline Initial learning rate & 0.003 \\ \hline \multicolumn{1}{c}{\(\Pi\)**-Model**} \\ \hline Initial learning rate & 0.003 \\ Max consistency coefficient & 20 \\ \hline \multicolumn{1}{c}{**Mean Teacher**} \\ \hline Initial learning rate & 0.0004 \\ Max consistency coefficient & 8 \\ Exponential moving average decay & 0.95 \\ \hline \multicolumn{1}{c}{**VAT**} \\ \hline Initial learning rate & 0.003 \\ Max consistency coefficient & 0.3 \\ VAT \(\epsilon\) & 3.0 \\ VAT \(\xi\) & \(10^{-6}\) \\ \hline \multicolumn{1}{c}{**Pseudo-Label**} \\ \hline Initial learning rate & 0.0003 \\ Max consistency coefficient & 1.0 \\ Pseudo-label threshold & 0.95 \\ \hline \hline \end{tabular}
\end{table}
Table 3.6: Hyperparameter settings used in MNIST experiments for four representative SSL. All robust SSL methods (e.g., ours (WR-SSL), DS3L, and UASD) are developed based on these representative SSL methods.
used the same hyperparameters as (Oliver et al., 2018). For CIFAR100 and SVHN datasets, we used the same hyperparameters as CIFAR10.

#### 3.5.3 Performance with different real-world OOD datasets

In all experiments, we report the performance over five runs. Denote OOD ratio\(=\mathcal{U}_{ood}/(\mathcal{U}_{ood}+\mathcal{U}_{in})\) where \(\mathcal{U}_{in}\) is ID unlabeled set, \(\mathcal{U}_{ood}\) is OOD unlabeled set, and \(\mathcal{U}=\mathcal{U}_{in}+\mathcal{U}_{ood}\).

**Impact of faraway OODs on SSL performance (with batch normalization).** We used FashionMNIST (Xiao et al., 2017) dataset to construct a set of OODs \(\mathcal{U}_{ood}\) faraway from the decision boundary of the MNIST dataset, as FashionMNIST and MNIST have been shown very different and considered as cross-domain benchmark datasets (Meinke and Hein, 2019). As shown in Fig 3.6 (a)-(b), with the OOD ratio increase, the performance of the existing SSL method decreases rapidly, whereas our approach can still maintain clear performance improvement, i.e., the outperformance of our methods are fairly impressive(e.g., 10% increase with R-IFT-PI over PI model when OOD ratio = 75%). Compare with other robust SSL methods, our methods surprisingly improves the accuracy and suffers much less degradation under a high OOD ratio.

**Impact of boundary OODs on SSL performance (without batch normalization).** We generate boundary OOD by mix up (fusion) existing ID unlabeled samples, i.e., \(\hat{\mathbf{x}}_{ood}=0.5(\mathbf{x}_{i}+\mathbf{x}_{j})\), where \(\mathbf{x}_{i}\), \(\mathbf{x}_{j}\) is ID images from a different class, and \(\hat{\mathbf{x}}_{ood}\) can be regarded as

Figure 3.6: Classification accuracy with varying OOD ratio on MNIST. (a)-(b) consider faraway OODs with batch normalization; (c)-(d) consider boundary OODs without batch normalization. Shaded regions indicate standard deviation.
boundary OOD (Guo et al., 2019). As shown in Fig 3.6 (c)-(d), we get a similar result pattern that the accuracy of existing SSL methods decreases when the OOD ratio increases. Across different OOD ratios, particularly our method significantly outperformed among all (e.g., 10% increase with Meta-VAT over VAT when OOD ratio = 75%). We also conduct experiments based on other SSL algorithms, results are shown in the supplementary material.

**Impact of mixed OODs on SSL performance (with batch normalization).** We followed (Oliver et al., 2018) to adapt CIFAR10 for a 6-class classification task, using 400 labels per class. The ID classes are: "bird", "cat", "deer", "dog", "frog", "horse", and OOD classes are: "airline", "automobile", "ship", "truck". As our implementation follows (Oliver et al., 2018) that freeze BN layers for the WRN model, we freeze BN layers for all the methods for CIFAR10 for fair comparisons. In this dataset, the examples of the OOD classes were considered as OODs. As these OODs are from the same dataset, it may have OODs close to or far away from the decision boundary of the ID classes. We hence called these OODs as mixed-type OODs. The averaged accuracy of all compared methods v.s. OOD ratio is plotted in Fig 3.7. Across different OOD ratios, particularly our method significantly outperformed among all, strikingly exceeding the performance when the OOD ratio is large (i.e., 4.5% increase with Ours-Meta over L2RW when OOD ratio = 75%).

Figure 3.7: Classification accuracy with varying OOD ratio on CIFAR10. We use _WRN-28-2_ (contains BN module) as the backbone. Shaded regions indicate standard deviation.
Unlike most SSL methods that degrade drastically when increasing the OOD ratio, ours achieves a stable performance even in a 75% OOD ratio.

#### Efficiency Analysis

To evaluate the efficiency of our proposed approach, we first compare the running time among all methods. Fig 3.8 (a)-(b) shows the running time (relative to the original SSL algorithm) for MNIST and CIFAR-10. We see that our proposed approaches are only \(1.7\times\) to \(1.8\times\) slower than the original SSL algorithm, while other robust SSL methods (L2RW and DS3L) are almost \(3\times\) slower. We note that our implementation tricks can also be applied to these other techniques (DS3L, L2RW, MWN), but this would possibly degrade performance since these approaches' performance is worse than ours even without these tricks. To further analyze our proposed speedup strategies, we plot the running time v.s. accuracy in Fig 3.8 (d)-(e) for different settings (with/without last and with/without infrequent updates). As expected, the results show that, without the only last layer updates and the infrequent updates (i.e. if \(L=1\)), Algorithm 3 is \(3\times\) slower than SSL baseline. Whereas with the last

Figure 3.8: Running time results. (a)-(b) show our proposed approaches are only \(1.7\times\) to \(1.8\times\) slower compared to base SSL algorithms, while other robust SSL methods are \(3\times\) slower. (c) shows that the running time of our method would increase with \(J\) (inner loop gradients steps) and \(P\) (inverse Hessian approximation) increase. (d)-(e) show the running time of our strategies with different combinations of tricks viz; last layer updates and updating weights every \(L\) iterations. Note that by using only last layer updates, our strategies are around \(2\times\) slower. With \(L=5\) and last layer updates, we are around \(1.7\times\) to \(1.8\times\) slower with comparable test accuracy.
layer updates, it is around \(2\times\) slower. We get the best trade-off between speed and accuracy considering both \(L=5\) and the last layer updates. In addition, we analyze the efficiency of our approach with varying inner loop gradient steps (\(J\)) and inverse Hessian approximation (\(P\)). The result shows that the running time of our method would increase with \(J\) and \(P\) increase, we choose the best trade-off between speed and accuracy considering \(J=3\) and \(P=5\).

Figure 3.10: (a) shows that WBN and CRW (or L1 regularization) are critical in retaining the performance gains of reweighting; (b)-(c) demonstrate that the performance of our approach would increase with (inner loop gradients steps) and inverse Hessian approximation) increase due to high-order approximation.

Figure 3.9: (a) shows that our method learns optimal weights for ID and OOD samples; (b) shows that our method is stable even for a small validation set containing 25 images.
#### 3.5.5 Additional Analysis

**Analysis of weight variation.** Fig 3.9 (a) shows the weight learning curve of our proposed approach and DS3L on Fashion-MNIST OOD. The results show that our method learns better weights for unlabeled samples compared to DS3L. The weight distribution learned in other cases are also similar.

**Size of the clean validation set.** We explore the sensitivity of the clean validation set used in robust SSL approaches on Mean MNIST OOD. Fig 3.9 (b) plots the classification performance with varying the size of the clean validation set. Surprisingly, our methods are stable even when using only 25 validation images, and the overall classification performance does not grow after having more than 1000 validation images.

**Ablation Studies.** We conducted additional experiments on Fashion-MNIST OOD (see Fig 3.10 (a)-(c)) in order to demonstrate the contributions of the key technical components, including Cluster Re-weight (CRW) and weighted Batch Normalization (WBN). The key

\begin{table}
\begin{tabular}{c|c c c}
**OOD ratio** & _25\%_ & _50\%_ & _75\%_ \\ \hline \hline VAT & 94.1\(\pm\) 0.5 & 93.6\(\pm\) 0.7 & 92.8\(\pm\) 0.9 \\ L2RW-VAT & 96.0\(\pm\) 0.6 & 93.5\(\pm\) 0.8 & 92.7\(\pm\) 0.8 \\ MWN-VAT & 96.2\(\pm\) 0.5 & 93.8\(\pm\) 1.1 & 93.0\(\pm\) 1.3 \\ DS3L-VAT & 96.4\(\pm\) 0.7 & 93.9\(\pm\) 1.0 & 92.9\(\pm\) 1.2 \\ Ours-VAT+L1 & 96.6\(\pm\) 0.6 & 94.4\(\pm\) 0.8 & 93.2\(\pm\) 1.1 \\ Ours-VAT+CRW & **96.8\(\pm\) 0.7** & **95.2\(\pm\) 0.9** & **94.9\(\pm\) 1.3** \\ \end{tabular}
\end{table}
Table 3.7: SVHN-Extra (VAT) with different OOD ratios.

\begin{table}
\begin{tabular}{c|c c c}
**OOD ratio** & _25\%_ & _50\%_ & _75\%_ \\ \hline \hline DS3L-MT & 60.8\(\pm\) 0.5 & 60.1\(\pm\) 1.1 & 57.2\(\pm\) 1.2 \\ Ours-MT+L1 & 61.5\(\pm\) 0.4 & 60.7\(\pm\) 0.6 & 59.0\(\pm\) 0.8 \\ Ours-MT+CRW & **62.1\(\pm\) 0.5** & **61.0\(\pm\) 0.5** & **59.7\(\pm\) 0.9** \\ \hline DS3L-PI & 60.5\(\pm\) 0.6 & 60.1\(\pm\) 1.0 & 57.4\(\pm\) 1.3 \\ Ours-PI+L1 & 61.2\(\pm\) 0.4 & 60.4\(\pm\) 0.4 & 58.9\(\pm\) 0.6 \\ Ours-PI+CRW & **61.6\(\pm\) 0.4** & **60.7\(\pm\) 0.5** & **59.5\(\pm\) 0.7** \\ \end{tabular}
\end{table}
Table 3.8: CIFAR100 (MT) with different OOD ratios.
findings obtained from this experiment are _1)_ WBN plays a vital role in our uncertainty-aware robust SSL framework to improve the robustness of BN against OOD data; _2)_ Removing CRW (or L1 regularization) results in performance decrease, especially for VAT based approach, which demonstrates that CRW (and L1 regularization) can further improve performance for our robust-SSL approach; _3)_ Fig 3.10 (b)-(c) demonstrate that the performance of our approach would increase with (inner loop gradients steps) and inverse Hessian approximation) increase due to high-order approximation. Based on this, we choose the best trade-off between speed and accuracy considering \(J=3\) and \(P=5\) when considering running time analysis in Fig 3.8 (c).

**L1 vs CRW tricks.** Next, we discuss the trade-offs between L1 and CRW. We first analyzed the sensitivity of our proposed CRW methods to the number of clusters used. Table 3.9 demonstrates the test accuracies of our approach with varying numbers of clusters. The results indicate a low sensitivity of our proposed methods to the number of clusters. We also find that CRW generally can further improve performance. Part of this success can be attributed to the good pretrained features (ImageNet). In addition, we compared our approach with the DS3L (safe SSL, SOTA robust SSL method) on CIFAR100 and SVHN dataset and get a similar pattern. The results are shown in Table 3.7 and 3.8.

### Conclusion

In this work, we first propose the research question: _How out-of-distribution data hurt semi-supervised learning performance?_ To answer this question, we study the impact of OOD data

\begin{table}
\begin{tabular}{c|c c c c} \# Clusters & K=5 & K=10 & K=20 & K =30 \\ \hline Ours-VAT & 94.7\(\pm\) 0.7 & 95.3\(\pm\) 0.4 & 96.3\(\pm\) 0.5 & 95.6\(\pm\) 0.5 \\ \hline Ours-PL & 95.2\(\pm\) 0.5 & 95.3\(\pm\) 0.5 & 96.2\(\pm\) 0.4 & 95.9\(\pm\) 0.5 \\ \end{tabular}
\end{table}
Table 3.9: Test accuracies for different numbers of clusters \(K\) on the MNIST dataset with 50% Mean MNIST as OODs.
on SSL algorithms and demonstrate empirically on synthetic data that the SSL algorithms' performance depends on how close the OOD instances are to the decision boundary (and the ID data instances). To address the above causes, we proposed a novel unified uncertainty-aware robust SSL framework that treats the weights directly as hyper-parameters in conjunction with weighted batch normalization, which is designed to improve the robustness of BN against OODs. To address the limitation of low-order approximations in bi-level optimization (DS3L), we designed an implicit-differentiation-based algorithm that considered high-order approximations of the objective and is scalable to a higher number of inner optimization steps to learn a massive amount of weight parameters. Next, we made our reweighting algorithms significantly more efficient by considering only last layer updates and infrequent weight updates, enabling us to have the same run time as simple SSL (naive reweighting algorithms are generally \(3\times\) more expensive). In addition, we conduct a theoretical analysis of the impact of faraway OODs in the BN step and discuss the connection between our approach (high-order approximation based on implicit differentiation) and low-order approximation approaches. We show that our weighted robust SSL approach significantly outperforms existing robust approaches (L2RW, MWN, Safe-SSL, and UASD) on several real-world datasets.

In Chapter 2 and Chapter 3, we studied the uncertainty quantification on graph and image data with a semi-supervised learning setting. However, the uncertainty framework used in Chapter 2 and Chapter 3 only focuses on multi-class classification and statics problems. Therefore, it can not extend to multi-label classification or time series problems. To this end, in the following Chapter, we will study a time series multi-label classification setting for early event detection. Specifically, we first propose a novel framework, Multi-Label Temporal Evidential Neural Network, to estimate the evidential uncertainty of multi-label time series classification. Then, we propose two novel uncertainty estimation heads to quantify the fused uncertainty of a sub-sequence for early event detection.
## Chapter 4 Multi-label temporal evidential neural networks for early event detection

### 4.1 Introduction

In recent decades, early detection of temporal events has aroused a lot of attention and has applications in a variety of industries, including security (Sai and Reddy, 2017), quality monitoring (He et al., 2020), medical diagnostic (Zhao et al., 2019), transportation (Gupta et al., 2020), _etc_. According to the time series, an event can be viewed with three components, pre-event, ongoing event, and post-event. Early event detection in machine learning identifies an event during its initial ongoing phase after it has begun but before it concludes (Hoai and De la Torre, 2014; Phan et al., 2018). As illustrated in Figure 4.1, given a video clip with multiple frames, the goal is to accurately and rapidly detect human action(s) in the box (_i.e._ smoke and watch a person) in the observation of incomplete video segments so that timely responses can be provided. This demands the detection of events prior to their completion.

To achieve the earliness of event detection, existing approaches can be broadly divided into several major categories. Prefix-based techniques (Gupta et al., 2020, 2020) aim to learn a minimum prefix length of the time series from the training instances and utilize it to classify a testing time series. Shapelet-based approaches (Yan et al., 2020; Zhao et al., 2019) focus on obtaining a set of key shapelets from the training dataset and utilizing them as class discriminatory features. Model-based methods for event early detection (Mori et al., 2019; Lv et al., 2019) are proposed to obtain conditional probabilities by either fitting a discriminative
classifier or using generative classifiers on training. Although these approaches address the importance of early detection, they primarily focus on an event with a single label but fail to be applied to situations with multiple labels.

Another non-negligible issue for early event detection is the prediction with overconfidence (Zhao et al., 2020; Sensoy et al., 2018). In general, the occurrence of an event is determined by its predicted probability. An event with a high probability is considered as an occurrence. This, however, may not be reliable. Figure 4.2 shows an example that the prediction of the occurrence of an event (_i.e._ an action) in a video clip with a binary class (occurs or not) based on its predicted probability is overconfident at the pre-event stage. In this case, the groundtruth (red line) demonstrates that the ongoing stage starts at the 20th frame. Nevertheless, the event is falsely detected, prior to it actually occurring (Figure 4.2, left), because a greater probability (_i.e._ 0.9 indicated on the green line) is given by positive evidence. Here, the evidence indicates data samples (_i.e._ actions) that are closest to the predicted one in the feature space and used to support the decision-making. Positive (negative) evidence is the observed samples that have the same (opposite) class labels. The event prediction with overconfidence at its early stage is due to high vacuity uncertainty (Josang,

Figure 4.1: How many frames do we need to detect smoke and watch actions reliably? Can we even detect these actions before they finish? Existing event detectors are trained to recognize complete events only; they require seeing the entire event for a reliable decision, preventing early detection. We propose a learning formulation to recognize partial events, enabling early detection.
2016) which is a terminology representing a lack of evidence. Therefore, it makes event detection based on probability unreliable. To overcome this flaw, methods developed on uncertainty estimation using evidence are desirable for early event detection.

In this work, to address the aforementioned issues, we first introduce a novel problem, namely _early event detection with multiple labels_. In the problem setting, a temporal data with multiple events occurs sequentially over time. The goal of this work is to accurately detect the occurrence of all events within the least amount of time. Inspired by (Sensoy et al., 2018) and subjective logic (SL) (Yager and Liu, 2008), a proposed framework is proposed, which is composed of two phases: in phase one, a time series data is viewed as a sequence of segments with equal temporal length, where each segment comes one after another. Instead of predicting occurrence probabilities for all events, their positive and negative evidence is estimated through the proposed Multi-Label Temporal Evidential Neural Network (MTENN). The positive and negative evidence is seen as parameters of a Beta distribution which is a conjugate prior to Binomial likelihood. In the second phase, a sliding window spanning the most recent collected segments is designed to validate whether an event is successfully detected through two novel uncertainty estimation heads: (1) Weighted Binomial Comultiplication (WBC), where the belief of the occurrence of an event is successively updated through a binomial comultiplication operation (Josang, 2016) from SL, and (2) Uncertainty Mean Scan Statistics (UMSS) for early event detection aims to detect the distribution change of the vacuity uncertainty through hypothesis testing from statistics. **Key contributions** of this work are summarized:

* We introduce a novel framework consisting of two phases for early event detection with multiple labels. At each timestamp, the framework estimates positive and negative evidence through the proposed Multi-Label Temporal Evidential Neural Network (MTENN). Inspired by subjective logic and belief theory, the occurrence uncertainty of an event is sequentially estimated over a subset of temporal segments.
* We introduce two novel uncertainty fusion operators (weighted binomial comultiplication (WBC) and uncertainty mean scan statistics (UMSS)) based on MTENN to quantify the fused uncertainty of a sub-sequence for early event detection. We demonstrate the effectiveness of WBC and UMSS on detection accuracy and detection delay, respectively.
* We validate the performance of our approach with state-of-the-art techniques on real-world audio and video datasets. Theoretic analysis and empirical studies demonstrate the effectiveness and efficiency of the proposed framework.

### 4.2 Related Work

**Early Event Detection** has been studied extensively in the literature of the time series domain. The primary task of it is to classify an incomplete time series event as soon as

Figure 4.2: Illustration of overconfidence prediction. (Left) The occurrence of the event is falsely detected at the pre-event stage prior to its starting. This indicates that predicted probabilities are not reliable due to insufficient evidence. (Right) Instead of probabilities, subjective opinions (_e.g.,_ belief, disbelief, uncertainty) are used in the proposed method for early event detection.
possible with some desired level of accuracy. (Gupta et al., 2020c) attempts to classify various complex human activities such as sitting on a sofa, sitting on the floor, standing while talking, walking upstairs, and eating, using only partial time series. A maximum-margin framework is proposed in (Hoai and De la Torre, 2014) for training temporal event detectors to recognize partial events, enabling early detection. The generative adversarial network introduced in (Wang et al., 2019) improves the early recognition accuracy of partially observed videos though narrowing the feature difference of partially observed videos from complete ones. Dual-DNN (Phan et al., 2018) is proposed for sound event early detection via a monotonous function design. (McLoughlin et al., 2018) identifies seed regions from spectrogram features to detect events at the early stage. Other algorithms have considered epistemic uncertainty for reliable event prediction (Soleimani et al., 2017). However, little attention has been paid to early event detection with multi-label settings, where multiple events may occur at the same time. Although there are several existing works designed for multi-label event detection (Pan et al., 2021; Tang et al., 2020), most of them cannot be applied to early detection event problems.

**Uncertainty Estimation.** In machine learning and data mining, researchers have mainly focused on aleatoric uncertainty and epistemic uncertainty using Bayesian Neural Networks for computer vision applications. Bayesian Neural Networks frameworks are presented to simultaneously estimate both aleatoric and epistemic uncertainty in regression (Gal and Ghahramani, 2016) and classification tasks (Kendall and Gal, 2017). However, aleatoric or epistemic uncertainty is not able to estimate evidence uncertainty, which is essential for early event detection. As for evidential uncertainty, its origins from the belief (or evidence) theory domain, such as Dempster-Shafer Theory (DST) (Sentz et al., 2002), or Subjective Logic (SL) (Josang, 2016). SL considered predictive uncertainty in subjective opinions in terms of _vacuity_(Josang, 2016). Evidential neural networks (ENN) was proposed in (Sensoy et al., 2018) to estimate evidential uncertainty for multi-class classification problem in the
deep learning domain. However, ENN is designed for single-label classification due to the subjective logic assumption.

To address the limitation of ENN and existing early event detection methods, we proposed a novel framework, namely Multi-Label Temporal Evidential Neural Network (MTENN), for early event detection in temporal data. MTENN is able to quality predictive uncertainty due to lack of evidence for multi-label classifications at each time stamp based on belief/evidence theory.

### Preliminaries

The introduction of subjective logic is in Sec 2.3.2 In this section, we start with Evidential neural networks (ENN) (Sensoy et al., 2018), a hybrid model of subjective logic and neural networks. Then we recap multi-label classification.

#### 4.3.1 Notations

A time series data \(\{(\mathbf{x}^{t},\mathbf{y}^{t})\}_{t=1}^{T}\in(\mathcal{X}\times\mathcal{Y})\) consists of \(T\) segments where each \((\mathbf{x}^{t},\mathbf{y}^{t})\) is collected one after another over time. \(\mathbf{x}^{t}\) represents the feature vector. \(\mathbf{y}^{t}=[y_{1}^{t},\dots,y_{K}^{t}]^{T}\) denotes the multi-label formula with \(y_{k}^{t}=\{0,1\},\forall k\in\{1,\cdots K\}\) representing an event occurs or not and \(K\) is the number of classes. Vectors are denoted by lower case bold face letters, _e.g._, class probability \(\mathbf{p}\in[0,1]^{T}\) where their \(i\)-th entries are \(p_{i}\). Scalars are denoted by lowercase italic letters, _e.g._\(u\in[0,1]\). Matrices are denoted by capital italic letters. \(\omega\) denotes the subjective opinion. We use subscripts to denote the index of the class, and we use superscripts to denote the index of the time stamp. Some important notations are listed in Table 4.1
#### 4.3.2 Evidential neural networks

Evidential neural networks (ENNs) (Sensoy et al., 2018) is a hybrid framework of subjective belief models (Josang, 2016) with neural networks. ENNs is designed to estimate the evidential uncertainty of classification problem. They are similar to classic neural networks for classification. The main difference is that the softmax layer is replaced with an activation function in ENNs, _e.g.,_ ReLU, to ensure non-negative output (range of \([0,+\infty)\)), which is taken as the evidence vector for the predicted Dirichlet (or Beta) distribution, or equivalently, multinomial (binomial) opinion.

Given of an input sample \(\mathbf{x}\), let \(f(\mathbf{x}|\mathbf{\theta})\) represent the evidence vector by the network for the classification, where \(\mathbf{\theta}\) is network parameters. Then the corresponding Dirichlet distribution has parameters \(\mathbf{\alpha}=f(\mathbf{x}_{i}|\mathbf{\theta})\), where \(\mathbf{\alpha}=[\alpha_{1},\ldots,\alpha_{K}]\), \(K\) is the number of classes. Let \(\mathbf{p}=(p_{1},\ldots,p_{K})^{T}\) be the class probabilities, which can be sampled from the

\begin{table}
\begin{tabular}{l|l} \hline \hline
**Notations** & **Descriptions** \\ \hline \(\mathcal{B}\) & Segment buffer \\ \(\mathbf{x}^{t}\) & feature vector for segment \(t\) \\ \(\mathbf{y}^{t}\) & multi-label for segment \(t\) \\ \(\mathbf{p}^{t}\) & Class probability for segment \(t\) \\ \(\mathbf{\theta}\) & model parameters \\ \(\omega\) & Subjective opinion \\ \(b\) & Belief mass \\ \(d\) & Disbelief mass \\ \(u\) & Vacuity uncertainty \\ \(a\) & Base rate \\ \(\alpha_{k}^{t}\) & Positive evidence at segment \(t\) for class \(k\) \\ \(\beta_{k}^{t}\) & Negative evidence at segment \(t\) for class \(k\) \\ \(K\) & Number of classes \\ \(\mathbf{c}\) & Opinion weight in WBC \\ \(f(\cdot)\) & MTENN model function \\ \(\psi(\cdot)\) & Digamma function \\ \(\mathbf{Beta}(p|\alpha,\beta)\) & PDF of Beta distribution \\ \(\mathbf{BCE}(\cdot)\) & binary cross-entropy loss \\ \hline \hline \end{tabular}
\end{table}
Table 4.1: Important notations and corresponding descriptions.
Dirichlet distribution. Therefore, the output of an ENNs can be applied to measure the evidential uncertainty about the predictive class variable \(\mathbf{y}\), such as vacuity. Usually, we consider the following loss function (Sensoy et al., 2018) to train an ENNs model:

\[\mathcal{L}_{ENN}=\int\Big{[}\sum_{i=1}^{K}-y_{i}\log(p_{i})\Big{]}\mathbf{Dir} (p|\mathbf{\alpha})dp \tag{4.1}\]

#### 4.3.3 Multi-label classification

In machine learning and data mining, multi-class classification is a learning problem where each data sample is associated with a unique label from a set of disjoint classes. The single-label classification problem can be divided to binary classification or multi-class classification depending on the number of classes. Unlike multi-class classification problems, multi-label classification allows each data sample belongs to more than one class. Similar to deep learning models for multi-label classification where they typically use a sigmoid layer on top of deep neural networks for each of class, for time series data, a temporal multi-label classifier is considered to handle the temporal dependency between segments collected at each timestamp. Both traditional binary and multi-class problems can be posed as specific cases of multi-label problems. For most single-label classification methods, cross-entropy is used as the loss function. In contrast, for multi-label classification problems, traditional multi-label temporal neural networks take binary cross entropy as the objective function,

\[\mathcal{L}_{ML} = \sum_{t=1}^{T}\sum_{k=1}^{K}\mathbf{BCE}(y_{k}^{t},p_{k}^{t}) \tag{4.2}\] \[= \sum_{t=1}^{T}\sum_{k=1}^{K}-y_{k}^{t}\log(p_{k}^{t})-(1-y_{k}^{t })\log(1-p_{k}^{t})\]

where \(\mathbf{BCE}(\cdot)\) is the binary cross-entropy loss.

### Problem Formulation

Given a time series data with multiple labels (_e.g._ a person in a video clip has multiple actions) where each class label is viewed as an event, let \(\mathcal{X}\times\mathcal{Y}\) be the data space, where
\(\mathcal{X}\) is an input space and \(\mathcal{Y}=\{0,1\}^{K}\) is an output space. A time series data \(\{(\mathbf{x}^{t},\mathbf{y}^{t})\}_{t=1}^{T}\in(\mathcal{X}\times\mathcal{Y})\) consists of \(T\) segments where each \((\mathbf{x}^{t},\mathbf{y}^{t})\) is collected one after another over time. \(\mathbf{x}^{t}\) represents the feature vector. \(\mathbf{y}^{t}=[y_{1}^{t},\ldots,y_{K}^{t}]^{T}\) denotes the multi-label formula with \(y_{k}^{t}=\{0,1\},\forall k\in\{1,\cdots K\}\) representing an event occurs or not and \(K\) is the number of classes. A segment buffer \(\mathcal{B}\) is initialized as empty. It is maintained by adding each segment one at a time. That is, at timestamp \(t\), the buffer includes all segments from previous \(\mathcal{B}=\{(\mathbf{x}^{i},\mathbf{y}^{i})\}_{i=1}^{t}\) and \(|\mathcal{B}|=t\). At each time, a predictive model \(f:\mathcal{X}\rightarrow\mathcal{Y}\) parameterized by \(\boldsymbol{\theta}\) takes segments in \(\mathcal{B}\) as the input and outputs a event prediction vector \(\hat{\mathbf{y}}^{t}=[\hat{y}_{1}^{t},\ldots,\hat{y}_{K}^{t}]^{T}\) where \(\hat{y}_{k}^{t}\in\{0,1\}\) represents the predicted result of the \(k\)-th event at time \(t\) (1 represents occurrence 0 otherwise). Therefore, for some events which are predicted as occurrences, one may conclude that they can be detected at time \(t\).

In the following sections, as demonstrated in Figure 4.3, we propose a novel framework for early event detection, that is Multi-label Temporal Evidential Neural Networks (MTENN) followed by sequential uncertainty estimation. This framework is composed of two phases. In the first phase, the data is viewed as a sequence of segments with equal temporal length, where each segment comes one after another over time. At the time \(t\), instead of the prediction result \(\hat{\mathbf{y}}^{t}\), a pair of vectors consisting of positive evidence \(\boldsymbol{\alpha}^{t}\) and negative evidence \(\boldsymbol{\beta}^{t}\) are estimated. They can be seen as parameters of a Beta distribution which is a conjugate prior to Binomial likelihood. In the second phase, a sliding window including \(m\) most recent collected segments is used to validate whether an event is successfully detected through an early detection function. The function maps a sequence of \(\{\boldsymbol{\alpha}^{i},\boldsymbol{\beta}^{i}\}_{i=t-m}^{t}\) in the window and outputs a subjective opinion for all events by recursively combining a set of opinions of each segment. The integrated opinion is used to determine the occurrence of each event.
### Multi-Label Temporal Evidential Neural Networks

In this section, we introduce the proposed Multi-Label Temporal Evidential Neural Networks (MTENN) Framework for reliable early event detection. The overall description of the framework is shown in Figure 4.3.

#### MTENN Framework

For multi-label early event detection, most existing methods would consider a binary classification for each class, such as sigmoid output (Turpault et al., 2019; Hershey et al., 2021). As discussed in Section 4.3, evidential uncertainty can be derived from binomial opinions or Beta distributions to model an event distribution for each class. Therefore, we proposed a novel Multi-label Evidential Temporal Neural Network (MTENN) \(f(\cdot)\) to form their binomial opinions for the class-level Beta distribution of a given time series segments \([\mathbf{x}^{1},\ldots,\mathbf{x}^{t}]\). Then, the conditional probability \(P(p_{k}^{t}|\mathbf{x}^{1},\ldots,\mathbf{x}^{t};\mathbf{\theta})\) of class \(k\) at timestamp \(t\) can be ob

Figure 4.3: **Framework Overview. Given the streaming data, (b) MTENN is able to quality predictive uncertainty due to a lack of evidence for multi-label classifications at each time stamp based on belief/evidence theory. Specifically, (a) at each time step with data segment \(x^{t}\), MTENN is able to predict Beta distribution for each class, which can be equivalent transfer to subjective opinion \(\omega_{t}\); (c) based on a sliding window, two novel fusion operators (weighted binomial comultiplication and uncertainty mean scan statistics) are introduced to quantify the fused uncertainty of a sub-sequence for an early event.**
tained by:

\[[f^{1},\ldots,f^{t}] \leftarrow f(\mathbf{x}^{1},\ldots,\mathbf{x}^{t};\boldsymbol{\theta})\] \[(\alpha_{1}^{t},\beta_{1}^{t}),\ldots,(\alpha_{K}^{t},\beta_{K}^{t}), \leftarrow f^{t}(\mathbf{x}^{1},\ldots,\mathbf{x}^{t};\boldsymbol{\theta}),\] \[p_{k}^{t} \sim \mathbf{Beta}(p_{k}^{t}|\alpha_{k}^{t},\beta_{k}^{t}),\] \[y_{k}^{t} \sim \mathbf{Bernoulli}(p_{k}^{t}), \tag{4.3}\]

where \(k\in\{1,\cdots,K\}\), \(t\in\{1,\cdots,T\}\), \(f^{t}\) is the output of MTENN at timestamp \(t\), and \(\boldsymbol{\theta}\) refers to model parameters. \(\mathbf{Beta}(p^{t}|\alpha_{k}^{t},\beta_{k}^{t})\) is the Beta probability function. Note that MTENN is similar to the classical multi-label time classification model (e.g., CRNN (Turpault et al., 2019)), except that we use an activation layer (e.g., ReLU) instead of the sigmoid layer (only outputs class probabilities). This ensures that MTENN would output non-negative values taken as the evidence for the predicted Beta distribution. Therefore, MTENN is able to quality predictive uncertainty (vacuity) due to a lack of evidence for multi-label classifications at each time stamp based on belief/evidence theory, and vacuity can be calculated from the estimated Beta distribution.

#### 4.5.2 Loss

In this work, we design and train MTENN to form their binomial opinions for the classification of a given streaming segment as a Beta distribution. For the binary cross-entropy loss, we have the MTENN loss by computing its Bayes risk for the class predictor,

\[\mathcal{L}_{MTENN} = \sum_{t=1}^{T}\sum_{k=1}^{K}\int\Big{[}\mathbf{BCE}(y_{k}^{t},p_{ k}^{t})\Big{]}\mathbf{Beta}(p_{k}^{t};\alpha_{k}^{t},\beta_{k}^{t})dp_{k}^{t} \tag{4.4}\] \[= \sum_{t=1}^{T}\sum_{k=1}^{K}\Big{[}y_{k}^{t}\Big{(}\psi(\alpha_{k }^{t}+\beta_{k}^{t})-\psi(\alpha_{k}^{t})\Big{)}\] \[+(1-y_{k}^{t})\Big{(}\psi(\alpha_{k}^{t}+\beta_{k}^{t})-\psi( \beta_{k}^{t})\Big{)}\Big{]},\]

where \(\mathbf{BCE}(y_{k}^{t},p_{k}^{t})=-y_{k}^{t}\log(p_{k}^{t})-(1-y_{k}^{t})\log (1-p_{k}^{t})\) is the binary cross-entropy loss, and \(\psi(\cdot)\) is the _digamma_ function. The log expectation of Beta distribution derives the second
equality. The details of the first phase of our proposed framework for MTENN are shown in Algorithm 4.

```
Input: A time series data \(\{(\mathbf{x}^{t},\mathbf{y}^{t})\}_{t=1}^{T}\) Output: Model params: \(\boldsymbol{\theta}\)
1 Set \(t=0\); learning rate \(\alpha\);
2 Initialize model parameters \(\boldsymbol{\theta}\);
3repeat
4 Estimate the Beta distribution via Eq. (4.3);
5 Calculate the gradient \(\nabla_{\boldsymbol{\theta}}\mathcal{L}_{MTENN}\) via Eq. (4.4);
6 Update net parameters
7\(\boldsymbol{\theta}_{t+1}=\boldsymbol{\theta}_{t}-\alpha\nabla_{\boldsymbol{ \theta}}\mathcal{L}_{MTENN}(\boldsymbol{\theta}_{t})\)
8\(t=t+1\)
9untilconvergence return\(\boldsymbol{\theta}_{t+1}\)
```

**Algorithm 4**MTENN-Phase I

#### Theoretical Analysis

In this section, we demonstrate two main theoretical results. First, traditional evidential neural networks (ENN) can be posed as specific cases of multi-label temporal evidential neural networks. Second, traditional multi-label temporal neural networks (MTNN) can be posed as specific cases of multi-label Temporal Evidential neural networks (MTENN) when training data has large evidence for each class. Theorem 4 shows that the loss function in MTENN is equivalent to it in MTNN when sufficient evidence is observed. Furthermore, given a feature vector, MTNN predicts probabilities for each class, while MTENN outputs positive and negative evidence estimations (\(\alpha\) and \(\beta\)) that can be seen as parameters of a Beta distribution. Statistically, the predicted class probabilities are sampled from a Beta probability density function parameterized by the estimated \(\alpha\) and \(\beta\). When uncertainty mass approaches zero, the variance of sampled class probabilities is small and close to its expectation \(\frac{\alpha}{\alpha+\beta}\). As a consequence, one may infer the probability of each class using the predicted evidence from MTENN, which is equivalent to the output of MTNN. The results
indicate that our proposed MTENN is a generalization of ENN and MTNN and has thus inherited the merits of both models for the task of early event detection.

**Theorem 3**.: _Denote \(\mathcal{L}_{ML}\) is the loss function of traditional multi-label temporal neural networks, \(\mathcal{L}_{TMENN}\) is the loss function of multi-label Temporal Evidential neural networks, and \(u\) is the vacuity uncertainty estimated form MTENN. We have \(\lim_{\alpha\rightarrow\infty,\beta\rightarrow\infty}|\mathcal{L}_{ML}- \mathcal{L}_{MTENN}|\to 0\)._

Proof.: When \(\alpha\rightarrow\infty\), we have

\[\psi(\alpha_{k}^{t}+\beta_{k}^{t})-\psi(\alpha_{k}^{t})\] \[\xrightarrow{\alpha\rightarrow\infty}\ln(\alpha_{k}^{t}+\beta_ {k}^{t})-\frac{1}{2(\alpha_{k}^{t}+\beta_{k}^{t})}-\ln(\alpha_{k}^{t})+\frac{ 1}{2\alpha_{k}^{t}}\] \[=-\ln(\frac{\alpha_{k}^{t}}{\alpha_{k}^{t}+\beta_{k}^{t}})+\frac {1}{2\alpha_{k}^{t}}-\frac{1}{2(\alpha_{k}^{t}+\beta_{k}^{t})}\] \[\xrightarrow{\alpha\rightarrow\infty}-\ln(\frac{\alpha_{k}^{t}} {\alpha_{k}^{t}+\beta_{k}^{t}})=-\ln p_{k}^{t}\]

and when \(\beta\rightarrow\infty\), we have

\[\psi(\alpha_{k}^{t}+\beta_{k}^{t})-\psi(\beta_{k}^{t})\] \[\xrightarrow{\beta\rightarrow\infty}\ln(\alpha_{k}^{t}+\beta_ {k}^{t})-\frac{1}{2(\alpha_{k}^{t}+\beta_{k}^{t})}-\ln(\beta_{k}^{t})+\frac{ 1}{2\beta_{k}^{t}}\] \[=-\ln(\frac{\beta_{k}^{t}}{\alpha_{k}^{t}+\beta_{k}^{t}})+\frac{ 1}{2\beta_{k}^{t}}-\frac{1}{2(\alpha_{k}^{t}+\beta_{k}^{t})}\] \[\xrightarrow{\beta\rightarrow\infty}-\ln(\frac{\beta_{k}^{t}} {\alpha_{k}^{t}+\beta_{k}^{t}})=-\ln(1-p_{k}^{t})\]

where the expected probability \(p_{k}^{t}=\frac{\alpha_{k}^{t}}{\alpha_{k}^{t}+\beta_{k}^{t}}\). Then we have \(|\mathcal{L}_{ML}-\mathcal{L}_{MTENN}|\to 0\). 

**Theorem 4**.: _Denote \(\mathcal{L}_{ENN}\) is the loss function of traditional evidential neural networks, \(\mathcal{L}_{Beta}\) is the loss function of multi-label Temporal Evidential neural networks, and \(K\) is the total number of the class. We have \(\mathcal{L}_{ENN}=\mathcal{L}_{MTENN}\) when \(K=1,T=1\)._
Proof.: When \(K=1,T=1\), we have

\[\mathcal{L}_{TMENN}=\sum_{t=1}^{1}\sum_{k=1}^{1}\int\Big{[}\mathbf{ BCE}(y_{k}^{t},p_{k}^{t})\Big{]}\mathbf{Beta}(p_{k}^{t};\alpha_{k}^{t},\beta_{k}^{ t})dp_{k}^{t}\] \[=\int\Big{[}\mathbf{BCE}(y,p)\Big{]}\mathbf{Beta}(p;\alpha,\beta )dp\] \[=y\Big{(}\psi(\alpha+\beta)-\psi(\alpha)\Big{)}+(1-y)\Big{(}\psi( \alpha+\beta)-\psi(\beta)\Big{)}\]

and for the ENN model, \(k=1\) means the binary classification, and we denote the positive evidence \(\alpha=\alpha_{1}\), negative evidence \(\beta=\alpha_{2}\), positive label \(y=y_{1}\), and negative label \((1-y)=y_{2}\)

\[\mathcal{L}_{ENN}=\int\Big{[}\mathbf{CrossEntopy}(y,p)\Big{]} \mathbf{Dir}(p;\alpha)dp\] \[=\sum_{j=1}^{2}y_{j}\Big{(}\psi(\sum_{j=1}^{2}\alpha_{j})-\psi( \alpha_{j})\Big{)}\] \[=y\Big{(}\psi(\alpha+\beta)-\psi(\alpha)\Big{)}+(1-y)\Big{(}\psi (\alpha+\beta)-\psi(\beta)\Big{)}\]

Then we proof that \(\mathcal{L}_{ENN}=\mathcal{L}_{TMENN}\). 

### Multi-label Sequential Uncertainty Quantittation

In the second phase, for early event detection, at time \(t\), a subset including \(m\) most recent collected segments are considered to validate whether an event is successfully detected or not, as shown in Fig 4.3 (c). We name the subset as a sliding window, as it dynamically restructures a small sequence of segments from \(t-m\) to \(t\) and performs validation through an early detection function at each time. Based on the sliding window, we introduce two novel uncertainty fusion operators based on MTENN to quantify the fused uncertainty of a sub-sequence for early event detection.
#### 4.6.1 Weighted Binomial Comultiplication

**Binomial Comultiplication Operator.** After we get the sequential Beta distribution output, a sequential fusional opinion can be estimated via a subjective operator (e.g., union operator). As shown in Fig 4.3 (b), we can use subjective operator \(\oplus\) to fuse the opinions. Here we consider to use comultiplication operator (Josang, 2006) to fusion two opinion \(\omega_{i}\) and \(\omega_{j}\) via Eq. (4.5),

\[\begin{split}& b_{i\oplus j}=b_{i}+b_{j}-b_{i}b_{j}\\ & d_{i\oplus j}=d_{i}d_{j}+\frac{a_{i}\left(1-a_{j}\right)d_{i}u_ {j}+\left(1-a_{i}\right)a_{j}u_{i}d_{j}}{a_{i}+a_{j}-a_{i}a_{j}}\\ & u_{i\oplus j}=u_{i}u_{j}+\frac{a_{j}d_{i}u_{j}+a_{i}u_{i}d_{j}}{ a_{i}+a_{j}-a_{i}a_{j}}\\ & a_{i\oplus j}=a_{i}+a_{j}-a_{i}a_{j}\end{split} \tag{4.5}\]

Based on \(m\) sliding windows, the sequential fusional opinion can be calculated by

\[\omega_{t-m,\ldots,t}=\omega_{t-m}\oplus\omega_{t-m+1}\oplus\ldots\oplus \omega_{t} \tag{4.6}\]

The above operator ignores the order information, which means \(\omega_{x}\oplus\omega_{y}\) has the same effect as \(\omega_{y}\oplus\omega_{x}\). To consider the order information and emphasize the importance of current time step \(t\), we propose a weighted comultiplication operator that assigns the weight \(\mathbf{c}\) for each opinion when executing the operator, then the weighted sequential opinion can be obtained,

\[\hat{\omega}^{t}=c_{t-m}\cdot\omega^{t-m}\oplus c_{t-m+1}\cdot\omega^{t-m+1} \oplus\ldots\oplus c_{t}\cdot\omega^{t} \tag{4.7}\]

We consider the vacuity from \(\hat{\omega}^{t}\) as sequential uncertainty for a sub-sequence.

**Uncertainty-based Inference.** At the test stage, we consider a simple strategy to make a reliable prediction based on the sequential uncertainty estimated from WBC. For each class, we predict sound events happened only when the belief is larger than disbelief
\[\hat{y}_{k}^{t}=\begin{cases}1,&\text{if $b_{k}^{t}>d_{k}^{t}$ and $u_{k}^{t}<V$}\\ 0,&\text{otherwise}\end{cases} \tag{4.8}\]

where \(\hat{y}_{k}^{t}\in\{0,1\}\) is the model prediction for class \(k\) in segment \(t\), \(V\) is the vacuity threshold.

#### Uncertainty mean scan statistics.

Intuition: uncertainty distribution changes at the early ongoing event stage. One example is shown in Fig 4.4. Here we proposed a simple uncertainty fusion operator based on the mean scan statistics method for early event detection. Let \(u_{t}\) be the vacuity uncertainty at time \(t\) and \(T\) be the sliding window size. Let \(S_{t}\) be the sliding window at time \(t\): \(S_{t}=\{u_{t-T+1},u_{t-T+2},\ldots,u_{t}\}\). We consider the following hypothesis testing about the detection of an event at time \(t\).

* **Null hypothesis \(H_{0}\):** The uncertainty at \(S_{t}\) follow the distribution \(u\in\mathcal{N}(0,1),\forall u\in S_{t}\)
* **Alternative hypothesis \(H_{1}\):** The uncertainty at \(S_{t}\) follow the distribution \(u\in\mathcal{N}(\mu,1),\forall u\in S_{t}\) with \(\mu>0\)

Figure 4.4: Uncertainty distribution changed at the ongoing event early stage.
Based on the above hypothesis testing, we can derive the log-likelihood ratio, called positive alleviated mean scan statistic (EMS), that is used as the test statistic for event detection. The larger the test statistic, the higher the chance there is an event in this time window.

\[\hat{u}_{t}=\frac{\sum_{u\in S_{t}}u_{i}}{T} \tag{4.9}\]

After we get the scan statistic score \(\hat{u}_{t}\), we need to decide a threshold, i.e., \(V\), such that we will reject \(H_{0}\) and accept \(H_{1}\) if \(\hat{u}_{t}>V\), based on the confidence level, and such as 0.05. In order to decide the threshold \(V\), we use Monte Carlo sampling as follows: We calculate the EMS statistics scores for all historical windows that have no event, we call them historical windows under \(H_{0}\), and find the 5% quantile value, i.e., the value, such that the number of historical windows under \(H_{0}\) less than this value is 5% of the total number of historic windows. The details of the second phase of our framework for early event detection are shown in Algorithm 5.

### Experiments

Our experimental section aims to verify the effectiveness of our proposed method (MTENN) by evaluating MTENN through both _early sound event detection_ scenario and _early human action detection_ scenario on real-world datasets. Furthermore, our work's experimental scenarios are very relevant in terms of research and real-world applications. Finally, we have implemented the MTENN framework using PyTorch. We repeat the same experiment for three runs with different initialization and report the mean detection delay and detection F1 score (ref to Evaluation Metrics section).

#### 4.7.1 Experiment Details

**Dataset.**_a) Early sound event detection task_, we conduct the experiments on DESED2021 dataset (Turpault et al., 2019) and AudioSet-Strong-Labeled dataset (Hershey et al., 2021).
**Algorithm 5**: MTENN-Phase II

**Algorithm 4.2**: Description of datasets and their experimental setup for the early event detection.

\begin{table}
\begin{tabular}{l|c|c|c|c|c|c} \hline  & **DESED2021** & **Explosion** & **Alarm** & **Liquid** & **Engine** & **AVA** \\ \hline \# Classes & 10 & 5 & 7 & 9 & 8 & 60 \\ \hline \# Training samples & 10,000 & 5,518 & 8,085 & 6,517 & 18,741 & 43,232 \\ \# Validation samples & 1,168 & 788 & 1,355 & 931 & 2,677 & 20,000 \\ \# Test samples & 1,016 & 1,577 & 2,311 & 1,862 & 5,354 & 23,498 \\ \hline \end{tabular} DESED2021 dataset is composed of 10 second audio clips recorded in domestic environments or synthesized using Scaper to simulate a domestic environment. The original AudioSet-Strong-Labeled dataset consists of an expanding ontology of 632 audio event classes and a collection of 2,084,320 human-labeled 10-second sound clips drawn from YouTube videos. To simulate the application of early event detection in industries, we select some subsets from the AudioSet-Strong-Labeled dataset to form early event detection datasets. Specifi

\begin{table}
\begin{tabular}{l|c|c|c|c} \hline  & **DESED2021** & **Explosion** & **Alarm** & **Liquid** & **Engine** & **AVA** \\ \hline \# Classes & 10 & 5 & 7 & 9 & 8 & 60 \\ \hline \# Training samples & 10,000 & 5,518 & 8,085 & 6,517 & 18,741 & 43,232 \\ \# Validation samples & 1,168 & 788 & 1,355 & 931 & 2,677 & 20,000 \\ \# Test samples & 1,016 & 1,577 & 2,311 & 1,862 & 5,354 & 23,498 \\ \hline \end{tabular} DESED2021 dataset is composed of 10 second audio clips recorded in domestic environments or synthesized using Scaper to simulate a domestic environment. The original AudioSet-Strong-Labeled dataset consists of an expanding ontology of 632 audio event classes and a collection of 2,084,320 human-labeled 10-second sound clips drawn from YouTube videos. To simulate the application of early event detection in industries, we select some subsets from the AudioSet-Strong-Labeled dataset to form early event detection datasets. Specifi

\begin{table}
\begin{tabular}{l|c|c|c} \hline  & **DESED2021** & **Explosion** & **Alarm** & **Liquid** & **Engine** & **AVA** \\ \hline \# Classes & 10 & 5 & 7 & 9 & 8 & 60 \\ \hline \# Training samples & 10,000 & 5,518 & 8,085 & 6,517 & 18,741 & 43,232 \\ \# Validation samples & 1,168 & 788 & 1,355 & 931 & 2,677 & 20,000 \\ \# Test samples & 1,016 & 1,577 & 2,311 & 1,862 & 5,354 & 23,498 \\ \hline \end{tabular} DESED2021 dataset is composed of 10 second audio clips recorded in domestic environments or synthesized using Scaper to simulate a domestic environment. The original AudioSet-Strong-Labeled dataset consists of an expanding ontology of 632 audio event classes and a collection of 2,084,320 human-labeled 10-second sound clips drawn from YouTube videos. To simulate the application of early event detection in industries, we select some subsets from the AudioSet-Strong-Labeled dataset to form early event detection datasets. Specifi

\begin{table}
\begin{tabular}{l|c} \hline  & **DESED2021** & **Explosion** & **Alarm** & **Liquid** & **Engine** & **AVA** \\ \hline \# Classes & 10 & 5 & 7 & 9 & 8 & 60 \\ \hline \# Training samples & 10,000 & 5,518 & 8,085 & 6,517 & 18,741 & 43,232 \\ \# Validation samples & 1,168 & 788 & 1,355 & 931 & 2,677 & 20,000 \\ \# Test samples & 1,016 & 1,577 & 2,311 & 1,862 & 5,354 & 23,498 \\ \hline \end{tabular} DESED2021 dataset is composed of 10 second audio clips recorded in domestic environments or synthesized using Scaper to simulate a domestic environment. The original AudioSet-Strong-Labeled dataset consists of an expanding ontology of 632 audio event classes and a collection of 2,084,320 human-labeled 10-second sound clips drawn from YouTube videos. To simulate the application of early event detection in industries, we select some subsets from the AudioSet-Strong-Labeled dataset to form early event detection datasets. Specifi

\end{table}
Table 4.2: Description of datasets and their experimental setup for the early event detection.
cally, we select four subsets from the AudioSet-Strong-Labeled dataset, including explosion, alarm, liquid, and engine subclasses. _b) Early human action detection task_, we consider AVA dataset (Gu et al., 2018). AVA is a video dataset for spatiotemporal localizing atomic visual actions with 60 classes. For AVA, box annotations and their corresponding action labels are provided on key frames of 430 15-minute videos with a temporal stride of 1 second. We use version 2.2 of the AVA dataset by default. The details of each dataset are shown in Table 4.2.

**Features.** For the early sound event detection task, the input features used in the experiments are log-mel spectrograms extracted from the audio signal resampled to 16000 Hz. The log-mel spectrogram uses 2048 STFT windows with a hop size of 256 and 128 Mel-scale filters. At the training stage, the input is the full observed 10-second sound clip. As a result, each 10-second sound clip is transformed into a 2D time-frequency representation with a size of (626\(\times\)128). At the test stage, we collect an audio segment at each timestamp, which can be transformed into a 2D time-frequency representation with a size of (4\(\times\)128). For the early human action detection task, each input video contains 91 image frames. To satisfy the streaming data at the inference stage, we cut the video into \(T\) segments. In our experiment, we consider \(T=\{4,6,8,10,12,15\}\), the corresponding segment length \(ST=\{0.75s,0.5s,0.375s,0.3s,0.25s,0.2s\}\).

**Comparing Methods.** To evaluate the effectiveness of our proposed approach with two variants, named MTENN-WBC and MTENN-UMSS, _a) Early sound event detection task_, we compare it with two state-of-the-art early sound event detection methods: Dual DNN (Phan et al., 2018) and SEED (Zhao et al., 2022); two sound event detection methods: CRNN (Turpault et al., 2019) and Conformer (Miyazaki et al., 2020); _b) Early human action detection task_, we compare it with three sound human action detection methods: ACAR (Pan et al., 2021), AIA (Tang et al., 2020), and SlowFast (Feichtenhofer et al., 2019); For both early detection tasks, we consider three different uncertainty methods as the baselines, which include _Entropy_, _Epistemic_ uncertainty (Gal and Ghahramani, 2016) (represents the uncertainty of model parameters), and _Aleatoric_ uncertainty (Depeweg et al., 2018) ( represents
the uncertainty of data noise). We consider using uncertainty to filter the high uncertainty prediction for three uncertainty-based methods. We use MC-drop (Gal and Ghahramani, 2016) to estimate epistemic and aleatoric uncertainties in the experiments.

**Evaluation Metrics.** We consider both early detection F1 score and detection delay as the evaluation metrics to evaluate early detection performance. We first define the true positive prediction for the event \(k\), which only happens when the first prediction timestamp \(d_{p}\) is located in the ongoing event region.

\[\text{TP}_{k}=\begin{cases}1,&\text{if }y_{k}^{d_{p}}==1\text{ and }d_{p}-d_{t}\geq L\\ 0,&\text{otherwise}\end{cases} \tag{4.10}\]

where \(d_{t}\) is the onset timestamp of the predicted event. In contrast, the false positive prediction happened when the first prediction timestamp \(d_{p}\) is not located in the ongoing event region. Then we can calculate precision, recall, and F1 score based on true positive prediction and false positive prediction for each event. For detection delay, it's only measured when we have a true positive prediction. Then the detection delay is defined as follows,

\[\text{delay}=\begin{cases}d_{p}-d_{t},&\text{if }d_{p}\geq d_{t}\\ 0,&\text{if }d_{p}<d_{t}\end{cases} \tag{4.11}\]

**Settings.**_a) Early sound event detection task_, we use CRNN (Turpault and Serizel, 2020) as the backbone except for Conformer. We use the Adam optimizer for all methods and follow the same training setting as (Turpault and Serizel, 2020). _b) Early human action detection task_, we use ACAR as the backbone except for AIA and SlowFast. We use the SGD optimizer for all methods and follow the same training setting as (Pan et al., 2021). For the uncertainty threshold, we set 0.5 for epistemic uncertainty and 0.9 for other uncertainties (entropy, vacuity, aleatoric).
#### 4.7.2 Results and Analysis

**Early Sound Event Detection Performance.** Table 4.3 shows that our proposed methods (MTENN-WBC and MTENN-UMSS) outperform all baseline models under the detection delay and early detection F1 score for the sound event early detection. The outperformance of MTENN-WBC is fairly impressive. This confirms that the belief comultiplication operator is the key to improving the sequential uncertainty estimation such that MTENN-WBC can significantly improve the early detection accuracy. In addition, MTENN-UMSS is a more aggressive method for early event detection, which significantly reduced the detection delay, demonstrating that vacuity uncertainty distribution changed at the event's ongoing early stage. Furthermore, the test inference time of our approach is around 5ms, less than the streaming segment duration (60ms), which indicates that our method satisfies the real-time requirement.

**Early human action detection performance.** Table 4.4 shows the experiment results of early human action detection, which get a similar pattern to early sound event detection. Note that MTENN-WBC achieved the best detection accuracy (e.g., 50% increase compared with ACAR baseline) with a large detection delay. While our MTENN-UMSS outperforms all baseline models under the detection delay and early detection F1 score. In addition, as

\begin{table}
\begin{tabular}{l|c|c|c|c|c} \hline \hline
**Datasets** & **DESED2021** & **Explosion** & **Alarm** & **Liquid** & **Engine** \\  & & **Detection Delay \(\downarrow\) / Detection F1 Score \(\uparrow\) & & \\ \hline Dual DNN & 0.386 / 0.682 & 0.325 / 0.295 & 0.257 / 0.221 & 0.467 / 0.162 & 0.324 / 0.323 \\ SEED & 0.252 / 0.691 & 0.339 / 0.288 & 0.293 / 0.407 & 0.334 / 0.172 & 0.428 / 0.342 \\ Conformer & 0.372 / 0.639 & 0.444 / 0.268 & 0.292 / 0.429 & 0.463 / 0.166 & 0.427 / 0.323 \\ CRNN & 0.284 / 0.677 & 0.415 / 0.278 & 0.273 / 0.408 & 0.451 / 0.144 & 0.404 / 0.301 \\ CRNN + entropy & 0.312 / 0.669 & 0.422 / 0.272 & 0.282 / 0.406 & 0.465 / 0.142 & 0.423 / 0.313 \\ CRNN + epistemic & 0.278 / 0.647 & 0.401 / 0.28 & 0.244 / 0.413 & 0.411 / 0.152 & 0.356 / 0.31 \\ CRNN + aleatoric & 0.281 / 0.643 & 0.404 / 0.288 & 0.252 / 0.419 & 0.421 / 0.157 & 0.377 / 0.312 \\ \hline MTENN-WBC & **0.206 / 0.727** & **0.119** / 0.314 & 0.217 / 0.470 & 0.059 / **0.200** & 0.294 / **0.391** \\ MTENN-UMSS & 0.267 / 0.575 & 0.120 / **0.345** & **0.191** / **0.473** & **0.026** / 0.188 & **0.237** / 0.349 \\ \hline \hline \end{tabular}
\end{table}
Table 4.3: Early sound event detection performance on Audio datasets.
segment length decreases (more challenging to detect event), baseline methods' performance decreases significantly. In contrast, our proposed methods (MTENN-WBC and MTENN-UMSS) can still hold a robust performance.

**Sensitive Analysis.** (1) Uncertainty threshold. We explore the sensitivity of the vacuity threshold used in the MTENN-WBC model. Figure 4.5 (a) shows the detection delay and early detection F1 score with varying vacuity threshold values. When the vacuity threshold increases, the detection delay decreases continuously, while the early detection accuracy (F1 score) decreases as well. There is a tradeoff between detection delay and detection accuracy. The higher the uncertainty threshold increase, the more overconfident predictions (predictions with high uncertainty) result in an aggressive early prediction (may predict event happen early but may cause a false positive prediction).

(2) Effect of sliding window size. We analyzed the sensitivity of our proposed sequential fusional opinion to the size of sliding windows. Fig 4.6 (b) shows the performance of detection delay and F1 score with the varying size of sliding windows. When the sliding window size increases, the detection delay continuously decreases, and detection F1 increases until the sliding window size is large enough. The results demonstrate that sequential uncertainty estimation is critical to improving early event detection performance.

**Per-class performance.** In addition to the overall comparison, we plot the per-class performance on the Audio (Engine) dataset compared with our method and SEED baselines.

\begin{table}
\begin{tabular}{l|c|c|c|c|c|c} \hline \hline
**Segment Length** & **0.75s** & **0.5s** & **0.375s** & **0.3s** & **0.25s** & **0.2s** \\ \multicolumn{7}{c}{**Detection Delay \(\downarrow\) / Detection F1 Score \(\uparrow\)**} \\ \hline SlowFast & 0.156 / 0.402 & 0.175 / 0.376 & 0.183 / 0.372 & 0.208 / 0.367 & 0.220 / 0.360 & 0.229 / 0.357 \\ AIA & 0.214 / 0.410 & 0.231 / 0.387 & 0.230 / 0.382 & 0.239 / 0.379 & 0.250 / 0.368 & 0.264 / 0.360 \\ ACAR & 0.227 / 0.446 & 0.245 / 0.430 & 0.245 / 0.424 & 0.240 / 0.406 & 0.235 / 0.399 & 0.253 / 0.389 \\ ACAR + entropy & 0.234 / 0.464 & 0.268 / 0.462 & 0.267 / 0.457 & 0.284 / 0.456 & 0.276 / 0.456 & 0.307 / 0.447 \\ ACAR + epistemic & 0.232 / 0.451 & 0.265 / 0.448 & 0.264 / 0.442 & 0.441 / 0.413 & 0.274 / 0.438 & 0.301 / 0.430 \\ ACAR + aleatoric & 0.213 / 0.434 & 0.244 / 0.428 & 0.243 / 0.423 & 0.259 / 0.421 & 0.254 / 0.416 & 0.275 / 0.407 \\ \hline MTENN-WBC & 0.308 / **0.736** & 0.343 / **0.734** & 0.341 / **0.706** & 0.361 / **0.708** & 0.354 / **0.706** & 0.377 / **0.698** \\ MTENN-UMSS & **0.089** / 0.533 & **0.090** / 0.535 & **0.090** / 0.527 & **0.093** / 0.532 & **0.093** / 0.525 & **0.081** / 0.524 \\ \hline \hline \end{tabular}
\end{table}
Table 4.4: Early human action detection performance on AVA datasets with different segment lengths (ST).
Figure 4.6: Sensitive Analysis of sliding window size. When the sliding window size increases, the detection delay continuously decreases, and detection F1 increases until the sliding window size is large enough.

As shown in Figure 4.7, MTENN-WBC outperforms others under the detection accuracy among most classes. MTENN-UMSS outperforms others under the detection delay. Among most classes. Note that both SEED and MTENN cannot detect difficult events (‘Heavy engine’ or ‘Idling’) due to class imbalance in the training set. But our MTENN-UMSS can detect these complex events with a small detection delay.

**Ablation study.** We conducted additional experiments (see Table 4.5) in order to demonstrate the contributions of the key technical components, including MTENN loss, WBC, and UMSS. Specifically, we consider three ablated models: (a) MTENN-BC, a vari

Figure 4.5: Sensitive Analysis of uncertainty threshold. There is a tradeoff between detection delay and detection accuracy. The higher uncertainty threshold increase, the more overconfidence predictions.

Figure 4.6: Sensitive Analysis of sliding window size. When the sliding window size increases, the detection delay continuously decreases, and detection F1 increases until the sliding window size is large enough.
\begin{table}
\begin{tabular}{l|c|c} \hline \hline
**Datasets** & **AudioSet(Engine)** & **AudioSet(Liquid)** \\  & **Detection Delay \(\downarrow\) / Detection F1 Score \(\uparrow\)** \\ \hline MTENN w/o MTENN loss & 0.463 / 0.307 & 0.326 / 0.083 \\ MTENN (Phase I) & 0.448 / 0.313 & 0.329 / 0.142 \\ MTENN-BC & 0.312 /0.383 & 0.074 / 0.207 \\ \hline MTENN-WBC & 0.294 / **0.391** & 0.057 / **0.196** \\ MTENN-UMSS & **0.237** / 0.349 & **0.026** / 0.193 \\ \hline \hline \end{tabular}
\end{table}
Table 4.5: Ablation study. MTENN-BC: a variant of MTENN-WBC that uses binomial comultiplication instead of weighted binomial comultiplication; MTENN (Phase I): only consider phase I to predict event without any sequential uncertainty head; MTENN w/o MTENN loss: a variant of MTENN (Phase I) that consider BCE loss.

Figure 4.7: Per-Class Evaluation on Audio (Engine) dataset.
**Inference time.** Table 4.6 shows the inference time for all methods used in our experiments. Note that the audio streaming segment duration is 60 milliseconds (ms), and the video streaming segment duration is 300 milliseconds when \(ST=0.3s\), while our approaches only take around 5ms and 190 ms for audio and video streaming segments, respectively. This indicates that our proposed framework satisfies the real-time requirement for early event detection.

### Conclusion

In this work, we propose a novel framework, Multi-Label Temporal Evidential Neural Network (MTENN), for early event detection in temporal data. MTENN is able to quality predictive uncertainty due to the lack of evidence for multi-label classifications at each time stamp based on belief/evidence theory. In addition, we introduce two novel uncertainty fusion operators (weighted binomial comultiplication (WBC) and uncertainty mean scan statistics (UMSS)) based on MTENN to quantify the fused uncertainty of a sub-sequence for early event detection.. We validate the performance of our approach with state-of-the-art techniques on real-world audio and video datasets. Theoretic analysis and empirical studies

\begin{table}
\begin{tabular}{l|l|l|l} \hline \hline \multicolumn{2}{c|}{DESED2021} & \multicolumn{2}{c}{AVA (ST=0.3s)} \\ \hline Dual DNN & 5.1ms & & \\ SEED & 5.0ms & SlowFast & 175ms \\ Conformer & 6.6ms & AIA & 181ms \\ CRNN & 5.0ms & ACAR & 187ms \\ CRNN + entropy & 5.0ms & ACAR + entropy & 188ms \\ CRNN + epistemic & 27.0ms & ACAR + epistemic & 564ms \\ CRNN + aleatoric & 27.0ms & ACAR + aleatoric & 564ms \\ \hline MTENN-WBC & 5.5ms & MTENN-WBC & 192ms \\ MTENN-UMSS & 5.3ms & MTENN-UMSS & 190ms \\ \hline \hline \end{tabular}
\end{table}
Table 4.6: Compare inference time with different methods.
demonstrate the effectiveness and efficiency of the proposed framework in both detection delay and accuracy.
## Chapter Conclusion and Future Work

### 5.1 Conclusion of Completed Work

In this dissertation, the proposed research aims on the design a general multi-source uncertainty framework to quantify the inherent uncertainties of deep neural networks. We are focused on three major types of direction, including uncertainty-aware semi-supervised learning on graph data (Chapter 2), uncertainty-aware robust semi-supervised learning (Chapter 3), and uncertainty-aware early event detection with multi-labels (Chapter 4).

In Chapter 2, we study the uncertainty decomposition problem for graph neural networks. We first provide a theoretical analysis of the relationships between different types of uncertainties. Then, we proposed a multi-source uncertainty framework of GNNs for semi-supervised node classification. Our proposed framework provides an effective way of predicting node classification and out-of-distribution detection considering multiple types of uncertainty. We leveraged various types of uncertainty estimates from both deep learning and evidence/belief theory domains. Through our extensive experiments, we found that dissonance-based detection yielded the best performance on misclassification detection while vacuity-based detection performed the best for OOD detection, compared to other competitive counterparts. In particular, it was noticeable that applying GKDE and the Teacher network further enhanced the accuracy in node classification and uncertainty estimates.

We further study uncertainty in robust semi-supervised learning setting in Chapter 3. In this setting, traditional semi-supervised learning (SSL) performance can degrade substantially and is sometimes even worse than simple supervised learning approaches due to the OODs involved in the unlabeled pool. To solve this problem, we first study the impact of OOD data on SSL algorithms and demonstrate empirically on synthetic data that the SSL algorithms' performance depends on how close the OOD instances are to the decision boundary
(and the ID data instances), which can also be measured via vacuity uncertainty introduced in Chapter 2. Based on this observation, we proposed a novel unified uncertainty-aware robust SSL framework that treats the weights directly as hyper-parameters in conjunction with weighted batch normalization, which is designed to improve the robustness of BN against OODs. In addition, we proposed two efficient bi-level algorithms for our proposed robust SSL approach, including meta-approximation and implicit-differentiation based, that have different tradeoffs on computational efficiency and accuracy. We also conduct a theoretical analysis of the impact of faraway OODs in the BN step and discuss the connection between our approach (high-order approximation based on implicit differentiation) and low-order approximation approaches.

Finally, in Chapter 4, we consider a time series setting for early event detection. In this setting, a temporal event with multiple labels occurs sequentially along the timeline. The goal of this work is to accurately detect all classes at the ongoing stage of an event within the least amount of time. The problem is formulated as an online multi-label time series classification problem. To this end, technically, we propose a novel framework, Multi-Label Temporal Evidential Neural Network, and two novel uncertainty estimation heads (weighted binomial comultiplication (WBC) and uncertainty mena scan statistics(UMSS)) to quantify the fused uncertainty of a sub-sequence for early event detection. We empirically show that the proposed approach outperforms state-of-the-art techniques on real-world datasets.

In light of these discoveries, the following are some interesting future avenues to investigate.

### Future Work

#### 5.2.1 Quantification of multidimensional uncertainty

Different forms of the distribution have respective limitations in quantifying uncertainty. For example, a Dirichlet distribution can estimate vacuity and dissonance, but not vague
ness (e.g., non-distinctive class labels, such as 'A or B'). Vagueness can emerge only in a hyper-Dirichlet distribution; but both Dirichlet and hyper-Dirichlet distributions are uni-models and cannot estimate data source dependent uncertainty, i.e., the training data fused from multiple sources. Even subjective logic does not provide ways of measuring the uncertainty types based on multi-model or heterogeneous distributions over a simplex. Therefore, future researchers can explore different forms of distributions to measure different types of uncertainties, such as Dirichlet, hyper-Dirichlet, a mixture of Dirichlet, Logistic Normal distributions, or implicit generative models that are free of parametric forms about the distribution.

#### 5.2.2 Interpretation of Multidimensional Uncertainty

Based on our in-depth literature review on different uncertainty types, we observed that some uncertainty types were studied in different domains as DL and belief theory with using distinctive terminologies but referring to the same uncertainty types. For example, the distributional uncertainty in deep learning and vacuity in subjective logic are designed to measure uncertainty caused by a lack of information and knowledge. Based on my prior work (Zhao et al., 2020), we found that vacuity is more effective than distributional uncertainty for node-level OOD detection in graph data. This finding explains the difference between distributional uncertainty and vacuity, even if the intent of formulating them was from the same origin. Hence, in this plan, I will further delve into how and why these two similar types of uncertainties perform differently through empirical experiments and theoretical proof. Here is the research question for future investigation: what type of uncertainty is more critical than other types to maximize decision effectiveness under what problem contexts (e.g., images, graph data) and what task types (e.g., classification prediction or OOD)?
**APPENDIX**

**PROOFS OF THE PROPOSED THEOREMS**

### Proof of Theorem 1

**Interpretation**. **Theorem 1.1 (a)** implies that increases in both uncertainty types may not happen at the same time. A higher vacuity leads to a lower dissonance, and vice versa (a higher dissonance leads to a lower vacuity). This indicates that a high dissonance only occurs only when a large amount of evidence is available and the vacuity is low. **Theorem 1.1 (b)** shows relationships between vacuity and epistemic uncertainty in which vacuity is an upper bound of epistemic uncertainty. Although some existing approaches (Josang, 2016; Sensoy et al., 2018) treat epistemic uncertainty the same as vacuity, it is not necessarily true except for an extreme case where a sufficiently large amount of evidence available, making vacuity close to zero. **Theorem 1.2 (a) and (b)** explain how entropy differs from vacuity and/or dissonance. We observe that entropy is 1 when either vacuity or dissonance is 0. This implies that entropy cannot distinguish different types of uncertainty due to different root causes. For example, a high entropy is observed when an example is either an OOD or misclassified example. Similarly, a high aleatoric uncertainty value and a low epistemic uncertainty value are observed under both cases. However, vacuity and dissonance can capture different causes of uncertainty due to lack of information and knowledge and to conflicting evidence, respectively. For example, an OOD objects typically show a high vacuity value and a low dissonance value while a conflicting prediction exhibits a low vacuity and a high dissonance.

Proof.: 1. (a) Let the opinion \(\omega=[b_{1},\ldots,b_{K},u_{v}]\), where \(K\) is the number of classes, \(b_{i}\) is the belief for class \(i\), \(u_{v}\) is the uncertainty mass (vacuity), and \(\sum_{i=1}^{K}b_{i}+u_{v}=1\). Dissonance has
an upper bound with

\[u_{diss} = \sum_{i=1}^{K}\Big{(}\frac{b_{i}\sum_{j=1,j\neq i}^{K}b_{j}\text{Bal} (b_{i},b_{j})}{\sum_{j=1,j\neq i}^{K}b_{j}}\Big{)}\] \[\leq \sum_{i=1}^{K}\Big{(}\frac{b_{i}\sum_{j=1,j\neq i}^{K}b_{j}}{\sum_{ j=1,j\neq i}^{K}b_{j}}\Big{)},\quad\text{(since $0\leq\text{Bal}(b_{i},b_{j})\leq 1$)}\] \[= \sum_{i=1}^{K}b_{i},\]

where \(\text{Bal}(b_{i},b_{j})\) is the relative mass balance, then we have

\[u_{v}+u_{diss}\leq\sum_{i=1}^{K}b_{i}+u_{v}=1.\] (A.2)

1. (b) For the multinomial random variable \(y\), we have

\[y\sim\text{Cal}(\mathbf{p}),\quad\mathbf{p}\sim\text{Dir}( \boldsymbol{\alpha}),\] (A.3)

where \(\text{Cal}(\mathbf{p})\) is the categorical distribution and \(\text{Dir}(\boldsymbol{\alpha})\) is Dirichlet distribution. Then we have

\[\text{Prob}(y|\boldsymbol{\alpha})=\int\text{Prob}(y|\mathbf{ p})\text{Prob}(\mathbf{p}|\boldsymbol{\alpha})d\mathbf{p},\] (A.4)

and the epistemic uncertainty is estimated by mutual information,

\[\mathcal{I}[y,\mathbf{p}|\boldsymbol{\alpha}]=\mathcal{H}\Big{[} \mathbb{E}_{\text{Prob}(\mathbf{p}|\boldsymbol{\alpha})}[P(y|\mathbf{p})] \Big{]}-\mathbb{E}_{\text{Prob}(\mathbf{p}|\boldsymbol{\alpha})}\Big{[} \mathcal{H}[P(y|\mathbf{p})]\Big{]}.\] (A.5)

Now we consider another measure of ensemble diversity: _Expected Pairwise KL-Divergence_ between each model in the ensemble. Here the expected pairwise KL-Divergence between two independent distributions, including \(P(y|\mathbf{p}_{1})\) and \(P(y|\mathbf{p}_{2})\), where \(\mathbf{p}_{1}\) and \(\mathbf{p}_{2}\) are two independent samples from \(\text{Prob}(\mathbf{p}|\boldsymbol{\alpha})\), can be computed,

\[\mathcal{K}[y,\mathbf{p}|\boldsymbol{\alpha}] = \mathbb{E}_{\text{Prob}(\mathbf{p}_{1}|\boldsymbol{\alpha}\text{ Prob}(\mathbf{p}_{2}|\boldsymbol{\alpha})}\Big{[}KL[P(y|\mathbf{p}_{1})\|P(y| \mathbf{p}_{2})]\Big{]}\] \[= -\sum_{i=1}^{K}\mathbb{E}_{\text{Prob}(\mathbf{p}_{1}|\boldsymbol {\alpha})}[P(y|\mathbf{p}_{1})]\mathbb{E}_{\text{Prob}(\mathbf{p}_{2}| \boldsymbol{\alpha})}[\ln P(y|\mathbf{p}_{2})]-\mathbb{E}_{\text{Prob}( \mathbf{p}|\boldsymbol{\alpha})}\Big{[}\mathcal{H}[P(y|\mathbf{p})]\Big{]}\] \[\geq \mathcal{I}[y,\mathbf{p}|\boldsymbol{\alpha}],\]
where \({\cal I}[y,{\bf p}_{1}|\mathbf{\alpha}]={\cal I}[y,{\bf p}_{2}|\mathbf{\alpha}]\). We consider Dirichlet ensemble, the _Expected Pairwise KL Divergence_,

\[{\cal K}[y,{\bf p}|\mathbf{\alpha}] = -\sum_{i=1}^{K}\frac{\alpha_{i}}{S}\Big{(}\psi(\alpha_{i})-\psi(S) \Big{)}-\sum_{i=1}^{K}-\frac{\alpha_{i}}{S}\Big{(}\psi(\alpha_{i}+1)-\psi(S+1) \Big{)}\] (A.7) \[= \frac{K-1}{S},\]

where \(S=\sum_{i=1}^{K}\alpha_{i}\) and \(\psi(\cdot)\) is the _digamma Function_, which is the derivative of the natural logarithm of the gamma function. Now we obtain the relations between vacuity and epistemic,

\[\underbrace{\frac{K}{S}}_{\rm Vacuity}>{\cal K}[y,{\bf p}|\mathbf{\alpha}]=\frac{K-1}{S}\geq\underbrace{{\cal I}[y,{\bf p}|\mathbf{\alpha}]}_{\rm Epistemic}.\] (A.8)

2. (a) For an out-of-distribution sample, \(\alpha=[1,\ldots,1]\), the vacuity can be calculated as

\[u_{v} = \frac{K}{\sum_{i=1}^{K}\alpha_{i}}=\frac{K}{K}=1,\] (A.9)

and the belief mass \(b_{i}=(\alpha_{i}-1)/\sum_{i=1}^{K}\alpha_{i}=0\), we estimate dissonance,

\[u_{diss} = \sum_{i=1}^{K}\Big{(}\frac{b_{i}\sum_{j=1,j\neq i}^{K}b_{j}{\rm Bal }(b_{i},b_{j})}{\sum_{j=1,j\neq i}^{K}b_{j}}\Big{)}=0.\] (A.10)

Given the expected probability \(\hat{p}=[1/K,\ldots,1/K]^{\top}\), the entropy is calculated based on \(\log_{K}\),

\[u_{en}={\cal H}[\hat{p}]=-\sum_{i=1}^{K}\hat{p}_{i}\log_{K}\hat{p}_{i}=-\sum_{ i=1}^{K}\frac{1}{K}\log_{K}\frac{1}{K}=\log_{K}\frac{1}{K}^{-1}=\log_{K}K=1,\] (A.11)
where \(\mathcal{H}(\cdot)\) is the entropy. Based on Dirichlet distribution, the aleatoric uncertainty refers to the expected entropy,

\[u_{alea} = \mathbb{E}_{p\sim\text{Dir}(\alpha)}[\mathcal{H}[p]]\] \[= -\sum_{i=1}^{K}\frac{\Gamma(S)}{\prod_{i=1}^{K}\Gamma(\alpha_{i})} \int_{S_{K}}p_{i}\log_{K}p_{i}\prod_{i=1}^{K}p_{i}^{\alpha_{i}-1}d\mathbf{p}\] \[= -\frac{1}{\ln K}\sum_{i=1}^{K}\frac{\Gamma(S)}{\prod_{i=1}^{K} \Gamma(\alpha_{i})}\int_{S_{K}}p_{i}\ln p_{i}\prod_{i=1}^{K}p_{i}^{\alpha_{i}-1 }d\mathbf{p}\] \[= -\frac{1}{\ln K}\sum_{i=1}^{K}\frac{\alpha_{i}}{S}\frac{\Gamma(S+ 1)}{\Gamma(\alpha_{i}+1)\prod_{i^{\prime}=1,\neq i}^{K}\Gamma(\alpha_{i^{ \prime}})}\int_{S_{K}}p_{i}^{\alpha_{i}}\ln p_{i}\prod_{i^{\prime}=1,\neq i}^{ K}p_{i^{\prime}}^{\alpha_{i^{\prime}}-1}d\mathbf{p}\] \[= \frac{1}{\ln K}\sum_{i=1}^{K}\frac{\alpha_{i}}{S}\big{(}\psi(S+ 1)-\psi(\alpha_{i}+1)\big{)}\] \[= \frac{1}{\ln K}\sum_{i=1}^{K}\frac{1}{K}(\psi(K+1)-\psi(2))\] \[= \frac{1}{\ln K}(\psi(K+1)-\psi(2))\] \[= \frac{1}{\ln K}(\psi(2)+\sum_{k=2}^{K}\frac{1}{k}-\psi(2))\] \[= \frac{1}{\ln K}\sum_{k=2}^{K}\frac{1}{k}<\frac{1}{\ln K}\ln K=1,\]

where \(S=\sum_{i=1}^{K}\alpha_{i}\), \(\mathbf{p}=[p_{1},\ldots,p_{K}]^{\top}\), and \(K\geq 2\) is the number of category. The epistemic uncertainty can be calculated via the mutual information,

\[u_{epis} = \mathcal{H}[\mathbb{E}_{p\sim\text{Dir}(\alpha)}[p]]-\mathbb{E}_ {p\sim\text{Dir}(\alpha)}[\mathcal{H}[p]]\] \[= \mathcal{H}[\hat{p}]-u_{alea}\] \[= 1-\frac{1}{\ln K}\sum_{k=2}^{K}\frac{1}{k}<1.\]

To compare aleatoric uncertainty with epistemic uncertainty, we first prove that aleatoric uncertainty (Eq. (A.13)) is monotonically increasing and converging to 1 as \(K\) increases.
Based on _Lemma 1_, we have

\[\Big{(}\ln(K+1)-\ln K\Big{)}\sum_{k=2}^{K}\frac{1}{k}<\frac{\ln K}{K +1}\] \[\Rightarrow\ln(K+1)\sum_{k=2}^{K}\frac{1}{k}<\ln K\Big{(}\sum_{k=2 }^{K}\frac{1}{k}+\frac{1}{K+1}\Big{)}=\ln K\sum_{k=2}^{K+1}\frac{1}{k}\] \[\Rightarrow\frac{1}{\ln K}\sum_{k=2}^{K}\frac{1}{k}<\frac{1}{\ln( K+1)}\sum_{k=2}^{K+1}\frac{1}{k}.\] (A.14)

Based on Eq. (A.14) and Eq. (A.13), we prove that aleatoric uncertainty is monotonically increasing with respect to \(K\). So the minimum aleatoric can be shown to be \(\frac{1}{\ln 2}\frac{1}{2}\), when \(K=2\).

Similarly, for epistemic uncertainty, which is monotonically decreasing as \(K\) increases based on _Lemma 1_, the maximum epistemic can be shown to be \(1-\frac{1}{\ln 2}\frac{1}{2}\) when \(K=2\). Then we have,

\[u_{alea}\geq\frac{1}{\ln 2}\frac{1}{2}>1-\frac{1}{2\ln 2}\geq u_{epis}\] (A.15)

Therefore, we prove that \(1=u_{v}=u_{en}>u_{alea}>u_{epis}>u_{diss}=0\).

2. (b) For a conflicting prediction, i.e., \(\alpha=[\alpha_{1},\ldots,\alpha_{K}]\), with \(\alpha_{1}=\alpha_{2}=\cdots=\alpha_{K}=C\), and \(S=\sum_{i=1}^{K}\alpha_{i}=CK\), the expected probability \(\hat{p}=[1/K,\ldots,1/K]^{\top}\), the belief mass \(b_{i}=(\alpha_{i}-1)/S\), and the vacuity can be calculated as

\[u_{v} = \frac{K}{S}\xrightarrow{S\rightarrow\infty}0,\] (A.16)

and the dissonance can be calculated as

\[u_{diss} = \sum_{i=1}^{K}\Big{(}\frac{b_{i}\sum_{j=1,j\neq i}^{K}b_{j}\text {Bal}(b_{i},b_{j})}{\sum_{j=1,j\neq i}^{K}b_{j}}\Big{)}=\sum_{i=1}^{K}b_{i}\] \[= \sum_{i=1}^{K}\Bigg{(}\frac{a_{i}-1}{\sum_{i=1}^{K}a_{i}}\Bigg{)}\] \[= \frac{\sum_{i=1}^{K}a_{i}-k}{\sum_{i=1}^{K}a_{i}}\] \[= 1-\frac{K}{S}\xrightarrow{S\rightarrow\infty}1.\]
Given the expected probability \(\hat{p}=[1/K,\ldots,1/K]^{\top}\), the entropy can be calculated based on Dirichlet distribution,

\[u_{en} = \mathcal{H}[\hat{p}]=-\sum_{i=1}^{K}\hat{p}_{i}\log_{K}\hat{p}_{i}=1,\] (A.18)

and the aleatoric uncertainty is estimated as the expected entropy,

\[u_{alea} = \mathbb{E}_{p\sim\mathrm{Dir}(\alpha)}[\mathcal{H}[p]]\] \[= -\sum_{i=1}^{K}\frac{\Gamma(S)}{\prod_{i=1}^{K}\Gamma(\alpha_{i} )}\int_{S_{K}}p_{i}\log_{K}p_{i}\prod_{i=1}^{K}p_{i}^{\alpha_{i}-1}d\mathbf{p}\] \[= -\frac{1}{\ln K}\sum_{i=1}^{K}\frac{\Gamma(S)}{\prod_{i=1}^{K} \Gamma(\alpha_{i})}\int_{S_{K}}p_{i}\ln p_{i}\prod_{i=1}^{K}p_{i}^{\alpha_{i}- 1}d\mathbf{p}\] \[= -\frac{1}{\ln K}\sum_{i=1}^{K}\frac{\alpha_{i}}{S}\frac{\Gamma(S +1)}{\Gamma(\alpha_{i}+1)\prod_{i^{\prime}=1,\neq i}^{K}\Gamma(\alpha_{i^{ \prime}})}\int_{S_{K}}p_{i}^{\alpha_{i}}\ln p_{i}\prod_{i^{\prime}=1,\neq i}^{ K}p_{i^{\prime\prime}}^{\alpha_{i^{\prime}}-1}d\mathbf{p}\] \[= \frac{1}{\ln K}\sum_{i=1}^{K}\frac{\alpha_{i}}{S}\big{(}\psi(S+1 )-\psi(\alpha_{i}+1)\big{)}\] \[= \frac{1}{\ln K}\sum_{i=1}^{K}\frac{1}{K}(\psi(S+1)-\psi(C+1))\] \[= \frac{1}{\ln K}(\psi(S+1)-\psi(C+1))\] \[= \frac{1}{\ln K}(\psi(C+1)+\sum_{k=C+1}^{S}\frac{1}{k}-\psi(C+1))\] \[= \frac{1}{\ln K}\sum_{k=C+1}^{S}\frac{1}{k}\xrightarrow{S\to \infty}1.\]

The epistemic uncertainty can be calculated via mutual information,

\[u_{epis} = \mathcal{H}[\mathbb{E}_{p\sim\mathrm{Dir}(\alpha)}[p]]-\mathbb{E }_{p\sim\mathrm{Dir}(\alpha)}[\mathcal{H}[p]]\] \[= \mathcal{H}[\hat{p}]-u_{alea}\] \[= 1-\frac{1}{\ln K}\sum_{k=C+1}^{S}\frac{1}{k}\xrightarrow{S\to \infty}0.\]
Now we compare aleatoric uncertainty with vacuity,

\[u_{alea} = \frac{1}{\ln K}\sum_{k=C+1}^{S}\frac{1}{k}\] \[= \frac{1}{\ln K}\sum_{k=C+1}^{CK}\frac{1}{k}\] \[= \frac{\ln(CK+1)-\ln(C+1)}{\ln K}\] \[= \frac{\ln(K-\frac{K-1}{C+1})}{\ln K}\] \[> \frac{\ln(K-\frac{K-1}{2})}{\ln K}\] \[= \frac{\ln(4/K+4/K+1/2)}{\ln K}\] \[\geq \frac{\ln[3(4/K+4/K+1/2)^{\frac{1}{3}}]}{\ln K}\] \[= \frac{\ln 3+\frac{1}{3}\ln(\frac{K^{2}}{32})}{\ln K}\] \[= \frac{\ln 3+\frac{2}{3}\ln K-\frac{1}{3}\ln 32}{\ln K}>\frac{2 }{3}.\]

Based on Eq. (A.22), when \(C>\frac{3}{2}\), we have

\[u_{alea}>\frac{2}{3}>\frac{1}{C}=u_{v}\] (A.22)

We have already proved that \(u_{v}>u_{epis}\), when \(u_{en}=1\), we have \(u_{alea}>u_{diss}\) Therefore, we prove that \(u_{en}>u_{alea}>u_{diss}>u_{v}>u_{epis}\) with \(u_{en}=1,u_{diss}\to 1,u_{alea}\to 1,u_{v}\to 0,u_{epis}\to 0\) 

**Lemma 1**.: _For all integer \(N\geq 2\), we have \(\sum_{n=2}^{N}\frac{1}{n}<\frac{\ln N}{(N+1)\ln(\frac{N+1}{N})}\)._

Proof.: We will prove by induction that, for all integer \(N\geq 2\),

\[\sum_{n=2}^{N}\frac{1}{n}<\frac{\ln N}{(N+1)\ln(\frac{N+1}{N})}.\] (A.23)

_Base case_: When \(N=2\), we have \(\frac{1}{2}<\frac{\ln 2}{3\ln\frac{3}{2}}\) and Eq. (A.23) is true for \(N=2\).
_Induction step_: Let the integer \(K\geq 2\) is given and suppose Eq. (A.23) is true for \(N=K\), then

\[\sum_{k=2}^{K+1}\frac{1}{k}=\frac{1}{K+1}+\sum_{k=2}^{K}\frac{1}{k}< \frac{1}{K+1}+\frac{\ln K}{(K+1)\ln(\frac{K+1}{K})}=\frac{\ln(K+1)}{(K+1)\ln( \frac{K+1}{K})}.\] (A.24)

Denote that \(g(x)=(x+1)\ln(\frac{x+1}{x})\) with \(x>2\). We get its derivative, \(g^{\prime}(x)=\ln(1+\frac{1}{x})-\frac{1}{x}<0\), such that \(g(x)\) is monotonically decreasing, which results in \(g(K)>g(K+1)\). Based on Eq. (A.24) we have,

\[\sum_{k=2}^{K+1}\frac{1}{k}<\frac{\ln(K+1)}{g(K)}<\frac{\ln(K+1)} {g(K+1)}=\frac{\ln(K+1)}{(K+2)\ln(\frac{K+2}{K+1})}.\] (A.25)

Thus, Eq. (A.23) holds for \(N=K+1\), and the proof of the induction step is complete.

_Conclusion_: By the principle of induction, Eq. (A.23) is true for all integer \(N\geq 2\). 

### Derivations for Joint Probability and KL Divergence

#### a.2.1 Joint Probability

We infer the joint probability (Eq. (2.8)) by:

\[p(\mathbf{y}|A,\mathbf{r};\mathcal{G})=\int\int\mathrm{Prob}( \mathbf{y}|\mathbf{p})\mathrm{Prob}(\mathbf{p}|A,\mathbf{r};\boldsymbol{ \theta})\mathrm{Prob}(\boldsymbol{\theta}|\mathcal{G})d\mathbf{p}d\boldsymbol {\theta}\] \[\approx \int\int\mathrm{Prob}(\mathbf{y}|\mathbf{p})\mathrm{Prob}( \mathbf{p}|A,\mathbf{r};\boldsymbol{\theta})q(\boldsymbol{\theta})d\mathbf{p}d\theta\] \[\approx \frac{1}{M}\sum_{m=1}^{M}\int\mathrm{Prob}(\mathbf{y}|\mathbf{p} )\mathrm{Prob}(\mathbf{p}|A,\mathbf{r};\boldsymbol{\theta}^{(m)})d\mathbf{p}, \quad\boldsymbol{\theta}^{(m)}\sim q(\boldsymbol{\theta})\] \[\approx \frac{1}{M}\sum_{m=1}^{M}\int\sum_{i=1}^{N}\mathrm{Prob}(\mathbf{y }_{i}|\mathbf{p}_{i})\mathrm{Prob}(\mathbf{p}_{i}|A,\mathbf{r};\boldsymbol{ \theta}^{(m)})d\mathbf{p}_{i},\quad\boldsymbol{\theta}^{(m)}\sim q( \boldsymbol{\theta})\] \[\approx \frac{1}{M}\sum_{m=1}^{M}\prod_{i=1}^{N}\int\mathrm{Prob}( \mathbf{y}_{i}|\mathbf{p}_{i})\mathrm{Dir}(\mathbf{p}_{i}|\boldsymbol{ \alpha}_{i}^{(m)})d\mathbf{p}_{i},\quad\boldsymbol{\alpha}^{(m)}=f(A,\mathbf{ r},\boldsymbol{\theta}^{(m)}),q\quad\boldsymbol{\theta}^{(m)}\sim q(\boldsymbol{\theta}),\]
where the posterior over class label \(p\) will be given by the mean of the Dirichlet:

\[\mathrm{Prob}(y_{i}=p|\boldsymbol{\theta}^{(m)})=\int\mathrm{Prob}(y_{i}=p| \mathbf{p}_{i})\mathrm{Prob}(\mathbf{p}_{i}|A,\mathbf{r};\boldsymbol{\theta}^{(m )})d\mathbf{p}_{i}=\frac{\alpha_{ip}^{(m)}}{\sum_{k=1}^{K}\alpha_{ik}^{(m)}}.\]

The probabilistic form for a specific node \(i\) by using marginal probability,

\[\mathrm{Prob}(\mathbf{y}_{i}|A,\mathbf{r};\mathcal{G}) = \sum_{y\backslash y_{i}}\mathrm{Prob}(\mathbf{y}|A,\mathbf{r}; \mathcal{G})\] \[= \sum_{y\backslash y_{i}}\int\int\prod_{j=1}^{N}\mathrm{Prob}( \mathbf{y}_{j}|\mathbf{p}_{j})\mathrm{Prob}(\mathbf{p}_{j}|A,\mathbf{r}; \boldsymbol{\theta})\mathrm{Prob}(\boldsymbol{\theta}|\mathcal{G})d\mathbf{p}d \boldsymbol{\theta}\] \[\approx \sum_{y\backslash y_{i}}\int\int\prod_{j=1}^{N}\mathrm{Prob}( \mathbf{y}_{j}|\mathbf{p}_{j})\mathrm{Prob}(\mathbf{p}_{j}|A,\mathbf{r}; \boldsymbol{\theta})q(\boldsymbol{\theta})d\mathbf{p}d\boldsymbol{\theta}\] \[\approx \sum_{m=1}^{M}\sum_{y\backslash y_{i}}\int\prod_{j=1}^{N}\mathrm{ Prob}(\mathbf{y}_{j}|\mathbf{p}_{j})\mathrm{Prob}(\mathbf{p}_{j}|A,\mathbf{r}; \boldsymbol{\theta}^{(m)})d\mathbf{p},\quad\boldsymbol{\theta}^{(m)}\sim q( \boldsymbol{\theta})\] \[\approx \sum_{m=1}^{M}\Big{[}\sum_{y\backslash y_{i}}\int\prod_{j=1}^{N} \mathrm{Prob}(\mathbf{y}_{j}|\mathbf{p}_{j})\mathrm{Prob}(\mathbf{p}_{j}|A, \mathbf{r};\boldsymbol{\theta}^{(m)})d\mathbf{p}_{j}\Big{]},\quad\boldsymbol{ \theta}^{(m)}\sim q(\boldsymbol{\theta})\] \[\approx \sum_{m=1}^{M}\Big{[}\sum_{y\backslash y_{i}}\prod_{j=1,j\neq i}^ {N}\mathrm{Prob}(\mathbf{y}_{j}|A,\mathbf{r}_{j};\boldsymbol{\theta}^{(m)}) \Big{]}\mathrm{Prob}(\mathbf{y}_{i}|A,\mathbf{r};\boldsymbol{\theta}^{(m)}), \quad\boldsymbol{\theta}^{(m)}\sim q(\boldsymbol{\theta})\] \[\approx \sum_{m=1}^{M}\int\mathrm{Prob}(\mathbf{y}_{i}|\mathbf{p}_{i}) \mathrm{Prob}(\mathbf{p}_{i}|A,\mathbf{r};\boldsymbol{\theta}^{(m)})d\mathbf{ p}_{i},\quad\boldsymbol{\theta}^{(m)}\sim q(\boldsymbol{\theta}).\]

To be specific, the probability of label \(p\) is,

\[\mathrm{Prob}(y_{i}=p|A,\mathbf{r};\mathcal{G})\approx\frac{1}{M}\sum_{m=1}^{M} \frac{\alpha_{ip}^{(m)}}{\sum_{k=1}^{K}\alpha_{ik}^{(m)}},\quad\boldsymbol{ \alpha}^{(m)}=f(A,\mathbf{r},\boldsymbol{\theta}^{(m)}),\quad\boldsymbol{ \theta}^{(m)}\sim q(\boldsymbol{\theta}).\]
#### a.2.2 KL-Divergence

KL-divergence between \(\text{Prob}(\mathbf{y}|\mathbf{r};\mathbf{\gamma},\mathcal{G})\) and \(\text{Prob}(\mathbf{y}|\hat{\mathbf{p}})\) is given by

\[\text{KL}[\text{Prob}(\mathbf{y}|A,\mathbf{r};\mathcal{G})||\text{ Prob}(\mathbf{y}|\hat{\mathbf{p}}))] = \mathbb{E}_{\text{Prob}(\mathbf{y}|A,\mathbf{r};\mathcal{G})} \Big{[}\log\frac{\text{Prob}(\mathbf{y}|A,\mathbf{r};\mathcal{G})}{\text{ Prob}(\mathbf{y}|\hat{\mathbf{p}})}\Big{]}\] \[\approx \mathbb{E}_{\text{Prob}(\mathbf{y}|A,\mathbf{r};\mathcal{G})} \Big{[}\log\frac{\prod_{i=1}^{N}\text{Prob}(\mathbf{y}_{i}|A,\mathbf{r}; \mathcal{G})}{\prod_{i=1}^{N}\text{Prob}(\mathbf{y}|\hat{\mathbf{p}})}\Big{]}\] \[\approx \sum_{i=1}^{N}\mathbb{E}_{\text{Prob}(\mathbf{y}|A,\mathbf{r}; \mathcal{G})}\Big{[}\log\frac{\text{Prob}(\mathbf{y}_{i}|A,\mathbf{r}; \mathcal{G})}{\text{Prob}(\mathbf{y}|\hat{\mathbf{p}})}\Big{]}\] \[\approx \sum_{i=1}^{N}\sum_{j=1}^{K}\text{Prob}(y_{i}=j|A,\mathbf{r}; \mathcal{G})\Big{(}\log\frac{\text{Prob}(y_{i}=j|A,\mathbf{r};\mathcal{G})}{ \text{Prob}(y_{i}=j|\hat{\mathbf{p}})}\Big{)}\]

The KL divergence between two Dirichlet distributions \(\text{Dir}(\alpha)\) and \(\text{Dir}(\hat{\alpha})\) can be obtained in closed form as,

\[\text{KL}[\text{Dir}(\alpha)\|\text{Dir}(\hat{\alpha})]\] \[=\ln\Gamma(S)-\ln\Gamma(\hat{S})+\sum_{c=1}^{K}\big{(}\ln\Gamma( \hat{\alpha}_{c})-\ln\Gamma(\alpha_{c})\big{)}+\sum_{c=1}^{K}(\alpha_{c}-\hat {\alpha}_{c})(\psi(\alpha_{c})-\psi(S)),\]

where \(S=\sum_{c=1}^{K}\alpha_{c}\) and \(\hat{S}=\sum_{c=1}^{K}\hat{\alpha}_{c}\).

### Proof of Theorem 2

For our robust SSL, the training loss \(\mathcal{L}_{T}\) can be decomposition into supervised loss \(\mathcal{L}_{L}\) and unsupervised loss \(\mathcal{L}_{U}\), i.e., \(\mathcal{L}_{T}(\theta)=\mathcal{L}_{L}(\theta)+\mathbf{w}\mathcal{L}_{U}(\theta)\), where \(\mathcal{L}_{L}(\theta)=\sum_{(\mathbf{x}_{i},y_{i})\in\mathcal{D}}l(f( \mathbf{x}_{i},\theta),y_{i})\) and \(\mathcal{L}_{U}(\theta)=\sum_{x_{j}\in\mathcal{U}}r(f(\mathbf{x}_{j},\theta))\).

**Lemma 2**.: _Suppose the validation loss function \(\mathcal{L}_{V}\) is Lipschitz smooth with constant L, and the unsupervised loss function \(\mathcal{L}_{U}\) have \(\gamma\)-bounded gradients. Then the gradient of the validation loss function with respect to \(\mathbf{w}\) is Lipschitz continuous._
Proof.: For the meta approximation method, the gradient of the validation loss function with respect to \(\mathbf{w}\) can be written as:

\[\nabla_{\mathbf{w}}\partial\mathcal{L}_{V}(\theta^{*}(\mathbf{w})) = \frac{\partial\mathcal{L}_{V}(\theta^{*}(\mathbf{w}))}{\partial \theta^{*}}\cdot\frac{\theta^{*}(\mathbf{w})}{\partial\mathbf{w}}\] (A.26) \[= \frac{\partial\mathcal{L}_{V}(\theta^{*}(\mathbf{w}))}{\partial \theta^{*}}\cdot\frac{\theta-\alpha\frac{\partial\mathcal{L}_{T}(\theta)}{ \partial\theta}}{\partial\mathbf{w}}\] \[= \frac{\partial\mathcal{L}_{V}(\theta^{*}(\mathbf{w}))}{\partial \theta^{*}}\cdot\frac{\theta-\alpha\frac{\partial(\mathcal{L}_{L}(\theta)+ \mathbf{w}\mathcal{L}_{U}(\theta))}{\partial\theta}}{\partial\mathbf{w}}\] \[= -\alpha\frac{\partial\mathcal{L}_{V}(\theta^{*}(\mathbf{w}))}{ \partial\theta^{*}}\cdot\frac{\partial\mathcal{L}_{U}(\theta)}{\partial \theta}.\]

Taking gradients on both sides of Eq (A.26) ]with respect to \(\mathbf{w}\), we have

\[\|\nabla_{\mathbf{w}}^{2}\partial\mathcal{L}_{V}(\theta^{*}( \mathbf{w}))\| = -\alpha\Big{\|}\frac{\partial}{\partial\mathbf{w}}\Big{(}\frac{ \partial\mathcal{L}_{V}(\theta^{*}(\mathbf{w}))}{\partial\theta^{*}}\cdot \frac{\partial\mathcal{L}_{U}(\theta)}{\partial\theta}\Big{)}\Big{\|}\] (A.27) \[= -\alpha\Big{\|}\frac{\partial}{\partial\theta}\Big{(}\frac{ \partial\mathcal{L}_{V}(\theta^{*}(\mathbf{w}))}{\partial\mathbf{w}}\Big{)} \cdot\frac{\partial\mathcal{L}_{U}(\theta)}{\partial\theta}\Big{\|}\] \[= -\alpha\Big{\|}\frac{\partial}{\partial\theta}\Big{(}-\alpha \frac{\partial\mathcal{L}_{V}(\theta^{*}(\mathbf{w}))}{\partial\theta^{*}} \cdot\frac{\partial\mathcal{L}_{U}(\theta)}{\partial\theta}\Big{)}\cdot\frac{ \partial\mathcal{L}_{U}(\theta)}{\partial\theta}\Big{\|}\] \[= \alpha^{2}\Big{\|}\frac{\partial^{2}\mathcal{L}_{V}(\theta^{*}( \mathbf{w}))}{\partial\theta^{*}\partial\theta^{*}}\frac{\partial\mathcal{L}_ {U}(\theta)}{\partial\theta}\cdot\frac{\mathcal{L}_{U}(\theta)}{\partial \theta}\Big{\|}\] \[\leq \alpha^{2}\gamma^{2}L,\]

since \(\|\frac{\partial^{2}\mathcal{L}_{V}(\theta^{*}(\mathbf{w}))}{\partial\theta^{ *}\partial\theta^{*}}\|\leq L,\|\frac{\mathcal{L}_{U}(\theta)}{\partial \theta}\|\leq\gamma\). Let \(\tilde{L}=\alpha^{2}\gamma^{2}L\). Based on the Lagrange mean value theorem, we have,

\[\|\nabla\mathcal{L}_{V}(\theta^{*}(\mathbf{w}_{i}))-\nabla\mathcal{L}_{V}( \theta^{*}(\mathbf{w}_{j}))\|\leq\tilde{L}\|\mathbf{w}_{i}-\mathbf{w}_{j}\|, \quad\text{for all }\mathbf{w}_{i},\mathbf{w}_{j},\] (A.28)

where \(\nabla\mathcal{L}_{V}(\theta^{*}(\mathbf{w}_{i}))=\nabla\mathcal{L}_{V}( \theta^{*}(\mathbf{w}))|_{\mathbf{w}_{i}}\) 

Based on Lemma 2, now we start to proof of theorem 2.

Proof.: First, according to the updating rule, we have:

\[\mathcal{L}_{V}(\theta_{t+1})-\mathcal{L}_{V}(\theta_{t}) = \mathcal{L}_{V}(\theta_{t}-\alpha\nabla_{\theta}\mathcal{L}_{T}( \theta_{t},\mathbf{w}_{t}))-\mathcal{L}_{V}(\theta_{t-1}-\alpha\nabla_{\theta }\mathcal{L}_{T}(\theta_{t-1},\mathbf{w}_{t-1}))\] (A.29) \[= \underbrace{\mathcal{L}_{V}(\theta_{t}-\alpha\nabla_{\theta} \mathcal{L}_{T}(\theta_{t},\mathbf{w}_{t}))-\mathcal{L}_{V}(\theta_{t-1}- \alpha\nabla_{\theta}\mathcal{L}_{T}(\theta_{t},\mathbf{w}_{t}))}_{(a)}+\] \[\underbrace{\mathcal{L}_{V}(\theta_{t-1}-\alpha\nabla_{\theta} \mathcal{L}_{T}(\theta_{t},\mathbf{w}_{t}))-\mathcal{L}_{V}(\theta_{t-1}- \alpha\nabla_{\theta}\mathcal{L}_{T}(\theta_{t-1},\mathbf{w}_{t-1}))}_{(b)}.\]
and for term (a), we have

\[{\cal L}_{V}(\theta_{t}-\alpha\nabla_{\theta}{\cal L}_{T}(\theta_{t },{\bf w}_{t}))-{\cal L}_{V}(\theta_{t-1}-\alpha\nabla_{\theta}{\cal L}_{T}( \theta_{t},{\bf w}_{t}))\] (A.30) \[\leq (\theta_{t}-\theta_{t-1})\cdot\nabla_{\theta}{\cal L}_{V}(\theta_ {t-1}-\alpha\nabla_{\theta}{\cal L}_{T}(\theta_{t},{\bf w}_{t}))+\frac{L}{2} \|\theta_{t}-\theta_{t-1}\|_{2}^{2}\quad\mbox{(Lipschitzs smooth)}\] \[\leq \alpha\gamma^{2}+\frac{L}{2}\alpha^{2}\gamma^{2}\] \[= \alpha\gamma^{2}(\frac{\alpha L}{2}+1).\]

For term (b), we can adapt a Lipschitz-continuous function to make \({\cal L}_{V}\) smooth w.r.t. \({\bf w}\). Then we have,

\[{\cal L}_{V}(\theta_{t-1}-\alpha\nabla_{\theta}{\cal L}_{T}( \theta_{t},{\bf w}_{t}))-{\cal L}_{V}(\theta_{t-1}-\alpha\nabla_{\theta}{\cal L }_{T}(\theta_{t-1},{\bf w}_{t-1}))\] (A.31) \[= {\cal L}_{V}(\theta^{*}({\bf w}_{t}))-{\cal L}_{V}(\theta^{*}({ \bf w}_{t-1}))\] \[\leq ({\bf w}_{t}-{\bf w}_{t-1})\cdot\nabla_{\bf w}{\cal L}_{V}( \theta_{t})+\frac{\tilde{L}}{2}\|{\bf w}_{t}-{\bf w}_{t-1}\|_{2}^{2}\qquad \mbox{(From Lemma \ref{lem:L1})}\] \[= -\beta\nabla_{\bf w}{\cal L}_{V}(\theta_{t})\cdot\nabla_{\bf w}{ \cal L}_{V}(\theta_{t})+\frac{\tilde{L}}{2}\|-\beta\nabla_{\bf w}{\cal L}_{V}( \theta_{t})\|_{2}^{2}\] \[= (\frac{\tilde{L}}{2}\beta^{2}-\beta)\|\nabla_{\bf w}{\cal L}_{V}( \theta_{t})\|_{2}^{2}.\]

Then we have,

\[{\cal L}_{V}(\theta_{t+1})-{\cal L}_{V}(\theta_{t})\leq\alpha \gamma^{2}(\frac{\alpha L}{2}+1)+(\frac{\tilde{L}}{2}\beta^{2}-\beta)\|\nabla _{\bf w}{\cal L}_{V}(\theta_{t})\|_{2}^{2}\] (A.32)

Summing up the above inequalities and rearranging the terms, we can obtain

\[\sum_{t=1}^{T}(\beta-\frac{\tilde{L}}{2}\beta^{2})\|\nabla_{\bf w }{\cal L}_{V}(\theta_{t})\|_{2}^{2} \leq {\cal L}_{V}(\theta_{1})-{\cal L}_{V}(\theta_{T+1})+\alpha\gamma^ {2}(\frac{\alpha LT}{2}-T)\] (A.33) \[\leq {\cal L}_{V}(\theta_{1})+\alpha\gamma^{2}(\frac{\alpha LT}{2}+T)\]
Furthermore, we can deduce that,

\[\min_{t}\mathbb{E}\big{[}\|\nabla_{\textbf{w}}\mathcal{L}_{V}(\theta _{t})\|_{2}^{2}\big{]} \leq \frac{\sum_{t=1}^{T}(\beta-\frac{\tilde{L}}{2}\beta^{2})\|\nabla_{ \textbf{w}}\mathcal{L}_{V}(\theta_{t})\|_{2}^{2}}{\sum_{t=1}^{T}(\beta-\frac{ L}{2}\beta^{2})}\] (A.34) \[\leq \frac{\sum_{t=1}^{T}(\beta-\frac{\tilde{L}}{2}\beta^{2})\|\nabla_ {\textbf{w}}\mathcal{L}_{V}(\theta_{t})\|_{2}^{2}}{\sum_{t=1}^{T}(\beta-\frac{ L}{2}\beta^{2})}\] \[\leq \frac{1}{\sum_{t=1}^{T}(2\beta-\tilde{L}\beta^{2})}\Big{[}2 \mathcal{L}_{V}(\theta_{1})+\alpha\gamma^{2}(\alpha LT+2T)\Big{]}\] \[\leq \frac{1}{\sum_{t=1}^{T}\beta}\Big{[}2\mathcal{L}_{V}(\theta_{1}) +\alpha\gamma^{2}(LT+2T)\Big{]}\] \[= \frac{2\mathcal{L}_{V}(\theta_{1})}{T}\frac{1}{\beta}+\frac{ \alpha\gamma^{2}(L+2)}{\beta}\] \[= \frac{2\mathcal{L}_{V}(\theta_{1})}{T}\max\{L,\frac{\sqrt{T}}{C} \}+\min\{1,\frac{k}{T}\}\max\{L,\frac{\sqrt{T}}{C}\}\gamma^{2}(L+2)\] \[= \frac{2\mathcal{L}_{V}(\theta_{1})}{C\sqrt{T}}+\frac{k\gamma^{2}( L+2)}{C\sqrt{T}}=\mathcal{O}(\frac{1}{\sqrt{T}})\]

The third inequality holds for \(\sum_{t=1}^{T}\beta\leq\sum_{t=1}^{T}(2\beta-\tilde{L}\beta^{2})\). Therefore, we can conclude that our algorithm can always achieve \(\min_{0\leq t\leq T}\mathbb{E}[\|\nabla_{\textbf{w}}\mathcal{L}_{V}(\theta_{t} )\|_{2}^{2}]\leq\mathcal{O}(\frac{1}{\sqrt{T}})\) in T steps. 

### Proof of Proposition 2

Proof.: The bi-level optimization problem for weight hyperparameters **w** using a model characterized by parameters \(\theta\) is as follows:

\[\textbf{w}^{*}=\operatorname*{argmin}_{\textbf{w}}\mathcal{L}_{V} (\textbf{w},\theta^{*}(\textbf{w}))\;\text{where}\] (A.35) \[\theta^{*}(\textbf{w})=\operatorname*{argmin}_{\theta}\mathcal{L}_ {T}(\textbf{w},\theta)\] (A.36)

**Case 1**.: _IFT Approach:_ _In order to optimize **w** using gradient descent, we need to calculate the weight gradient \(\frac{\partial\mathcal{L}_{V}(\theta^{*}(\textbf{w}),\textbf{w})}{\partial \textbf{w}}\). Using chain rule in Eq. (A.35), we have:_

\[\frac{\partial\mathcal{L}_{V}(\theta^{*}(\textbf{w}),\textbf{w})}{\partial \textbf{w}}=\underbrace{\frac{\partial\mathcal{L}_{V}}{\partial\textbf{w}}}_{ (a)}+\underbrace{\frac{\partial\mathcal{L}_{V}}{\partial\theta^{*}(\textbf{w} )}}_{(b)}\times\underbrace{\frac{\partial\theta^{*}(\textbf{w})}{\partial \textbf{w}}}_{(c)}\] (A.37)
_where (a) is the direct weight gradient and (b) is the direct parameter gradient, which is easy to compute. The tricky part is the term (c) (best-response Jacobian)._

_In the IFT approach, we approximate (c) using the Implicit function theorem,_

\[\frac{\partial\theta^{*}(\mathbf{w})}{\mathbf{w}}=-\underbrace{\left[\frac{\partial \mathcal{L}_{T}}{\partial\theta\partial\theta^{T}}\right]^{-1}}_{(d)}\times \underbrace{\frac{\partial\mathcal{L}_{T}}{\partial\mathbf{w}\partial\theta^{T}} }_{(e)}\] (A.38)

_However, computing Eq. (A.38) is challenging when using deep nets because it requires inverting a high dimensional Hessian (term (d)), which often requires \(\mathcal{O}(m^{3})\) operations. Therefore, the IFT approach (Lorraine et al., 2020) uses the Neumann series approximation to effectively compute the Hessian inverse term(d), which is as follows,_

\[\left[\frac{\partial\mathcal{L}_{T}}{\partial\theta\partial\theta^{T}}\right] ^{-1}=\lim_{P\rightarrow\infty}\sum_{p=0}^{P}\left[I-\frac{\partial\mathcal{L }_{T}}{\partial\theta\partial\theta^{T}}\right]^{p}\] (A.39)

_where \(I\) is the identity matrix._

_Assuming \(P=0\) in Eq. A.39, we have \(\left[\frac{\partial\mathcal{L}_{T}}{\partial\theta\partial\theta^{T}} \right]^{-1}=\mathbf{I}\) and substituting it in Eq. (A.38), we have:_

\[\frac{\partial\theta^{*}(\mathbf{w})}{\mathbf{w}}=-\frac{\partial\mathcal{L}_{T}}{ \partial\mathbf{w}\partial\theta^{T}}\] (A.40)

_Substituting the above equation in Eq. (A.37), we have:_

\[\frac{\partial\mathcal{L}_{V}(\theta^{*}(\mathbf{w}),\mathbf{w})}{\partial\mathbf{w}}= \frac{\partial\mathcal{L}_{V}}{\partial\mathbf{w}}-\frac{\partial\mathcal{L}_{V} (\theta^{*}(\mathbf{w}))}{\partial\theta^{*}(\mathbf{w})}\times\frac{\partial^{2} \mathcal{L}_{T}}{\partial\mathbf{w}\partial\theta^{T}}\] (A.41)

_Since we are using unweighted validation loss \(\mathcal{L}_{V}\), there is no dependence of validation loss on weights directly, i.e., \(\frac{\partial\mathcal{L}_{V}}{\partial\mathbf{w}}=0\). Hence, the weight gradient is as follows:_

\[\frac{\partial\mathcal{L}_{V}(\theta^{*}(\mathbf{w}),\mathbf{w})}{\partial\mathbf{w}}=- \frac{\partial\mathcal{L}_{V}(\theta^{*}(\mathbf{w}))}{\partial^{2}\theta^{*}(\bm {w})}\times\frac{\partial\mathcal{L}_{T}}{\partial\mathbf{w}\partial\theta^{T}}\] (A.42)

_Since we are using one-step gradient approximation, we have \(\theta^{*}(\mathbf{w})=\theta-\alpha\frac{\partial\mathcal{L}_{T}(\mathbf{w},\theta)} {\partial\theta}\) where \(\alpha\) is the model parameters learning rate._
_The weight update step is as follows:_

\[\mathbf{w}^{*}=\mathbf{w}+\beta\frac{\partial\mathcal{L}_{V}(\theta^{*}(\mathbf{w}))}{ \partial\theta^{*}(\mathbf{w})}\times\frac{\partial^{2}\mathcal{L}_{T}}{\partial \mathbf{w}\partial\theta^{T}}\] (A.43)

_where \(\beta\) is the weight learning rate._

**Case 2**.: _Meta-approximation Approach In Meta-approximation approach, we have \(\theta^{*}(\mathbf{w})=\theta-\alpha\frac{\partial\mathcal{L}_{T}(\mathbf{w},\theta)} {\partial\theta}\) where \(\alpha\) is the model parameters learning rate._

_Using the value of \(\theta^{*}\), the gradient of validation loss with weight hyperparameters is as follows:_

\[\frac{\partial\mathcal{L}_{V}(\theta^{*}(\mathbf{w}))}{\partial\mathbf{w}} =\frac{\partial\mathcal{L}_{V}(\theta-\alpha\frac{\partial \mathcal{L}_{T}(\mathbf{w},\theta)}{\partial\mathbf{w}})}{\partial\mathbf{w}}\] (A.44) \[=-\frac{\partial\mathcal{L}_{V}(\theta^{*}(\mathbf{w}))}{\partial \theta^{*}(\mathbf{w})}\times\alpha\frac{\partial^{2}\mathcal{L}_{T}(\mathbf{w}, \theta)}{\partial\theta\partial\mathbf{w}^{T}}\] (A.45)

_Assuming \(\alpha=1\), we have:_

\[\frac{\partial\mathcal{L}_{V}(\theta^{*}(\mathbf{w}))}{\partial\mathbf{w}}=-\frac{ \partial\mathcal{L}_{V}(\theta^{*}(\mathbf{w}))}{\partial\theta^{*}(\mathbf{w})} \times\frac{\partial^{2}\mathcal{L}_{T}(\mathbf{w},\theta)}{\partial\theta \partial\mathbf{w}^{T}}\] (A.46)

_Hence, the weight update step is as follows:_

\[\mathbf{w}^{*}=\mathbf{w}+\beta\frac{\partial\mathcal{L}_{V}(\theta^{*}(\mathbf{w}))}{ \partial\theta^{*}(\mathbf{w})}\times\frac{\partial^{2}\mathcal{L}_{T}}{\partial \mathbf{w}\partial\theta^{T}}\] (A.47)

_where \(\beta\) is the weight learning rate_

As shown in the cases above, we have a similar weight update. Hence, it inherently means that using the meta-approximation of \(J=1\) is equivalent to using an identity matrix as the Hessian inverse of training loss with \(\theta\) (i.e., \(P=0\) for implicit differentiation approach). 

### Proof of Proposition 3

Proof.: (1). The mini-batch mean of \(\mathcal{I}\),

\[\mu_{\mathcal{I}}=\frac{1}{m}\sum_{i=1}^{m}\mathbf{x}_{i}=\mu_{I}.\] (A.48)
The mixed mini-batch mean of \({\cal IO}\),

\[\mu_{\cal IO} = \frac{1}{2m}(\sum_{i=1}^{m}{\bf x}_{i}+\sum_{i=1}^{m}\hat{\bf x}_{i})\] (A.49) \[= \frac{1}{2}\mu_{\cal I}+\frac{1}{2}\mu_{\cal O}.\]

Then we have,

\[\|\mu_{\cal IO}-\mu_{\cal I}\|_{2} = \|\frac{1}{2}\mu_{\cal I}+\frac{1}{2}\mu_{\cal O}-\mu_{\cal I}\|_ {2}\] (A.50) \[= \|\frac{1}{2}\mu_{\cal O}-\mu_{\cal I}\|_{2}>\frac{L}{2}\gg 0.\]

The mini-batch variance of \({\cal I}\),

\[\sigma_{\cal I}^{2}=\frac{1}{m}\sum_{i=1}^{m}({\bf x}_{i}-\mu_{\cal I})^{2}.\] (A.51)

The traditional batch normalizing transform based on mini-batch \({\cal I}\) for \({\bf x}_{i}\)

\[BN_{\cal I}({\bf x}_{i})=\gamma\frac{{\bf x}_{i}-\mu_{\cal I}}{\sqrt{\sigma_{ \cal I}^{2}+\epsilon}}+\beta.\] (A.52)

The mini-batch variance of \({\cal IO}\),

\[\sigma_{\cal IO}^{2} = \frac{1}{2m}(\sum_{i=1}^{m}{\bf x}_{i}^{2}+\sum_{i=1}^{m}\hat{\bf x }_{i}^{2})-\mu_{\cal IO}^{2}\] (A.53) \[= \frac{1}{2}\sigma_{\cal I}^{2}+\frac{1}{2}\sigma_{\cal O}^{2}+ \frac{1}{4}(\mu_{\cal O}-\mu_{\cal I})^{2}\] \[\approx \frac{1}{4}(\mu_{\cal O}-\mu_{\cal I})^{2},\]

and the traditional batch normalizing transform based on mini-batch \({\cal IO}\) for \({\bf x}_{i}\),

\[BN_{\cal IO}({\bf x}_{i}) = \gamma\frac{{\bf x}_{i}-\mu_{\cal B}(IO)}{\sqrt{\sigma_{\cal B}^{ 2}(IO)+\epsilon}}+\beta\] (A.54) \[= \gamma\Big{(}\frac{{\bf x}_{i}-\mu_{O}}{2\sqrt{\sigma_{\cal B}^{ 2}(IO)+\epsilon}}+\frac{{\bf x}_{i}-\mu_{I}}{2\sqrt{\sigma_{\cal B}^{2}(IO)+ \epsilon}}\Big{)}+\beta\] \[\approx \gamma\Big{(}\frac{{\bf x}_{i}-\mu_{O}}{\|\mu_{O}-\mu_{I}\|_{2}} +\frac{{\bf x}_{i}-\mu_{I}}{\|\mu_{O}-\mu_{I}\|_{2}}\Big{)}+\beta\] \[\approx \gamma\frac{{\bf x}_{i}-\mu_{O}}{\|\mu_{O}-\mu_{I}\|_{2}}+\beta.\]
The approximations in Eq. (A.53) and Eq. (A.54) hold when \(\sigma_{\mathcal{I}}^{2}\) and \(\sigma_{\mathcal{O}}^{2}\) have the same magnitude levels as \(\mu_{I}\), i.e., \(\|\mu_{\mathcal{O}}-\sigma_{\mathcal{I}}^{2}\|_{2}>L\) and \(\|\mu_{\mathcal{O}}-\sigma_{\mathcal{O}}^{2}\|_{2}>L\). Comparing Eq. (A.52) with Eq. (A.54), we prove that \(BN_{\mathcal{I}}(\mathbf{x}_{i})\neq BN_{\mathcal{IO}}(\mathbf{x}_{i})\).

(2) The weighted mini-batch mean of \(\mathcal{IO}\),

\[\mu_{\mathcal{IO}}^{\mathbf{w}} = \frac{\sum_{i=1}^{m}w_{\mathcal{I}}^{i}\mathbf{x}_{i}+\sum_{i=1}^ {m}w_{\mathcal{O}}^{i}\hat{\mathbf{x}}_{i}}{\sum_{i=1}^{m}w_{\mathcal{I}}^{i}+ \sum_{i=1}^{m}w_{\mathcal{O}}^{i}}\] \[= \frac{\sum_{i=1}^{m}1\cdot\mathbf{x}_{i}+\sum_{i=1}^{m}0\cdot \hat{\mathbf{x}}_{i}}{\sum_{i=1}^{m}1+\sum_{i=1}^{m}0}\] \[= \mu_{I},\]

witch proves that \(\mu_{\mathcal{I}}=\mu_{\mathcal{IO}}^{\mathbf{w}}\). The weighted mini-batch variance of \(\mathcal{IO}\),

\[\sigma_{\mathcal{IO}}^{\mathbf{w}}\ {}^{2} = \frac{\sum_{i=1}^{m}w_{\mathcal{I}}^{i}(\mathbf{x}_{i}-\mu_{ \mathcal{IO}}^{\mathbf{w}})^{2}}{\sum_{i=1}^{m}w_{\mathcal{I}}^{i}+\sum_{i=1} ^{m}w_{\mathcal{O}}^{i}}+\frac{\sum_{i=1}^{m}w_{\mathcal{O}}^{i}(\hat{ \mathbf{x}}_{i}-\mu_{\mathcal{IO}}^{\mathbf{w}})^{2}}{\sum_{i=1}^{m}w_{ \mathcal{I}}^{i}+\sum_{i=1}^{m}w_{\mathcal{O}}^{i}}\] \[= \frac{\sum_{i=1}^{m}1\cdot(\mathbf{x}_{i}-\mu_{\mathcal{IO}})^{2 }+\mathbf{0}}{\sum_{i=1}^{m}1+\sum_{i=1}^{m}0}\] \[= \frac{\sum_{i=1}^{m}1\cdot(\mathbf{x}_{i}-\mu_{\mathcal{IO}})^{2 }}{m}\] \[= \sigma_{\mathcal{I}}^{2}.\]

The weighted batch normalizing transform based on mini-batch \(\mathcal{IO}\) for \(\mathbf{x}_{i}\),

\[WBN_{\mathcal{IO}}(\mathbf{x}_{i},\mathbf{w})=\gamma\frac{\mathbf{x}_{i}-\mu _{\mathcal{IO}}^{\mathbf{w}}}{\sqrt{\sigma_{\mathcal{IO}}^{\mathbf{w}}\ {}^{2}+\epsilon}}+\beta=\gamma\frac{\mathbf{x}_{i}-\mu_{\mathcal{I}}}{\sqrt{ \sigma_{\mathcal{I}}^{2}+\epsilon}}+\beta,\] (A.55)

which proves that \(BN_{\mathcal{I}}(\mathbf{x}_{i})=WBN_{\mathcal{IO}}(\mathbf{x}_{i},\mathbf{w})\).