# Efficient Algorithms for Learning Monophonic Halfspaces in Graphs

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 56 references that are in the map.
- First posted on arXiv 1 May 2024.

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

- [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)
- [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)
- [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)
- [VC Set Systems in Minor-free (Di)Graphs and Applications](https://mlsanity.com/paper/2304.01790/) (2023)
- [A Parameterized Theory of PAC Learning](https://mlsanity.com/paper/2304.14058/) (2023)
- [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)
- [First-order logic axiomatization of metric graph theory](https://mlsanity.com/paper/2203.01070/) (2022)

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

- [Efficient Algorithms for Learning and Compressing Monophonic Halfspaces in Graphs](https://mlsanity.com/paper/2506.23186/) (2025)
- [Self-Directed Learning of Convex Labelings on Graphs](https://mlsanity.com/paper/2409.01428/) (2024)
- [Active Learning on Adversarially Corrupted Graphs](https://mlsanity.com/paper/2607.04869/) (2026)

## Abstract (arXiv)

We study the problem of learning a binary classifier on the vertices of a graph. In particular, we consider classifiers given by monophonic halfspaces, partitions of the vertices that are convex in a certain abstract sense. Monophonic halfspaces, and related notions such as geodesic halfspaces,have recently attracted interest, and several connections have been drawn between their properties(e.g., their VC dimension) and the structure of the underlying graph G. We prove several novel results for learning monophonic halfspaces in the supervised, online, and active settings. Our main result is that a monophonic halfspace can be learned with near-optimal passive sample complexity in time polynomial in n = |V(G)|. This requires us to devise a polynomial-time algorithm for consistent hypothesis checking, based on several structural insights on monophonic halfspaces and on a reduction to 2-satisfiability. We prove similar results for the online and active settings. We also show that the concept class can be enumerated with delay operatornamepoly(n), and that empirical risk minimization can be performed in time 2ω(G)operatornamepoly(n) where ω(G) is the clique number of G. These results answer open questions from the literature (Gonz'alez et al., 2020), and show a contrast with geodesic halfspaces, for which some of the said problems are NP-hard (Seiffarth et al., 2023).