Research map / Learning theory and algorithms / Sample complexity
Active Learning of Convex Halfspaces on Graphs
Maximilian Thiessen, Thomas Gärtner
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use convex hulls and extensions to deduce labels after each query (Theorem 5) instead of binary search per shortest-path cover | Active halfspace learning on graphs · Query complexity bound | upper bound on queries: |S*|(2 + ⌈log d(G)⌉) -> h(G) + ⌈log d(G)⌉ + max |W*=ab| | Improved |
| Greedy query selection instead of S2, active label propagation or random sampling | Halfspace learner · Two moons, Iris, grid, hypercube cut-vertex discovery | queries to find all cut vertices: at most 6 queries | Improved |
| Selective sampling instead of greedy selection (ablation) | Halfspace learner · Two moons, Iris, grid, hypercube | queries to deduce all labels: 2-8 queries more | Hurt |
| Halfspace-prediction with hull labels instead of label propagation for prediction | Greedy learner · Two moons, Iris, grid, hypercube accuracy | accuracy over 20 queries: all labels identified within 6 queries | Improved |
| Use S2 instead of plain active label propagation or random sampling | Baseline active learners · 20x20 grid | cut vertices found per query | Improved |
| Label propagation for prediction on halfspace-labelled graphs | Active label propagation, random sampling, S2 · Grid and hypercube | prediction accuracy | Hurt |
| Remove found cut edges from the graph before propagation (S2) | Label propagation · Grid | prediction accuracy | Mixed |
| Use margin-free graph-convexity bound instead of margin-based Euclidean bound | Bound on 2 x k grid · 2 x k grid | query bound: log(2k) + (3k)dens(X) -> 2 + log(k + 1) | Improved |
| Replace minimum hull set with greedy-built hull set | Algorithm 1 · Practical variants | query bound | Mixed |
| Check convexity of ground-truth communities in DBLP | SNAP community datasets · DBLP | fraction convex communities: 4308/5000 | Improved |
| Check convexity of ground-truth communities in Orkut and Eu-core | SNAP community datasets · Orkut, LiveJournal, Eu-core | fraction convex communities: 363/5000 | Hurt |
| Probabilistic random-sample start instead of hull set when balance beta is known | Algorithm 1 first step · Theory | query bound | No clear effect |
Closest papers by meaning
- Active Learning of General Halfspaces: Label Queries vs Membership Queries (NeurIPS 2024 · similarity 0.89)
- The Query Complexity of Local Search in Rounds on General Graphs (NeurIPS 2026 · similarity 0.88)
- Algorithms and Hardness for Active Learning on Graphs (ICML 2025 · similarity 0.86)
- On the Rademacher Complexity of Graph Neural Networks: Unifying Expressivity and Geometry (NeurIPS 2026 · similarity 0.86)
- Robust Offline Active Learning on Graphs (NeurIPS 2024 · similarity 0.85)
- Active Classification with Few Queries under Misspecification (NeurIPS 2024 · similarity 0.84)
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.
