Spectral clustering revisited: information hidden in the Fiedler vector

DOI10.3934/FODS.2021015MaRDI QIDQ2072633zbMATH OpenOpenAlexFDO

Authors Adela DePavia, Stefan Steinerberger

Publication date 26 January 2022

Published in Foundations of Data Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2003.09969

zbMATH Keywords

clustering problem on graphshot spotsLaplacian eigenvector

Mathematics Subject Classification ID

Potential theory on fractals and metric spaces (31E05) Comparison principles in context of PDEs (35B51)

Abstract: We are interested in the clustering problem on graphs: it is known that if there are two underlying clusters, then the signs of the eigenvector corresponding to the second largest eigenvalue of the adjacency matrix can reliably reconstruct the two clusters. We argue that the vertices for which the eigenvector has the largest and the smallest entries, respectively, are unusually strongly connected to their own cluster and more reliably classified than the rest. This can be regarded as a discrete version of the Hot Spots conjecture and should be useful in applications. We give a rigorous proof for the stochastic block model and several examples.

Recommendations

• Spectral clustering and the high-dimensional stochastic blockmodel
• Spectral Clustering by Recursive Partitioning
• Spectral concentration and greedy k-clustering
• A simple spectral algorithm for recovering planted partitions
• Partitioning well-clustered graphs: spectral clustering works!

Cites work

• A counterexample to the ``hot spots conjecture
• Community detection and stochastic block models: recent developments
• Entrywise eigenvector analysis of random matrices with low expected rank
• Euclidean triangles have no hot spots
• Exact Recovery in the Stochastic Block Model
• Hot spots in convex domains are in the tips (up to an inradius)
• scientific article; zbMATH DE number 4208110 (Why is no real title available?)
• scientific article; zbMATH DE number 3681933 (Why is no real title available?)
• scientific article; zbMATH DE number 6276186 (Why is no real title available?)
• scientific article; zbMATH DE number 3239038 (Why is no real title available?)
• scientific article; zbMATH DE number 3417498 (Why is no real title available?)
• scientific article; zbMATH DE number 964896 (Why is no real title available?)
• Improved Cheeger's inequality, analysis of spectral partitioning algorithms through higher order spectral gap
• Lower Bounds for the Partitioning of Graphs
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Max cut and the smallest eigenvalue
• Message-passing algorithms for synchronization problems over compact groups
• On clusterings: good, bad and spectral
• On the ``hot spots conjecture of J. Rauch
• On the diffusion geometry of graph Laplacians and applications
• On the Location of Maxima of Solutions of Schrödinger's Equation
• Proof of the achievability conjectures for the general stochastic block model
• Random Laplacian matrices and convex relaxations
• Rearrangements and convexity of level sets in PDE
• Schur reduction of trees and extremal entries of the Fiedler vector
• Spectral clustering and the high-dimensional stochastic blockmodel
• The geometry of nodal sets and outlier detection
• The hot spots problem in planar domains with on hole
• The Rotation of Eigenvectors by a Perturbation. III
• The two-to-infinity norm and singular subspace geometry with applications to high-dimensional statistics
• Uniform Bounds for Invariant Subspace Perturbations
• Wavelets on graphs via spectral graph theory

Cited in

(5)

• Regularity-based spectral clustering and mapping the Fiedler-carpet
• Boundary estimation from point clouds: algorithms, guarantees and applications
• Localization of dominant eigenpairs and planted communities by means of Frobenius inner products.
• Experimental and Efficient Algorithms
• Spectrahedral geometry of graph sparsifiers

This page was built for publication: Spectral clustering revisited: information hidden in the Fiedler vector

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2072633)