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

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 is known to approximate the Balanced Cut problem up to value O(α) [MMV'12] 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)|¹⁺ᵒ⁽¹⁾ + |E(G)|¹⁺ᵒ⁽¹⁾) 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].