論文の概要: Structural Preservation and the Logical Expressiveness of Graph Neural Networks

• arxiv url: http://arxiv.org/abs/2606.17882v1
• Date: Tue, 16 Jun 2026 12:57:50 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-17 17:15:32.438854
• Title: Structural Preservation and the Logical Expressiveness of Graph Neural Networks
• Title（参考訳）: グラフニューラルネットワークの構造保存と論理表現性
• Authors: Przemysław Andrzej Wałęga, Bernardo Cuenca Grau,
• Abstract要約: 我々は,グラフニューラルネットワーク(GNN)のクラスを構造的特性で保存する論理的表現性を確立することによって,意味論的視点を定めている。 それぞれの特性に対して、GNNのクラスを特徴づける格式付きモーダル論理の断片が存在することを示す。 特に、埋め込み、射影準同型、準同型による保存は、実数次モジュラー論理、その存在正の断片および存在正のモジュラー論理にそれぞれ対応している。
• 参考スコア（独自算出の注目度）: 10.885910878567456
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Bridges between graph neural networks (GNNs) and logical formalisms have been established by fixing architectural choices, such as the types of aggregation, combination, and activation functions. These choices define restricted classes of GNNs for which tight correspondences with logical formalisms can be obtained, by showing that logical formulae can be translated into equivalent GNNs and, conversely, that GNNs can be translated into equivalent formulae. In this paper we take a semantic perspective by establishing the logical expressiveness of classes of GNN classifiers that are preserved under structural properties: embeddings (extensions), injective homomorphisms, and homomorphisms. We show that, for each such property, there exists a fragment of graded modal logic characterising the class of GNNs. In particular, preservation under embeddings, injective homomorphisms, and homomorphisms corresponds to existential graded modal logic, its existential-positive fragment, and existential-positive modal logic, respectively. These results characterise the expressiveness of broad classes of GNNs independently of specific architectural choices, but we also show that each of these classes admits a GNN architecture of the same expressiveness. Technically, our approach uses a new well-quasi-order result for trees of bounded height, yielding finite representations of unravelling-invariant classes.
• Abstract（参考訳）: グラフニューラルネットワーク(GNN)と論理形式の間のブリッジは、アグリゲーション、組み合わせ、アクティベーション関数といったアーキテクチャ上の選択を固定することで確立されている。 これらの選択は、論理式が等価なGNNに変換可能であることを示し、逆に、GNNが等価な公式に変換可能であることを示し、論理形式主義と密接な対応を得ることができるGNNの制限クラスを定義する。 本稿では,GNN分類器のクラスを構造的特性下で保存する論理的表現性(埋め込み(拡張),射影準同型,準同型)を確立することによって,意味論的視点をとる。 それぞれの特性に対して、GNNのクラスを特徴づける格式付きモーダル論理の断片が存在することを示す。 特に、埋め込み、射影準同型、準同型による保存は、実数次モジュラー論理、その存在正の断片および存在正のモジュラー論理にそれぞれ対応している。 これらの結果は、特定のアーキテクチャ選択とは無関係に、GNNの幅広いクラスの表現性を特徴付けるが、それぞれのクラスが同じ表現性を持つGNNアーキテクチャを持つことを示す。 技術的には、我々のアプローチは有界高さのツリーに対して新しい有界次数の結果を使い、無声不変クラスの有限表現をもたらす。

関連論文リスト

• Do We Really Need GNNs with Explicit Structural Modeling? MLPs Suffice for Language Model Representations [50.45261187796993]
  グラフニューラルネットワーク(GNN)は構造情報を十分に活用できないが、MLP(Multi-Layer Perceptrons)は構造認識タスクにおいて驚くべき能力を示す。 本稿では,情報理論の観点から総合的な探索フレームワークを提案する。
  論文  参考訳（メタデータ） (2025-06-26T18:10:28Z)
• Logical Expressiveness of Graph Neural Networks with Hierarchical Node Individualization [0.6215404942415159]
  Hierarchical Ego Graph Neural Networks (HEGNN)は、グラフニューラルネットワーク(GNN)の表現的拡張である。 HEGNNは部分グラフ-GNNを一般化し、グラフを同型まで区別できる表現的モデルの階層を形成する。 実験により,HEGNNの実用性を確認し,従来のGNNアーキテクチャと比較した場合の利点を示した。
  論文  参考訳（メタデータ） (2025-06-16T18:39:31Z)
• A Logic for Reasoning About Aggregate-Combine Graph Neural Networks [11.313331046805365]
  各式が等価グラフニューラルネットワーク(GNN)に変換可能であることを示す。 また, 満足度問題はPSPACE完全であることを示す。
  論文  参考訳（メタデータ） (2024-04-30T21:16:38Z)
• Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness [35.409017863665575]
  準同型表現性は、GNNモデルが準同型の下でグラフを数える能力を測定する。 ケーススタディとして著名なGNNの4つのクラスを調べることで、それらの同型表現の単純で統一的でエレガントな記述を導き出す。 本研究の結果は, 過去の一連の研究に対する新たな洞察を与え, 地域社会における様々なサブアレスの景観を統一し, いくつかのオープンな疑問を解決した。
  論文  参考訳（メタデータ） (2024-01-16T17:23:23Z)
• Representation Power of Graph Neural Networks: Improved Expressivity via Algebraic Analysis [124.97061497512804]
  標準グラフニューラルネットワーク (GNN) はWeisfeiler-Lehman (WL) アルゴリズムよりも差別的な表現を生成する。 また、白い入力を持つ単純な畳み込みアーキテクチャは、グラフの閉経路をカウントする同変の特徴を生じさせることを示した。
  論文  参考訳（メタデータ） (2022-05-19T18:40:25Z)
• Universal approximation property of invertible neural networks [76.95927093274392]
  Invertible Neural Network (INN) は、設計によって可逆性を持つニューラルネットワークアーキテクチャである。 その可逆性とヤコビアンのトラクタビリティのおかげで、IGNは確率的モデリング、生成的モデリング、表現的学習など、さまざまな機械学習応用がある。
  論文  参考訳（メタデータ） (2022-04-15T10:45:26Z)
• Equivariant Neural Network for Factor Graphs [83.26543234955855]
  因子同変ニューラルネットワーク(FE-NBP)と因子同変グラフニューラルネットワーク(FE-GNN)の2つの推論モデルを提案する。 FE-NBPは小さなデータセットで最先端のパフォーマンスを達成する一方、FE-GNNは大規模なデータセットで最先端のパフォーマンスを達成する。
  論文  参考訳（メタデータ） (2021-09-29T06:54:04Z)
• Stability of Algebraic Neural Networks to Small Perturbations [179.55535781816343]
  Algebraic Neural Network (AlgNN) は、代数的信号モデルと関連する各層のカスケードで構成されている。 畳み込みという形式的な概念を用いるアーキテクチャは、シフト演算子の特定の選択を超えて、いかに安定であるかを示す。
  論文  参考訳（メタデータ） (2020-10-22T09:10:16Z)
• Algebraic Neural Networks: Stability to Deformations [179.55535781816343]
  可換代数を用いた代数ニューラルネットワーク(AlgNN)について検討する。 AlgNNはユークリッド畳み込みニューラルネットワーク、グラフニューラルネットワーク、グループニューラルネットワークなどの多様なアーキテクチャを統合する。
  論文  参考訳（メタデータ） (2020-09-03T03:41:38Z)

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

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