論文の概要: Understanding over-squashing and bottlenecks on graphs via curvature

• arxiv url: http://arxiv.org/abs/2111.14522v1
• Date: Mon, 29 Nov 2021 13:27:56 GMT
• ステータス: 処理完了
• システム内更新日: 2021-11-30 15:41:23.289592
• Title: Understanding over-squashing and bottlenecks on graphs via curvature
• Title（参考訳）: 曲率によるグラフの過剰探索とボトルネックの理解
• Authors: Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, Michael M. Bronstein
• Abstract要約: オーバースカッシング(Over-squashing)は、$k$ホップの隣人の数が、$k$で急速に増加する現象である。 我々は新しいエッジベースの曲率を導入し、負の湾曲したエッジがオーバースカッシングの原因であることを証明した。 また,オーバーカッシングを緩和するための曲率に基づく再配線法を提案し,実験的に検証した。
• 参考スコア（独自算出の注目度）: 17.359098638324546
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Most graph neural networks (GNNs) use the message passing paradigm, in which node features are propagated on the input graph. Recent works pointed to the distortion of information flowing from distant nodes as a factor limiting the efficiency of message passing for tasks relying on long-distance interactions. This phenomenon, referred to as 'over-squashing', has been heuristically attributed to graph bottlenecks where the number of $k$-hop neighbors grows rapidly with $k$. We provide a precise description of the over-squashing phenomenon in GNNs and analyze how it arises from bottlenecks in the graph. For this purpose, we introduce a new edge-based combinatorial curvature and prove that negatively curved edges are responsible for the over-squashing issue. We also propose and experimentally test a curvature-based graph rewiring method to alleviate the over-squashing.
• Abstract（参考訳）: ほとんどのグラフニューラルネットワーク(GNN)は、入力グラフ上にノードの特徴が伝播するメッセージパッシングパラダイムを使用している。 近年の研究では、長距離インタラクションに依存するタスクのメッセージパッシング効率を制限する要因として、遠方のノードから流れる情報の歪みが指摘されている。 オーバー・スカッシング」と呼ばれるこの現象は、$k$ホップの隣人の数が$k$で急速に増加するグラフボトルネックに起因する。 我々は,gnnにおける過剰スキャッシング現象の正確な説明と,グラフのボトルネックから発生する現象の分析を行う。 この目的のために,新しいエッジベースの組合せ曲率を導入し,負に曲がった辺が過剰な探索問題の原因であることを証明した。 また,オーバースワッシングを緩和する曲線型グラフリワイリング手法の提案と実験を行った。

関連論文リスト

• The Effectiveness of Curvature-Based Rewiring and the Role of Hyperparameters in GNNs Revisited [0.7373617024876725]
  グラフニューラルネットワーク(GNN)におけるメッセージパッシングは支配的なパラダイムである 近年、データと計算グラフから入力グラフを切断し、メッセージパッシングを行うグラフリウィリング技術に力を入れている。 オーバーシャッシングは合成データセットで実証されているが、この研究では、曲率ベースのリワイアリングが現実のデータセットにもたらすパフォーマンス向上を再評価する。
  論文  参考訳（メタデータ） (2024-07-12T16:03:58Z)
• Over-Squashing in Riemannian Graph Neural Networks [1.6317061277457001]
  ほとんどのグラフニューラルネットワーク(GNN)は、オーバースカッシング(over-squashing)という現象を起こしやすい。 最近の研究では、グラフのトポロジがオーバー・スカッシングに最も大きな影響を与えることが示されている。 我々は, GNN の埋め込み空間を通じて, オーバースカッシングを緩和できるかどうかを考察する。
  論文  参考訳（メタデータ） (2023-11-27T15:51:07Z)
• BOURNE: Bootstrapped Self-supervised Learning Framework for Unified Graph Anomaly Detection [50.26074811655596]
  自己指導型自己学習(BOURNE)に基づく新しい統合グラフ異常検出フレームワークを提案する。 ノードとエッジ間のコンテキスト埋め込みを交換することで、ノードとエッジの異常を相互に検出できる。 BOURNEは、負のサンプリングを必要としないため、大きなグラフを扱う際の効率を高めることができる。
  論文  参考訳（メタデータ） (2023-07-28T00:44:57Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。 効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。 グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2023-06-14T09:21:15Z)
• Rethinking Explaining Graph Neural Networks via Non-parametric Subgraph Matching [68.35685422301613]
  そこで我々はMatchExplainerと呼ばれる新しい非パラメトリックな部分グラフマッチングフレームワークを提案し、説明的部分グラフを探索する。 ターゲットグラフと他のインスタンスを結合し、ノードに対応する距離を最小化することで最も重要な結合部分構造を識別する。 合成および実世界のデータセットの実験は、最先端のパラメトリックベースラインをかなりのマージンで上回り、MatchExplainerの有効性を示す。
  論文  参考訳（メタデータ） (2023-01-07T05:14:45Z)
• Revisiting Over-smoothing and Over-squashing Using Ollivier-Ricci Curvature [11.592567773739411]
  本研究は,局所グラフ幾何学と過平滑化・過赤化の発生との関係を明らかにする。 Batch Ollivier-Ricci Flowは,オーバー・スムーシングとオーバー・スクアッシングの両方を同時に処理できる新しいリワイニングアルゴリズムである。
  論文  参考訳（メタデータ） (2022-11-28T21:21:31Z)
• FoSR: First-order spectral rewiring for addressing oversquashing in GNNs [0.0]
  グラフニューラルネットワーク(GNN)は、グラフのエッジに沿ってメッセージを渡すことによって、グラフデータの構造を活用することができる。 本稿では,グラフにエッジを体系的に付加することで過疎化を防止する計算効率のよいアルゴリズムを提案する。 提案アルゴリズムは,いくつかのグラフ分類タスクにおいて,既存のグラフリウィリング手法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2022-10-21T07:58:03Z)
• Oversquashing in GNNs through the lens of information contraction and graph expansion [6.8222473597904845]
  本稿では,情報収縮に基づく過疎分析のためのフレームワークを提案する。 オーバーカッシングを緩和するグラフ再配線アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-08-06T08:44:39Z)
• Line Graph Neural Networks for Link Prediction [71.00689542259052]
  実世界の多くのアプリケーションにおいて古典的なグラフ解析問題であるグラフリンク予測タスクについて検討する。 このフォーマリズムでは、リンク予測問題をグラフ分類タスクに変換する。 本稿では,線グラフをグラフ理論に用いて,根本的に異なる新しい経路を求めることを提案する。 特に、線グラフの各ノードは、元のグラフのユニークなエッジに対応するため、元のグラフのリンク予測問題は、グラフ分類タスクではなく、対応する線グラフのノード分類問題として等価に解決できる。
  論文  参考訳（メタデータ） (2020-10-20T05:54:31Z)
• Fast Graph Attention Networks Using Effective Resistance Based Graph Sparsification [70.50751397870972]
  FastGATは、スペクトルスペーシフィケーションを用いて、注目に基づくGNNを軽量にし、入力グラフの最適プルーニングを生成する手法である。 我々は,ノード分類タスクのための大規模実世界のグラフデータセット上でFastGATを実験的に評価した。
  論文  参考訳（メタデータ） (2020-06-15T22:07:54Z)
• Structural Temporal Graph Neural Networks for Anomaly Detection in Dynamic Graphs [54.13919050090926]
  本稿では,動的グラフの異常エッジを検出するために,エンドツーエンドの時間構造グラフニューラルネットワークモデルを提案する。 特に,まずターゲットエッジを中心にした$h$ホップ囲むサブグラフを抽出し,各ノードの役割を識別するノードラベル機能を提案する。 抽出した特徴に基づき,GRU(Gated Recurrent Unit)を用いて,異常検出のための時間的情報を取得する。
  論文  参考訳（メタデータ） (2020-05-15T09:17:08Z)

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

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