  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
$\operatorname{poly}(n)$, and that empirical risk minimization can be performed
in time $2^{\omega(G)}\operatorname{poly}(n)$ where $\omega(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).
