Gilad Gal, Sharan Roded
School of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel.
PNAS Nexus. 2023 Jun 1;2(6):pgad180. doi: 10.1093/pnasnexus/pgad180. eCollection 2023 Jun.
Graph clustering is a fundamental problem in machine learning with numerous applications in data science. State-of-the-art approaches to the problem, Louvain and Leiden, aim at optimizing the modularity function. However, their greedy nature leads to fast convergence to sub-optimal solutions. Here, we design a new approach to graph clustering, Tel-Aviv University (TAU), that efficiently explores the solution space using a genetic algorithm. We benchmark TAU on synthetic and real data sets and show its superiority over previous methods both in terms of the modularity of the computed solution and its similarity to a ground-truth partition when such exists. TAU is available at https://github.com/GalGilad/TAU.
图聚类是机器学习中的一个基本问题，在数据科学中有众多应用。针对该问题的现有先进方法，如Louvain和Leiden，旨在优化模块度函数。然而，它们的贪婪性质导致快速收敛到次优解。在此，我们设计了一种新的图聚类方法——特拉维夫大学（TAU）方法，该方法使用遗传算法有效地探索解空间。我们在合成数据集和真实数据集上对TAU进行基准测试，并表明其在计算解的模块度以及与真实划分（若存在）的相似性方面均优于先前方法。TAU可在https://github.com/GalGilad/TAU获取。
