論文の概要: Expressive Power of Graph Transformers via Logic

• arxiv url: http://arxiv.org/abs/2508.01067v1
• Date: Fri, 01 Aug 2025 20:59:13 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-05 18:25:21.69626
• Title: Expressive Power of Graph Transformers via Logic
• Title（参考訳）: 論理によるグラフ変換器の表現力
• Authors: Veeti Ahvonen, Maurice Funk, Damian Heiman, Antti Kuusisto, Carsten Lutz,
• Abstract要約: Dwivedi and Bresson (2020) によるグラフトランスフォーマー (GT) の表現力と Ramp'asek et al. (2022) による GPS-networks について検討する。 実数では、GPSネットワークは、グローバルなモダリティを持つグレードド・モーダル論理(GML)と同じ表現力を持つことを示す。 フロートでは、GPSネットワークはグローバルなモダリティを数えながら、GMLと同等に表現できることがわかった。
• 参考スコア（独自算出の注目度）: 7.89576199021427
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Transformers are the basis of modern large language models, but relatively little is known about their precise expressive power on graphs. We study the expressive power of graph transformers (GTs) by Dwivedi and Bresson (2020) and GPS-networks by Ramp\'asek et al. (2022), both under soft-attention and average hard-attention. Our study covers two scenarios: the theoretical setting with real numbers and the more practical case with floats. With reals, we show that in restriction to vertex properties definable in first-order logic (FO), GPS-networks have the same expressive power as graded modal logic (GML) with the global modality. With floats, GPS-networks turn out to be equally expressive as GML with the counting global modality. The latter result is absolute, not restricting to properties definable in a background logic. We also obtain similar characterizations for GTs in terms of propositional logic with the global modality (for reals) and the counting global modality (for floats).
• Abstract（参考訳）: トランスフォーマーは現代の大きな言語モデルの基礎であるが、グラフの正確な表現力についてはあまり知られていない。 Dwivedi and Bresson (2020) によるグラフトランスフォーマー (GT) の表現力と Ramp\'asek et al (2022) によるGPSネットワークの研究を行った。 本研究は,実数を用いた理論的設定と,フロートを用いたより実用的な場合の2つのシナリオについて述べる。 実数では、一階述語論理(FO)で定義可能な頂点特性に制限される場合、GPS-networksはグローバルなモダリティを持つ次数修飾論理(GML)と同じ表現力を持つことを示す。 フロートでは、GPSネットワークはグローバルなモダリティを数えながら、GMLと同等に表現できることがわかった。 後者の結果は絶対的であり、バックグラウンドロジックで定義可能なプロパティに制限されない。 また、GTに対して、(実数に対する)大域的モダリティと(フロートに対する)大域的モダリティとの命題論理の観点から、同様の特徴付けを得る。

関連論文リスト

• The Correspondence Between Bounded Graph Neural Networks and Fragments of First-Order Logic [8.430502131775723]
  本稿では,一階述語論理(FO)の顕著な断片に対応するGNNアーキテクチャを提案する。 FO内のGNNの論理的表現性を理解するための統一的なフレームワークを提供する。
  論文  参考訳（メタデータ） (2025-05-12T19:45:45Z)
• Plain Transformers Can be Powerful Graph Learners [64.50059165186701]
  研究者たちは、Transformerをグラフ学習に移行しようとしたが、ほとんどの高度なGraph Transformerは、普通のTransformerから遠く離れている。 この研究は、普通のTransformerアーキテクチャが強力なグラフ学習者になれることを示した。
  論文  参考訳（メタデータ） (2025-04-17T02:06:50Z)
• Learning Efficient Positional Encodings with Graph Neural Networks [109.8653020407373]
  グラフのための学習可能なPEの新しいフレームワークであるPEARLを紹介する。 PEARL は線形複雑性を持つ固有ベクトルの同変関数を近似し、その安定性と高表現力を厳密に確立する。 解析の結果、PEARLは線形複雑度を持つ固有ベクトルの同変関数を近似し、その安定性と高表現能を厳密に確立することを示した。
  論文  参考訳（メタデータ） (2025-02-03T07:28:53Z)
• Global Graph Counterfactual Explanation: A Subgraph Mapping Approach [54.42907350881448]
  グラフニューラルネットワーク(GNN)は、様々な現実世界のアプリケーションに広くデプロイされている。 対実的説明は、GNN予測を変える入力グラフ上で最小の摂動を見つけることを目的としている。 我々は,グローバルレベルのグラフ対実的説明法であるGlobalGCEを提案する。
  論文  参考訳（メタデータ） (2024-10-25T21:39:05Z)
• Logical Characterizations of Recurrent Graph Neural Networks with Reals and Floats [6.176021290715425]
  本稿では,2つのシナリオにおいて,繰り返しグラフニューラルネットワーク(GNN)の正確な論理的特徴について述べる。 フロートに対して、繰り返しGNNと一致する形式主義は数えられるルールベースのモーダル論理であり、実数に対しては適切な無限のモーダル論理を用いる。 キャラクタリゼーションを適用することで、モナディック二階述語論理で定義可能なグラフ特性と比較して、無限論理と規則論理は等しく表現力があることが証明できる。
  論文  参考訳（メタデータ） (2024-05-23T14:19:21Z)
• Topology-Informed Graph Transformer [7.193109202139812]
  グラフアイソモーフィズムの検出における識別力とグラフ変換器全体の性能を両立させる新しい変換器である「トポロジーインフォーマグラフ変換器(TIGT)」について検討した。 TIGTは4つの構成要素から構成される: 非同型普遍被覆を用いた位相的位置埋め込み層はグラフの巡回部分グラフに基づいて一意なグラフ表現を保証する。 TIGTは、グラフの同型クラスを識別することを目的とした合成データセットの分類において、従来のグラフ変換器よりも優れている。
  論文  参考訳（メタデータ） (2024-02-03T03:17:44Z)
• Graph Transformers for Large Graphs [57.19338459218758]
  この研究は、モデルの特徴と重要な設計制約を識別することに焦点を当てた、単一の大規模グラフでの表現学習を前進させる。 この研究の重要な革新は、局所的な注意機構と組み合わされた高速な近傍サンプリング技術の作成である。 ogbn-products と snap-patents の3倍の高速化と16.8%の性能向上を報告し、ogbn-100M で LargeGT を5.9% の性能改善で拡張した。
  論文  参考訳（メタデータ） (2023-12-18T11:19:23Z)
• The logic of rational graph neural networks [0.7614628596146602]
  我々は,GC2 の深度 3$ のクエリは,合理的なアクティベーション関数を持つ GNN では表現できないことを証明した。 これは、すべての非ポリノミカル活性化関数がGNNの最大表現性を参照しているわけではないことを示している。 また、一階述語論理(RGC2)の有理サブフラグメントを示し、すべてのグラフに対して有理GNNがRGC2クエリを均一に表現できることを証明する。
  論文  参考訳（メタデータ） (2023-10-19T20:32:25Z)
• Pure Transformers are Powerful Graph Learners [51.36884247453605]
  グラフ固有の修正のない標準変換器は、理論と実践の両方において、グラフ学習において有望な結果をもたらす可能性があることを示す。 このアプローチは、理論的には、同変線形層からなる不変グラフネットワーク(2-IGN)と同程度に表現可能であることを証明している。 提案手法は,Tokenized Graph Transformer (TokenGT) を作成した。
  論文  参考訳（メタデータ） (2022-07-06T08:13:06Z)
• Representation Power of Graph Neural Networks: Improved Expressivity via Algebraic Analysis [124.97061497512804]
  標準グラフニューラルネットワーク (GNN) はWeisfeiler-Lehman (WL) アルゴリズムよりも差別的な表現を生成する。 また、白い入力を持つ単純な畳み込みアーキテクチャは、グラフの閉経路をカウントする同変の特徴を生じさせることを示した。
  論文  参考訳（メタデータ） (2022-05-19T18:40:25Z)
• On the expressive power of message-passing neural networks as global feature map transformers [5.040463208115643]
  入力グラフのノードに格納されている数値的特徴を変換するために,MPNN(Message-passing Neural Network)の能力について検討する。 我々の焦点はグローバルな表現力であり、全ての入力グラフを均一に上り、あるいは有界領域の特徴を持つ有界次数グラフに当てはまる。
  論文  参考訳（メタデータ） (2022-03-17T18:37:21Z)

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

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