New walk extraction strategies improve node embeddings in KGs.
problem Improving node embeddings in knowledge graphs.
method Proposed five different walk extraction strategies to complement basic random walks.
result The n-gram strategy performs best on average for node classification tasks.
New method explains GNN predictions using walks.
problem GNNs are black-boxes and hard to explain.
method Nested attribution scheme using relevant walks.
result Extracts meaningful explanations from GNNs.
In this paper, we introduce a new gait segmentation method based on accelerometer data and develop a new distance function between two time series, showing novel and effectiveness in simultaneously identifying user and adversary. Comparing with the normally used Neural Network methods, our approaches use geometric feat…
Community detection has been an active research area for decades. Among all probabilistic models, Stochastic Block Model has been the most popular one. This paper introduces a novel probabilistic model: RW-HDP, based on random walks and Hierarchical Dirichlet Process, for community extraction. In RW-HDP, random walks c…
CAWs learn temporal network dynamics without node identities or edge attributes.
problem Learning temporal network dynamics without node identities or edge attributes.
method Causal Anonymous Walks (CAWs) using temporal random walks and hitting counts.
result CAW-N outperforms previous methods in predicting links over 6 real temporal networks.
Wi-Fi signals-based person identification attracts increasing attention in the booming Internet-of-Things era mainly due to its pervasiveness and passiveness. Most previous work applies gaits extracted from WiFi distortions caused by the person walking to achieve the identification. However, to extract useful gait, a p…
The paper studies pseudo-Anosov maps from typical Thurston constructions.
problem Estimating the entropy of pseudo-Anosov maps from Thurston's constructions.
method Developed a method to extract information about random walks associated with Thurston's construction.
result Random walks eventually become pseudo-Anosov under certain conditions.
Enhances graph neural networks with random walks to improve performance.
problem Limited input to graph neural networks, especially for molecular data.
method Random walk data processing to enrich graph neural network input.
result Shallow network outperforms deep GNNs using only node features.
Predicting the occurrence of links is a fundamental problem in networks. In the link prediction problem we are given a snapshot of a network and would like to infer which interactions among existing members are likely to occur in the near future or which existing interactions are we missing. Although this problem has b…
The ubiquitous availability of wearable sensors is responsible for driving the Internet-of-Things but is also making an impact on sport sciences and precision medicine. While human activity recognition from smartphone data or other types of inertial measurement units (IMU) has evolved to one of the most prominent daily…
We construct a new type of quantum walks on simplicial complexes as a natural extension of the well-known Szegedy walk on graphs. One can numerically observe that our proposing quantum walks possess linear spreading and localization as in the case of the Grover walk on lattices. Moreover, our numerical simulation sugge…
This work investigates how context should be taken into account when performing continuous authentication of a smartphone user based on touchscreen and accelerometer readings extracted from swipe gestures. The study is conducted on the publicly available HMOG dataset consisting of 100 study subjects performing pre-defi…
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…
We propose and analyze two new MCMC sampling algorithms, the Vaidya walk and the John walk, for generating samples from the uniform distribution over a polytope. Both random walks are sampling algorithms derived from interior point methods. The former is based on volumetric-logarithmic barrier introduced by Vaidya wher…
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.
The paper introduces walks with jumps for modeling neuron activity in hyperbolic space.
problem Encoding neuron activity sequences in hyperbolic space.
method Introducing walks with jumps in hyperbolic geometry to model neuron activity.
result Endpoints of walks with jumps do not fully encode the sequence of jump times.
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.
Unified view on random walk and Weisfeiler-Leman kernels, improving accuracy.
problem Improving graph kernel methods for better classification accuracy.
method Define and analyze walk-based node refinement methods, relate to Weisfeiler-Leman test, and introduce new walk-based kernels.
result Walk-based kernels are as expressive as Weisfeiler-Leman subtree kernel but support non-strict neighborhood comparison.
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.
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…
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.
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.
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.
This paper shows that pairwise PageRank orders emerge from two-hop walks. The main tool used here refers to a specially designed sign-mirror function and a parameter curve, whose low-order derivative information implies pairwise PageRank orders with high probability. We study the pairwise correct rate by placing the Go…
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.
The paper finds braid representatives minimizing simple walks for knots.
problem Finding efficient braid representatives for knots.
method Developed methods to minimize the number of simple walks in braids.
result Computed the colored Jones polynomial for specific knots.
Quantum walks model financial returns with flexibility and asymmetry.
problem Accurate modeling of financial asset price dynamics.
method Discrete-time quantum walks to model asset price evolution.
result Quantum walk models can generate asymmetric return distributions and higher probabilities for extreme events.
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.
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.
Proposes a new method to describe graph vertex features using characteristic functions.
problem Describing the distribution of vertex features at multiple scales on graphs.
method Introduces FEATHER, a computationally efficient algorithm to calculate characteristic functions based on random walk transition probabilities.
result Demonstrates that the proposed method creates high-quality graph representations and is robust to data corruption.
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.
Geodesic walks converge to Brownian motion on Finsler manifolds.
problem Understanding random walks on Finsler manifolds.
method Analyzing convergence of geodesic random walks to diffusion processes.
result The Brownian motion on a Riemannian metric is a key result.
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.
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.
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.
We review statistical properties of models generated by the application of a (positive and negative order) fractional derivative operator to a standard random walk and show that the resulting stochastic walks display slowly-decaying autocorrelation functions. The relation between these correlated walks and the well-kno…
We introduce the geodesic walk for sampling Riemannian manifolds and apply it to the problem of generating uniform random points from polytopes in R^n specified by m inequalities. The walk is a discrete-time simulation of a stochastic differential equation (SDE) on the Riemannian manifold equipped with the metric induc…
Uniform drift estimates found for random walks on graph products.
problem Finding uniform lower bounds on drift for random walks on graph products.
method Extending Gouëzel's argument and introducing the combinatorial notion of piling.
result Uniform lower bounds on the drift for a family of random walks on graph products.
A quantum walk-based method for generating precise probability distributions efficiently.
problem Generating high-precision probability distributions for various applications.
method Integrates variational quantum circuits with split-step quantum walks to dynamically tune coin parameters and evolve quantum states.
result Achieves high simulation fidelity and reduces computational overhead compared to conventional methods.
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.
The study of random walks on hyperbolic spaces and Teichmüller spaces, proving central limit theorems and geodesic tracking.
problem Analyzing random walks on hyperbolic and Teichmüller spaces.
method Proving central limit theorems and geodesic tracking using finite moments and logarithmic moments.
result Translation lengths of random isometries satisfy a central limit theorem if and only if the random walk has finite second moment.
We extend some properties of random walks on hyperbolic groups to random walks on convergence groups. In particular we prove that if a convergence group G acts on a compact metrizable space M with the convergence property then we can provide G∪M with a compact topology such that random walks on G converge a…
For any pseudo-Anosov diffeomorphism on a closed orientable surface S of genus greater than one, it is known by the work of Bers and Thurston that the topological entropy agrees with the translation distance on the Teichmüller space with respect to the Teichmüller metric. In this paper, we consider random walks on th…