# MAGNOLIA: Matching Algorithms via GNNs for Online Value-to-go Approximation

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 30 references that are in the map.
- First posted on arXiv 10 Jun 2024.

## Builds on (most cited first, 18 of 18)

- [Optuna: A Next-generation Hyperparameter Optimization Framework](https://mlsanity.com/paper/1907.10902/) (2019)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [How Attentive are Graph Attention Networks?](https://mlsanity.com/paper/2105.14491/) (2021)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [DeeperGCN: All You Need to Train Deeper GCNs](https://mlsanity.com/paper/2006.07739/) (2020)
- [OSMnx: New Methods for Acquiring, Constructing, Analyzing, and Visualizing Complex Street Networks](https://mlsanity.com/paper/1611.01890/) (2016)
- [Smoothed Analysis with Adaptive Adversaries](https://mlsanity.com/paper/2102.08446/) (2021)
- [Deep Policies for Online Bipartite Matching: A Reinforcement Learning Approach](https://mlsanity.com/paper/2109.10380/) (2021)
- [An Experimental Study of Algorithms for Online Bipartite Matching](https://mlsanity.com/paper/1808.04863/) (2018)
- [Adversarial Deep Learning for Online Resource Allocation](https://mlsanity.com/paper/2111.10285/) (2021)
- [Learning Robust Algorithms for Online Allocation Problems Using Adversarial Training](https://mlsanity.com/paper/2010.08418/) (2020)
- [Learning for Edge-Weighted Online Bipartite Matching with Robustness Guarantees](https://mlsanity.com/paper/2306.00172/) (2023)
- [Online Stochastic Max-Weight Matching: prophet inequality for vertex and edge arrival models](https://mlsanity.com/paper/2002.09807/) (2020)
- [Online Stochastic Max-Weight Bipartite Matching: Beyond Prophet Inequalities](https://mlsanity.com/paper/2102.10261/) (2021)
- [Max-Weight Online Stochastic Matching: Improved Approximations Against the Online Benchmark](https://mlsanity.com/paper/2206.01270/) (2022)
- [Online Dependent Rounding Schemes for Bipartite Matchings, with Applications](https://mlsanity.com/paper/2301.08680/) (2023)

## Built on by (most cited first, 2 of 2)

- [Primal-Dual Neural Algorithmic Reasoning](https://mlsanity.com/paper/2505.24067/) (2025)
- [Learning Optimal Dynamic Matching via Graph Neural Networks](https://mlsanity.com/paper/2607.28925/) (2026)

## Abstract (arXiv)

Online Bayesian bipartite matching is a central problem in digital marketplaces and exchanges, including advertising, crowdsourcing, ridesharing, and kidney exchange. We introduce a graph neural network (GNN) approach that emulates the problem's combinatorially-complex optimal online algorithm, which selects actions (e.g., which nodes to match) by computing each action's value-to-go (VTG) -- the expected weight of the final matching if the algorithm takes that action, then acts optimally in the future. We train a GNN to estimate VTG and show empirically that this GNN returns high-weight matchings across a variety of tasks. Moreover, we identify a common family of graph distributions in spatial crowdsourcing applications, such as rideshare, under which VTG can be efficiently approximated by aggregating information within local neighborhoods in the graphs. This structure matches the local behavior of GNNs, providing theoretical justification for our approach.