A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering

Vincent Cohen-Addad, Tommaso D’Orsi, Aida Mousavifar
Proceedings of the 41st International Conference on Machine Learning, PMLR 235:9208-9229, 2024.

Abstract

We consider the semi-random graph model of [Makarychev, Makarychev and Vijayaraghavan, STOC’12], where, given a random bipartite graph with α edges and an unknown bipartition (A,B) of the vertex set, an adversary can add arbitrary edges inside each community and remove arbitrary edges from the cut (A,B) (i.e. all adversarial changes are monotone with respect to the bipartition). For this model, a polynomial time algorithm [MMV’12] is known to approximate the Balanced Cut problem up to value O(α) as long as the cut (A,B) has size Ω(α). However, it consists of slow subroutines requiring optimal solutions for logarithmically many semidefinite programs. We study the fine-grained complexity of the problem and present the first near-linear time algorithm that achieves similar performances to that of [MMV’12]. Our algorithm runs in time O(|V(G)|1+o(1)+|E(G)|1+o(1)) and finds a balanced cut of value O(α). Our approach appears easily extendible to related problem, such as Sparsest Cut, and also yields an near-linear time O(1)-approximation to Dagupta’s objective function for hierarchical clustering [Dasgupta, STOC’16] for the semi-random hierarchical stochastic block model inputs of [Cohen-Addad, Kanade, Mallmann-Trenn, Mathieu, JACM’19].

Cite this Paper

BibTeX
@InProceedings{pmlr-v235-cohen-addad24c, title = {A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering}, author = {Cohen-Addad, Vincent and D'Orsi, Tommaso and Mousavifar, Aida}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, pages = {9208--9229}, 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/cohen-addad24c/cohen-addad24c.pdf}, url = {https://proceedings.mlr.press/v235/cohen-addad24c.html}, abstract = {We consider the semi-random graph model of [Makarychev, Makarychev and Vijayaraghavan, STOC’12], where, given a random bipartite graph with $\alpha$ edges and an unknown bipartition $(A, B)$ of the vertex set, an adversary can add arbitrary edges inside each community and remove arbitrary edges from the cut $(A, B)$ (i.e. all adversarial changes are monotone with respect to the bipartition). For this model, a polynomial time algorithm [MMV’12] is known to approximate the Balanced Cut problem up to value $O(\alpha)$ as long as the cut $(A, B)$ has size $\Omega(\alpha)$. However, it consists of slow subroutines requiring optimal solutions for logarithmically many semidefinite programs. We study the fine-grained complexity of the problem and present the first near-linear time algorithm that achieves similar performances to that of [MMV’12]. Our algorithm runs in time $O(|V(G)|^{1+o(1)} + |E(G)|^{1+o(1)})$ and finds a balanced cut of value $O(\alpha).$ Our approach appears easily extendible to related problem, such as Sparsest Cut, and also yields an near-linear time $O(1)$-approximation to Dagupta’s objective function for hierarchical clustering [Dasgupta, STOC’16] for the semi-random hierarchical stochastic block model inputs of [Cohen-Addad, Kanade, Mallmann-Trenn, Mathieu, JACM’19].} }
Endnote
%0 Conference Paper %T A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering %A Vincent Cohen-Addad %A Tommaso D’Orsi %A Aida Mousavifar %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-cohen-addad24c %I PMLR %P 9208--9229 %U https://proceedings.mlr.press/v235/cohen-addad24c.html %V 235 %X We consider the semi-random graph model of [Makarychev, Makarychev and Vijayaraghavan, STOC’12], where, given a random bipartite graph with $\alpha$ edges and an unknown bipartition $(A, B)$ of the vertex set, an adversary can add arbitrary edges inside each community and remove arbitrary edges from the cut $(A, B)$ (i.e. all adversarial changes are monotone with respect to the bipartition). For this model, a polynomial time algorithm [MMV’12] is known to approximate the Balanced Cut problem up to value $O(\alpha)$ as long as the cut $(A, B)$ has size $\Omega(\alpha)$. However, it consists of slow subroutines requiring optimal solutions for logarithmically many semidefinite programs. We study the fine-grained complexity of the problem and present the first near-linear time algorithm that achieves similar performances to that of [MMV’12]. Our algorithm runs in time $O(|V(G)|^{1+o(1)} + |E(G)|^{1+o(1)})$ and finds a balanced cut of value $O(\alpha).$ Our approach appears easily extendible to related problem, such as Sparsest Cut, and also yields an near-linear time $O(1)$-approximation to Dagupta’s objective function for hierarchical clustering [Dasgupta, STOC’16] for the semi-random hierarchical stochastic block model inputs of [Cohen-Addad, Kanade, Mallmann-Trenn, Mathieu, JACM’19].
APA
Cohen-Addad, V., D’Orsi, T. & Mousavifar, A.. (2024). A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering. Proceedings of the 41st International Conference on Machine Learning, in Proceedings of Machine Learning Research 235:9208-9229 Available from https://proceedings.mlr.press/v235/cohen-addad24c.html.

Related Material