論文の概要: Generalization and Representational Limits of Graph Neural Networks
- arxiv url: http://arxiv.org/abs/2002.06157v1
- Date: Fri, 14 Feb 2020 18:10:14 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-01 04:03:23.549340
- Title: Generalization and Representational Limits of Graph Neural Networks
- Title(参考訳): グラフニューラルネットワークの一般化と表現限界
- Authors: Vikas K. Garg, Stefanie Jegelka, and Tommi Jaakkola
- Abstract要約: ローカル情報に完全に依存するグラフニューラルネットワーク(GNN)では,いくつかの重要なグラフ特性を計算できないことを示す。
メッセージパッシングGNNに対する最初のデータ依存一般化境界を提供する。
私たちのバウンダリは、既存のVC次元ベースのGNN保証よりもはるかに厳格で、リカレントニューラルネットワークのRademacherバウンダリと同等です。
- 参考スコア(独自算出の注目度): 46.20253808402385
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We address two fundamental questions about graph neural networks (GNNs).
First, we prove that several important graph properties cannot be computed by
GNNs that rely entirely on local information. Such GNNs include the standard
message passing models, and more powerful spatial variants that exploit local
graph structure (e.g., via relative orientation of messages, or local port
ordering) to distinguish neighbors of each node. Our treatment includes a novel
graph-theoretic formalism. Second, we provide the first data dependent
generalization bounds for message passing GNNs. This analysis explicitly
accounts for the local permutation invariance of GNNs. Our bounds are much
tighter than existing VC-dimension based guarantees for GNNs, and are
comparable to Rademacher bounds for recurrent neural networks.
- Abstract(参考訳): グラフニューラルネットワーク(GNN)に関する2つの基本的な問題に対処する。
まず、ローカル情報に完全に依存するGNNでは、いくつかの重要なグラフ特性を計算できないことを示す。
そのようなgnnには、標準的なメッセージパッシングモデルや、ローカルグラフ構造(メッセージの相対方向やローカルポート順序など)を利用して各ノードの隣接を識別する、より強力な空間的変種が含まれている。
我々の治療には、新しいグラフ理論的形式が含まれる。
第2に、メッセージパッシングGNNに対して、最初のデータ依存の一般化境界を提供する。
この分析は、GNNの局所的な置換不変性を明示的に説明している。
私たちのバウンダリは、既存のVC次元ベースのGNN保証よりもはるかに厳格で、リカレントニューラルネットワークのRademacherバウンダリと同等です。
関連論文リスト
- Geodesic Graph Neural Network for Efficient Graph Representation
Learning [34.047527874184134]
我々はGeodesic GNN(GDGNN)と呼ばれる効率的なGNNフレームワークを提案する。
ラベル付けなしでノード間の条件付き関係をモデルに注入する。
ジオデシック表現を前提としたGDGNNは、通常のGNNよりもはるかにリッチな構造情報を持つノード、リンク、グラフ表現を生成することができる。
論文 参考訳(メタデータ) (2022-10-06T02:02:35Z) - Generalizing Aggregation Functions in GNNs:High-Capacity GNNs via
Nonlinear Neighborhood Aggregators [14.573383849211773]
グラフニューラルネットワーク(GNN)は多くのグラフ学習タスクで大きな成功を収めている。
既存のGNNは主に、メッセージの伝搬に線形近傍集約(平均,sum)または最大アグリゲータ(max aggregator)を採用する。
我々は、GNNにおけるメッセージ伝達機構を再考し、GNNにおける近隣情報集約のための一般的な非線形アグリゲータの開発を目指す。
論文 参考訳(メタデータ) (2022-02-18T11:49:59Z) - Feature Correlation Aggregation: on the Path to Better Graph Neural
Networks [37.79964911718766]
グラフニューラルネットワーク(GNN)が導入される以前、不規則なデータ、特にグラフのモデリングと解析は、ディープラーニングのアキレスのヒールであると考えられていた。
本稿では,GNNのコア操作に対して,極めて単純かつ無作為な修正を施した中央ノード置換変分関数を提案する。
モデルの具体的な性能向上は、モデルがより少ないパラメータを使用しながら、有意なマージンで過去の最先端結果を上回った場合に観察される。
論文 参考訳(メタデータ) (2021-09-20T05:04:26Z) - Identity-aware Graph Neural Networks [63.6952975763946]
グラフニューラルネットワーク(ID-GNN)を1-WLテストよりも表現力の高いメッセージクラスを開発しています。
ID-GNNは、メッセージパッシング中にノードのIDを誘導的に考慮することにより、既存のGNNアーキテクチャを拡張します。
既存のGNNをID-GNNに変換すると、挑戦ノード、エッジ、グラフプロパティ予測タスクの平均40%の精度が向上することを示す。
論文 参考訳(メタデータ) (2021-01-25T18: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) - Permutation-equivariant and Proximity-aware Graph Neural Networks with
Stochastic Message Passing [88.30867628592112]
グラフニューラルネットワーク(GNN)は、グラフ上の新たな機械学習モデルである。
置換等価性と近接認識性は、GNNにとって非常に望ましい2つの重要な特性である。
既存のGNNは、主にメッセージパッシング機構に基づいており、同時に2つの特性を保存できないことを示す。
ノードの近さを保つため,既存のGNNをノード表現で拡張する。
論文 参考訳(メタデータ) (2020-09-05T16:46:56Z) - Graph Neural Networks: Architectures, Stability and Transferability [176.3960927323358]
グラフニューラルネットワーク(GNN)は、グラフでサポートされている信号のための情報処理アーキテクチャである。
これらは、個々の層がグラフ畳み込みフィルタのバンクを含む畳み込みニューラルネットワーク(CNN)の一般化である。
論文 参考訳(メタデータ) (2020-08-04T18:57:36Z) - Eigen-GNN: A Graph Structure Preserving Plug-in for GNNs [95.63153473559865]
グラフニューラルネットワーク(GNN)は、グラフ上の新たな機械学習モデルである。
既存のGNNモデルの多くは浅く、本質的に機能中心である。
我々は,既存の浅いGNNがグラフ構造をよく保存できないことを経験的かつ解析的に示す。
本稿では,グラフ構造保存におけるGNNの能力を高めるプラグインモジュールであるEigen-GNNを提案する。
論文 参考訳(メタデータ) (2020-06-08T02:47:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。