Robust spectral clustering using LASSO regularization

• URL: http://arxiv.org/abs/2004.03845v1
• Date: Wed, 8 Apr 2020 07:12:56 GMT
• Title: Robust spectral clustering using LASSO regularization
• Authors: Camille Champion (IMT), Blaz\`ere M\'elanie (IMT), Burcelin R\'emy (I2MC), Loubes Jean-Michel (IMT), Risser Laurent (IMT)
• Abstract summary: This paper presents a variant of spectral clustering, called 1-spectral clustering, performed on a new random model closely related to block model. Its goal is to promote a sparse eigenbasis solution of a 1 minimization problem revealing the natural structure of the graph.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Cluster structure detection is a fundamental task for the analysis of graphs, in order to understand and to visualize their functional characteristics. Among the different cluster structure detection methods, spectral clustering is currently one of the most widely used due to its speed and simplicity. Yet, there are few theoretical guarantee to recover the underlying partitions of the graph for general models. This paper therefore presents a variant of spectral clustering, called 1-spectral clustering, performed on a new random model closely related to stochastic block model. Its goal is to promote a sparse eigenbasis solution of a 1 minimization problem revealing the natural structure of the graph. The effectiveness and the robustness to small noise perturbations of our technique is confirmed through a collection of simulated and real data examples.

Related papers

• Interpretable Multi-View Clustering Based on Anchor Graph Tensor Factorization [64.00146569922028]
  Multi-view clustering methods based on anchor graph factorization lack adequate cluster interpretability for the decomposed matrix. We address this limitation by using non-negative tensor factorization to decompose an anchor graph tensor that combines anchor graphs from multiple views.
  arXiv  Detail & Related papers  (2024-04-01T03:23:55Z)
• Latent Random Steps as Relaxations of Max-Cut, Min-Cut, and More [30.919536115917726]
  We present a probabilistic model based on non-negative matrix factorization which unifies clustering and simplification. By relaxing the hard clustering to a soft clustering, our algorithm relaxes potentially hard clustering problems to a tractable ones.
  arXiv  Detail & Related papers  (2023-08-12T02:47:57Z)
• 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)
• Learning Neural Eigenfunctions for Unsupervised Semantic Segmentation [12.91586050451152]
  Spectral clustering is a theoretically grounded solution to it where the spectral embeddings for pixels are computed to construct distinct clusters. Current approaches still suffer from inefficiencies in spectral decomposition and inflexibility in applying them to the test data. This work addresses these issues by casting spectral clustering as a parametric approach that employs neural network-based eigenfunctions to produce spectral embeddings. In practice, the neural eigenfunctions are lightweight and take the features from pre-trained models as inputs, improving training efficiency and unleashing the potential of pre-trained models for dense prediction.
  arXiv  Detail & Related papers  (2023-04-06T03:14:15Z)
• Unified Multi-View Orthonormal Non-Negative Graph Based Clustering Framework [74.25493157757943]
  We formulate a novel clustering model, which exploits the non-negative feature property and incorporates the multi-view information into a unified joint learning framework. We also explore, for the first time, the multi-model non-negative graph-based approach to clustering data based on deep features.
  arXiv  Detail & Related papers  (2022-11-03T08:18:27Z)
• flow-based clustering and spectral clustering: a comparison [0.688204255655161]
  We study a novel graph clustering method for data with an intrinsic network structure. We exploit an intrinsic network structure of data to construct Euclidean feature vectors. Our results indicate that our clustering methods can cope with certain graph structures.
  arXiv  Detail & Related papers  (2022-06-20T21:49:52Z)
• 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)
• Improving Spectral Clustering Using Spectrum-Preserving Node Reduction [1.52292571922932]
  We use spectrum-preserving node reduction to accelerate eigen-decomposition and generate concise representations of data sets. The experimental results show dramatically improved clustering performance when compared with state-of-the-art methods.
  arXiv  Detail & Related papers  (2021-10-24T01:43:12Z)
• Structured Graph Learning for Clustering and Semi-supervised Classification [74.35376212789132]
  We propose a graph learning framework to preserve both the local and global structure of data. Our method uses the self-expressiveness of samples to capture the global structure and adaptive neighbor approach to respect the local structure. Our model is equivalent to a combination of kernel k-means and k-means methods under certain condition.
  arXiv  Detail & Related papers  (2020-08-31T08:41:20Z)
• 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)
• Strong Consistency, Graph Laplacians, and the Stochastic Block Model [1.2891210250935143]
  We study the performance of classical two-step spectral clustering via the graph Laplacian to learn the block model. We prove that spectral clustering is able to achieve exact recovery of the planted community structure under conditions that match the information-theoretic limits.
  arXiv  Detail & Related papers  (2020-04-21T07:16:46Z)

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.