Approximations for the isoperimetric and spectral profile of graphs and related parameters

with Prasad Raghavendra, Prasad Tetali. STOC 2010.

PDF

abstract

The spectral profile of a graph is a natural generalization of the classical notion of its Rayleigh quotient. Roughly speaking, given a graph GG, for each 0<δ<10< \delta < 1, the spectral profile ΛG(δ)\Lambda_G(\delta) minimizes the Rayleigh quotient (from the variational characterization) of the spectral gap of the Laplacian matrix of GG over vectors with support at most δ\delta over a suitable probability measure. Formally, the spectral profile ΛG\Lambda_G of a graph GG is a function ΛG:[0,12]R\Lambda_G : [0,\frac{1}{2}] \rightarrow \R defined as: ΛG(δ):=minxRV, d(supp(x))δijgij(xixj)2idixi2. \Lambda_G(\delta) :=\min_{x\in \R^V,~d(\mathrm{supp}(x))\le \delta} \frac{\sum_{ij} g_{ij} (x_i-x_j)^2}{\sum_i d_i x_i^2} \,. where gijg_{ij} is the weight of the edge (i,j)(i,j) in the graph, did_i is the degree of vertex ii, and d(supp(x))d(\mathrm{supp}(x)) is the fraction of edges incident on vertices within the support of vector xx.

While the notion of the spectral profile has numerous applications in Markov chain, it is also is closely tied to its isoperimetric profile of a graph. Specifically, the spectral profile is a relaxation for the problem of approximating edge expansion of small sets in graphs.

In this work, we obtain an efficient algorithm that yields a log(1/δ)\log(1/\delta)-factor approximation for the value of ΛG(δ)\Lambda_G(\delta). By virtue of its connection to edge-expansion, we also obtain an algorithm for the problem of approximating edge expansion of small linear sized sets in a graph.

This problem was recently shown to be intimately connected to the Unique Games Conjecture [Raghavendra-Steurer'10].

Finally, we extend the techniques to obtain approximation algorithms with similar guarantees for restricted eigenvalue problems on diagonally dominant matrices.

keywords

  • small-set expansion
  • approximation algorithms
  • semidefinite programming