Is Cheeger-type Approximation Possible for Nonuniform Sparsest Cut?

In the em nonuniform sparsest cut problem, given two undirected graphs G and H over the same set of vertices V, we want to find a cut (S,V-S) that minimizes the ratio between the fraction of G-edges that are cut and the fraction of H-edges that are cut. The ratio (which is at most 1 in an optimal solution) is called the em sparsity of the cut. In the em uniform sparsest cut problem, H is a clique over V. If G is regular, it is possible to find a solution to the uniform sparsest cut of cost O(√opt) in nearly linear time. Is such an approximation, which we call "Cheege-type" approximation, achievable in the non-uniform case? We show that the answer is negative, assuming the Unique Games Conjecture, for general H. Furthermore, the Leighton-Rao linear programming relaxation and the spectral relaxation fail to find such an approximation even if H is a clique over a subset of vertices. Using semidefinite programming, however, we can find Cheeger-type approximations in polynomial time whenever the adjacency matrix of H has rank 1. (This includes the cases in which H is a clique over a subset of vertices.)