A Performance Guarantee for Spectral Clustering
- URL: http://arxiv.org/abs/2007.05627v1
- Date: Fri, 10 Jul 2020 22:03:43 GMT
- Title: A Performance Guarantee for Spectral Clustering
- Authors: March Boedihardjo, Shaofeng Deng, Thomas Strohmer
- Abstract summary: We study the central question: when is spectral clustering able to find the global solution to the minimum ratio cut problem?
We develop a deterministic two-to-infinity norm bound for the the invariant subspace of the graph Laplacian that corresponds to the $k$ smallest eigenvalues.
By combining these two results we give a condition under which spectral clustering is guaranteed to output the global solution to the minimum ratio cut problem.
- Score: 0.6445605125467572
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The two-step spectral clustering method, which consists of the Laplacian
eigenmap and a rounding step, is a widely used method for graph partitioning.
It can be seen as a natural relaxation to the NP-hard minimum ratio cut
problem. In this paper we study the central question: when is spectral
clustering able to find the global solution to the minimum ratio cut problem?
First we provide a condition that naturally depends on the intra- and
inter-cluster connectivities of a given partition under which we may certify
that this partition is the solution to the minimum ratio cut problem. Then we
develop a deterministic two-to-infinity norm perturbation bound for the the
invariant subspace of the graph Laplacian that corresponds to the $k$ smallest
eigenvalues. Finally by combining these two results we give a condition under
which spectral clustering is guaranteed to output the global solution to the
minimum ratio cut problem, which serves as a performance guarantee for spectral
clustering.
Related papers
- Graph Cuts with Arbitrary Size Constraints Through Optimal Transport [18.338458637795263]
We propose a new graph cut algorithm for partitioning graphs under arbitrary size constraints.
We solve it using an accelerated proximal GD algorithm which guarantees global convergence to a critical point.
arXiv Detail & Related papers (2024-02-07T10:33:09Z) - MeanCut: A Greedy-Optimized Graph Clustering via Path-based Similarity
and Degree Descent Criterion [0.6906005491572401]
spectral clustering is popular and attractive due to the remarkable performance, easy implementation, and strong adaptability.
We propose MeanCut as the objective function and greedily optimize it in degree descending order for a nondestructive graph partition.
The validity of our algorithm is demonstrated by testifying on real-world benchmarks and application of face recognition.
arXiv Detail & Related papers (2023-12-07T06:19:39Z) - Discretize Relaxed Solution of Spectral Clustering via a Non-Heuristic
Algorithm [77.53604156112144]
We develop a first-order term to bridge the original problem and discretization algorithm.
Since the non-heuristic method is aware of the original graph cut problem, the final discrete solution is more reliable.
arXiv Detail & Related papers (2023-10-19T13:57:38Z) - Spectral Normalized-Cut Graph Partitioning with Fairness Constraints [18.835004555146575]
Normalized-cut graph partitioning aims to divide the set of nodes in a graph into $k$ disjoint clusters to minimize the fraction of the total edges between any cluster and all other clusters.
We consider a fair variant of the partitioning problem wherein nodes are characterized by a categorical sensitive attribute indicating membership to different demographic groups.
Our goal is to ensure that each group is approximately proportionally represented in each cluster while minimizing the normalized cut value.
arXiv Detail & Related papers (2023-07-22T12:20:46Z) - Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [79.46465138631592]
We devise an efficient algorithm that recovers clusters using the observed labels.
We present Instance-Adaptive Clustering (IAC), the first algorithm whose performance matches these lower bounds both in expectation and with high probability.
arXiv Detail & Related papers (2023-06-18T08:46:06Z) - One-step Bipartite Graph Cut: A Normalized Formulation and Its
Application to Scalable Subspace Clustering [56.81492360414741]
We show how to enforce a one-step normalized cut for bipartite graphs, especially with linear-time complexity.
In this paper, we first characterize a novel one-step bipartite graph cut criterion with normalized constraints, and theoretically prove its equivalence to a trace problem.
We extend this cut criterion to a scalable subspace clustering approach, where adaptive anchor learning, bipartite graph learning, and one-step normalized bipartite graph partitioning are simultaneously modeled.
arXiv Detail & Related papers (2023-05-12T11:27:20Z) - Perfect Spectral Clustering with Discrete Covariates [68.8204255655161]
We propose a spectral algorithm that achieves perfect clustering with high probability on a class of large, sparse networks.
Our method is the first to offer a guarantee of consistent latent structure recovery using spectral clustering.
arXiv Detail & Related papers (2022-05-17T01:41:06Z) - Average Sensitivity of Spectral Clustering [31.283432482502278]
We study the stability of spectral clustering against edge perturbations in the input graph.
Our results suggest that spectral clustering is stable against edge perturbations when there is a cluster structure in the input graph.
arXiv Detail & Related papers (2020-06-07T09:14:44Z) - Computationally efficient sparse clustering [67.95910835079825]
We provide a finite sample analysis of a new clustering algorithm based on PCA.
We show that it achieves the minimax optimal misclustering rate in the regime $|theta infty$.
arXiv Detail & Related papers (2020-05-21T17:51:30Z) - Local Graph Clustering with Network Lasso [90.66817876491052]
We study the statistical and computational properties of a network Lasso method for local graph clustering.
The clusters delivered by nLasso can be characterized elegantly via network flows between cluster boundary and seed nodes.
arXiv Detail & Related papers (2020-04-25T17:52:05Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.