PaperlayerView exact revision on arXiv

Source-linked AI summary

Uncertainty for Active Learning on Graphs

Dominik Fuchsgruber, Tom Wollschläger, Bertrand Charpentier, Antonio Oroz, Stephan Günnemann

arXiv:2405.01462v3cs.LG

TL;DR

Active Learning with uncertainty is well established for independent data, but its usefulness for graph node classification and the value of disentangling uncertainty remain unclear. The paper benchmarks graph Uncertainty Sampling, derives Bayesian ground-truth aleatoric and epistemic uncertainties, and proves their connection to optimal querying. Epistemic Uncertainty Sampling performs effectively when uncertainty is properly disentangled, while the proposed real-data approximation outperforms other uncertainty estimators.

  • Problem

    The effectiveness of Uncertainty Sampling for graph node classification, especially beyond total predictive uncertainty, remains under-explored.

  • Method

    The paper benchmarks uncertainty and traditional active-learning strategies, derives ground-truth aleatoric and epistemic uncertainty from the data-generating process, and proves their alignment with active learning.

  • Results

    Epistemic Uncertainty Sampling is highly effective when uncertainty is properly disentangled, and an approximation consistently outperforms other uncertainty estimators on real data.

  • Takeaways & Limitations

    The analysis provides theoretical groundwork for developing principled uncertainty estimators on graphs that evaluate uncertainty by its active-learning usefulness.

  • Takeaways & Limitations

    Exact disentangled uncertainty requires unavailable unobserved labels, while the proposed approximation requires auxiliary classifiers for each query and is limited to lightweight models and small datasets.

Abstract

from arXiv · show

Uncertainty Sampling is an Active Learning strategy that aims to improve the data efficiency of machine learning models by iteratively acquiring labels of data points with the highest uncertainty. While it has proven effective for independent data its applicability to graphs remains under-explored. We propose the first extensive study of Uncertainty Sampling for node classification: (1) We benchmark Uncertainty Sampling beyond predictive uncertainty and highlight a significant performance gap to other Active Learning strategies. (2) We develop ground-truth Bayesian uncertainty estimates in terms of the data generating process and prove their effectiveness in guiding Uncertainty Sampling toward optimal queries. We confirm our results on synthetic data and design an approximate approach that consistently outperforms other uncertainty estimators on real datasets. (3) Based on this analysis, we relate pitfalls in modeling uncertainty to existing methods. Our analysis enables and informs the development of principled uncertainty estimation on graphs.

1. Introduction

This work studies Uncertainty Sampling for graph node classification, where existing methods often use total uncertainty despite the distinct roles of aleatoric and epistemic uncertainty. It benchmarks graph active-learning strategies, derives ground-truth uncertainty from the data-generating process, and finds that epistemic uncertainty can align queries with improved prediction confidence.

  • Active Learning queries informative labels to save labeling labor and training effort that would otherwise be spent on uninformative labeled data.
  • Epistemic uncertainty is effective for Uncertainty Sampling when uncertainty is disentangled, whereas total uncertainty can prioritize irreducible factors.
  • Many uncertainty estimators and traditional acquisition strategies do not outperform random acquisition in the extensive node-classification active-learning benchmark.
  • The study derives ground-truth aleatoric and epistemic uncertainty from the data-generating process and formally proves their alignment with active-learning objectives.
  • The work empirically confirms epistemic Uncertainty Sampling on synthetic and real data using an approximation that outperforms state-of-the-art uncertainty estimators off-the-shelf.

2. Background

The paper formulates pool-based active learning for semi-supervised node classification and distinguishes irreducible aleatoric uncertainty from reducible epistemic uncertainty. It uses a Contextual Stochastic Block Model to study exact ground-truth uncertainty under an explicit graph-generating process.

  • In pool-based active learning, the learner queries unobserved node labels, adds them to the observed set, and retrains the model at each iteration.
  • Aleatoric uncertainty is irreducible, epistemic uncertainty reflects knowledge gaps addressable by data acquisition, and total uncertainty combines both.
  • The Contextual Stochastic Block Model generates labels, class-conditional node features, and graph edges from an explicit data-generating process.

3. Related Work

Prior active-learning work largely targets i.i.d. data, while graph methods typically use predictive or total uncertainty without disentangling aleatoric and epistemic components. The paper positions this omission as an open opportunity for epistemic uncertainty estimation on graphs.

  • Active-learning methods for i.i.d. data include diversity-based, uncertainty-based, and combined strategies, with uncertainty often derived from predictive distributions or Bayesian disagreement.
  • Graph active-learning research spans random fields, risk minimization, adversarial learning, knowledge transfer, and soft-label querying, but uncertainty methods generally do not separate aleatoric from epistemic uncertainty.
  • The exploration of graph Uncertainty Sampling beyond total uncertainty remains largely uncharted, motivating the paper’s focus on epistemic uncertainty estimators.
  • Graph uncertainty estimation includes deterministic predictive distributions, Bayesian ensembles, Monte Carlo Dropout, variational methods, evidential models, and Gaussian processes, with differing access to disentangled uncertainties.

4. Benchmarking Uncertainty Sampling Approaches for Active Learning on Graphs

The benchmark finds that uncertainty sampling and most other acquisition strategies do not reliably outperform random selection on graph node classification. GEEM is the main exception, while uncertainty estimators generally fail to guide effective queries on Citeseer and related benchmarks.

  • Uncertainty Sampling: No uncertainty estimator significantly outperforms random selection on Citeseer, and many uncertainty methods underperform it.
  • Experimental Setup: Across five node-classification datasets, the study evaluates GCN, APPNP, MC-Dropout, BGCN, GPN, and ensemble models over repeated active-learning runs.The setup acquires one label per iteration, initializes one labeled node per class, and uses a budget of 4C.
  • Evaluation: The evaluation summarizes acquisition quality with normalized area under the accuracy curve and final accuracy after the labeling budget is exhausted.Higher accuracy with fewer queries produces a larger area under the curve, reported as an average-accuracy summary.
  • Non-Uncertainty-based Strategies: Figure 2 compares accuracy curves for active-learning strategies using GCN and SGC classifiers on Citeseer, with GEEM shown only for SGC because of tractability.The reported comparison is whether strategies significantly exceed random selection.
  • Non-Uncertainty-based Strategies: Traditional acquisition strategies generally fail to consistently improve over random selection, with GEEM the only method that consistently outperforms it.GEEM requires O(nC) models per acquisition, making it intractable for larger datasets and models beyond SGC.
  • Uncertainty Sampling: Figure 3 shows that no uncertainty-sampling method significantly outperforms random selection on Citeseer.Aleatoric uncertainty matches random queries, epistemic uncertainty often performs worse, and only ensembles slightly exceed random selection on some datasets.

5. Ground-Truth Uncertainty from the Data Generating Process

The paper defines Bayesian total, aleatoric, and epistemic uncertainty from the data-generating process, then proves that epistemic uncertainty aligns with the active-learning objective.

  • Bayesian classifier: The Bayesian classifier predicts unobserved labels by maximizing their posterior under the data-generating process, conditioned on observed labels.Its parameter posterior p(θ | A, X, yO) captures uncertainty over classifier parameters.
  • Confidence decomposition: Total confidence incorporates aleatoric randomness from the data-generating process and epistemic uncertainty caused by limited observed labels.As more labels are observed, irreducible aleatoric uncertainty increasingly dominates total predictive uncertainty.
  • Confidence decomposition: Epistemic uncertainty is obtained by comparing total and aleatoric confidence, equivalently favoring nodes whose uncertainty is predominantly non-aleatoric.The ratio formulation can also be expressed as a difference between log-likelihoods without changing acquisition behavior.
  • Ground-truth uncertainty: Epistemic uncertainty equals the relative gain in posterior confidence over the remaining true labels from acquiring a node.This equivalence makes querying the most epistemically uncertain node optimal for the Bayesian classifier.
  • Scope and limitation: Exact disentangled uncertainty requires unavailable labels for unobserved nodes, motivating tractable approximations despite the theoretical optimality result.The optimality claim applies to Bayesian classifiers with a posterior over parameters of the generative process.

6. Uncertainty Sampling with Ground-Truth Uncertainty

Experiments on CSBM graphs show that epistemic uncertainty sampling outperforms random, aleatoric, and total-uncertainty queries, while faithful generative modeling further matters.

  • Disentangling Uncertainty: Epistemic uncertainty significantly outperforms random, aleatoric, and total uncertainty on CSBM graphs, confirming its alignment with active learning.The evaluation uses five 100-node, 7-class CSBM graphs, with larger-graph results reported separately.
  • Disentangling Uncertainty: Total uncertainty can select intrinsically ambiguous nodes, improving the posterior by removing difficult cases rather than informing predictions on the remaining graph.Epistemic acquisition instead evaluates the posterior gain from acquiring each node.
  • Disentangling Uncertainty: Ground-truth epistemic uncertainty significantly outperforms other estimators and random queries, whereas aleatoric queries do not align with the active-learning objective.This follows from aleatoric uncertainty optimizing a posterior over unobserved true labels without accounting for information gained by the query.
  • Modelling the Data Generating Process: Misrepresenting the data-generating process harms uncertainty sampling even when aleatoric and epistemic uncertainty are properly disentangled.The inaccurate model neglects non-existing edges, resembling message-passing estimators that use only observed edges.
  • Pitfalls in US for Graphs: Effective graph uncertainty sampling requires both aleatoric–epistemic disentanglement and an expressive model of the unknown data-generating process.The paper identifies these requirements as explanations for the weak performance of existing estimators.

7. Disentangling Uncertainty on Real Data

The paper approximates theoretically grounded disentangled uncertainty on real graph data using multiple pseudo-labels or expectations over possible labels. The proposed epistemic uncertainty consistently outperforms existing uncertainty-sampling estimators and often matches the strongest non-uncertainty strategy.

  • 7. Disentangling Uncertainty on Real Data: The framework approximates unavailable ground-truth uncertainty through two paradigms: Multiple Pseudo-Labels (MP) and Expected Single Pseudo-Label (ESP).
  • 7. Disentangling Uncertainty on Real Data: MP estimates aleatoric confidence by augmenting data with predictions for unobserved labels and training auxiliary classifiers on those pseudo-labels.
  • 7. Disentangling Uncertainty on Real Data: ESP conditions on one possible label at a time and averages over labels using the predictive distribution, avoiding simultaneous pseudo-label substitution.
  • 7. Disentangling Uncertainty on Real Data: ESP is faster in practice than MP despite worse asymptotic runtime because its auxiliary classifiers use smaller training sets.
  • 7. Disentangling Uncertainty on Real Data: The approximate epistemic uncertainty consistently outperforms existing epistemic estimators in average AUC.
  • 7. Disentangling Uncertainty on Real Data: Across datasets, approximate epistemic uncertainty outperforms other uncertainty-sampling techniques and often matches the best non-uncertainty active-learning strategy.

8. Applicability to Indepenent Data

The uncertainty framework is defined through an unknown data-generating process and therefore also applies to i.i.d. data. Its graph-specific value comes from modeling interdependence and using graph models to approximate the generative process.

  • 8. Applicability to Indepenent Data: The framework can be applied to i.i.d. data because its uncertainty definitions and theoretical alignment derive from the underlying data-generating process.
  • 8. Applicability to Indepenent Data: For graphs, the generative perspective provides a theoretically grounded way to account for instance interdependence, while GNN inductive biases may help approximate graph-generating processes.

9. Limitations

The work identifies epistemic uncertainty as a strong guide for graph active learning, but its proposed approximation is computationally limited and primarily serves as a principled research framework.

  • 9. Limitations: Epistemic uncertainty is presented as an optimal guide for active learning on graphs.
  • 9. Limitations: Training auxiliary classifiers for every query gives the method O(n ∗c) runtime complexity, limiting it to lightweight models and small datasets.

10. Conclusion

The study finds that uncertainty sampling on graphs is often only marginally better than random unless uncertainty is properly disentangled. Its theory and experiments establish epistemic uncertainty as an effective guide and motivate principled future estimators.

  • 10. Conclusion: Most active-learning strategies only marginally outperform random queries at best, while existing uncertainty estimators inadequately guide uncertainty sampling.
  • 10. Conclusion: The paper introduces ground-truth uncertainty estimates, proves alignment between epistemic uncertainty and active learning, and validates the findings on synthetic and real data.
  • 10. Conclusion: The results support epistemic uncertainty as a highly effective acquisition signal when uncertainty is properly disentangled.
  • 10. Conclusion: The study provides theoretical groundwork for uncertainty estimators on graphs and may inform related interdependent tasks such as link prediction.

Impact Statement

The paper argues that principled uncertainty estimation can improve data efficiency for graph learning, while acknowledging risks from non-benign use and misuse.

  • The analysis aims to make graph-based AI systems more reliable and data-efficient, potentially reducing their environmental impact.
  • The authors caution that researchers and practitioners should validate proposed uncertainty estimators carefully, especially in safety-critical domains.

A. Proofs

The paper formalizes uncertainty-guided active learning for graphs, evaluates existing strategies, and develops Bayesian uncertainty estimates aligned with label acquisition objectives.

  • A. Proofs: Acquiring the most epistemically uncertain node is an optimal active-learning strategy for the ideal classifier.
  • B.1. Active Learning: The active-learning protocol initializes one labeled node per class, retrains after each single-node acquisition, and uses a fixed budget of 5C queries.
  • B.3. Datasets: The benchmark covers citation and synthetic graph datasets, multiple GNN-based classifiers, uncertainty estimators, and repeated dataset splits and initializations.
  • C. Additional Metrics and Plots: Most traditional acquisition strategies and uncertainty estimators fail to outperform random sampling, while only GEEM consistently does so among non-uncertainty methods.
  • D. Computing Aleatoric and Total Confidence on CSBMs: Mean-field approximations make epistemic confidence tractable on larger graphs, but approximation errors can arise and sometimes become substantial for larger graphs.
  • E. Uncertainty Sampling with Ground-Truth Uncertainty: For CSBMs, epistemic uncertainty gives the strongest performance, total uncertainty also exceeds random sampling, and incorrect generative modeling reduces performance.

E.1. Ablation of the Proposed Acquisition Strategy on Different CSBM Configurations

The paper studies how ground-truth uncertainty behaves across synthetic graph conditions, proposes practical approximations, and shows that graph-aware epistemic uncertainty is most effective within important scope limits.

  • E.1. Ablation of the Proposed Acquisition Strategy on Different CSBM Configurations: The proposed estimator improves active learning most at intermediate structural SNRs and when node features are noisy, where structurally informative queries matter.
  • E.1. Ablation of the Proposed Acquisition Strategy on Different CSBM Configurations: Below structural SNR 1.0, the method does not outperform random acquisition because the mean-field fixed-point iteration fails to converge.
  • F. Visualization of Ground-Truth Uncertainty on a Toy Example: In the toy graph, acquiring node 7 reduces node 8’s epistemic uncertainty and shifts the next promising queries toward nodes 0 and 4.
  • F. Visualization of Ground-Truth Uncertainty on a Toy Example: The visual analysis shows that structural information shifts classifier decision boundaries and that absent edges can affect aleatoric uncertainty.
  • G.2. Expected Single Pseudo-Label (ESP): ESP estimates epistemic uncertainty by evaluating possible single-label conditionings, avoiding the intractable O(C^|U|) evaluations required by a full multiple-pseudo-label expectation.
  • G.3. Implementation: Although MP is theoretically cheaper, ESP is practically faster because its auxiliary classifiers use fewer labels, whereas MP can fail to finish within 72 hours.
  • G.3. Implementation: ESP consistently outperforms other epistemic uncertainty estimators, but its accuracy depends on model fidelity, pseudo-label quality, calibration, and backbone choice.
  • G.4. Approximating Ground-Truth Uncertainty without Graph Inductive Biases: Ignoring network effects deteriorates performance because graph structure helps approximate the data-generating process and identify informative queries.
Loading 2405.01462v3…