Learning to Solve Combinatorial Graph Partitioning Problems via Efficient Exploration
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.