論文の概要: Effects of Random Edge-Dropping on Over-Squashing in Graph Neural Networks
- arxiv url: http://arxiv.org/abs/2502.07364v1
- Date: Tue, 11 Feb 2025 08:36:38 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-12 14:07:00.171757
- Title: Effects of Random Edge-Dropping on Over-Squashing in Graph Neural Networks
- Title（参考訳）: グラフニューラルネットワークのオーバースキャッシングに及ぼすランダムエッジドローピングの影響
- Authors: Jasraj Singh, Keyue Jiang, Brooks Paige, Laura Toni,
- Abstract要約: 遠方ノード間の感度に対するDropEdgeの負の効果を特徴付ける理論的結果を示す。
我々の発見は容易にその変種に拡張され、過度な監視にどのように影響するかを包括的に理解することが可能になる。
我々の結論は、深いGNNを訓練するために設計された様々な手法を再評価する必要性を浮き彫りにする。
- 参考スコア（独自算出の注目度）: 8.524684315458243
- License:
- Abstract: Message Passing Neural Networks (MPNNs) are a class of Graph Neural Networks (GNNs) that leverage the graph topology to propagate messages across increasingly larger neighborhoods. The message-passing scheme leads to two distinct challenges: over-smoothing and over-squashing. While several algorithms, e.g. DropEdge and its variants -- DropNode, DropAgg and DropGNN -- have successfully addressed the over-smoothing problem, their impact on over-squashing remains largely unexplored. This represents a critical gap in the literature as failure to mitigate over-squashing would make these methods unsuitable for long-range tasks. In this work, we take the first step towards closing this gap by studying the aforementioned algorithms in the context of over-squashing. We present novel theoretical results that characterize the negative effects of DropEdge on sensitivity between distant nodes, suggesting its unsuitability for long-range tasks. Our findings are easily extended to its variants, allowing us to build a comprehensive understanding of how they affect over-squashing. We evaluate these methods using real-world datasets, demonstrating their detrimental effects. Specifically, we show that while DropEdge-variants improve test-time performance in short range tasks, they deteriorate performance in long-range ones. Our theory explains these results as follows: random edge-dropping lowers the effective receptive field of GNNs, which although beneficial for short-range tasks, misaligns the models on long-range ones. This forces the models to overfit to short-range artefacts in the training set, resulting in poor generalization. Our conclusions highlight the need to re-evaluate various methods designed for training deep GNNs, with a renewed focus on modelling long-range interactions.
- Abstract（参考訳）: メッセージパッシングニューラルネットワーク(英: Message Passing Neural Networks、MPNN)は、グラフトポロジを利用するグラフニューラルネットワーク(GNN)のクラスである。
メッセージパッシング方式は、オーバースムーシングとオーバースキャッシングという、2つの異なる課題をもたらす。
DropEdgeとその変種であるDropNode、DropAgg、DropGNNといったいくつかのアルゴリズムは、オーバースムースな問題に対処した。
このことは、オーバースカッシングを軽減できないことが、これらのメソッドが長距離タスクには適さないことを物語の中で示している。
本研究では、上記のアルゴリズムをオーバー・スクワッシングの文脈で研究することで、このギャップを埋める第一歩を踏み出す。
本研究では,DropEdgeが遠隔ノード間の感度に与える影響を特徴付ける新たな理論的結果を示す。
我々の発見は容易にその変種に拡張され、過度な監視にどのように影響するかを包括的に理解することが可能になる。
実世界のデータセットを用いてこれらの手法を評価し,その有害な影響を実証した。
具体的には,DropEdge-variantsは短距離タスクにおけるテスト時間性能を向上するが,長距離タスクでは性能を低下させることを示した。
我々の理論はこれらの結果を次のように説明している: ランダムエッジドロップはGNNの効果的な受容領域を低くする。
これにより、モデルはトレーニングセット内の短い範囲のアーティファクトに過度に適合し、結果として一般化が不十分になる。
我々の結論は、長距離インタラクションのモデリングに重点を置き、深層GNNのトレーニング用に設計された様々な手法を再評価する必要性を浮き彫りにしている。
関連論文リスト
- DeltaGNN: Graph Neural Network with Information Flow Control [5.563171090433323]
グラフニューラルネットワーク(GNN)は、メッセージパッシングプロセスの近傍集約を通じてグラフ構造化データを処理するように設計されている。
メッセージパッシングにより、GNNは短距離空間的相互作用を理解できるだけでなく、過度なスムーシングや過度なスカッシングに悩まされる。
本稿では,線形計算オーバーヘッドを伴うオーバー・スムーシングとオーバー・スキャッシングに対処するための,emph情報フロー制御機構を提案する。
さまざまなサイズ、トポロジ、密度、ホモフィリック比のグラフを含む10の実世界のデータセットを対象に、我々のモデルをベンチマークし、優れたパフォーマンスを示す。
論文 参考訳（メタデータ） (2025-01-10T14:34:20Z) - ADEdgeDrop: Adversarial Edge Dropping for Robust Graph Neural Networks [53.41164429486268]
グラフニューラルネットワーク(GNN)は、近隣ノードからグラフ構造化情報を収集する強力な能力を示した。
GNNの性能は、ノイズや冗長なグラフデータによって引き起こされる一般化の貧弱さと脆弱な堅牢性によって制限される。
本稿では,エッジの除去を誘導する対向エッジ予測器を利用する新しい対向エッジドロップ法 (ADEdgeDrop) を提案する。
論文 参考訳（メタデータ） (2024-03-14T08:31:39Z) - Robust Graph Neural Network based on Graph Denoising [10.564653734218755]
グラフニューラルネットワーク(GNN)は、非ユークリッドデータセットを扱う学習問題に対して、悪名高い代替手段として登場した。
本研究は,観測トポロジにおける摂動の存在を明示的に考慮した,GNNの堅牢な実装を提案する。
論文 参考訳（メタデータ） (2023-12-11T17:43:57Z) - Reducing Over-smoothing in Graph Neural Networks Using Relational
Embeddings [0.15619750966454563]
本稿では,GNNにおけるオーバー・スムーシング問題の影響を緩和する,シンプルで効率的な手法を提案する。
我々の手法は他の手法と組み合わせて最高の性能を与えることができる。
論文 参考訳（メタデータ） (2023-01-07T19:26:04Z) - On the Trade-off between Over-smoothing and Over-squashing in Deep Graph
Neural Networks [8.105516788827451]
グラフ畳み込み層を積み重ねる場合、オーバースムーシングとオーバースキャッシングが重要な課題である。
我々の研究は、過剰な平滑化と過剰な赤道化がグラフラプラシアンのスペクトルギャップに本質的に関係していることを明らかにする。
適切な妥協を実現するために,エッジの追加と削除を実行可能なアプローチとして提案する。
論文 参考訳（メタデータ） (2022-12-05T15:56:08Z) - EIGNN: Efficient Infinite-Depth Graph Neural Networks [51.97361378423152]
グラフニューラルネットワーク(GNN)は多くのアプリケーションでグラフ構造化データのモデリングに広く利用されている。
この制限により、無限深度GNNモデルを提案し、これをEIGNN(Efficient Infinite-Depth Graph Neural Networks)と呼ぶ。
EIGNNは、最近のベースラインよりも長距離依存関係をキャプチャする能力が優れており、常に最先端のパフォーマンスを実現していることを示す。
論文 参考訳（メタデータ） (2022-02-22T08:16:58Z) - Very Deep Graph Neural Networks Via Noise Regularisation [57.450532911995516]
グラフニューラルネットワーク(GNN)は、入力グラフを介して学習されたメッセージパッシングを実行する。
最大100のメッセージパッシングステップを持つディープGNNをトレーニングし、いくつかの最先端の結果を得る。
論文 参考訳（メタデータ） (2021-06-15T08:50:10Z) - A Biased Graph Neural Network Sampler with Near-Optimal Regret [57.70126763759996]
グラフニューラルネットワーク(GNN)は、グラフおよびリレーショナルデータにディープネットワークアーキテクチャを適用する手段として登場した。
本論文では,既存の作業に基づいて,GNN近傍サンプリングをマルチアームバンディット問題として扱う。
そこで本研究では,分散を低減し,不安定かつ非限定的な支払いを回避すべく設計されたバイアスをある程度導入した報酬関数を提案する。
論文 参考訳（メタデータ） (2021-03-01T15:55:58Z) - Understanding and Resolving Performance Degradation in Graph
Convolutional Networks [105.14867349802898]
グラフ畳み込みネットワーク(GCN)は複数のレイヤを積み重ね、グラフ構造化データ上でノード表現を学習するためのPROPとTRANを実行する。
GCNはモデルが深くなるとパフォーマンスが低下する傾向がある。
本稿では,TRANやPROPのみを積み重ねることによるGCNの性能劣化について実験的に検討する。
論文 参考訳（メタデータ） (2020-06-12T12:12:12Z) - On the Bottleneck of Graph Neural Networks and its Practical
Implications [22.704284264177108]
グラフニューラルネットワーク(GNN)は,長い経路でメッセージを集約する場合,ボトルネックの影響を受けやすいことを示す。
このボトルネックは指数関数的に増加する情報を固定サイズのベクトルに過度に振る舞う。
GNNは、遠く離れたノードからのメッセージの伝搬に失敗し、予測タスクが長距離通信に依存する場合、性能が低下する。
論文 参考訳（メタデータ） (2020-06-09T12:04:50Z) - Towards an Efficient and General Framework of Robust Training for Graph
Neural Networks [96.93500886136532]
グラフニューラルネットワーク(GNN)は、いくつかの基本的な推論タスクに大きく進歩している。
GNNの目覚ましい性能にもかかわらず、グラフ構造上の摂動を慎重に作り、誤った予測を下すことが観察されている。
我々は,強靭なGNNを得るために,欲求探索アルゴリズムとゼロ階法を利用する汎用フレームワークを提案する。
論文 参考訳（メタデータ） (2020-02-25T15:17:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。