Learning to Solve Combinatorial Graph Partitioning Problems via Efficient Exploration

Understand

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.