Graph Expansion in the New Millennium: Advances and Insights

What have we learnt about graph expansion in the new millenium? Sanjeev Arora Princeton University & Center for Computational Intractability

Overview Last millenium: Central role of expansion and expanders Recognizing expander graphs via eigenvalues (Cheeger71,Alon-Milman85) O(log n)-approximation via flows (Leighton-Rao88); region-growing technique; Close connection to metric embeddings; O(log n) approximation for general sparsest cut via Bourgain s Embedding Theorem (Linial-London-Rabinovich, Aumann-Rabani) This millenium (so far): O( log n )-approximation (A., Rao, Vazirani 04) via both SDP and flows; Better metric embeddings; O( log n )-approximation for general sparsest cut (Chawla-Gupta-Raecke05, A.-Lee-Naor06) Inapproximability results via Unique Games Conjecture (CKKRS06; KV06) Lowerbounds for metric embeddings (inspired by PCPs) [KV06; others]; lowerbounds for SDPs; Progress in relating full eigenvalue spectrum to (small-set) expansion (A., Barak, Steurer10) (Will not talk about: New understanding of expansion in Cayley graphs of groups, new algebra-free constructions of optimal expanders, etc.)

Graph Expansion Important concept: derandomization, network routing, coding theory, Markov chains, differential geometry, group theory d-regular graph G d vertex set S expansion(S) = # edges leaving S d |S| -expander: expansion(S) for all S (co-NP-hard to recognize) 2/2 2 [Cheeger, Alon 85, Alon-Milman85]. = smallest nonzero eigenvalue of Laplacian of G. (often will restrict attention wlog to balanced sets: |S|, |Sc| > (n)) Allows us to recognize graphs with = (1) ( expander )

Approximating expansion via flows [Leighton-Rao 88] O(log n)-approximation. Find largest s.t. we can simultaneously route nunits of flow between every vertex pair. ( embed a complete graph ) b /2 a O(logn)b

Why /2 : Total flow out of each subset S is n |S| (n - |S|) |S|/2 n units of flow bet. each vtx pair Why O(log n) : The LP expressing existence of flow is feasible if graph diameter is O(1/ ). (uses duality theorem) In a graph with expansion , diameter is O(log n/ ). (Region growing argument: BFS from S one step at a time; # of edges increases by (1+ ) factor each step; reach >1/2 the edges in O(log n/ ) steps.)

Approximating expansion via expander flows (A.,Rao, Vazirani 2004) units of flow originating at each vtx Route a flow with some demand graph W= (wij) (wij = flow between i and j) s.t. W is -regular and has expansion 0.01 ( expander flow ) Maximise . Easy: 0.01 (Amount of flow leaving each set S is at least 0.01 |S|.) Main claim: O( log n) Next: Geometry of cuts and how efficiently they can be crossed

Geometry of cuts Cut semimetric 1 dS(i,j) = 1 if i, j on opposite sides of the cut, = 0 else. (gives embedding into a line) 0 Convex combination of cut semimetrics d(i, j) = S S dS(i, j) (Gives embedding into l1 : i vi |vi vj|1= fraction of cuts i, j are across)

Approximating expansion via flows (A.,Rao, Vazirani 2004) units of flow originating at each vtx LP formulation: Route a flow with demand graph W= (wij) (wij = flow between i and j) W is -regular and has expansion 0.01 Check by computing eigenvalue ( separation oracle ) Maximise . Main claim: O( log n) Duality Thm Feasibility follows if for every distribution ( S) on balanced cuts, there are (n) disjoint vertex pairs (i1, j1), (i2, j2), s.t. (a) d(ir, jr) = O( log n/ ) (b) ir, jr are across (1) fraction of cuts. 1st structure theorem Open: Replace log n with o( log n )? (Best lowerbound: log log n [DKSV06])

[ARV04] If G is an -expander then for every distribution (S) on balanced cuts, there are (n) disjoint vertex pairs (i1, j1), (i2, j2), s.t. (a) d(ir, jr) = O( log n/ ) (b) ir, jr are across (1) fraction of cuts. Thoughts on Structure Thm sink Warmup: If max degree= O(1) and given a single balanced cut, above is true with O(1/ ) instead of O( log n/ ) 1 1 Pf: Max-Flow Min Cut Thm 4/ 1 -expansion Min Cut = (|S|) = (n) =Max-Flow 1 (all other edges capacity 4/ ) source Total capacity = O(n/ ) Flow decomposition (n) flowpaths of length O(1/ ) with one endpoint in S and one in Sc

A flow-based O(log n)-approximation algorithm for expansion For = 1/n, 2/n, 4/n, do Try to solve above LP to route a -regular expander flow in G If succeed, have verified that expansion 0.01 If fail, use [ARV] technique to find a cut of expansion < O( log n) (note: before finding this cut had already verified expansion 0.01 /2) (Note: Can be implemented in O(n1.5) time using matrix multiplicative weight method [Sh09,AK07,AHK05]. Satyen Kale s talk.)

Suggested research directions Nothing special about routing an expander flow; could use any graph family whose expansion can be verified up to O(1) factor. (Suffices to solve LP.) Example: Graphs with a few small nonzero eigenvalues (generalizes expanders, which have no small eigenvalues) [A., Barak, Steurer 10] Could also try for o( log n) approximation in subexponential time. See David Steurer stalk .

View 2: Use of math programming relaxations Linear Semidefinite Integer program for c-balanced separator (expansion of sets of size cn) Recall: [LR88]; O(log n)-approximation Cut semimetric dS(i,j) = 1 if i, j on opposite sides of the cut, = 0 else. [ARV04]: O( log n) approximation. (Main obstacle: understanding vectors satisfying triangle inequality condition).

How to round the SDP: 2nd Structure Theorem v1, v2, v3, : unit vectors in Rn, s.t. avg |vi vj|2 = (1) ( well-spread ) |vi vj|2 + |vj-vk|2 |vi vk|2 (l22 property; angle subtended by any two points on the third is nonobtuse; includes l1 as subcase) THM: For = (1/ log n) there exist sets S, T of size (n) s.t. |vi vj|2 for all i in S, j in T (S, T are -separated) NB: Implies weak version of 1st Structure Thm: Maxflow Mincut applied to S, T yields (n) paths of length O(1/ ) that cross (1/ log n) fraction of cuts.

Rounding the SDP S, T: -separated sets of size (n) Do BFS wrt distance function d(i,j) = |vi vj|2 , starting from S and going until you hit T Output the level of the BFS tree with least expansion. Claim: This gives a balanced cut (O, Oc) s.t. |E(O, Oc)| SDPOPT / = O( log n) SDPOPT d(S, i) d(S, j) Edge (i,j) contributes to cut for |vi vj|2 levels, and each level cuts at least |E(O, Oc)| edges. S vj vi d(S, j) d(S, i) |vi vj|2

O(log n)-approximation for other cut-like problems MIN-2-CNF deletion and several graph deletion problems. [Agarwal, Charikar, Makarychev, Makarychev04] [ 04]. Weighted version of S MIN-LINEAR ARRANGEMENT [Charikar, Karloff, Rao 05] General SPARSEST CUT [Chawla-Gupta-Raecke05, A. Lee Naor 06] 0 Min-ratioVERTEX SEPARATORS and Balanced VERTEX SEPARATORS[Feige, Hajiaghayi, Lee 04] All Method: SDP rounding using a generalized structure theorem

Suggested future direction SDP with triangle inequality corresponds to level 2 of Lasserre, Lovasz-Schrijver, etc. (see Madhur Tulsiani s talk) Use more powerful SDP relaxations from higher levels? * May need to allow superpolynomial time (rth level nr time) * Not currently ruled out under UGC.

Cut problems and embeddings General Sparsest Cut: Cost matrix (cij) cij 0; Demand matrix (dij) dij 0; Find SDP relaxation: [LLR94,AR94]: Integrality gap = Minimum distortion incurred when embedding l22 metrics into l1 (= convex combination of cut semi-metrics)

Geometric Embeddings of Metric Spaces Geometric space, eg l1 Finite metric space (X, d) f f(x) x y d(x,y) f(y) Distortion of f : Minimum C s.t. d(x, y) |f(x) f(y)| C d(x,y) [Bourgain 85, LLR94]: Distortion O(log n) into l1, l2 What if X is itself geometric? [Chawla-Gupta-Raecke05, A.-Lee-Naor06]: Distortion O( log n log log n) for embedding l22 into l1; and embedding l1 into l2

Embedding theorems in one slide Tool 1: Padded decompositions [Krauthgamer,Lee, Mendel,Naor04] Scale S, padding parameter p: Metric space (X, d) Partition probabilistically into pieces of diameter S, s.t. for all x Pr[x s partition contains Ball(x, S/p)] x Line embedding Map each block to 0 with probability ; Map x to d(x, zero-block) 0 Tool 2: Use ARV structure theorem to produce padded decompositions at different scales; combine line embeddings into a single embedding using measured descent.

Proving lowerbounds on distortion [Khot-Vishnoi05] log log n lowerbound; construction inspired by PCPs (hypercontractivity of noisy hypercubes) [Lee-Naor],[Cheeger,Kleiner,Naor] (log n) lowerbound; construction based upon Heisenberg group; new notion of differentiation [Lee-Muharrami] log n lowerbound; only for embedding weak l22 spaces into l1. Elementary construction and analysis. Open: log n lowerbound for l22 spaces; (log n) lowerbound for SDP integrality gap of uniform sparsest cut (ie edge expansion).

Proof of Structure Theorems Recall: v1, v2, v3, : unit vectors in Rd, s.t. avg |vi vj|2 = (1) ( well-spread ) |vi vj|2 + |vj-vk|2 |vi vk|2 For = (1/ log n) there exist sets S, T of size (n) s.t. |vi vj|2 for all i in S, j in T (S, T are -separated) (Recall: 1st Structure Theorem concerned distributions of cuts, which correspond to l1 metrics, which are a subcase of l22)

Algorithm to produce two -separated sets (= 1/log n) 0.01/ d Easy: Su and Tu are likely to have size (n). Tu Delete any vi in Su and vj in Tu s.t. |vi vj|2 < (repeat until no such pair remains) Su u If Su and Tu still have size (n) output them. Main difficulty: Show that whp only o(n) points get deleted. Obs: Deleted pairs were stretched , i.e., |vi vj|2 < , |<vi vj, u>| > 0.01/ d Fact: Pr[|<vi vj, u>| > 0.01 / d] = exp(-1/ ) = exp(- log n). Too large for union bound

Walks in l22 space |vi vj|2 + |vj-vk|2 |vi vk|2 r steps of squared-length only take you a total squared distance r (i.e., distance r ) Main proof step: Use measure concentration to prove that for most directions u there is a walk of length r on stretched edges (v1, v2), (v2, v3),.. (vr, vr+1) so that |<v1 vr+1, u>| > 0.001 r/ d Pr[such v1 , vr+1 exist in the point set] < exp(- r/ ) < 1/n2

Unique Games Conjecture [Khot03] Given m equations in n variables x1, x2, , xn of the type axi + b Xj = a (mod 113) s.t. (1- ) fraction are simultaneously satisfiable, it is NP-hard to satisfy of them simultaneously. Used to prove best inapproximability results for host of problems, including expansion problems. Inspired SDP integrality gaps (aka embedding lowerbounds). (See Khot s talk) (Expansion strikes back) The Achilles heel of UGC appears to be expansion. Better understanding of small-set expansion may disprove UGC. (see Steurer s talk)

Looking forward to more insight in the next decade! Thank you!