pith. machine review for the scientific record. sign in

arxiv: 2605.12427 · v1 · submitted 2026-05-12 · 💻 cs.LG · math.CO

Recognition: no theorem link

Learning Minimally Rigid Graphs with High Realization Counts

Jan Legersk\'y, Jan Rube\v{s}, Oleksandr Slyvka, Rodrigo Alves

Pith reviewed 2026-05-13 04:53 UTC · model grok-4.3

classification 💻 cs.LG math.CO
keywords minimally rigid graphsrealization countsHenneberg movesreinforcement learningGraph Isomorphism Networkrigidity theorycombinatorial search
0
0 comments X

The pith

Reinforcement learning discovers minimally rigid graphs with record realization counts.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes a reinforcement learning approach to construct minimally rigid graphs that admit many distinct realizations from given edge lengths. By building graphs through successive Henneberg moves and training a policy to maximize the count of those realizations, the method avoids exhaustive enumeration of the enormous space of possible graphs. It recovers all known optimal graphs for the planar case and produces new graphs that improve the best known bounds for the spherical case. A reader should care because this shows how machine learning can tackle extremal combinatorial problems in geometry where direct search fails.

Core claim

Using the Deep Cross-Entropy Method with a Graph Isomorphism Network encoder and an equivariant action head, the authors train a policy that selects 0- and 1-extensions to build minimally rigid graphs. The resulting graphs match the known maximum realization counts in the plane and set new records on the sphere, providing explicit examples that exceed prior bounds.

What carries the argument

A policy network based on a Graph Isomorphism Network that encodes the current graph and outputs probabilities over possible Henneberg moves, optimized directly on the realization-count reward.

If this is right

  • New explicit graphs with higher spherical realization counts tighten the known bounds in rigidity theory.
  • The method provides a scalable way to explore larger minimally rigid graphs beyond what enumeration can reach.
  • Similar reinforcement learning setups can address other optimization problems involving counting geometric configurations.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • These high-count graphs could inform the design of mechanisms or linkages that have many possible configurations.
  • Patterns in the discovered graphs might reveal combinatorial reasons for high realization numbers that could lead to theoretical constructions.
  • Applying the same approach in three dimensions or to other rigidity models could uncover analogous extremal examples.

Load-bearing premise

The reinforcement learning policy, guided by the chosen network and reward, can reach or come close to the global maximum realization counts without systematic search bias.

What would settle it

An exhaustive search over all minimally rigid graphs of a given size that identifies one with a higher realization count than any found by the trained policy.

read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 2 minor

Summary. The paper proposes a reinforcement-learning method based on the Deep Cross-Entropy Method, using a Graph Isomorphism Network encoder and a permutation-equivariant action head, to construct minimally rigid graphs via successive 0- and 1-extensions (Henneberg moves). The objective is to maximize the number of realizations (up to rigid motions) of the resulting graphs; the authors report that the procedure recovers the known optimal planar realization counts and produces new graphs that improve the best-known spherical realization counts.

Significance. If the reported counts are accurate and the search is not systematically biased, the work supplies a practical, scalable heuristic for an extremal combinatorial problem whose exhaustive enumeration is infeasible. Matching known planar optima provides an internal consistency check, while the new spherical records would furnish concrete examples that could stimulate further theoretical investigation of realization-count bounds.

major comments (3)
  1. [Experimental results] The manuscript does not describe the concrete procedure used to compute and verify realization counts (algebraic, numerical, or combinatorial). Because the central empirical claims rest on these counts, the experimental section must specify the algorithm, any software libraries, termination criteria, and cross-checks against known small-n optima.
  2. [Method and training procedure] No analysis is given of possible bias induced by the GIN encoder or the equivariant action head. While the method recovers known planar maxima, the absence of ablations or comparisons with exhaustive enumeration for small n leaves open the possibility that higher-count graphs are systematically missed; this directly affects the credibility of the new spherical records.
  3. [Results] The new record graphs are asserted but not exhibited. The results section should supply explicit edge lists (or adjacency matrices) together with the precise realization counts obtained and the previous best bounds they surpass, each accompanied by a citation.
minor comments (2)
  1. [Introduction] Define the precise geometric setting (planar vs. spherical) and the corresponding realization-count invariants at the first use in the introduction.
  2. [Figures] Add vertex and edge labels to any illustrative figures of constructed graphs so that the Henneberg sequence can be reconstructed by the reader.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the careful and constructive review. The comments highlight important omissions in the experimental description, potential methodological biases, and the need for explicit data on new results. We address each point below and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: [Experimental results] The manuscript does not describe the concrete procedure used to compute and verify realization counts (algebraic, numerical, or combinatorial). Because the central empirical claims rest on these counts, the experimental section must specify the algorithm, any software libraries, termination criteria, and cross-checks against known small-n optima.

    Authors: We agree that the procedure for computing realization counts must be fully specified. In the revised manuscript we will add a subsection detailing an algebraic approach that solves the system of squared-distance equations using Groebner bases (implemented in Macaulay2) together with numerical cross-validation via homotopy continuation in Bertini. Termination criteria will be stated as stabilization of the number of distinct real solutions across 500 random edge-length perturbations; we will also report explicit reproduction of all known planar optima for n ≤ 10 as a sanity check. revision: yes

  2. Referee: [Method and training procedure] No analysis is given of possible bias induced by the GIN encoder or the equivariant action head. While the method recovers known planar maxima, the absence of ablations or comparisons with exhaustive enumeration for small n leaves open the possibility that higher-count graphs are systematically missed; this directly affects the credibility of the new spherical records.

    Authors: We acknowledge the absence of explicit bias analysis. In the revision we will add a comparison against exhaustive enumeration for all minimally rigid graphs on n ≤ 7 vertices, confirming that the learned policy recovers every known maximum. We will also include a short discussion of how the permutation-equivariant action head and GIN invariance reduce structural bias, supported by the perfect recovery of planar optima. Full architecture ablations are computationally expensive and will be noted as future work rather than performed exhaustively in this revision. revision: partial

  3. Referee: [Results] The new record graphs are asserted but not exhibited. The results section should supply explicit edge lists (or adjacency matrices) together with the precise realization counts obtained and the previous best bounds they surpass, each accompanied by a citation.

    Authors: We agree that the new record graphs must be exhibited for reproducibility. The revised manuscript will include a table (or appendix) listing the edge sets of all reported spherical-record graphs, the exact realization counts obtained, the previous best-known bounds, and the corresponding literature citations. revision: yes

Circularity Check

0 steps flagged

No circularity: empirical RL search validated against external benchmarks

full rationale

The paper describes a computational search procedure that uses reinforcement learning (Deep Cross-Entropy Method with GIN policy) to construct minimally rigid graphs via Henneberg moves and maximize realization counts. All claims rest on concrete empirical outputs—graphs that match known planar optima and improve spherical bounds—rather than any mathematical derivation, prediction, or first-principles result. No step reduces by the paper's own equations or self-citations to a fitted parameter or input quantity by construction; the method is a heuristic optimizer evaluated against independently known external results, rendering the work self-contained.

Axiom & Free-Parameter Ledger

1 free parameters · 1 axioms · 0 invented entities

The approach rests on standard domain assumptions from rigidity theory and standard RL machinery; no new entities are introduced and free parameters are the usual RL hyperparameters not detailed in the abstract.

free parameters (1)
  • RL training hyperparameters
    Learning rates, batch sizes, and reward scaling typical of Deep Cross-Entropy Method; not specified in abstract.
axioms (1)
  • domain assumption 0- and 1-extensions (Henneberg moves) preserve minimal rigidity
    Invoked as the construction primitive; standard result in rigidity theory.

pith-pipeline@v0.9.0 · 5436 in / 1260 out tokens · 59099 ms · 2026-05-13T04:53:15.667613+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

60 extracted references · 60 canonical work pages

  1. [1]

    2021 , doi =

    Wagner, Adam Zsolt , title =. 2021 , doi =

    work page 2021

  2. [2]

    2025 , doi =

    Mathematical exploration and discovery at scale , author=. 2025 , doi =

    work page 2025

  3. [3]

    SIAM Journal on Applied Algebra and Geometry , volume =

    Capco, José and Gallet, Matteo and Grasegger, Georg and Koutschan, Christoph and Lubbes, Niels and Schicho, Josef , title =. SIAM Journal on Applied Algebra and Geometry , volume =. 2018 , doi =

    work page 2018

  4. [4]

    2024 , note =

    Jose Capco , title =. 2024 , note =

    work page 2024

  5. [5]

    2025 , url =

    Jan Rubeš , title =. 2025 , url =

    work page 2025

  6. [6]

    2025 , doi =

    Grasegger, Georg , title =. 2025 , doi =

    work page 2025

  7. [7]

    2018 , doi =

    Zhang, Chiyuan and Vinyals, Oriol and Munos, Rémi and Bengio, Samy , title =. 2018 , doi =

    work page 2018

  8. [8]

    2019 , note =

    Omry Yadan , title =. 2019 , note =

    work page 2019

  9. [9]

    Zaharia, Matei A. and Chen, Andrew and Davidson, Aaron and Ghodsi, Ali and Hong, Sue Ann and Konwinski, Andy and Murching, Siddharth and Nykodym, Tomas and Ogilvie, Paul and Parkhe, Mani and Xie, Fen and Zumar, Corey , journal =

    work page

  10. [10]

    Proceedings of the International Conference on Learning Representations (ICLR) , year =

    Keyulu Xu and Weihua Hu and Jure Leskovec and Stefanie Jegelka , title =. Proceedings of the International Conference on Learning Representations (ICLR) , year =

    work page

  11. [11]

    doi:10.1109/icassp39728.2021.9413523 , booktitle=

    Huang, Ningyuan Teresa and Villar, Soledad , year=. doi:10.1109/icassp39728.2021.9413523 , booktitle=

    work page doi:10.1109/icassp39728.2021.9413523 2021

  12. [12]

    Temporal Graph Learning Workshop @ KDD , year=

    Matthias Fey and Jinu Sunil and Akihiro Nitta and Rishi Puri and Manan Shah and Bla. Temporal Graph Learning Workshop @ KDD , year=

    work page

  13. [13]

    and Laurent, Thomas and Bengio, Yoshua and Bresson, Xavier , title =

    Dwivedi, Vijay Prakash and Joshi, Chaitanya K. and Laurent, Thomas and Bengio, Yoshua and Bresson, Xavier , title =. Journal of Machine Learning Research (JMLR) , volume =. 2022 , url =

    work page 2022

  14. [14]

    ICLR Workshop on Representation Learning on Graphs and Manifolds , year =

    Errica, Federico and Podda, Marco and Bacciu, Davide and Micheli, Alessio , title =. ICLR Workshop on Representation Learning on Graphs and Manifolds , year =

    work page

  15. [15]

    Advances in Neural Information Processing Systems (NeurIPS) , editor =

    Yuning You and Tianlong Chen and Yongduo Sui and Ting Chen and Zhangyang Wang and Yang Shen , title =. Advances in Neural Information Processing Systems (NeurIPS) , editor =. 2020 , publisher =

    work page 2020

  16. [16]

    ACM Transactions on Mathematical Software , volume =

    Jan Verschelde , title =. ACM Transactions on Mathematical Software , volume =. 1999 , doi =

    work page 1999

  17. [17]

    Emiris and Josef Schicho , title =

    Evangelos Bartzos and Ioannis Z. Emiris and Josef Schicho , title =. Applied Algebra and Engineering Communications , volume =. 2020 , doi =

    work page 2020

  18. [18]

    Journal of the London Mathematical Society , volume =

    Oliver Clarke and Sean Dewar and Daniel Green Tripp and James Maxwell and Anthony Nixon and Yue Ren and Ben Smith , title =. Journal of the London Mathematical Society , volume =. doi:10.1112/jlms.70438 , year =

    work page doi:10.1112/jlms.70438

  19. [19]

    Owen , title =

    Bill Jackson and John C. Owen , title =. Discrete Applied Mathematics , volume =. 2019 , doi =

    work page 2019

  20. [20]

    Zeitschrift für Angewandte Mathematik und Mechanik (ZAMM) , volume =

    Pollaczek-Geiringer, Hilda , title =. Zeitschrift für Angewandte Mathematik und Mechanik (ZAMM) , volume =. 1927 , doi =

    work page 1927

  21. [21]

    Journal of Engineering Mathematics , volume =

    Laman, Gerard , title =. Journal of Engineering Mathematics , volume =. 1970 , doi =

    work page 1970

  22. [22]

    2018 , publisher=

    Reinforcement Learning: An Introduction , author=. 2018 , publisher=

    work page 2018

  23. [23]

    and Kroese, Dirk P

    Rubinstein, Reuven Y. and Kroese, Dirk P. , year=

    work page

  24. [24]

    and Legerský, Jan and Tsigaridas, Elias , title =

    Bartzos, Evangelos and Emiris, Ioannis Z. and Legerský, Jan and Tsigaridas, Elias , title =. Journal of Symbolic Computation , volume =. 2021 , doi =

    work page 2021

  25. [25]

    2019 , doi =

    Soft Actor-Critic Algorithms and Applications , author=. 2019 , doi =

    work page 2019

  26. [26]

    International Conference on Learning Representations (ICLR) , year =

    Hu, Weihua and Liu, Bowen and Gomes, Joseph and Zitnik, Marinka and Liang, Percy and Pande, Vijay and Leskovec, Jure , title =. International Conference on Learning Representations (ICLR) , year =

    work page

  27. [27]

    and Smola, Alexander J

    Zaheer, Manzil and Kottur, Satwik and Ravanbakhsh, Siamak and Poczos, Barnabas and Salakhutdinov, Russ R. and Smola, Alexander J. , booktitle =

    work page

  28. [28]

    2024 , doi =

    Mehrabian, Abbas and Anand, Ankit and others , booktitle =. 2024 , doi =

    work page 2024

  29. [29]

    Machine Learning , year =

    Angileri, Flora and Lombardi, Giulia and Fois, Andrea and Faraone, Renato and Metta, Carlo and Salvi, Michele and Bianchi, Luigi Amedeo and Fantozzi, Marco and Galfrè, Silvia Giulia and Pavesi, Daniele and Parton, Maurizio and Morandin, Francesco , title =. Machine Learning , year =. doi:10.1007/s10994-025-06890-2 , publisher =

    work page doi:10.1007/s10994-025-06890-2

  30. [30]

    Ellenberg and Adam Zsolt Wagner and Geordie Williamson , year=

    François Charton and Jordan S. Ellenberg and Adam Zsolt Wagner and Geordie Williamson , year=

    work page

  31. [31]

    2026 , note =

    Katie Clinch and Dániel Garamvölgyi and John Haslegrave and Tony Huynh and Jan Legerský and Anthony Nixon , title =. 2026 , note =

    work page 2026

  32. [32]

    Flexible realizations existence:

    Petr Laštovička and Jan Legerský , year =. Flexible realizations existence:

    work page

  33. [33]

    Matthias Adrian-Himmelmann and Matteo Gallet and Georg Grasegger and Jan Legerský , year =

    work page

  34. [34]

    Transactions of the American Mathematical Society , VOLUME =

    Asimow, Leonard and Roth, Ben , TITLE =. Transactions of the American Mathematical Society , VOLUME =. 1978 , PAGES =

    work page 1978

  35. [35]

    2008 , doi =

    Pebble game algorithms and sparse graphs , journal =. 2008 , doi =

    work page 2008

  36. [36]

    GitHub repository , note =

    Martin Larsson , title =. GitHub repository , note =. 2020 , publisher =

    work page 2020

  37. [37]

    Algebraic Combinatorics , pages =

    Dewar, Sean and Grasegger, Georg , title =. Algebraic Combinatorics , pages =. 2024 , publisher =

    work page 2024

  38. [38]

    The Electronic Journal of Combinatorics , volume =

    Gallet, Matteo and Grasegger, Georg and Schicho, Josef , title =. The Electronic Journal of Combinatorics , volume =. 2020 , doi =

    work page 2020

  39. [39]

    Discrete & Computational Geometry , volume =

    Georg Grasegger and Jan Legerský and Josef Schicho , title =. Discrete & Computational Geometry , volume =. 2019 , doi =

    work page 2019

  40. [40]

    Bülthoff and Paolo Robuffo Giordano , title =

    Daniel Zelazo and Antonio Franchi and Heinrich H. Bülthoff and Paolo Robuffo Giordano , title =. The International Journal of Robotics Research , volume =. 2015 , doi =

    work page 2015

  41. [41]

    and Francis, Bruce A

    Krick, Laura and Broucke, Mireille E. and Francis, Bruce A. , title =. International Journal of Control , volume =. 2009 , publisher =

    work page 2009

  42. [42]

    SIAM Journal on Optimization, 20(6) , Pages =

    Zhisu Zhu and Anthony Man-Cho So and Yinyu Ye , Title =. SIAM Journal on Optimization, 20(6) , Pages =

    work page

  43. [43]

    Husty , Title =

    Dominic Walter and Manfred L. Husty , Title =

    work page

  44. [44]

    and Csermely, Peter , title =

    G\'asp\'ar, Merse E. and Csermely, Peter , title =. Briefings in Functional Genomics , volume =. 2012 , doi =

    work page 2012

  45. [45]

    and Duxbury, Phillip M

    Billinge, Simon J.L. and Duxbury, Phillip M. and Gon. Assigned and unassigned distance geometry: applications to biological molecules and nanostructures , journal=. 2016 , volume=

    work page 2016

  46. [46]

    Tensegrity Structures Design Methods , publisher =

    Vilnay, Oren and Chernin, Leon and Vilnay, Margi , year =. Tensegrity Structures Design Methods , publisher =

    work page

  47. [47]

    and Graver, J

    Baglivo, J. and Graver, J. , Title =

    work page

  48. [48]

    Borcea and Ileana Streinu , Title =

    Ciprian S. Borcea and Ileana Streinu , Title =. Discrete & Computational Geometry , Pages =. 2004 , doi =

    work page 2004

  49. [49]

    Experimental Mathematics , volume =

    Georg Grasegger and Christoph Koutschan and Elias Tsigaridas , title =. Experimental Mathematics , volume =. 2020 , doi =

    work page 2020

  50. [50]

    Emiris and Raimundas Vidunas , title =

    Evangelos Bartzos and Ioannis Z. Emiris and Raimundas Vidunas , title =. Discrete & Computational Geometry , volume =. 2022 , doi =

    work page 2022

  51. [51]

    Emiris and Charalambos Tzamos , title =

    Evangelos Bartzos and Ioannis Z. Emiris and Charalambos Tzamos , title =. Discrete Applied Mathematics , volume =. 2023 , doi =

    work page 2023

  52. [52]

    2025 , doi =

    Computing the number of realisations of a rigid graph , author=. 2025 , doi =

    work page 2025

  53. [53]

    Mathematics of Computation , volume =

    Georg Grasegger and Boulos El Hilany and Niels Lubbes , title =. Mathematics of Computation , volume =. 2024 , doi =

    work page 2024

  54. [54]

    John and Jessica Sidman (Eds.) , title =

    Meera Sitharam and Audrey St. John and Jessica Sidman (Eds.) , title =. 2018 , doi =

    work page 2018

  55. [55]

    Triangle-Decomposable Graphs for Isoperimetric Robots , year=

    Usevitch, Nathan and Weaver, Isaac and Usevitch, James , journal=. Triangle-Decomposable Graphs for Isoperimetric Robots , year=

    work page

  56. [56]

    2021 , volume =

    Zhang, Ran and Auzinger, Thomas and Bickel, Bernd , title =. 2021 , volume =. doi:10.1145/3453477 , journal =

    work page doi:10.1145/3453477 2021

  57. [57]

    PyTorch 2: Faster machine learning through dynamic Python bytecode transformation and graph compilation,

    Ansel, Jason and Yang, Edward and He, Horace and others , booktitle =. doi:10.1145/3620665.3640366 , publisher =

    work page doi:10.1145/3620665.3640366

  58. [58]

    1903 , publisher =

    Lebrecht Henneberg , title =. 1903 , publisher =

    work page 1903

  59. [59]

    2025 , doi =

    AlphaEvolve: A coding agent for scientific and algorithmic discovery , author=. 2025 , doi =

    work page 2025

  60. [60]

    2026 , howpublished =

    Project Repository --- Code and hyperparameter configurations , author =. 2026 , howpublished =

    work page 2026