On spectral partitioning of signed graphs

2018/01/01 by Andrew Knyazev · 4 citations
Chemistry · Mathematics · Physics and Astronomy · #Algebraic connectivity #Artificial intelligence #Combinatorics #Complex Network Analysis Techniques #Computer science #Contrast (vision) #Discrete mathematics #Eigenvalues and eigenvectors #Graph #Graph theory and applications #Laplace operator #Laplacian matrix #Line graph #Mathematical analysis #Mathematics #Physics #Signed graph #Simple (philosophy) #Spectral graph theory #Synthesis and Properties of Aromatic Compounds #Voltage graph

paper · pdf · doi:10.1137/1.9781611975215.2

published in Society for Industrial and Applied Mathematics eBooks, 11-22 (Society for Industrial and Applied Mathematics)

openalex publication_date 2018/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

Abstract

We argue that the standard graph Laplacian is preferable for spectral partitioning of signed graphs compared to the signed Laplacian. Simple examples demonstrate that partitioning based on signs of components of the leading eigenvectors of the signed Laplacian may be meaningless, in contrast to partitioning based on the Fiedler vector of the standard graph Laplacian for signed graphs. We observe that negative eigenvalues are beneficial for spectral partitioning of signed graphs, making the Fiedler vector easier to compute.

Citations

• Toward the Optimal Preconditioned Eigensolver: Locally Optimal Block Preconditioned Conjugate Gradient Method
• A tutorial on spectral clustering
• Spectral Theory of Unsigned and Signed Graphs. Applications to Graph Clustering: a Survey
• megaman: Manifold Learning with Millions of points
• The Hidden Convexity of Spectral Clustering

Cited by

• A Method for Handling Negative Similarities in Explainable Graph Spectral Clustering of Text Documents -- Extended Version
• Graph partition [wikipedia]