Graph Neural Network Applications in Electronic Design Automation - Helaly, Abdelrahaman Wael (AUC Knowledge Fountain, 2026)
Multipatterning is an essential decomposition strategy in electronic design automation (EDA) that overcomes lithographic limitations when printing dense circuit layouts. Although heuristic-based backtracking and SAT solvers can address these challenges, they often struggle to simultaneously handle both complex constraints and secondary objectives such as mask balance. In this thesis, we present a comprehensive study of AI-driven approaches for autonomous graph coloring in multipatterning contexts, systematically comparing Graph Neural Networks (GNN), reinforcement learning (RL), and large language models (LLMs) across initial coloring and solution refinement tasks. We cast multipatterning as a variant of constrained graph coloring with the primary objective of minimizing feature violations and secondary objectives including balancing features across masks. The pipeline integrates three main components: (1) A GNN-based model, trained in an unsupervised manner to generate initial color predictions, which are refined by (2) Algorithmic refinement strategies (a GNN-based heuristic and simulated annealing) or (3) Learning-based refinement (reinforcement learning and large language models) that together enhance solution quality and balance. Lastly, we propose an agentic pipeline that autonomously orchestrates multiple AI components through structured tool interactions, enabling dynamic strategy selection and adaptation to novel constraints without human intervention. Experimental evaluations on both proprietary datasets and publicly available open-source layouts demonstrate that our workflow achieves accurate and balanced coloring assignments with high success rates.