Spectral Clustering

Follow this topic Ask about this topic

Spectral clustering turns data similarities into a graph or matrix, uses eigenvectors of a Laplacian or related operator to create a low-dimensional embedding, then partitions that embedding. It is used to find communities in networks and groups in text, images, multi-view data, and high-dimensional observations, including settings where relationships are directed or higher-order. Methods include normalized-Laplacian and non-backtracking embeddings, multi-kernel affinities, perturbation-based recovery guarantees, and scalable randomized or GPU-accelerated eigensolvers. A central challenge is choosing an affinity graph and spectral normalization that reveal the right structure across sparse, imbalanced, or geometrically complex data without making computation prohibitive.

Latest papers

21 papers3 papers in the last four weeks, level with the four weeks before. 0.0% of all new papers.

Kernelised covariance matrices, dimension reduction and imbalanced spectral clustering
Oct 23, 2026Xiaoyu Dong, Subhro Ghosh, Soumendu Sundar Mukherjee +1Clustering Spectral Clustering
National University of Singapore, Singapore · Indian Statistical Institute, Kolkata, India
Federated Community Detection in Bipartite Networks
Oct 19, 2026Wanjie WangGraph Clustering Federated Graph Learning
Department of Statistics and Data Science, National University of Singapore
LoomSC: Scalable Deep Subspace Clustering with Projector Factorization and Exact Spectral Reduction
Oct 7, 2026Nairouz Mrabah, Youssef Melki, Mohamed Bouguessa +3Clustering Spectral Clustering
École de technologie supérieure (ÉTS), Montréal, QC, Canada · University of Bahrain (UOB), Kingdom of Bahrain · Université du Québec à Montréal (UQAM), Montréal, QC, Canada +1
Randomized SVD Approximations for Spectral Co-Clustering of Word-Document Matrices
Sep 16, 2026Fateme Mazdarani, Carlos ToxtliClustering Randomized Sketching
School of Computing Clemson University Clemson, SC, USA
SPARROW: Scalable Taxonomy Induction via Structure-Preserving Partitioning and Constraint-Guided Merging
Sep 7, 2026Yirui Zhang, Yixuan Tang, Yandong Sun +2Spectral Clustering Taxonomy Induction
School of Computing, National University of Singapore
MSSP: Multi-Scale Spatially-Constrained Partition for Unsupervised Semantic Segmentation of 3D Point Clouds
Sep 7, 2026Zhenghao Zhang, Xinjie Wang, Wei Wang +23D Semantic Segmentation Clustering
College of Electronic Science and Technology, National University of Defense Technology, Changsha, China · School of Electronics and Communication Engineering, Sun Yat-sen University, Shenzhen, China
Clustering as Approximation by Constrained Projectors: Theory and Guarantees
Aug 29, 2026Angshul MajumdarClustering Spectral Clustering
Indraprastha Institute of Information Technology Delhi New Delhi 110020, India
Spectral partitioning for $k$ -block averaging kernels of finite Markov chains
Aug 21, 2026Michael C. H. Choi, Youjia WangMarkov Models Spectral Methods
Department of Statistics and Data Science, National University of Singapore, Level 7, 6 Science Drive 2, 117546, Singapore
Spectral graph clustering with inhomogeneous latent geometry
Aug 11, 2026Konstantin Avrachenkov, Lucas S. Sibemberg, Alexander Van WerdeSpectral Clustering Graph Clustering
Inria Sophia Antipolis, France · Federal University of Rio Grande do Sul, Brazil · University of Münster, Germany
Spectral Embeddings of Degree- $α$ Laplacians in Random Dot Product Graphs
Aug 11, 2026John Park, Ning HaoClustering Spectral Clustering
University of Hong Kong · University of Arizona
Multi-kernel spectral clustering: Entrywise eigenvector perturbation bounds and exact recovery
Aug 9, 2026Zeqin Lin, Guangming Pan, Zhixiang Zhang +1Clustering Unsupervised Clustering
1Nanyang Technological University · University of Macau · 3Dalian University of Technology
Learning and Clustering on Temporal Graphs: Principles, Primitives, and Pooling
Aug 4, 2026Nelson Aloysio Reis de Almeida Passos, Emanuele Carlini, Salvatore TraniGraph Neural Networks Graph Pooling
University of Pisa, Dept. of Computer Science, 56127 Pisa PI, Italy · National Research Council, 56124 Pisa PI, Italy
Accelerating Dynamic Graph Clustering on GPU Architectures with cuGraph
Aug 4, 2026Nelson Aloysio Reis de Almeida Passos, Emanuele Carlini, Salvatore TraniGPU Acceleration Clustering
University of Pisa, Dept. of Computer Science, 56127 Pisa PI, Italy · National Research Council, 56124 Pisa PI, Italy
CaSPECT: Discovering Causally Homogeneous Subgroups via Directed Spectral Clustering
Jul 3, 2026Arghya Pratihar, Shinjon Chakraborty, Swagatam DasCausal Effect Estimation Causal Structure Learning
1*Electronics and Communication Sciences Unit, Indian Statistical Institute, India. · 2Indian Statistical Institute, India.
Minimum Description Length based Granular-Ball Tree Regularization for Spectral Clustering
May 21, 2026Zeqiang Xian, Caihui Liu, Yong Zhang +1Graph Structure Learning Clustering
Department of Mathematics and Computer Science, Gannan Normal University, Ganzhou 341000, Jiangxi, China · Key Laboratory of Data Science and Artificial Intelligence of Jiangxi Education Institutes, Gannan Normal University, Ganzhou 341000, Jiangxi, China
Hidden Coalitions in Multi-Agent AI: A Spectral Diagnostic from Internal Representations
May 4, 2026Cameron Berg, Susan L. Schneider, Mark M. BaileyAI Agent Monitoring Spectral Clustering
Reciprocal Research · New York, NY, USA · Center for the Future of AI, Mind, and Society +5
Achieving the Kesten-Stigum bound in the non-uniform hypergraph stochastic block model
Apr 21, 2026Manuel Fernandez, Ludovic Stephan, Yizhe ZhuSpectral Clustering Stochastic Block Model
Department of Mathematics, University of Southern California · Univ Rennes, Ensai, CNRS, CREST-UMR 9194, F-35000 Rennes, France
Individual-heterogeneous sub-Gaussian Mixture Models
Apr 7, 2026Huan QingClustering Gaussian Mixture Models
School of Economics and Finance, Chongqing University of Technology, Chongqing, 400054, China
Incremental Graph Construction Enables Robust Spectral Clustering of Texts
Mar 3, 2026Marko Pranjić, Boshko Koloski, Nada Lavrač +2Text Clustering Clustering
Joˇzef Stefan Institute and International Postgraduate School, Ljubljana, Slovenia. · University of Ljubljana, Faculty of Computer and Information Science, Ljubljana, Slovenia.
TCG CREST System Description for the DISPLACE-M Challenge
Mar 2, 2026Nikhil Raghav, Md SahidullahVoice Activity Detection Speaker Diarization
Institute for Advancing Intelligence, TCG CREST, Kolkata-700 091, India · Department of Computer Science, RKMVERI, Howrah-711 202, India
Phase-Consistent Magnetic Spectral Learning for Multi-View Clustering
Feb 21, 2026Mingdong Lu, Zhikui Chen, Meng Liu +2Multi-View Clustering Unsupervised Clustering
School of Software, Dalian University of Technology

Oct 23, 2026J/K move · Enter open · S save

Kernelised covariance matrices, dimension reduction and imbalanced spectral clustering

Xiaoyu Dong, Subhro Ghosh, Soumendu Sundar Mukherjee, Himasish Talukdar

National University of Singapore, Singapore · Indian Statistical Institute, Kolkata, India

Clustering Spectral Clustering Dimensionality Reduction Kernel Methods

Open paper AskPDF arXiv

The Gaussian Mixture Model (abbrv. GMM) is a classic generative model for clustered data, for which spectral clustering based on dimension reduction via PCA has been an effective framework. In this work, we investigate kernelised covariance matrices as an alternative mechanism for dimension reduction and spectral clustering, focusing on truncation kernels that select pairs of data points with suitable separation constraints. The structure of these matrices is motivated by considerations from statistical mechanics of repulsive particle systems. Our approach is particularly relevant for the setting of imbalanced clusters, where the sizes of the largest and smallest clusters have a diverging ratio with the problem size, and existing PCA-based methods turn out to be of limited effectiveness. We demonstrate efficient dimension reduction and clustering performance of these modified covariance matrices, substantiated by quantitative bounds. In particular, they achieve superior dimension reduction guarantees compared to PCA for a wide range of parameters in the regime of imbalanced clusters. For spectral clustering, our approach exhibits improvements over PCA in the imbalanced setting, in particular guaranteeing accurate clustering in a much larger regime of intra-cluster separations. Our theoretical guarantees reflected in a range of simulation experiments that exhibit these improvements for unbalanced clustering problems. Our analytical approach, based on kernel Laplacians, provide a toolbox as well as a relevant conceptual ingredient for clustering problems at large. We believe that our work will motivate the application of such kernelised covariance matrices for related classes of statistical problems, as well as spur new investigations in the theory of random matrices.