Approximations for the isoperimetric and spectral profile of graphs and related parameters
with Prasad Raghavendra, Prasad Tetali. STOC 2010.
The spectral profile of a graph is a natural generalization of the classical notion of its Rayleigh quotient. Roughly speaking, given a graph , for each , the spectral profile minimizes the Rayleigh quotient (from the variational characterization) of the spectral gap of the Laplacian matrix of over vectors with support at most over a suitable probability measure. Formally, the spectral profile of a graph is a function defined as: where is the weight of the edge in the graph, is the degree of vertex , and is the fraction of edges incident on vertices within the support of vector .
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 -factor approximation for the value of . 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.
- small-set expansion
- approximation algorithms
- semidefinite programming