論文の概要: Neurosymbolic Discovery of Algebraic Graph Constructions

• arxiv url: http://arxiv.org/abs/2608.08118v1
• Date: Sat, 08 Aug 2026 13:07:51 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-11 19:16:36.684133
• Title: Neurosymbolic Discovery of Algebraic Graph Constructions
• Title（参考訳）: 代数グラフ構築のニューロシンボリック発見
• Abstract要約: この生データのみを提供する場合、短い代数的記述を自動的に発見できるかどうかを問う。 本研究では,汎用的な大規模言語モデル上で,微調整や目標ごとの訓練を行わないエージェントを提案する。 提案手法は高対称性グラフ100のベンチマークで検証する。
• 参考スコア（独自算出の注目度）: 22.962110170304594
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: There are several methods for searching for graphs with prescribed properties, such as SAT solvers and specialized generators. These methods return the result as raw data: an adjacency matrix or a string encoding. The raw data certifies that the graph exists, but it does not reveal any structural properties of the graph. We ask whether one can automatically discover a short algebraic description if only this raw data is provided. We look for a description such as a Cayley graph $\mathrm{Cay}(Γ, S)$ or a lexicographic product $C_5[K_3]$. We address this question with a neurosymbolic approach. We propose an agent that runs on a general-purpose large language model with no fine-tuning or per-target training. The model interleaves reasoning with calls to the computer algebra system SageMath: it analyzes the target graph, proposes and tests candidate constructions, and revises them until the output matches the target. The agent communicates with SageMath through a Model Context Protocol (MCP) server, which we release as a general-purpose bridge. Whether a construction matches the target is checked by a single exact isomorphism test, and therefore rests on the symbolic side and not on the model. We test the approach on a benchmark of 100 highly symmetric graphs, namely two-orbit graphs on up to 25 vertices; the benchmark was fixed in advance. Our agent could find verified algebraic constructions for all of them, without falling back to raw encodings. A strong template-enumeration baseline reaches only about $20\%$, and a catalog lookup could not identify any of these graphs. However, construction quality declines when symmetry is removed. As a concrete application, we identify the smallest known counterexample to the Bernhart-Kainen dispersability conjecture, a $16$-vertex graph that enumeration found as raw data. For this graph, our agent found an explicit algebraic construction.
• Abstract（参考訳）: SATソルバや特殊発生器など、所定の性質を持つグラフを探索する方法がいくつかある。 これらのメソッドは、結果を生のデータとして返します。 生データはグラフが存在することを証明しているが、グラフの構造的特性は明らかにしていない。 この生データのみを提供する場合、短い代数的記述を自動的に発見できるかどうかを問う。 ケイリーグラフ $\mathrm{Cay}( , S)$ や語彙積 $C_5[K_3]$ などの記述を求める。 我々はこの問題をニューロシンボリックアプローチで解決する。 本研究では,汎用的な大規模言語モデル上で,微調整や目標ごとの訓練を行わないエージェントを提案する。 モデルは、コンピュータ代数システムSageMathへの呼び出しと推論をインターリーブし、ターゲットグラフを分析し、候補構造を提案し、テストし、出力がターゲットと一致するまで修正する。 エージェントは、汎用ブリッジとしてリリースするModel Context Protocol (MCP)サーバを介してSageMathと通信する。 構成が対象と一致するか否かは、単一の正確な同型テストによってチェックされ、従って、モデル上ではなく象徴的な側に置かれる。 提案手法は, 最大25頂点上の高対称グラフ100個, 最大25頂点上の2軌道グラフ100個で試行し, ベンチマークを事前に修正した。 我々のエージェントは、それらのすべてに対して検証済みの代数的構造を見つけることができ、生のエンコーディングにフォールバックすることはなかった。 強力なテンプレート列挙ベースラインはわずか20\%の価格に達し、カタログのルックアップではこれらのグラフを識別できなかった。 しかし、対称性を除去すると建設品質は低下する。 具体的な応用として、実データとして列挙された16ドルの頂点グラフであるベルンハルト・カイネン分散性予想に対する最小の反例を同定する。 このグラフに対して、我々のエージェントは明示的な代数的構成を発見した。

関連論文リスト

• Agentic Graph Token Reasoning [10.837857911869035]
  エージェントグラフトークン推論を導入し,グラフトークン化を推論プロセスの一部として再キャストする。 我々のモデルは、大きなマージンで幅広いベースラインを上回り、ターゲットごとの微調整なしにゼロショットを目に見えない領域に転送することを示す。
  論文  参考訳（メタデータ） (2026-08-01T08:56:26Z)
• SWING: Unlocking Implicit Graph Representations for Graph Random Features [57.956136773668476]
  SWING: Space Walks for Implicit Network Graphsはグラフ上のグラフランダム特徴を含む計算アルゴリズムの新しいクラスである。 SWINGの詳細な解析を行い、様々なiグラフのクラスで徹底的な実験を行い、それを補完する。
  論文  参考訳（メタデータ） (2026-02-13T08:12:38Z)
• Learning from one graph: transductive learning guarantees via the geometry of small random worlds [8.781923502647055]
  我々は,低次元メートル法埋め込みによる大規模グラフの幾何正則性を活用する新しい集中度測定ツールを開発した。 まず、任意の決定論的 $k$-vertex グラフと、ErdHos-R'enyi グラフ $mathbfG=mathbfG(k,p)$ in the regime $p in the MathcalO((log (k)/k)1/2) で鍵幾何学的性質を共有するランダムグラフについて述べる。
  論文  参考訳（メタデータ） (2025-09-08T17:13:28Z)
• Graph Inference with Effective Resistance Queries [2.2349172369559156]
  一対の頂点間の有効抵抗(ER)を返すオラクルを用いてグラフ推論を研究する。 ERクエリから$n$-vertexグラフを一意に再構築できることは知られているが、他にはほとんど知られていない。
  論文  参考訳（メタデータ） (2025-02-25T16:37:25Z)
• Shedding Light on Problems with Hyperbolic Graph Learning [2.3743504594834635]
  双曲グラフ表現学習の分野を考察する。 結果は、ベースラインを厳格に提示せず、誤ったモデリングの仮定をし、誤解を招く指標を使用する。 我々は、(ハイエボリック)グラフニューラルネットワークの適用性を確認するために、ベンチマークデータセット群を紹介する。
  論文  参考訳（メタデータ） (2024-11-11T03:12:41Z)
• Universal graph representation of stabilizer codes [0.5097809301149342]
  安定化器符号の表現を特定の構造を持つグラフとして導入する。 これにより、優れたプロパティを持つグラフを見つける方法によって、コード構築のための新しい普遍的なレシピが提供されます。 確率論的解析においてグラフを用いて、量子ギルバート=バルシャモフ境界を3方向距離-レート-重み付きトレードオフに拡張する。
  論文  参考訳（メタデータ） (2024-11-07T18:58:58Z)
• Cayley Graph Propagation [0.0]
  グラフニューラルネットワーク(GNN)は、オーバースカッシングに弱いと悪名高い。 本研究は, トランケーションが対流膨張特性に有害であることを示す。 完全ケイリーグラフ構造上の情報伝達手法であるCGPを提案する。
  論文  参考訳（メタデータ） (2024-10-04T13:32:34Z)
• AnchorGAE: General Data Clustering via $O(n)$ Bipartite Graph Convolution [79.44066256794187]
  我々は、グラフ畳み込みネットワーク(GCN)を構築するために使用される生成グラフモデルを導入することにより、グラフに非グラフデータセットを変換する方法を示す。 アンカーによって構築された二部グラフは、データの背後にある高レベル情報を利用するために動的に更新される。 理論的には、単純な更新が退化につながることを証明し、それに従って特定の戦略が設計される。
  論文  参考訳（メタデータ） (2021-11-12T07:08:13Z)
• ExplaGraphs: An Explanation Graph Generation Task for Structured Commonsense Reasoning [65.15423587105472]
  スタンス予測のための説明グラフ生成の新しい生成および構造化コモンセンスリゾニングタスク(および関連するデータセット)を紹介します。 具体的には、信念と議論が与えられた場合、モデルは、議論が信念を支持しているかどうかを予測し、予測されたスタンスに対する非自明で完全で曖昧な説明として機能する常識強化グラフを生成する必要がある。 グラフの83%は、様々な構造と推論深度を持つ外部のコモンセンスノードを含んでいる。
  論文  参考訳（メタデータ） (2021-04-15T17:51:36Z)
• Learning Sparse Graph Laplacian with K Eigenvector Prior via Iterative GLASSO and Projection [58.5350491065936]
  グラフ Laplacian 行列 $L$ 上の構造的仮定を考える。 最初の$K$ eigenvectors of $L$は、例えばドメイン固有の基準に基づいて事前選択される。 本稿では,H_u+$$$$barC$で最も適切なグラフラプラシアン行列$L*を計算するために,効率的なハイブリッドグラフラッソ/投影アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-10-25T18:12:50Z)
• Inverse Graph Identification: Can We Identify Node Labels Given Graph Labels? [89.13567439679709]
  グラフ識別(GI)は、グラフ学習において長い間研究されており、特定の応用において不可欠である。 本稿では,逆グラフ識別(Inverse Graph Identification, IGI)と呼ばれる新しい問題を定義する。 本稿では,グラフアテンションネットワーク(GAT)を用いたノードレベルのメッセージパッシング処理を,GIのプロトコルの下でシンプルかつ効果的に行う方法を提案する。
  論文  参考訳（メタデータ） (2020-07-12T12:06:17Z)
• Non-Parametric Graph Learning for Bayesian Graph Neural Networks [35.88239188555398]
  グラフ隣接行列の後方分布を構築するための新しい非パラメトリックグラフモデルを提案する。 このモデルの利点を,ノード分類,リンク予測,レコメンデーションという3つの異なる問題設定で示す。
  論文  参考訳（メタデータ） (2020-06-23T21:10:55Z)
• Wasserstein-based Graph Alignment [56.84964475441094]
  我々は,より小さいグラフのノードと大きなグラフのノードをマッチングすることを目的とした,1対多のグラフアライメント問題に対する新しい定式化を行った。 提案手法は,各タスクに対する最先端のアルゴリズムに対して,大幅な改善をもたらすことを示す。
  論文  参考訳（メタデータ） (2020-03-12T22:31:59Z)

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

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