Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better

Vicente Balmaseda, Ying Xu, Yixin Cao, Nate Veldt
Proceedings of the 41st International Conference on Machine Learning, PMLR 235:2586-2606, 2024.

Abstract

Cluster deletion is an NP-hard graph clustering objective with applications in computational biology and social network analysis, where the goal is to delete a minimum number of edges to partition a graph into cliques. We first provide a tighter analysis of two previous approximation algorithms, improving their approximation guarantees from 4 to 3. Moreover, we show that both algorithms can be derandomized in a surprisingly simple way, by greedily taking a vertex of maximum degree in an auxiliary graph and forming a cluster around it. One of these algorithms relies on solving a linear program. Our final contribution is to design a new and purely combinatorial approach for doing so that is far more scalable in theory and practice.

Cite this Paper

BibTeX
@InProceedings{pmlr-v235-balmaseda24a, title = {Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better}, author = {Balmaseda, Vicente and Xu, Ying and Cao, Yixin and Veldt, Nate}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, pages = {2586--2606}, year = {2024}, editor = {Salakhutdinov, Ruslan and Kolter, Zico and Heller, Katherine and Weller, Adrian and Oliver, Nuria and Scarlett, Jonathan and Berkenkamp, Felix}, volume = {235}, series = {Proceedings of Machine Learning Research}, month = {21--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v235/main/assets/balmaseda24a/balmaseda24a.pdf}, url = {https://proceedings.mlr.press/v235/balmaseda24a.html}, abstract = {Cluster deletion is an NP-hard graph clustering objective with applications in computational biology and social network analysis, where the goal is to delete a minimum number of edges to partition a graph into cliques. We first provide a tighter analysis of two previous approximation algorithms, improving their approximation guarantees from 4 to 3. Moreover, we show that both algorithms can be derandomized in a surprisingly simple way, by greedily taking a vertex of maximum degree in an auxiliary graph and forming a cluster around it. One of these algorithms relies on solving a linear program. Our final contribution is to design a new and purely combinatorial approach for doing so that is far more scalable in theory and practice.} }
Endnote
%0 Conference Paper %T Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better %A Vicente Balmaseda %A Ying Xu %A Yixin Cao %A Nate Veldt %B Proceedings of the 41st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2024 %E Ruslan Salakhutdinov %E Zico Kolter %E Katherine Heller %E Adrian Weller %E Nuria Oliver %E Jonathan Scarlett %E Felix Berkenkamp %F pmlr-v235-balmaseda24a %I PMLR %P 2586--2606 %U https://proceedings.mlr.press/v235/balmaseda24a.html %V 235 %X Cluster deletion is an NP-hard graph clustering objective with applications in computational biology and social network analysis, where the goal is to delete a minimum number of edges to partition a graph into cliques. We first provide a tighter analysis of two previous approximation algorithms, improving their approximation guarantees from 4 to 3. Moreover, we show that both algorithms can be derandomized in a surprisingly simple way, by greedily taking a vertex of maximum degree in an auxiliary graph and forming a cluster around it. One of these algorithms relies on solving a linear program. Our final contribution is to design a new and purely combinatorial approach for doing so that is far more scalable in theory and practice.
APA
Balmaseda, V., Xu, Y., Cao, Y. & Veldt, N.. (2024). Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better. Proceedings of the 41st International Conference on Machine Learning, in Proceedings of Machine Learning Research 235:2586-2606 Available from https://proceedings.mlr.press/v235/balmaseda24a.html.

Related Material