Approximations of graph clustering

Question

Consider the task of clustering a graph, modelled as the balanced cut problem:

Input: $G = (V, E)$ simple graph

Output: $S^* \subseteq V$ such that $S^* = \arg\min_{S \subseteq V} h(S)$. Here, $h(S)$ is the edge expansion of $S$ with respect to the graph $G$, $h(S) = |\{ \{v, v'\} \in E \mid v \in S, v' \in V \setminus S\}|/\min\{|S|, |V\setminus S|\}$.

The task is known to be NP-hard, see e.g. Wagner D., Wagner F. (1993) Between Min Cut and Graph Bisection. Is it known in the literature whenever the task is APX or PTAS? In particular, do the Cheeger's inequalities and subsequent works in spectral clustering contribute in this direction?

Answer 1

As Yury says, the problem is known as the Sparsest Cut. See Theorem 1.3 in "Inapproximability results for maximum edge biclique, minimum linear arrangement, and sparsest cut" by Ambühl, Mastrolilli, and Svensson:

Let $\epsilon > 0$ be an arbitrarily small constant. If there is a PTAS for Sparsest Cut, Minimum Linear Arrangement, or Maximum Edge Biclique, then there is a (probabilistic) algorithm that decides whether a given SAT instance of size $n$ is satisfiable in time $2^{n^\epsilon}$.

So, PTAS seems unlikely since this almost (up to randomization) contradicts ETH. Maybe a stronger result exists.