論文の概要: Scaffold: Support Graph Theory Based Sparsification for Graph Neural Networks

• arxiv url: http://arxiv.org/abs/2609.31466v1
• Date: Fri, 25 Sep 2026 16:17:09 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-28 18:27:51.485805
• Title: Scaffold: Support Graph Theory Based Sparsification for Graph Neural Networks
• Title（参考訳）: Scaffold: グラフ理論に基づくグラフニューラルネットワークのスパーシフィケーションをサポート
• Abstract要約: グラフニューラルネットワークは、グラフエッジ上のメッセージパッシングに依存している。 エッジを無差別に除去することは、重要な通信構造を歪曲し、予測性能を低下させる。 トポロジに基づく教師なしグラフスパース化フレームワークであるScaffoldを紹介する。
• 参考スコア（独自算出の注目度）: 33.313101633897894
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph neural networks (GNNs) rely on message passing over graph edges, making their computational and memory costs strongly dependent on graph density. Graph sparsification offers a natural way to reduce these costs, but removing edges indiscriminately can distort important communication structure and degrade predictive performance. We introduce Scaffold, a topology-based, unsupervised graph sparsification framework derived from support graph theory preconditioners. Scaffold explicitly controls two complementary structural quantities: dilation, which measures the length of rerouting paths induced by removed edges, and congestion, which measures how strongly these rerouted paths concentrate on the retained support. By jointly controlling dilation and congestion, Scaffold preserves short communication paths while avoiding structural bottlenecks. To our knowledge, Scaffold is the first scalable GNN sparsification framework to use a joint supporting-path dilation-congestion criterion. Across 19 homophilic and heterophilic benchmarks spanning small to large graphs, Scaffold achieves the best aggregate rank among the evaluated sparsification and related methods. Using only 10%-50% of the original edges per sparse support, Scaffold recovers or closely approaches full-graph GNN performance while using less than half the memory of full-graph training and reducing end-to-end training time, including sparsification overhead. We provide an open-source software package at https://github.com/siddhartha047/Scaffold.
• Abstract（参考訳）: グラフニューラルネットワーク(GNN)は、グラフエッジ上のメッセージパッシングに依存しており、その計算とメモリコストはグラフ密度に強く依存している。 グラフスペーシフィケーションはこれらのコストを削減する自然な方法であるが、エッジを非差別に除去することで重要な通信構造を歪め、予測性能を低下させることができる。 グラフ理論プレコンディショナーから派生したトポロジに基づく教師なしグラフスペーシフィケーションフレームワークであるScaffoldを紹介する。 拡張(Dilation)は、除去された端によって引き起こされる経路の長さを計測し、混雑(cgestion)は、これらの経路が保持された支持にどれだけ強く集中するかを測定する。 拡張と混雑を共同で制御することで、スキャフォールドは構造的ボトルネックを避けながら短い通信経路を保ちます。 我々の知る限り、Scaffoldは、共同でサポートパス拡張-混雑基準を使用する最初のスケーラブルなGNNスペーサー化フレームワークである。 小さいグラフから大きなグラフにまたがる19のホモ親和性およびヘテロ親和性ベンチマークにおいて、スキャフォールドは評価されたスパーシフィケーションと関連する手法の中で最高の集計ランクを達成している。 スパースサポート毎のオリジナルのエッジの10%から50%しか使用せず、フルグラフトレーニングのメモリの半分未満を使用しながら、フルグラフGNNのパフォーマンスを回復または緊密に改善し、スパシフィケーションオーバーヘッドを含むエンドツーエンドのトレーニング時間を短縮する。 私たちはhttps://github.com/siddhartha047/Scaffold.comでオープンソースソフトウェアパッケージを提供しています。

関連論文リスト

• Topology-Aware Gaussian Graph Repair for Robust Graph Neural Networks [1.652121135969053]
  Topology-Aware Gaussian repair (TAGR)は、グラフニューラルネットワークにおける堅牢なメッセージパッシングのための単純なグラフ修復フレームワークである。 TAGRは、ノイズエッジと欠損エッジの両方の設定下で、グラフニューラルネットワークの堅牢性を改善する。
  論文  参考訳（メタデータ） (2026-06-02T10:39:24Z)
• Rethinking Efficient Graph Coarsening via a Non-Selfishness Principle [56.92868481531399]
  粗大化における近隣住民の集団干渉を優先する非利己的原則を提案する。 局所等方性仮定に基づいて、O(dot d)干渉評価をO(d)に還元する高速なNOPE*を導出する。 粗いグラフの学習は、元のグラフに匹敵する性能を示し、LLMベースのグラフ推論よりも優れた性能を示すことができる。
  論文  参考訳（メタデータ） (2026-05-13T05:24:35Z)
• Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification [81.06278257153835]
  本稿では,構造的ボトルネック低減とグラフ特性保存のバランスをとるグラフ再構成手法を提案する。 本手法は、疎性を維持しながら接続性を高めたグラフを生成し、元のグラフスペクトルを大半保存する。
  論文  参考訳（メタデータ） (2025-06-19T08:01:00Z)
• Two Heads Are Better Than One: Boosting Graph Sparse Training via Semantic and Topological Awareness [80.87683145376305]
  グラフニューラルネットワーク(GNN)は、様々なグラフ学習タスクに優れるが、大規模グラフに適用した場合、計算上の課題に直面している。 データレベルで空間を動的に操作するグラフスパーストレーニング(GST)を提案する。 GSTは、最大位相整合性と性能劣化のないスパースグラフを生成する。
  論文  参考訳（メタデータ） (2024-02-02T09:10:35Z)
• Deep Manifold Graph Auto-Encoder for Attributed Graph Embedding [51.75091298017941]
  本稿では,属性付きグラフデータに対する新しいDeep Manifold (Variational) Graph Auto-Encoder (DMVGAE/DMGAE)を提案する。 提案手法は,最先端のベースラインアルゴリズムを,一般的なデータセット間でのダウンストリームタスクの差を大きく越える。
  論文  参考訳（メタデータ） (2024-01-12T17:57:07Z)
• EGRC-Net: Embedding-induced Graph Refinement Clustering Network [66.44293190793294]
  埋め込みによるグラフリファインメントクラスタリングネットワーク (EGRC-Net) という新しいグラフクラスタリングネットワークを提案する。 EGRC-Netは学習した埋め込みを利用して初期グラフを適応的に洗練し、クラスタリング性能を向上させる。 提案手法はいくつかの最先端手法より一貫して優れている。
  論文  参考訳（メタデータ） (2022-11-19T09:08:43Z)
• FoSR: First-order spectral rewiring for addressing oversquashing in GNNs [0.0]
  グラフニューラルネットワーク(GNN)は、グラフのエッジに沿ってメッセージを渡すことによって、グラフデータの構造を活用することができる。 本稿では,グラフにエッジを体系的に付加することで過疎化を防止する計算効率のよいアルゴリズムを提案する。 提案アルゴリズムは,いくつかのグラフ分類タスクにおいて,既存のグラフリウィリング手法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2022-10-21T07:58:03Z)
• DiffWire: Inductive Graph Rewiring via the Lov\'asz Bound [1.0323063834827415]
  グラフニューラルネットワーク(GNN)は、グラフ関連タスクに対処するための競合的な結果を達成することが示されている。 MPNNは、過密、過密、過密に悩まされていると報告されている。 DiffWireは、MPNNでグラフを書き換える新しいフレームワークであり、原則的で、完全に微分可能で、パラメータフリーである。
  論文  参考訳（メタデータ） (2022-06-15T08:22:07Z)
• SoftEdge: Regularizing Graph Classification with Random Soft Edges [18.165965620873745]
  グラフデータ拡張はグラフニューラルネットワーク(GNN)の正規化において重要な役割を果たす 単純なエッジとノード操作は、同じ構造を持つグラフや、GNNをメッセージパッシングするための区別できない構造を生成することができる。 我々は,任意のグラフのエッジの一部にランダムな重みを割り当てて,そのグラフ上の動的近傍を構築するSoftEdgeを提案する。
  論文  参考訳（メタデータ） (2022-04-21T20:12:36Z)
• GNNAutoScale: Scalable and Expressive Graph Neural Networks via Historical Embeddings [51.82434518719011]
  GNNAutoScale(GAS)は、任意のメッセージパスGNNを大規模グラフにスケールするためのフレームワークである。 ガスは、前回のトレーニングの繰り返しから過去の埋め込みを利用して計算グラフのサブツリー全体を掘り起こします。 ガスは大規模グラフ上で最先端のパフォーマンスに達する。
  論文  参考訳（メタデータ） (2021-06-10T09:26:56Z)

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

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