論文の概要: Schreier-Coset Graph Rewiring

• arxiv url: http://arxiv.org/abs/2607.27479v1
• Date: Wed, 29 Jul 2026 21:42:02 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-31 21:37:00.32543
• Title: Schreier-Coset Graph Rewiring
• Title（参考訳）: Schreier-Cosetグラフのリライト
• Abstract要約: 特殊線型群から派生したシュライアー・コセットグラフを用いて入力グラフを拡大する群理論的再配線法を提案する。 提案手法は,スペクトルギャップと有界有効抵抗を示すグラフを理論的に保証し,長距離通信のための低抵抗バイパスを実現する。
• 参考スコア（独自算出の注目度）: 1.6566053195631467
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The information flow in the graph neural networks (GNNs) is fundamentally constrained by over-squashing, where structural bottlenecks impede long range information propagation. Graph-rewiring methods, which modify graph topology, have been extensively used to alleviate this. However, existing approaches often introduce prohibitive structural and computational bottlenecks, fail to preserve the critical properties of original graphs, and increase the edge counts massively. We introduce a novel method Schreier-Coset Graph Rewiring , a group-theoretic rewiring method that augments the input graph with a Schreier-Coset graph derived from a special linear group. Our method provides theoretical guarantees, a graph that exhibits spectral gap and a bounded effective resistance, creating a low-resistance bypass for long-range communication. Empirical evaluations demonstrate that SCGR reduces effective resistance by 5-40% across various learning tasks, effectively mitigating connectivity bottlenecks while maintaining competitive accuracy.
• Abstract（参考訳）: グラフニューラルネットワーク(GNN)における情報フローは、構造的ボトルネックが長距離情報伝達を妨げるオーバースカッシングによって根本的に制限される。 グラフトポロジを変更するグラフ置換法は、これを緩和するために広く利用されている。 しかし、既存のアプローチは、しばしば禁止的な構造的および計算的ボトルネックを導入し、元のグラフの臨界特性を保たず、エッジ数を大幅に増やす。 特殊線型群から派生したシュライアー・コセットグラフを用いて入力グラフを拡大する群理論的再配線法であるSchreier-Coset Graph Rewiringを導入する。 提案手法は,スペクトルギャップと有界有効抵抗を示すグラフを理論的に保証し,長距離通信のための低抵抗バイパスを実現する。 経験的評価では、SCGRは様々な学習タスクにおいて有効抵抗を5～40%削減し、競争精度を維持しながら接続ボトルネックを効果的に軽減する。

関連論文リスト

• Topology-Aware Gaussian Graph Repair for Robust Graph Neural Networks [1.652121135969053]
  Topology-Aware Gaussian repair (TAGR)は、グラフニューラルネットワークにおける堅牢なメッセージパッシングのための単純なグラフ修復フレームワークである。 TAGRは、ノイズエッジと欠損エッジの両方の設定下で、グラフニューラルネットワークの堅牢性を改善する。
  論文  参考訳（メタデータ） (2026-06-02T10:39:24Z)
• Improved large-scale graph learning through ridge spectral sparsification [65.84577791298442]
  分散ストリーミング環境におけるラプラシアンLの学習問題を考察する。 この設定では、L の分散表現を維持しながら、素早く、あるいはほぼ学習することは困難である。 本稿では, 有効抵抗の小さなサブセットを維持することにより, ラプラシアンを効率的に分散させる新しいアルゴリズムGSQUEAKを提案する。
  論文  参考訳（メタデータ） (2026-04-22T00:49:31Z)
• Effective Resistance Rewiring: A Simple Topological Correction for Over-Squashing [0.03636228980200798]
  本稿では,実効抵抗をグローバル信号として利用し,構造的ボトルネックを検出する単純なトポロジ補正手法であるEffective resistance Rewiring(ERR)を紹介する。 ERRは、最大の抵抗を持つノードペア間のエッジを反復的に追加し、最小抵抗のエッジを除去し、弱い通信経路を強化する。 層間におけるノード埋め込みのコサイン類似性を追跡することにより、初期ノード特徴と学習された表現の関係がメッセージパッシング中にどのように進化するかを検討する。
  論文  参考訳（メタデータ） (2026-03-12T13:55:48Z)
• Structural Invariance Matters: Rethinking Graph Rewiring through Graph Metrics [52.077620040518646]
  我々は、リワイアが様々なグラフ構造指標にどのように影響するかを、初めて体系的に分析する。 ノード分類精度と局所的および大域的グラフ特性の変化の相関関係を考察した。 提案手法は,グローバル接続の柔軟性を確保しつつ,局所的な構造を保ちながら再配線を成功させる傾向にある。
  論文  参考訳（メタデータ） (2025-10-23T13:38:41Z)
• GraphTorque: Torque-Driven Rewiring Graph Neural Network [24.311681447733346]
  ヘテロ親和性グラフとホモ親和性グラフの表現学習を改善するために,トルク駆動型階層的再配線戦略を提案する。 我々は,各層の階層的受容場を,高トルクエッジを任意に刈り上げ,低トルクリンクを追加することで再構成する。 提案手法は, ヘテロフィルグラフとホモフィルグラフの両面において, 最先端の切り換え手法を超越した手法である。
  論文  参考訳（メタデータ） (2025-07-29T01:14:27Z)
• Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification [81.06278257153835]
  本稿では,構造的ボトルネック低減とグラフ特性保存のバランスをとるグラフ再構成手法を提案する。 本手法は、疎性を維持しながら接続性を高めたグラフを生成し、元のグラフスペクトルを大半保存する。
  論文  参考訳（メタデータ） (2025-06-19T08:01:00Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。 効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。 グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2023-06-14T09:21:15Z)
• Learning Graph Structure from Convolutional Mixtures [119.45320143101381]
  本稿では、観測されたグラフと潜伏グラフのグラフ畳み込み関係を提案し、グラフ学習タスクをネットワーク逆(デコンボリューション)問題として定式化する。 固有分解に基づくスペクトル法の代わりに、近似勾配反復をアンロール・トランケートして、グラフデコンボリューションネットワーク(GDN)と呼ばれるパラメータ化ニューラルネットワークアーキテクチャに到達させる。 GDNは、教師付き方式でグラフの分布を学習し、損失関数を適応させることでリンク予測やエッジウェイト回帰タスクを実行し、本質的に帰納的である。
  論文  参考訳（メタデータ） (2022-05-19T14:08:15Z)
• A Graph Data Augmentation Strategy with Entropy Preserving [11.886325179121226]
  本稿では,グラフ間の特徴情報を評価するための定量的指標として,新しいグラフエントロピー定義を提案する。 グラフエントロピーの保存を考慮し、摂動機構を用いてトレーニングデータを生成する効果的な方法を提案する。 提案手法はトレーニング過程におけるGCNの堅牢性と一般化能力を大幅に向上させる。
  論文  参考訳（メタデータ） (2021-07-13T12:58:32Z)
• Multilayer Graph Clustering with Optimized Node Embedding [70.1053472751897]
  多層グラフクラスタリングは、グラフノードをカテゴリまたはコミュニティに分割することを目指しています。 与えられた多層グラフの層をクラスタリングに親しみやすい埋め込みを提案する。 実験の結果,本手法は著しい改善をもたらすことがわかった。
  論文  参考訳（メタデータ） (2021-03-30T17:36:40Z)
• Multilayer Clustered Graph Learning [66.94201299553336]
  我々は、観測された層を代表グラフに適切に集約するために、データ忠実度用語として対照的な損失を用いる。 実験により,本手法がクラスタクラスタw.r.tに繋がることが示された。 クラスタリング問題を解くためのクラスタリングアルゴリズムを学習する。
  論文  参考訳（メタデータ） (2020-10-29T09:58:02Z)

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

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