  We study polynomial-time approximation algorithms for (edge/vertex) Sparsest
Cut and Small Set Expansion in terms of $k$, the number of edges or vertices
cut in the optimal solution. Our main results are $\mathcal{O}(\text{polylog}\,
k)$-approximation algorithms for various versions in this setting.
  Our techniques involve an extension of the notion of sample sets (Feige and
Mahdian STOC'06), originally developed for small balanced cuts, to sparse cuts
in general. We then show how to combine this notion of sample sets with two
algorithms, one based on an existing framework of LP rounding and another new
algorithm based on the cut-matching game, to get such approximation algorithms.
Our cut-matching game algorithm can be viewed as a local version of the
cut-matching game by Khandekar, Khot, Orecchia and Vishnoi and certifies an
expansion of every vertex set of size $s$ in $\mathcal{O}(\log s)$ rounds.
These techniques may be of independent interest.
  As corollaries of our results, we also obtain an $\mathcal{O}(\log
opt)$-approximation for min-max graph partitioning, where $opt$ is the min-max
value of the optimal cut, and improve the bound on the size of multicut
mimicking networks computable in polynomial time.
