Abstract: Clustering nodes in a graph is a common primitive in statistical data analysis. There are many methods to accomplish this. In practice, it is often useful 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 an implicitly modified graph. These cluster improvement algorithms are powerful, both in theory and in practice, but they have not been as widely adopted for problems such as community detection, local graph clustering, semi-supervised learning as one might expect. Our speculation on reasons includes: 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. The objective of our recent survey (https://arxiv.org/abs/2004.09608) is to address these issues.
In this talk, we will walk through these powerful algorithms and how they would apply to a variety of scenarios including social networks and image-based data graphs. Time-permitting, we will also present a unifying fractional programming optimization framework that permits us to distill out in a simple way the crucial components of all these algorithms. It also makes apparent similarities and differences between related methods. These algorithms are implemented in a python software package to make it easy for others to start using them as well.