Delving Into Deep Walkers: A Convergence Analysis of Random-Walk-Based Vertex Embeddings

• URL: http://arxiv.org/abs/2107.10014v1
• Date: Wed, 21 Jul 2021 11:23:04 GMT
• Title: Delving Into Deep Walkers: A Convergence Analysis of Random-Walk-Based Vertex Embeddings
• Authors: Dominik Kloepfer, Angelica I. Aviles-Rivero, Daniel Heydecker
• Abstract summary: We provide a theoretical analysis for random-walks based embeddings techniques. We prove that, under some weak assumptions, corpora converge both in the single limit of the number of random walks $N to infty$ and in the double limit of both $N$ and the length of each random walk $Ltoinfty$.
• Score: 0.7366405857677227
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph vertex embeddings based on random walks have become increasingly influential in recent years, showing good performance in several tasks as they efficiently transform a graph into a more computationally digestible format while preserving relevant information. However, the theoretical properties of such algorithms, in particular the influence of hyperparameters and of the graph structure on their convergence behaviour, have so far not been well-understood. In this work, we provide a theoretical analysis for random-walks based embeddings techniques. Firstly, we prove that, under some weak assumptions, vertex embeddings derived from random walks do indeed converge both in the single limit of the number of random walks $N \to \infty$ and in the double limit of both $N$ and the length of each random walk $L\to\infty$. Secondly, we derive concentration bounds quantifying the converge rate of the corpora for the single and double limits. Thirdly, we use these results to derive a heuristic for choosing the hyperparameters $N$ and $L$. We validate and illustrate the practical importance of our findings with a range of numerical and visual experiments on several graphs drawn from real-world applications.

Related papers

• Sensitivity of quantum walk to phase reversal and geometric perturbations: an exploration in complete graphs [0.0]
  We analyze the dynamics of quantum walks on a graph structure resulting from the integration of a main connected graph $G$ and a secondary connected graph $G'$. We explore the impact of this geometric perturbation on the success probability of quantum walk-based search algorithms.
  arXiv  Detail & Related papers  (2024-02-13T06:17:07Z)
• 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)
• Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
  We present two new classes of algorithms for efficient field integration on graphs encoding point clouds. The first class, SeparatorFactorization(SF), leverages the bounded genus of point cloud mesh graphs, while the second class, RFDiffusion(RFD), uses popular epsilon-nearest-neighbor graph representations for point clouds.
  arXiv  Detail & Related papers  (2023-02-02T08:33:36Z)
• Causal Bandits for Linear Structural Equation Models [58.2875460517691]
  This paper studies the problem of designing an optimal sequence of interventions in a causal graphical model. It is assumed that the graph's structure is known and has $N$ nodes. Two algorithms are proposed for the frequentist (UCB-based) and Bayesian settings.
  arXiv  Detail & Related papers  (2022-08-26T16:21:31Z)
• Collaborative likelihood-ratio estimation over graphs [55.98760097296213]
  Graph-based Relative Unconstrained Least-squares Importance Fitting (GRULSIF) We develop this idea in a concrete non-parametric method that we call Graph-based Relative Unconstrained Least-squares Importance Fitting (GRULSIF) We derive convergence rates for our collaborative approach that highlights the role played by variables such as the number of available observations per node, the size of the graph, and how accurately the graph structure encodes the similarity between tasks.
  arXiv  Detail & Related papers  (2022-05-28T15:37:03Z)
• Minimax Optimal Quantization of Linear Models: Information-Theoretic Limits and Efficient Algorithms [59.724977092582535]
  We consider the problem of quantizing a linear model learned from measurements. We derive an information-theoretic lower bound for the minimax risk under this setting. We show that our method and upper-bounds can be extended for two-layer ReLU neural networks.
  arXiv  Detail & Related papers  (2022-02-23T02:39:04Z)
• Inferring Hidden Structures in Random Graphs [13.031167737538881]
  We study the two inference problems of detecting and recovering an isolated community of emphgeneral structure planted in a random graph. We derive lower bounds for detecting/recovering the structure $Gamma_k$ in terms of the parameters $(n,k,q)$, as well as certain properties of $Gamma_k$, and exhibit computationally optimal algorithms that achieve these lower bounds.
  arXiv  Detail & Related papers  (2021-10-05T09:39:51Z)
• Recurrently Predicting Hypergraphs [30.092688729343678]
  A problem arises from the number of possible multi-way relationships, or hyperedges, scaling in $mathcalO(2n)$ for a set of $n$ elements. We propose a recurrent hypergraph neural network that predicts the incidence matrix by iteratively refining an initial guess of the solution.
  arXiv  Detail & Related papers  (2021-06-26T01:12:41Z)
• Intervention Efficient Algorithms for Approximate Learning of Causal Graphs [22.401163479802094]
  We study the problem of learning the causal relationships between a set of observed variables in the presence of latents. Our goal is to recover the directions of all causal or ancestral relations in $G$, via a minimum cost set of interventions. Our algorithms combine work on efficient intervention design and the design of low-cost separating set systems.
  arXiv  Detail & Related papers  (2020-12-27T17:08:46Z)
• Continuous-time quantum walks in the presence of a quadratic perturbation [55.41644538483948]
  We address the properties of continuous-time quantum walks with Hamiltonians of the form $mathcalH= L + lambda L2$. We consider cycle, complete, and star graphs because paradigmatic models with low/high connectivity and/or symmetry.
  arXiv  Detail & Related papers  (2020-05-13T14:53:36Z)
• Better Theory for SGD in the Nonconvex World [2.6397379133308214]
  Large-scale non optimization problems are ubiquitous in modern machine learning. We perform experiments on the effects of a wide array of synthetic minibatch sizes on the Gradient Descent (SG) problem.
  arXiv  Detail & Related papers  (2020-02-09T09:56:06Z)

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.