WeaveNet for Approximating Two-sided Matching Problems
Shusaku Sone Jiaxin Ma Atsushi Hashimoto Naoya Chiba Yoshitaka Ushiku
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), \textit{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 \textit{strongly
NP-hard} problems, \textit{fair stable 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.