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

• URL: http://arxiv.org/abs/2406.04857v1
• Date: Fri, 7 Jun 2024 11:40:54 GMT
• Title: A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering
• Authors: Vincent Cohen-Addad, Tommaso d'Orsi, Aida Mousavifar,
• Abstract summary: We consider the semi-random graph model of [Makarychev, Makarychev and Vijayaraghavan, STOC'12]. A time algorithm is known to approximate the Balanced Cut problem up to value $O(alpha)$ [MMV'12] as long as the cut $(A, B)$ has size $Omega(alpha)$. We study the fine-grained complexity of the problem and present the first near-linear time subroutine that achieves similar performances to that of [MMV'12].
• Score: 18.29151197560866
• License: http://creativecommons.org/licenses/by/4.0/
• 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 \textit{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(\alpha)$ [MMV'12] 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].

Related papers

• A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
  We present a scalable algorithm for the individually fair ($p$, $k$)-clustering problem introduced by Jung et al. and Mahabadi et al. A clustering is then called individually fair if it has centers within distance $delta(x)$ of $x$ for each $xin P$. We show empirically that not only is our algorithm much faster than prior work, but it also produces lower-cost solutions.
  arXiv  Detail & Related papers  (2024-02-09T19:01:48Z)
• An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue Optimization Problems [76.2042837251496]
  We introduce two oblivious mirror descent algorithms based on a complementary composite setting. Remarkably, both algorithms work without prior knowledge of the Lipschitz constant or smoothness of the objective function. We show how to extend our framework to scale and demonstrate the efficiency and robustness of our methods on large scale semidefinite programs.
  arXiv  Detail & Related papers  (2023-06-30T08:34:29Z)
• Sparse PCA Beyond Covariance Thresholding [2.311583680973075]
  We show that for every $t ll k$ there exists an algorithm running in time $ncdot dO(t)$ that solves this problem as long as [ gtrsim fracksqrtntsqrtln(2 + td/k2)$. We provide time algorithms for the sparse planted vector problem that have better guarantees than the state of the art in some regimes.
  arXiv  Detail & Related papers  (2023-02-20T18:45:24Z)
• Private estimation algorithms for stochastic block models and mixture models [63.07482515700984]
  General tools for designing efficient private estimation algorithms. First efficient $(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery.
  arXiv  Detail & Related papers  (2023-01-11T09:12:28Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  We give a sketching-based iterative algorithm that computes $1+varepsilon$ approximate solutions for the ridge regression problem. We also show that this algorithm can be used to give faster algorithms for kernel ridge regression.
  arXiv  Detail & Related papers  (2022-04-13T22:18:47Z)
• Finding the KT partition of a weighted graph in near-linear time [1.572727650614088]
  Kawarabayashi and Thorup gave a near-trivial time deterministic algorithm for minimum cut in a simple graph $G = (V,E)$. We give a near-linear time randomized algorithm to find the $(1+varepsilon)$-KT partition of a weighted graph.
  arXiv  Detail & Related papers  (2021-11-02T05:26:10Z)
• Sublinear Time and Space Algorithms for Correlation Clustering via Sparse-Dense Decompositions [9.29659220237395]
  We present a new approach for solving (minimum disagreement) correlation clustering. We obtain sublinear algorithms with highly efficient time and space complexity. The main ingredient of our approach is a novel connection to sparse-dense graph decompositions.
  arXiv  Detail & Related papers  (2021-09-29T16:25:02Z)
• Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
  We study the problem of list-decodable mean estimation, where an adversary can corrupt a majority of the dataset. We develop new algorithms for list-decodable mean estimation, achieving nearly-optimal statistical guarantees.
  arXiv  Detail & Related papers  (2021-06-16T03:34:14Z)
• Quantum complexity of minimum cut [0.2538209532048867]
  We characterize the quantum query and time complexity of the minimum cut problem in the adjacency matrix model. Our algorithm uses a quantum algorithm for graph sparsification by Apers and de Wolf (FOCS 2020) and results on the structure of near-minimum cuts by Kawarabayashi and Thorup (STOC 2015) and Rubinstein, Schramm and Weinberg (ITCS 2018)
  arXiv  Detail & Related papers  (2020-11-19T13:51:49Z)
• Streaming Complexity of SVMs [110.63976030971106]
  We study the space complexity of solving the bias-regularized SVM problem in the streaming model. We show that for both problems, for dimensions of $frac1lambdaepsilon$, one can obtain streaming algorithms with spacely smaller than $frac1lambdaepsilon$.
  arXiv  Detail & Related papers  (2020-07-07T17:10:00Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.