論文の概要: Rethinking the Expressiveness of GNNs: A Computational Model Perspective

• arxiv url: http://arxiv.org/abs/2410.01308v1
• Date: Wed, 2 Oct 2024 08:01:50 GMT
• ステータス: 処理完了
• システム内更新日: 2024-11-04 21:49:06.925782
• Title: Rethinking the Expressiveness of GNNs: A Computational Model Perspective
• Title（参考訳）: GNNの表現性を再考する:計算モデルの視点から
• Authors: Guanyu Cui, Zhewei Wei, Hsin-Hao Su,
• Abstract要約: 本稿では,資源制限型CONGEST(RL-CONGEST)モデルを導入し,任意の前処理と後処理を導入し,GNN表現性を解析するためのフレームワークを形成する。 我々のフレームワークは、WLテストにおけるハッシュ関数の計算硬度や、ネットワーク容量の削減における仮想ノードの役割など、計算面に光を当てている。
• 参考スコア（独自算出の注目度）: 21.683245760896313
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph Neural Networks (GNNs) are extensively employed in graph machine learning, with considerable research focusing on their expressiveness. Current studies often assess GNN expressiveness by comparing them to the Weisfeiler-Lehman (WL) tests or classical graph algorithms. However, we identify three key issues in existing analyses: (1) some studies use preprocessing to enhance expressiveness but overlook its computational costs; (2) some claim the anonymous WL test's limited power while enhancing expressiveness using non-anonymous features, creating a mismatch; and (3) some characterize message-passing GNNs (MPGNNs) with the CONGEST model but make unrealistic assumptions about computational resources, allowing $\textsf{NP-Complete}$ problems to be solved in $O(m)$ depth. We contend that a well-defined computational model is urgently needed to serve as the foundation for discussions on GNN expressiveness. To address these issues, we introduce the Resource-Limited CONGEST (RL-CONGEST) model, incorporating optional preprocessing and postprocessing to form a framework for analyzing GNN expressiveness. Our framework sheds light on computational aspects, including the computational hardness of hash functions in the WL test and the role of virtual nodes in reducing network capacity. Additionally, we suggest that high-order GNNs correspond to first-order model-checking problems, offering new insights into their expressiveness.
• Abstract（参考訳）: グラフニューラルネットワーク(GNN)はグラフ機械学習に広く採用されており、その表現性に重点を置いている。 現代の研究は、それらをWeisfeiler-Lehman (WL)テストや古典グラフアルゴリズムと比較することによって、GNN表現性を評価することが多い。 しかし、既存の分析では、(1)事前処理を用いて表現性を高め、計算コストを見落としている研究、(2)匿名のWLテストの限られたパワーを主張する研究、(3)匿名でない特徴を用いて表現性を高め、ミスマッチを発生させる研究、(3)ConGESTモデルでメッセージパスGNN(MPGNN)を特徴付ける研究があるが、計算資源に関する非現実的な仮定を行い、$\textsf{NP-Complete}$問題を$O(m)$で解決する研究がある。 我々は、GNN表現性に関する議論の基盤となるために、適切に定義された計算モデルが緊急に必要であると主張している。 これらの問題に対処するために、予備処理と後処理を任意に取り入れたResource-Limited CONGEST(RL-CONGEST)モデルを導入し、GNN表現性を解析するためのフレームワークを構築した。 我々のフレームワークは、WLテストにおけるハッシュ関数の計算硬度や、ネットワーク容量の削減における仮想ノードの役割など、計算面に光を当てている。 さらに、高次GNNは1次モデルチェック問題に対応し、表現性に関する新たな洞察を提供することを示唆する。

関連論文リスト

• On the Computational Capability of Graph Neural Networks: A Circuit Complexity Bound Perspective [28.497567290882355]
  グラフニューラルネットワーク(GNN)は、リレーショナルデータに対する学習と推論の標準的なアプローチとなっている。 本稿では,回路複雑性のレンズによるGNNの計算限界について検討する。 具体的には、共通GNNアーキテクチャの回路複雑性を分析し、定数層、線形またはサブ線形埋め込みサイズ、精度の制約の下で、GNNはグラフ接続やグラフ同型といった重要な問題を解くことができないことを証明している。
  論文  参考訳（メタデータ） (2025-01-11T05:54:10Z)
• Generalization Limits of Graph Neural Networks in Identity Effects Learning [12.302336258860116]
  グラフニューラルネットワーク(GNN)は、さまざまなグラフドメインでデータ駆動学習を行う強力なツールとして登場した。 我々は、いわゆるアイデンティティ効果の学習において、GNNの新たな一般化特性と基本的限界を確立する。 我々の研究は、単純な認知タスクを行う際に、GNNの能力を理解する必要性によって動機付けられている。
  論文  参考訳（メタデータ） (2023-06-30T20:56:38Z)
• Rethinking the Expressive Power of GNNs via Graph Biconnectivity [45.4674360883544]
  本稿では,グラフ双連結性による表現度指標の新たなクラスを導入し,理論と実践の両面での重要性を強調した。 我々は、GD-WL(Generalized Distance Weisfeiler-Lehman)と呼ばれる原理的で効率的なアプローチを導入する。 実際に,GD-WLをTransformerのようなアーキテクチャで実装し,完全な並列化性を保ち,実現可能であることを示す。
  論文  参考訳（メタデータ） (2023-01-23T15:58:59Z)
• 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)
• Expressiveness and Approximation Properties of Graph Neural Networks [6.1323142294300625]
  Wesfeiler-Leman (WL) テストの観点で GNN の分離パワーのバウンダリを得るためのエレガントな方法を提供する。 我々はテンソル言語を用いて、MPNNの自然な拡張である高次メッセージパッシングニューラルネットワーク(またはk-MPNN)を定義する。 提案手法は,GNNアーキテクチャ設計者がGNNの分離パワーを解析できるツールボックスを提供する。
  論文  参考訳（メタデータ） (2022-04-10T11:33:04Z)
• Optimization of Graph Neural Networks: Implicit Acceleration by Skip Connections and More Depth [57.10183643449905]
  グラフニューラルネットワーク(GNN)は表現力と一般化のレンズから研究されている。 GNNのダイナミクスを深部スキップ最適化により研究する。 本研究は,GNNの成功に対する最初の理論的支援を提供する。
  論文  参考訳（メタデータ） (2021-05-10T17:59:01Z)
• The Surprising Power of Graph Neural Networks with Random Node Initialization [54.4101931234922]
  グラフニューラルネットワーク(GNN)は、関係データ上での表現学習に有効なモデルである。 標準 GNN はその表現力に制限があり、Weisfeiler-Leman グラフ同型(英語版)の能力以外の区別はできない。 本研究では,ランダムノード(RNI)を用いたGNNの表現力の解析を行う。 我々はこれらのモデルが普遍的であることを証明し、GNNが高次特性の計算に頼らない最初の結果である。
  論文  参考訳（メタデータ） (2020-10-02T19:53:05Z)
• Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning [63.97983530843762]
  グラフニューラルネットワーク(GNN)はグラフ表現学習において大きな成功を収めている。 GNNは、実際には非常に異なるグラフ部分構造に対して同一の表現を生成する。 より強力なGNNは、最近高階試験を模倣して提案され、基礎となるグラフ構造を疎結合にできないため、非効率である。 本稿では,グラフ表現学習の新たなクラスとして距離分解(DE)を提案する。
  論文  参考訳（メタデータ） (2020-08-31T23:15:40Z)
• Expressive Power of Invariant and Equivariant Graph Neural Networks [10.419350129060598]
  Folklore Graph Neural Networks (FGNN) は、与えられたテンソル次数に対してこれまで提案されてきた最も表現力のあるアーキテクチャである。 FGNNはこの問題の解決方法を学ぶことができ、既存のアルゴリズムよりも平均的なパフォーマンスが向上する。
  論文  参考訳（メタデータ） (2020-06-28T16:35:45Z)
• Optimization and Generalization Analysis of Transduction through Gradient Boosting and Application to Multi-scale Graph Neural Networks [60.22494363676747]
  現在のグラフニューラルネットワーク(GNN)は、オーバースムーシング(over-smoothing)と呼ばれる問題のため、自分自身を深くするのは難しいことが知られている。 マルチスケールGNNは、オーバースムーシング問題を緩和するための有望なアプローチである。 マルチスケールGNNを含むトランスダクティブ学習アルゴリズムの最適化と一般化を保証する。
  論文  参考訳（メタデータ） (2020-06-15T17:06:17Z)
• Eigen-GNN: A Graph Structure Preserving Plug-in for GNNs [95.63153473559865]
  グラフニューラルネットワーク(GNN)は、グラフ上の新たな機械学習モデルである。 既存のGNNモデルの多くは浅く、本質的に機能中心である。 我々は,既存の浅いGNNがグラフ構造をよく保存できないことを経験的かつ解析的に示す。 本稿では,グラフ構造保存におけるGNNの能力を高めるプラグインモジュールであるEigen-GNNを提案する。
  論文  参考訳（メタデータ） (2020-06-08T02:47:38Z)

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

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