Flow-Based Algorithms for Improving Clusters: A Unifying Framework, Software, and Performance
Flow-Based Algorithms for Improving Clusters: A Unifying Framework, Software, and Performance
复制标题
DOI：
10.1137/20m1333055
复制
发表时间：
2023-01-01
期刊：
影响因子：
10.2
通讯作者：
Mahoney，Michael W.
中科院分区：
文献类型：
--
作者：
Fountoulakis，Kimon;Liu，Meng;Mahoney，Michael W.
聚类向量空间中的点或图中的节点是统计数据分析中普遍存在的基本方法，通常用于探索性数据分析。 在实践中，通常感兴趣的是“细化”或“改进”通过某些其他方法获得的给定聚类。在这次调查中，我们专注于原则性算法，这类改进问题。许多这样的集群改进算法是基于流的方法，我们的意思是，在操作上，他们需要解决一系列的最大流问题（通常是隐式的）修改的数据图。这些聚类改进算法是强大的，在理论和实践中，但他们还没有被广泛采用的问题，如社区检测，局部图聚类，半监督学习等，可能的原因是这些算法的陡峭的学习曲线，缺乏高效和易于使用的软件，以及缺乏详细的数值实验，在现实世界的数据，证明其有用性。我们的目标是解决这些问题。为此，我们将引导读者了解如何实现和应用这些强大的算法的整个过程。我们提出了一个统一的分式规划优化框架，使我们能够以一种简单的方式提取所有这些算法的关键组成部分。这也使得相关方法之间存在明显的相似性和差异性。通过分式编程框架查看这些聚类改进算法，为未来的算法开发提出了方向。最后，我们在我们的LocalGraphClustering Python包中开发了这些算法的有效实现，并进行了大量的数值实验，以证明这些方法在社交网络和基于图像的数据图上的性能。
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 thiscluster 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, semisupervised 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. This also makes apparent similarities and differences among 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.