نمایش چکیده فارسی

Learning to Partition Graphs: A Systematic Review of GNN and Reinforcement Learning Approaches and Their Theoretical Limits

Abbas Jafarzadeh1 Morteza Khani Dehnoi2

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


زبان مقاله : انگلیسی
محور مقاله : مهندسی کامپیوتر
محل انتشار : چهارمین کنگره بین المللی علوم، مهندسی و فن آوری های نو
آدرس وب سایت کنفرانس : secongress.com
کد IOI مقاله : ACCA-ACAHBC
لینک مستقیم مقاله : https://isnac.ir/ACCA-ACAHBC
نمایش چکیده فارسی : https://isnac.ir/SA/ACCA-ACAHBC

سایر مقالات محل انتشار
  1. همگرایی نهادی و کارایی فناورانه در توسعه شهر هوشمند: تحلیل تطبیقی مدل‌های آسیایی
  2. بهینه‌سازی استوار و چندمرحله‌ای تصادفی برای کربن‌زدایی عمیق و استراتژی سبد محصولات در پتروپالایشگاه‌های یکپارچه تحت عدم قطعیت عمیق
  3. شناسایی فن آوری‌های نوین و اولویت‌بندی آنها برای استفاده در مدیریت نگهداشت تجهیزات دریایی و بندری؛ مطالعه موردی بندر چابهار
  4. A Review of Recent Advances in Nanoparticle-Enhanced 1–3 Piezoelectric Composite Sensors for High-Sensitivity and Broadband Medical Imaging
  5. The dawn of a new generation of CNC on the path to sustainable, precise production (smart machining)
  6. Optimization of CNC machining parameters with the aim of increasing surface quality and reducing production time
  7. The role of space and place in the formation of psychological behaviors
  8. Design and Analysis of Combined Power Amplifiers (Combined PAs) Using Nonlinear Structures: From Circuit Implementation to Spectral-Energy Efficiency Evaluation in Hybrid-Beamforming MIMO Systems
  9. Power Management Strategies Incorporating Thermal Considerations for Integrated Power Amplifiers in Digital Phased-Array Systems
  10. Design and Optimization of a Sub-threshold Differential Amplifier for Ultra-low-power Biosignal Processing Applications
  11. Comparative Analysis and Performance Enhancement of FinFET-Based Differential Amplifiers for High-Speed Telecommunication Systems
  12. Design of a High-Linearity Power Amplifier Using Feedback Structures at High Frequencies
  13. Quantum Symmetry and Compactness in Graphs: A Convex-Geometric Approach
  14. Green Entrepreneurship and the Transition to a Sustainable Economy: A Conceptual Framework for Transformative Transition Capacity
  15. A Review of Thermoelectric Energy Harvesting Circuits and Methods for Self-Powered Wireless Sensor Nodes and the Internet of Things