Research map / Graph learning / Graph algorithms and clustering
Algorithms and Hardness 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.
Gives the first resource-augmented (O(log n) slack) algorithm with guarantees for graph label selection on general weighted graphs via a flow gadget and greedy submodular selection, plus an NP-hardness-of-approximation result for unweighted graphs.
Problem
Offline active learning on graphs: choose k vertices whose labels best predict all other vertex labels under a label smoothness assumption (Guillory & Bilmes graph label selection objective), which is neither submodular nor supermodular and previously lacked guarantees on general graphs.
Approach
Reduce thresholded graph label selection to s-t max-flow in an augmented graph where selecting a vertex adds an edge to the sink; the flow value is submodular in the label set, so greedy selection gives O(log n) slack, with binary search over thresholds.
Key results
- Greedy flow-based algorithm returns a set of size O(log n)·k with Psi(L') at least the optimum for budget k on general weighted graphs, running in k·|V|·(|V|+|E|)^{1+o(1)} time.
- NP-hard to distinguish max Psi(L) <= 2 from >= 3 for general unweighted graphs, via reduction from maximum independent set on 3-regular graphs.
- On ca-GrQc with k=100, the proposed method achieves ratio 0.333 versus 0.132 for Guillory-Bilmes and 0.062 for Cesa-Bianchi et al.; it outperforms both baselines on all reported budgets except near k=n.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed algorithm instead of the strongest prior method | Graph label selection · ca-GrQc, k = 10, 50, 100 | Ψ(L): 0.054±0.006 -> 0.091; 0.066±0.011 -> 0.215; 0.132±0.011 -> 0.333 | Helped |
| Use the proposed algorithm instead of the strongest prior method | Graph label selection · ego-Facebook, k = 10, 50, 100 | Ψ(L): 0.076±0.008 -> 1.0; 0.396±0.055 -> 1.0; 0.831±0.339 -> 1.080 | Helped |
| Use the proposed algorithm instead of Guillory & Bilmes | Graph label selection · S(50), k = 3 | Ψ(L): 0.16±0.28 -> 1.0 | Helped |
| Use the proposed algorithm instead of Cesa-Bianchi et al. | Graph label selection · 3C(10, 30, 10), k = 3 | Ψ(L): 0.1 ± 0.03 -> 1.0 | Helped |
Surprising findings
- When the label budget approaches n, the proposed algorithm is outperformed by Guillory and Bilmes, since for stars it picks the center while the optimum may be to label all leaves.
Limitations
- Guarantee requires slack O(log n) in the label budget rather than an exact budget solution.
- Runtime is super-linear and prevents scaling to large real-world graphs.
- Hardness only shows constant-factor inapproximability for unweighted graphs; no approximation without slack is given.
Experimental setup
Datasets: Davis southern woman graph ca-GrQc (SNAP) ego-Facebook (SNAP) synthetic star S(50) synthetic clique-path graph 3C(10,30,10)
Benchmarks: Davis southern woman graph ca-GrQc ego-Facebook S(50) 3C(10,30,10)
Metrics: ratio Psi(L) achieved for given budget k
Baselines: Guillory and Bilmes (2009) heuristic Cesa-Bianchi et al. (2010) algorithm (BGVZ)
Builds on: Guillory and Bilmes graph label selection objective Cesa-Bianchi et al. tree-based active learning Goldberg densest subgraph flow reduction
Closest papers by meaning
- Robust Offline Active Learning on Graphs (NeurIPS 2024 · similarity 0.90)
- An Approximation Algorithm for Graph Label Selection (ICML 2026 · similarity 0.88)
- Active Learning for Decision Trees with Provable Guarantees (ICLR 2026 · similarity 0.87)
- Know Your Neighbors: Subgraph Importance Sampling for Heterophilic Graph Active Learning (AAAI 2026 · similarity 0.87)
- The Computational Complexity of Positive Non-Clashing Teaching in Graphs (ICLR 2025 · similarity 0.85)
- Improved Approximations for Hard Graph Problems using Predictions (ICML 2025 · similarity 0.85)
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.