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

hot spotsLaplacian eigenvectorclustering problem on graphs

Mathematics Subject Classification ID

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

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

• 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?)
• 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)
• 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 Location of Maxima of Solutions of Schrödinger's Equation
• On the ``hot spots conjecture of J. Rauch
• On the diffusion geometry of graph Laplacians and applications
• 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 Rotation of Eigenvectors by a Perturbation. III
• The geometry of nodal sets and outlier detection
• The hot spots problem in planar domains with on hole
• 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

(4)

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

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)