論文の概要: On the Connection Between MPNN and Graph Transformer
- arxiv url: http://arxiv.org/abs/2301.11956v1
- Date: Fri, 27 Jan 2023 19:15:31 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-31 19:59:34.351589
- Title: On the Connection Between MPNN and Graph Transformer
- Title（参考訳）: MPNNとグラフ変換器の接続について
- Authors: Chen Cai, Truong Son Hy, Rose Yu, Yusu Wang
- Abstract要約: Graph Transformer (GT) はグラフ学習アルゴリズムの新しいパラダイムとして登場した。
仮想ノード(VN)を持つMPNNは,GTの自己保持層を任意に近似できるほど強力であることを示す。
- 参考スコア（独自算出の注目度）: 23.86842313651931
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Graph Transformer (GT) recently has emerged as a new paradigm of graph
learning algorithms, outperforming the previously popular Message Passing
Neural Network (MPNN) on multiple benchmarks. Previous work (Kim et al., 2022)
shows that with proper position embedding, GT can approximate MPNN arbitrarily
well, implying that GT is at least as powerful as MPNN. In this paper, we study
the inverse connection and show that MPNN with virtual node (VN), a commonly
used heuristic with little theoretical understanding, is powerful enough to
arbitrarily approximate the self-attention layer of GT.
In particular, we first show that if we consider one type of linear
transformer, the so-called Performer/Linear Transformer (Choromanski et al.,
2020; Katharopoulos et al., 2020), then MPNN + VN with only O(1) depth and O(1)
width can approximate a self-attention layer in Performer/Linear Transformer.
Next, via a connection between MPNN + VN and DeepSets, we prove the MPNN + VN
with O(n^d) width and O(1) depth can approximate the self-attention layer
arbitrarily well, where d is the input feature dimension. Lastly, under some
assumptions, we provide an explicit construction of MPNN + VN with O(1) width
and O(n) depth approximating the self-attention layer in GT arbitrarily well.
On the empirical side, we demonstrate that 1) MPNN + VN is a surprisingly
strong baseline, outperforming GT on the recently proposed Long Range Graph
Benchmark (LRGB) dataset, 2) our MPNN + VN improves over early implementation
on a wide range of OGB datasets and 3) MPNN + VN outperforms Linear Transformer
and MPNN on the climate modeling task.
- Abstract（参考訳）: グラフトランスフォーマー(GT)は最近、グラフ学習アルゴリズムの新しいパラダイムとして登場し、これまで人気があったMPNN(Message Passing Neural Network)を、複数のベンチマークで上回っている。
以前の研究 (Kim et al., 2022) は、適切な位置埋め込みで、GTがMPNNを任意に近似できることを示し、GTが少なくともMPNNと同じくらい強力であることを示唆している。
本稿では, 逆接続について検討し, 理論的な理解がほとんどない一般のヒューリスティックである仮想ノード (vn) を持つ mpnn が gt の自己結合層を任意に近似できるほど強力であることを示す。
特に,1種類の線形変換器,いわゆるPerformer/Linear Transformer(Choromanski et al., 2020; Katharopoulos et al., 2020)を考えると,O(1)深さとO(1)幅しか持たないMPNN+VNはPerformer/Linear Transformerの自己保持層を近似することができる。
次に、MPNN + VN と DeepSets の接続を通して、MPNN + VN を O(n^d) 幅で証明し、O(1) 深さは d が入力特徴次元であるような自己認識層を任意に近似することができる。
最後に、いくつかの仮定の下で、GT における自己保持層を任意に近似する O(1) 幅と O(n) 深さの MPNN + VN の明示的な構成を提供する。
実証的な側面では、
1) MPNN + VNは驚くほど強力なベースラインであり、最近提案されたLong Range Graph Benchmark(LRGB)データセットでGTを上回っている。
2)MPNN+VNは、幅広いOGBデータセットの早期実装よりも改善されている。
3)MPNN+VNはLinear TransformerとMPNNより気候モデリングに優れる。
関連論文リスト
- Spatio-Spectral Graph Neural Networks [50.277959544420455]
比スペクトルグラフネットワーク(S$2$GNN)を提案する。
S$2$GNNは空間的およびスペクトル的にパラメータ化されたグラフフィルタを組み合わせる。
S$2$GNNsは、MPGNNsよりも厳密な近似理論誤差境界を生じる。
論文 参考訳（メタデータ） (2024-05-29T14:28:08Z) - Rethinking the Capacity of Graph Neural Networks for Branching Strategy [40.99368410911088]
グラフニューラルネットワーク(GNN)は、混合整数線形プログラム(MILP)の特性を予測するために広く利用されている。
本稿では,強い分岐(SB)を示すGNNの能力について検討する。
我々はMP-GNNがSBスコアを正確に近似できる「MP-tractable」MILPのクラスを定義する。
論文 参考訳（メタデータ） (2024-02-11T04:09:50Z) - How does over-squashing affect the power of GNNs? [39.52168593457813]
グラフニューラルネットワーク(GNN)は、グラフ構造化データ上での機械学習のための最先端モデルである。
与えられた容量のMPNNがどのノード特徴の関数クラスを学習できるかを決定するための厳密な分析を提供する。
一対のノード間の十分な通信を保証するために、MPNNの容量は十分大きすぎることを証明する。
論文 参考訳（メタデータ） (2023-06-06T11:15:53Z) - Graph Neural Networks are Inherently Good Generalizers: Insights by
Bridging GNNs and MLPs [71.93227401463199]
本稿では、P(ropagational)MLPと呼ばれる中間モデルクラスを導入することにより、GNNの性能向上を本質的な能力に向ける。
PMLPは、トレーニングにおいてはるかに効率的でありながら、GNNと同等(あるいはそれ以上)に動作することを観察する。
論文 参考訳（メタデータ） (2022-12-18T08:17:32Z) - Empowering GNNs via Edge-Aware Weisfeiler-Leman Algorithm [79.68451803954751]
メッセージパッシンググラフニューラルネットワーク(GNN)は1次元Weisfeiler-Leman (1-WL)アルゴリズムによって上界表現性を持つことが知られている。
本稿では,メッセージパッシング方式のスケーラビリティを保った汎用かつ実証可能なGNNフレームワークを提案する。
論文 参考訳（メタデータ） (2022-06-04T21:37:59Z) - From Stars to Subgraphs: Uplifting Any GNN with Local Structure
Awareness [23.279464786779787]
私たちはMPNNをより表現力のあるものにするための一般的なフレームワークを導入します。
私たちのフレームワークは1&2-WLよりも強力で、3WLよりも強力です。
本手法は,いくつかのよく知られたグラフMLタスクに対して,新たな最先端性能を大きなマージンで設定する。
論文 参考訳（メタデータ） (2021-10-07T19:08:08Z) - Identity-aware Graph Neural Networks [63.6952975763946]
グラフニューラルネットワーク(ID-GNN)を1-WLテストよりも表現力の高いメッセージクラスを開発しています。
ID-GNNは、メッセージパッシング中にノードのIDを誘導的に考慮することにより、既存のGNNアーキテクチャを拡張します。
既存のGNNをID-GNNに変換すると、挑戦ノード、エッジ、グラフプロパティ予測タスクの平均40%の精度が向上することを示す。
論文 参考訳（メタデータ） (2021-01-25T18:59:01Z) - Bi-GCN: Binary Graph Convolutional Network [57.733849700089955]
ネットワークパラメータと入力ノードの特徴を二項化するバイナリグラフ畳み込みネットワーク(Bi-GCN)を提案する。
我々のBi-GCNは、ネットワークパラメータと入力データの両方で平均30倍のメモリ消費を削減でき、推論速度を平均47倍に加速できる。
論文 参考訳（メタデータ） (2020-10-15T07:26:23Z) - Walk Message Passing Neural Networks and Second-Order Graph Neural
Networks [4.355567556995855]
我々は,新しいタイプのMPNNである$ell$-walk MPNNを紹介した。
2ドル(約2万円)のMPNNが表現力で2-WLと一致していることを示す。
特に、W[$ell$]を表現力で一致させるために、各層で$ell-1$行列乗法を許す。
論文 参考訳（メタデータ） (2020-06-16T20:24:01Z) - Tensor-to-Vector Regression for Multi-channel Speech Enhancement based
on Tensor-Train Network [53.47564132861866]
マルチチャネル音声強調のためのテンソル-ベクトル回帰手法を提案する。
キーとなる考え方は、従来のディープニューラルネットワーク(DNN)ベースのベクトル-ベクトル回帰の定式化を、テンソル-トレインネットワーク(TTN)フレームワークで行うことである。
8チャンネル条件では、3.12のPSSQはTTNの2000万のパラメータを使用して達成されるが、6800万のパラメータを持つDNNは3.06のPSSQしか達成できない。
論文 参考訳（メタデータ） (2020-02-03T02:58:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。