Spectral clustering revisited: information hidden in the Fiedler vector

DOI10.3934/FODS.2021015zbMATH Open1483.31038arXiv2003.09969OpenAlexW3176060348MaRDI QIDQ2072633FDOQ2072633

Authors: Adela DePavia, Stefan Steinerberger 

Publication date: 26 January 2022

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

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.

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

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!

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)

Cites Work

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

Cited In (4)

• 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
• Experimental and Efficient Algorithms

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)