RIDGECUT: Learning Graph Partitioning with Rings and Wedges
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912532173684736 |
|---|---|
| author | Jiang, Qize Pang, Linsey Gatti, Alice Aggarwal, Mahima Vantini, Giovanna Ma, Xiaosong Sun, Weiwei Medya, Sourav Chawla, Sanjay |
| author_facet | Jiang, Qize Pang, Linsey Gatti, Alice Aggarwal, Mahima Vantini, Giovanna Ma, Xiaosong Sun, Weiwei Medya, Sourav Chawla, Sanjay |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_13986 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | RIDGECUT: Learning Graph Partitioning with Rings and Wedges Jiang, Qize Pang, Linsey Gatti, Alice Aggarwal, Mahima Vantini, Giovanna Ma, Xiaosong Sun, Weiwei Medya, Sourav Chawla, Sanjay Optimization and Control Artificial Intelligence Machine Learning I.2.8 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. |
| title | RIDGECUT: Learning Graph Partitioning with Rings and Wedges |
| topic | Optimization and Control Artificial Intelligence Machine Learning I.2.8 |
| url | https://arxiv.org/abs/2505.13986 |