Modularity-based Sparse Soft Graph Clustering
Alexandre Hollocou, Thomas Bonald, Marc Lelarge
Abstract
Clustering is a central problem in machine learning for which graph-based approaches have proven their efficiency. In this paper, we study a relaxation of the modularity maximization problem, well-known 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 state-of-the-art technique to solve the traditional modularity problem. Experiments on both synthetic and real-world data illustrate that our approach provides meaningful information on various types of data.
BibTeX
@InProceedings{pmlr-v89-hollocou19a,
title = {Modularity-based Sparse Soft Graph Clustering},
author = {Hollocou, Alexandre and Bonald, Thomas and Lelarge, Marc},
booktitle = {Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics},
pages = {323--332},
year = {2019},
editor = {Chaudhuri, Kamalika and Sugiyama, Masashi},
volume = {89},
series = {Proceedings of Machine Learning Research},
month = {16--18 Apr},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v89/hollocou19a/hollocou19a.pdf},
url = {https://proceedings.mlr.press/v89/hollocou19a.html},
abstract = {Clustering is a central problem in machine learning for which graph-based approaches have proven their efficiency. In this paper, we study a relaxation of the modularity maximization problem, well-known 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 state-of-the-art technique to solve the traditional modularity problem. Experiments on both synthetic and real-world data illustrate that our approach provides meaningful information on various types of data.}
}