### 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.

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 | Spain |

City | Barcelona |

Period | 5/12/16 → 10/12/16 |

### Keywords

- signed networks
- spectral clustering
- Laplacians
- geometric mean
- neural networks

## Cite this

Mercado, P., Tudisco, F., & Hein, M. (2016).

*Clustering signed networks with the geometric mean of Laplacians*. Paper presented at NIPS 2016 - Neural Information Processing Systems, Barcelona, Spain.