The Power Mean Laplacian for Multilayer Graph Clustering

Pedro Mercado, Antoine Gautier, Francesco Tudisco, Matthias Hein
Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, PMLR 84:1828-1838, 2018.

Abstract

Multilayer graphs encode different kind of interactions between the same set of entities. When one wants to cluster such a multilayer graph, the natural question arises how one should merge the information from different layers. We introduce in this paper a one-parameter family of matrix power means for merging the Laplacians from different layers and analyze it in expectation in the stochastic block model. We show that this family allows to recover ground truth clusters under different settings and verify this in real world data. While the matrix power mean is computationally expensive to compute we introduce a scalable numerical scheme that allows to efficiently compute the eigenvectors of the matrix power mean of large sparse graphs.

Cite this Paper

BibTeX
@InProceedings{pmlr-v84-mercado18a, title = {The Power Mean Laplacian for Multilayer Graph Clustering}, author = {Mercado, Pedro and Gautier, Antoine and Tudisco, Francesco and Hein, Matthias}, booktitle = {Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics}, pages = {1828--1838}, year = {2018}, editor = {Storkey, Amos and Perez-Cruz, Fernando}, volume = {84}, series = {Proceedings of Machine Learning Research}, month = {09--11 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v84/mercado18a/mercado18a.pdf}, url = {https://proceedings.mlr.press/v84/mercado18a.html}, abstract = {Multilayer graphs encode different kind of interactions between the same set of entities. When one wants to cluster such a multilayer graph, the natural question arises how one should merge the information from different layers. We introduce in this paper a one-parameter family of matrix power means for merging the Laplacians from different layers and analyze it in expectation in the stochastic block model. We show that this family allows to recover ground truth clusters under different settings and verify this in real world data. While the matrix power mean is computationally expensive to compute we introduce a scalable numerical scheme that allows to efficiently compute the eigenvectors of the matrix power mean of large sparse graphs.} }
Endnote
%0 Conference Paper %T The Power Mean Laplacian for Multilayer Graph Clustering %A Pedro Mercado %A Antoine Gautier %A Francesco Tudisco %A Matthias Hein %B Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2018 %E Amos Storkey %E Fernando Perez-Cruz %F pmlr-v84-mercado18a %I PMLR %P 1828--1838 %U https://proceedings.mlr.press/v84/mercado18a.html %V 84 %X Multilayer graphs encode different kind of interactions between the same set of entities. When one wants to cluster such a multilayer graph, the natural question arises how one should merge the information from different layers. We introduce in this paper a one-parameter family of matrix power means for merging the Laplacians from different layers and analyze it in expectation in the stochastic block model. We show that this family allows to recover ground truth clusters under different settings and verify this in real world data. While the matrix power mean is computationally expensive to compute we introduce a scalable numerical scheme that allows to efficiently compute the eigenvectors of the matrix power mean of large sparse graphs.
APA
Mercado, P., Gautier, A., Tudisco, F. & Hein, M.. (2018). The Power Mean Laplacian for Multilayer Graph Clustering. Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 84:1828-1838 Available from https://proceedings.mlr.press/v84/mercado18a.html.

Related Material