论文标题
学会通过有效探索解决组合图分区问题
Learning to Solve Combinatorial Graph Partitioning Problems via Efficient Exploration
论文作者
论文摘要
从物流到自然科学，图表上的组合优化是众多现实世界应用的基础。强化学习（RL）在这种情况下表现出了特别的希望，因为它可以适应特定的问题结构，并且不需要这些问题（通常是NP）问题的预言实例。但是，最新的（SOTA）方法通常遇到严重的可伸缩性问题，这主要是由于它们在每个决策步骤中都依赖昂贵的图形神经网络（GNN）。我们介绍Ecord；一种新颖的RL算法，通过将GNN限制为单个预处理步骤，从而减轻这笔费用，然后再进入由经常性单元指导的快速作用探索阶段。在实验上，ECORD在最大切割问题上实现了用于RL算法的新SOTA，同时还提供了速度和可伸缩性的数量级提高。与最近的竞争对手相比，ECORD在500个顶点图中最多将最佳差距降低了73％，并且壁式锁定时间减少。此外，ECORD在概括到最多10000个顶点的较大图表时会保持强劲的性能。
From logistics to the natural sciences, combinatorial optimisation on graphs underpins numerous real-world applications. Reinforcement learning (RL) has shown particular promise in this setting as it can adapt to specific problem structures and does not require pre-solved instances for these, often NP-hard, problems. However, state-of-the-art (SOTA) approaches typically suffer from severe scalability issues, primarily due to their reliance on expensive graph neural networks (GNNs) at each decision step. We introduce ECORD; a novel RL algorithm that alleviates this expense by restricting the GNN to a single pre-processing step, before entering a fast-acting exploratory phase directed by a recurrent unit. Experimentally, ECORD achieves a new SOTA for RL algorithms on the Maximum Cut problem, whilst also providing orders of magnitude improvement in speed and scalability. Compared to the nearest competitor, ECORD reduces the optimality gap by up to 73% on 500 vertex graphs with a decreased wall-clock time. Moreover, ECORD retains strong performance when generalising to larger graphs with up to 10000 vertices.
