From Leiden to Tel-Aviv University (TAU): exploring clustering solutions via a genetic algorithm

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.