Stochastic Parallelizable Eigengap Dilation for Large Graph Clustering

• URL: http://arxiv.org/abs/2207.14589v1
• Date: Fri, 29 Jul 2022 10:13:07 GMT
• Title: Stochastic Parallelizable Eigengap Dilation for Large Graph Clustering
• Authors: Elise van der Pol, Ian Gemp, Yoram Bachrach, Richard Everett
• Abstract summary: We aim to identify clusters of nodes where most edges fall within clusters and only few edges fall between clusters. A core step of spectral clustering is performing an eigendecomposition of the corresponding graph Laplacian matrix. This paper introduces a parallelizable approach to dilating the spectrum in order to accelerate SVD solvers and in turn, spectral clustering.
• Score: 12.544602297450533
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Large graphs commonly appear in social networks, knowledge graphs, recommender systems, life sciences, and decision making problems. Summarizing large graphs by their high level properties is helpful in solving problems in these settings. In spectral clustering, we aim to identify clusters of nodes where most edges fall within clusters and only few edges fall between clusters. This task is important for many downstream applications and exploratory analysis. A core step of spectral clustering is performing an eigendecomposition of the corresponding graph Laplacian matrix (or equivalently, a singular value decomposition, SVD, of the incidence matrix). The convergence of iterative singular value decomposition approaches depends on the eigengaps of the spectrum of the given matrix, i.e., the difference between consecutive eigenvalues. For a graph Laplacian corresponding to a well-clustered graph, the eigenvalues will be non-negative but very small (much less than $1$) slowing convergence. This paper introduces a parallelizable approach to dilating the spectrum in order to accelerate SVD solvers and in turn, spectral clustering. This is accomplished via polynomial approximations to matrix operations that favorably transform the spectrum of a matrix without changing its eigenvectors. Experiments demonstrate that this approach significantly accelerates convergence, and we explain how this transformation can be parallelized and stochastically approximated to scale with available compute.

Related papers

• Learning Sparse High-Dimensional Matrix-Valued Graphical Models From Dependent Data [12.94486861344922]
  We consider the problem of inferring the conditional independence graph (CIG) of a sparse, high-dimensional, stationary matrix- Gaussian time series. We consider a sparse-based formulation of the problem with a Kronecker-decomposable power spectral density (PSD) We illustrate our approach using numerical examples utilizing both synthetic and real data.
  arXiv  Detail & Related papers  (2024-04-29T19:32:50Z)
• Graph Generation via Spectral Diffusion [51.60814773299899]
  We present GRASP, a novel graph generative model based on 1) the spectral decomposition of the graph Laplacian matrix and 2) a diffusion process. Specifically, we propose to use a denoising model to sample eigenvectors and eigenvalues from which we can reconstruct the graph Laplacian and adjacency matrix. Our permutation invariant model can also handle node features by concatenating them to the eigenvectors of each node.
  arXiv  Detail & Related papers  (2024-02-29T09:26:46Z)
• Spectral Clustering via Orthogonalization-Free Methods [6.460951804337735]
  We propose four orthogonalization-free methods for spectral clustering. In theory, two methods converge to features isomorphic to the eigenvectors corresponding to the smallest eigenvalues of the symmetric normalized Laplacian. Numerical results are provided to demonstrate the scalability of our methods.
  arXiv  Detail & Related papers  (2023-05-16T16:01:12Z)
• 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)
• Learning Graphical Factor Models with Riemannian Optimization [70.13748170371889]
  This paper proposes a flexible algorithmic framework for graph learning under low-rank structural constraints. The problem is expressed as penalized maximum likelihood estimation of an elliptical distribution. We leverage geometries of positive definite matrices and positive semi-definite matrices of fixed rank that are well suited to elliptical models.
  arXiv  Detail & Related papers  (2022-10-21T13:19:45Z)
• Semi-Supervised Subspace Clustering via Tensor Low-Rank Representation [64.49871502193477]
  We propose a novel semi-supervised subspace clustering method, which is able to simultaneously augment the initial supervisory information and construct a discriminative affinity matrix. Comprehensive experimental results on six commonly-used benchmark datasets demonstrate the superiority of our method over state-of-the-art methods.
  arXiv  Detail & Related papers  (2022-05-21T01:47:17Z)
• 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)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  This paper shows that graph spectral embedding using the random walk Laplacian produces vector representations which are completely corrected for node degree. In the special case of a degree-corrected block model, the embedding concentrates about K distinct points, representing communities.
  arXiv  Detail & Related papers  (2021-05-03T16:36:27Z)
• 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)
• Spectral Learning on Matrices and Tensors [74.88243719463053]
  We show that tensor decomposition can pick up latent effects that are missed by matrix methods. We also outline computational techniques to design efficient tensor decomposition methods.
  arXiv  Detail & Related papers  (2020-04-16T22:53:00Z)
• Approximate Graph Spectral Decomposition with the Variational Quantum Eigensolver [1.0152838128195465]
  Spectral graph theory studies the relationships between the eigenvectors and eigenvalues of Laplacian and adjacency matrices and their associated graphs. The Variational Quantum Eigensolver (VQE) algorithm was proposed as a hybrid quantum/classical algorithm. In this paper, we will expand upon the VQE algorithm to analyze the spectra of directed and undirected graphs.
  arXiv  Detail & Related papers  (2019-12-27T23:27:38Z)

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.