論文の概要: Effective Resistance Rewiring: A Simple Topological Correction for Over-Squashing
- arxiv url: http://arxiv.org/abs/2603.11944v1
- Date: Thu, 12 Mar 2026 13:55:48 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-03-13 14:46:26.122634
- Title: Effective Resistance Rewiring: A Simple Topological Correction for Over-Squashing
- Title（参考訳）: オーバーカッシングのための簡易なトポロジカル補正
- Authors: Bertran Miquel-Oliver, Manel Gil-Sorribes, Victor Guallar, Alexis Molina,
- Abstract要約: 本稿では,実効抵抗をグローバル信号として利用し,構造的ボトルネックを検出する単純なトポロジ補正手法であるEffective resistance Rewiring(ERR)を紹介する。
ERRは、最大の抵抗を持つノードペア間のエッジを反復的に追加し、最小抵抗のエッジを除去し、弱い通信経路を強化する。
層間におけるノード埋め込みのコサイン類似性を追跡することにより、初期ノード特徴と学習された表現の関係がメッセージパッシング中にどのように進化するかを検討する。
- 参考スコア（独自算出の注目度）: 0.03636228980200798
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Graph Neural Networks struggle to capture long-range dependencies due to over-squashing, where information from exponentially growing neighborhoods must pass through a small number of structural bottlenecks. While recent rewiring methods attempt to alleviate this limitation, many rely on local criteria such as curvature, which can overlook global connectivity constraints that restrict information flow. We introduce Effective Resistance Rewiring (ERR), a simple topology correction strategy that uses effective resistance as a global signal to detect structural bottlenecks. ERR iteratively adds edges between node pairs with the largest resistance while removing edges with minimal resistance, strengthening weak communication pathways while controlling graph densification under a fixed edge budget. The procedure is parameter-free beyond the rewiring budget and relies on a single global measure aggregating all paths between node pairs. Beyond predictive performance with GCN models, we analyze how rewiring affects message propagation. By tracking cosine similarity between node embeddings across layers, we examine how the relationship between initial node features and learned representations evolves during message passing, comparing graphs with and without rewiring. This analysis helps determine whether improvements arise from better long-range communication rather than changes in embedding geometry. Experiments on homophilic and heterophilic graphs, including directed settings with DirGCN, reveal a trade-off between over-squashing and oversmoothing, where oversmoothing corresponds to the loss of representation diversity across layers. Resistance-guided rewiring improves connectivity and signal propagation but can accelerate representation mixing in deep models. Combining ERR with normalization techniques such as PairNorm stabilizes this trade-off and improves performance.
- Abstract（参考訳）: グラフニューラルネットワークは、急激に成長する近隣からの情報が少数の構造的ボトルネックを通り抜けなければならない、オーバースカッシング(over-squshing)による長距離依存関係のキャプチャに苦労する。
最近のリワイア法はこの制限を緩和しようとするが、情報フローを制限するグローバルな接続制約を無視できる曲率のような局所的な基準に頼っている。
本稿では,実効抵抗をグローバル信号として利用し,構造的ボトルネックを検出する単純なトポロジ補正手法であるEffective resistance Rewiring(ERR)を紹介する。
ERRは、最大の抵抗を持つノードペア間のエッジを反復的に追加し、最小の抵抗を持つエッジを除去し、固定されたエッジ予算の下でグラフの密度を制御しながら弱い通信経路を強化する。
この手順は、変更予算を超えてパラメータフリーであり、ノードペア間のすべてのパスを集約する単一のグローバル測度に依存している。
GCNモデルによる予測性能以外にも、リウィリングがメッセージの伝搬にどのように影響するかを分析する。
層間におけるノード埋め込みのコサイン類似性を追跡することにより、初期ノード特徴と学習された表現の関係がメッセージパッシング中にどのように進化するかを調べ、グラフを切り替えることなく比較する。
この分析は、埋め込み幾何学の変化よりも、より優れた長距離通信から改善が生じるかどうかを判断するのに役立つ。
DirGCNによる配向設定を含むホモ親和性グラフとヘテロ親和性グラフの実験では、オーバー・スキャッシングとオーバー・スムーシングのトレードオフが示され、オーバー・スムーシングは層間における表現の多様性の喪失に対応する。
抵抗誘導リ配線は接続性や信号伝搬を改善するが、深層モデルでの表現混合を加速することができる。
ERRとPairNormのような正規化技術を組み合わせることで、このトレードオフが安定し、パフォーマンスが向上する。
関連論文リスト
- On the Geometric Coherence of Global Aggregation in Federated GNN [0.0]
フェデレートラーニング(FL)は、集中的なデータ共有なしに、複数のクライアント間で分散トレーニングを可能にする。
グラフニューラルネットワーク(GNN)は、メッセージパッシングを通じて関係データをモデル化する。
フェデレートされたGNN設定では、クライアントグラフは不均一な構造と伝搬特性を示すことが多い。
本研究は,クロスドメインフェデレーションGNNにおけるグローバルアグリゲーションの幾何学的障害モードを特定する。
本稿では,サーバサイドのフレームワークであるGGRSを提案する。
論文 参考訳（メタデータ） (2026-02-17T11:34:04Z) - Generalizing GNNs with Tokenized Mixture of Experts [75.8310720413187]
安定性の向上には,変化に敏感な特徴への依存を低減し,既約最悪の一般化フロアを残す必要があることを示す。
本研究では,STEM-GNNを提案する。STEM-GNN,STEM-GNN,STEM-GNN,STEM-GNN,STEM-GNN,STEM-GNN,STEM-GNN,STEM-GNN,STEM-GNN。
9つのノード、リンク、グラフのベンチマークで、STEM-GNNはより強力な3方向バランスを実現し、クリアグラフ上での競争力を維持しながら、次数/ホモフィリーシフトや特徴/エッジの破損に対する堅牢性を改善している。
論文 参考訳（メタデータ） (2026-02-09T22:48:30Z) - Riemannian Flow Matching for Disentangled Graph Domain Adaptation [51.98961391065951]
グラフドメイン適応(GDA)は典型的には、ユークリッド空間におけるグラフ埋め込みの整列に逆学習を使用する。
DisRFMは、埋め込みとフローベースのトランスポートを統一する幾何学的なGDAフレームワークである。
論文 参考訳（メタデータ） (2026-01-31T11:05:35Z) - Structural Invariance Matters: Rethinking Graph Rewiring through Graph Metrics [52.077620040518646]
我々は、リワイアが様々なグラフ構造指標にどのように影響するかを、初めて体系的に分析する。
ノード分類精度と局所的および大域的グラフ特性の変化の相関関係を考察した。
提案手法は,グローバル接続の柔軟性を確保しつつ,局所的な構造を保ちながら再配線を成功させる傾向にある。
論文 参考訳（メタデータ） (2025-10-23T13:38:41Z) - Asynchronous Message Passing for Addressing Oversquashing in Graph Neural Networks [21.49824162847618]
グラフニューラルネットワーク(GNN)は、タスクが長距離インタラクションを必要とする場合に発生するオーバーカッシングに悩まされる。
本稿では,従来の同期メッセージパッシングGNNとは異なり,ノード機能を非同期に更新する効率的なモデルに依存しないフレームワークを提案する。
本フレームワークは6つの標準グラフデータセットと2つの長距離データセットに適用してグラフ分類を行う。
論文 参考訳（メタデータ） (2025-09-08T15:03:05Z) - Limits of message passing for node classification: How class-bottlenecks restrict signal-to-noise ratio [0.6117371161379209]
メッセージパッシングニューラルネットワーク(MPNN)はノード分類の強力なモデルであるが、グラフのヘテロフィリーおよび構造的ボトルネックの下でのパフォーマンス制限に悩まされている。
本稿では,MPNN表現の信号対雑音比(SNR)を用いて,ヘテロフィリとボトルネックの関係を明らかにする。
高次ホモフィリーを最大化するための最適グラフ構造は、単クラスおよび二クラス二部体の解離結合であることを示す。
これにより、全てのホモフィリーにおけるほぼ完璧な分類精度を達成するグラフアンサンブルに基づく再配線アルゴリズムBRIDGEが得られる。
論文 参考訳（メタデータ） (2025-08-25T09:25:14Z) - A Signed Graph Approach to Understanding and Mitigating Oversmoothing in GNNs [54.62268052283014]
署名されたグラフの枠組みに基づく統一的な理論的視点を示す。
既存の戦略の多くは、メッセージパッシングを変えて過度な操作に抵抗する負のエッジを暗黙的に導入している。
本稿では,ラベルや特徴の類似性に基づいて署名されたエッジを割り当てるプラグイン・アンド・プレイ方式であるStructure Balanced Propagation (SBP)を提案する。
論文 参考訳（メタデータ） (2025-02-17T03:25:36Z) - Point Cloud Denoising With Fine-Granularity Dynamic Graph Convolutional Networks [58.050130177241186]
ノイズの摂動は、しばしば3次元の点雲を破損させ、表面の再構成、レンダリング、さらなる処理といった下流のタスクを妨げる。
本稿では,GDGCNと呼ばれる粒度動的グラフ畳み込みネットワークについて紹介する。
論文 参考訳（メタデータ） (2024-11-21T14:19:32Z) - NetDiff: Deep Graph Denoising Diffusion for Ad Hoc Network Topology Generation [1.6768151308423371]
本稿では,無線アドホックネットワークリンクトポロジを生成する拡散確率的アーキテクチャを記述したグラフであるNetDiffを紹介する。
この結果から,生成したリンクは現実的であり,データセットグラフに類似した構造的特性を有しており,操作するには小さな修正と検証ステップのみが必要であることがわかった。
論文 参考訳（メタデータ） (2024-10-09T15:39:49Z) - Adversarial Graph Disentanglement [47.27978741175575]
実世界のグラフは複雑な位相構造を持ち、しばしば異なる潜在因子の相互作用によって形成される。
グラフ表現学習のためのアンダーラインtextbfAdversarial underlinetextbfDisentangled underlinetextbfGraph underlinetextbfConvolutional underlinetextbfNetwork (ADGCN)を提案する。
論文 参考訳（メタデータ） (2021-03-12T14:11:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。