Expander flows, geometric embeddings and graph partitioning

By Sanjeev Arora, Satish Rao, Umesh V. Vazirani. Symposium on the Theory of Computing, 2004

674 citations recorded by the source corpus.

We give a O(√log n)-approximation algorithm for sparsest cut, balanced separator, and graph conductance problems. This improves the O(log n)-approximation of Leighton and Rao (1988). We use a well-known semidefinite relaxation with triangle inequality constraints. Central to our analysis is a geometric theorem about projections of point sets in Rd, whose proof makes essential use of a phenomenon called measure concentration. We also describe an interesting and natural "certificate" for a graph's expansion, by embedding an n-node expander in it with appropriate dilation and congestion. We call this an expander flow.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/be38c30285bf48c127f87d9c83ea8516af02958e

How researchers see this paper

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

In Artificial Intelligence

In Computational Theory and Mathematics

In Statistics and Probability

Citations in the corpus

SoK: The Evolution of Sybil Defense via Social Networks (2013, background): “Several sophisticated algorithms offer non trivial guarantees on the quality of their approximation to the problem [4], [14], [31], but they have two serious drawbacks when it comes to large social graphs: they are not obviously parallelizable and their running time is polynomial in the size of the ”
Can ISPS and P2P users cooperate for improved performance? (2007, methodology): “The graph H can be characterized using several metrics.”
The Design of Approximation Algorithms (2011, methodology): “4 is a breakthrough due to Arora, Rao, and Vazirani [22]; the discussion in this section follows an improved analysis due to Lee [212].”
The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into 1 (Extended Abstract) (2005, background): “A breakthrough result of Arora, Rao and Vazirani (ARV) [ 5 ] gave an O( √ log n) ap-”
Consistency of spectral clustering (2008, background): “Even good approximations are difficult to obtain and are sometimes known to be NP-hard as well (see Arora et al. (2004) for some recent work on complexity of approximations).”
A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning (2008, background): “Arora, Rao and Vazirani [ ARV04 ] improved this to O( √ log n) through semi-definite”
Graph expansion and the unique games conjecture (2010, methodology): “[5] obtained an O( √ logn) approximation for the problem using semidefinite programming techniques.”
Energy Models for Graph Clustering (2007, positive): “The problem of nding the bipartition of a given graph with minimum node-normalized cut is NP-hard for edge-weighted graphs [38], but approximable within factor O( p log(jVj)) in deterministic polynomial time [ 3 ].”
A combinatorial, primal-dual approach to semidefinite programs (2007, methodology): “This lemma can be proved using the techniques of [8, 21]:”
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.”
Comparison of Metric Spectral Gaps (2013, background): “It follows from [3] (using in part ideas of [4, 19, 61, 81]) that if (X, dX) is a metric space that admits a quasisymmetric embedding into Hilbert space then there exist ε, δ ∈ (0, 1) (depending only on the modulus of quasisymmetry of the implicit embedding) such that for every n ∈ N, any n-point su”
Structure preserving embedding (2009, methodology): “For example, using hyperplanes to separate points after graph embedding is useful for e.ciently approximating the NPhard sparsest cut problem (Arora et al., 2004).”
Improved approximation algorithms for minimum-weight vertex separators (2005, methodology): “In preparation for applying the techniques of [ 7 ], the relaxation includes so-called \triangle inequality" constraints on the variables.”
The little engine(s) that could: scaling online social networks (2010, background): “Graph Partitioning: There exist several offline algorithms for partitioning a graph into a fixed number of equal sized partitions in such a way that the number of inter-partition edges are minimized [10, 19].”