Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising
This work addresses the need for fast, resource-efficient matching algorithms in dynamic, large-scale applications like online advertising, representing an incremental improvement over existing approximation approaches.
The paper tackles the challenge of efficiently solving large-scale, dynamic maximum weighted b-matching problems in online advertising by proposing NeuSearcher, which uses a graph neural network to predict thresholds and a parallel heuristic search, resulting in a 2 to 3 times speedup while maintaining solution quality compared to state-of-the-art methods.
Bipartite b-matching is fundamental in algorithm design, and has been widely applied into economic markets, labor markets, etc. These practical problems usually exhibit two distinct features: large-scale and dynamic, which requires the matching algorithm to be repeatedly executed at regular intervals. However, existing exact and approximate algorithms usually fail in such settings due to either requiring intolerable running time or too much computation resource. To address this issue, we propose \texttt{NeuSearcher} which leverages the knowledge learned from previously instances to solve new problem instances. Specifically, we design a multichannel graph neural network to predict the threshold of the matched edges weights, by which the search region could be significantly reduced. We further propose a parallel heuristic search algorithm to iteratively improve the solution quality until convergence. Experiments on both open and industrial datasets demonstrate that \texttt{NeuSearcher} can speed up 2 to 3 times while achieving exactly the same matching solution compared with the state-of-the-art approximation approaches.