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

Alexandre Hayderi, Amin Saberi, Ellen Vitercik, Anders Wikum
Proceedings of the 41st International Conference on Machine Learning, PMLR 235:17759-17782, 2024.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v235-hayderi24a, title = {{MAGNOLIA}: Matching Algorithms via {GNN}s for Online Value-to-go Approximation}, author = {Hayderi, Alexandre and Saberi, Amin and Vitercik, Ellen and Wikum, Anders}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, pages = {17759--17782}, year = {2024}, editor = {Salakhutdinov, Ruslan and Kolter, Zico and Heller, Katherine and Weller, Adrian and Oliver, Nuria and Scarlett, Jonathan and Berkenkamp, Felix}, volume = {235}, series = {Proceedings of Machine Learning Research}, month = {21--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v235/main/assets/hayderi24a/hayderi24a.pdf}, url = {https://proceedings.mlr.press/v235/hayderi24a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T MAGNOLIA: Matching Algorithms via GNNs for Online Value-to-go Approximation %A Alexandre Hayderi %A Amin Saberi %A Ellen Vitercik %A Anders Wikum %B Proceedings of the 41st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2024 %E Ruslan Salakhutdinov %E Zico Kolter %E Katherine Heller %E Adrian Weller %E Nuria Oliver %E Jonathan Scarlett %E Felix Berkenkamp %F pmlr-v235-hayderi24a %I PMLR %P 17759--17782 %U https://proceedings.mlr.press/v235/hayderi24a.html %V 235 %X 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.
APA
Hayderi, A., Saberi, A., Vitercik, E. & Wikum, A.. (2024). MAGNOLIA: Matching Algorithms via GNNs for Online Value-to-go Approximation. Proceedings of the 41st International Conference on Machine Learning, in Proceedings of Machine Learning Research 235:17759-17782 Available from https://proceedings.mlr.press/v235/hayderi24a.html.

Related Material