MSR Talk Series: Graph Multi-partitioning and Higher Order Cheeger Inequalities; Anand Louis – Georgia Tech

Cheeger’s fundamental inequality states that any edge-weighted graph has a vertex subsetS such that its expansion (a.k.a. conductance ofS or the sparsity of the cut(S,S ̅) ) is bounded as follows:

ϕ(S)=w(S,S ̅ )/(w(S))≤√(2λ2 ),

where w is the total edge weight of a subset or a cut andλ2 is the second smallest eigenvalue of the normalized Laplacian of the graph.

I will talk about some natural generalizations of the sparsest cut in a graph:

  1. A partition of the vertex set intok parts that minimizes the sparsity of the partition (defined as the ratio of the weight of edges between parts to the total weight of edges incident to the smallestk-1 parts);
  2. A partition of the vertex set intok partsS1,…,Sk that minimizemax i∈[k])ϕ(Si);
  3. A subset of sizeO(1/k) of the graph with minimum expansion.

I will present some extensions of Cheeger’s classical inequality to these problems via higher eigenvalues of the graph Laplacian and some approximation-algorithms for them. In particular, for the sparsestk-partition, we prove that the sparsity is at most8√(λk ) log k whereλk is the k-th smallest eigenvalue of the normalized Laplacian matrix. For the k sparse cuts problem we prove that there exist ck disjoint subsetsS1,…,S(1-ε)k, such that

maxiϕ(Si )≤C √λk logk

whereC0 are suitable absolute constants; this leads to a similar bound for the small-set expansion problem, namely for anyk, there is a subsetS whose weight is at most aO(1/k) fraction of the total weight andϕ(S)≤ C √λk logk. The latter two results are the best possible in terms of the eigenvalues up to constant factors. Our results are derived via simple and efficient algorithms, and can themselves be viewed as generalizations of Cheeger’s method.

Based on joint works with Prasad Raghavendra, Prasad Tetali and Santosh Vempala.

Series:
Microsoft Research Talks
Date:
Speakers:
Anand Louis

    • Portrait of Jeff Running

      Jeff Running

Series: Microsoft Research Talks