論文の概要: Learning Minimally Rigid Graphs with High Realization Counts

• arxiv url: http://arxiv.org/abs/2605.12427v1
• Date: Tue, 12 May 2026 17:23:30 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-13 21:48:57.048448
• Title: Learning Minimally Rigid Graphs with High Realization Counts
• Title（参考訳）: 高精算数を用いた最小剛グラフの学習
• Authors: Oleksandr Slyvka, Jan Rubeš, Rodrigo Alves, Jan Legerský,
• Abstract要約: 厳密なグラフの場合、同じエッジ長のデータは複数の実現(翻訳と回転)を許容できる。 例外的に多くの実現可能なグラフを見つけることは、剛性理論における極端問題である。 ヘネバーグ運動 (Henneberg move) としても知られる 0- および 1-拡張(英語版) を通した最小剛性グラフを構成する強化学習手法を提案する。
• 参考スコア（独自算出の注目度）: 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.
• Abstract（参考訳）: 最小限の厳密なグラフの場合、同じエッジ長のデータには複数の実現(翻訳と回転)がある。 例外的に多くの実現性を持つグラフを見つけることは、剛性理論における極端問題であるが、候補グラフの数が超指数的に増加することと、実現数評価のコストが高いことから、徹底的な探索はすぐに実現不可能となる。 ヘネバーグ運動 (Henneberg move) としても知られる 0- および 1-拡張(英語版) を通した最小剛性グラフを構成する強化学習手法を提案する。 グラフ同型ネットワークエンコーダと置換等価な拡張レベルアクションヘッドによってパラメータ化されたポリシーを用いたDeep Cross-Entropy Methodを用いて、実現数不変量を最適化する。 経験的に,本手法は平面現実化数に対する既知の最適値と一致し,球面実化数に対する最もよく知られた境界値を改善し,新しい記録グラフを生成する。

関連論文リスト

• Leveraging Low-rank Factorizations of Conditional Correlation Matrices in Graph Learning [46.49143964254245]
  本稿では,各ノードに収集されたデータから非方向グラフを学習する問題に対処する。 対応するグラフ学習問題は、変数の数(ノード)の平方にスケールする。 条件相関行列の低ランク分解を利用したグラフ学習フレームワークを提案する。
  論文  参考訳（メタデータ） (2025-06-12T12:13:11Z)
• ExMAG: Learning of Maximally Ancestral Graphs [2.740961764574832]
  本稿では,最大祖先グラフを学習するためのスコアベース分岐切断アルゴリズムを提案する。 このアルゴリズムは最先端の手法よりも正確な結果を生成するが、中小の合成インスタンスではより高速に動作する。
  論文  参考訳（メタデータ） (2025-03-11T10:08:39Z)
• Sparse Training of Discrete Diffusion Models for Graph Generation [45.103518022696996]
  SparseDiffは、ほとんど全ての大きなグラフがスパースであるという観察に基づく、新しい拡散モデルである。 エッジのサブセットを選択することで、SparseDiffは、ノイズ発生過程とノイズ発生ネットワーク内のスパースグラフ表現を効果的に活用する。 本モデルでは,小規模・大規模両方のデータセットにおいて,複数のメトリクスにわたる最先端性能を示す。
  論文  参考訳（メタデータ） (2023-11-03T16:50:26Z)
• Gradient scarcity with Bilevel Optimization for Graph Learning [0.0]
  勾配不足は、ノードのサブセットの損失を最小限にすることでグラフを学習する際に発生する。 我々は、この現象の正確な数学的特徴を与え、双レベル最適化にも現れることを証明した。 この問題を緩和するために,グラフ・ツー・グラフモデル(G2G)を用いた潜時グラフ学習,グラフに先行構造を課すグラフ正規化,あるいは直径を縮小した元のグラフよりも大きなグラフを最適化することを提案する。
  論文  参考訳（メタデータ） (2023-03-24T12:37:43Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  最適グラフ構造を学習するための二段階最適化手法を提案する。 また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
  論文  参考訳（メタデータ） (2022-05-06T03:37:00Z)
• Generalized Dirichlet Energy and Graph Laplacians for Clustering Directed and Undirected Graphs [2.4118754741048987]
  有向グラフのクラスタリングは、エッジ接続の非対称性のため、依然として根本的な課題である。 我々は、古典的なディリクレエネルギーを拡張する新しいエネルギー汎関数である一般化ディリクレエネルギー(GDE)を導入する。 本稿では,弱連結なダイグラフのクラスタリングを可能にする一般化スペクトルクラスタリング(GSC)手法を提案する。
  論文  参考訳（メタデータ） (2022-03-07T09:18:42Z)
• Learning Graphs from Smooth Signals under Moment Uncertainty [23.868075779606425]
  与えられたグラフ信号の集合からグラフ構造を推測する問題を検討する。 従来のグラフ学習モデルは、この分布の不確実性を考慮していない。
  論文  参考訳（メタデータ） (2021-05-12T06:47:34Z)
• Multilayer Clustered Graph Learning [66.94201299553336]
  我々は、観測された層を代表グラフに適切に集約するために、データ忠実度用語として対照的な損失を用いる。 実験により,本手法がクラスタクラスタw.r.tに繋がることが示された。 クラスタリング問題を解くためのクラスタリングアルゴリズムを学習する。
  論文  参考訳（メタデータ） (2020-10-29T09:58:02Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  我々は高密度サブグラフ発見のための新しい学習問題を導入する。 まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。 そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-06-24T11:37:33Z)
• Iterative Deep Graph Learning for Graph Neural Networks: Better and Robust Node Embeddings [53.58077686470096]
  グラフ構造とグラフ埋め込みを協調的かつ反復的に学習するための、エンドツーエンドのグラフ学習フレームワーク、すなわち、IDGL(Iterative Deep Graph Learning)を提案する。 実験の結果,提案したIDGLモデルは,最先端のベースラインを一貫して上回る,あるいは一致させることができることがわかった。
  論文  参考訳（メタデータ） (2020-06-21T19:49:15Z)
• Graph Pooling with Node Proximity for Hierarchical Representation Learning [80.62181998314547]
  本稿では,ノード近接を利用したグラフプーリング手法を提案し,そのマルチホップトポロジを用いたグラフデータの階層的表現学習を改善する。 その結果,提案したグラフプーリング戦略は,公開グラフ分類ベンチマークデータセットの集合において,最先端のパフォーマンスを達成できることが示唆された。
  論文  参考訳（メタデータ） (2020-06-19T13:09:44Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。