# Learning Minimally Rigid Graphs with High Realization Counts

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

## Key facts

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

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

- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Deep Sets](https://mlsanity.com/paper/1703.06114/) (2017)
- [A Short Tutorial on The Weisfeiler-Lehman Test And Its Variants](https://mlsanity.com/paper/2201.07083/) (2022)
- [PyG 2.0: Scalable Learning on Real World Graphs](https://mlsanity.com/paper/2507.16991/) (2025)
- [Finding Increasingly Large Extremal Graphs with AlphaZero and Tabu Search](https://mlsanity.com/paper/2311.03583/) (2023)
- [Decentralized Rigidity Maintenance Control with Range Measurements for Multi-Robot Systems](https://mlsanity.com/paper/1309.0535/) (2013)
- [The number of realizations of a Laman graph](https://mlsanity.com/paper/1701.05500/) (2017)
- [Lower bounds on the number of realizations of rigid graphs](https://mlsanity.com/paper/1710.08237/) (2017)
- [Flexible realizations existence: NP-completeness on sparse graphs and algorithms](https://mlsanity.com/paper/2412.13721/) (2024)
- [PyRigi -- a general-purpose Python package for the rigidity and flexibility of bar-and-joint frameworks](https://mlsanity.com/paper/2505.22652/) (2025)

## Abstract (arXiv)

For minimally rigid graphs, the same edge-length data can admit multiple realizations (up to translations and rotations). Finding graphs with exceptionally many realizations is an extremal problem in rigidity theory, but exhaustive search quickly becomes infeasible due to the super-exponential growth of the number of candidate graphs and the high cost of realization-count evaluation. We propose a reinforcement-learning approach that constructs minimally rigid graphs via 0- and 1-extensions, also known as Henneberg moves. We optimize realization-count invariants using the Deep Cross-Entropy Method with a policy parameterized by a Graph Isomorphism Network encoder and a permutation-equivariant extension-level action head. Empirically, our method matches the known optima for planar realization counts and improves the best known bounds for spherical realization counts, yielding new record graphs.