# On a 'Two Truths' Phenomenon in Spectral Graph Clustering

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

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Aug 2018.

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

- [One-Hot Graph Encoder Embedding](https://mlsanity.com/paper/2109.13098/) (2021)
- [Graph Encoder Ensemble for Simultaneous Vertex Embedding and Community Detection](https://mlsanity.com/paper/2301.11290/) (2023)
- [Matrix factorisation and the interpretation of geodesic distance](https://mlsanity.com/paper/2106.01260/) (2021)
- [Refined Graph Encoder Embedding via Self-Training and Latent Community Recovery](https://mlsanity.com/paper/2405.12797/) (2024)
- [Encoder Embedding for General Graph and Node Classification](https://mlsanity.com/paper/2405.15473/) (2024)
- [Informative core identification in complex networks](https://mlsanity.com/paper/2101.06388/) (2021)
- [Heterogeneous Data Fusion Considering Spatial Correlations using Graph Convolutional Networks and its Application in Air Quality Prediction](https://mlsanity.com/paper/2105.13125/) (2021)
- [Principal Graph Encoder Embedding and Principal Community Detection](https://mlsanity.com/paper/2501.14939/) (2025)
- [Implications of sparsity and high triangle density for graph representation learning](https://mlsanity.com/paper/2210.15277/) (2022)
- [Detection of Model-based Planted Pseudo-cliques in Random Dot Product Graphs by the Adjacency Spectral Embedding and the Graph Encoder Embedding](https://mlsanity.com/paper/2312.11054/) (2023)
- [Edge-Parallel Graph Encoder Embedding](https://mlsanity.com/paper/2402.04403/) (2024)
- [A Graph Sufficiency Perspective for Neural Networks](https://mlsanity.com/paper/2507.10215/) (2025)
- [Community Detection in Weighted Multilayer Networks with Ambient Noise](https://mlsanity.com/paper/2103.00486/) (2021)
- [Latent structure blockmodels for Bayesian spectral graph clustering](https://mlsanity.com/paper/2107.01734/) (2021)
- [Spectral embedding and the latent geometry of multipartite networks](https://mlsanity.com/paper/2202.03945/) (2022)
- [A generative neural network model for random dot product graphs](https://mlsanity.com/paper/2204.07634/) (2022)
- [Dynamic Network Sampling for Community Detection](https://mlsanity.com/paper/2208.13921/) (2022)
- [Two to Five Truths in Non-Negative Matrix Factorization](https://mlsanity.com/paper/2305.05389/) (2023)
- [On the Power of SVD in the Stochastic Block Model](https://mlsanity.com/paper/2309.15322/) (2023)
- [Fast and Scalable Multi-Kernel Encoder Classifier](https://mlsanity.com/paper/2406.02189/) (2024)
- [Asymptotically perfect seeded graph matching without edge correlation (and applications to inference)](https://mlsanity.com/paper/2506.02825/) (2025)
- [Beyond the Laplacian: Interpolated Spectral Augmentation for Graph Neural Networks](https://mlsanity.com/paper/2511.11928/) (2025)
- [Adjacency Spectral Embeddings of Correlation Networks](https://mlsanity.com/paper/2602.21055/) (2026)
- [The ASE-LSE Disagreement Landscape: An End-to-End Characterisation of Extremes and Structural Drivers](https://mlsanity.com/paper/2605.22346/) (2026)

## Abstract (arXiv)

Clustering is concerned with coherently grouping observations without any explicit concept of true groupings. Spectral graph clustering - clustering the vertices of a graph based on their spectral embedding - is commonly approached via K-means (or, more generally, Gaussian mixture model) clustering composed with either Laplacian or Adjacency spectral embedding (LSE or ASE). Recent theoretical results provide new understanding of the problem and solutions, and lead us to a 'Two Truths' LSE vs. ASE spectral graph clustering phenomenon convincingly illustrated here via a diffusion MRI connectome data set: the different embedding methods yield different clustering results, with LSE capturing left hemisphere/right hemisphere affinity structure and ASE capturing gray matter/white matter core-periphery structure.