Spectral Clustering via Orthogonalization-Free Methods
- URL: http://arxiv.org/abs/2305.10356v1
- Date: Tue, 16 May 2023 16:01:12 GMT
- Title: Spectral Clustering via Orthogonalization-Free Methods
- Authors: Qiyuan Pang and Haizhao Yang
- Abstract summary: Graph Signal Filter used as dimensionality reduction in spectral clustering usually requires expensive eigenvalue estimation.
We propose to use four orthogonalization-free methods by optimizing objective functions as dimensionality reduction in spectral clustering.
We numerically hypothesize that the proposed methods are equivalent in clustering quality to the ideal Graph Signal Filter.
- Score: 2.995087247817663
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Graph Signal Filter used as dimensionality reduction in spectral clustering
usually requires expensive eigenvalue estimation. We analyze the filter in an
optimization setting and propose to use four orthogonalization-free methods by
optimizing objective functions as dimensionality reduction in spectral
clustering. The proposed methods do not utilize any orthogonalization, which is
known as not well scalable in a parallel computing environment. Our methods
theoretically construct adequate feature space, which is, at most, a weighted
alteration to the eigenspace of a normalized Laplacian matrix. We numerically
hypothesize that the proposed methods are equivalent in clustering quality to
the ideal Graph Signal Filter, which exploits the exact eigenvalue needed
without expensive eigenvalue estimation. Numerical results show that the
proposed methods outperform Power Iteration-based methods and Graph Signal
Filter in clustering quality and computation cost. Unlike Power Iteration-based
methods and Graph Signal Filter which require random signal input, our methods
are able to utilize available initialization in the streaming graph scenarios.
Additionally, numerical results show that our methods outperform ARPACK and are
faster than LOBPCG in the streaming graph scenarios. We also present numerical
results showing the scalability of our methods in multithreading and
multiprocessing implementations to facilitate parallel spectral clustering.
Related papers
- Closed-form Filtering for Non-linear Systems [83.91296397912218]
We propose a new class of filters based on Gaussian PSD Models, which offer several advantages in terms of density approximation and computational efficiency.
We show that filtering can be efficiently performed in closed form when transitions and observations are Gaussian PSD Models.
Our proposed estimator enjoys strong theoretical guarantees, with estimation error that depends on the quality of the approximation and is adaptive to the regularity of the transition probabilities.
arXiv Detail & Related papers (2024-02-15T08:51:49Z) - 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) - Adaptive Graph Convolutional Subspace Clustering [10.766537212211217]
Spectral-type subspace clustering algorithms have shown excellent performance in many subspace clustering applications.
In this paper, inspired by graph convolutional networks, we use the graph convolution technique to develop a feature extraction method and a coefficient matrix constraint simultaneously.
We claim that by using AGCSC, the aggregated feature representation of original data samples is suitable for subspace clustering.
arXiv Detail & Related papers (2023-05-05T10:27:23Z) - A Distributed Block Chebyshev-Davidson Algorithm for Parallel Spectral
Clustering [7.632758664232665]
We develop a distributed Block Chebyshev-Davidson algorithm to solve large-scale leading eigenvalue problems for spectral analysis in spectral clustering.
The efficiency of the Chebyshev-Davidson algorithm relies on the prior knowledge of the eigenvalue spectrum, which could be expensive to estimate.
A distributed and parallel version has been developed with attractive scalability.
arXiv Detail & Related papers (2022-12-08T18:06:13Z) - Computational Doob's h-transforms for Online Filtering of Discretely
Observed Diffusions [65.74069050283998]
We propose a computational framework to approximate Doob's $h$-transforms.
The proposed approach can be orders of magnitude more efficient than state-of-the-art particle filters.
arXiv Detail & Related papers (2022-06-07T15:03:05Z) - An application of the splitting-up method for the computation of a
neural network representation for the solution for the filtering equations [68.8204255655161]
Filtering equations play a central role in many real-life applications, including numerical weather prediction, finance and engineering.
One of the classical approaches to approximate the solution of the filtering equations is to use a PDE inspired method, called the splitting-up method.
We combine this method with a neural network representation to produce an approximation of the unnormalised conditional distribution of the signal process.
arXiv Detail & Related papers (2022-01-10T11:01:36Z) - Sparse Quadratic Optimisation over the Stiefel Manifold with Application
to Permutation Synchronisation [71.27989298860481]
We address the non- optimisation problem of finding a matrix on the Stiefel manifold that maximises a quadratic objective function.
We propose a simple yet effective sparsity-promoting algorithm for finding the dominant eigenspace matrix.
arXiv Detail & Related papers (2021-09-30T19:17:35Z) - A Manifold Proximal Linear Method for Sparse Spectral Clustering with
Application to Single-Cell RNA Sequencing Data Analysis [9.643152256249884]
This paper considers the widely adopted SSC model as an optimization model with nonsmooth and non objective.
We propose a new method (ManPL) that solves the original SSC problem.
Results of the proposed methods are established.
arXiv Detail & Related papers (2020-07-18T22:05:00Z) - Scalable Spectral Clustering with Nystrom Approximation: Practical and
Theoretical Aspects [1.6752182911522515]
This work presents a principled spectral clustering algorithm that exploits spectral properties of the similarity matrix associated with sampled points to regulate accuracy-efficiency trade-offs.
The overarching goal of this work is to provide an improved baseline for future research directions to accelerate spectral clustering.
arXiv Detail & Related papers (2020-06-25T15:10:56Z) - 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) - Optimization of Graph Total Variation via Active-Set-based Combinatorial
Reconditioning [48.42916680063503]
We propose a novel adaptive preconditioning strategy for proximal algorithms on this problem class.
We show that nested-forest decomposition of the inactive edges yields a guaranteed local linear convergence rate.
Our results suggest that local convergence analysis can serve as a guideline for selecting variable metrics in proximal algorithms.
arXiv Detail & Related papers (2020-02-27T16:33:09Z)
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.