論文の概要: Rethinking GNN Expressive Power from a Distributed Computational Model Perspective

• arxiv url: http://arxiv.org/abs/2410.01308v3
• Date: Wed, 28 May 2025 11:20:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-29 15:04:26.65161
• Title: Rethinking GNN Expressive Power from a Distributed Computational Model Perspective
• Title（参考訳）: 分散計算モデルから見たGNN表現力の再考
• Authors: Guanyu Cui, Yuhe Guo, Zhewei Wei, Hsin-Hao Su,
• Abstract要約: 事前処理と後処理を明確に指定した修正 CONGEST モデルなど,明確に定義された計算モデルを使用することによって,GNN 表現性を分析するためのより健全なフレームワークが提供される,と我々は主張する。 制約のない事前処理を許可したり、外部に計算された機能を組み込んだりすることは、これらの事前計算によって表現性が向上し、時には問題を引き起こす可能性があることを示す。 これらの否定的な結果にもかかわらず、計算モデルの観点から仮想ノードとエッジの効果を特徴付ける肯定的な結果も提示する。
• 参考スコア（独自算出の注目度）: 21.723600297533835
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The success of graph neural networks (GNNs) has motivated theoretical studies on their expressive power, often through alignments with the Weisfeiler-Lehman (WL) tests. However, such analyses typically focus on the ability of GNNs to distinguish between graph structures, rather than to compute or approximate specific function classes. The latter is more commonly studied in machine learning theory, including results such as the Turing completeness of recurrent networks and the universal approximation property of feedforward networks. We argue that using well-defined computational models, such as a modified CONGEST model with clearly specified preprocessing and postprocessing, offers a more sound framework for analyzing GNN expressiveness. Within this framework, we show that allowing unrestricted preprocessing or incorporating externally computed features, while claiming that these precomputations enhance the expressiveness, can sometimes lead to problems. We also show that the lower bound on a GNN's capacity (depth multiplied by width) to simulate one iteration of the WL test actually grows nearly linearly with graph size, indicating that the WL test is not locally computable and is misaligned with message-passing GNNs. Despite these negative results, we also present positive results that characterize the effects of virtual nodes and edges from a computational model perspective. Finally, we highlight several open problems regarding GNN expressiveness for further exploration.
• Abstract（参考訳）: グラフニューラルネットワーク(GNN)の成功は、しばしばWeisfeiler-Lehman(WL)テストとのアライメントを通じて、その表現力に関する理論的研究を動機付けている。 しかし、そのような分析は通常、特定の関数クラスを計算したり近似したりするのではなく、グラフ構造を区別するGNNの能力に焦点を当てる。 後者は、リカレントネットワークのチューリング完全性やフィードフォワードネットワークの普遍近似特性などの結果を含む、機械学習理論でより一般的に研究されている。 事前処理と後処理を明確に指定した修正 CONGEST モデルなど,明確に定義された計算モデルを使用することによって,GNN 表現性を分析するためのより健全なフレームワークが提供される,と我々は主張する。 この枠組みでは、制約なしの事前処理や外部計算機能の導入が可能である一方で、これらの事前計算によって表現性が向上すると主張している。 また、WLテストの1つの繰り返しをシミュレーションするGNNの容量の低い値が、実際にはグラフサイズとほぼ線形に成長していることを示し、WLテストは局所計算可能ではなく、メッセージパスGNNと不一致であることを示す。 これらの否定的な結果にもかかわらず、計算モデルの観点から仮想ノードとエッジの効果を特徴付ける肯定的な結果も提示する。 最後に,GNNの表現性に関するいくつかのオープンな問題に注目し,さらなる探索を行う。

関連論文リスト

• On the Computational Capability of Graph Neural Networks: A Circuit Complexity Bound Perspective [28.497567290882355]
  グラフニューラルネットワーク(GNN)は、リレーショナルデータに対する学習と推論の標準的なアプローチとなっている。 本稿では,回路複雑性のレンズによるGNNの計算限界について検討する。 具体的には、共通GNNアーキテクチャの回路複雑性を分析し、定数層、線形またはサブ線形埋め込みサイズ、精度の制約の下で、GNNはグラフ接続やグラフ同型といった重要な問題を解くことができないことを証明している。
  論文  参考訳（メタデータ） (2025-01-11T05:54:10Z)
• LOGIN: A Large Language Model Consulted Graph Neural Network Training Framework [30.54068909225463]
  我々は,GNN設計プロセスの合理化とLarge Language Models(LLM)の利点を活用して,下流タスクにおけるGNNの性能向上を目指す。 我々は,LLMs-as-Consultants(LLMs-as-Consultants)という新たなパラダイムを策定し,LLMとGNNを対話的に統合する。 両グラフのノード分類におけるLOGINの有効性を実証的に評価した。
  論文  参考訳（メタデータ） (2024-05-22T18:17:20Z)
• Unleash Graph Neural Networks from Heavy Tuning [33.948899558876604]
  グラフニューラルネットワーク(GNN)は、グラフ型データ用に設計されたディープラーニングアーキテクチャである。 本稿では,光チューニングされた粗い探索中に保存されたチェックポイントから学習することで,高性能なGNNを直接生成するグラフ条件付き潜時拡散フレームワーク(GNN-Diff)を提案する。
  論文  参考訳（メタデータ） (2024-05-21T06:23:47Z)
• The Expressive Power of Graph Neural Networks: A Survey [9.08607528905173]
  定義の異なる表現力向上モデルに関する第1回調査を行う。 モデルは、グラフ機能拡張、グラフトポロジ拡張、GNNアーキテクチャ拡張という3つのカテゴリに基づいてレビューされる。
  論文  参考訳（メタデータ） (2023-08-16T09:12:21Z)
• 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)
• GNNLens: A Visual Analytics Approach for Prediction Error Diagnosis of Graph Neural Networks [42.222552078920216]
  Graph Neural Networks(GNN)は、ディープラーニング技術をグラフデータに拡張することを目的としている。 GNNは、モデル開発者やユーザから詳細を隠したブラックボックスのように振る舞う。 したがって、GNNの潜在的なエラーを診断することは困難である。 本稿では,対話型視覚分析ツールGNNLensで研究ギャップを埋め,モデル開発者やユーザによるGNNの理解と分析を支援する。
  論文  参考訳（メタデータ） (2020-11-22T16:09:08Z)
• 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)
• Attentive Graph Neural Networks for Few-Shot Learning [74.01069516079379]
  グラフニューラルネットワーク(GNN)は、数ショットの学習タスクを含む多くの困難なアプリケーションにおいて、優れたパフォーマンスを示している。 少数のサンプルからモデルを学習し、一般化する能力があるにもかかわらず、GNNは通常、モデルが深くなるにつれて、過度な過度な適合と過度なスムーシングに悩まされる。 本稿では,三重注意機構を組み込むことにより,これらの課題に対処するための新しい注意型GNNを提案する。
  論文  参考訳（メタデータ） (2020-07-14T07:43:09Z)
• 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)
• Efficient Probabilistic Logic Reasoning with Graph Neural Networks [63.099999467118245]
  マルコフ論理ネットワーク(MLN)は、多くの知識グラフ問題に対処するために用いられる。 MLNの推論は計算集約的であり、MLNの産業規模での応用は非常に困難である。 本稿では,表現力とモデルの単純さとのバランスのよいグラフニューラルネット(GNN)モデルであるExpressGNNを提案する。
  論文  参考訳（メタデータ） (2020-01-29T23:34:36Z)

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

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