Deep Graph Reinforcement Learning for Solving Multicut Problem.

Area of Science:

• Combinatorial Optimization
• Graph Theory
• Machine Learning

Background:

• The multicut problem, or correlation clustering, is a key graph partitioning task.
• Existing methods struggle with NP-hard complexity and inflexible heuristics.
• Applications span data mining and computer vision.

Purpose of the Study:

• To develop a novel deep graph reinforcement learning method for the multicut problem.
• To overcome limitations of existing combinatorial solvers and hand-designed heuristics.
• To achieve end-to-end learning of feasible multicut solutions.

Main Methods:

• A deep graph reinforcement learning framework utilizing sequential edge contractions.
• A customized subgraph neural network for dynamic graph environments.
• Extraction of bilevel connected features from contracted and original graphs.

Main Results:

• The method learns adaptive heuristics, implicitly gaining knowledge from graph topology.
• High-quality multicut solutions are constructed in polynomial time.
• Demonstrated superiority over existing combinatorial solvers on synthetic and real-world data.

Conclusions:

• The proposed deep graph reinforcement learning method offers a powerful, data-driven approach to the multicut problem.
• Learned heuristics provide targeted solutions, overcoming limitations of traditional methods.
• The approach shows strong performance and generalization ability on diverse instances.