Introduction
The Bellman-Ford algorithm is a classic computer science primitive used to find single-source shortest paths in graphs with negative edge weights. In the worst case, it requires $O(|V|)$ passes over all edges, leading to an $O(|V||E|)$ running time. However, if the algorithm magically processes the vertices in the exact order of the shortest path, it converges in just a single pass!
In practice, we rarely know this optimal order in advance. But what if we repeatedly solve shortest path problems on similar graphs—such as a road network where traffic weights change slightly day-to-day? This paper tackles this problem through the lens of "Algorithms with Predictions." It demonstrates how to use historical data from similar graphs to learn a near-optimal vertex ordering, significantly reducing the number of iterations required to compute shortest paths.
The Minimum Violation Permutations (MVP) Problem
The authors formalize this challenge as the Minimum Violation Permutations (MVP) problem. Given a set of shortest paths from historical data, the goal is to find a single vertex ordering that minimizes the maximum number of "backward" edges (violations) across any of these paths. Every backward edge in an ordering forces Bellman-Ford to perform an extra iteration.
To solve MVP, the authors introduce three main approaches:
- An LP-Rounding Algorithm: They formulate MVP as a Linear Program (LP) and provide a rounding scheme that achieves an $O(\sqrt{n} \log n \log \log n)$ approximation.
- A Bi-criteria Algorithm: Recognizing the difficulty of finding a single perfect order, they design an algorithm that outputs a small set of $O(\log k)$ orderings (where $k$ is the number of paths). By modifying Bellman-Ford to alternate between these orderings, they achieve a much tighter $O(\log n \log \log n)$ approximation.
- A Practical Heuristic: Because solving LPs is computationally heavy, the authors adapt a fast, linear-time greedy heuristic (
GreedyFas) from the Feedback Arc Set literature for real-world empirical evaluations.
Experimental Setup and Results
The authors evaluated their approach on both synthetic layered bipartite graphs and real-world temporal network datasets from SNAP (CollegeMsg, email-Eu-core, MathOverflow, and AskUbuntu).
Key Results: * Theoretical Guarantees: The LP rounding algorithm guarantees an $O(\sqrt{n} \log n \log \log n)$ approximation for a single ordering, while the bi-criteria algorithm achieves an $O(\log n \log \log n)$ approximation using alternating orders. * Synthetic Experiments: When training and test graphs are identical, the learned ordering reduces Bellman-Ford to a single iteration. Even with 90% of the graph layers randomly permuted, the learned ordering shows a statistically significant improvement over a random baseline. * Real-World Experiments: On the SNAP datasets, the learned ordering reduced the number of Bellman-Ford iterations by 10.3% to 23.8% compared to a random ordering baseline, consistently outperforming temporal and standard Bellman-Ford orderings.
Key Insights
- The MVP Abstraction: Framing Bellman-Ford's iteration complexity as a permutation problem over known paths elegantly connects shortest path algorithms to the well-known Feedback Arc Set problem.
- Alternating Orders: A brilliant theoretical workaround to the hardness of finding one perfect order is to find a logarithmic set of orders and alternate between them. If just one order aligns well with a given path, the algorithm makes fast progress.
- Theoretical Hardness vs. Practical Utility: The authors prove that, assuming the Variant Label Cover conjecture, it is NP-hard to approximate MVP within any constant factor. However, the simple
GreedyFasheuristic bridges the gap, proving the "learned advice" framework is highly viable in production despite theoretical worst-case hardness.
Limitations and Future Work
The theoretically sound LP-based algorithms are currently too slow for massive real-world graphs, necessitating heuristics like GreedyFas in practice. Furthermore, the theoretical integrality gap of the LP is bounded by $\sqrt{n}$, leaving room for tighter mathematical analysis.
Future work could extend the MVP problem to a $k$-center clustering variant. Instead of learning one ordering, an algorithm could learn multiple different orderings for different "types" of graphs in a distribution. The authors also suggest applying this historical data framework to speed up other classic algorithms.
Summary updated