論文の概要: How does over-squashing affect the power of GNNs?

• arxiv url: http://arxiv.org/abs/2306.03589v2
• Date: Wed, 16 Aug 2023 13:17:03 GMT
• ステータス: 処理完了
• システム内更新日: 2023-08-17 16:40:28.453398
• Title: How does over-squashing affect the power of GNNs?
• Title（参考訳）: オーバースカッシングはGNNのパワーにどのように影響しますか?
• Authors: Francesco Di Giovanni, T. Konstantin Rusch, Michael M. Bronstein, Andreea Deac, Marc Lackenby, Siddhartha Mishra, Petar Veli\v{c}kovi\'c
• Abstract要約: グラフニューラルネットワーク(GNN)は、グラフ構造化データ上での機械学習のための最先端モデルである。 与えられた容量のMPNNがどのノード特徴の関数クラスを学習できるかを決定するための厳密な分析を提供する。 一対のノード間の十分な通信を保証するために、MPNNの容量は十分大きすぎることを証明する。
• 参考スコア（独自算出の注目度）: 39.52168593457813
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph Neural Networks (GNNs) are the state-of-the-art model for machine learning on graph-structured data. The most popular class of GNNs operate by exchanging information between adjacent nodes, and are known as Message Passing Neural Networks (MPNNs). Given their widespread use, understanding the expressive power of MPNNs is a key question. However, existing results typically consider settings with uninformative node features. In this paper, we provide a rigorous analysis to determine which function classes of node features can be learned by an MPNN of a given capacity. We do so by measuring the level of pairwise interactions between nodes that MPNNs allow for. This measure provides a novel quantitative characterization of the so-called over-squashing effect, which is observed to occur when a large volume of messages is aggregated into fixed-size vectors. Using our measure, we prove that, to guarantee sufficient communication between pairs of nodes, the capacity of the MPNN must be large enough, depending on properties of the input graph structure, such as commute times. For many relevant scenarios, our analysis results in impossibility statements in practice, showing that over-squashing hinders the expressive power of MPNNs. We validate our theoretical findings through extensive controlled experiments and ablation studies.
• Abstract（参考訳）: グラフニューラルネットワーク(GNN)は、グラフ構造化データの機械学習のための最先端モデルである。 最もポピュラーなGNNクラスは、隣接ノード間で情報を交換することで動作し、Message Passing Neural Networks (MPNNs)として知られている。 広く使われているMPNNの表現力を理解することは重要な問題である。 しかし、既存の結果は、通常、ノード機能のない設定を考える。 本稿では,与えられたキャパシティを持つMPNNがどのノード特徴の関数クラスを学習できるかを決定するための厳密な分析を行う。 私たちはMPNNが許容するノード間のペアワイズインタラクションのレベルを測定することで実現しています。 この尺度は、大量のメッセージが固定サイズのベクトルに集約されたときに発生する、いわゆるオーバースワッシング効果の新しい定量的特徴付けを提供する。 提案手法を用いて,一対のノード間の十分な通信を保証するために,MPNNの容量は,通勤時間などの入力グラフ構造の性質に応じて十分に大きくなければならないことを示す。 多くの関連するシナリオにおいて、我々の分析は実際には不可能なステートメントを生じさせ、過剰なスカッシングがMPNNの表現力を妨げていることを示す。 我々は,広範囲な制御実験とアブレーション研究を通じて理論的知見を検証する。

関連論文リスト

• Sign is Not a Remedy: Multiset-to-Multiset Message Passing for Learning on Heterophilic Graphs [77.42221150848535]
  我々は、Multiset to Multiset GNN(M2M-GNN)と呼ばれる新しいメッセージパッシング機能を提案する。 M2M-GNNは上述のSMPの限界を効果的に緩和し, 比較性能が向上することを示した。
  論文  参考訳（メタデータ） (2024-05-31T07:39:22Z)
• Probabilistic Graph Rewiring via Virtual Nodes [21.273828055299408]
  メッセージパッシンググラフニューラルネットワーク(MPNN)は、グラフベースの機械学習の強力なパラダイムとして登場した。 MPNNは、受信フィールドの制限や構造的ボトルネックが、グラフ内の情報フローを妨げている、アンダーリーチ(low-reaching)やオーバースキャッシング(over-squashing)といった課題に直面している。 本稿では,暗黙的にメッセージパッシングニューラルネットワーク(IPR-MPNN)を提案する。
  論文  参考訳（メタデータ） (2024-05-27T16:11:49Z)
• Information Flow in Graph Neural Networks: A Clinical Triage Use Case [49.86931948849343]
  グラフニューラルネットワーク(GNN)は、マルチモーダルグラフとマルチリレーショナルグラフを処理する能力によって、医療やその他の領域で人気を集めている。 GNNにおける埋め込み情報のフローが知識グラフ(KG)におけるリンクの予測に与える影響について検討する。 以上の結果から,ドメイン知識をGNN接続に組み込むことで,KGと同じ接続を使用する場合や,制約のない埋め込み伝搬を行う場合よりも優れた性能が得られることが示された。
  論文  参考訳（メタデータ） (2023-09-12T09:18:12Z)
• 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)
• Boosting the Cycle Counting Power of Graph Neural Networks with I$^2$-GNNs [9.806910643086043]
  本稿では,各サブグラフ内のルートノードとその隣人に異なる識別子を割り当てることで,サブグラフMPNNを拡張するための2$-GNNを提案する。 2$-GNNsの識別力は、サブグラフMPNNよりも強く、3WLテストより部分的に強いことが示されている。 我々の知る限りでは、理論的な保証とともに6サイクルを数えられる最初の線形時間GNNモデルである。
  論文  参考訳（メタデータ） (2022-10-22T09:40:00Z)
• Discovering the Representation Bottleneck of Graph Neural Networks from Multi-order Interactions [51.597480162777074]
  グラフニューラルネットワーク(GNN)は、ノード機能を伝搬し、インタラクションを構築するためにメッセージパッシングパラダイムに依存している。 最近の研究は、異なるグラフ学習タスクはノード間の異なる範囲の相互作用を必要とすることを指摘している。 科学領域における2つの共通グラフ構築法、すなわち、emphK-nearest neighbor(KNN)グラフとemphfully-connected(FC)グラフについて検討する。
  論文  参考訳（メタデータ） (2022-05-15T11:38:14Z)
• Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning [63.97983530843762]
  グラフニューラルネットワーク(GNN)はグラフ表現学習において大きな成功を収めている。 GNNは、実際には非常に異なるグラフ部分構造に対して同一の表現を生成する。 より強力なGNNは、最近高階試験を模倣して提案され、基礎となるグラフ構造を疎結合にできないため、非効率である。 本稿では,グラフ表現学習の新たなクラスとして距離分解(DE)を提案する。
  論文  参考訳（メタデータ） (2020-08-31T23:15:40Z)
• How hard is to distinguish graphs with graph neural networks? [32.09819774228997]
  本研究では,メッセージパッシングモデル(MPNN)におけるグラフアイソモーフィズムの分類変種に対する硬度結果の導出を行う。 MPNNは、今日のグラフニューラルネットワークの大部分を包含しており、ノードにユニークな特徴が与えられた場合、普遍的である。 12のグラフ分類タスクと420のネットワークを含む実証的研究は、実際の性能と理論的予測の間に強い整合性を示す。
  論文  参考訳（メタデータ） (2020-05-13T22:28:46Z)

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

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