Spectral Clustering Revisited: Information Hidden in the Fiedler Vector
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.
Code (0)
등록된 구현이 없습니다.
Tasks
ClusteringStochastic Block ModelSimilar Papers 제목 키워드 기반
Semi-supervised Spectral Clustering for Classification
We propose a Classification Via Clustering (CVC) algorithm which enables existing clustering methods to be efficiently employed in classification problems. In CVC, training and test data are co-clustered and class-cluste…
ClassificationClusteringGeneral ClassificationA Min-max Cult Algorithm for Graph Partitioning and Data Clustering
An important application of graph partitioning is data clustering using a graph model - the pairwise similarities between all data objects form a weighted graph adjacency matrix that contains all necessary information fo…
Clusteringgraph partitioningSpectral Gap Regularization of Neural Networks
We introduce Fiedler regularization, a novel approach for regularizing neural networks that utilizes spectral/graphical information. Existing regularization methods often focus on penalizing weights in a global/uniform m…
When Slepian Meets Fiedler: Putting a Focus on the Graph Spectrum
The study of complex systems benefits from graph models and their analysis. In particular, the eigendecomposition of the graph Laplacian lets emerge properties of global organization from local interactions; e.g., the Fi…
ClusteringGraph ClusteringOn spectral partitioning of signed graphs
We argue that the standard graph Laplacian is preferable for spectral partitioning of signed graphs compared to the signed Laplacian. Simple examples demonstrate that partitioning based on signs of components of the lead…