AI Paper Atlas

Research map / Learning theory and algorithms / Sample complexity

Active Learning of Convex Halfspaces on Graphs

Maximilian Thiessen, Thomas Gärtner

NeurIPS 2021 · Learning theory and algorithms › Sample complexity · approach: Computational thresholds in graphs and structure

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 changedWhereMeasuredEffect
Use convex hulls and extensions to deduce labels after each query (Theorem 5) instead of binary search per shortest-path coverActive halfspace learning on graphs · Query complexity boundupper 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 samplingHalfspace learner · Two moons, Iris, grid, hypercube cut-vertex discoveryqueries to find all cut vertices: at most 6 queriesImproved
Selective sampling instead of greedy selection (ablation)Halfspace learner · Two moons, Iris, grid, hypercubequeries to deduce all labels: 2-8 queries moreHurt
Halfspace-prediction with hull labels instead of label propagation for predictionGreedy learner · Two moons, Iris, grid, hypercube accuracyaccuracy over 20 queries: all labels identified within 6 queriesImproved
Use S2 instead of plain active label propagation or random samplingBaseline active learners · 20x20 gridcut vertices found per queryImproved
Label propagation for prediction on halfspace-labelled graphsActive label propagation, random sampling, S2 · Grid and hypercubeprediction accuracyHurt
Remove found cut edges from the graph before propagation (S2)Label propagation · Gridprediction accuracyMixed
Use margin-free graph-convexity bound instead of margin-based Euclidean boundBound on 2 x k grid · 2 x k gridquery bound: log(2k) + (3k)dens(X) -> 2 + log(k + 1)Improved
Replace minimum hull set with greedy-built hull setAlgorithm 1 · Practical variantsquery boundMixed
Check convexity of ground-truth communities in DBLPSNAP community datasets · DBLPfraction convex communities: 4308/5000Improved
Check convexity of ground-truth communities in Orkut and Eu-coreSNAP community datasets · Orkut, LiveJournal, Eu-corefraction convex communities: 363/5000Hurt
Probabilistic random-sample start instead of hull set when balance beta is knownAlgorithm 1 first step · Theoryquery boundNo clear effect

Closest papers by meaning

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.

Open scime draft

Get the next scime Dispatch and a monthly field update

Free. We send a confirmation link first; every email has a one-click unsubscribe. Privacy