Average Sensitivity of Spectral Clustering

2020-06-07 · Pan Peng, Yuichi Yoshida

Spectral clustering is one of the most popular clustering methods for finding clusters in a graph, which has found many applications in data mining. However, the input graph in those applications may have many missing edges due to error in measurement, withholding for a privacy reason, or arbitrariness in data conversion. To make reliable and efficient decisions based on spectral clustering, we assess the stability of spectral clustering against edge perturbations in the input graph using the notion of average sensitivity, which is the expected size of the symmetric difference of the output clusters before and after we randomly remove edges. We first prove that the average sensitivity of spectral clustering is proportional to $\lambda_2/\lambda_3^2$, where $\lambda_i$ is the $i$-th smallest eigenvalue of the (normalized) Laplacian. We also prove an analogous bound for $k$-way spectral clustering, which partitions the graph into $k$ clusters. Then, we empirically confirm our theoretical bounds by conducting experiments on synthetic and real networks. Our results suggest that spectral clustering is stable against edge perturbations when there is a cluster structure in the input graph.

📄 PDF Abstract BibTeX arXiv:2006.04094

Code (0)

등록된 구현이 없습니다.

Tasks

ClusteringSensitivity

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…

Average Sensitivity of Hierarchical $k$-Median Clustering

2025-07-14 · Shijie Li, Weiqiang He, Ruobing Bai, Pan Peng arxiv

Hierarchical clustering is a widely used method for unsupervised learning with numerous applications. However, in the application of modern algorithms, the datasets studied are usually large and dynamic. If the hierarchi…

Understanding Regularized Spectral Clustering via Graph Conductance

2018-06-05 · NeurIPS 2018 12 · Yilin Zhang, Karl Rohe

This paper uses the relationship between graph conductance and spectral clustering to study (i) the failures of spectral clustering and (ii) the benefits of regularization. The explanation is simple. Sparse and stochasti…

Clustering

Local and Global Optimization Techniques in Graph-Based Clustering

2018-06-01 · CVPR 2018 6 · Daiki Ikami, Toshihiko Yamasaki, Kiyoharu Aizawa

The goal of graph-based clustering is to divide a dataset into disjoint subsets with members similar to each other from an affinity (similarity) matrix between data. The most popular method of solving graph-based cluster…

Clustering global-optimization

Connecting Spectral Clustering to Maximum Margins and Level Sets

2018-12-16 · David P. Hofmeyr

We study the connections between spectral clustering and the problems of maximum margin clustering, and estimation of the components of level sets of a density function. Specifically, we obtain bounds on the eigenvectors…

Clustering

Iterative Spectral Clustering for Unsupervised Object Localization

2017-06-29 · Aditya Vora, Shanmuganathan Raman

This paper addresses the problem of unsupervised object localization in an image. Unlike previous supervised and weakly supervised algorithms that require bounding box or image level annotations for training classifiers …

Clustering Object Object Discovery Object Localization+1