Deep Graph Reinforcement Learning for Solving Multicut Problem

The multicut problem, also known as correlation clustering, is a classic combinatorial optimization problem that aims to optimize graph partitioning given only node (dis)similarities on edges. It serves as an elegant generalization for several graph partitioning problems and has found successful applications in various areas such as data mining and computer vision. However, the multicut problem with an exponentially large number of cycle constraints proves to be NP-hard, and existing solvers either suffer from exponential complexity or often give unsatisfactory solutions due to inflexible heuristics driven by hand-designed mechanisms. In this article, we propose a deep graph reinforcement learning method to solve the multicut problem within a combinatorial decision framework involving sequential edge contractions. The customized subgraph neural network adapts to the dynamically edge-contracted graph environment by extracting bilevel connected features from both contracted and original graphs. Our method can learn to infer feasible multicut solutions end-to-end toward optimization of the multicut objective in a data-driven manner. More specifically, by exploring the decision space adaptively, it implicitly gains heuristic knowledge from topological patterns of instances and thereby generates more targeted heuristics overcoming the short-sightedness inherent in the hand-designed ones. During testing, the learned heuristics iteratively contract graphs to construct high-quality solutions within polynomial time. Extensive experiments on synthetic and real-world multicut instances show the superiority of our method over existing combinatorial solvers, while also maintaining a certain level of out-of-distribution generalization ability.