# Faster Fundamental Graph Algorithms via Learned Predictions

arXiv: https://arxiv.org/abs/2204.12055 · HTML: https://mlsanity.com/paper/2204.12055/

## Key facts

- Cited by 42 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Apr 2022.

## Built on by (most cited first, 30 of 42)

- [Algorithms with Prediction Portfolios](https://mlsanity.com/paper/2210.12438/) (2022)
- [Discrete-Convex-Analysis-Based Framework for Warm-Starting Algorithms with Predictions](https://mlsanity.com/paper/2205.09961/) (2022)
- [Sorting with Predictions](https://mlsanity.com/paper/2311.00749/) (2023)
- [Online bipartite matching with imperfect advice](https://mlsanity.com/paper/2405.09784/) (2024)
- [Algorithms for Caching and MTS with reduced number of predictions](https://mlsanity.com/paper/2404.06280/) (2024)
- [Learning-Augmented Maximum Flow](https://mlsanity.com/paper/2207.12911/) (2022)
- [Learning-Augmented Algorithms for Online Linear and Semidefinite Programming](https://mlsanity.com/paper/2209.10614/) (2022)
- [Learning-augmented Maximum Independent Set](https://mlsanity.com/paper/2407.11364/) (2024)
- [Paging with Succinct Predictions](https://mlsanity.com/paper/2210.02775/) (2022)
- [Improved Learning-augmented Algorithms for k-means and k-medians Clustering](https://mlsanity.com/paper/2210.17028/) (2022)
- [Improved Frequency Estimation Algorithms with and without Predictions](https://mlsanity.com/paper/2312.07535/) (2023)
- [Non-clairvoyant Scheduling with Partial Predictions](https://mlsanity.com/paper/2405.01013/) (2024)
- [Learning-Augmented Priority Queues](https://mlsanity.com/paper/2406.04793/) (2024)
- [Learning-Augmented Algorithms for the Bahncard Problem](https://mlsanity.com/paper/2410.15257/) (2024)
- [Learning-Augmented Private Algorithms for Multiple Quantile Release](https://mlsanity.com/paper/2210.11222/) (2022)
- [Online List Labeling with Predictions](https://mlsanity.com/paper/2305.10536/) (2023)
- [Online Classification with Predictions](https://mlsanity.com/paper/2405.14066/) (2024)
- [The Predicted-Updates Dynamic Model: Offline, Incremental, and Decremental to Fully Dynamic Transformations](https://mlsanity.com/paper/2307.08890/) (2023)
- [Learning-Augmented Search Data Structures](https://mlsanity.com/paper/2402.10457/) (2024)
- [Competitive strategies to use "warm start" algorithms with predictions](https://mlsanity.com/paper/2405.03661/) (2024)
- [Learning multivariate Gaussians with imperfect advice](https://mlsanity.com/paper/2411.12700/) (2024)
- [Improved Approximations for Hard Graph Problems using Predictions](https://mlsanity.com/paper/2505.23967/) (2025)
- [Approximate Proportionality in Online Fair Division](https://mlsanity.com/paper/2508.03253/) (2025)
- [On the Power of Learning-Augmented Search Trees](https://mlsanity.com/paper/2211.09251/) (2022)
- [Scheduling with Predictions](https://mlsanity.com/paper/2212.10433/) (2022)
- [Rethinking Warm-Starts with Predictions: Learning Predictions Close to Sets of Optimal Solutions for Faster L-/L^natural-Convex Function Minimization](https://mlsanity.com/paper/2302.00928/) (2023)
- [Faster Discrete Convex Function Minimization with Predictions: The M-Convex Case](https://mlsanity.com/paper/2306.05865/) (2023)
- [Accelerating Matroid Optimization through Fast Imprecise Oracles](https://mlsanity.com/paper/2402.02774/) (2024)
- [Warm-starting Push-Relabel](https://mlsanity.com/paper/2405.18568/) (2024)
- [Learning-Augmented Frequent Directions](https://mlsanity.com/paper/2503.00937/) (2025)

## Abstract (arXiv)

We consider the question of speeding up classic graph algorithms with machine-learned predictions. In this model, algorithms are furnished with extra advice learned from past or similar instances. Given the additional information, we aim to improve upon the traditional worst-case run-time guarantees. Our contributions are the following: (i) We give a faster algorithm for minimum-weight bipartite matching via learned duals, improving the recent result by Dinitz, Im, Lavastida, Moseley and Vassilvitskii (NeurIPS, 2021); (ii) We extend the learned dual approach to the single-source shortest path problem (with negative edge lengths), achieving an almost linear runtime given sufficiently accurate predictions which improves upon the classic fastest algorithm due to Goldberg (SIAM J. Comput., 1995); (iii) We provide a general reduction-based framework for learning-based graph algorithms, leading to new algorithms for degree-constrained subgraph and minimum-cost 0-1 flow, based on reductions to bipartite matching and the shortest path problem. Finally, we give a set of general learnability theorems, showing that the predictions required by our algorithms can be efficiently learned in a PAC fashion.