Spectral clustering under degree heterogeneity: a case for the random walk Laplacian

• URL: http://arxiv.org/abs/2105.00987v2
• Date: Tue, 4 May 2021 07:20:12 GMT
• Title: Spectral clustering under degree heterogeneity: a case for the random walk Laplacian
• Authors: Alexander Modell and Patrick Rubin-Delanchy
• Abstract summary: 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.
• Score: 83.79286663107845
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper shows that graph spectral embedding using the random walk Laplacian produces vector representations which are completely corrected for node degree. Under a generalised random dot product graph, the embedding provides uniformly consistent estimates of degree-corrected latent positions, with asymptotically Gaussian error. In the special case of a degree-corrected stochastic block model, the embedding concentrates about K distinct points, representing communities. These can be recovered perfectly, asymptotically, through a subsequent clustering step, without spherical projection, as commonly required by algorithms based on the adjacency or normalised, symmetric Laplacian matrices. While the estimand does not depend on degree, the asymptotic variance of its estimate does -- higher degree nodes are embedded more accurately than lower degree nodes. Our central limit theorem therefore suggests fitting a weighted Gaussian mixture model as the subsequent clustering step, for which we provide an expectation-maximisation algorithm.

Related papers

• Curvature-Independent Last-Iterate Convergence for Games on Riemannian Manifolds [77.4346324549323]
  We show that a step size agnostic to the curvature of the manifold achieves a curvature-independent and linear last-iterate convergence rate. To the best of our knowledge, the possibility of curvature-independent rates and/or last-iterate convergence has not been considered before.
  arXiv  Detail & Related papers  (2023-06-29T01:20:44Z)
• Convergence of Adam Under Relaxed Assumptions [72.24779199744954]
  We show that Adam converges to $epsilon$-stationary points with $O(epsilon-4)$ gradient complexity under far more realistic conditions. We also propose a variance-reduced version of Adam with an accelerated gradient complexity of $O(epsilon-3)$.
  arXiv  Detail & Related papers  (2023-04-27T06:27:37Z)
• Optimal and exact recovery on general non-uniform Hypergraph Stochastic Block Model [0.0]
  We consider the community detection problem in random hypergraphs under the non-uniform hypergraphinger block model (HSBM) We establish, for the first time in the literature, a sharp threshold for exact recovery under this non-uniform case, subject to minor constraints. We provide two efficient algorithms which successfully achieve exact recovery when above the threshold, and attain the lowest possible ratio when the exact recovery is impossible.
  arXiv  Detail & Related papers  (2023-04-25T20:30:33Z)
• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
  We consider the smooth convex-concave bilinearly-coupled saddle-point problem, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$, where one has access to first-order oracles for $F$, $G$ as well as the bilinear coupling function $H$. We present a emphaccelerated gradient-extragradient (AG-EG) descent-ascent algorithm that combines extragrad
  arXiv  Detail & Related papers  (2022-06-17T06:10:20Z)
• Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problems [98.34292831923335]
  Motivated by the problem of online correlation analysis, we propose the emphStochastic Scaled-Gradient Descent (SSD) algorithm. We bring these ideas together in an application to online correlation analysis, deriving for the first time an optimal one-time-scale algorithm with an explicit rate of local convergence to normality.
  arXiv  Detail & Related papers  (2021-12-29T18:46:52Z)
• Partial recovery and weak consistency in the non-uniform hypergraph Stochastic Block Model [6.681901523019242]
  We consider the community detection problem in random hypergraphs under the nonuniform hypergraph block model (HSBM) We provide a spectral algorithm that outputs a partition with at least a $gamma$ fraction of the vertices classified correctly, where $gammain depends on the signal-to-noise ratio (SNR) of the model. The theoretical analysis of our algorithm relies on the concentration and regularization of the adjacency matrix for non-uniform random hypergraphs, which can be of independent interest.
  arXiv  Detail & Related papers  (2021-12-22T05:38:33Z)
• Stochastic optimization with momentum: convergence, fluctuations, and traps avoidance [0.0]
  In this paper, a general optimization procedure is studied, unifying several variants of the gradient descent such as, among others, the heavy ball method, the Nesterov Accelerated Gradient (S-NAG), and the widely used Adam method. The avoidance is studied as a noisy discretization of a non-autonomous ordinary differential equation.
  arXiv  Detail & Related papers  (2020-12-07T19:14:49Z)
• Asymptotic Analysis of Conditioned Stochastic Gradient Descent [0.0]
  We investigate a class of gradient descent (SGD) algorithms, called Conditioned SGD, based on a preconditioning of the gradient direction. Almost sure convergence results, which may be of independent interest, are presented.
  arXiv  Detail & Related papers  (2020-06-04T10:08:05Z)
• On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration [115.1954841020189]
  We study the inequality and non-asymptotic properties of approximation procedures with Polyak-Ruppert averaging. We prove a central limit theorem (CLT) for the averaged iterates with fixed step size and number of iterations going to infinity.
  arXiv  Detail & Related papers  (2020-04-09T17:54:18Z)

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.