Speeding Up Bellman Ford via Minimum Violation Permutations

Silvio Lattanzi, Ola Svensson, Sergei VassilvitskiiICML 2023 · OpenReview

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:

  1. 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.
  2. 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.
  3. 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.
GreedyFas Heuristic Pseudocode

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 GreedyFas heuristic 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

Abstract

The Bellman-Ford algorithm is a basic primitive for computing single source shortest paths in graphs with negative weight edges. Its running time is governed by the order the algorithm examines vertices for iterative updates on the value of their shortest path. In this work we study this problem through the lens of ’Algorithms with predictions,’ and show how to leverage auxiliary information from similar instances to improve the running time. We do this by identifying the key problem of Minimum Violation Permutations, and give algorithms with strong approximation guarantees as well as formal lower bounds. We complement the theoretical analysis with an empirical evaluation, showing that this approach can lead to a significant speed up in practice.
BibTeX
@inproceedings{lattanzi2023speeding,
  author = {Silvio Lattanzi and Ola Svensson and Sergei Vassilvitskii},
  title = {{Speeding Up Bellman Ford via Minimum Violation Permutations}},
  booktitle = {International Conference on Machine Learning},
  year = {2023},
  url = {https://openreview.net/forum?id=klRU6IKJyD},
}
Figure