論文の概要: Let's Agree to Degree: Comparing Graph Convolutional Networks in the
Message-Passing Framework
- arxiv url: http://arxiv.org/abs/2004.02593v1
- Date: Mon, 6 Apr 2020 12:14:00 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-16 05:42:56.006255
- Title: Let's Agree to Degree: Comparing Graph Convolutional Networks in the
Message-Passing Framework
- Title（参考訳）: Degree:メッセージパッシングフレームワークにおけるグラフ畳み込みネットワークの比較
- Authors: Floris Geerts, Filip Mazowiecki and Guillermo A. P\'erez
- Abstract要約: 我々は、グラフ上に定義されたニューラルネットワークをメッセージパッシングニューラルネットワーク(MPNN)としてキャストした。
匿名MPNNと学位対応MPNNの2種類のMPNNについて検討する。
Wesfeiler-Lehman (WL)アルゴリズムの差分パワーの観点から,MPNNの差分パワーの下位値と上位値を求める。
- 参考スコア（独自算出の注目度）: 5.835421173589977
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper we cast neural networks defined on graphs as message-passing
neural networks (MPNNs) in order to study the distinguishing power of different
classes of such models. We are interested in whether certain architectures are
able to tell vertices apart based on the feature labels given as input with the
graph. We consider two variants of MPNNS: anonymous MPNNs whose message
functions depend only on the labels of vertices involved; and degree-aware
MPNNs in which message functions can additionally use information regarding the
degree of vertices. The former class covers a popular formalisms for computing
functions on graphs: graph neural networks (GNN). The latter covers the
so-called graph convolutional networks (GCNs), a recently introduced variant of
GNNs by Kipf and Welling. We obtain lower and upper bounds on the
distinguishing power of MPNNs in terms of the distinguishing power of the
Weisfeiler-Lehman (WL) algorithm. Our results imply that (i) the distinguishing
power of GCNs is bounded by the WL algorithm, but that they are one step ahead;
(ii) the WL algorithm cannot be simulated by "plain vanilla" GCNs but the
addition of a trade-off parameter between features of the vertex and those of
its neighbours (as proposed by Kipf and Welling themselves) resolves this
problem.
- Abstract（参考訳）: 本稿では,グラフ上に定義されたニューラルネットワークをメッセージパッシングニューラルネットワーク(MPNN)としてキャストし,これらのモデルの異なるクラスの識別能力について検討する。
私たちは、グラフの入力として与えられる特徴ラベルに基づいて、あるアーキテクチャが頂点を区別できるかどうかに興味を持っています。
我々は,メッセージ関数が関連する頂点のラベルのみに依存する匿名mpnnと,メッセージ関数が頂点の程度に関する情報を付加できる程度認識mpnnの2つの変種を検討した。
グラフニューラルネットワーク(GNN)は、グラフ上の関数を計算するための一般的な形式である。
後者は、KipfとWellingによって最近導入されたGNNの変種GCN(Graph Convolutional Network)をカバーしている。
Wesfeiler-Lehman (WL)アルゴリズムの差分パワーの観点から,MPNNの差分パワーの下位値と上位値を求める。
私たちの結果は
(i)GCNの識別能力はWLアルゴリズムによって制限されるが、それらは一歩前進している。
(II) WLアルゴリズムは「プレーンバニラ」GCNではシミュレートできないが、頂点の特徴と近隣(キップフとウェリング自身によって提案されている)の特徴との間のトレードオフパラメータの追加によりこの問題は解決される。
関連論文リスト
- FSW-GNN: A Bi-Lipschitz WL-Equivalent Graph Neural Network [2.766564215769441]
グラフを区別するMPNNの能力は、Weisfeiler-Lemann (WL) グラフ同型テストによって分離できるグラフに限られる。
我々のMPNNは、いくつかのグラフ学習タスクで標準的なMPNNと競合し、過度な長距離タスクでははるかに正確であることを示す。
論文 参考訳（メタデータ） (2024-10-10T18:11:23Z) - Uplifting the Expressive Power of Graph Neural Networks through Graph
Partitioning [3.236774847052122]
グラフ分割のレンズによるグラフニューラルネットワークの表現力について検討する。
我々は新しいGNNアーキテクチャ、すなわちグラフ分割ニューラルネットワーク(GPNN)を導入する。
論文 参考訳（メタデータ） (2023-12-14T06:08:35Z) - Weisfeiler and Leman go Hyperbolic: Learning Distance Preserving Node
Representations [26.77596449192451]
グラフニューラルネットワーク(GNN)は、グラフ上の機械学習問題を解決するための有望なツールとして登場した。
本論文では,Weisfeiler-Leman(WL)アルゴリズムによって生成される階層に基づいて,ノード間の距離関数を定義する。
本稿では,ノード間の距離を保存する表現を学習するモデルを提案する。
論文 参考訳（メタデータ） (2022-11-04T15:03:41Z) - Training Graph Neural Networks on Growing Stochastic Graphs [114.75710379125412]
グラフニューラルネットワーク(GNN)は、ネットワーク化されたデータの意味のあるパターンを活用するために、グラフ畳み込みに依存している。
我々は,成長するグラフ列の極限オブジェクトであるグラフオンを利用して,非常に大きなグラフ上のGNNを学習することを提案する。
論文 参考訳（メタデータ） (2022-10-27T16:00:45Z) - KerGNNs: Interpretable Graph Neural Networks with Graph Kernels [14.421535610157093]
グラフニューラルネットワーク(GNN)は、下流グラフ関連タスクにおける最先端の手法となっている。
我々は新しいGNNフレームワークKernel Graph Neural Networks(KerGNNs)を提案する。
KerGNNはグラフカーネルをGNNのメッセージパッシングプロセスに統合する。
提案手法は,既存の最先端手法と比較して,競争性能が向上することを示す。
論文 参考訳（メタデータ） (2022-01-03T06:16:30Z) - Graph Neural Networks with Learnable Structural and Positional
Representations [83.24058411666483]
任意のグラフの大きな問題は、ノードの標準位置情報の欠如である。
ノードの位置ノード(PE)を導入し、Transformerのように入力層に注入する。
両方のGNNクラスで学習可能なPEを考えると、分子データセットのパフォーマンスは2.87%から64.14%に向上する。
論文 参考訳（メタデータ） (2021-10-15T05:59:15Z) - Identity-aware Graph Neural Networks [63.6952975763946]
グラフニューラルネットワーク(ID-GNN)を1-WLテストよりも表現力の高いメッセージクラスを開発しています。
ID-GNNは、メッセージパッシング中にノードのIDを誘導的に考慮することにより、既存のGNNアーキテクチャを拡張します。
既存のGNNをID-GNNに変換すると、挑戦ノード、エッジ、グラフプロパティ予測タスクの平均40%の精度が向上することを示す。
論文 参考訳（メタデータ） (2021-01-25T18:59:01Z) - Distance Encoding: Design Provably More Powerful Neural Networks for
Graph Representation Learning [63.97983530843762]
グラフニューラルネットワーク(GNN)はグラフ表現学習において大きな成功を収めている。
GNNは、実際には非常に異なるグラフ部分構造に対して同一の表現を生成する。
より強力なGNNは、最近高階試験を模倣して提案され、基礎となるグラフ構造を疎結合にできないため、非効率である。
本稿では,グラフ表現学習の新たなクラスとして距離分解(DE)を提案する。
論文 参考訳（メタデータ） (2020-08-31T23:15:40Z) - Graph Neural Networks: Architectures, Stability and Transferability [176.3960927323358]
グラフニューラルネットワーク(GNN)は、グラフでサポートされている信号のための情報処理アーキテクチャである。
これらは、個々の層がグラフ畳み込みフィルタのバンクを含む畳み込みニューラルネットワーク(CNN)の一般化である。
論文 参考訳（メタデータ） (2020-08-04T18:57:36Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。