用强化学习构造刚性图，让相同边长有更多空间构型。
Learning Minimally Rigid Graphs with High Realization Counts
- 通过亨内伯格变换逐步构建最小刚性图
- 在平面和球面上均达到或超越现有最优记录
- 适合对几何构型与图结构关系感兴趣的研究者
对于最小刚性图，相同的边长数据可能对应多个构型（忽略平移和旋转）。寻找具有异常多构型的图是刚性理论中的极值问题，但因候选图数量呈超指数增长且构型计数代价高，穷举搜索迅速不可行。本文提出一种强化学习方法，通过0-和1-扩展（即亨内伯格变换）构建最小刚性图。采用深度交叉熵方法优化构型计数不变量，策略网络由图同构网络编码器与置换等变的扩展层级动作头组成。实验表明，该方法在平面构型计数上匹配已知最优解，在球面构型计数上优于现有最佳结果，发现新的记录图。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。