Clustering signed networks with the geometric mean of Laplacians

Pedro Mercado; Francesco Tudisco; Matthias Hein

Clustering signed networks with the geometric mean of Laplacians

Pedro Mercado, Francesco Tudisco, Matthias Hein

Mathematics And Statistics

Research output: Contribution to conference › Paper › peer-review

42 Citations (Scopus)

88 Downloads (Pure)

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.

Original language	English
Publication status	Published - 5 Dec 2016
Event	NIPS 2016 - Neural Information Processing Systems - Centre Convencions Internacional Barcelona, Barcelona, Spain Duration: 5 Dec 2016 → 10 Dec 2016

Conference

Conference	NIPS 2016 - Neural Information Processing Systems
Abbreviated title	NIPS
Country/Territory	Spain
City	Barcelona
Period	5/12/16 → 10/12/16

Keywords

signed networks
spectral clustering
Laplacians
geometric mean
neural networks

Access to Document

Mercado-etal-ANIPS-2016-clustering-signed-networks-with-the-geometric-mean-of-laplaciansFinal published version, 3.04 MB

Cite this

@conference{8111ea4f6d26473781d581e6312ee08c,

title = "Clustering signed networks with the geometric mean of Laplacians",

abstract = "Signed networks allow to model positive and negative relationships. We analyzeexisting extensions of spectral clustering to signed networks. It turns out thatexisting approaches do not recover the ground truth clustering in several situationswhere either the positive or the negative network structures contain no noise. Ouranalysis shows that these problems arise as existing approaches take some form ofarithmetic mean of the Laplacians of the positive and negative part. As a solutionwe propose to use the geometric mean of the Laplacians of positive and negativepart and show that it outperforms the existing approaches. While the geometricmean of matrices is computationally expensive, we show that eigenvectors of thegeometric mean can be computed efficiently, leading to a numerical scheme forsparse matrices which is of independent interest.",

keywords = "signed networks, spectral clustering, Laplacians, geometric mean, neural networks",

author = "Pedro Mercado and Francesco Tudisco and Matthias Hein",

year = "2016",

month = dec,

day = "5",

language = "English",

note = "NIPS 2016 - Neural Information Processing Systems, NIPS ; Conference date: 05-12-2016 Through 10-12-2016",

}

TY - CONF

T1 - Clustering signed networks with the geometric mean of Laplacians

AU - Mercado, Pedro

AU - Tudisco, Francesco

AU - Hein, Matthias

PY - 2016/12/5

Y1 - 2016/12/5

N2 - Signed networks allow to model positive and negative relationships. We analyzeexisting extensions of spectral clustering to signed networks. It turns out thatexisting approaches do not recover the ground truth clustering in several situationswhere either the positive or the negative network structures contain no noise. Ouranalysis shows that these problems arise as existing approaches take some form ofarithmetic mean of the Laplacians of the positive and negative part. As a solutionwe propose to use the geometric mean of the Laplacians of positive and negativepart and show that it outperforms the existing approaches. While the geometricmean of matrices is computationally expensive, we show that eigenvectors of thegeometric mean can be computed efficiently, leading to a numerical scheme forsparse matrices which is of independent interest.

AB - Signed networks allow to model positive and negative relationships. We analyzeexisting extensions of spectral clustering to signed networks. It turns out thatexisting approaches do not recover the ground truth clustering in several situationswhere either the positive or the negative network structures contain no noise. Ouranalysis shows that these problems arise as existing approaches take some form ofarithmetic mean of the Laplacians of the positive and negative part. As a solutionwe propose to use the geometric mean of the Laplacians of positive and negativepart and show that it outperforms the existing approaches. While the geometricmean of matrices is computationally expensive, we show that eigenvectors of thegeometric mean can be computed efficiently, leading to a numerical scheme forsparse matrices which is of independent interest.

KW - signed networks

KW - spectral clustering

KW - Laplacians

KW - geometric mean

KW - neural networks

UR - https://papers.nips.cc/paper/6164-clustering-signed-networks-with-the-geometric-mean-of-laplacians

M3 - Paper

T2 - NIPS 2016 - Neural Information Processing Systems

Y2 - 5 December 2016 through 10 December 2016

ER -

Clustering signed networks with the geometric mean of Laplacians

Abstract

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this