論文の概要: The Correspondence Between Bounded Graph Neural Networks and Fragments of First-Order Logic

• arxiv url: http://arxiv.org/abs/2505.08021v1
• Date: Mon, 12 May 2025 19:45:45 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-14 20:57:54.31753
• Title: The Correspondence Between Bounded Graph Neural Networks and Fragments of First-Order Logic
• Title（参考訳）: 境界グラフニューラルネットワークと一階論理のフラグメントの対応
• Authors: Bernardo Cuenca Grau, Przemysław A. Wałęga,
• Abstract要約: 有界GNNアーキテクチャは、一階述語論理(FO)の特定の断片に対応することを示す。 これにより、FO内のGNNの論理的表現性を理解するための統一的なフレームワークが提供される。
• 参考スコア（独自算出の注目度）: 9.475039534437334
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph Neural Networks (GNNs) address two key challenges in applying deep learning to graph-structured data: they handle varying size input graphs and ensure invariance under graph isomorphism. While GNNs have demonstrated broad applicability, understanding their expressive power remains an important question. In this paper, we show that bounded GNN architectures correspond to specific fragments of first-order logic (FO), including modal logic (ML), graded modal logic (GML), modal logic with the universal modality (ML(A)), the two-variable fragment (FO2) and its extension with counting quantifiers (C2). To establish these results, we apply methods and tools from finite model theory of first-order and modal logics to the domain of graph representation learning. This provides a unifying framework for understanding the logical expressiveness of GNNs within FO.
• Abstract（参考訳）: グラフニューラルネットワーク(GNN)は、グラフ構造化データにディープラーニングを適用する際の2つの重要な課題に対処する。 GNNは幅広い適用性を示してきたが、その表現力を理解することは依然として重要な問題である。 本稿では,GNNアーキテクチャが一階述語論理(FO)の特定のフラグメントに対応していることを示す。例えば,モーダル論理(ML),次数修飾論理(GML),普遍モジュラリティを持つモーダル論理(ML(A)),2変数フラグメント(FO2),および数量化子(C2)による拡張である。 これらの結果を確立するために、グラフ表現学習の領域に一階述語論理と様相論理の有限モデル理論の手法とツールを適用する。 これにより、FO内のGNNの論理的表現性を理解するための統一的なフレームワークが提供される。

関連論文リスト

• Logical Distillation of Graph Neural Networks [47.859911892875346]
  グラフを学習するための論理に基づく解釈可能なモデルと,このモデルをグラフニューラルネットワーク(GNN)から抽出するアルゴリズムを提案する。 最近の結果は、GNNの表現性と数量化器を用いた一階述語論理の2変数フラグメント(C2)の関連性を示している。
  論文  参考訳（メタデータ） (2024-06-11T10:18:58Z)
• Generalization Limits of Graph Neural Networks in Identity Effects Learning [12.302336258860116]
  グラフニューラルネットワーク(GNN)は、さまざまなグラフドメインでデータ駆動学習を行う強力なツールとして登場した。 我々は、いわゆるアイデンティティ効果の学習において、GNNの新たな一般化特性と基本的限界を確立する。 我々の研究は、単純な認知タスクを行う際に、GNNの能力を理解する必要性によって動機付けられている。
  論文  参考訳（メタデータ） (2023-06-30T20:56:38Z)
• Representation Power of Graph Neural Networks: Improved Expressivity via Algebraic Analysis [124.97061497512804]
  標準グラフニューラルネットワーク (GNN) はWeisfeiler-Lehman (WL) アルゴリズムよりも差別的な表現を生成する。 また、白い入力を持つ単純な畳み込みアーキテクチャは、グラフの閉経路をカウントする同変の特徴を生じさせることを示した。
  論文  参考訳（メタデータ） (2022-05-19T18:40:25Z)
• Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting [63.04999833264299]
  グラフサブストラクチャネットワーク(GSN)は,サブストラクチャエンコーディングに基づくトポロジ的に認識可能なメッセージパッシング方式である。 Wesfeiler-Leman (WL) グラフ同型テストよりも厳密に表現可能であることを示す。 グラフ分類と回帰タスクについて広範囲に評価を行い、様々な実世界の環境において最先端の結果を得る。
  論文  参考訳（メタデータ） (2020-06-16T15:30:31Z)
• Evaluating Logical Generalization in Graph Neural Networks [59.70452462833374]
  グラフニューラルネットワーク(GNN)を用いた論理一般化の課題について検討する。 ベンチマークスイートであるGraphLogでは、学習アルゴリズムが異なる合成論理でルール誘導を実行する必要がある。 モデルが一般化し適応する能力は、トレーニング中に遭遇する論理規則の多様性によって強く決定される。
  論文  参考訳（メタデータ） (2020-03-14T05:45:55Z)

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

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