Francesco Tudisco

Associate Professor (Reader) in Machine Learning

School of Mathematics, The University of Edinburgh
The Maxwell Institute for Mathematical Sciences
School of Mathematics, Gran Sasso Science Institute JCMB, King’s Buildings, Edinburgh EH93FD UK
email: f dot tudisco at ed.ac.uk

Clustering Signed Networks with the Geometric Mean of Laplacians

Pedro Mercado, Francesco Tudisco, Matthias Hein,
In: Advances in Neural Information Processing Systems 29 (NeurIPS), (2016)

Abstract

Signed networks allow to model positive and negative relationships. We analyze existing extensions of spectral clustering to signed networks. It turns out that existing approaches do not recover the ground truth clustering in several situations where either the positive or the negative network structures contain no noise. Our analysis shows that these problems arise as existing approaches take some form of arithmetic mean of the Laplacians of the positive and negative part. As a solution we propose to use the geometric mean of the Laplacians of positive and negative part and show that it outperforms the existing approaches. While the geometric mean of matrices is computationally expensive, we show that eigenvectors of the geometric mean can be computed efficiently, leading to a numerical scheme for sparse matrices which is of independent interest.


Please cite this work as:

@inproceedings{mercado2016clustering,
  title={Clustering signed networks with the geometric mean of Laplacians},
  author={Mercado, Pedro and Tudisco, Francesco and Hein, Matthias},
  booktitle={Advances in Neural Information Processing Systems (NIPS)},
  pages={4421--4429},
  year={2016}
}

Links: nips code

Keywords: spectral clustering signed networks matrix means geometric mean graph Laplacian networks