# Predicting Winning Regions in Parity Games via Graph Neural Networks (Extended Abstract)

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 23 references that are in the map.
- First posted on arXiv 18 Oct 2022.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Relational inductive biases, deep learning, and graph networks](https://mlsanity.com/paper/1806.01261/) (2018)
- [Practical Synthesis of Reactive Systems from LTL Specifications via Parity Games](https://mlsanity.com/paper/1903.12576/) (2019)
- [Oink: an Implementation and Evaluation of Modern Parity Game Solvers](https://mlsanity.com/paper/1801.03859/) (2018)
- [Efficient Parallel Strategy Improvement for Parity Games](https://mlsanity.com/paper/1705.02313/) (2017)
- [Synthesizing Optimally Resilient Controllers](https://mlsanity.com/paper/1709.04854/) (2017)
- [Easy to Win, Hard to Master: Optimal Strategies in Parity Games with Costs](https://mlsanity.com/paper/1604.05543/) (2016)
- [Parity Games with Weights](https://mlsanity.com/paper/1804.06168/) (2018)

## Abstract (arXiv)

Solving parity games is a major building block for numerous applications in reactive program verification and synthesis. While they can be solved efficiently in practice, no known approach has a polynomial worst-case runtime complexity. We present a incomplete polynomial-time approach to determining the winning regions of parity games via graph neural networks. Our evaluation on 900 randomly generated parity games shows that this approach is effective and efficient in practice. It correctly determines the winning regions of ~60% of the games in our data set and only incurs minor errors in the remaining ones. We believe that this approach can be extended to efficiently solve parity games as well.