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.
C-RSP embeds multi-view graphs using randomized shortest paths.
problem Combining multiple views of a graph to improve inference quality.
method C-RSP algorithm that generates a common embedding using RSP.
result C-RSP outperforms benchmarks in embedding and clustering tasks.
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…
Optimizes exploration in networks by interpolating between random and deterministic paths.
problem Balancing exploitation and exploration in network routing with constraints.
method Developed a constrained randomized shortest-paths framework using Lagrangian duality and iterative procedures.
result Optimal routing policy that interpolates between random and deterministic paths while satisfying constraints.
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 …
Extends RSP model with net flow and capacity constraints for better network analysis.
problem Improving shortest path models with net flows and capacity constraints.
method Developed net flow RSP model and introduced capacity constraints. Proposed algorithms for computing expected routing costs and solving constrained problems using Lagrangian duality.
result Net flow RSP dissimilarity measure is competitive with state-of-the-art dissimilarities.
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…
Proposes a method to improve graph embedding by removing least frequent nodes.
problem Capturing global graph structure in random walk-based embeddings.
method Extends random walk-based graph embedding by removing least frequent nodes.
result Improves predictive performance slightly, if at all.
Sparse RSP routing improves graph exploration and classification.
problem Optimal randomized routing and distance measures on weighted graphs.
method Tsallis divergence regularization for sparse RSP.
result Sparse random walk converges to least-cost graph as temperature decreases.
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.
Power weighted shortest paths improve clustering of high-dimensional data.
problem Clustering high-dimensional Euclidean data with disjoint low-dimensional manifolds.
method Use of power weighted shortest path distance functions and a fast algorithm.
result Higher clustering accuracy achieved through power weighted shortest paths.
Paper proves convergence of optimistic policy iteration for stochastic shortest path problems.
problem Optimizing policies in stochastic shortest path problems.
method Analyzes optimistic policy iteration algorithm with Monte Carlo and TD(λ) methods.
result Proves convergence of the algorithm under specific conditions.
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.
Deep learning approximates shortest path distances in large graphs.
problem Scaling up shortest path distance computation in large networks.
method Deep learning techniques to approximate distances using vector embeddings.
result Feedforward neural networks with embeddings can approximate distances with low distortion error.
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.
The paper proves properties for random graphs based on geometric submanifolds.
problem Establishing measure-metric properties of random geometric graphs.
method Analyzing ε \varepsilon ε -neighborhood graphs with specific conditions on submanifold and distribution. result Volume doubling and local Poincaré inequalities hold for random geometric graphs with high probability.
A new clustering method for intersecting surfaces using curvature constraints.
problem Challenges in clustering intersecting surfaces, especially with shortest path algorithms failing.
method Imposes curvature constraints on shortest paths in Isomap algorithm.
result Outperforms existing methods like K-manifold and spectral multi-manifold clustering.
Fast algorithm for shortest paths on data-manifolds.
problem Computing shortest paths on manifolds learned from data is challenging.
method Fixed-point iteration scheme for solving ODEs without requiring Jacobians.
result Significant improvements in speed and stability over existing methods.
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.
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…
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.
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…
We find approximate geodesics in deep models using graph shortest paths.
problem Computational complexity of finding geodesics in high-dimensional latent spaces.
method Approximate geodesics via shortest paths in a finite graph of samples.
result Applicable to high-dimensional problems, e.g., visual data.
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.
New algorithm reduces regret in stochastic shortest path problems.
problem Planning and control in environments with unknown dynamics and variable episode lengths.
method Developed an algorithm with a new regret bound of O ( B ⋆ ∣ S ∣ ∣ A ∣ K ) O(B_\star |S| \sqrt{|A| K}) O ( B ⋆ ∣ S ∣ ∣ A ∣ K ) . result Guaranteed a significant reduction in regret compared to previous methods.
We examine the existence of tangent hyperplanes to subriemannian balls. Strictly abnormal shortest paths are allowed
Algorithm learns to prune search space for repeated computations.
problem Exploit common structure in repeated similar problems.
method Exploit explore-exploit technique for pruning search space.
result Reduces runtime while provably outputting correct solutions.
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.
Efficient routing algorithms learn from feedback to minimize path lengths.
problem Optimizing online shortest path routing with end-to-end feedback.
method Adaptive exploration algorithms leveraging networked structure.
result Achieves nearly optimal instance-dependent and worst-case regret for directed acyclic networks.
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.
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 O ( d B ∗ K ) O(dB_*\sqrt{K}) O ( d B ∗ K ) . 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 Ω ( S A B ⋆ 3 / ( c min ε 2 ) ) Ω(SAB_{\star}^3/(c_{\min}ε^2)) Ω ( S A B ⋆ 3 / ( c m i n ε 2 )) samples for general case, and up to logarithmic factors for bounded hitting time condition. 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.
While state-of-the-art kernels for graphs with discrete labels scale well to graphs with thousands of nodes, the few existing kernels for graphs with continuous attributes, unfortunately, do not scale well. To overcome this limitation, we present hash graph kernels, a general framework to derive kernels for graphs with…
The paper bounds crossing numbers of dense graphs on surfaces.
problem Estimating the minimum number of edge crossings for dense graphs on surfaces.
method Proved lower and upper bounds on crossing numbers, providing explicit families of surfaces.
result Upper and lower bounds on crossing numbers match up to constant factors.
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.
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.
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.
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 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 O ( log T ) O(\log T) O ( log T ) regret in stochastic and O ( T ) {O}(\sqrt{T}) O ( T ) regret in adversarial settings. URerF learns geodesic distances in noisy manifolds.
problem Learning geodesic distances in noisy high-dimensional data.
method Unsupervised random forest (URerF) with Bayesian Information Criterion.
result URerF outperforms other methods in estimating geodesic distances on noisy data.
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 Q ∗ Q^* Q ∗ 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.
UC-SSP algorithm tackles exploration in stochastic shortest path problems without loop-free assumption.
problem Exploration in goal-oriented reinforcement learning problems under stochastic shortest path formulation.
method UC-SSP algorithm with a novel stopping rule to interrupt and switch policies.
result Regret bound of O ~ ( D S A D K ) \displaystyle \widetilde{\mathcal{O}}( D S \sqrt{ A D K}) O ( D S A D K ) after K K K episodes. Linear-time graph optimization using reinforcement learning.
problem Solving combinatorial optimization problems on real-world graphs.
method Graph neural network trained with reinforcement learning.
result Approximate solutions in linear time for various graph problems.