論文の概要: Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification

• arxiv url: http://arxiv.org/abs/2506.16110v1
• Date: Thu, 19 Jun 2025 08:01:00 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-23 19:00:04.983816
• Title: Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification
• Title（参考訳）: スペクトル保存スパシフィケーションによるグラフニューラルネットワークのオーバースカッシングの軽減
• Authors: Langzhang Liang, Fanchen Bu, Zixing Song, Zenglin Xu, Shirui Pan, Kijung Shin,
• Abstract要約: 本稿では,構造的ボトルネック低減とグラフ特性保存のバランスをとるグラフ再構成手法を提案する。 本手法は、疎性を維持しながら接続性を高めたグラフを生成し、元のグラフスペクトルを大半保存する。
• 参考スコア（独自算出の注目度）: 81.06278257153835
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The message-passing paradigm of Graph Neural Networks often struggles with exchanging information across distant nodes typically due to structural bottlenecks in certain graph regions, a limitation known as \textit{over-squashing}. To reduce such bottlenecks, \textit{graph rewiring}, which modifies graph topology, has been widely used. However, existing graph rewiring techniques often overlook the need to preserve critical properties of the original graph, e.g., \textit{spectral properties}. Moreover, many approaches rely on increasing edge count to improve connectivity, which introduces significant computational overhead and exacerbates the risk of over-smoothing. In this paper, we propose a novel graph rewiring method that leverages \textit{spectrum-preserving} graph \textit{sparsification}, for mitigating over-squashing. Our method generates graphs with enhanced connectivity while maintaining sparsity and largely preserving the original graph spectrum, effectively balancing structural bottleneck reduction and graph property preservation. Experimental results validate the effectiveness of our approach, demonstrating its superiority over strong baseline methods in classification accuracy and retention of the Laplacian spectrum.
• Abstract（参考訳）: Graph Neural Networksのメッセージパッシングパラダイムは、通常は特定のグラフ領域における構造的ボトルネックのために、遠くのノード間で情報を交換するのに苦労する。 このようなボトルネックを軽減するために、グラフトポロジを修飾する \textit{graph rewiring} が広く使われている。 しかし、既存のグラフ書き換え技術は、しばしば元のグラフの臨界特性、例えば g , \textit{spectral properties} を保存する必要性を見落としている。 さらに、多くのアプローチは接続性を改善するためにエッジ数の増加に依存しており、計算オーバーヘッドが大幅に増加し、過度なスムース化のリスクが悪化する。 本稿では,<textit{spectrum-preserving} graph \textit{sparsification} を利用してオーバースカッシングを緩和する新しいグラフ再構成手法を提案する。 本手法は,空間性を維持しながら接続性を高めたグラフを生成し,元のグラフスペクトルを保存し,構造的ボトルネックの低減とグラフ特性の保存を効果的に両立させる。 実験により,ラプラシアスペクトルの分類精度と保持率において,強いベースライン法よりも優れていることを示すとともに,本手法の有効性を検証した。

関連論文リスト

• A Signed Graph Approach to Understanding and Mitigating Oversmoothing in GNNs [54.62268052283014]
  署名されたグラフの枠組みに基づく統一的な理論的視点を示す。 既存の戦略の多くは、メッセージパッシングを変えて過度な操作に抵抗する負のエッジを暗黙的に導入している。 本稿では,ラベルや特徴の類似性に基づいて署名されたエッジを割り当てるプラグイン・アンド・プレイ方式であるStructure Balanced Propagation (SBP)を提案する。
  論文  参考訳（メタデータ） (2025-02-17T03:25:36Z)
• Cayley Graph Propagation [0.0]
  グラフニューラルネットワーク(GNN)は、オーバースカッシングに弱いと悪名高い。 本研究は, トランケーションが対流膨張特性に有害であることを示す。 完全ケイリーグラフ構造上の情報伝達手法であるCGPを提案する。
  論文  参考訳（メタデータ） (2024-10-04T13:32:34Z)
• Graph Coarsening with Message-Passing Guarantees [10.02138130221506]
  提案手法は,信号の保存に関する理論的保証を示す,粗いグラフに特有な新しいメッセージパッシング操作を提案する。 我々は合成データと実データに対してノード分類タスクを行い、粗いグラフ上で単純メッセージパッシングを行うのと比べて改善された結果を観察する。
  論文  参考訳（メタデータ） (2024-05-28T12:39:24Z)
• Deep Manifold Graph Auto-Encoder for Attributed Graph Embedding [51.75091298017941]
  本稿では,属性付きグラフデータに対する新しいDeep Manifold (Variational) Graph Auto-Encoder (DMVGAE/DMGAE)を提案する。 提案手法は,最先端のベースラインアルゴリズムを,一般的なデータセット間でのダウンストリームタスクの差を大きく越える。
  論文  参考訳（メタデータ） (2024-01-12T17:57:07Z)
• FoSR: First-order spectral rewiring for addressing oversquashing in GNNs [0.0]
  グラフニューラルネットワーク(GNN)は、グラフのエッジに沿ってメッセージを渡すことによって、グラフデータの構造を活用することができる。 本稿では,グラフにエッジを体系的に付加することで過疎化を防止する計算効率のよいアルゴリズムを提案する。 提案アルゴリズムは,いくつかのグラフ分類タスクにおいて,既存のグラフリウィリング手法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2022-10-21T07:58:03Z)
• SoftEdge: Regularizing Graph Classification with Random Soft Edges [18.165965620873745]
  グラフデータ拡張はグラフニューラルネットワーク(GNN)の正規化において重要な役割を果たす 単純なエッジとノード操作は、同じ構造を持つグラフや、GNNをメッセージパッシングするための区別できない構造を生成することができる。 我々は,任意のグラフのエッジの一部にランダムな重みを割り当てて,そのグラフ上の動的近傍を構築するSoftEdgeを提案する。
  論文  参考訳（メタデータ） (2022-04-21T20:12:36Z)
• Understanding over-squashing and bottlenecks on graphs via curvature [17.359098638324546]
  オーバースカッシング(Over-squashing)は、$k$ホップの隣人の数が、$k$で急速に増加する現象である。 我々は新しいエッジベースの曲率を導入し、負の湾曲したエッジがオーバースカッシングの原因であることを証明した。 また,オーバーカッシングを緩和するための曲率に基づく再配線法を提案し,実験的に検証した。
  論文  参考訳（メタデータ） (2021-11-29T13:27:56Z)
• Spectral Graph Convolutional Networks With Lifting-based Adaptive Graph Wavelets [81.63035727821145]
  スペクトルグラフ畳み込みネットワーク(SGCN)はグラフ表現学習において注目を集めている。 本稿では,適応グラフウェーブレットを用いたグラフ畳み込みを実装した新しいスペクトルグラフ畳み込みネットワークを提案する。
  論文  参考訳（メタデータ） (2021-08-03T17:57:53Z)
• GraphMI: Extracting Private Graph Data from Graph Neural Networks [59.05178231559796]
  GNNを反転させてトレーニンググラフのプライベートグラフデータを抽出することを目的とした textbfGraph textbfModel textbfInversion attack (GraphMI) を提案する。 具体的には,グラフ特徴の空間性と滑らかさを保ちながら,グラフエッジの離散性に対処する勾配モジュールを提案する。 エッジ推論のためのグラフトポロジ、ノード属性、ターゲットモデルパラメータを効率的に活用するグラフ自動エンコーダモジュールを設計する。
  論文  参考訳（メタデータ） (2021-06-05T07:07:52Z)

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

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