Graph Neural Networks with Triangle-Based Messages for the Multicut Problem
Provides a faster, higher-quality heuristic for the multicut problem, which is important for applications in bioinformatics, data mining, and computer vision.
The authors propose a graph neural network for the NP-hard multicut problem, using triangle-based messages on edge features. Their method outperforms state-of-the-art heuristics on instances up to 200 nodes, finding optimal solutions in seconds versus hours for exact solvers.
The multicut problem is an NP-hard combinatorial optimization problem with diverse applications in fields such as bioinformatics, data mining and computer vision. Graph neural networks have been defined for the multicut problem but can be adapted further to its specific objective function and constraints. In this article, we introduce such an adapted graph neural network architecture in which features are assigned only to edges, and the computation of messages is based on triangles in the underlying graph. Experiments with synthetic and real-world instances with up to 200 nodes show that our method outperforms state-of-the-art heuristic solvers in terms of solution quality while maintaining feasible runtimes. For some instances, our method finds optimal solutions in seconds whereas exact solvers need hours to find and certify optimal solutions.