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.

在线贝叶斯二分匹配问题是数字市场和交易所中的一个核心问题，我们引入了一种图神经网络（GNN）方法，模拟了该问题的组合复杂的最优在线算法，通过计算每个动作的 VTG（value-to-go）来选择动作（例如，匹配哪些节点），然后在未来以最佳方式行动。我们训练了一个 GNN 来估计 VTG，并从实证上显示，这个 GNN 在各种任务中返回高权重的匹配。此外，我们在空间众包应用中鉴定了一类常见的图分布，例如拼车，其中 VTG 可以通过在图中的局部邻域内聚合信息进行有效的近似。这种结构符合 GNN 的局部行为，为我们的方法提供了理论上的依据。