Skip to yearly menu bar Skip to main content


Poster

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

Alexandre Hayderi · Amin Saberi · Ellen Vitercik · Anders Wikum


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 combinatorially-complex optimal online algorithm. This optimal algorithm selects actions (e.g., which nodes to match) by computing each action's value-to-go (VTG), which is the expected weight of the matching if the algorithm takes that action, and then chooses each subsequent action optimally. 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.

Live content is unavailable. Log in and register to view live content