arXiv research

Random walks on cell complexes link to Laplacians and Novikov-Shubin invariants.

New method clusters hypergraphs using weighted random walks and Laplacians.

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…

The paper corrects for node degree in spectral clustering using random walk Laplacian.

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…

Study uniform convergence of random walk Laplacians to diffusion Laplacian on smooth manifolds.

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.

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…

Study shows rates for Laplacian-eigenmap methods in nonparametric regression.

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 …

Survey of Laplacian-based methods for data dimensionality reduction and embedding.

Universal inequalities for Laplacian eigenvalues on discrete groups.

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…

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…

A new method improves graph random features with quasi-Monte Carlo techniques.

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…

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…

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…

Paper extends tail bounds to high-dimensional random objects on Riemannian manifolds.

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…

New graph embedding method improves link prediction and node classification.

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…

The paper proves Lipschitz regularity of graph Laplacian eigenvectors on random data clouds.

The paper proves spectral convergence rates for graph Laplacian to manifold Laplace-Beltrami operator.

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…

Study shows how Laplacian semi-supervised learning behaves at low labeling rates.

Neumann eigenmaps improve landmark-based diffusion map embeddings.

New spectral Dehn function characterizes word-hyperbolic groups.

New method clusters directed and undirected graphs without losing directional information.

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…

Let $Γ$ be a (non-elementary) convex co-compact group of isometries of a pinched Hadamard manifold $X$. We show that a normal subgroup $Γ_0$ has critical exponent equal to the critical exponent of $Γ$ if and only if $Γ/ Γ_0$ is amenable. We prove a similar result for the exponential growth rate of closed geodesics on $…

The paper develops a method to sparsify magnetic Laplacians using multi-type spanning forests.

Community detection was a hot topic on network analysis, where the main aim is to perform unsupervised learning or clustering in networks. Recently, semi-supervised learning has received increasing attention among researchers. In this paper, we propose a new algorithm, called weighted inverse Laplacian (WIL), for predi…

Most network-based protein (or gene) function prediction methods are based on the assumption that the labels of two adjacent proteins in the network are likely to be the same. However, assuming the pairwise relationship between proteins or genes is not complete, the information a group of genes that show very similar p…

Clustering is fundamental for gaining insights from complex networks, and spectral clustering (SC) is a popular approach. Conventional SC focuses on second-order structures (e.g., edges connecting two nodes) without direct consideration of higher-order structures (e.g., triangles and cliques). This has motivated SC ext…

Since the invention of word2vec, the skip-gram model has significantly advanced the research of network embedding, such as the recent emergence of the DeepWalk, LINE, PTE, and node2vec approaches. In this work, we show that all of the aforementioned models with negative sampling can be unified into the matrix factoriza…

In this paper we consider the problem of graph-based transductive classification, and we are particularly interested in the directed graph scenario which is a natural form for many real world applications. Different from existing research efforts that either only deal with undirected graphs or circumvent directionality…

We consider a fundamental algorithmic question in spectral graph theory: Compute a spectral sparsifier of random-walk matrix-polynomial $L_α(G)=D-\sum_{r=1}^dα_rD(D^{-1}A)^r$ where $A$ is the adjacency matrix of a weighted, undirected graph, $D$ is the diagonal matrix of weighted degrees, and $α=(α_1...α_d)$ are nonn…

Study large deviations in random walks on Lie groups.

Local limit theorem for random walks on hyperbolic groups with parabolic subgroups.

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 diffusions and random walks on hyperbolic spaces, focusing on their Martin boundaries.

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…

New proof shows rapid mixing for random walks on nilmanifolds.

Random walks on metric spaces embed quasi-isometrically into the space.

Study random walks on groups with superlinear divergent geodesics.

Random walks on hyperbolic spaces show linear growth in translation lengths.