Research map / Graph learning / Graph algorithms and clustering
MAGNOLIA: Matching Algorithms via GNNs for Online Value-to-go Approximation
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Trains a GNN to approximate the value-to-go of the optimal online algorithm for online Bayesian bipartite matching, with local-approximation guarantees for bipartite random geometric graphs.
Problem
Online Bayesian bipartite matching requires computing value-to-go (VTG) for each action, which is PSPACE-hard to approximate and intractable for moderate graph sizes.
Approach
Train a message-passing GNN via supervised learning to predict VTG of each feasible matching action, replacing exact DP inside the optimal online algorithm; prove that for bipartite random geometric graphs VTG is locally approximable, matching GNN locality.
Key results
- GNN achieves average competitive ratio about 2-5% higher than the best baseline across 12 graph configurations of size 10x30 (e.g., 0.945 on ER p=0.25 at 10x20 vs 0.929 for LP-rounding).
- Trained only on 16-node graphs, performance remains consistent on graphs up to 18 times larger.
- Proves that for bipartite random geometric graphs VTG is (O(beta log N), eps, delta)-locally approximable.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use MAGNOLIA instead of the best baseline | OBBM across the evaluated graph configurations · 12 unseen graph configurations | average competitive ratio: 2-5% higher | Helped |
| Train MAGNOLIA exclusively on 16-node graphs and evaluate on larger graphs | MAGNOLIA · Inputs up to 18 times larger than training graphs | competitive ratio | No clear effect |
| Use a meta-GNN to select between GNNs trained on different regimes | MAGNOLIA · Different online-to-offline node ratios | competitive ratio | Helped |
| Evaluate using noisy edge weights and arrival probabilities | MAGNOLIA and baselines · Noisy OBBM inputs across graph configurations | competitive ratio robustness | Helped |
| Replace the VTG approximator with alternative GNN architectures (ablation) | MAGNOLIA · Graph configurations, (10×20) | competitive ratio | No clear effect |
Surprising findings
- A model trained in an offline-heavy regime performs poorly in online-heavy regimes, motivating a meta-GNN over regime-specific GNNs.
- LP-rounding is eventually better than the GNN in very online-heavy regimes that are out-of-distribution for the GNN.
Limitations
- Exact VTG (the teacher) is intractable beyond small graphs, so training targets are limited to 16-node instances.
- Performance degrades out of distribution across online/offline regimes, requiring a meta-model.
- Theoretical locality result applies only to bipartite random geometric graphs under a beta-smooth distribution assumption.
Experimental setup
Datasets: Erdos-Renyi synthetic bipartite graphs Barabasi-Albert synthetic bipartite graphs bipartite random geometric graphs OSMnx rideshare semi-synthetic graphs gMission
Benchmarks: synthetic ER, BA, b-RGG graphs OSMnx rideshare gMission
Metrics: competitive ratio vs offline OPT model accuracy vs online optimal action
Baselines: greedy greedy-t (threshold greedy) LP-rounding
Builds on: GENConv PyTorch Geometric Optuna
Closest papers by meaning
- Stochastic Matching via Local Sparsification (NeurIPS 2026 · similarity 0.86)
- Online Matching with Stochastic Rewards: Provable Better Bound via Adversarial Reinforcement Learning (ICML 2024 · similarity 0.86)
- Learning-Augmented Online Bipartite Fractional Matching (NeurIPS 2025 · similarity 0.85)
- Online bipartite matching with imperfect advice (ICML 2024 · similarity 0.85)
- DiMa: Understanding the Hardness of Online Matching Problems via Diffusion Models (ICML 2025 · similarity 0.85)
- Gradient-Guided Credit Assignment and Joint Optimization for Dependency-Aware Spatial Crowdsourcing (AAAI 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.