PaperlayerView exact revision on arXiv

Source-linked AI summary

Uncertainty Aware Semi-Supervised Learning on Graph Data

Xujiang Zhao, Feng Chen, Shu Hu, Jin-Hee Cho

arXiv:2010.12783v2cs.LG

TL;DR

GNNs lack mechanisms for handling multiple uncertainty sources in semi-supervised node classification, motivating a framework that combines deep-learning and belief/evidence-theory uncertainties. The paper uses GKDE to estimate node-level Dirichlet distributions and evaluates uncertainty-based misclassification and OOD detection. Dissonance performs best for misclassification detection, while vacuity performs best for OOD detection, with GKDE and the Teacher network further improving accuracy and uncertainty estimates.

  • Problem

    GNNs do not account for different uncertainty types associated with class probabilities in semi-supervised node classification.

  • Method

    The paper combines deep-learning and belief/evidence-theory uncertainty estimates with GKDE for node-level Dirichlet distribution estimation.

  • Results

    Dissonance-based detection performed best for misclassification detection, while vacuity-based detection performed best for OOD detection across six real graph datasets.

  • Takeaways & Limitations

    GKDE and the Teacher network further enhanced node-classification accuracy and uncertainty estimates.

  • Takeaways & Limitations

    The paper identifies further work to determine whether the framework can enhance misclassification or OOD detection and affect other real-world problems.

Abstract

from arXiv · show

Thanks to graph neural networks (GNNs), semi-supervised node classification has shown the state-of-the-art performance in graph data. However, GNNs have not considered different types of uncertainties associated with class probabilities to minimize risk of increasing misclassification under uncertainty in real life. In this work, we propose a multi-source uncertainty framework using a GNN that reflects various types of predictive uncertainties in both deep learning and belief/evidence theory domains for node classification predictions. By collecting evidence from the given labels of training nodes, the Graph-based Kernel Dirichlet distribution Estimation (GKDE) method is designed for accurately predicting node-level Dirichlet distributions and detecting out-of-distribution (OOD) nodes. We validated the outperformance of our proposed model compared to the state-of-the-art counterparts in terms of misclassification detection and OOD detection based on six real network datasets. We found that dissonance-based detection yielded the best results on misclassification detection while vacuity-based detection was the best for OOD detection. To clarify the reasons behind the results, we provided the theoretical proof that explains the relationships between different types of uncertainties considered in this work.

1 Introduction

The paper argues that GNNs achieve strong semi-supervised node-classification performance but do not account for diverse predictive uncertainties. It proposes a multi-source uncertainty framework combining deep-learning and belief/evidence-theory uncertainties, with GKDE and theoretical and empirical validation.

  • GNNs perform strongly in semi-supervised node classification but do not consider diverse uncertainty types in their decision process.
  • The framework estimates uncertainties from deep learning and belief/evidence theory, including dissonance and vacuity.
  • GKDE is designed to reduce errors in quantifying predictive uncertainties and support node-level Dirichlet distribution estimation.
  • Theoretical analysis relates the uncertainty types and shows that OOD nodes may have high predictive uncertainty under GKDE.
  • Experiments on six real graph datasets found dissonance best for misclassification detection and vacuity best for OOD detection.

2 Related Work

Prior work studies predictive uncertainty through Bayesian deep learning and belief or evidence theory. These traditions emphasize different uncertainty sources, including data noise, limited model knowledge, missing evidence, and conflicting evidence.

  • Bayesian neural networks commonly distinguish aleatoric uncertainty from data randomness and epistemic uncertainty from limited model knowledge.
  • Bayesian deep-learning frameworks estimate aleatoric and epistemic uncertainty in tasks such as depth regression and semantic segmentation.
  • Belief theory addresses uncertainty caused by unreliable, incomplete, deceptive, or conflicting evidence.
  • Subjective Logic represents predictive uncertainty using vacuity from lack of evidence and vagueness from failure to discriminate a belief state.

3 Multidimensional Uncertainty and Subjective Logic

The paper represents class predictions with subjective opinions and Dirichlet distributions, separating evidence, belief, vacuity, dissonance, aleatoric uncertainty, and epistemic uncertainty. These measures provide complementary views of predictive uncertainty.

  • Subjective Logic represents a multinomial opinion with belief mass, uncertainty mass corresponding to vacuity, and a base-rate distribution.
  • A multinomial opinion is equivalently represented by a K-dimensional Dirichlet probability density function.
  • Class evidence contributes to Dirichlet strength through α_k = e_k + a_kW, where e_k measures supporting observations and W is uncertain evidence weight.
  • The framework discusses multiple subjective-logic uncertainty dimensions but focuses on vacuity and dissonance alongside aleatoric and epistemic uncertainty.
  • Vacuity reflects insufficient evidence or knowledge, whereas dissonance measures conflicting belief masses and is zero when all belief masses are zero.
  • Probabilistic uncertainty uses entropy, aleatoric uncertainty, and epistemic uncertainty, with epistemic uncertainty obtained from entropy after accounting for aleatoric uncertainty.

4 Relationships Between Multiple Uncertainties

The paper analyzes how uncertainty measures behave across confident, conflicting, and OOD predictions. It concludes that vacuity and dissonance distinguish OOD from conflicting predictions more clearly than entropy, aleatoric, or epistemic uncertainty.

  • The framework tracks vacuity, dissonance, aleatoric uncertainty, epistemic uncertainty, and entropy as uncertainty measures.
  • Confident predictions concentrate near one simplex corner, conflicting predictions produce a central distribution, and OOD predictions yield a flat simplex distribution from α = [1, 1, 1].
  • For all prediction scenarios, the theorem gives uv + udiss ≤ 1 and uv > uepis.
  • For OOD samples with uniform prediction, 1 = uv = uen > ualea > uepis > udiss = 0.
  • In the limiting equal-strength case, the uncertainty ordering is uen > ualea > udiss > uv > uepis.
  • Entropy, aleatoric, and epistemic uncertainty cannot distinguish OOD from conflicting predictions, whereas vacuity is high for OOD and dissonance is high for conflicting predictions.

5 Uncertainty-Aware Semi-Supervised Learning

The framework predicts node-level Dirichlet distributions and class probabilities while quantifying multiple uncertainty types in semi-supervised graphs. It combines Subjective Bayesian GNNs, GKDE-based evidential estimation, and teacher-network refinement, with GKDE linking graph proximity to vacuity and dissonance patterns.

  • Framework overview: The framework predicts subjective opinions as node-level Dirichlet distributions, enabling vacuity, dissonance, aleatoric, and epistemic uncertainty estimates alongside testing-node class probabilities.It uses posterior model parameters and estimated subjective opinions to quantify these uncertainty types.
  • Subjective Bayesian GNN: Subjective GNNs replace softmax with a non-negative activation layer so outputs can parameterize predicted Dirichlet distributions.The resulting parameters define the node-level Dirichlet distribution used for evidential uncertainty estimation.
  • Subjective Bayesian GNN: Subjective Bayesian GNNs model probabilistic uncertainty by placing a prior over model parameters and estimating the posterior through dropout inference.Training with stochastic gradient descent learns an approximate weight distribution, while the loss targets prediction error and variance.
  • Graph-based Kernel Dirichlet distribution Estimation (GKDE): GKDE estimates each node’s prior Dirichlet distribution from labeled training-node evidence and graph distances, then minimizes KL-divergence between predicted and prior distributions.The prior evidence aggregates kernel-weighted contributions from training nodes, with node distance determining their distributional effect.
  • Graph-based Kernel Dirichlet distribution Estimation (GKDE): GKDE encodes high vacuity for nodes far from training nodes and high dissonance for nodes near class boundaries.The framework uses these learned patterns to prioritize data relevance through evidential uncertainty.
  • Teacher-network refinement: Teacher-network distillation refines node-level class probabilities by regularizing the proposed student model toward a pretrained vanilla GNN.The objective combines the base loss with KL-divergence terms for the GKDE prior and teacher predictions.

6 Experiments

Experiments on six network datasets compare uncertainty estimates for misclassification and OOD detection. Dissonance performs best for misclassification detection, while vacuity performs best for OOD detection; GKDE and the Teacher Network further improve results.

  • Experimental Setup: Experiments use six datasets spanning citation, coauthor, and Amazon networks, with comparisons against state-of-the-art counterparts.The datasets are Cora, Citeseer, Pubmed, Coauthor Physics, Amazon Computer, and Amazon Photo.
  • Misclassification Detection: Dissonance-based detection outperforms other uncertainty estimates for misclassification detection.The observed performance order is Dissonance > Entropy ≈ Aleatoric > Vacuity ≈ Epistemic.
  • OOD Detection: Vacuity-based detection outperforms other uncertainty estimates for OOD detection.The observed performance order is Vacuity > Entropy ≈ Aleatoric > Epistemic ≈ Dissonance.
  • Ablation Study: GKDE improves OOD detection by 30% with vacuity, while the Teacher Network further improves node classification accuracy.The ablation findings support the theoretical claim that OOD nodes have higher vacuity than other nodes.
  • Uncertainty Comparison: Epistemic uncertainty is less effective than vacuity for OOD detection in these semi-supervised experiments.The paper suggests epistemic uncertainty may capture less OOD-related information because it is smaller than vacuity and has been less validated in semi-supervised learning.

7 Conclusion

The paper proposes a multi-source uncertainty framework for semi-supervised GNN node classification. Experiments show that dissonance is best for misclassification detection and vacuity is best for OOD detection, with GKDE and the Teacher Network further improving performance.

  • Conclusion: The framework combines uncertainty estimates from deep learning and evidence/belief theory for node classification and OOD detection.The framework includes multiple uncertainty types and uses GKDE and a Teacher Network to improve classification and uncertainty estimates.
  • Conclusion: Dissonance-based detection performs best for misclassification detection, while vacuity-based detection performs best for OOD detection.These results are reported relative to other competitive counterparts.

Broader Impact

The proposed uncertainty-aware GNN framework predicts multiple uncertainties and may support applications beyond semi-supervised node classification. The authors identify further research on its effects in misclassification and OOD detection as an opportunity.

  • The framework is designed to predict multiple uncertainties of different roots for GNNs.
  • Potential applications include computer vision, natural language processing, recommendation systems, traffic prediction, and generative models.
  • Future research could investigate whether the framework further enhances misclassification or OOD detection.
  • The authors encourage studying how the framework addresses real-world problems involving different types of uncertainty.

A.1 Theorem 1’s Proof

Theorem 1 establishes how vacuity, dissonance, entropy, aleatoric, and epistemic uncertainties relate under out-of-distribution and conflicting-prediction scenarios. It also connects graph distance to GKDE-estimated vacuity, explaining why distant test nodes are expected to have higher OOD uncertainty.

  • Special relations on the OOD and the CP: For OOD samples with uniform predictions, vacuity and entropy equal 1, while aleatoric exceeds epistemic, which exceeds dissonance at 0.The stated ordering is 1 = uv = uen > ualea > uepis > udiss = 0.
  • Special relations on the OOD and the CP: For conflicting in-distribution predictions, entropy exceeds aleatoric, which exceeds dissonance, vacuity, and epistemic uncertainty.The theorem states uen > ualea > udiss > uv > uepis.
  • General relations on all prediction scenarios: Vacuity and dissonance cannot increase together: high vacuity implies lower dissonance, whereas high dissonance requires substantial evidence and low vacuity.The interpretation distinguishes missing evidence from conflicting evidence.
  • General relations on all prediction scenarios: Vacuity upper-bounds epistemic uncertainty, so treating the two as identical is valid only in the extreme case of sufficiently large evidence.The theorem interpretation explicitly rejects general equivalence between vacuity and epistemic uncertainty.
  • General relations on all prediction scenarios: Entropy, aleatoric, and epistemic uncertainty cannot distinguish OOD samples from conflicting predictions, whereas vacuity and dissonance can.OOD samples typically have high vacuity and low dissonance, while conflicting predictions show the opposite pattern.
  • GKDE-based vacuity relation: If a testing node is farther from every training node, GKDE estimates higher vacuity, indicating that OOD nodes are expected to have high vacuity.The proposition compares graph-distance vectors to relate distance from labeled nodes to estimated vacuity.

B.2 Description of Datasets

The experiments use six graph datasets spanning citation, coauthorship, and Amazon co-purchase networks, with fixed labeled-node setups and standard detection metrics. OOD detection withholds randomly selected categories during training, while the proposed components improve classification or OOD detection in reported comparisons.

  • Datasets: Six datasets comprise Cora, Citeseer, Pubmed, Coauthor Physics, Amazon Computer, and Amazon Photo.The first three are citation networks; the latter datasets represent coauthorship and Amazon co-purchase graphs.
  • Experimental setup: All datasets use undirected graphs with 20 training nodes per category, alongside dataset-specific validation and split protocols.Citation datasets use an additional 500-node validation set for hyperparameter selection.
  • Metrics: AUROC measures ranking of positive above negative examples, while AUPR summarizes the precision–recall curve.A perfect AUROC is 100%, and the ideal precision and recall values are both 1.
  • OOD detection setup: OOD experiments randomly designate 1–4 categories as OOD and train only on nodes from the remaining categories.The model therefore predicts only the categories observed during training; positive ratio denotes the OOD share of test nodes.
  • Ablation findings: The teacher network increases node-classification accuracy by 0.2%–1.5%, while GKDE with uncertainty estimates increases OOD detection by 4%–30%.These component effects are reported in Tables 8 and 9.
  • Visualization and uncertainty behavior: GKDE improves OOD detection on the Amazon Photo visualization, while dissonance shows low uncertainty and outperforms alternatives for node-classification prediction.The visualization discussion links uncertainty patterns to the reported detection behavior.

C.6 Analysis for Epistemic Uncertainty in OOD Detection

Epistemic uncertainty is less effective for OOD detection than vacuity in the reported semi-supervised setting, despite prior supervised-learning results favoring epistemic uncertainty. An auxiliary image experiment reports the same reversal under semi-supervised learning.

  • OOD detection comparison: Epistemic uncertainty is less effective for OOD detection than the vacuity-based approach in the reported experiments.This contrasts with its reported effectiveness in supervised computer-vision applications.
  • Auxiliary image experiment: In the semi-supervised image experiment, OOD samples show low epistemic uncertainty, making epistemic uncertainty less effective for detection.The experiment uses MNIST and FashionMNIST samples with 50 labeled images and 50% OOD images among unlabeled data.
  • Interpretation: The reported semi-supervised pattern is opposite to the supervised-learning pattern previously observed for epistemic uncertainty.The authors relate the image setting to semi-supervised node classification because unlabeled samples are used during training.

D Derivations for Joint Probability and KL Divergence

The derivation specifies how the model forms joint and marginal class probabilities from the learned predictive distribution. It also defines KL-divergence objectives for comparing predictive distributions and Dirichlet distributions.

  • Probability derivation: At test time, the model infers the joint probability and obtains the posterior class-label distribution from the mean of the Dirichlet distribution.The derivation then specializes the probability calculation to a specific node through marginal probability.
  • Probability derivation: The node-specific class probability is derived from the model output α(m) = f(A, r, θ(m)) with θ(m) sampled from q(θ).This connects Bayesian parameter sampling to the resulting Dirichlet parameters.
  • KL-divergence derivation: The derivation defines KL-divergence between the predictive probability and its reference distribution, then gives a closed form for two Dirichlet distributions.These expressions support distributional comparison within the model.
Loading 2010.12783v2…