論文の概要: How Powerful are K-hop Message Passing Graph Neural Networks
- arxiv url: http://arxiv.org/abs/2205.13328v1
- Date: Thu, 26 May 2022 13:03:56 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-27 13:18:14.808631
- Title: How Powerful are K-hop Message Passing Graph Neural Networks
- Title（参考訳）: k-hopメッセージパッシンググラフニューラルネットワークはいかに強力か
- Authors: Jiarui Feng, Yixin Chen, Fuhai Li, Anindya Sarkar, Muhan Zhang
- Abstract要約: 理論的には、Kホップメッセージパッシングの表現力の特徴付けを行う。
表現力が高いにもかかわらず、Kホップメッセージパッシングが依然として単純な正規グラフを区別できないことを示す。
KP-GNNフレームワークを導入し、各ホップの周辺サブグラフ情報を活用することにより、Kホップメッセージパッシングを改善する。
- 参考スコア（独自算出の注目度）: 29.30591474875481
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The most popular design paradigm for Graph Neural Networks (GNNs) is 1-hop
message passing -- aggregating features from 1-hop neighbors repeatedly.
However, the expressive power of 1-hop message passing is bounded by the
Weisfeiler-Lehman (1-WL) test. Recently, researchers extended 1-hop message
passing to K-hop message passing by aggregating information from K-hop
neighbors of nodes simultaneously. However, there is no work on analyzing the
expressive power of K-hop message passing. In this work, we theoretically
characterize the expressive power of K-hop message passing. Specifically, we
first formally differentiate two kinds of kernels of K-hop message passing
which are often misused in previous works. We then characterize the expressive
power of K-hop message passing by showing that it is more powerful than 1-hop
message passing. Despite the higher expressive power, we show that K-hop
message passing still cannot distinguish some simple regular graphs. To further
enhance its expressive power, we introduce a KP-GNN framework, which improves
K-hop message passing by leveraging the peripheral subgraph information in each
hop. We prove that KP-GNN can distinguish almost all regular graphs including
some distance regular graphs which could not be distinguished by previous
distance encoding methods. Experimental results verify the expressive power and
effectiveness of KP-GNN. KP-GNN achieves competitive results across all
benchmark datasets.
- Abstract（参考訳）: グラフニューラルネットワーク(gnns)の最も一般的な設計パラダイムは、1-hopメッセージパッシングである。
しかし、1-hopメッセージの表現力はweisfeiler-lehman (1-wl) テストによって制限される。
近年,k-hop近傍ノードからの情報を同時集約することで,k-hopメッセージパッシングに1-hopメッセージパッシングを拡張した。
しかし、k-hopメッセージパッシングの表現力を分析する作業はない。
本研究では,Kホップメッセージパッシングの表現力を理論的に特徴づける。
具体的には、まず2種類のk-hopメッセージパスのカーネルを形式的に区別する。
次に、k-hopメッセージパッシングの表現力の特徴として、1-hopメッセージパッシングよりも強力であることを示す。
表現力が高いにもかかわらず、Kホップメッセージパッシングが依然として単純な正規グラフを区別できないことを示す。
さらに表現力を高めるために,各ホップ内の周辺サブグラフ情報を活用することで,Kホップメッセージパッシングを改善するKP-GNNフレームワークを導入する。
KP-GNNは,従来の距離符号化法では区別できない距離正規グラフを含む,ほぼすべての正規グラフを識別できることを示す。
KP-GNNの表現力と有効性を検証する実験結果を得た。
KP-GNNは、すべてのベンチマークデータセット間で競合する結果を達成する。
関連論文リスト
- Improving the Expressiveness of $K$-hop Message-Passing GNNs by Injecting Contextualized Substructure Information [17.56609419806051]
K$ホップメッセージパスGNNの表現力を高めるために,テキストサブストラクチャ符号化関数を提案する。
提案手法は,従来の$K$-hopグラフニューラルネットワークや1-WLサブグラフGNNよりも強力である。
論文 参考訳（メタデータ） (2024-06-27T15:10:56Z) - Fine-grained Expressivity of Graph Neural Networks [15.766353435658043]
我々は1ドルWLとMPNNの連続的な拡張をグラファイトに検討する。
連続的な1ドルWLの変動は,MPNNのグラフ上での表現力の正確なトポロジ的特徴を与えることを示す。
また,グラフ距離の保存能力に基づいて,異なるMPNNアーキテクチャの評価を行った。
論文 参考訳（メタデータ） (2023-06-06T14:12:23Z) - A Practical, Progressively-Expressive GNN [27.267362661067285]
近年,メッセージパッシングニューラルネットワーク(MPNN)がグラフニューラルネットワーク(GNN)の主流となっている。
MPNNは、グラフ同型テストのフレームワークにおいてグラフを区別する1次元のWeisfeiler-Leman (1-WL)テストと同じくらい強力である。
我々は,k-tuples ノードから =c 連結成分上で定義された=k ノードの集合へ移動することで,k-WL から k-WL への複雑性を大幅に低減した (k, c)(=)-SETWL 階層を提案する。
論文 参考訳（メタデータ） (2022-10-18T01:27:21Z) - Are Message Passing Neural Networks Really Helpful for Knowledge Graph
Completion? [49.858038034580005]
単純なモデルでMPNNに匹敵する性能が得られることを示す。
評価関数と損失関数の設計がKGCモデルの性能に強い影響を与えることを示す。
論文 参考訳（メタデータ） (2022-05-21T18:14:52Z) - Representation Power of Graph Neural Networks: Improved Expressivity via
Algebraic Analysis [124.97061497512804]
標準グラフニューラルネットワーク (GNN) はWeisfeiler-Lehman (WL) アルゴリズムよりも差別的な表現を生成する。
また、白い入力を持つ単純な畳み込みアーキテクチャは、グラフの閉経路をカウントする同変の特徴を生じさせることを示した。
論文 参考訳（メタデータ） (2022-05-19T18:40:25Z) - GraphHop++: New Insights into GraphHop and Its Enhancement [37.61655151222875]
GraphHopと呼ばれる拡張ラベル伝搬(LP)法が最近提案されている。
グラフ畳み込みネットワーク(GCN)は、様々なネットワーク上の半教師付きノード分類タスクにおいて優れる。
グラフ上で定義された特定の正規化問題に対して、グラフホップが代替的な最適化を提供することを示す。
論文 参考訳（メタデータ） (2022-04-19T03:58:47Z) - Twin Weisfeiler-Lehman: High Expressive GNNs for Graph Classification [48.087302573188396]
本稿では,ノードラベルとノードIDを同時に渡す新しいグラフ同型テスト手法Twin-WLを提案する。
2つのツイン-GNNは、従来のメッセージパッシングGNNよりも表現力が高いことが証明された。
論文 参考訳（メタデータ） (2022-03-22T12:58:03Z) - SMORE: Knowledge Graph Completion and Multi-hop Reasoning in Massive
Knowledge Graphs [147.73127662757335]
我々は、知識グラフ(KG)におけるシングルホップおよびマルチホップ推論のための最初の汎用フレームワークであるスケーラブルなマルチホップ推論(SMORE)を提案する。
シングルマシンのSMOREはFreebase KG(86Mエンティティ、338Mエッジ)でマルチホップ推論を行うことができる。
SMOREは、従来のマルチホップKGフレームワークよりもスループット(トレーニング速度)を、最小のGPUメモリ要件で2.2倍向上させる。
論文 参考訳（メタデータ） (2021-10-28T05:02:33Z) - Multi-hop Question Generation with Graph Convolutional Network [58.31752179830959]
マルチホップ質問生成(Multi-hop Question Generation, QG)は,異なる段落から散在する複数の証拠を集約・推論することで,回答に関連する質問を生成することを目的とする。
複数のホップでコンテキストエンコーディングを行うMulQG(Multi-Hop volution Fusion Network for Question Generation)を提案する。
提案モデルでは,高い完全性を有する流動的な質問を生成することができ,マルチホップ評価において,最強のベースラインを20.8%向上させることができる。
論文 参考訳（メタデータ） (2020-10-19T06:15:36Z) - Distance Encoding: Design Provably More Powerful Neural Networks for
Graph Representation Learning [63.97983530843762]
グラフニューラルネットワーク(GNN)はグラフ表現学習において大きな成功を収めている。
GNNは、実際には非常に異なるグラフ部分構造に対して同一の表現を生成する。
より強力なGNNは、最近高階試験を模倣して提案され、基礎となるグラフ構造を疎結合にできないため、非効率である。
本稿では,グラフ表現学習の新たなクラスとして距離分解(DE)を提案する。
論文 参考訳（メタデータ） (2020-08-31T23:15:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。