Learning to Partition Graphs: A Systematic Review of GNN and Reinforcement Learning Approaches and Their Theoretical Limits
Learning to Partition Graphs: A Systematic Review of GNN and Reinforcement Learning Approaches and Their Theoretical Limits
Abbas Jafarzadeh1 Morteza Khani Dehnoi2
1) Department of Mathematics, Faculty of Engineering, Quchan University of Technology, Quchan, Iran,
2) Department of Computer Engineering, Faculty of Electrical and Computer Engineering, Quchan University of Technology, Quchan, Iran,
IOI Code
:
ACCA-ACAHBC
Publication :
4th International Congress on Science, engineering & New Technologies(secongress.com)
Abstract :
Graph partitioning is often treated as a solved problem in practice, yet no partitioner generalizes reliably across workloads, and the field has increasingly turned to learned components to close this gap. This review synthesizes ten studies published between 2019 and 2026 that apply graph neural networks (GNNs) and reinforcement learning to the graph partitioning problem. Searches were conducted in IEEE Xplore, ACM Digital Library, ScienceDirect, and arXiv under the PRISMA protocol; of the ten included studies, eight are primary learning-based investigations and two are review or framework papers used for comparative and theoretical context. Three paradigms recur across the learning-based corpus: supervised or semi-supervised labeling, unsupervised or self-supervised loss minimization, and reinforcement learning, with GNNs serving as the shared architectural core in most recent methods. The central finding is not architectural but theoretical: none of the eight learning-based studies establishes a non-trivial bound on the distance between its output and the optimal cut, and evaluations remain confined to empirical comparisons against METIS or best-known solutions. This absence of guaranteed proximity to the optimum is what separates learned partitioners from the algorithmic tradition they seek to replace. The review closes by proposing that spectral bounds be integrated into learning objectives and that evaluation practices shift from relative improvement to absolute distance from computable lower bounds.
Keywords : graph partitioning graph neural network reinforcement learning combinatorial optimization systematic review