論文の概要: FSW-GNN: A Bi-Lipschitz WL-Equivalent Graph Neural Network

• arxiv url: http://arxiv.org/abs/2410.09118v1
• Date: Thu, 10 Oct 2024 18:11:23 GMT
• ステータス: 処理完了
• システム内更新日: 2024-10-30 16:13:24.725486
• Title: FSW-GNN: A Bi-Lipschitz WL-Equivalent Graph Neural Network
• Title（参考訳）: FSW-GNN: バイリプシッツWL等価グラフニューラルネットワーク
• Authors: Yonatan Sverdlov, Yair Davidson, Nadav Dym, Tal Amir,
• Abstract要約: グラフを区別するMPNNの能力は、Weisfeiler-Lemann (WL) グラフ同型テストによって分離できるグラフに限られる。 我々のMPNNは、いくつかのグラフ学習タスクで標準的なMPNNと競合し、過度な長距離タスクでははるかに正確であることを示す。
• 参考スコア（独自算出の注目度）: 2.766564215769441
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Many of the most popular graph neural networks fall into the category of message-passing neural networks (MPNNs). Famously, MPNNs' ability to distinguish between graphs is limited to graphs separable by the Weisfeiler-Lemann (WL) graph isomorphism test, and the strongest MPNNs, in terms of separation power, are WL-equivalent. Recently, it was shown that the quality of separation provided by standard WL-equivalent MPNN can be very low, resulting in WL-separable graphs being mapped to very similar, hardly distinguishable features. This paper addresses this issue by seeking bi-Lipschitz continuity guarantees for MPNNs. We demonstrate that, in contrast with standard summation-based MPNNs, which lack bi-Lipschitz properties, our proposed model provides a bi-Lipschitz graph embedding with respect to two standard graph metrics. Empirically, we show that our MPNN is competitive with standard MPNNs for several graph learning tasks and is far more accurate in over-squashing long-range tasks.
• Abstract（参考訳）: 最も人気のあるグラフニューラルネットワークの多くは、メッセージパッシングニューラルネットワーク(MPNN)のカテゴリに分類される。 有名なことに、MPNNがグラフを区別する能力は、Weisfeiler-Lemann (WL) グラフ同型テストで分離可能なグラフに限られており、分離パワーの観点では最強のMPNNはWL同値である。 近年,標準WL等価MPNNによって提供される分離の質が非常に低くなり,WL分離グラフが非常によく似ており,区別しにくい特徴にマッピングされることが示されている。 本稿では,MPNNに対するバイリプシッツ連続性保証を求めることでこの問題に対処する。 バイリプシッツ特性に欠ける標準和に基づくMPNNとは対照的に,提案モデルは2つの標準グラフメトリクスに対してバイリプシッツグラフを埋め込む。 経験的に、MPNNはいくつかのグラフ学習タスクにおいて、標準的なMPNNと競合し、過度な長距離タスクでははるかに正確であることを示す。

関連論文リスト

• 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)
• 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)
• 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)
• KerGNNs: Interpretable Graph Neural Networks with Graph Kernels [14.421535610157093]
  グラフニューラルネットワーク(GNN)は、下流グラフ関連タスクにおける最先端の手法となっている。 我々は新しいGNNフレームワークKernel Graph Neural Networks(KerGNNs)を提案する。 KerGNNはグラフカーネルをGNNのメッセージパッシングプロセスに統合する。 提案手法は,既存の最先端手法と比較して,競争性能が向上することを示す。
  論文  参考訳（メタデータ） (2022-01-03T06:16:30Z)
• On Graph Neural Networks versus Graph-Augmented MLPs [51.23890789522705]
  Graph-Augmented Multi-Layer Perceptrons (GA-MLPs)は、まずグラフ上の特定のマルチホップ演算子でノード機能を拡張する。 我々は,GA-MLPとGNNの表現力の分離を証明し,指数関数的に成長することを示す。
  論文  参考訳（メタデータ） (2020-10-28T17:59:59Z)
• 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)
• Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting [63.04999833264299]
  グラフサブストラクチャネットワーク(GSN)は,サブストラクチャエンコーディングに基づくトポロジ的に認識可能なメッセージパッシング方式である。 Wesfeiler-Leman (WL) グラフ同型テストよりも厳密に表現可能であることを示す。 グラフ分類と回帰タスクについて広範囲に評価を行い、様々な実世界の環境において最先端の結果を得る。
  論文  参考訳（メタデータ） (2020-06-16T15:30:31Z)
• 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)

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

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