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

• arxiv url: http://arxiv.org/abs/2302.06835v2
• Date: Tue, 6 Jun 2023 03:57:37 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-07 20:47:38.334185
• Title: Understanding Oversquashing in GNNs through the Lens of Effective Resistance
• Title（参考訳）: 効果的な抵抗レンズによるgnnの過剰探索の理解
• Authors: Mitchell Black and Zhengchao Wan and Amir Nayyeri and Yusu Wang
• Abstract要約: 本研究では,入力グラフに付加されるエッジを同定し,全体の有効抵抗を最小限に抑えるアルゴリズムを開発し,オーバーカッシングを緩和する。 我々は,GNNの性能向上のための総合的有効抵抗に基づくスイッチング戦略の有効性を示す実証的証拠を提供する。
• 参考スコア（独自算出の注目度）: 9.640594614636047
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Message passing graph neural networks (GNNs) are a popular learning architectures for graph-structured data. However, one problem GNNs experience is oversquashing, where a GNN has difficulty sending information between distant nodes. Understanding and mitigating oversquashing has recently received significant attention from the research community. In this paper, we continue this line of work by analyzing oversquashing through the lens of the effective resistance between nodes in the input graph. Effective resistance intuitively captures the ``strength'' of connection between two nodes by paths in the graph, and has a rich literature spanning many areas of graph theory. We propose to use total effective resistance as a bound of the total amount of oversquashing in a graph and provide theoretical justification for its use. We further develop an algorithm to identify edges to be added to an input graph to minimize the total effective resistance, thereby alleviating oversquashing. We provide empirical evidence of the effectiveness of our total effective resistance based rewiring strategies for improving the performance of GNNs.
• Abstract（参考訳）: メッセージパッシンググラフニューラルネットワーク(GNN)は、グラフ構造化データのための一般的な学習アーキテクチャである。 しかし、GNNが遠いノード間で情報を送るのが難しいという問題もある。 オーバースクワッシングの理解と緩和は、最近研究コミュニティから大きな注目を集めている。 本稿では,入力グラフ内のノード間の有効抵抗のレンズによるオーバーカッシングを解析することにより,この作業線を継続する。 有効抵抗は、グラフ内の経路によって2つのノード間の接続の ``strength'' を直感的に捉え、グラフ理論の多くの領域にまたがる豊富な文献を持つ。 本稿では,グラフにおけるオーバーカッシングの総量の境界として全有効抵抗を用い,その使用を理論的に正当化することを提案する。 さらに,入力グラフに付加されるエッジを識別し,全有効抵抗を最小限に抑えるアルゴリズムを開発し,オーバーカッシングを緩和する。 我々は,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)

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

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