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

We consider the semi-random graph model of (Makarychev et al., 2012) , 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(α) (Makarychev et al., 2012) 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 (Makarychev et al., 2012) . Our algorithm runs in time ) 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, 2016) for the semi-random hierarchical stochastic block model inputs of (Cohen-Addad et al., 2019) . * Equal contribution 1 Google Research 2 BIDSA, Bocconi. Fast Algorithm for Beyond-Worst-Case Graph Clustering 1 These are often times referred to as monotone perturbations. Such perturbations may have surprising effects on the statistical and computational aspects of the problem. For instance see (Moitra et al., 2016; Liu & Moitra, 2022) . 2 We remark this model is significantly more general than the stochastic block model, see Section 1.2 3 We point out that the algorithm requires an actual feasible solution with nearly optimal objective value and not a rounded solution. 4 We write o(1) to denote real-valued functions tending to zero as n grows.