論文の概要: Pair-Centric Graph Rewiring for Over-Squashing via Optimal Transport-Guided Communication Alignment

• arxiv url: http://arxiv.org/abs/2608.10619v1
• Date: Tue, 11 Aug 2026 08:05:32 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-12 19:14:45.954995
• Title: Pair-Centric Graph Rewiring for Over-Squashing via Optimal Transport-Guided Communication Alignment
• Title（参考訳）: 最適搬送誘導通信アライメントによるオーバーカッシングのためのペア中心グラフリウィリング
• Authors: Yan Wang, Chuan-Xian Ren,
• Abstract要約: グラフのリワイアリングはオーバースカッシングに対する構造的応答を提供する。 変更予算が限られているため、重要な疑問は、どのペアワイズ通信が構造的サポートを必要とするかである。 本稿では,ペア中心グラフ再構成フレームワークであるPairAlignを提案する。
• 参考スコア（独自算出の注目度）: 24.215683640150413
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Message-passing neural networks (MPNNs) often struggle when task-relevant information is distributed across distant regions of a graph, since local propagation must compress remote signals through limited structural interfaces. Graph rewiring provides a structural response to over-squashing. Most existing methods rely on edge-level bottleneck scores or graph-level connectivity surrogates. With a limited rewiring budget, the key question is which pairwise communications most need structural support. This paper proposes PairAlign, a pair-centric graph rewiring framework that makes this question explicit through demand-support shortage. Specifically, PairAlign combines original-graph structural demand with current-graph finite-hop propagation support; their ratio highlights interactions whose communication demand is poorly supported by topology, and our theory shows that this score provides a computable proxy for the corresponding Jacobian-based shortage with a pair-level interpretation of over-squashing. Our theory reveals a two-sided effect of edge insertion: a new edge can create useful walks and simultaneously dilute existing normalized transition mass. Guided by this observation, PairAlign optimizes shortage to favor edge additions that alleviate over-squashing. Beyond selecting useful additions, PairAlign further introduces an Optimal Transport-guided rewiring mechanism to coordinate the finite edge budget for pair-level structural compatibility and shortage-target coverage. It formulates communication alignment between the candidate edge budget and the shortage targets, and the theory shows that this allocation covers shortage targets more broadly and effectively than a greedy-local assignment. Experiments on standard graph benchmarks show PairAlign's improvement across message-passing backbones, validating pair-level repair as an effective route for alleviating over-squashing.
• Abstract（参考訳）: メッセージパッシングニューラルネットワーク(MPNN)は、タスク関連情報がグラフの遠くの領域に分散する際にしばしば苦労する。 グラフのリワイアリングはオーバースカッシングに対する構造的応答を提供する。 既存の手法のほとんどはエッジレベルのボトルネックスコアやグラフレベルの接続サロゲートに依存している。 変更予算が限られているため、重要な疑問は、どのペアワイズ通信が構造的サポートを必要とするかである。 本稿では、需要支援不足を通じてこの問題を明確化するペア中心グラフリウィリングフレームワークであるPairAlignを提案する。 具体的には、PairAlignは、元のグラフ構造要求と、現在のグラフ有限ホップ伝播支援を組み合わせることで、通信要求がトポロジによって不十分な相互作用を強調し、このスコアは、ペアレベルのオーバーカッシングの解釈で、対応するヤコビアンベースの不足に対する計算可能なプロキシを提供することを示す。 我々の理論では、エッジ挿入の両面効果が明らかであり、新しいエッジは有用なウォーキングと既存の正規化遷移質量を同時に希釈することができる。 この観察によって導かれたPairAlignは、過剰な監視を緩和するエッジの追加を優先するために不足を最適化する。 PairAlignはさらに、ペアレベルの構造互換性と不足ターゲットカバレッジのために、有限エッジ予算を調整するために、最適なトランスポート誘導スイッチング機構を導入している。 候補のエッジ予算と不足目標との通信アライメントを定式化し、このアロケーションが不足目標をより広く効果的にカバーしていることを示す。 標準的なグラフベンチマークの実験では、メッセージパスバックボーン間でのPairAlignの改善が示され、ペアレベルの修復がオーバースカッシングを緩和する有効な方法として検証されている。

関連論文リスト

• Effective Resistance Rewiring: A Simple Topological Correction for Over-Squashing [0.03636228980200798]
  本稿では,実効抵抗をグローバル信号として利用し,構造的ボトルネックを検出する単純なトポロジ補正手法であるEffective resistance Rewiring(ERR)を紹介する。 ERRは、最大の抵抗を持つノードペア間のエッジを反復的に追加し、最小抵抗のエッジを除去し、弱い通信経路を強化する。 層間におけるノード埋め込みのコサイン類似性を追跡することにより、初期ノード特徴と学習された表現の関係がメッセージパッシング中にどのように進化するかを検討する。
  論文  参考訳（メタデータ） (2026-03-12T13:55:48Z)
• LineGraph2Road: Structural Graph Reasoning on Line Graphs for Road Network Extraction [0.0]
  LineGraph2Roadは、構築されたグローバルだがスパースなユークリッドグラフにおいて、エッジ上のバイナリ分類として定式化することで接続性予測を改善するフレームワークである。 都市スケール,SpaceNet,Global-scaleの3つのベンチマークで評価し,TOPO-F1とAPLSの2つの主要な指標で最先端の結果が得られたことを示す。
  論文  参考訳（メタデータ） (2026-02-26T18:02:44Z)
• HELP: HyperNode Expansion and Logical Path-Guided Evidence Localization for Accurate and Efficient GraphRAG [53.30561659838455]
  大きな言語モデル(LLM)は、しばしば固有の知識境界と幻覚に苦しむ。 Retrieval-Augmented Generation (RAG) は、マルチホップ推論に不可欠な構造的相互依存性をしばしば見落としている。 ヘルプは、複数の単純でマルチホップなQAベンチマークで競合性能を達成し、グラフベースのRAGベースラインよりも28.8$times$のスピードアップを実現している。
  論文  参考訳（メタデータ） (2026-02-24T14:05:29Z)
• A New Decomposition Paradigm for Graph-structured Nonlinear Programs via Message Passing [11.765197673198983]
  決定変数がグラフやハイパーグラフに従って局所的に相互作用する有限サム非線形プログラムについて検討する。 本稿では,ミニサムメッセージパッシングとJacodiブロック更新を結合したグラフ対応分散フレームワークMP-Jacobiを提案する。
  論文  参考訳（メタデータ） (2025-12-31T07:05:37Z)
• Transfer Learning on Edge Connecting Probability Estimation under Graphon Model [7.805468525082696]
  本稿では,グラフ間の構造パターンの整合と伝達を行うため,近傍の平滑化とGromov-Wassersteinの最適輸送を統合した伝達学習フレームワークを提案する。 GTRANSには適応的脱バイアス機構があり、残留な平滑化を通じて標的特異的な偏差を識別し修正する。 これらの改善は、グラフ分類タスクやリンク予測タスクなど、下流アプリケーションの性能向上に直接寄与する。
  論文  参考訳（メタデータ） (2025-10-07T02:37:12Z)
• T-GAE: Transferable Graph Autoencoder for Network Alignment [79.89704126746204]
  T-GAEはグラフオートエンコーダフレームワークで、GNNの転送性と安定性を活用して、再トレーニングなしに効率的なネットワークアライメントを実現する。 実験の結果、T-GAEは最先端の最適化手法と最高のGNN手法を最大38.7%、50.8%で上回っていることがわかった。
  論文  参考訳（メタデータ） (2023-10-05T02:58:29Z)
• Self-Supervised Relation Alignment for Scene Graph Generation [44.3983804479146]
  シーングラフ生成性能を改善するために,自己教師付きリレーショナルアライメントの正規化を導入する。 提案されたアライメントは一般的なもので、既存のシーングラフ生成フレームワークと組み合わせることができる。 本稿では,この自己教師付きリレーショナルアライメントと2つのシーングラフ生成アーキテクチャの有効性について述べる。
  論文  参考訳（メタデータ） (2023-02-02T20:34:13Z)
• Graph Reasoning Transformer for Image Parsing [67.76633142645284]
  本稿では,画像解析のためのグラフ推論変換器(GReaT)を提案する。 従来の変圧器と比較して、GReaTは高い相互作用効率とより目的のある相互作用パターンを有する。 その結果、GReaTは、最先端のトランスフォーマーベースラインにわずかに計算オーバーヘッドを伴って、一貫した性能向上を実現していることがわかった。
  論文  参考訳（メタデータ） (2022-09-20T08:21:37Z)

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

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