Research map / Probabilistic and scientific modeling / Uncertainty and Gaussian processes
Uncertainty for Active Learning on Graphs
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Benchmarks uncertainty sampling for graph active learning, derives ground-truth epistemic uncertainty from a CSBM data-generating process, and proposes approximate disentangled estimators (MP/ESP) that outperform existing uncertainty estimators on real citation datasets.
Problem
Uncertainty sampling for active learning on graphs (node classification) is under-explored; existing uncertainty estimators often fail to beat random querying, and it is unclear whether disentangling aleatoric and epistemic uncertainty helps as in i.i.d. settings.
Approach
Defines ground-truth aleatoric, epistemic, and total confidence for a Bayesian classifier under the graph data-generating process, proves epistemic uncertainty equals the relative gain in posterior of remaining true labels (so querying the most epistemic node is optimal), and approximates it with multiple pseudo-labels (MP) or expected single pseudo-label (ESP).
Key results
- On CoraML, the best strategy is SGC with GEEM (AUC 71.39), while random sampling reaches 62.51 for GCN; most uncertainty-sampling estimators fail to beat random.
- On real datasets, the proposed approximate epistemic estimator ESP reaches AUC 71.45 on CoraML and 85.52 on Amazon Photos, outperforming Ensemble (63.47 and 84.46 respectively) and other uncertainty estimators.
- On synthetic CSBM graphs, ground-truth epistemic uncertainty significantly outperforms random queries and aleatoric/total uncertainty; using an inaccurate generative model that ignores non-edges harms performance.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the ESP approximation of disentangled epistemic uncertainty instead of existing epistemic uncertainty estimators | Uncertainty Sampling · CoraML, Citeseer, PubMed, Amazon Photos, Amazon Computers | AUC: 63.97 -> 71.45; 82.94 -> 83.43; 63.70 -> 64.36; 84.46 -> 85.52; 68.38 -> 72.54 | Helped |
| Use the MP approximation of disentangled epistemic uncertainty instead of existing epistemic uncertainty estimators | Uncertainty Sampling · CoraML, Citeseer, Amazon Photos | AUC: 63.97 -> 68.16; 82.94 -> 83.96; 84.46 -> 75.37 | Helped |
| Replace MP's simultaneous pseudo-labeling with ESP's expectation over one pseudo-label at a time | Approximate epistemic uncertainty · CoraML, PubMed, Amazon Photos, Amazon Computers | AUC: 68.16 -> 71.45; 75.37 -> 85.52 | Helped |
| Use ground-truth epistemic uncertainty rather than random, aleatoric, or total uncertainty | Uncertainty Sampling on CSBM graphs · CSBM synthetic graphs | AUC | Helped |
| Disentangle uncertainty into aleatoric and epistemic components and acquire using the epistemic component | Uncertainty Sampling on graphs · CSBM synthetic graphs | AUC | Helped |
| Use total uncertainty instead of epistemic uncertainty for acquisition | Uncertainty Sampling on CSBM graphs · CSBM synthetic graphs | AUC | Hurt |
| Use aleatoric uncertainty instead of epistemic uncertainty for acquisition | Uncertainty Sampling on CSBM graphs · CSBM synthetic graphs | AUC | Hurt |
| Neglect non-existing edges in the modeled data-generating process (ablation) | Ground-truth uncertainty estimator · CSBM synthetic graphs | AUC | Hurt |
| Use conventional uncertainty estimators for Uncertainty Sampling rather than random acquisition | GCN, APPNP, MC-Dropout, BGCN, GPN, and Ensemble · Citation and co-purchase graph benchmarks | AUC | Mixed |
Surprising findings
- Most uncertainty-sampling estimators, including epistemic ones, underperform random sampling on real graphs, while aleatoric uncertainty only matches random.
- Epistemic uncertainty proxies (MC-Dropout, BGCN, GPN, energy) often significantly underperform random queries when used for uncertainty sampling.
Limitations
- The approximate ground-truth uncertainty requires retraining auxiliary classifiers per query, O(n*c) cost, limiting scalability to lightweight models and small datasets.
- Approximations are exposed to miscalibration of GNNs and pseudo-label errors, especially with small training sets.
- Theoretical analysis assumes a known Bayesian classifier and CSBM parameters; real-data results rely on heuristic approximations.
Experimental setup
Datasets: CoraML Citeseer PubMed Amazon Photos Amazon Computers CSBM synthetic graphs
Benchmarks: CoraML Citeseer PubMed Amazon Photos Amazon Computers
Metrics: AUC of accuracy vs. number of acquired labels final accuracy
Baselines: Random Coreset AGE ANRMAB GEEM SEAL Coreset PPR MC-Dropout Ensembles BGCN GPN Energy
Builds on: GCN APPNP GPN Bayesian GCN AGE GEEM
Closest papers by meaning
- Uncertainty Herding: One Active Learning Method for All Label Budgets (ICLR 2025 · similarity 0.88)
- Robust Sampling for Active Statistical Inference (NeurIPS 2025 · similarity 0.87)
- Robust Offline Active Learning on Graphs (NeurIPS 2024 · similarity 0.87)
- Accurate and Scalable Estimation of Epistemic Uncertainty for Graph Neural Networks (ICLR 2024 · similarity 0.87)
- Uncertainty Estimation for Heterophilic Graphs Through the Lens of Information Theory (ICML 2025 · similarity 0.86)
- Linear Uncertainty Quantification of Graphical Model Inference (NeurIPS 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.