RIDGECUT: Learning Graph Partitioning with Rings and Wedges

RidgeCut is a novel reinforcement learning framework designed for graph partitioning, specifically addressing the Normalized Cut problem by constraining the action space to enhance structure-aware partitioning. It leverages domain knowledge of urban road topology, utilizing transformer-based policies and Proximal Policy Optimization to achieve efficient learning. Experimental results indicate that RidgeCut outperforms existing methods in terms of normalized cuts and demonstrates strong inductive generalization across various graph sizes, making it a valuable approach for practitioners seeking to incorporate structural priors into graph-based optimization tasks.