Priebe, Carey E.; Park, Youngser; Vogelstein, Joshua T.; Conroy, John M.; Lyzinski, Vince; Tang, Minh; Athreya, Avanti; Cape, Joshua; Bridgeford, Eric On a two-truths phenomenon in spectral graph clustering. (English) Zbl 1431.62269 Proc. Natl. Acad. Sci. USA 116, No. 13, 5995-6000 (2019). Summary: 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 spectral embedding (LSE) or adjacency spectral embedding (ASE). Recent theoretical results provide deeper 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 dataset: 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. Cited in 7 Documents MSC: 62H30 Classification and discrimination; cluster analysis (statistical aspects) 68T10 Pattern recognition, speech recognition 62R40 Topological data analysis 05C85 Graph algorithms (graph-theoretic aspects) 05C82 Small world graphs, complex networks (graph-theoretic aspects) 05C50 Graphs and linear algebra (matrices, eigenvalues, etc.) PDFBibTeX XMLCite \textit{C. E. Priebe} et al., Proc. Natl. Acad. Sci. USA 116, No. 13, 5995--6000 (2019; Zbl 1431.62269) Full Text: DOI arXiv