論文の概要: Understanding Oversquashing in GNNs through the Lens of Effective Resistance

• arxiv url: http://arxiv.org/abs/2302.06835v1
• Date: Tue, 14 Feb 2023 05:16:12 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-15 16:19:46.927005
• Title: Understanding Oversquashing in GNNs through the Lens of Effective Resistance
• Title（参考訳）: 効果的な抵抗レンズによるgnnの過剰探索の理解
• Authors: Mitchell Black and Amir Nayyeri and Zhengchao Wan and Yusu Wang
• Abstract要約: 入力グラフ内のノード間の有効抵抗レンズを用いてオーバーカッシング問題を解析する。 本稿では,グラフにおけるオーバーカッシングの総量を定量化するための尺度として,全有効抵抗の概念を提案する。 入力グラフに付加されるエッジを識別するアルゴリズムを開発し、全有効抵抗を最小化する。
• 参考スコア（独自算出の注目度）: 9.640594614636047
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Message passing graph neural networks are popular learning architectures for graph-structured data. However, it can be challenging for them to capture long range interactions in graphs. One of the potential reasons is the so-called oversquashing problem, first termed in [Alon and Yahav, 2020], that has recently received significant attention. In this paper, we analyze the oversquashing problem through the lens of effective resistance between nodes in the input graphs. The concept of effective resistance intuitively captures the "strength" of connection between two nodes by paths in the graph, and has a rich literature connecting spectral graph theory and circuit networks theory. We propose the use the concept of total effective resistance as a measure to quantify the total amount of oversquashing in a graph, and provide theoretical justification of its use. We further develop algorithms to identify edges to be added to an input graph so as to minimize the total effective resistance, thereby alleviating the oversquashing problem when using GNNs. We provide empirical evidence of the effectiveness of our total effective resistance based rewiring strategies.
• Abstract（参考訳）: メッセージパッシンググラフニューラルネットワークは、グラフ構造化データのための一般的な学習アーキテクチャである。 しかし、グラフ内の長い範囲の相互作用をキャプチャすることは困難である。 考えられる理由の1つは,[alon and yahav, 2020]で最初に言及された,いわゆるオーバースクワッシング問題である。 本稿では,入力グラフのノード間の有効抵抗のレンズを通して,過度な探索問題を解析する。 有効抵抗の概念は、グラフ内の経路によって2つのノード間の接続の「強度」を直感的に捉え、スペクトルグラフ理論と回路ネットワーク理論を結合する豊富な文献を持つ。 本稿では,グラフにおけるオーバーカッシングの総量を定量化するための尺度として,全有効抵抗の概念を提案し,その使用を理論的に正当化する。 さらに,入力グラフに付加されるエッジを識別し,全有効抵抗を最小限に抑えるアルゴリズムを開発し,GNNを用いた場合のオーバーカッシング問題を緩和する。 我々は, 完全有効抵抗法の有効性を示す実証的証拠を提供する。

関連論文リスト

• Information Flow in Graph Neural Networks: A Clinical Triage Use Case [49.86931948849343]
  グラフニューラルネットワーク(GNN)は、マルチモーダルグラフとマルチリレーショナルグラフを処理する能力によって、医療やその他の領域で人気を集めている。 GNNにおける埋め込み情報のフローが知識グラフ(KG)におけるリンクの予測に与える影響について検討する。 以上の結果から,ドメイン知識をGNN接続に組み込むことで,KGと同じ接続を使用する場合や,制約のない埋め込み伝搬を行う場合よりも優れた性能が得られることが示された。
  論文  参考訳（メタデータ） (2023-09-12T09:18:12Z)
• Fast and Effective GNN Training with Linearized Random Spanning Trees [20.73637495151938]
  ノード分類タスクにおいて,GNNをトレーニングするための,より効果的でスケーラブルなフレームワークを提案する。 提案手法は, ランダムに分布する木々の広範囲に分布するGNN重みを徐々に改善する。 これらの経路グラフのスパース性は、GNN訓練の計算負担を大幅に軽減する。
  論文  参考訳（メタデータ） (2023-06-07T23:12:42Z)
• DEGREE: Decomposition Based Explanation For Graph Neural Networks [55.38873296761104]
  我々は,GNN予測に対する忠実な説明を提供するためにDGREEを提案する。 GNNの情報生成と集約機構を分解することにより、DECREEは入力グラフの特定のコンポーネントのコントリビューションを最終的な予測に追跡することができる。 また,従来の手法で見過ごされるグラフノード間の複雑な相互作用を明らかにするために,サブグラフレベルの解釈アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2023-05-22T10:29:52Z)
• Resisting Graph Adversarial Attack via Cooperative Homophilous Augmentation [60.50994154879244]
  最近の研究では、グラフニューラルネットワークは弱く、小さな摂動によって簡単に騙されることが示されている。 本研究では,グラフインジェクションアタック(Graph Injection Attack)という,新興だが重要な攻撃に焦点を当てる。 本稿では,グラフデータとモデルの協調的同好性増強によるGIAに対する汎用防衛フレームワークCHAGNNを提案する。
  論文  参考訳（メタデータ） (2022-11-15T11:44:31Z)
• Anti-Symmetric DGN: a stable architecture for Deep Graph Networks [12.71306369339218]
  安定かつ非散逸的なDGN設計のためのフレームワークであるアンチサイメトリディープグラフネットワーク(A-DGN)を提案する。 A-DGNは性能向上に寄与し、数十のレイヤが使用されている場合でも効果的に学習できる。
  論文  参考訳（メタデータ） (2022-10-18T12:04:55Z)
• Tackling Oversmoothing of GNNs with Contrastive Learning [35.88575306925201]
  グラフニューラルネットワーク(GNN)は、グラフデータと表現学習能力の包括的な関係を統合する。 オーバースムーシングはノードの最終的な表現を識別不能にし、ノード分類とリンク予測性能を劣化させる。 本稿では,TGCL(Topology-Guided Graph Contrastive Layer)を提案する。
  論文  参考訳（メタデータ） (2021-10-26T15:56:16Z)
• Uniting Heterogeneity, Inductiveness, and Efficiency for Graph Representation Learning [68.97378785686723]
  グラフニューラルネットワーク(GNN)は,グラフ上のノード表現学習の性能を大幅に向上させた。 GNNの過半数クラスは均質グラフのためにのみ設計されており、より有益な異種グラフに劣る適応性をもたらす。 本稿では,低次ノードと高次ノードの両方のエッジに付随するヘテロジニアスなノード特徴をパッケージ化する,新しい帰納的メタパスフリーメッセージパッシング方式を提案する。
  論文  参考訳（メタデータ） (2021-04-04T23:31:39Z)
• Information Obfuscation of Graph Neural Networks [96.8421624921384]
  本稿では,グラフ構造化データを用いた学習において,情報難読化による機密属性保護の問題について検討する。 本稿では,全変動量とワッサーシュタイン距離を交互に学習することで,事前決定された機密属性を局所的にフィルタリングするフレームワークを提案する。
  論文  参考訳（メタデータ） (2020-09-28T17:55:04Z)
• Fast Graph Attention Networks Using Effective Resistance Based Graph Sparsification [70.50751397870972]
  FastGATは、スペクトルスペーシフィケーションを用いて、注目に基づくGNNを軽量にし、入力グラフの最適プルーニングを生成する手法である。 我々は,ノード分類タスクのための大規模実世界のグラフデータセット上でFastGATを実験的に評価した。
  論文  参考訳（メタデータ） (2020-06-15T22:07:54Z)

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

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