論文の概要: The Logical Expressiveness of Topological Neural Networks

• arxiv url: http://arxiv.org/abs/2604.19212v1
• Date: Tue, 21 Apr 2026 08:15:16 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-22 22:41:49.683635
• Title: The Logical Expressiveness of Topological Neural Networks
• Title（参考訳）: トポロジカルニューラルネットワークの論理表現性
• Authors: Amirreza Akbari, Amauri H. Souza, Vikas Garg,
• Abstract要約: グラフ表現学習の代替として、トポロジカルニューラルネットワーク(TNN)が登場した。 メッセージパス方式に高階リレーショナル構造を組み込むことで、TNNは従来のGNNよりも高い表現力を提供する。
• 参考スコア（独自算出の注目度）: 28.797706806810528
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph neural networks (GNNs) are the standard for learning on graphs, yet they have limited expressive power, often expressed in terms of the Weisfeiler-Leman (WL) hierarchy or within the framework of first-order logic. In this context, topological neural networks (TNNs) have recently emerged as a promising alternative for graph representation learning. By incorporating higher-order relational structures into message-passing schemes, TNNs offer higher representational power than traditional GNNs. However, a fundamental question remains open: what is the logical expressiveness of TNNs? Answering this allows us to characterize precisely which binary classifiers TNNs can represent. In this paper, we address this question by analyzing isomorphism tests derived from the underlying mechanisms of general TNNs. We introduce and investigate the power of higher-order variants of WL-based tests for combinatorial complexes, called $k$-CCWL test. In addition, we introduce the topological counting logic (TC$_k$), an extension of standard counting logic featuring a novel pairwise counting quantifier $ \exists^{N}(x_i,x_j)\, \varphi(x_i,x_j), $ which explicitly quantifies pairs $(x_i, x_j)$ satisfying property $\varphi$. We rigorously prove the exact equivalence: $ \text{k-CCWL} \equiv \text{TC}_{k{+}2} \equiv \text{Topological }(k{+}2)\text{-pebble game}.$ These results establish a logical expressiveness theory for TNNs.
• Abstract（参考訳）: グラフニューラルネットワーク(GNN)はグラフの学習の標準であるが、表現力は限られており、しばしばWeisfeiler-Leman(WL)階層や一階述語論理のフレームワーク内で表現される。 この文脈では、最近、グラフ表現学習の代替としてトポロジカルニューラルネットワーク(TNN)が出現している。 メッセージパス方式に高階リレーショナル構造を組み込むことで、TNNは従来のGNNよりも高い表現力を提供する。 しかし、根本的な疑問が残る。TNNの論理的表現性は何なのか? これを答えることで、TNNが表現できるバイナリ分類器を正確に特徴付けることができます。 本稿では、一般的なTNNのメカニズムから導かれる同型性テストを分析することにより、この問題に対処する。 組合せ複素数に対する高次変量WL法($k$-CCWL法)の導入と検討を行った。 さらに、新しい対数量子化器である \exists^{N}(x_i,x_j)\, \varphi(x_i,x_j), $ を明示的に定量化する標準数え上げ論理の拡張である TC$_k$ を導入する。 $ \text{k-CCWL} \equiv \text{TC}_{k{+}2} \equiv \text{Topological }(k{+}2)\text{-pebble game}。 これらの結果は、TNNに対する論理的表現性理論を確立する。

関連論文リスト

• Enhancing Logical Expressiveness in Graph Neural Networks via Path-Neighbor Aggregation [22.086161213961244]
  本稿では,GNNの論理的表現力を高めるため,PN-GNN(Path-Neighbor enhanced GNN)を提案する。 まず,既存のGNN手法の論理表現力を分析し,これらの手法の欠点を指摘する。 そこで理論的にPN-GNNの論理表現力について検討し、C-GNNよりも強い表現力を持つだけでなく、$(k+1)$-hop論理表現性が$k$-hopよりも厳密に優れていることを示す。
  論文  参考訳（メタデータ） (2025-11-11T08:59:10Z)
• On Efficiently Representing Regular Languages as RNNs [49.88310438099143]
  RNNは、人間の言語で広く使われている有界階層構造を効率的に表現できることを示す。 これは、RNNの成功が階層をモデル化する能力と結びついていることを示唆している。 我々は,RNNが従来主張していたより大規模なLMを効率的に表現できることを示す。
  論文  参考訳（メタデータ） (2024-02-24T13:42:06Z)
• On the Computational Complexity and Formal Hierarchy of Second Order Recurrent Neural Networks [59.85314067235965]
  2次次リカレントネットワーク(RNN)の理論基盤を拡大する(2次RNN) 有界時間でチューリング完備な RNN のクラスが存在することを証明している。 また、記憶のない2ドルのRNNは、バニラRNNのような現代のモデルよりも優れており、正規文法の認識において繰り返し単位をゲートしていることを示す。
  論文  参考訳（メタデータ） (2023-09-26T06:06:47Z)
• Fine-grained Expressivity of Graph Neural Networks [15.766353435658043]
  我々は1ドルWLとMPNNの連続的な拡張をグラファイトに検討する。 連続的な1ドルWLの変動は,MPNNのグラフ上での表現力の正確なトポロジ的特徴を与えることを示す。 また,グラフ距離の保存能力に基づいて,異なるMPNNアーキテクチャの評価を行った。
  論文  参考訳（メタデータ） (2023-06-06T14:12:23Z)
• The Descriptive Complexity of Graph Neural Networks [2.6728900378310514]
  グラフクエリはグラフニューラルネットワーク(GNN)の有界サイズファミリによって計算可能であることを示す。 GNNは、カウントとビルトインの関係を持つ一階述語論理のガードされた断片で定義できる。 GFO+Cでは1つのGNNで1つの線形アクティベーションと有理重みを持つクエリが組込み関係なく定義可能であることを示す。
  論文  参考訳（メタデータ） (2023-03-08T14:32:59Z)
• Representation Power of Graph Neural Networks: Improved Expressivity via Algebraic Analysis [124.97061497512804]
  標準グラフニューラルネットワーク (GNN) はWeisfeiler-Lehman (WL) アルゴリズムよりも差別的な表現を生成する。 また、白い入力を持つ単純な畳み込みアーキテクチャは、グラフの閉経路をカウントする同変の特徴を生じさせることを示した。
  論文  参考訳（メタデータ） (2022-05-19T18:40:25Z)
• Counting Substructures with Higher-Order Graph Neural Networks: Possibility and Impossibility Results [58.277290855841976]
  グラフニューラルネットワーク(GNN)の計算コストと表現力のトレードオフについて検討する。 新しいモデルでは、$k$のサブグラフをカウントでき、低次GNNの既知の制限を克服できることを示す。 いくつかの場合において、提案アルゴリズムは既存の高階$k$-GNNに比べて計算量を大幅に削減することができる。
  論文  参考訳（メタデータ） (2020-12-06T03:42:54Z)
• Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting [63.04999833264299]
  グラフサブストラクチャネットワーク(GSN)は,サブストラクチャエンコーディングに基づくトポロジ的に認識可能なメッセージパッシング方式である。 Wesfeiler-Leman (WL) グラフ同型テストよりも厳密に表現可能であることを示す。 グラフ分類と回帰タスクについて広範囲に評価を行い、様々な実世界の環境において最先端の結果を得る。
  論文  参考訳（メタデータ） (2020-06-16T15:30:31Z)
• Can Graph Neural Networks Count Substructures? [53.256112515435355]
  グラフニューラルネットワーク(GNN)の能力について,属性付きグラフサブ構造をカウントする能力を用いて検討する。 我々は2種類のサブストラクチャカウントを区別する: インダクションサブグラフカウントとサブグラフカウント、および人気のあるGNNアーキテクチャに対する肯定的および否定的な回答である。
  論文  参考訳（メタデータ） (2020-02-10T18:53:30Z)

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

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