Efficient Algorithms for Learning Monophonic Halfspaces in Graphs

Marco Bressan, Emmanuel Esposito, Maximilian Thiessen
Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:669-696, 2024.

Abstract

We study the problem of learning a binary classifier on the vertices of a graph. In particular, we consider classifiers given by \emph{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 $\mathrm{poly}(n)$, and that empirical risk minimization can be performed in time $2^{\omega(G)}\mathrm{poly}(n)$ where $\omega(G)$ is the clique number of $G$. These results answer open questions from the literature (González et al. 2020), and show a contrast with geodesic halfspaces, for which some of the said problems are NP-hard (Seiffarth et al., 2023).

Cite this Paper

BibTeX
@InProceedings{pmlr-v247-bressan24b, title = {Efficient Algorithms for Learning Monophonic Halfspaces in Graphs}, author = {Bressan, Marco and Esposito, Emmanuel and Thiessen, Maximilian}, booktitle = {Proceedings of Thirty Seventh Conference on Learning Theory}, pages = {669--696}, year = {2024}, editor = {Agrawal, Shipra and Roth, Aaron}, volume = {247}, series = {Proceedings of Machine Learning Research}, month = {30 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v247/bressan24b/bressan24b.pdf}, url = {https://proceedings.mlr.press/v247/bressan24b.html}, abstract = {We study the problem of learning a binary classifier on the vertices of a graph. In particular, we consider classifiers given by \emph{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 $\mathrm{poly}(n)$, and that empirical risk minimization can be performed in time $2^{\omega(G)}\mathrm{poly}(n)$ where $\omega(G)$ is the clique number of $G$. These results answer open questions from the literature (González et al. 2020), and show a contrast with geodesic halfspaces, for which some of the said problems are NP-hard (Seiffarth et al., 2023).} }
Endnote
%0 Conference Paper %T Efficient Algorithms for Learning Monophonic Halfspaces in Graphs %A Marco Bressan %A Emmanuel Esposito %A Maximilian Thiessen %B Proceedings of Thirty Seventh Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2024 %E Shipra Agrawal %E Aaron Roth %F pmlr-v247-bressan24b %I PMLR %P 669--696 %U https://proceedings.mlr.press/v247/bressan24b.html %V 247 %X We study the problem of learning a binary classifier on the vertices of a graph. In particular, we consider classifiers given by \emph{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 $\mathrm{poly}(n)$, and that empirical risk minimization can be performed in time $2^{\omega(G)}\mathrm{poly}(n)$ where $\omega(G)$ is the clique number of $G$. These results answer open questions from the literature (González et al. 2020), and show a contrast with geodesic halfspaces, for which some of the said problems are NP-hard (Seiffarth et al., 2023).
APA
Bressan, M., Esposito, E. & Thiessen, M.. (2024). Efficient Algorithms for Learning Monophonic Halfspaces in Graphs. Proceedings of Thirty Seventh Conference on Learning Theory, in Proceedings of Machine Learning Research 247:669-696 Available from https://proceedings.mlr.press/v247/bressan24b.html.

Related Material