論文の概要: Constant-Depth Rational-Weight GNNs and their Connection to Schanuel's Conjecture

• arxiv url: http://arxiv.org/abs/2610.16993v1
• Date: Mon, 12 Oct 2026 15:44:17 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-18 03:49:41.231758
• Title: Constant-Depth Rational-Weight GNNs and their Connection to Schanuel's Conjecture
• Title（参考訳）: 定深比重GNNとSchanuelの導出との関係
• Abstract要約: グラフニューラルネットワーク(GNN)の表現力は、上から1次元Weisfeiler-Leman (1-WL) テストによって制限される。 定深GNNが有理重みのみを用いて1-WLの表現力と一致できるかを問う。 これは、超越数論からの有名な開問題であるシャヌエル予想が真であると考える場合である。
• 参考スコア（独自算出の注目度）: 5.134998749955833
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A landmark result states that the expressive power of graph neural networks (GNNs) is bounded from above by the 1-dimensional Weisfeiler-Leman (1-WL) test. We ask whether a constant-depth GNN can match the expressive power of 1-WL while using only rational weights. We prove that this is the case when Schanuel's conjecture, a famous open problem from transcendental number theory, is taken to be true. Our GNN construction works even with integer weights, and more generally with a broad range of rational weights. As the activation function, it may use logistic sigmoid, hyperbolic tangent, or related functions. It is uniform across all graph sizes. We also prove a partial converse: if a GNN with exponentiation, hyperbolic sine or hyperbolic cosine as activation matches the expressive power of the 1-WL test in a slightly more expressive setting where graphs may contain certain auxiliary vertices, then this implies Schanuel's conjecture restricted to the numbers that arise in computations of the GNN. We also conduct experiments showing that the constructed GNNs indeed match the 1-WL test.
• Abstract（参考訳）: グラフニューラルネットワーク(GNN)の表現力は、上から1次元Weisfeiler-Leman (1-WL) テストによって制限される。 定深GNNが有理重みのみを用いて1-WLの表現力と一致できるかを問う。 このことは、超越数論からの有名な開問題であるシャヌエル予想が真であるとするものである。 我々のGNN構造は整数重みでも機能し、より一般的には幅広い有理重みで機能する。 活性化関数として、ロジスティックシグモイド、双曲タンジェント、または関連する関数を用いる。 すべてのグラフサイズに一様である。 また, 指数, 双曲正弦, 双曲コサインをアクティベーションとするGNNが, グラフがある種の補助頂点を含むようなより表現力のある環境で 1-WL テストの表現力と一致する場合, このことは, GNN の計算で生じる数に制限されるSchanuel の予想を意味する。 また,構築したGNNが実際に1-WL試験と一致することを示す実験を行った。

関連論文リスト

• A Manifold Perspective on the Statistical Generalization of Graph Neural Networks [84.01980526069075]
  我々は、スペクトル領域の多様体からサンプリングされたグラフ上のGNNの統計的一般化理論を確立するために多様体の視点を取る。 我々はGNNの一般化境界が対数スケールのグラフのサイズとともに線形に減少し、フィルタ関数のスペクトル連続定数とともに線形的に増加することを証明した。
  論文  参考訳（メタデータ） (2024-06-07T19:25:02Z)
• Some Might Say All You Need Is Sum [2.226803104060345]
  グラフニューラルネットワーク(GNN)の表現性は、採用する集約関数に依存する。 我々は,Mean や Max GNN によって正確に計算できる基本関数が任意の Sum GNN によって近似できないことを証明した。
  論文  参考訳（メタデータ） (2023-02-22T19:01:52Z)
• WL meet VC [9.468816647649104]
  本稿では,Vapnik-Chervonenkis(VC)次元理論のレンズによるグラフニューラルネットワーク(GNN)の表現力について検討する。 我々は、GNNのVC次元と1text-mathsfWL$およびGNNのVC次元によって生成される色数を用いて、GNNのVC次元の上限を導出する。
  論文  参考訳（メタデータ） (2023-01-26T11:29:36Z)
• Two-Dimensional Weisfeiler-Lehman Graph Neural Networks for Link Prediction [61.01337335214126]
  グラフニューラルネットワーク(GNN)のリンク予測 リンク予測のためのほとんどの既存のGNNは、1次元Weisfeiler-Lehman (1-WL) テストに基づいている。 テキスト2次元Weisfeiler-Lehman (2-WL) テストに基づいて,ノード対(リンク)表現を直接取得可能な,まったく異なるアプローチを提案する。
  論文  参考訳（メタデータ） (2022-06-20T04:50:38Z)
• Representation Power of Graph Neural Networks: Improved Expressivity via Algebraic Analysis [124.97061497512804]
  標準グラフニューラルネットワーク (GNN) はWeisfeiler-Lehman (WL) アルゴリズムよりも差別的な表現を生成する。 また、白い入力を持つ単純な畳み込みアーキテクチャは、グラフの閉経路をカウントする同変の特徴を生じさせることを示した。
  論文  参考訳（メタデータ） (2022-05-19T18:40:25Z)
• Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning [63.97983530843762]
  グラフニューラルネットワーク(GNN)はグラフ表現学習において大きな成功を収めている。 GNNは、実際には非常に異なるグラフ部分構造に対して同一の表現を生成する。 より強力なGNNは、最近高階試験を模倣して提案され、基礎となるグラフ構造を疎結合にできないため、非効率である。 本稿では,グラフ表現学習の新たなクラスとして距離分解(DE)を提案する。
  論文  参考訳（メタデータ） (2020-08-31T23:15:40Z)

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

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