論文の概要: Representation Power of Graph Neural Networks: Improved Expressivity via Algebraic Analysis

• arxiv url: http://arxiv.org/abs/2205.09801v3
• Date: Fri, 21 Jul 2023 22:30:27 GMT
• ステータス: 処理完了
• システム内更新日: 2023-07-26 01:09:07.548429
• Title: Representation Power of Graph Neural Networks: Improved Expressivity via Algebraic Analysis
• Title（参考訳）: グラフニューラルネットワークの表現力:代数解析による表現性の向上
• Authors: Charilaos I. Kanatsoulis and Alejandro Ribeiro
• Abstract要約: 標準グラフニューラルネットワーク (GNN) はWeisfeiler-Lehman (WL) アルゴリズムよりも差別的な表現を生成する。 また、白い入力を持つ単純な畳み込みアーキテクチャは、グラフの閉経路をカウントする同変の特徴を生じさせることを示した。
• 参考スコア（独自算出の注目度）: 124.97061497512804
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Despite the remarkable success of Graph Neural Networks (GNNs), the common belief is that their representation power is limited and that they are at most as expressive as the Weisfeiler-Lehman (WL) algorithm. In this paper, we argue the opposite and show that standard GNNs, with anonymous inputs, produce more discriminative representations than the WL algorithm. Our novel analysis employs linear algebraic tools and characterizes the representation power of GNNs with respect to the eigenvalue decomposition of the graph operators. We prove that GNNs are able to generate distinctive outputs from white uninformative inputs, for, at least, all graphs that have different eigenvalues. We also show that simple convolutional architectures with white inputs, produce equivariant features that count the closed paths in the graph and are provably more expressive than the WL representations. Thorough experimental analysis on graph isomorphism and graph classification datasets corroborates our theoretical results and demonstrates the effectiveness of the proposed approach.
• Abstract（参考訳）: グラフニューラルネットワーク(GNN)の顕著な成功にもかかわらず、その表現力は限られており、Weisfeiler-Lehman(WL)アルゴリズムと同程度に表現力があるという共通の信念がある。 本稿では、その逆を論じ、匿名入力を持つ標準GNNがWLアルゴリズムよりも差別的な表現を生成することを示す。 本稿では,線形代数ツールを用いてグラフ演算子の固有値分解に関して,GNNの表現力を特徴付ける。 我々は、GNNが、少なくとも異なる固有値を持つ全てのグラフに対して、白い非形式的な入力から特徴的な出力を生成することができることを証明した。 また、ホワイトインプットを持つ単純な畳み込みアーキテクチャは、グラフの閉路を数え、WL表現よりも確実に表現できる同変特徴を持つことを示す。 グラフ同型とグラフ分類データセットに関する徹底的な実験分析により,提案手法の有効性が実証された。

関連論文リスト

• A Manifold Perspective on the Statistical Generalization of Graph Neural Networks [84.01980526069075]
  我々は、スペクトル領域の多様体からサンプリングされたグラフ上のGNNの統計的一般化理論を確立するために多様体の視点を取る。 我々はGNNの一般化境界が対数スケールのグラフのサイズとともに線形に減少し、フィルタ関数のスペクトル連続定数とともに線形的に増加することを証明した。
  論文  参考訳（メタデータ） (2024-06-07T19:25:02Z)
• GOAt: Explaining Graph Neural Networks via Graph Output Attribution [32.66251068600664]
  本稿では,入力グラフの特徴にグラフ出力を属性付ける新しい手法として,グラフ出力属性(GOAt)を提案する。 GOAtは忠実で差別的で、類似のサンプルで安定している。 提案手法は, 一般に使用されている忠実度測定値において, 最先端のGNN説明器よりも優れていることを示す。
  論文  参考訳（メタデータ） (2024-01-26T00:32:58Z)
• Uplifting the Expressive Power of Graph Neural Networks through Graph Partitioning [3.236774847052122]
  グラフ分割のレンズによるグラフニューラルネットワークの表現力について検討する。 我々は新しいGNNアーキテクチャ、すなわちグラフ分割ニューラルネットワーク(GPNN)を導入する。
  論文  参考訳（メタデータ） (2023-12-14T06:08:35Z)
• Generalization Limits of Graph Neural Networks in Identity Effects Learning [12.302336258860116]
  グラフニューラルネットワーク(GNN)は、さまざまなグラフドメインでデータ駆動学習を行う強力なツールとして登場した。 我々は、いわゆるアイデンティティ効果の学習において、GNNの新たな一般化特性と基本的限界を確立する。 我々の研究は、単純な認知タスクを行う際に、GNNの能力を理解する必要性によって動機付けられている。
  論文  参考訳（メタデータ） (2023-06-30T20:56:38Z)
• Weisfeiler-Lehman goes Dynamic: An Analysis of the Expressive Power of Graph Neural Networks for Attributed and Dynamic Graphs [1.3757956340051607]
  グラフニューラルネットワーク(GNN)は、グラフ処理のための大規模なリレーショナルモデルである。 GNNの表現力に関する最近の研究は、グラフを識別する能力に焦点を当てている。 実生活のアプリケーションは、しばしばより広い種類のグラフを含む。
  論文  参考訳（メタデータ） (2022-10-08T10:14:41Z)
• GraphSVX: Shapley Value Explanations for Graph Neural Networks [81.83769974301995]
  グラフニューラルネットワーク(GNN)は、幾何データに基づく様々な学習タスクにおいて大きな性能を発揮する。 本稿では,既存のGNN解説者の多くが満足する統一フレームワークを提案する。 GNN用に特別に設計されたポストホックローカルモデル非依存説明法であるGraphSVXを紹介します。
  論文  参考訳（メタデータ） (2021-04-18T10:40:37Z)
• Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning [63.97983530843762]
  グラフニューラルネットワーク(GNN)はグラフ表現学習において大きな成功を収めている。 GNNは、実際には非常に異なるグラフ部分構造に対して同一の表現を生成する。 より強力なGNNは、最近高階試験を模倣して提案され、基礎となるグラフ構造を疎結合にできないため、非効率である。 本稿では,グラフ表現学習の新たなクラスとして距離分解(DE)を提案する。
  論文  参考訳（メタデータ） (2020-08-31T23:15:40Z)
• Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting [63.04999833264299]
  グラフサブストラクチャネットワーク(GSN)は,サブストラクチャエンコーディングに基づくトポロジ的に認識可能なメッセージパッシング方式である。 Wesfeiler-Leman (WL) グラフ同型テストよりも厳密に表現可能であることを示す。 グラフ分類と回帰タスクについて広範囲に評価を行い、様々な実世界の環境において最先端の結果を得る。
  論文  参考訳（メタデータ） (2020-06-16T15:30:31Z)
• XGNN: Towards Model-Level Explanations of Graph Neural Networks [113.51160387804484]
  グラフニューラルネットワーク(GNN)は、隣の情報を集約して組み合わせることでノードの特徴を学習する。 GNNはブラックボックスとして扱われ、人間の知的な説明が欠けている。 我々はモデルレベルでGNNを解釈する新しい手法 XGNN を提案する。
  論文  参考訳（メタデータ） (2020-06-03T23:52:43Z)

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

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