WeaveNet for Approximating Two-sided Matching Problems
This work addresses the underexplored challenge of designing efficient neural network architectures for matching problems, which are fundamental for resource allocation in society, though it is incremental as it focuses on a specific graph type and small-scale scenarios.
The paper tackled the problem of efficiently approximating strongly NP-hard two-sided matching problems, such as fair stable matching, by proposing a novel graph neural network called WeaveNet that avoids over-smoothing in dense bipartite graphs, achieving comparative performance with state-of-the-art specialized algorithms for small numbers of agents.
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.