  Flow-based methods for local graph clustering have received significant
recent attention for their theoretical cut improvement and runtime guarantees.
In this work we present two improvements for using flow-based methods in
real-world semi-supervised clustering problems. Our first contribution is a
generalized objective function that allows practitioners to place strict and
soft penalties on excluding specific seed nodes from the output set. This
feature allows us to avoid the tendency, often exhibited by previous flow-based
methods, to contract a large seed set into a small set of nodes that does not
contain all or even most of the seed nodes. Our second contribution is a fast
algorithm for minimizing our generalized objective function, based on a variant
of the push-relabel algorithm for computing preflows. We make our approach very
fast in practice by implementing a global relabeling heuristic and employing a
warm-start procedure to quickly solve related cut problems. In practice our
algorithm is faster than previous related flow-based methods, and is also more
robust in detecting ground truth target regions in a graph, thanks to its
ability to better incorporate semi-supervised information about target
clusters.
