On a 'Two Truths' Phenomenon in Spectral Graph Clustering

Abstract

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.

References in corpus (5)

• Comparing community structure identification
• Spectral clustering and the high-dimensional stochastic blockmodel
• Matrix estimation by Universal Singular Value Thresholding
• The ground truth about metadata and community detection in networks
• Network histograms and universality of blockmodel approximation

Cited by in corpus (17)

• One-Hot Graph Encoder Embedding
• Inference for multiple heterogeneous networks with a common invariant subspace
• Bayesian estimation of the latent dimension and communities in stochastic blockmodels
• A Simple Spectral Failure Mode for Graph Convolutional Networks
• Heterogeneous Data Fusion Considering Spatial Correlations using Graph Convolutional Networks and its Application in Air Quality Prediction
• Nonparametric two-sample hypothesis testing for low-rank random graphs of differing sizes
• On Two Distinct Sources of Nonidentifiability in Latent Position Random Graph Models
• The Phantom Alignment Strength Conjecture: Practical use of graph matching alignment strength to indicate a meaningful graph match
• The Importance of Being Correlated: Implications of Dependence in Joint Spectral Inference across Multiple Networks
• Encoder Embedding for General Graph and Node Classification
• Simultaneous Dimensionality and Complexity Model Selection for Spectral Graph Clustering
• Manifold structure in graph embeddings
• Latent structure blockmodels for Bayesian spectral graph clustering
• Refined Graph Encoder Embedding via Self-Training and Latent Community Recovery
• Fast and Scalable Multi-Kernel Encoder Classifier
• Matrix factorisation and the interpretation of geodesic distance
• Co-factor analysis of citation networks