Flow-based Algorithms for Improving Clusters: A Unifying Framework, Software, and Performance

Abstract

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.

75 Pages, 21 Figures

References in corpus (9)

• Fast unfolding of communities in large networks
• Modularity and community structure in networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Detecting the overlapping and hierarchical community structure of complex networks
• Think Locally, Act Locally: The Detection of Small, Medium-Sized, and Large Communities in Large Networks
• Inhomogeneous Hypergraph Clustering with Applications
• Conditional Hardness of Earth Mover Distance
• Semi-supervised Eigenvectors for Large-scale Locally-biased Learning
• Hypergraph Cuts with General Splitting Functions

Cited by in corpus (5)

• Targeted Pandemic Containment Through Identifying Local Contact Network Bottlenecks
• Strongly Local Hypergraph Diffusions for Clustering and Semi-supervised Learning
• $p$-Norm Flow Diffusion for Local Graph Clustering
• Strongly local p-norm-cut algorithms for semi-supervised learning and local graph clustering
• Local Hyper-Flow Diffusion