Improved Parallel Algorithms for Density-Based Network Clustering

Mohsen Ghaffari, Silvio Lattanzi, Slobodan Mitrović
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:2201-2210, 2019.

Abstract

Clustering large-scale networks is a central topic in unsupervised learning with many applications in machine learning and data mining. A classic approach to cluster a network is to identify regions of high edge density, which in the literature is captured by two fundamental problems: the densest subgraph and the $k$-core decomposition problems. We design massively parallel computation (MPC) algorithms for these problems that are considerably faster than prior work. In the case of $k$-core decomposition, our work improves exponentially on the algorithm provided by Esfandiari et al. (ICML’18). Compared to the prior work on densest subgraph presented by Bahmani et al. (VLDB’12, ’14), our result requires quadratically fewer MPC rounds. We complement our analysis with an experimental scalability analysis of our techniques.

Cite this Paper

BibTeX
@InProceedings{pmlr-v97-ghaffari19a, title = {Improved Parallel Algorithms for Density-Based Network Clustering}, author = {Ghaffari, Mohsen and Lattanzi, Silvio and Mitrovi{\'c}, Slobodan}, booktitle = {Proceedings of the 36th International Conference on Machine Learning}, pages = {2201--2210}, year = {2019}, editor = {Chaudhuri, Kamalika and Salakhutdinov, Ruslan}, volume = {97}, series = {Proceedings of Machine Learning Research}, month = {09--15 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v97/ghaffari19a/ghaffari19a.pdf}, url = {https://proceedings.mlr.press/v97/ghaffari19a.html}, abstract = {Clustering large-scale networks is a central topic in unsupervised learning with many applications in machine learning and data mining. A classic approach to cluster a network is to identify regions of high edge density, which in the literature is captured by two fundamental problems: the densest subgraph and the $k$-core decomposition problems. We design massively parallel computation (MPC) algorithms for these problems that are considerably faster than prior work. In the case of $k$-core decomposition, our work improves exponentially on the algorithm provided by Esfandiari et al. (ICML’18). Compared to the prior work on densest subgraph presented by Bahmani et al. (VLDB’12, ’14), our result requires quadratically fewer MPC rounds. We complement our analysis with an experimental scalability analysis of our techniques.} }
Endnote
%0 Conference Paper %T Improved Parallel Algorithms for Density-Based Network Clustering %A Mohsen Ghaffari %A Silvio Lattanzi %A Slobodan Mitrović %B Proceedings of the 36th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Ruslan Salakhutdinov %F pmlr-v97-ghaffari19a %I PMLR %P 2201--2210 %U https://proceedings.mlr.press/v97/ghaffari19a.html %V 97 %X Clustering large-scale networks is a central topic in unsupervised learning with many applications in machine learning and data mining. A classic approach to cluster a network is to identify regions of high edge density, which in the literature is captured by two fundamental problems: the densest subgraph and the $k$-core decomposition problems. We design massively parallel computation (MPC) algorithms for these problems that are considerably faster than prior work. In the case of $k$-core decomposition, our work improves exponentially on the algorithm provided by Esfandiari et al. (ICML’18). Compared to the prior work on densest subgraph presented by Bahmani et al. (VLDB’12, ’14), our result requires quadratically fewer MPC rounds. We complement our analysis with an experimental scalability analysis of our techniques.
APA
Ghaffari, M., Lattanzi, S. & Mitrović, S.. (2019). Improved Parallel Algorithms for Density-Based Network Clustering. Proceedings of the 36th International Conference on Machine Learning, in Proceedings of Machine Learning Research 97:2201-2210 Available from https://proceedings.mlr.press/v97/ghaffari19a.html.

Related Material