arXiv research

Deep learning approximates shortest path distances in large graphs.

There have lately been several suggestions for parametrized distances on a graph that generalize the shortest path distance and the commute time or resistance distance. The need for developing such distances has risen from the observation that the above-mentioned common distances in many situations fail to take into ac…

Consider a weighted or unweighted k-nearest neighbor graph that has been built on n data points drawn randomly according to some density p on R^d. We study the convergence of the shortest path distance in such graphs as the sample size tends to infinity. We prove that for unweighted kNN graphs, this distance converges …

Power weighted shortest paths improve clustering of high-dimensional data.

Landmark-based node embeddings approximate shortest path distances in random graphs.

We present a simple, yet effective, approach to Semi-Supervised Learning. Our approach is based on estimating density-based distances (DBD) using a shortest path calculation on a graph. These Graph-DBD estimates can then be used in any distance-based supervised learning method, such as Nearest Neighbor methods and SVMs…

Matching datasets of multiple modalities has become an important task in data analysis. Existing methods often rely on the embedding and transformation of each single modality without utilizing any correspondence information, which often results in sub-optimal matching performance. In this paper, we propose a nonlinear…

This paper approximates 1-Wasserstein distance using tree-based embedding.

Revisits Isomap, showing it constructs Euclidean representations of geodesic structure.

Fast algorithm for shortest paths on data-manifolds.

New method estimates geodesic distances using spherelets.

This work develops a generic framework, called the bag-of-paths (BoP), for link and network data analysis. The central idea is to assign a probability distribution on the set of all paths in a network. More precisely, a Gibbs-Boltzmann distribution is defined over a bag of paths in a network, that is, on a representati…

EntroPath learns manifold geometry from diffusion paths.

New geometric analysis of PWSPDs balances density and geometry in high-dimensional data.

Predicts unseen links in graphs using motifs of 3-5 nodes.

The paper proposes a method to infer differentiation trees from RNA velocity data.

Sparse RSP routing improves graph exploration and classification.

We improve density-based distances using normalizing flows and score matching.

Paper proves convergence of optimistic policy iteration for stochastic shortest path problems.

Generative Flow Networks solve shortest path problems in graphs.

URerF learns geodesic distances in noisy manifolds.

The classical theorem of Fáry states that every planar graph can be represented by an embedding in which every edge is represented by a straight line segment. We consider generalizations of Fáry's theorem to surfaces equipped with Riemannian metrics. In this setting, we require that every edge is drawn as a shortest pa…

PRODIGE maps data into weighted graphs for better representation learning.

Jacobi solved geodesics on triaxial ellipsoids.

Unified pipeline classifies time series using complex networks and persistent homology.

Given a point (the "spider") on a rectangular box, we would like to find the minimal distance along the surface to its opposite point (the "fly" - the reflection of the spider across the center of the box). Without loss of generality, we can assume that the box has dimensions $1\times a\times b$ with the spider on one …

Algorithm reduces regret in SSP problems with LFA.

Geodesic clustering improves latent space clustering in deep generative models.

Paper tackles offline SSP with value iteration for policy evaluation and learning.

For a compact Riemannian manifold with boundary, we want to find the metric structure from knowledge of distances between boundary points. This is called the "boundary rigidity problem". If the boundary is not concave, which means locally not all shortest paths lie entirely in the boundary, then we are able to find the…

Q-learning for average cost MDPs gets a concentration bound.

Generative models use Riemannian manifolds to improve latent space interpretation.

C-RSP embeds multi-view graphs using randomized shortest paths.

Gradient descent finds the shortest path to global optima in overparameterized models.

A new metric for deep generative models using Riemannian geometry.

The paper proves properties for random graphs based on geometric submanifolds.

We find approximate geodesics in deep models using graph shortest paths.

In this paper we study the metric geometry of the space $Σ$ of positive invertible elements of a von Neumann algebra ${\mathcal A}$ with a finite, normal and faithful tracial state $τ$. The trace induces an incomplete Riemannian metric $<x,y>_a=τ(ya^{-1}xa^{-1})$, and though the techniques involved are quite different,…

New algorithms for planning with adversarial changes in costs.

Optimizes exploration in networks by interpolating between random and deterministic paths.

Extends RSP model with net flow and capacity constraints for better network analysis.

New graph distances derived from optimal transport framework using path flows.

Study models Indian stock market using hyperbolic geometry for market stability and volatility analysis.

New algorithm reduces regret in stochastic shortest path problems.

Algorithm learns to prune search space for repeated computations.

We examine the existence of tangent hyperplanes to subriemannian balls. Strictly abnormal shortest paths are allowed

New algorithms minimize regret in SSP with optimal sparse updates.

Paper generalizes control contraction metrics to Finsler geometry.