Modularity-based Sparse Soft Graph Clustering

Alexandre Hollocou, Thomas Bonald, Marc Lelarge
Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, PMLR 89:323-332, 2019.

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.

Cite this Paper

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.} }
Endnote
%0 Conference Paper %T Modularity-based Sparse Soft Graph Clustering %A Alexandre Hollocou %A Thomas Bonald %A Marc Lelarge %B Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Masashi Sugiyama %F pmlr-v89-hollocou19a %I PMLR %P 323--332 %U https://proceedings.mlr.press/v89/hollocou19a.html %V 89 %X 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.
APA
Hollocou, A., Bonald, T. & Lelarge, M.. (2019). Modularity-based Sparse Soft Graph Clustering. Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 89:323-332 Available from https://proceedings.mlr.press/v89/hollocou19a.html.

Related Material