Learning to Partition using Score Based Compatibilities
This work addresses the challenge of forming optimal groups based on user compatibilities, which is incremental as it builds on existing concepts like homophilous and heterophilous partitions from psychology.
The paper tackles the problem of learning to partition users into groups by learning compatibilities between them, showing that without structure the problems are NP-hard and providing approximation or inapproximability results, while introducing an intrinsic scores structure that makes many problems polynomial-time solvable and proposing an online algorithm with low sample complexity for learning optimal partitions.
We study the problem of learning to partition users into groups, where one must learn the compatibilities between the users to achieve optimal groupings. We define four natural objectives that optimize for average and worst case compatibilities and propose new algorithms for adaptively learning optimal groupings. When we do not impose any structure on the compatibilities, we show that the group formation objectives considered are $NP$ hard to solve and we either give approximation guarantees or prove inapproximability results. We then introduce an elegant structure, namely that of \textit{intrinsic scores}, that makes many of these problems polynomial time solvable. We explicitly characterize the optimal groupings under this structure and show that the optimal solutions are related to \emph{homophilous} and \emph{heterophilous} partitions, well-studied in the psychology literature. For one of the four objectives, we show $NP$ hardness under the score structure and give a $\frac{1}{2}$ approximation algorithm for which no constant approximation was known thus far. Finally, under the score structure, we propose an online low sample complexity PAC algorithm for learning the optimal partition. We demonstrate the efficacy of the proposed algorithm on synthetic and real world datasets.