Generative Flow Networks solve shortest path problems in graphs.
problem Finding shortest paths in graphs.
method Generative Flow Networks with flow regularization.
result Training a GFlowNet can solve pathfinding problems in arbitrary graphs.
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,657 papers · 148 categories
Trend · papers per month
48 results for “shortest path”
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…
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 …
Developments in the theory of randomized shortest paths with a comparison of graph node distancesstat.ML
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…
Algorithm reduces regret in SSP problems with LFA.
problem Finding shortest paths in stochastic environments with linear approximations.
method Uses linear function approximation and stationary policies to minimize regret.
result Achieves sublinear regret under minimal assumptions.
Landmark-Based Node Representations for Shortest Path Distance Approximations in Random Graphsstat.ML
Landmark-based node embeddings approximate shortest path distances in random graphs.
problem Capturing global graph distances in node representations.
method Landmark-based node embeddings using shortest path distances from a subset of reference nodes (landmarks).
result Random graphs require lower dimensions in landmark-based embeddings compared to worst-case graphs.
Computing shortest path distances between nodes lies at the heart of many graph algorithms and applications. Traditional exact methods such as breadth-first-search (BFS) do not scale up to contemporary, rapidly evolving today's massive networks. Therefore, it is required to find approximation methods to enable scalable…
In this paper, we prove some convergence results of a special case of optimistic policy iteration algorithm for stochastic shortest path problem. We consider both Monte Carlo and methods for the policy evaluation step under the condition that the termination state will eventually be reached almost surely.
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…
We study the use of power weighted shortest path distance functions for clustering high dimensional Euclidean data, under the assumption that the data is drawn from a collection of disjoint low dimensional manifolds. We argue, theoretically and experimentally, that this leads to higher clustering accuracy. We also pres…
Paper tackles offline SSP with value iteration for policy evaluation and learning.
problem Goal-oriented RL with offline data and cost minimization.
method Simple value iteration algorithms for OPE and offline policy learning.
result Strong instance-dependent bounds implying near-minimax optimal worst-case bounds.
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…
Q-learning for average cost MDPs gets a concentration bound.
problem Finding bounds for Q-learning in average cost MDPs.
method Derives a concentration bound using shortest path problem equivalence.
result Numerical comparison with relative value iteration shows the bound's effectiveness.
Generative models use Riemannian manifolds to improve latent space interpretation.
problem Generative models often bias latent space interpretations.
method Use Riemannian manifolds to define latent space paths that respect ambient geometry.
result Improves interpretability of learned representations for both stochastic and deterministic generators.
Study examines how information flows in Indian stock market during crises.
problem Understanding information diffusion in financial networks during market turbulence.
method Applied communicability, a measure of ease of information flow, to financial networks.
result Approximately 70% and 80% of stock pairs exhibit significant changes in communicability during crises.
The problem of multiple surface clustering is a challenging task, particularly when the surfaces intersect. Available methods such as Isomap fail to capture the true shape of the surface nearby the intersection and result in incorrect clustering. The Isomap algorithm uses the shortest path between points. The main draw…
EntroPath learns manifold geometry from diffusion paths.
problem Learning geodesic geometry from data graphs with spurious shortcuts.
method Maximum Entropy Path Ensemble Embedding (MERW) with k-step diffusion paths.
result EntroPath converges to squared geodesic distance in the short-time limit.
Control Contraction Metrics (CCMs) provide a nonlinear controller design involving an offline search for a Riemannian metric and an online search for a shortest path between the current and desired trajectories. In this paper, we generalize CCMs to Finsler geometry, allowing the use of non-Riemannian metrics. We provid…
The present work extends the randomized shortest-paths framework (RSP), interpolating between shortest-path and random-walk routing in a network, in three directions. First, it shows how to deal with equality constraints on a subset of transition probabilities and develops a generic algorithm for solving this constrain…
New algorithms for planning with adversarial changes in costs.
problem Planning with adversarial changes in costs over time.
method Developed algorithms for adversarial SSP with high probability regret bounds.
result Obtained sub-linear regret bounds for adversarial SSP.
We examine the existence of tangent hyperplanes to subriemannian balls. Strictly abnormal shortest paths are allowed
Implicit Finite-Horizon Approximation and Efficient Optimal Algorithms for Stochastic Shortest Pathcs.LG
New algorithms minimize regret in SSP with optimal sparse updates.
problem Minimizing regret in Stochastic Shortest Path models.
method Implicit finite-horizon approximation for analysis, model-free and model-based algorithms developed.
result Minimax optimal regret for both model-free and model-based algorithms.
Unified algorithm for optimizing rewards in stochastic path problems.
problem Optimizing rewards in stochastic path problems with unknown reward scales.
method A simple optimistic algorithm with regret guarantees.
result Regret bound matches best known results for SSP with all non-positive rewards.
A new method extracts events and their arguments efficiently from text.
problem Efficiently extract event information from texts with long-range dependencies and associations.
method Graph Convolutional Networks with shortest dependency paths to capture syntactic relationships.
result Significant improvement over state-of-the-art methods.
New RL approach builds short ancestral recombination graphs.
problem Building short ancestral recombination graphs (ARGs).
method Reinforcement Learning applied to genetic sequences.
result RL can build ARGs as short as heuristic algorithms.
Study examines how wind affects shortest paths on Finsler manifolds.
problem Investigating shortest paths in Finsler manifolds with wind effects.
method Coordinate-free approach to compare isoparametric functions and mean curvatures.
result Mean curvatures differ in presence and absence of wind on Finsler manifolds.
Paper finds shortest geodesic paths on hyperbolic surfaces.
problem Finding the shortest geodesic paths on hyperbolic surfaces.
method Analyzes genus g hyperbolic surfaces to find minimal length geodesics.
result Minimal geodesic length is realized by a specific polygon.
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…
New bounds on shortest geodesic loops on a sphere.
problem Finding shortest geodesic loops on a sphere.
method Analyzing geodesic loops starting and ending at a fixed point on a sphere.
result At any point on a sphere, there are at least two distinct geodesic loops whose lengths are bounded by 8d and 14d.
New algorithm reduces regret in linear mixture SSPs without cost bounds.
problem Learning optimal paths in stochastic environments with cost constraints.
method Extended value iteration with variance-aware confidence set.
result Achieves nearly minimax optimal regret bound of .
Study shows sample complexity for learning optimal policies in SSP with generative model.
problem Learning optimal policies in Stochastic Shortest Path problems.
method Derive and prove lower and upper bounds on sample complexity.
result Lower bound of samples for general case, and up to logarithmic factors for bounded hitting time condition.
This work extends the randomized shortest paths (RSP) model by investigating the net flow RSP and adding capacity constraints on edge flows. The standard RSP is a model of movement, or spread, through a network interpolating between a random-walk and a shortest-path behavior [30, 42, 49]. The framework assumes a unit f…
PathNNs improve graph neural networks by distinguishing non-isomorphic graphs.
problem Limitations of standard GNNs in distinguishing non-isomorphic graphs.
method Proposes PathNNs that aggregate paths to update node representations.
result Two variants of PathNNs are strictly more powerful than 1-WL algorithm.
Paper studies CLO with partial feedback, improving decision-making in uncertain contexts.
problem Improving decision-making in contexts with uncertain cost coefficients using partial feedback.
method Unified class of offline learning algorithms for CLO with different types of feedback, using IERM framework.
result Fast-rate regret bound for IERM with partial feedback and misspecified model classes.
Agent learns to navigate uncertain 3D maps using a hybrid planner.
problem Planning in 3D environments with uncertain topological maps.
method Hierarchical strategy combining graph planner and local policy, data-driven learning with neural network.
result Machine learning can overcome missing information in probabilistic topological maps.
Revisits Isomap, showing it constructs Euclidean representations of geodesic structure.
problem Nonlinear dimension reduction of manifold data.
method Revisits Isomap's rationale, clarifying its approach to constructing Euclidean representations of geodesic structure.
result Convexity is not required for shortest path distances to converge to Riemannian distances.
We propose a fast, simple and robust algorithm for computing shortest paths and distances on Riemannian manifolds learned from data. This amounts to solving a system of ordinary differential equations (ODEs) subject to boundary conditions. Here standard solvers perform poorly because they require well-behaved Jacobians…
It is common to encounter situations where one must solve a sequence of similar computational problems. Running a standard algorithm with worst-case runtime guarantees on each instance will fail to take advantage of valuable structure shared across the problem instances. For example, when a commuter drives from work to…
Study shows hard sample complexity for learning optimal policies in stochastic shortest path problems.
problem Learning optimal policies in stochastic shortest path problems.
method Analyzes sample complexity with and without generative models, derives lower and upper bounds.
result Proves sample complexity bounds and impossibility of horizon-free regret in SSPs.
New algorithm learns optimal path in reinforcement learning with linear approximations.
problem Optimal path learning in reinforcement learning with linear approximations.
method Proposes novel algorithm with Hoeffding-type and Bernstein-type confidence sets.
result Achieves near-optimal regret guarantee for linear mixture SSP.
This paper approximates 1-Wasserstein distance using tree-based embedding.
problem Computational inefficiency of estimating 1-Wasserstein distance.
method L1-regularized approach to learn tree weights, using shortest path distance as a linear model.
result Tree-Wasserstein distance (TWD) approximates 1-Wasserstein distance efficiently.
Study online learning in MDPs with aggregate bandit feedback, achieving low regret in both stochastic and adversarial settings.
problem Online learning in finite-horizon episodic MDPs with aggregate bandit feedback.
method Best-of-both-worlds (BOBW) algorithms using FTRL over occupancy measures, self-bounding techniques, and new loss estimators.
result First BOBW algorithms for episodic tabular MDPs with aggregate bandit feedback achieving regret in stochastic and regret in adversarial settings.
Geodesics connect model modes in neural network loss landscapes.
problem Connecting modes in neural network loss landscapes.
method Reframed mode connectivity in Information Geometry, hypothesized geodesics as mode-connecting paths, proposed algorithm to approximate geodesics.
result Geodesics achieve mode connectivity in neural networks.
Bayesian framework for SSP problem learns optimal strategy through interactions.
problem Sequential decision-making in stochastic shortest path problems.
method Develops a Bayesian framework to learn optimal action-value function through interactions, avoiding unrealistic assumptions.
result Demonstrates data efficiency and uncertainty quantification compared to other methods.
Graph embedding method captures both local and global network structure.
problem Representing and analyzing complex graph networks.
method Spectral embedding based on a generalized graph Laplacian.
result Significant improvement in data analysis tasks.
Paper identifies reductive MDPs, solving them in polynomial time.
problem Computational hardness of general MDPs and tractability of finite-horizon MDPs.
method Defines reductivity, a new class of SSPs, and develops a polynomial-time solution.
result Optimal policies can be found in polynomial time for reductive SSPs and MDPs.
We introduce efficient algorithms which achieve nearly optimal regrets for the problem of stochastic online shortest path routing with end-to-end feedback. The setting is a natural application of the combinatorial stochastic bandits problem, a special case of the linear stochastic bandits problem. We show how the diffi…
New geometric analysis of PWSPDs balances density and geometry in high-dimensional data.
problem Balancing density and geometry in high-dimensional data.
method Power-weighted shortest-path distances (PWSPDs) and their geometric and computational analyses.
result High probability guarantees on the equivalence of PWSPDs on complete and nearest neighbor graphs.