RIDGECUT: Learning Graph Partitioning with Rings and Wedges
This work addresses the challenge of steering reinforcement learning towards domain-appropriate outcomes in graph partitioning, with applications in transportation networks, though it is incremental as it builds on existing RL frameworks.
The paper tackled the problem of integrating domain knowledge into reinforcement learning for graph partitioning in combinatorial optimization, specifically for the Normalized Cut problem, and achieved lower normalized cuts compared to existing methods, with results aligned with expected spatial layouts.
Reinforcement Learning (RL) has proven to be a powerful tool for combinatorial optimization (CO) problems due to its ability to learn heuristics that can generalize across problem instances. However, integrating knowledge that will steer the RL framework for CO solutions towards domain appropriate outcomes remains a challenging task. In this paper, we propose RIDGECUT, the first RL framework that constrains the action space to enforce structure-aware partitioning in the Normalized Cut problem. Using transportation networks as a motivating example, we introduce a novel concept that leverages domain knowledge about urban road topology -- where natural partitions often take the form of concentric rings and radial wedges. Our method reshapes the graph into a linear or circular structure to simplify the partitioning task so that we can apply sequential transformers and enables efficient learning via Proximal Policy Optimization. The resulting partitions are not only aligned with expected spatial layouts but also achieve lower normalized cuts compared to existing methods. While we focus on traffic data, our approach is broadly applicable and offers a mechanism for embedding structural priors into RL for graph partitioning.