Modularitybased Sparse Soft Graph Clustering
[edit]
Proceedings of Machine Learning Research, PMLR 89:323332, 2019.
Abstract
Clustering is a central problem in machine learning for which graphbased approaches have proven their efficiency. In this paper, we study a relaxation of the modularity maximization problem, wellknown in the graph partitioning literature. A solution of this relaxation gives to each element of the dataset a probability to belong to a given cluster, whereas a solution of the standard modularity problem is a partition. We introduce an efficient optimization algorithm to solve this relaxation, that is both memory efficient and local. Furthermore, we prove that our method includes, as a special case, the Louvain optimization scheme, a stateoftheart technique to solve the traditional modularity problem. Experiments on both synthetic and realworld data illustrate that our approach provides meaningful information on various types of data.
Related Material


