Edge-Colored Clustering in Hypergraphs: Beyond Minimizing Unsatisfied Edges

Alex Crane, Thomas Stanley, Blair D. Sullivan, Nate Veldt
Proceedings of the 42nd International Conference on Machine Learning, PMLR 267:11435-11464, 2025.

Abstract

We consider a framework for clustering edge-colored hypergraphs, where the goal is to cluster (equivalently, to color) objects based on the primary type of multiway interactions they participate in. One well-studied objective is to color nodes to minimize the number of unsatisfied hyperedges—those containing one or more nodes whose color does not match the hyperedge color. We motivate and present advances for several directions that extend beyond this minimization problem. We first provide new algorithms for maximizing satisfied edges, which is the same at optimality but is much more challenging to approximate, with all prior work restricted to graphs. We develop the first approximation algorithm for hypergraphs, and then refine it to improve the best-known approximation factor for graphs. We then introduce new objective functions that incorporate notions of balance and fairness, and provide new hardness results, approximations, and fixed-parameter tractability results.

Cite this Paper

BibTeX
@InProceedings{pmlr-v267-crane25a, title = {Edge-Colored Clustering in Hypergraphs: Beyond Minimizing Unsatisfied Edges}, author = {Crane, Alex and Stanley, Thomas and Sullivan, Blair D. and Veldt, Nate}, booktitle = {Proceedings of the 42nd International Conference on Machine Learning}, pages = {11435--11464}, year = {2025}, editor = {Singh, Aarti and Fazel, Maryam and Hsu, Daniel and Lacoste-Julien, Simon and Berkenkamp, Felix and Maharaj, Tegan and Wagstaff, Kiri and Zhu, Jerry}, volume = {267}, series = {Proceedings of Machine Learning Research}, month = {13--19 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v267/main/assets/crane25a/crane25a.pdf}, url = {https://proceedings.mlr.press/v267/crane25a.html}, abstract = {We consider a framework for clustering edge-colored hypergraphs, where the goal is to cluster (equivalently, to color) objects based on the primary type of multiway interactions they participate in. One well-studied objective is to color nodes to minimize the number of unsatisfied hyperedges—those containing one or more nodes whose color does not match the hyperedge color. We motivate and present advances for several directions that extend beyond this minimization problem. We first provide new algorithms for maximizing satisfied edges, which is the same at optimality but is much more challenging to approximate, with all prior work restricted to graphs. We develop the first approximation algorithm for hypergraphs, and then refine it to improve the best-known approximation factor for graphs. We then introduce new objective functions that incorporate notions of balance and fairness, and provide new hardness results, approximations, and fixed-parameter tractability results.} }
Endnote
%0 Conference Paper %T Edge-Colored Clustering in Hypergraphs: Beyond Minimizing Unsatisfied Edges %A Alex Crane %A Thomas Stanley %A Blair D. Sullivan %A Nate Veldt %B Proceedings of the 42nd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2025 %E Aarti Singh %E Maryam Fazel %E Daniel Hsu %E Simon Lacoste-Julien %E Felix Berkenkamp %E Tegan Maharaj %E Kiri Wagstaff %E Jerry Zhu %F pmlr-v267-crane25a %I PMLR %P 11435--11464 %U https://proceedings.mlr.press/v267/crane25a.html %V 267 %X We consider a framework for clustering edge-colored hypergraphs, where the goal is to cluster (equivalently, to color) objects based on the primary type of multiway interactions they participate in. One well-studied objective is to color nodes to minimize the number of unsatisfied hyperedges—those containing one or more nodes whose color does not match the hyperedge color. We motivate and present advances for several directions that extend beyond this minimization problem. We first provide new algorithms for maximizing satisfied edges, which is the same at optimality but is much more challenging to approximate, with all prior work restricted to graphs. We develop the first approximation algorithm for hypergraphs, and then refine it to improve the best-known approximation factor for graphs. We then introduce new objective functions that incorporate notions of balance and fairness, and provide new hardness results, approximations, and fixed-parameter tractability results.
APA
Crane, A., Stanley, T., Sullivan, B.D. & Veldt, N.. (2025). Edge-Colored Clustering in Hypergraphs: Beyond Minimizing Unsatisfied Edges. Proceedings of the 42nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 267:11435-11464 Available from https://proceedings.mlr.press/v267/crane25a.html.

Related Material