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 $G$, for each $0< \delta < 1$, the spectral profile $\Lambda_G(\delta)$ minimizes the Rayleigh quotient (from the variational characterization) of the spectral gap of the Laplacian matrix of $G$ over vectors with support at most $\delta$ over a suitable probability measure. Formally, the spectral profile $\Lambda_G$ of a graph $G$ is a function $\Lambda_G : [0,\frac{1}{2}] \rightarrow \R$ defined as: $$\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 $g_{ij}$ is the weight of the edge $(i,j)$ in the graph, $d_i$ is the degree of vertex $i$, and $d(\mathrm{supp}(x))$ is the fraction of edges incident on vertices within the support of vector $x$.

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/\delta)$-factor approximation for the value of $\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