Learning Minimally Rigid Graphs with High Realization Counts

• URL: http://arxiv.org/abs/2605.12427v1
• Date: Tue, 12 May 2026 17:23:30 GMT
• Title: Learning Minimally Rigid Graphs with High Realization Counts
• Abstract summary: For rigid graphs, the same edge-length data can admit multiple realizations (up to translations and rotations)<n>Finding graphs with exceptionally many realizations is an extremal problem in rigidity theory.<n>We propose a reinforcement-learning approach that constructs minimally rigid graphs via 0- and 1-extensions, also known as Henneberg moves.
• Score: 21.481970640320856
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• GraphK: Variable-Size Graph Generation with Efficient Edge Construction [0.27998963147546135]
  We present GraphK, a novel encoder-sampler-decoder framework for graph generation.<n>By learning permutation-invariant latent representations, GraphK generalizes across graph sizes and structures.<n>Experiments on synthetic and real-world datasets show that GraphK outperforms existing methods.
  arXiv  Detail & Related papers  (2026-08-19T10:34:17Z)
• Leveraging Low-rank Factorizations of Conditional Correlation Matrices in Graph Learning [46.49143964254245]
  This paper addresses the problem of learning an undirected graph from data gathered at each nodes.<n>The corresponding graph learning problem then scales to the squares of the number of variables (nodes)<n>We propose a graph learning framework that leverages a low-rank factorization of the conditional correlation matrix.
  arXiv  Detail & Related papers  (2025-06-12T12:13:11Z)
• ExMAG: Learning of Maximally Ancestral Graphs [2.740961764574832]
  We propose a score-based branch-and-cut algorithm for learning maximally ancestral graphs.<n>The algorithm produces more accurate results than state-of-the-art methods, while being faster to run on small and medium-sized synthetic instances.
  arXiv  Detail & Related papers  (2025-03-11T10:08:39Z)
• Polynomial Graphical Lasso: Learning Edges from Gaussian Graph-Stationary Signals [18.45931641798935]
  This paper introduces Polynomial Graphical Lasso (PGL), a new approach to learning graph structures from nodal signals. Our key contribution lies in the signals as Gaussian and stationary on the graph, enabling the development of a graph-learning lasso.
  arXiv  Detail & Related papers  (2024-04-03T10:19:53Z)
• Sparse Training of Discrete Diffusion Models for Graph Generation [45.103518022696996]
  We introduce SparseDiff, a novel diffusion model based on the observation that almost all large graphs are sparse. By selecting a subset of edges, SparseDiff effectively leverages sparse graph representations both during the noising process and within the denoising network. Our model demonstrates state-of-the-art performance across multiple metrics on both small and large datasets.
  arXiv  Detail & Related papers  (2023-11-03T16:50:26Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  We introduce a novel all-pair message passing scheme for efficiently propagating node signals between arbitrary nodes. The efficient computation is enabled by a kernerlized Gumbel-Softmax operator. Experiments demonstrate the promising efficacy of the method in various tasks including node classification on graphs.
  arXiv  Detail & Related papers  (2023-06-14T09:21:15Z)
• Gradient scarcity with Bilevel Optimization for Graph Learning [0.0]
  gradient scarcity occurs when learning graphs by minimizing a loss on a subset of nodes causes edges between unlabelled nodes that are far from labelled ones to receive zero gradients. We give a precise mathematical characterization of this phenomenon, and prove it also emerges in bilevel optimization. To alleviate this issue, we study several solutions: we propose to resort to latent graph learning using a Graph-to-Graph model (G2G), graph regularization to impose a prior structure on the graph, or optimizing on a larger graph than the original one with a reduced diameter.
  arXiv  Detail & Related papers  (2023-03-24T12:37:43Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  We propose a bi-level optimization approach for learning the optimal graph structure. We also explore a low-rank approximation model for further reducing the time complexity.
  arXiv  Detail & Related papers  (2022-05-06T03:37:00Z)
• Generalized Dirichlet Energy and Graph Laplacians for Clustering Directed and Undirected Graphs [2.4118754741048987]
  Clustering in directed graphs remains a fundamental challenge due to the asymmetry in edge connectivity.<n>We introduce the generalized Dirichlet energy (GDE), a novel energy functional that extends the classical Dirichlet energy.<n>We propose the generalized spectral clustering (GSC) method that enables principled clustering of weakly connected digraphs.
  arXiv  Detail & Related papers  (2022-03-07T09:18:42Z)
• Learning Graphs from Smooth Signals under Moment Uncertainty [23.868075779606425]
  We consider the problem of inferring the graph structure from a given set of graph signals. Traditional graph learning models do not take this distributional uncertainty into account.
  arXiv  Detail & Related papers  (2021-05-12T06:47:34Z)
• Multilayer Clustered Graph Learning [66.94201299553336]
  We use contrastive loss as a data fidelity term, in order to properly aggregate the observed layers into a representative graph. Experiments show that our method leads to a clustered clusters w.r.t. We learn a clustering algorithm for solving clustering problems.
  arXiv  Detail & Related papers  (2020-10-29T09:58:02Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  We introduce a novel learning problem for dense subgraph discovery. We first propose a edge-time algorithm that obtains a nearly-optimal solution with high probability. We then design a more scalable algorithm with a theoretical guarantee.
  arXiv  Detail & Related papers  (2020-06-24T11:37:33Z)
• Iterative Deep Graph Learning for Graph Neural Networks: Better and Robust Node Embeddings [53.58077686470096]
  We propose an end-to-end graph learning framework, namely Iterative Deep Graph Learning (IDGL) for jointly and iteratively learning graph structure and graph embedding. Our experiments show that our proposed IDGL models can consistently outperform or match the state-of-the-art baselines.
  arXiv  Detail & Related papers  (2020-06-21T19:49:15Z)
• Graph Pooling with Node Proximity for Hierarchical Representation Learning [80.62181998314547]
  We propose a novel graph pooling strategy that leverages node proximity to improve the hierarchical representation learning of graph data with their multi-hop topology. Results show that the proposed graph pooling strategy is able to achieve state-of-the-art performance on a collection of public graph classification benchmark datasets.
  arXiv  Detail & Related papers  (2020-06-19T13:09:44Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.