論文の概要: Oversquashing in GNNs through the lens of information contraction and graph expansion

• arxiv url: http://arxiv.org/abs/2208.03471v1
• Date: Sat, 6 Aug 2022 08:44:39 GMT
• ステータス: 処理完了
• システム内更新日: 2022-08-09 14:31:07.663121
• Title: Oversquashing in GNNs through the lens of information contraction and graph expansion
• Title（参考訳）: 情報収縮とグラフ展開のレンズによるGNNのオーバーカッシング
• Authors: Pradeep Kr. Banerjee, Kedar Karhadkar, Yu Guang Wang, Uri Alon, Guido Mont\'ufar
• Abstract要約: 本稿では,情報収縮に基づく過疎分析のためのフレームワークを提案する。 オーバーカッシングを緩和するグラフ再配線アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 6.8222473597904845
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The quality of signal propagation in message-passing graph neural networks (GNNs) strongly influences their expressivity as has been observed in recent works. In particular, for prediction tasks relying on long-range interactions, recursive aggregation of node features can lead to an undesired phenomenon called "oversquashing". We present a framework for analyzing oversquashing based on information contraction. Our analysis is guided by a model of reliable computation due to von Neumann that lends a new insight into oversquashing as signal quenching in noisy computation graphs. Building on this, we propose a graph rewiring algorithm aimed at alleviating oversquashing. Our algorithm employs a random local edge flip primitive motivated by an expander graph construction. We compare the spectral expansion properties of our algorithm with that of an existing curvature-based non-local rewiring strategy. Synthetic experiments show that while our algorithm in general has a slower rate of expansion, it is overall computationally cheaper, preserves the node degrees exactly and never disconnects the graph.
• Abstract（参考訳）: メッセージパッシンググラフニューラルネットワーク(GNN)における信号伝搬の質は、最近の研究で見られるように、その表現性に強く影響を及ぼす。 特に、長距離インタラクションに依存する予測タスクでは、ノード機能の再帰的な集約は、"oversquashing"と呼ばれる望ましくない現象につながる可能性がある。 本稿では,情報収縮に基づくオーバースクワッシング分析の枠組みを提案する。 我々の解析はフォン・ノイマンによる信頼性計算モデルによって導かれ、ノイズの多い計算グラフにおける信号の待ち行列としての新しい洞察を与える。 そこで本研究では,オーバーカッシングを緩和するグラフ再構成アルゴリズムを提案する。 本アルゴリズムは、拡張グラフ構成に動機づけられたランダムな局所エッジフリッププリミティブを用いる。 提案アルゴリズムのスペクトル展開特性と既存の曲率に基づく非局所再配線戦略との比較を行った。 合成実験により、我々のアルゴリズムは拡張速度が遅いが、全体的な計算コストが低く、ノードの度合いを正確に保ち、グラフを切断しないことを示した。

関連論文リスト

• Over-Squashing in Riemannian Graph Neural Networks [1.6317061277457001]
  ほとんどのグラフニューラルネットワーク(GNN)は、オーバースカッシング(over-squashing)という現象を起こしやすい。 最近の研究では、グラフのトポロジがオーバー・スカッシングに最も大きな影響を与えることが示されている。 我々は, GNN の埋め込み空間を通じて, オーバースカッシングを緩和できるかどうかを考察する。
  論文  参考訳（メタデータ） (2023-11-27T15:51:07Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。 効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。 グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2023-06-14T09:21:15Z)
• Graph Signal Sampling for Inductive One-Bit Matrix Completion: a Closed-form Solution [112.3443939502313]
  グラフ信号解析と処理の利点を享受する統合グラフ信号サンプリングフレームワークを提案する。 キーとなる考え方は、各ユーザのアイテムのレーティングをアイテムイットグラフの頂点上の関数(信号)に変換することである。 オンライン設定では、グラフフーリエ領域における連続ランダムガウス雑音を考慮したベイズ拡張(BGS-IMC)を開発する。
  論文  参考訳（メタデータ） (2023-02-08T08:17:43Z)
• FoSR: First-order spectral rewiring for addressing oversquashing in GNNs [0.0]
  グラフニューラルネットワーク(GNN)は、グラフのエッジに沿ってメッセージを渡すことによって、グラフデータの構造を活用することができる。 本稿では,グラフにエッジを体系的に付加することで過疎化を防止する計算効率のよいアルゴリズムを提案する。 提案アルゴリズムは,いくつかのグラフ分類タスクにおいて,既存のグラフリウィリング手法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2022-10-21T07:58:03Z)
• Expander Graph Propagation [0.0]
  本稿では,拡張グラフ上での情報伝達に基づくエレガントなアプローチを提案する。 EGPは、セットアップに最小限の労力を要しながら、上記の懸念に対処できることを示します。 我々の分析は、GNNの過剰な監視に対処する、スケーラブルな方法の新たなクラスへの道を開くものだと信じています。
  論文  参考訳（メタデータ） (2022-10-06T15:36:37Z)
• Understanding over-squashing and bottlenecks on graphs via curvature [17.359098638324546]
  オーバースカッシング(Over-squashing)は、$k$ホップの隣人の数が、$k$で急速に増加する現象である。 我々は新しいエッジベースの曲率を導入し、負の湾曲したエッジがオーバースカッシングの原因であることを証明した。 また,オーバーカッシングを緩和するための曲率に基づく再配線法を提案し,実験的に検証した。
  論文  参考訳（メタデータ） (2021-11-29T13:27:56Z)
• Towards Deeper Graph Neural Networks [63.46470695525957]
  グラフ畳み込みは近傍の集約を行い、最も重要なグラフ操作の1つである。 いくつかの最近の研究で、この性能劣化は過度に滑らかな問題に起因している。 本研究では,大きな受容領域からの情報を適応的に組み込むディープ適応グラフニューラルネットワーク(DAGNN)を提案する。
  論文  参考訳（メタデータ） (2020-07-18T01:11:14Z)
• Graph Pooling with Node Proximity for Hierarchical Representation Learning [80.62181998314547]
  本稿では,ノード近接を利用したグラフプーリング手法を提案し,そのマルチホップトポロジを用いたグラフデータの階層的表現学習を改善する。 その結果,提案したグラフプーリング戦略は,公開グラフ分類ベンチマークデータセットの集合において,最先端のパフォーマンスを達成できることが示唆された。
  論文  参考訳（メタデータ） (2020-06-19T13:09:44Z)
• 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)
• Hierarchical Representation Learning in Graph Neural Networks with Node Decimation Pooling [31.812988573924674]
  グラフニューラルネットワーク(GNN)では、プール演算子は入力グラフの局所的な要約を計算し、そのグローバルな特性をキャプチャする。 グラフトポロジ全体を保存しながら粗いグラフを生成するGNNのためのプール演算子であるNode Decimation Pooling (NDP)を提案する。 NDPは、最先端のグラフプーリング演算子よりも効率的であり、同時に、様々なグラフ分類タスクにおける競合性能にも達する。
  論文  参考訳（メタデータ） (2019-10-24T21:42:12Z)

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

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