# Spectral Theory of Unsigned and Signed Graphs. Applications to Graph Clustering: a Survey

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Jan 2016.

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

- [Two Trades is not Baffled: Condensing Graph via Crafting Rational Gradient Matching](https://mlsanity.com/paper/2402.04924/) (2024)
- [Learning to solve Minimum Cost Multicuts efficiently using Edge-Weighted Graph Convolutional Neural Networks](https://mlsanity.com/paper/2204.01366/) (2022)
- [Graph similarity learning for change-point detection in dynamic networks](https://mlsanity.com/paper/2203.15470/) (2022)
- [A Method for Handling Negative Similarities in Explainable Graph Spectral Clustering of Text Documents -- Extended Version](https://mlsanity.com/paper/2504.12360/) (2025)
- [Enabling Tensor Decomposition for Time-Series Classification via A Simple Pseudo-Laplacian Contrast](https://mlsanity.com/paper/2409.15200/) (2024)

## Abstract (arXiv)

This is a survey of the method of graph cuts and its applications to graph clustering of weighted unsigned and signed graphs. I provide a fairly thorough treatment of the method of normalized graph cuts, a deeply original method due to Shi and Malik, including complete proofs. The main thrust of this paper is the method of normalized cuts. I give a detailed account for K = 2 clusters, and also for K > 2 clusters, based on the work of Yu and Shi. I also show how both graph drawing and normalized cut K-clustering can be easily generalized to handle signed graphs, which are weighted graphs in which the weight matrix W may have negative coefficients. Intuitively, negative coefficients indicate distance or dissimilarity. The solution is to replace the degree matrix by the matrix in which absolute values of the weights are used, and to replace the Laplacian by the Laplacian with the new degree matrix of absolute values. As far as I know, the generalization of K-way normalized clustering to signed graphs is new. Finally, I show how the method of ratio cuts, in which a cut is normalized by the size of the cluster rather than its volume, is just a special case of normalized cuts.