論文の概要: Mitigating Over-Smoothing and Over-Squashing using Augmentations of Forman-Ricci Curvature

• arxiv url: http://arxiv.org/abs/2309.09384v1
• Date: Sun, 17 Sep 2023 21:43:18 GMT
• ステータス: 処理完了
• システム内更新日: 2023-09-19 15:52:18.622292
• Title: Mitigating Over-Smoothing and Over-Squashing using Augmentations of Forman-Ricci Curvature
• Title（参考訳）: Forman-Ricci曲率の増大による過スムージングと過スワッシングの緩和
• Authors: Lukas Fesser and Melanie Weber
• Abstract要約: スケーラブルな曲率表記法であるAFRC(Augmented Forman-Ricci curvature)に基づく書き換え手法を提案する。 AFRCはメッセージパッシングGNNにおける過剰なスムースと過剰なスキャッシング効果を効果的に特徴付ける。
• 参考スコア（独自算出の注目度）: 1.3144299362395917
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: While Graph Neural Networks (GNNs) have been successfully leveraged for learning on graph-structured data across domains, several potential pitfalls have been described recently. Those include the inability to accurately leverage information encoded in long-range connections (over-squashing), as well as difficulties distinguishing the learned representations of nearby nodes with growing network depth (over-smoothing). An effective way to characterize both effects is discrete curvature: Long-range connections that underlie over-squashing effects have low curvature, whereas edges that contribute to over-smoothing have high curvature. This observation has given rise to rewiring techniques, which add or remove edges to mitigate over-smoothing and over-squashing. Several rewiring approaches utilizing graph characteristics, such as curvature or the spectrum of the graph Laplacian, have been proposed. However, existing methods, especially those based on curvature, often require expensive subroutines and careful hyperparameter tuning, which limits their applicability to large-scale graphs. Here we propose a rewiring technique based on Augmented Forman-Ricci curvature (AFRC), a scalable curvature notation, which can be computed in linear time. We prove that AFRC effectively characterizes over-smoothing and over-squashing effects in message-passing GNNs. We complement our theoretical results with experiments, which demonstrate that the proposed approach achieves state-of-the-art performance while significantly reducing the computational cost in comparison with other methods. Utilizing fundamental properties of discrete curvature, we propose effective heuristics for hyperparameters in curvature-based rewiring, which avoids expensive hyperparameter searches, further improving the scalability of the proposed approach.
• Abstract（参考訳）: グラフニューラルネットワーク(GNN)は、ドメイン間のグラフ構造化データ学習に成功しているが、いくつかの潜在的な落とし穴が最近説明されている。 それらは、長距離接続でエンコードされた情報を正確に活用できないことや、ネットワークの深さを増加させることで、近くのノードの学習した表現を区別することの困難さを含む。 両効果を特徴づける効果的な方法は離散曲率である: オーバースキャッシング効果の根底にある長距離接続は低曲率であるが、オーバースムーシングに寄与するエッジは高曲率である。 この観察は、過剰なスムーシングと過剰なスケーシングを緩和するためにエッジを追加または削除する技術を生み出した。 グラフの曲率やラプラシアンのスペクトルなどのグラフ特性を利用するいくつかの再配線手法が提案されている。 しかし、既存の手法、特に曲率に基づく手法は、しばしば高価なサブルーチンと注意深いハイパーパラメータチューニングを必要とし、大規模なグラフに適用性を制限する。 本稿では、線形時間で計算可能なスケーラブルな曲率表記法であるAFRC(Augmented Forman-Ricci curvature)に基づく書き換え手法を提案する。 AFRCはメッセージパッシングGNNにおける過剰なスムースと過剰なスキャッシング効果を効果的に特徴付ける。 提案手法は,他の手法と比較して計算コストを大幅に削減しつつ,最先端の性能を実現することを示す実験により理論的結果を補完する。 離散曲率の基本特性を生かして,高コストなハイパーパラメータ探索を回避し,提案手法のスケーラビリティを向上する,曲率ベースリワイアリングにおけるハイパーパラメータの効果的なヒューリスティックスを提案する。

関連論文リスト

• The Effectiveness of Curvature-Based Rewiring and the Role of Hyperparameters in GNNs Revisited [0.7373617024876725]
  グラフニューラルネットワーク(GNN)におけるメッセージパッシングは支配的なパラダイムである 近年、データと計算グラフから入力グラフを切断し、メッセージパッシングを行うグラフリウィリング技術に力を入れている。 オーバーシャッシングは合成データセットで実証されているが、この研究では、曲率ベースのリワイアリングが現実のデータセットにもたらすパフォーマンス向上を再評価する。
  論文  参考訳（メタデータ） (2024-07-12T16:03:58Z)
• Revisiting Edge Perturbation for Graph Neural Network in Graph Data Augmentation and Attack [58.440711902319855]
  エッジ摂動はグラフ構造を変更する方法である。 グラフニューラルネットワーク(GNN)の性能への影響に基づき、2つの静脈に分類できる。 統一的な定式化を提案し、エッジ摂動法の2つのカテゴリ間の明確な境界を確立する。
  論文  参考訳（メタデータ） (2024-03-10T15:50:04Z)
• Revealing Decurve Flows for Generalized Graph Propagation [108.80758541147418]
  本研究は,有向グラフと重み付きグラフを用いて,m文を一般化した伝播を定義することによって,従来のメッセージパッシング(中心からグラフ学習)の限界に対処する。 この分野ではじめて、データセットにおける学習された伝播パターンの予備的な探索を含む。
  論文  参考訳（メタデータ） (2024-02-13T14:13:17Z)
• DeepRicci: Self-supervised Graph Structure-Feature Co-Refinement for Alleviating Over-squashing [72.70197960100677]
  グラフ構造学習(GSL)はグラフニューラルネットワーク(GNN)を改良したグラフで強化する上で重要な役割を果たしている。 GSLソリューションは、通常、タスク固有の監督(ノード分類)による構造改善に焦点を当てるか、GNN自体の固有の弱点を見落としている。 本稿では,典型的なGNNにおけるオーバー・スカッシングの問題を効果的に緩和する,自己教師付きグラフ構造-機能共分法について検討する。
  論文  参考訳（メタデータ） (2024-01-23T14:06:08Z)
• Accelerating Scalable Graph Neural Network Inference with Node-Adaptive Propagation [80.227864832092]
  グラフニューラルネットワーク(GNN)は、様々なアプリケーションで例外的な効果を発揮している。 大規模グラフの重大化は,GNNによるリアルタイム推論において重要な課題となる。 本稿では,オンライン伝搬フレームワークと2つの新しいノード適応伝搬手法を提案する。
  論文  参考訳（メタデータ） (2023-10-17T05:03:00Z)
• Revisiting Over-smoothing and Over-squashing Using Ollivier-Ricci Curvature [11.592567773739411]
  本研究は,局所グラフ幾何学と過平滑化・過赤化の発生との関係を明らかにする。 Batch Ollivier-Ricci Flowは,オーバー・スムーシングとオーバー・スクアッシングの両方を同時に処理できる新しいリワイニングアルゴリズムである。
  論文  参考訳（メタデータ） (2022-11-28T21:21:31Z)
• Efficient Graph Neural Network Inference at Large Scale [54.89457550773165]
  グラフニューラルネットワーク(GNN)は、幅広いアプリケーションで優れた性能を示している。 既存のスケーラブルなGNNは、線形伝搬を利用して特徴を前処理し、トレーニングと推論の手順を高速化する。 本稿では,そのトポロジ情報に基づいて各ノードに対してパーソナライズされた伝搬順序を生成する適応的伝搬順序法を提案する。
  論文  参考訳（メタデータ） (2022-11-01T14:38:18Z)
• Optimization-Induced Graph Implicit Nonlinear Diffusion [64.39772634635273]
  我々はGIND(Graph Implicit Diffusion)と呼ばれる新しいグラフ畳み込み変種を提案する。 GINDは暗黙的に隣人の無限のホップにアクセスでき、非線型拡散を伴う特徴を適応的に集約することで過度な平滑化を防いでいる。 学習された表現は、明示的な凸最適化目標の最小化として定式化できることを示す。
  論文  参考訳（メタデータ） (2022-06-29T06:26:42Z)
• Understanding over-squashing and bottlenecks on graphs via curvature [17.359098638324546]
  オーバースカッシング(Over-squashing)は、$k$ホップの隣人の数が、$k$で急速に増加する現象である。 我々は新しいエッジベースの曲率を導入し、負の湾曲したエッジがオーバースカッシングの原因であることを証明した。 また,オーバーカッシングを緩和するための曲率に基づく再配線法を提案し,実験的に検証した。
  論文  参考訳（メタデータ） (2021-11-29T13:27:56Z)
• Improved Analysis of Clipping Algorithms for Non-convex Optimization [19.507750439784605]
  最近、citetzhang 2019gradient show that clipped (stochastic) Gradient Descent (GD) converges faster than vanilla GD/SGD。 実験は、深層学習におけるクリッピングに基づく手法の優位性を確認する。
  論文  参考訳（メタデータ） (2020-10-05T14:36:59Z)

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

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