Flow-Based Algorithms for Local Graph Clustering
  Given a subset S of vertices of an undirected graph G, the cut-improvement
problem asks us to find a subset S that is similar to A but has smaller
conductance. A very elegant algorithm for this problem has been given by
Andersen and Lang [AL08] and requires solving a small number of
single-commodity maximum flow computations over the whole graph G. In this
paper, we introduce LocalImprove, the first cut-improvement algorithm that is
local, i.e. that runs in time dependent on the size of the input set A rather
than on the size of the entire graph. Moreover, LocalImprove achieves this
local behaviour while essentially matching the same theoretical guarantee as
the global algorithm of Andersen and Lang.
  The main application of LocalImprove is to the design of better
local-graph-partitioning algorithms. All previously known local algorithms for
graph partitioning are random-walk based and can only guarantee an output
conductance of O(\sqrt{OPT}) when the target set has conductance OPT \in [0,1].
Very recently, Zhu, Lattanzi and Mirrokni [ZLM13] improved this to O(OPT /
\sqrt{CONN}) where the internal connectivity parameter CONN \in [0,1] is
defined as the reciprocal of the mixing time of the random walk over the graph
induced by the target set. In this work, we show how to use LocalImprove to
obtain a constant approximation O(OPT) as long as CONN/OPT = Omega(1). This
yields the first flow-based algorithm. Moreover, its performance strictly
outperforms the ones based on random walks and surprisingly matches that of the
best known global algorithm, which is SDP-based, in this parameter regime
[MMV12].
  Finally, our results show that spectral methods are not the only viable
approach to the construction of local graph partitioning algorithm and open
door to the study of algorithms with even better approximation and locality
guarantees.
