Solving maximum weighted matching on large graphs with deep reinforcement learning

Maximum weighted matching (MWM), which finds a subset of vertex-disjoint edges with maximum weight, is a fundamental topic with a wide spectrum of applications in various fields, such as biotechnology, social analysis, web services, etc. However, traditional meth-ods cannot achieve a good balance between cost and quality. Inspired by the reinforcement learning techniques, we propose an MWM framework, L2M, with a Deep Reinforcement Learning (DRL) model, which can efficiently and effectively solve the MWM problem on large-scale general graphs. First, in contrast to traditional DRL methods that define the Markov Decision Process (MDP) without considering the efficiency issue, we represent MWM as an MDP that is carefully designed to accelerate computation. In particular, this MDP supports selecting multiple edges for each action and uses a pruning method to reduce search space efficiently. Second, since none of the existing DRL methods can sup-port edge selection on large-scale graphs efficiently, we propose an edge-message -passing network EEN to generate edge embedding. To the best of our knowledge, this is the first attempt that uses DRL model for solving the MWM problem. Experimental results show that L2M outperforms state-of-the-art algorithms and generalizes well on graphs of different sizes and distributions.(c) 2022 Elsevier Inc. All rights reserved.

Automated summary

This paper introduces a framework called L2M, based on a deep reinforcement learning (DRL) model, for solving the maximum weighted matching (MWM) problem on large-scale general graphs. The framework represents MWM as a carefully designed Markov Decision Process (MDP) and incorporates pruning methods and an edge-message passing network to improve efficiency and effectiveness.