# Spectral Clustering of Signed Graphs via Matrix Power Means

arXiv: https://arxiv.org/abs/1905.06230 · HTML: https://mlsanity.com/paper/1905.06230/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 May 2019.

## Built on by (most cited first, 10 of 10)

- [Multilayer Graph Contrastive Clustering Network](https://mlsanity.com/paper/2112.14021/) (2021)
- [Bures-Wasserstein Means of Graphs](https://mlsanity.com/paper/2305.19738/) (2023)
- [Exact Community Recovery over Signed Graphs](https://mlsanity.com/paper/2202.12255/) (2022)
- [DropEdge not Foolproof: Effective Augmentation Method for Signed Graph Neural Networks](https://mlsanity.com/paper/2409.19620/) (2024)
- [Sublinear-Time Clustering Oracle for Signed Graphs](https://mlsanity.com/paper/2206.13813/) (2022)
- [An Efficient Local Search Approach for Polarized Community Discovery in Signed Networks](https://mlsanity.com/paper/2502.02197/) (2025)
- [Community Detection in Weighted Multilayer Networks with Ambient Noise](https://mlsanity.com/paper/2103.00486/) (2021)
- [Defensive Alliances in Signed Networks](https://mlsanity.com/paper/2309.06801/) (2023)
- [A Spectral Framework for Tracking Communities in Evolving Networks](https://mlsanity.com/paper/2412.07378/) (2024)
- [Fast and Featureless Node Representation Learning with Partial Pairwise Supervision](https://mlsanity.com/paper/2605.19916/) (2026)

## Abstract (arXiv)

Signed graphs encode positive (attractive) and negative (repulsive) relations between nodes. We extend spectral clustering to signed graphs via the one-parameter family of Signed Power Mean Laplacians, defined as the matrix power mean of normalized standard and signless Laplacians of positive and negative edges. We provide a thorough analysis of the proposed approach in the setting of a general Stochastic Block Model that includes models such as the Labeled Stochastic Block Model and the Censored Block Model. We show that in expectation the signed power mean Laplacian captures the ground truth clusters under reasonable settings where state-of-the-art approaches fail. Moreover, we prove that the eigenvalues and eigenvector of the signed power mean Laplacian concentrate around their expectation under reasonable conditions in the general Stochastic Block Model. Extensive experiments on random graphs and real world datasets confirm the theoretically predicted behaviour of the signed power mean Laplacian and show that it compares favourably with state-of-the-art methods.