WeaveNet for Approximating Two-sided Matching Problems

Matching, a task to optimally assign limited resources under constraints, is a fundamental technology for society. The task potentially has various objectives, conditions, and constraints; however, the efficient neural network architecture for matching is underexplored. This paper proposes a novel graph neural network (GNN), $\mathit{\text{WeaveNet}}$, designed for bipartite graphs. Since a bipartite graph is generally dense, general GNN architectures lose node-wise information by over-smoothing when deeply stacked. Such a phenomenon is undesirable for solving matching problems. WeaveNet avoids it by preserving edge-wise information while passing messages densely to reach a better solution. To evaluate the model, we approximated one of the $\mathit{\text{strongly}}\mathit{\text{NP-hard}}$ problems, $\mathit{\text{fair}}\mathit{\text{stable}}\mathit{\text{matching}}$. Despite its inherent difficulties and the network’s general purpose design, our model reached a comparative performance with state-of-the-art algorithms specially designed for stable matching for small numbers of agents.