Research map / Graph learning / Graph algorithms and clustering
Robust Offline 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.
Proposes an offline active learning method for node-level tasks that combines a spectral "informativeness" criterion (bandwidth frequency) with a randomized spectral-sparsification "representativeness" sampling step, giving generalization bounds for graph signal recovery.
Problem
Selecting which nodes to label in a graph under a fixed budget, offline (no sequential annotator feedback), when both network structure and node covariates matter and labels/covariates may be noisy.
Approach
Defines a graph function space Proj_{L_omega} Span(X) and a node-set "bandwidth frequency" that measures identifiable signal complexity; a two-stage procedure first samples a candidate set via a spectral-sparsification potential-function method (representativeness, controls the condition number of the covariate design) and then picks the candidate maximizing an informativeness gradient, yielding w
Key results
- On Cora with 35 labeled nodes the proposed method reaches 78.4% Micro-F1 vs 77.5% for RIM and 68.2% for random sampling.
- On Texas with 45 labels, the proposed method reaches 80.4% Micro-F1 vs 74.6% for the best baselines (RIM, GPT).
- On Ogbn-Arxiv the Macro-F1 gain is up to 4.8 points at 320 labeled nodes over the best baseline; the method takes about 2.1 seconds per queried node at n=169,343.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed biased-sampling query method instead of IGP | SGC node classification · Cora, 35 labeled nodes | Micro-F1 (%): 77.4 ± 1.7 -> 78.4 ± 1.7 | Helped |
| Use the proposed biased-sampling query method instead of IGP | SGC node classification · Pubmed, 30 labeled nodes | Micro-F1 (%): 82.3 ± 1.4 -> 79.1 ± 0.6 | Hurt |
| Use the proposed biased-sampling query method instead of IGP | SGC node classification · Citeseer, 60 labeled nodes | Micro-F1 (%): 72.1 ± 0.9 -> 72.2 ± 1.3 | No clear effect |
| Use the proposed biased-sampling query method instead of RIM | SGC node classification · Chameleon, 75 labeled nodes | Micro-F1 (%): 42.8 ± 3.0 -> 35.7 ± 3.0 | Hurt |
| Use the proposed biased-sampling query method instead of GPT | SGC node classification · Texas, 15 labeled nodes | Micro-F1 (%): 72.6 ± 2.0 -> 75.0 ± 1.9 | Helped |
| Use the proposed biased-sampling query method instead of GPT | SGC node classification · Ogbn-Arxiv, 320 labeled nodes | Macro-F1: 29.5 ± 0.8 -> 34.3 ± 1.4 | Helped |
| Use the proposed method instead of baselines | Synthetic graph regression · Synthetic networks across labeling-noise settings | Prediction MSE | Helped |
| Combine eigenvectors from the lowest and highest ends of the spectrum for heterophilic graphs | Proposed method · Chameleon and Texas | Micro-F1 (%) | Mixed |
Surprising findings
- Partition-based baselines GPT and SPA are highly sensitive to the number of partitions, limiting generalization to networks without clear community structure.
- Theory suggests the method is advantageous only when the minimum degree is large and certain network statistics are small; the authors also note that handling heterophily required switching to a signal subspace from both smallest and largest eigenvalues.
Limitations
- Theoretical analysis is developed for regression; extension to classification is conjectured rather than proven.
- Handling heterophilous networks requires a priori knowledge of label construction (using both low- and high-frequency eigenvectors).
Experimental setup
Datasets: Cora Pubmed Citeseer Chameleon Texas Ogbn-Arxiv Co-Physics Watts-Strogatz synthetic Stochastic block model synthetic Barabasi-Albert synthetic
Benchmarks: Cora Pubmed Citeseer Chameleon Texas Ogbn-Arxiv Co-Physics
Metrics: Micro-F1 Macro-F1 MSE query time
Baselines: D-optimal RIM GPT SPA AGE IGP Random
Builds on: graph signal sampling spectral graph sparsification (batson et al.) simplified graph convolution
Closest papers by meaning
- Algorithms and Hardness for Active Learning on Graphs (ICML 2025 · similarity 0.90)
- Structural Fairness-aware Active Learning for Graph Neural Networks (ICLR 2024 · similarity 0.89)
- Active Learning on Attributed Graphs via Graph Cognizant Logistic Regression and Preemptive Query Generation (ICML 2020 · similarity 0.88)
- Know Your Neighbors: Subgraph Importance Sampling for Heterophilic Graph Active Learning (AAAI 2026 · similarity 0.88)
- Uncertainty for Active Learning on Graphs (ICML 2024 · similarity 0.87)
- Information Gain Propagation: a New Way to Graph Active Learning with Soft Labels (ICLR 2022 · similarity 0.87)
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.