論文の概要: On the Computational Capability of Graph Neural Networks: A Circuit Complexity Bound Perspective

• arxiv url: http://arxiv.org/abs/2501.06444v1
• Date: Sat, 11 Jan 2025 05:54:10 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-14 14:26:49.203698
• Title: On the Computational Capability of Graph Neural Networks: A Circuit Complexity Bound Perspective
• Title（参考訳）: グラフニューラルネットワークの計算能力について:回路複雑度境界の視点
• Authors: Xiaoyu Li, Yingyu Liang, Zhenmei Shi, Zhao Song, Wei Wang, Jiahao Zhang,
• Abstract要約: グラフニューラルネットワーク(GNN)は、リレーショナルデータに対する学習と推論の標準的なアプローチとなっている。 本稿では,回路複雑性のレンズによるGNNの計算限界について検討する。 具体的には、共通GNNアーキテクチャの回路複雑性を分析し、定数層、線形またはサブ線形埋め込みサイズ、精度の制約の下で、GNNはグラフ接続やグラフ同型といった重要な問題を解くことができないことを証明している。
• 参考スコア（独自算出の注目度）: 28.497567290882355
• License:
• Abstract: Graph Neural Networks (GNNs) have become the standard approach for learning and reasoning over relational data, leveraging the message-passing mechanism that iteratively propagates node embeddings through graph structures. While GNNs have achieved significant empirical success, their theoretical limitations remain an active area of research. Existing studies primarily focus on characterizing GNN expressiveness through Weisfeiler-Lehman (WL) graph isomorphism tests. In this paper, we take a fundamentally different approach by exploring the computational limitations of GNNs through the lens of circuit complexity. Specifically, we analyze the circuit complexity of common GNN architectures and prove that under constraints of constant-depth layers, linear or sublinear embedding sizes, and polynomial precision, GNNs cannot solve key problems such as graph connectivity and graph isomorphism unless $\mathsf{TC}^0 = \mathsf{NC}^1$. These results reveal the intrinsic expressivity limitations of GNNs behind their empirical success and introduce a novel framework for analyzing GNN expressiveness that can be extended to a broader range of GNN models and graph decision problems.
• Abstract（参考訳）: グラフニューラルネットワーク(GNN)は、グラフ構造を介してノードの埋め込みを反復的に伝播するメッセージパッシング機構を活用することで、関係データの学習と推論の標準的なアプローチとなっている。 GNNは経験的成功をおさめたが、理論上の限界は依然として研究の活発な領域である。 既存の研究は主にWeisfeiler-Lehman(WL)グラフ同型テストによるGNN表現性の特徴付けに重点を置いている。 本稿では,回路複雑性のレンズを通してGNNの計算限界を探索することで,根本的に異なるアプローチをとる。 具体的には、共通GNNアーキテクチャの回路複雑性を分析し、定数層、線形またはサブ線形埋め込みサイズ、多項式精度の制約の下で、GNNは、$\mathsf{TC}^0 = \mathsf{NC}^1$でない限り、グラフ接続やグラフ同型といった重要な問題を解くことができない。 これらの結果は、GNNの本質的な表現性限界を経験的成功の裏で明らかにし、GNNの表現性を分析するための新しいフレームワークを導入し、より広い範囲のGNNモデルやグラフ決定問題に拡張することができる。

関連論文リスト

• A Manifold Perspective on the Statistical Generalization of Graph Neural Networks [84.01980526069075]
  我々は、スペクトル領域の多様体からサンプリングされたグラフ上のGNNの統計的一般化理論を確立するために多様体の視点を取る。 我々はGNNの一般化境界が対数スケールのグラフのサイズとともに線形に減少し、フィルタ関数のスペクトル連続定数とともに線形的に増加することを証明した。
  論文  参考訳（メタデータ） (2024-06-07T19:25:02Z)
• On the Expressive Power of Graph Neural Networks [0.0]
  グラフニューラルネットワーク(GNN)は、社会科学、化学、医学といった分野における様々なタスクを解くことができる。 ディープラーニングをグラフ構造化データに拡張することにより、GNNは、社会科学、化学、医学といった分野におけるさまざまなタスクを解決できる。
  論文  参考訳（メタデータ） (2024-01-03T08:54:56Z)
• DEGREE: Decomposition Based Explanation For Graph Neural Networks [55.38873296761104]
  我々は,GNN予測に対する忠実な説明を提供するためにDGREEを提案する。 GNNの情報生成と集約機構を分解することにより、DECREEは入力グラフの特定のコンポーネントのコントリビューションを最終的な予測に追跡することができる。 また,従来の手法で見過ごされるグラフノード間の複雑な相互作用を明らかにするために,サブグラフレベルの解釈アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2023-05-22T10:29:52Z)
• Graph Neural Networks are Inherently Good Generalizers: Insights by Bridging GNNs and MLPs [71.93227401463199]
  本稿では、P(ropagational)MLPと呼ばれる中間モデルクラスを導入することにより、GNNの性能向上を本質的な能力に向ける。 PMLPは、トレーニングにおいてはるかに効率的でありながら、GNNと同等(あるいはそれ以上)に動作することを観察する。
  論文  参考訳（メタデータ） (2022-12-18T08:17:32Z)
• EvenNet: Ignoring Odd-Hop Neighbors Improves Robustness of Graph Neural Networks [51.42338058718487]
  グラフニューラルネットワーク(GNN)は、グラフ機械学習における有望なパフォーマンスについて、広範な研究の注目を集めている。 GCNやGPRGNNのような既存のアプローチは、テストグラフ上のホモフィリな変化に直面しても堅牢ではない。 偶数多項式グラフフィルタに対応するスペクトルGNNであるEvenNetを提案する。
  論文  参考訳（メタデータ） (2022-05-27T10:48:14Z)
• Expressiveness and Approximation Properties of Graph Neural Networks [6.1323142294300625]
  Wesfeiler-Leman (WL) テストの観点で GNN の分離パワーのバウンダリを得るためのエレガントな方法を提供する。 我々はテンソル言語を用いて、MPNNの自然な拡張である高次メッセージパッシングニューラルネットワーク(またはk-MPNN)を定義する。 提案手法は,GNNアーキテクチャ設計者がGNNの分離パワーを解析できるツールボックスを提供する。
  論文  参考訳（メタデータ） (2022-04-10T11:33:04Z)
• Edge-Level Explanations for Graph Neural Networks by Extending Explainability Methods for Convolutional Neural Networks [33.20913249848369]
  グラフニューラルネットワーク(GNN)は、グラフデータを入力として扱うディープラーニングモデルであり、トラフィック予測や分子特性予測といった様々なタスクに適用される。 本稿では,CNNに対する説明可能性の手法として,LIME(Local Interpretable Model-Agnostic Explanations)やGradient-Based Saliency Maps,Gradient-Weighted Class Activation Mapping(Grad-CAM)をGNNに拡張する。 実験結果から,LIMEに基づくアプローチは実環境における複数のタスクに対する最も効率的な説明可能性手法であり,その状態においても優れていたことが示唆された。
  論文  参考訳（メタデータ） (2021-11-01T06:27:29Z)
• Optimization of Graph Neural Networks: Implicit Acceleration by Skip Connections and More Depth [57.10183643449905]
  グラフニューラルネットワーク(GNN)は表現力と一般化のレンズから研究されている。 GNNのダイナミクスを深部スキップ最適化により研究する。 本研究は,GNNの成功に対する最初の理論的支援を提供する。
  論文  参考訳（メタデータ） (2021-05-10T17:59:01Z)
• Expressive Power of Invariant and Equivariant Graph Neural Networks [10.419350129060598]
  Folklore Graph Neural Networks (FGNN) は、与えられたテンソル次数に対してこれまで提案されてきた最も表現力のあるアーキテクチャである。 FGNNはこの問題の解決方法を学ぶことができ、既存のアルゴリズムよりも平均的なパフォーマンスが向上する。
  論文  参考訳（メタデータ） (2020-06-28T16:35:45Z)
• Eigen-GNN: A Graph Structure Preserving Plug-in for GNNs [95.63153473559865]
  グラフニューラルネットワーク(GNN)は、グラフ上の新たな機械学習モデルである。 既存のGNNモデルの多くは浅く、本質的に機能中心である。 我々は,既存の浅いGNNがグラフ構造をよく保存できないことを経験的かつ解析的に示す。 本稿では,グラフ構造保存におけるGNNの能力を高めるプラグインモジュールであるEigen-GNNを提案する。
  論文  参考訳（メタデータ） (2020-06-08T02:47:38Z)

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

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