The Power Mean Laplacian for Multilayer Graph Clustering

About

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 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 computing the matrix power mean can be very expensive for large graphs, we introduce a numerical scheme to efficiently compute its eigenvectors for the case of large sparse graphs.

Pedro Mercado, Antoine Gautier, Francesco Tudisco, Matthias Hein (1) __INSTITUTION_4__ Saarland University, (2) University of Strathclyde) · 2018

Related benchmarks

Task	Dataset	Result
Multilayer Graph Clustering	BBCS (BBC Sports)	Average Clustering Error0.144	8
Multilayer Graph Clustering	Wiki Wikipedia	Average Clustering Error0.368	8
Multilayer Graph Clustering	UCI Handwritten Digits	Avg Clustering Error0.095	8
Multilayer Graph Clustering	Citeseer	Avg Clustering Error0.283	8
Multilayer Graph Clustering	Cora	Avg Clustering Error37.4	8
Multilayer Graph Clustering	3Sources	Average Clustering Error20	8
Multilayer Graph Clustering	BBC	Average Clustering Error15.9	8
Multilayer Graph Clustering	WebKB Texas	Average Clustering Error0.439	8