Random walks on cell complexes link to Laplacians and Novikov-Shubin invariants.
problem Computing Novikov-Shubin invariants for complex cell structures.
method Construct random walks on cell complexes, relate to Laplacians, and use return probabilities.
result Novikov-Shubin invariants can be recovered from random walk return probabilities.
New method clusters hypergraphs using weighted random walks and Laplacians.
problem Clustering hypergraph data with edge-dependent weights.
method Random walks with edge-dependent vertex weights, constructing hypergraph Laplacians for clustering.
result Proposed methods outperform existing hypergraph clustering algorithms.
Study uniform convergence of random walk Laplacians to diffusion Laplacian on smooth manifolds.
problem Uniform convergence of random walk Laplacians to diffusion Laplacian on smooth manifolds.
method Analysis of random walks on geometric and directed kNN graphs, using concentration tools and differential geometry.
result Uniform convergence of kNN Laplacians to diffusion Laplacian, without continuity of transition kernel. The paper corrects for node degree in spectral clustering using random walk Laplacian.
problem Node degree heterogeneity in spectral clustering.
method Graph spectral embedding using the random walk Laplacian.
result The embedding provides uniformly consistent estimates of degree-corrected latent positions.
This paper considers a classical question of approximation of Brownian motion by a random walk in the setting of a sub-Riemannian manifold M. To construct such a random walk we first address several issues related to the degeneracy of such a manifold. In particular, we define a family of sub-Laplacian operators natur…
Hypergraphs are used in machine learning to model higher-order relationships in data. While spectral methods for graphs are well-established, spectral theory for hypergraphs remains an active area of research. In this paper, we use random walks to develop a spectral theory for hypergraphs with edge-dependent vertex wei…
Invariance principle proved for lifted geodesic walks on Riemannian submersions.
problem Proving convergence to horizontal Brownian motion for lifted geodesic walks.
method Appropriate conditions on geodesic random walks' speed; proving invariance principle.
result Convergence to horizontal Brownian motion for lifted geodesic walks.
Discrete time random walks on a finite set naturally translate via a one-to-one correspondence to discrete Laplace operators. Typically, Ollivier curvature has been investigated via random walks. We first extend the definition of Ollivier curvature to general weighted graphs and then give a strikingly simple representa…
We relate some basic constructions of stochastic analysis to differential geometry, via random walk approximations. We consider walks on both Riemannian and sub-Riemannian manifolds in which the steps consist of travel along either geodesics or integral curves associated to orthonormal frames, and we give particular at…
A new method improves graph random features with quasi-Monte Carlo techniques.
problem Improving the accuracy of graph random features.
method Induces negative correlations in random walks using antithetic termination.
result Strong theoretical guarantees on lower-variance estimators of the Laplacian kernel.
On a sub-Riemannian manifold we define two type of Laplacians. The \emph{macroscopic Laplacian} Δω, as the divergence of the horizontal gradient, once a volume ω is fixed, and the \emph{microscopic Laplacian}, as the operator associated with a sequence of geodesic random walks. We consider a general class of rando…
Protein function prediction is the important problem in modern biology. In this paper, the un-normalized, symmetric normalized, and random walk graph Laplacian based semi-supervised learning methods will be applied to the integrated network combined from multiple networks to predict the functions of all yeast proteins …
Paper extends tail bounds to high-dimensional random objects on Riemannian manifolds.
problem Need for tail bounds in high-dimensional data.
method Random walks on graph approximating the manifold, ensuring spectral similarity.
result Derived tensor Chernoff bound for Riemannian manifolds.
Convolution operations designed for graph-structured data usually utilize the graph Laplacian, which can be seen as message passing between the adjacent neighbors through a generic random walk. In this paper, we propose PAN, a new graph convolution framework that involves every path linking the message sender and recei…
Universal inequalities for Laplacian eigenvalues on discrete groups.
problem Proving inequalities for Laplacian eigenvalues on discrete groups.
method Analyzing Laplacian eigenvalues with Dirichlet boundary conditions on subsets of discrete groups.
result Yang-type universal inequalities for Cayley graphs of amenable groups and the d-regular tree.
The paper proves Lipschitz regularity of graph Laplacian eigenvectors on random data clouds.
problem Analyzing the regularity of solutions to graph Laplacian equations on random data points.
method Probabilistic coupling of random walks and interpolation method for point clouds to continuum.
result Graph Laplacian eigenvectors are essentially Lipschitz with constants depending on eigenvalues.
Study shows rates for Laplacian-eigenmap methods in nonparametric regression.
problem Minimizing error in nonparametric regression using Laplacian-eigenmap.
method Adaptive and non-adaptive minimax rates using Sobolev space constraints.
result Extends minimax rates to various weighted Laplacian matrices.
New graph embedding method improves link prediction and node classification.
problem Improving graph embedding methods for better node representation.
method Spectral-biased random walks with neighborhood similarity bias.
result Significantly improves link prediction and node classification.
To detect the irregular trade behaviors in the stock market is the important problem in machine learning field. These irregular trade behaviors are obviously illegal. To detect these irregular trade behaviors in the stock market, data scientists normally employ the supervised learning techniques. In this paper, we empl…
Survey of Laplacian-based methods for data dimensionality reduction and embedding.
problem Efficiently reducing high-dimensional data to lower dimensions while preserving important features and structures.
method Laplacian-based methods including spectral clustering, Laplacian eigenmap, locality preserving projection, graph embedding, and diffusion map.
result Comprehensive overview of various optimization variants and applications of Laplacian-based techniques.
This paper investigates the behavior of the Min-Sum message passing scheme to solve systems of linear equations in the Laplacian matrices of graphs and to compute electric flows. Voltage and flow problems involve the minimization of quadratic functions and are fundamental primitives that arise in several domains. Algor…
Spectral clustering is widely used to partition graphs into distinct modules or communities. Existing methods for spectral clustering use the eigenvalues and eigenvectors of the graph Laplacian, an operator that is closely associated with random walks on graphs. We propose a new spectral partitioning method that exploi…
We study the problem of finding the maximum of a function defined on the nodes of a connected graph. The goal is to identify a node where the function obtains its maximum. We focus on local iterative algorithms, which traverse the nodes of the graph along a path, and the next iterate is chosen from the neighbors of the…
Treebolic space HT(q,p) is a key example of a strip complex in the sense of Bendikov, Saloff-Coste, Salvatori, and Woess [Adv. Math. 226 (2011), 992-1055]. It is an analog of the Sol geometry, namely, it is a horocylic product of the hyperbolic upper half plane with a "stretching" parameter q and the homogeneous tree T…
Study shows how Laplacian semi-supervised learning behaves at low labeling rates.
problem Understanding behavior of Laplacian semi-supervised learning at very low label rates.
method Analysis of random geometric graphs and Γ-convergence tools. result For certain conditions, Laplacian learning becomes degenerate and spikes form; for others, it remains well-posed and consistent.
Study large deviations in random walks on Lie groups.
problem Large deviations in sub-Riemannian random walks.
method Prove large deviation principle for random walks on stratified Lie groups.
result Proved a large deviation principle with a rate function adapted to sub-Riemannian geometry.
We review recent advances on the record statistics of strongly correlated time series, whose entries denote the positions of a random walk or a Lévy flight on a line. After a brief survey of the theory of records for independent and identically distributed random variables, we focus on random walks. During the last few…
This paper presents VEC-NBT, a variation on the unsupervised graph clustering technique VEC, which improves upon the performance of the original algorithm significantly for sparse graphs. VEC employs a novel application of the state-of-the-art word2vec model to embed a graph in Euclidean space via random walks on the n…
Quantum walks blend patterns into splines when averaged.
problem Understanding the asymptotic patterns of quantum random walks.
method Averaging over quantum coins using the Haar measure.
result Patterns blend into splines, showing a unified behavior.
New method clusters directed and undirected graphs without losing directional information.
problem Clustering directed graphs due to asymmetry in edge connectivity.
method Generalized Dirichlet Energy (GDE) and generalized spectral clustering (GSC).
result GSC outperforms existing methods in clustering accuracy and robustness.
Neumann eigenmaps improve landmark-based diffusion map embeddings.
problem Landmark-based diffusion map embeddings can be computationally inefficient and unstable.
method NeuMaps use a renormalized Neumann Laplacian for eigendecomposition, incorporating landmarks as a subgraph.
result NeuMaps offer a computationally efficient and stable embedding method.
Local limit theorem for random walks on hyperbolic groups with parabolic subgroups.
problem Analyzing the behavior of random walks on relatively hyperbolic groups.
method Study of convergent random walks with finite derivative of Green function at spectral radius.
result Proves a local limit theorem for the probability of returning to the origin.
Study diffusions and random walks on hyperbolic spaces, focusing on their Martin boundaries.
problem Understanding diffusions and random walks on hyperbolic spaces.
method Analyzing specific diffusions and random walks on hyperbolic spaces, examining their Martin boundaries.
result Characterized the Martin boundaries of diffusions and random walks on hyperbolic spaces.
Random walks on metric spaces embed quasi-isometrically into the space.
problem Embedding random subgroups of metric spaces quasi-isometrically.
method Analyzing random walks and contracting elements in metric spaces.
result Random subgroups of isometry groups are quasi-isometrically embedded.
This work estimates edge weights of edge-reinforced random walks using observed data.
problem Statistical estimation of edge weights in edge-reinforced random walks.
method Proposes an estimator based on the generalized method of moments using the magic formula and hyperbolic Gaussian structure.
result Analyzes the sample complexity of the proposed estimator.
New proof shows rapid mixing for random walks on nilmanifolds.
problem Proving rapid mixing for random walks on nilmanifolds.
method Proved rapid mixing for almost all random walks generated by m translations on nilmanifolds under mild assumptions.
result For several classical classes of nilmanifolds, m=2 suffices for rapid mixing.
Random walks on hyperbolic spaces show linear growth in translation lengths.
problem Investigate the growth of translation lengths in random walks on hyperbolic spaces.
method Prove linear growth without moment conditions and apply to Teichmüller spaces.
result Linear growth of translation lengths in random walks on hyperbolic spaces.
Discrete Green's functions are the inverses or pseudo-inverses of combinatorial Laplacians. We present compact formulas for discrete Green's functions, in terms of the eigensystems of corresponding Laplacians, for products of regular graphs with or without boundary. Explicit formulas are derived for the cycle, torus, a…
Study random walks on groups with superlinear divergent geodesics.
problem Existence of superlinear divergent geodesics in groups.
method Developed theory of superlinear divergence and applied Gouëzel's pivoting technique.
result Established a central limit theorem for random walks on groups with superlinear divergent geodesics.
Study random walks on sub-Riemannian manifolds using retractions.
problem Modeling random walks on sub-Riemannian manifolds.
method Use retractions to approximate normal geodesics and study convergence to Brownian motion.
result Convergence of geodesic random walks defined with different connections.
The paper proves spectral convergence rates for graph Laplacian to manifold Laplace-Beltrami operator.
problem Spectral convergence of graph Laplacian to manifold Laplace-Beltrami operator.
method Analysis of Dirichlet form convergence and construction of approximate eigenfunctions via manifold heat kernel.
result Proves spectral convergence rates for Gaussian kernelized graph Laplacian.
In this paper we study the common distance between points and the behavior of a constant length step discrete random walk on finite area hyperbolic surfaces. We show that if the second smallest eigenvalue of the Laplacian is at least 1/4, then the distances on the surface are highly concentrated around the minimal poss…
The paper examines random walks on metric spaces and finds commensurable subgroups.
problem Determining commensurable subgroups via stationary measures in metric spaces.
method Analyzing random walks on isometry groups of metric spaces with non-singular stationary measures.
result Subgroups generated by random walks are commensurable under mild conditions.
Random walks on free groups reveal asymmetric expansion factors.
problem Understanding expansion factors in free groups.
method Random walks and BGIP on metric spaces.
result Generic outer automorphisms have different forward and backward expansion factors.
Survey on random walks on mapping class groups and their properties.
problem Understanding random walks on mapping class groups.
method Analyzing actions on Teichmüller spaces and curve complexes.
result Laws of large numbers and central limit theorems for random walks.
Deviation inequalities and limit laws for random walks on metric spaces.
problem Understanding random walks on metric spaces with contracting isometries.
method Adapting Gouëzel's pivotal time construction to establish deviation inequalities.
result Exponential bounds and limit laws for random walks on mapping class groups and CAT(0) spaces.
Random walks on Fuchsian Schottky groups have harmonic measures with lower dimension.
problem Understanding the dimensionality of harmonic measures for random walks.
method Analyzing finite range random walks on Fuchsian Schottky groups.
result Harmonic measures have dimension strictly less than the limit set's Hausdorff dimension.
UniNet efficiently learns network representations from large graphs.
problem Efficiently learning network representations from large graphs.
method Metropolis-Hastings sampling for efficient edge sampling and random walk model abstraction.
result UniNet outperforms existing NRL models on billion-edge networks.