# Efficient Algorithms for Learning and Compressing Monophonic Halfspaces in Graphs

arXiv: https://arxiv.org/abs/2506.23186 · HTML: https://mlsanity.com/paper/2506.23186/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 78 references that are in the map.
- First posted on arXiv 29 Jun 2025.

## Builds on (most cited first, 18 of 18)

- [Proper Learning, Helly Number, and an Optimal SVM Bound](https://mlsanity.com/paper/2005.11818/) (2020)
- [Sample compression schemes for VC classes](https://mlsanity.com/paper/1503.06960/) (2015)
- [S2: An Efficient Graph Based Active Learning Algorithm with Application to Nonparametric Classification](https://mlsanity.com/paper/1506.08760/) (2015)
- [Unlabeled sample compression schemes and corner peelings for ample and maximum classes](https://mlsanity.com/paper/1812.02099/) (2018)
- [Labeled compression schemes for extremal classes](https://mlsanity.com/paper/1506.00165/) (2015)
- [Active Learning on Trees and Graphs](https://mlsanity.com/paper/1301.5112/) (2013)
- [Exact Recovery of Clusters in Finite Metric Spaces Using Oracle Queries](https://mlsanity.com/paper/2102.00504/) (2021)
- [Sample compression schemes for balls in graphs](https://mlsanity.com/paper/2206.13254/) (2022)
- [Labeled sample compression schemes for complexes of oriented matroids](https://mlsanity.com/paper/2110.15168/) (2021)
- [Non-Clashing Teaching Maps for Balls in Graphs](https://mlsanity.com/paper/2309.02876/) (2023)
- [Online Similarity Prediction of Networked Data from Known and Unknown Graphs](https://mlsanity.com/paper/1302.7263/) (2013)
- [Maximal Closed Set and Half-Space Separations in Finite Closure Systems](https://mlsanity.com/paper/2001.04417/) (2020)
- [Unlabelled Sample Compression Schemes for Intersection-Closed Classes and Extremal Classes](https://mlsanity.com/paper/2210.05455/) (2022)
- [Practical Computation of Graph VC-Dimension](https://mlsanity.com/paper/2405.07588/) (2024)
- [VC Set Systems in Minor-free (Di)Graphs and Applications](https://mlsanity.com/paper/2304.01790/) (2023)
- [Efficient Algorithms for Learning Monophonic Halfspaces in Graphs](https://mlsanity.com/paper/2405.00853/) (2024)
- [Convexity in scientific collaboration networks](https://mlsanity.com/paper/1811.11030/) (2018)
- [Half-space separation in monophonic convexity](https://mlsanity.com/paper/2404.17564/) (2024)

## Built on by (most cited first, 1 of 1)

- [Active Learning on Adversarially Corrupted Graphs](https://mlsanity.com/paper/2607.04869/) (2026)

## Abstract (arXiv)

Abstract notions of convexity over the vertices of a graph, and corresponding notions of halfspaces, have recently gained attention from the machine learning community. In this work we study monophonic halfspaces, a notion of graph halfspaces defined through closure under induced paths. Our main result is a 2-satisfiability based decomposition theorem, which allows one to represent monophonic halfspaces as a disjoint union of certain vertex subsets. Using this decomposition, we achieve efficient and (nearly) optimal algorithms for various learning problems, such as teaching, active, and online learning. Most notably, we obtain a polynomial-time algorithm for empirical risk minimization. Independently of the decomposition theorem, we obtain an efficient, stable, and proper sample compression scheme. This makes monophonic halfspaces efficiently learnable with proper learners and linear error rate 1/varepsilon in the realizable PAC setting. Our results answer open questions from the literature, and show a stark contrast with geodesic halfspaces, for which most of the said learning problems are NP-hard.