Clustering signed networks with the geometric mean of Laplacians

Mercado, Pedro and Tudisco, Francesco and Hein, Matthias (2016) Clustering signed networks with the geometric mean of Laplacians. In: NIPS 2016 - Neural Information Processing Systems, 2016-12-05 - 2016-12-10, Centre Convencions Internacional Barcelona. (https://papers.nips.cc/paper/6164-clustering-signe...)

[thumbnail of Mercado-etal-ANIPS-2016-clustering-signed-networks-with-the-geometric-mean-of-laplacians]
Preview
 Text. Filename: Mercado_etal_ANIPS_2016_clustering_signed_networks_with_the_geometric_mean_of_laplacians.pdf
Final Published Version
Download (3MB)| Preview

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.

  • Item type:Conference or Workshop Item(Paper)
    ID code:62138
    Dates:
    Date
    Event
    5 December 2016
    Published
    22 July 2016
    Accepted
    Subjects:Science > Mathematics
    Department:Faculty of Science > Mathematics and Statistics
    Depositing user: Pure Administrator
    Date deposited:24 Oct 2017 10:00
    Last modified:11 Nov 2024 16:52
    URI:https://strathprints.strath.ac.uk/id/eprint/62138
CORE (COnnecting REpositories)