Efficient Algorithms for Learning Monophonic Halfspaces in Graphs

arXiv:2405.00853v1 Announce Type: new
Abstract: 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 …

abstract algorithms arxiv binary classifier classifiers cs.lg graph graphs sense stat.ml study type