论文标题
学习使用边缘加权卷积神经网络有效地解决最低成本多功能
Learning to solve Minimum Cost Multicuts efficiently using Edge-Weighted Graph Convolutional Neural Networks
论文作者
论文摘要
最低成本多功能问题是分区的NP/APX-HARD组合优化问题，该问题是将实价的边缘加权图分区，例如最大程度地减少分区的总成本。尽管在组合优化的背景下，图形卷积神经网络（GNN）已被证明是有希望的，但它们中的大多数仅针对正值边缘重量量身定制或测试，即它们不符合多通问题的性质。因此，我们调整了各种GNN体系结构，包括图形卷积网络，签名的图形卷积网络和图形等构型网络，以促进实用值的有效编码。此外，我们将多项式ILP约束对多项式程序进行重新制定为损失函数，允许以可扩展的方式学习可行的多功能解决方案。因此，我们为端到端的可训练多功能提供了第一种方法。我们的发现支持GNN方法可以在实践中产生良好的解决方案，同时与LP求解器相比，提供较低的计算时间，并在很大程度上提高了可伸缩性，并优化了启发式方法，尤其是在考虑大型实例时。
The minimum cost multicut problem is the NP-hard/APX-hard combinatorial optimization problem of partitioning a real-valued edge-weighted graph such as to minimize the total cost of the partition. While graph convolutional neural networks (GNN) have proven to be promising in the context of combinatorial optimization, most of them are only tailored to or tested on positive-valued edge weights, i.e. they do not comply to the nature of the multicut problem. We therefore adapt various GNN architectures including Graph Convolutional Networks, Signed Graph Convolutional Networks and Graph Isomorphic Networks to facilitate the efficient encoding of real-valued edge costs. Moreover, we employ a reformulation of the multicut ILP constraints to a polynomial program as loss function that allows to learn feasible multicut solutions in a scalable way. Thus, we provide the first approach towards end-to-end trainable multicuts. Our findings support that GNN approaches can produce good solutions in practice while providing lower computation times and largely improved scalability compared to LP solvers and optimized heuristics, especially when considering large instances.
