Expander flows, geometric embeddings and graph partitioning

By Sanjeev Arora, S. Rao, Umesh V. Vazirani. JACM, 2009

383 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/892e4d061bee860096e151d80b349239b8b512c8

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Statistics and Probability

Citations in the corpus

Hierarchical Clustering (2017, neutral): “[2], this yields an O( √ logn)-approximation.”
The Multiplicative Weights Update Method: a Meta-Algorithm and Applications (2012, methodology): “The work of Arora, Rao and Vazirani [7] gave the ﬁrst O ( √ log n ) approximation algorithm to the S PARSEST C UT problem.”
Empirical comparison of algorithms for network community detection (2010, background): “Then, since the objective is typically NP-hard to optimize exactly [24, 4, 31], one employs heuristics [16, 20, 9] or approximation algorithms [25, 33, 2] to ﬁnd sets of nodes that approximately optimize the objective function and that can be understood or interpreted as “real” communities.”
On the Equivalence between Positional Node Embeddings and Structural Graph Representations (2019, background): “, 2016), implicit matrix factorization (Mikolov et al., 2013; Arora et al., 2009; Chen et al., 2012; Perozzi et al., 2014; Grover & Leskovec, 2016), Bayesian factor models (Mnih & Salakhutdinov, 2008; Gopalan et al.”
Large-Scale Community Detection on YouTube for Topic Discovery and Exploration (2011, neutral): “From the computational complexity perspective, finding optimum partitioning problems are NP-hard, and despite a lot of research in this area no constant-factor approximation algorithm is known for these problems (Leighton and Rao 1999; Arora, Rao, and Vazirani 2009; Feige, Peleg, and Kortsarz 2001).”
Provable Guarantees for Self-Supervised Deep Learning with Spectral Contrastive Loss (2021, background): “Previous works on graph partitioning (Arora et al., 2009, Lee et al., 2014, Leighton and Rao, 1999) often analyze the rounding algorithms that conduct clustering based on the representations of unlabeled data and do not analyze the performance of linear probe (which has access to labeled data).”
Streaming graph partitioning for large distributed graphs (2012, methodology): “This connection has inspired many spectral solutions to the problem, including the Arora-Rao-Vazirani algorithm [11] and the many works that followed.”
FENNEL: streaming graph partitioning for massive scale graphs (2014, background): “Speciﬁcally, in the traditional balanced graph partitioning problem, the goal is to minimize the number of edges cut subject to hard constraints on the number of vertices in a cluster [8, 38].”
Can ISPS and P2P users cooperate for improved performance? (2007, background): “The best known algo rithm can only guarantee an approximation ratio of O( √ logn) [29].”