# Unsupervised Graph Neural Network Framework for Balanced Multipatterning in Advanced Electronic Design Automation Layouts

arXiv: https://arxiv.org/abs/2511.16374 · HTML: https://mlsanity.com/paper/2511.16374/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 25 references that are in the map.
- First posted on arXiv 20 Nov 2025.

## Builds on (most cited first, 15 of 15)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [AlphaEvolve: A coding agent for scientific and algorithmic discovery](https://mlsanity.com/paper/2506.13131/) (2025)
- [Principal Neighbourhood Aggregation for Graph Nets](https://mlsanity.com/paper/2004.05718/) (2020)
- [Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs](https://mlsanity.com/paper/2006.10643/) (2020)
- [Graph Colouring Meets Deep Learning: Effective Graph Neural Network Models for Combinatorial Problems](https://mlsanity.com/paper/1903.04598/) (2019)
- [Graph Coloring with Physics-Inspired Graph Neural Networks](https://mlsanity.com/paper/2202.01606/) (2022)
- [Rethinking Graph Neural Networks for the Graph Coloring Problem](https://mlsanity.com/paper/2208.06975/) (2022)
- [Cross-Modality Program Representation Learning for Electronic Design Automation with High-Level Synthesis](https://mlsanity.com/paper/2406.09606/) (2024)
- [IR-Aware ECO Timing Optimization Using Reinforcement Learning](https://mlsanity.com/paper/2402.07781/) (2024)
- [Automated Physical Design Watermarking Leveraging Graph Neural Networks](https://mlsanity.com/paper/2407.20544/) (2024)
- [Generating a Graph Colouring Heuristic with Deep Q-Learning and Graph Neural Networks](https://mlsanity.com/paper/2304.04051/) (2023)
- [Reinforcement Learning for Graph Coloring: Understanding the Power and Limits of Non-Label Invariant Representations](https://mlsanity.com/paper/2401.12470/) (2024)
- [VLSI Hypergraph Partitioning with Deep Learning](https://mlsanity.com/paper/2409.01387/) (2024)

## Abstract (arXiv)

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. In this study, we present a hybrid workflow that casts multipatterning as a variant of a constrained graph coloring problem with the primary objective of minimizing feature violations and a secondary objective of balancing the number of features on each mask. Our pipeline integrates two main components: (1) A GNN-based agent, trained in an unsupervised manner to generate initial color predictions, which are refined by (2) refinement strategies (a GNN-based heuristic and simulated annealing) that together enhance solution quality and balance. Experimental evaluation in both proprietary data sets and publicly available open source layouts demonstrate complete conflict-free decomposition and consistent color balancing. The proposed framework provides a reproducible, data-efficient and deployable baseline for scalable layout decomposition in EDA workflows.