論文の概要: Ramanujan Graph Rewiring with Non Negative Resistance Curvature

• arxiv url: http://arxiv.org/abs/2606.21333v1
• Date: Fri, 19 Jun 2026 11:26:42 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-25 14:20:11.895746
• Title: Ramanujan Graph Rewiring with Non Negative Resistance Curvature
• Title（参考訳）: 非負の抵抗曲率を持つラマヌジャングラフ再構成
• Authors: Hugo Attali, Rachid El Jouhri,
• Abstract要約: グラフニューラルネットワーク(GNN)は、エッジ間で情報を反復的に伝播し集約することにより、グラフ構造化データを学ぶための強力なパラダイムとして登場した。 従来のメッセージパッシング方式は、しばしばオーバースカッシングに悩まされ、指数関数的に大きな近傍は固定次元の埋め込みに圧縮される。
• 参考スコア（独自算出の注目度）: 1.4323566945483497
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph Neural Networks (GNNs) have emerged as a powerful paradigm for learning on graph-structured data by iteratively propagating and aggregating information across edges. However, conventional message passing schemes often suffer from over-squashing, whereby exponentially large neighborhoods are compressed into fixed-dimensional embeddings, impeding effective long-range dependency learning. In this work, we introduce Ramanujan Propagation, a graph rewiring strategy that leverages Ramanujan graphs to alleviate topological bottlenecks in GNNs. We first establish that suitably chosen Ramanujan graphs guarantee non-negative resistance curvature, which mitigates over-squashing and facilitates efficient information flow. We then propose an algorithmic framework to construct a Ramanujan rewired graph that preserves the local connectivity of the original graph. Our experiments demonstrate that our method outperforms nine state-of-the-art rewiring techniques. These results establish Ramanujan graphs as a rigorous structural prior for scalable, topology-aware message passing in GNNs.
• Abstract（参考訳）: グラフニューラルネットワーク(GNN)は、エッジ間で情報を反復的に伝播し集約することにより、グラフ構造化データを学ぶための強力なパラダイムとして登場した。 しかし、従来のメッセージパッシング方式は、しばしばオーバースカッシングに悩まされるため、指数関数的に大きな近傍を固定次元の埋め込みに圧縮することで、効果的な長距離依存性学習を阻害する。 本稿では,GNNにおけるトポロジ的ボトルネックを軽減するために,ラマヌジャングラフを利用するグラフ再構成戦略であるラマヌジャン・プロパゲーションを紹介する。 まず、好適に選択されたラマヌジャングラフが非負の抵抗曲率を保証し、過度なスキャッシングを緩和し、効率的な情報フローを促進することを確立する。 次に、元のグラフの局所接続性を保持するラマヌジャン再配線グラフを構築するアルゴリズムフレームワークを提案する。 実験の結果,本手法は9つの最先端リワイア技術より優れていることがわかった。 これらの結果は、GNNにおけるスケーラブルなトポロジ対応メッセージパッシングのための厳密な構造としてラマヌジャングラフを確立する。

関連論文リスト

• Structural Invariance Matters: Rethinking Graph Rewiring through Graph Metrics [52.077620040518646]
  我々は、リワイアが様々なグラフ構造指標にどのように影響するかを、初めて体系的に分析する。 ノード分類精度と局所的および大域的グラフ特性の変化の相関関係を考察した。 提案手法は,グローバル接続の柔軟性を確保しつつ,局所的な構造を保ちながら再配線を成功させる傾向にある。
  論文  参考訳（メタデータ） (2025-10-23T13:38:41Z)
• Dynamic Triangulation-Based Graph Rewiring for Graph Neural Networks [7.527798155040119]
  グラフニューラルネットワーク(GNN)は、グラフ構造化データを学習するための主要なパラダイムとして登場した。 グラフリウィリングの最近の進歩は、より効果的な情報伝達を促進するために、グラフトポロジを変更することによってこれらの制限を緩和することを目的としている。 複数のグラフビューから関連する三角形を選択することを学ぶことで、リッチで非平面三角測量を構築する新しいフレームワークであるTRIGONを紹介する。
  論文  参考訳（メタデータ） (2025-08-26T14:28:31Z)
• Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification [81.06278257153835]
  本稿では,構造的ボトルネック低減とグラフ特性保存のバランスをとるグラフ再構成手法を提案する。 本手法は、疎性を維持しながら接続性を高めたグラフを生成し、元のグラフスペクトルを大半保存する。
  論文  参考訳（メタデータ） (2025-06-19T08:01:00Z)
• A Signed Graph Approach to Understanding and Mitigating Oversmoothing in GNNs [54.62268052283014]
  署名されたグラフの枠組みに基づく統一的な理論的視点を示す。 既存の戦略の多くは、メッセージパッシングを変えて過度な操作に抵抗する負のエッジを暗黙的に導入している。 本稿では,ラベルや特徴の類似性に基づいて署名されたエッジを割り当てるプラグイン・アンド・プレイ方式であるStructure Balanced Propagation (SBP)を提案する。
  論文  参考訳（メタデータ） (2025-02-17T03:25:36Z)
• FoSR: First-order spectral rewiring for addressing oversquashing in GNNs [0.0]
  グラフニューラルネットワーク(GNN)は、グラフのエッジに沿ってメッセージを渡すことによって、グラフデータの構造を活用することができる。 本稿では,グラフにエッジを体系的に付加することで過疎化を防止する計算効率のよいアルゴリズムを提案する。 提案アルゴリズムは,いくつかのグラフ分類タスクにおいて,既存のグラフリウィリング手法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2022-10-21T07:58:03Z)
• Learning Graph Structure from Convolutional Mixtures [119.45320143101381]
  本稿では、観測されたグラフと潜伏グラフのグラフ畳み込み関係を提案し、グラフ学習タスクをネットワーク逆(デコンボリューション)問題として定式化する。 固有分解に基づくスペクトル法の代わりに、近似勾配反復をアンロール・トランケートして、グラフデコンボリューションネットワーク(GDN)と呼ばれるパラメータ化ニューラルネットワークアーキテクチャに到達させる。 GDNは、教師付き方式でグラフの分布を学習し、損失関数を適応させることでリンク予測やエッジウェイト回帰タスクを実行し、本質的に帰納的である。
  論文  参考訳（メタデータ） (2022-05-19T14:08:15Z)
• Towards Unsupervised Deep Graph Structure Learning [67.58720734177325]
  本稿では,学習したグラフトポロジを外部ガイダンスなしでデータ自身で最適化する,教師なしグラフ構造学習パラダイムを提案する。 具体的には、元のデータから"アンカーグラフ"として学習目標を生成し、対照的な損失を用いてアンカーグラフと学習グラフとの一致を最大化する。
  論文  参考訳（メタデータ） (2022-01-17T11:57:29Z)
• Implicit Graph Neural Networks [46.0589136729616]
  Indicit Graph Neural Networks (IGNN) と呼ばれるグラフ学習フレームワークを提案する。 IGNNは一貫して長距離依存を捉え、最先端のGNNモデルより優れている。
  論文  参考訳（メタデータ） (2020-09-14T06:04:55Z)
• Graph Pooling with Node Proximity for Hierarchical Representation Learning [80.62181998314547]
  本稿では,ノード近接を利用したグラフプーリング手法を提案し,そのマルチホップトポロジを用いたグラフデータの階層的表現学習を改善する。 その結果,提案したグラフプーリング戦略は,公開グラフ分類ベンチマークデータセットの集合において,最先端のパフォーマンスを達成できることが示唆された。
  論文  参考訳（メタデータ） (2020-06-19T13:09:44Z)

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

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