Improved Analysis of Spectral Algorithm for Clustering

2019-12-06 · Tomohiko Mizutani

Spectral algorithms are graph partitioning algorithms that partition a node set of a graph into groups by using a spectral embedding map. Clustering techniques based on the algorithms are referred to as spectral clustering and are widely used in data analysis. To gain a better understanding of why spectral clustering is successful, Peng et al. (2015) and Kolev and Mehlhorn (2016) studied the behavior of a certain type of spectral algorithm for a class of graphs, called well-clustered graphs. Specifically, they put an assumption on graphs and showed the performance guarantee of the spectral algorithm under it. The algorithm they studied used the spectral embedding map developed by Shi and Malic (2000). In this paper, we improve on their results, giving a better performance guarantee under a weaker assumption. We also evaluate the performance of the spectral algorithm with the spectral embedding map developed by Ng et al. (2001).

📄 PDF Abstract BibTeX arXiv:1912.02997

Code (0)

등록된 구현이 없습니다.

Tasks

Clusteringgraph partitioning

Methods 이 논문이 사용한 방법론

Spectral Clustering Spectral clustering has attracted increasing attention due to the promising ability in dealing with nonlinearly separable datasets [15], [16]. In spectral clustering, the…

Clustering Mixtures of Discrete Distributions: A Note on Mitra's Algorithm

2024-05-29 · Mohamed Seif, Yanxi Chen

In this note, we provide a refined analysis of Mitra's algorithm \cite{mitra2008clustering} for classifying general discrete mixture distribution models. Built upon spectral clustering \cite{mcsherry2001spectral}, this a…

Clustering

An improved spectral clustering method for community detection under the degree-corrected stochastic blockmodel

2020-11-12 · Huan Qing, Jingli Wang

For community detection problem, spectral clustering is a widely used method for detecting clusters in networks. In this paper, we propose an improved spectral clustering (ISC) approach under the degree corrected stochas…

Clustering Community Detection Stochastic Block Model

An Improved and Generalised Analysis for Spectral Clustering

2025-11-28 · George Tyler, Luca Zanetti arxiv

We revisit the theoretical performances of Spectral Clustering, a classical algorithm for graph partitioning that relies on the eigenvectors of a matrix representation of the graph. Informally, we show that Spectral Clus…

graph partitioning

Consistent Spectral Clustering in Hyperbolic Spaces

2024-09-14 · Sagar Ghosh, Swagatam Das

Clustering, as an unsupervised technique, plays a pivotal role in various data analysis applications. Among clustering algorithms, Spectral Clustering on Euclidean Spaces has been extensively studied. However, with the r…

Clustering

Spectral Modification of Graphs for Improved Spectral Clustering

2019-12-01 · NeurIPS 2019 12 · Ioannis Koutis, Huong Le

Spectral clustering algorithms provide approximate solutions to hard optimization problems that formulate graph partitioning in terms of the graph conductance. It is well understood that the quality of these approxima…

Clustering graph partitioning