論文の概要: Graph Neural Networks Are More Powerful Than we Think

• arxiv url: http://arxiv.org/abs/2205.09801v1
• Date: Thu, 19 May 2022 18:40:25 GMT
• ステータス: 処理完了
• システム内更新日: 2022-05-23 12:45:34.102768
• Title: Graph Neural Networks Are More Powerful Than we Think
• Title（参考訳）: グラフニューラルネットワークは思った以上に強力
• Authors: Charilaos I. Kanatsoulis and Alejandro Ribeiro
• Abstract要約: グラフニューラルネットワーク(GNN)は、様々なノードレベルおよびグラフレベルタスクにおいて顕著なパフォーマンスを示す強力な畳み込みアーキテクチャである。 彼らの成功にもかかわらず、GNNの表現力は限られており、Weisfeiler-Lehman (WL)アルゴリズムと同じくらい差別的であるという共通の信念がある。 GNNは、少なくとも1つの固有値が異なるグラフと、WLアルゴリズムよりも確実に表現可能な単純なGNNアーキテクチャを区別できることを示す。
• 参考スコア（独自算出の注目度）: 124.97061497512804
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph Neural Networks (GNNs) are powerful convolutional architectures that have shown remarkable performance in various node-level and graph-level tasks. Despite their success, the common belief is that the expressive power of GNNs is limited and that they are at most as discriminative as the Weisfeiler-Lehman (WL) algorithm. In this paper we argue the opposite and show that the WL algorithm is the upper bound only when the input to the GNN is the vector of all ones. In this direction, we derive an alternative analysis that employs linear algebraic tools and characterize the representational power of GNNs with respect to the eigenvalue decomposition of the graph operators. We show that GNNs can distinguish between any graphs that differ in at least one eigenvalue and design simple GNN architectures that are provably more expressive than the WL algorithm. Thorough experimental analysis on graph isomorphism and graph classification datasets corroborates our theoretical results and demonstrates the effectiveness of the proposed architectures.
• Abstract（参考訳）: グラフニューラルネットワーク(GNN)は、様々なノードレベルおよびグラフレベルタスクにおいて顕著なパフォーマンスを示す強力な畳み込みアーキテクチャである。 彼らの成功にもかかわらず、GNNの表現力は限られており、Weisfeiler-Lehman (WL)アルゴリズムと同じくらい差別的であるという共通の信念がある。 本稿では、逆を論じ、GNNへの入力が全てのベクトルである場合にのみ、WLアルゴリズムが上限となることを示す。 この方向において、線形代数ツールを用いてグラフ演算子の固有値分解に関するGNNの表現力を特徴づける別の解析法を導出する。 GNNは、少なくとも1つの固有値が異なるグラフと、WLアルゴリズムよりも確実に表現可能な単純なGNNアーキテクチャを区別できることを示す。 グラフ同型とグラフ分類データセットに関する徹底した実験分析により,提案するアーキテクチャの有効性が実証された。

関連論文リスト

• Equivariant Polynomials for Graph Neural Networks [38.15983687193912]
  グラフネットワーク(GNN)は本質的に表現力に制限がある。 本稿では、GNNがある程度の同変を計算する能力に基づく代替パワー階層を提案する。 これらの強化されたGNNは、複数のグラフ学習ベンチマークの実験において最先端の結果を示す。
  論文  参考訳（メタデータ） (2023-02-22T18:53:38Z)
• Theoretically Improving Graph Neural Networks via Anonymous Walk Graph Kernels [25.736529232578178]
  グラフニューラルネットワーク(GNN)は、グラフマイニングで大きな成功を収めました。 一般的なGNNとしてMPGNNは、多くのグラフのサブ構造を識別、検出、カウントできないことが理論的に示されている。 理論的にはグラフ構造を区別する能力の強いGNNモデルであるGSKNを提案する。
  論文  参考訳（メタデータ） (2021-04-07T08:50:34Z)
• 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)
• Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting [63.04999833264299]
  グラフサブストラクチャネットワーク(GSN)は,サブストラクチャエンコーディングに基づくトポロジ的に認識可能なメッセージパッシング方式である。 Wesfeiler-Leman (WL) グラフ同型テストよりも厳密に表現可能であることを示す。 グラフ分類と回帰タスクについて広範囲に評価を行い、様々な実世界の環境において最先端の結果を得る。
  論文  参考訳（メタデータ） (2020-06-16T15:30:31Z)
• Eigen-GNN: A Graph Structure Preserving Plug-in for GNNs [95.63153473559865]
  グラフニューラルネットワーク(GNN)は、グラフ上の新たな機械学習モデルである。 既存のGNNモデルの多くは浅く、本質的に機能中心である。 我々は,既存の浅いGNNがグラフ構造をよく保存できないことを経験的かつ解析的に示す。 本稿では,グラフ構造保存におけるGNNの能力を高めるプラグインモジュールであるEigen-GNNを提案する。
  論文  参考訳（メタデータ） (2020-06-08T02:47:38Z)
• XGNN: Towards Model-Level Explanations of Graph Neural Networks [113.51160387804484]
  グラフニューラルネットワーク(GNN)は、隣の情報を集約して組み合わせることでノードの特徴を学習する。 GNNはブラックボックスとして扱われ、人間の知的な説明が欠けている。 我々はモデルレベルでGNNを解釈する新しい手法 XGNN を提案する。
  論文  参考訳（メタデータ） (2020-06-03T23:52:43Z)

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

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