On a two-truths phenomenon in spectral graph clustering

2018/08/31 by Carey E. Priebe, Youngser Park, Joshua T Vogelstein +7 · 1 citation
Computer Science · Mathematics · Medicine · Neuroscience · Physics and Astronomy · #Adjacency list #Advanced Neuroimaging Techniques and Applications #Artificial intelligence #Cluster analysis #Combinatorics #Complex Network Analysis Techniques #Computer science #Embedding #Functional Brain Connectivity Studies #Graph #Mathematics #Pattern recognition (psychology) #Spectral clustering #cs.LG #stat.ML

paper · pdf · doi:10.1073/pnas.1814462116

published as PNAS 116 (2019) 5995-6000

arxiv created 2019/02/11 · openalex publication_date 2019/03/08 · arxiv updated 2019/04/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

Abstract

Significance Spectral graph clustering—clustering the vertices of a graph based on their spectral embedding—is of significant current interest, finding applications throughout the sciences. But as with clustering in general, what a particular methodology identifies as “clusters” is defined (explicitly, or, more often, implicitly) by the clustering algorithm itself. We provide a clear and concise demonstration of a “two-truths” phenomenon for spectral graph clustering in which the first step—spectral embedding—is either Laplacian spectral embedding, wherein one decomposes the normalized Laplacian of the adjacency matrix, or adjacency spectral embedding given by a decomposition of the adjacency matrix itself. The two resulting clustering methods identify fundamentally different (true and meaningful) structure.

Citations

• Model-Based Clustering, Discriminant Analysis, and Density Estimation
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• Comparing community structure identification
• THE DISTRIBUTION OF THE FLORA IN THE ALPINE ZONE.1
• A tutorial on spectral clustering
• A new look at the statistical model identification
• Comparing clusterings—an information based distance
• The ground truth about metadata and community detection in networks

Cited by

• Accurate and Efficient MCMC for Latent Position Models

Related

• flow-based clustering and spectral clustering: a comparison
• A Tutorial on Spectral Clustering
• Advanced Graph Clustering Methods: A Comprehensive and In-Depth Analysis
• A Tighter Analysis of Spectral Clustering, and Beyond
• Partitioning Well-Clustered Graphs: Spectral Clustering Works!