基于三角形消息传递的图神经网络，高效求解多割问题
Graph Neural Networks with Triangle-Based Messages for the Multicut Problem
- 仅在边上传递信息，消息计算依赖图中三角形结构
- 200节点以内实例上，解质量优于顶尖启发式算法
- 部分案例秒级找到最优解，远快于传统精确求解器
多割问题是具有广泛应用的NP难组合优化问题，涵盖生物信息学、数据挖掘和计算机视觉等领域。现有图神经网络虽已用于该问题，但可进一步针对其目标函数与约束进行优化。本文提出一种新架构：仅在边上传递特征，消息计算基于图中的三角形结构。在包含多达200个节点的合成与真实世界实例上实验表明，该方法在解质量上超越当前最先进的启发式求解器，同时保持可接受的运行时间。某些实例中，本方法可在数秒内找到最优解，而精确求解器需数小时才能找到并验证最优性。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。