論文の概要: Walk Message Passing Neural Networks and Second-Order Graph Neural Networks

• arxiv url: http://arxiv.org/abs/2006.09499v1
• Date: Tue, 16 Jun 2020 20:24:01 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-20 19:47:30.947798
• Title: Walk Message Passing Neural Networks and Second-Order Graph Neural Networks
• Title（参考訳）: ウォークメッセージパッシングニューラルネットワークと2次グラフニューラルネットワーク
• Authors: Floris Geerts
• Abstract要約: 我々は,新しいタイプのMPNNである$ell$-walk MPNNを紹介した。 2ドル(約2万円)のMPNNが表現力で2-WLと一致していることを示す。 特に、W[$ell$]を表現力で一致させるために、各層で$ell-1$行列乗法を許す。
• 参考スコア（独自算出の注目度）: 4.355567556995855
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The expressive power of message passing neural networks (MPNNs) is known to match the expressive power of the 1-dimensional Weisfeiler-Leman graph (1-WL) isomorphism test. To boost the expressive power of MPNNs, a number of graph neural network architectures have recently been proposed based on higher-dimensional Weisfeiler-Leman tests. In this paper we consider the two-dimensional (2-WL) test and introduce a new type of MPNNs, referred to as $\ell$-walk MPNNs, which aggregate features along walks of length $\ell$ between vertices. We show that $2$-walk MPNNs match 2-WL in expressive power. More generally, $\ell$-walk MPNNs, for any $\ell\geq 2$, are shown to match the expressive power of the recently introduced $\ell$-walk refinement procedure (W[$\ell$]). Based on a correspondence between 2-WL and W[$\ell$], we observe that $\ell$-walk MPNNs and $2$-walk MPNNs have the same expressive power, i.e., they can distinguish the same pairs of graphs, but $\ell$-walk MPNNs can possibly distinguish pairs of graphs faster than $2$-walk MPNNs. When it comes to concrete learnable graph neural network (GNN) formalisms that match 2-WL or W[$\ell$] in expressive power, we consider second-order graph neural networks that allow for non-linear layers. In particular, to match W[$\ell$] in expressive power, we allow $\ell-1$ matrix multiplications in each layer. We propose different versions of second-order GNNs depending on the type of features (i.e., coming from a countable set, or coming from an uncountable set) as this affects the number of dimensions needed to represent the features. Our results indicate that increasing non-linearity in layers by means of allowing multiple matrix multiplications does not increase expressive power. At the very best, it results in a faster distinction of input graphs.
• Abstract（参考訳）: メッセージパッシングニューラルネットワーク(MPNN)の表現力は、1次元Weisfeiler-Lemanグラフ(1-WL)の表現力と一致することが知られている。 MPNNの表現力を高めるために、高次元のWeisfeiler-Lemanテストに基づいて、最近多くのグラフニューラルネットワークアーキテクチャが提案されている。 本稿では,2次元 (2-WL) テストについて考察し,その特徴を頂点間距離$\ell$-walk MPNNと呼ばれる新しいタイプのMPNNを導入する。 2ドルのMPNNが2-WLと表現力で一致していることを示す。 より一般的に、$\ell$-walk MPNNは、任意の$\ell\geq 2$に対して、最近導入された$\ell$-walkリファインメントプロシージャ(W[$\ell$])の表現力と一致する。 2-WL と W[$\ell$] の対応に基づき、$\ell$-walk MPNN と $2$-walk MPNN が同じ表現力を持つ、すなわち、同じグラフのペアを区別できるが、$$$-walk MPNN は 2$-walk MPNN よりも早くグラフのペアを区別することができる。 表現力で2-WLまたはW[$\ell$]と一致する具体的な学習可能なグラフニューラルネットワーク(GNN)形式について、非線形層を許容する2階グラフニューラルネットワークを検討する。 特に、W[$\ell$] を表現力で一致させるために、各層で$\ell-1$行列乗法を許す。 我々は、特徴のタイプ(例えば可算集合から来るか、非可算集合から来るか)によって、特徴を表現するのに必要な次元の数に影響するため、2次gnnの異なるバージョンを提案する。 以上の結果から,複数行列乗算による層内の非線形性の増加は表現力を増加させるものではないことが示唆された。 最善の点では、入力グラフの区別がより速くなります。

関連論文リスト

• FSW-GNN: A Bi-Lipschitz WL-Equivalent Graph Neural Network [2.766564215769441]
  グラフを区別するMPNNの能力は、Weisfeiler-Lemann (WL) グラフ同型テストによって分離できるグラフに限られる。 我々のMPNNは、いくつかのグラフ学習タスクで標準的なMPNNと競合し、過度な長距離タスクでははるかに正確であることを示す。
  論文  参考訳（メタデータ） (2024-10-10T18:11:23Z)
• 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)
• Spatio-Spectral Graph Neural Networks [50.277959544420455]
  比スペクトルグラフネットワーク(S$2$GNN)を提案する。 S$2$GNNは空間的およびスペクトル的にパラメータ化されたグラフフィルタを組み合わせる。 S$2$GNNsは、MPGNNsよりも厳密な近似理論誤差境界を生じる。
  論文  参考訳（メタデータ） (2024-05-29T14:28:08Z)
• Fine-grained Expressivity of Graph Neural Networks [15.766353435658043]
  我々は1ドルWLとMPNNの連続的な拡張をグラファイトに検討する。 連続的な1ドルWLの変動は,MPNNのグラフ上での表現力の正確なトポロジ的特徴を与えることを示す。 また,グラフ距離の保存能力に基づいて,異なるMPNNアーキテクチャの評価を行った。
  論文  参考訳（メタデータ） (2023-06-06T14:12:23Z)
• Extending the Design Space of Graph Neural Networks by Rethinking Folklore Weisfeiler-Lehman [66.23316415757456]
  近年、グラフニューラルネットワーク(GNN)の最も人気のあるフレームワークとして、メッセージパッシングニューラルネットワーク(MPNN)が登場している。 しかし、その表現力は1次元のWeisfeiler-Lehman (1-WL) テストによって制限される。 我々は、任意の同変集合をすべてのノードの代わりに隣人と考える拡張、$(k,t)$-FWLを提案する。 N$2-GNN は ZINC-Subset (0.059) で記録破りの結果を達成し、以前の SOTA の成績を 10.6% 上回った。
  論文  参考訳（メタデータ） (2023-06-05T21:35:32Z)
• WL meet VC [9.468816647649104]
  本稿では,Vapnik-Chervonenkis(VC)次元理論のレンズによるグラフニューラルネットワーク(GNN)の表現力について検討する。 我々は、GNNのVC次元と1text-mathsfWL$およびGNNのVC次元によって生成される色数を用いて、GNNのVC次元の上限を導出する。
  論文  参考訳（メタデータ） (2023-01-26T11:29:36Z)
• Two-Dimensional Weisfeiler-Lehman Graph Neural Networks for Link Prediction [61.01337335214126]
  グラフニューラルネットワーク(GNN)のリンク予測 リンク予測のためのほとんどの既存のGNNは、1次元Weisfeiler-Lehman (1-WL) テストに基づいている。 テキスト2次元Weisfeiler-Lehman (2-WL) テストに基づいて,ノード対(リンク)表現を直接取得可能な,まったく異なるアプローチを提案する。
  論文  参考訳（メタデータ） (2022-06-20T04:50:38Z)
• Twin Weisfeiler-Lehman: High Expressive GNNs for Graph Classification [48.087302573188396]
  本稿では,ノードラベルとノードIDを同時に渡す新しいグラフ同型テスト手法Twin-WLを提案する。 2つのツイン-GNNは、従来のメッセージパッシングGNNよりも表現力が高いことが証明された。
  論文  参考訳（メタデータ） (2022-03-22T12:58:03Z)
• Let's Agree to Degree: Comparing Graph Convolutional Networks in the Message-Passing Framework [5.835421173589977]
  我々は、グラフ上に定義されたニューラルネットワークをメッセージパッシングニューラルネットワーク(MPNN)としてキャストした。 匿名MPNNと学位対応MPNNの2種類のMPNNについて検討する。 Wesfeiler-Lehman (WL)アルゴリズムの差分パワーの観点から,MPNNの差分パワーの下位値と上位値を求める。
  論文  参考訳（メタデータ） (2020-04-06T12:14:00Z)
• $\Pi-$nets: Deep Polynomial Neural Networks [86.36557534288535]
  $Pi$-Netsは、出力が入力の高次であるニューラルネットワークである。 我々は、$Pi$-Netsが標準のDCNNよりも優れた表現能力を持っていることを実証的に実証した。 近年のStyleGANのような生成モデルが,先行モデルに改良を加えた理由を解明する。
  論文  参考訳（メタデータ） (2020-03-08T18:48:43Z)
• Can Graph Neural Networks Count Substructures? [53.256112515435355]
  グラフニューラルネットワーク(GNN)の能力について,属性付きグラフサブ構造をカウントする能力を用いて検討する。 我々は2種類のサブストラクチャカウントを区別する: インダクションサブグラフカウントとサブグラフカウント、および人気のあるGNNアーキテクチャに対する肯定的および否定的な回答である。
  論文  参考訳（メタデータ） (2020-02-10T18:53:30Z)

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

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