Abstract
In the generalized sparsest cut problem, given two undirected graphs G and H sharing the same set of vertices V, the goal is to find a a cut (S,V−S) that minimizes the ratio between the G-edges that are cut and the H-edges that are cut. It is known that Cheeger-like approximations to the cut are not possible assuming the Unique Games Conjecture. Despite that, we claim that generalized eigenvectors of the pair can still provide valuable information about the cut. We discuss appropriate generalizations of the Cheeger inequality that lend theoretical support to this claim. We also present experimental evidence: we formulate 'constrained clustering' problems as generalized cut problems and solve them through their spectral relaxations. The resulting algorithms provide large gains in speed and output quality relative to known methods.
.This is joint work with Mihai Cucuringu and Sanjay Chawla.