MAGNOLIA: Matching Algorithms via GNNs for Online Value-to-go Approximation
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916293838372864 |
|---|---|
| author | Hayderi, Alexandre Saberi, Amin Vitercik, Ellen Wikum, Anders |
| author_facet | Hayderi, Alexandre Saberi, Amin Vitercik, Ellen Wikum, Anders |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_05959 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | MAGNOLIA: Matching Algorithms via GNNs for Online Value-to-go Approximation Hayderi, Alexandre Saberi, Amin Vitercik, Ellen Wikum, Anders Machine Learning Data Structures and Algorithms 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. |
| title | MAGNOLIA: Matching Algorithms via GNNs for Online Value-to-go Approximation |
| topic | Machine Learning Data Structures and Algorithms |
| url | https://arxiv.org/abs/2406.05959 |