Flow-based Algorithms for Improving Clusters: A Unifying Framework,
  Software, and Performance
  Clustering points in a vector space or nodes in a graph is a ubiquitous
primitive in statistical data analysis, and it is commonly used for exploratory
data analysis. In practice, it is often of interest to "refine" or "improve" a
given cluster that has been obtained by some other method. In this survey, we
focus on principled algorithms for this cluster improvement problem. Many such
cluster improvement algorithms are flow-based methods, by which we mean that
operationally they require the solution of a sequence of maximum flow problems
on a (typically implicitly) modified data graph. These cluster improvement
algorithms are powerful, both in theory and in practice, but they have not been
widely adopted for problems such as community detection, local graph
clustering, semi-supervised learning, etc. Possible reasons for this are: the
steep learning curve for these algorithms; the lack of efficient and easy to
use software; and the lack of detailed numerical experiments on real-world data
that demonstrate their usefulness. Our objective here is to address these
issues. To do so, we guide the reader through the whole process of
understanding how to implement and apply these powerful algorithms. We present
a unifying fractional programming optimization framework that permits us to
distill, in a simple way, the crucial components of all these algorithms. It
also makes apparent similarities and differences between related methods.
Viewing these cluster improvement algorithms via a fractional programming
framework suggests directions for future algorithm development. Finally, we
develop efficient implementations of these algorithms in our
LocalGraphClustering Python package, and we perform extensive numerical
experiments to demonstrate the performance of these methods on social networks
and image-based data graphs.
