論文の概要: On the Complexity of Optimal Graph Rewiring for Oversmoothing and Oversquashing in Graph Neural Networks

• arxiv url: http://arxiv.org/abs/2603.26140v1
• Date: Fri, 27 Mar 2026 07:50:42 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-30 21:49:48.394178
• Title: On the Complexity of Optimal Graph Rewiring for Oversmoothing and Oversquashing in Graph Neural Networks
• Title（参考訳）: グラフニューラルネットワークにおけるオーバースムーシングとオーバースキャッシングのための最適グラフリウィリングの複雑さについて
• Authors: Mostafa Haghir Chehreghani,
• Abstract要約: グラフニューラルネットワーク(GNN)は、ディープアーキテクチャへのスケールアップにおいて、2つの根本的な課題に直面している。 オーバースムーシングとオーバースキャッシングは、基礎となるグラフ構造と密接に結びついている。 本稿では,そのようなグラフ構造最適化の計算複雑性について理論的に考察する。
• 参考スコア（独自算出の注目度）: 2.8427946758947304
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph Neural Networks (GNNs) face two fundamental challenges when scaled to deep architectures: oversmoothing, where node representations converge to indistinguishable vectors, and oversquashing, where information from distant nodes fails to propagate through bottlenecks. Both phenomena are intimately tied to the underlying graph structure, raising a natural question: can we optimize the graph topology to mitigate these issues? This paper provides a theoretical investigation of the computational complexity of such graph structure optimization. We formulate oversmoothing and oversquashing mitigation as graph optimization problems based on spectral gap and conductance, respectively. We prove that exact optimization for either problem is NP-hard through reductions from Minimum Bisection, establishing NP-completeness of the decision versions. Our results provide theoretical foundations for understanding the fundamental limits of graph rewiring for GNN optimization and justify the use of approximation algorithms and heuristic methods in practice.
• Abstract（参考訳）: グラフニューラルネットワーク(GNN)は、ディープアーキテクチャにスケールされた場合、ノード表現が識別不能なベクトルに収束するオーバースムーシング(oversmoothing)と、遠くのノードからの情報がボトルネックを介して伝播しないオーバースキャッシング(oversquashing)という、2つの基本的な課題に直面している。 グラフトポロジを最適化してこれらの問題を緩和できるだろうか? 本稿では,そのようなグラフ構造最適化の計算複雑性について理論的に考察する。 本稿では,スペクトルギャップとコンダクタンスに基づくグラフ最適化問題として,過度なスムース化と過度な緩和を定式化する。 いずれの問題の正確な最適化も、最小二分法から減算してNP完全性を確立することによりNPハードであることが証明される。 本研究は,GNN最適化におけるグラフリウィリングの基本的限界を理解し,近似アルゴリズムとヒューリスティック手法の使用を正当化するための理論的基礎を提供する。

関連論文リスト

• GADPN: Graph Adaptive Denoising and Perturbation Networks via Singular Value Decomposition [6.24191713518868]
  GADPNはグラフ構造学習フレームワークであり、低ランクな denoising と一般化された構造摂動によってグラフトポロジーを適応的に洗練する。 最先端のパフォーマンスを実現し、効率を大幅に向上させる。 グラフ構造を強固に学習する能力を検証することで、不合理なグラフに挑戦する上で特に大きな利益をもたらす。
  論文  参考訳（メタデータ） (2026-01-13T05:25:32Z)
• A Spectral Interpretation of Redundancy in a Graph Reservoir [51.40366905583043]
  この研究はMRGNN(Multi resolution Reservoir Graph Neural Network)における貯留層の定義を再考する。 コンピュータグラフィックスにおける表面設計の分野で最初に導入されたフェアリングアルゴリズムに基づく変種を提案する。 この論文の中核的な貢献は、ランダムウォークの観点からのアルゴリズムの理論解析にある。
  論文  参考訳（メタデータ） (2025-07-17T10:02:57Z)
• Statistical physics analysis of graph neural networks: Approaching optimality in the contextual stochastic block model [0.0]
  グラフニューラルネットワーク(GNN)は、グラフに関連するデータを処理するように設計されている。 GNNは、繰り返し集約ステップによって遠く離れたノードから情報を集めるのに苦労する可能性がある。 我々は,GCNのアーキテクチャが過度なスムーシングを避けるために,深さとともにスケールしなければならないことを示す。
  論文  参考訳（メタデータ） (2025-03-03T09:55:10Z)
• Spectral Greedy Coresets for Graph Neural Networks [61.24300262316091]
  ノード分類タスクにおける大規模グラフの利用は、グラフニューラルネットワーク(GNN)の現実的な応用を妨げる 本稿では,GNNのグラフコアセットについて検討し,スペクトル埋め込みに基づくエゴグラフの選択により相互依存の問題を回避する。 我々のスペクトルグレディグラフコアセット(SGGC)は、数百万のノードを持つグラフにスケールし、モデル事前学習の必要性を排除し、低ホモフィリーグラフに適用する。
  論文  参考訳（メタデータ） (2024-05-27T17:52:12Z)
• Robust Graph Neural Network based on Graph Denoising [10.564653734218755]
  グラフニューラルネットワーク(GNN)は、非ユークリッドデータセットを扱う学習問題に対して、悪名高い代替手段として登場した。 本研究は,観測トポロジにおける摂動の存在を明示的に考慮した,GNNの堅牢な実装を提案する。
  論文  参考訳（メタデータ） (2023-12-11T17:43:57Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。 効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。 グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2023-06-14T09:21:15Z)
• Gradient scarcity with Bilevel Optimization for Graph Learning [0.0]
  勾配不足は、ノードのサブセットの損失を最小限にすることでグラフを学習する際に発生する。 我々は、この現象の正確な数学的特徴を与え、双レベル最適化にも現れることを証明した。 この問題を緩和するために,グラフ・ツー・グラフモデル(G2G)を用いた潜時グラフ学習,グラフに先行構造を課すグラフ正規化,あるいは直径を縮小した元のグラフよりも大きなグラフを最適化することを提案する。
  論文  参考訳（メタデータ） (2023-03-24T12:37:43Z)
• Comprehensive Graph Gradual Pruning for Sparse Training in Graph Neural Networks [52.566735716983956]
  本稿では,CGPと呼ばれるグラフの段階的プルーニングフレームワークを動的にGNNに提案する。 LTHに基づく手法とは異なり、提案手法では再学習を必要とせず、計算コストを大幅に削減する。 提案手法は,既存の手法の精度を一致させたり,あるいは超えたりしながら,トレーニングと推論の効率を大幅に向上させる。
  論文  参考訳（メタデータ） (2022-07-18T14:23:31Z)
• Learning Graph Structure from Convolutional Mixtures [119.45320143101381]
  本稿では、観測されたグラフと潜伏グラフのグラフ畳み込み関係を提案し、グラフ学習タスクをネットワーク逆(デコンボリューション)問題として定式化する。 固有分解に基づくスペクトル法の代わりに、近似勾配反復をアンロール・トランケートして、グラフデコンボリューションネットワーク(GDN)と呼ばれるパラメータ化ニューラルネットワークアーキテクチャに到達させる。 GDNは、教師付き方式でグラフの分布を学習し、損失関数を適応させることでリンク予測やエッジウェイト回帰タスクを実行し、本質的に帰納的である。
  論文  参考訳（メタデータ） (2022-05-19T14:08:15Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  最適グラフ構造を学習するための二段階最適化手法を提案する。 また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
  論文  参考訳（メタデータ） (2022-05-06T03:37:00Z)

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

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