論文の概要: Scalable Topology-Preserving Graph Coarsening with Graph Collapse

• arxiv url: http://arxiv.org/abs/2601.22943v1
• Date: Fri, 30 Jan 2026 13:02:26 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-02 18:28:15.452043
• Title: Scalable Topology-Preserving Graph Coarsening with Graph Collapse
• Title（参考訳）: グラフ崩壊によるスケーラブルなトポロジ保存グラフ粗大化
• Authors: Xiang Wu, Rong-Hua Li, Xunkai Li, Kangfei Zhao, Hongchao Qin, Guoren Wang,
• Abstract要約: トポロジ的特徴の保存は,粗いグラフ上でトレーニングされたグラフニューラルネットワーク(GNN)の予測性能を維持するのに役立つが,指数時間的複雑性に悩まされていることを示す。 本稿では,代数的トポロジから拡張されたグラフ強崩壊とグラフエッジ崩壊の概念を導入して,スケーラブルなトポロジ保存グラフ粗大化(STPGC)を提案する。 STPGCは、これらの2つの概念に基づいてGStrongCollapse、GEdgeCollapse、NeighborhoodConingという3つの新しいアルゴリズムで構成されており、トポロジ的特徴を厳格に保存しながら空間的エッジを排除している。
• 参考スコア（独自算出の注目度）: 40.30540248213416
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph coarsening reduces the size of a graph while preserving certain properties. Most existing methods preserve either spectral or spatial characteristics. Recent research has shown that preserving topological features helps maintain the predictive performance of graph neural networks (GNNs) trained on the coarsened graph but suffers from exponential time complexity. To address these problems, we propose Scalable Topology-Preserving Graph Coarsening (STPGC) by introducing the concepts of graph strong collapse and graph edge collapse extended from algebraic topology. STPGC comprises three new algorithms, GStrongCollapse, GEdgeCollapse, and NeighborhoodConing based on these two concepts, which eliminate dominated nodes and edges while rigorously preserving topological features. We further prove that STPGC preserves the GNN receptive field and develop approximate algorithms to accelerate GNN training. Experiments on node classification with GNNs demonstrate the efficiency and effectiveness of STPGC.
• Abstract（参考訳）: グラフ粗化は、特定のプロパティを保持しながらグラフのサイズを減らす。 既存の手法のほとんどは、スペクトル特性または空間特性を保存している。 近年の研究では、トポロジ的特徴を保存することで、粗いグラフでトレーニングされたグラフニューラルネットワーク(GNN)の予測性能を維持することができるが、指数時間的複雑性に悩まされていることが示されている。 これらの問題に対処するために,代数的トポロジから拡張されたグラフ強崩壊とグラフエッジ崩壊の概念を導入して,スケーラブルなトポロジ保存グラフ粗大化(STPGC)を提案する。 STPGCは、これらの2つの概念に基づいてGStrongCollapse、GEdgeCollapse、NeighborhoodConingという3つの新しいアルゴリズムで構成されている。 さらに,STPGCはGNN受容野を保ち,GNN訓練を加速する近似アルゴリズムを開発することを証明した。 GNNを用いたノード分類実験は、STPGCの有効性と有効性を示す。

関連論文リスト

• Line Graph Vietoris-Rips Persistence Diagram for Topological Graph Representation Learning [3.6881508872690825]
  トポロジカルエッジ図(TED)と呼ばれる新しいエッジフィルタを用いた永続化図を導入する。 TEDは、ノードの埋め込み情報を保存し、追加の位相情報を含むことが数学的に証明されている。 本稿では,グラフを行グラフに変換することによってエッジ情報を抽出するLine Graph Vietoris-Rips (LGVR) Persistence Diagramを提案する。
  論文  参考訳（メタデータ） (2024-12-23T10:46:44Z)
• Spectral Greedy Coresets for Graph Neural Networks [61.24300262316091]
  ノード分類タスクにおける大規模グラフの利用は、グラフニューラルネットワーク(GNN)の現実的な応用を妨げる 本稿では,GNNのグラフコアセットについて検討し,スペクトル埋め込みに基づくエゴグラフの選択により相互依存の問題を回避する。 我々のスペクトルグレディグラフコアセット(SGGC)は、数百万のノードを持つグラフにスケールし、モデル事前学習の必要性を排除し、低ホモフィリーグラフに適用する。
  論文  参考訳（メタデータ） (2024-05-27T17:52:12Z)
• 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)
• Robust Graph Neural Network based on Graph Denoising [10.564653734218755]
  グラフニューラルネットワーク(GNN)は、非ユークリッドデータセットを扱う学習問題に対して、悪名高い代替手段として登場した。 本研究は,観測トポロジにおける摂動の存在を明示的に考慮した,GNNの堅牢な実装を提案する。
  論文  参考訳（メタデータ） (2023-12-11T17:43:57Z)
• DEGREE: Decomposition Based Explanation For Graph Neural Networks [55.38873296761104]
  我々は,GNN予測に対する忠実な説明を提供するためにDGREEを提案する。 GNNの情報生成と集約機構を分解することにより、DECREEは入力グラフの特定のコンポーネントのコントリビューションを最終的な予測に追跡することができる。 また,従来の手法で見過ごされるグラフノード間の複雑な相互作用を明らかにするために,サブグラフレベルの解釈アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2023-05-22T10:29:52Z)
• Comprehensive Graph Gradual Pruning for Sparse Training in Graph Neural Networks [52.566735716983956]
  本稿では,CGPと呼ばれるグラフの段階的プルーニングフレームワークを動的にGNNに提案する。 LTHに基づく手法とは異なり、提案手法では再学習を必要とせず、計算コストを大幅に削減する。 提案手法は,既存の手法の精度を一致させたり,あるいは超えたりしながら,トレーニングと推論の効率を大幅に向上させる。
  論文  参考訳（メタデータ） (2022-07-18T14:23:31Z)
• Topological Relational Learning on Graphs [2.4692806302088868]
  グラフニューラルネットワーク(GNN)は、グラフ分類と表現学習のための強力なツールとして登場した。 本稿では,GNNに高階グラフ情報を統合可能な新しいトポロジカルリレーショナル推論(TRI)を提案する。 新しいTRI-GNNは、6つの7つのグラフで14の最先端のベースラインを上回り、摂動に対して高い堅牢性を示すことを示す。
  論文  参考訳（メタデータ） (2021-10-29T04:03:27Z)
• Geom-GCN: Geometric Graph Convolutional Networks [15.783571061254847]
  本稿では,この2つの弱点を克服するために,グラフニューラルネットワークのための新しい幾何集約手法を提案する。 提案したアグリゲーションスキームは置換不変であり、ノード埋め込み、構造近傍、二レベルアグリゲーションという3つのモジュールから構成される。 また,このスキームをGeom-GCNと呼ばれるグラフ畳み込みネットワークに実装し,グラフ上でトランスダクティブ学習を行う。
  論文  参考訳（メタデータ） (2020-02-13T00:03:09Z)
• Gated Graph Recurrent Neural Networks [176.3960927323358]
  グラフ処理の一般的な学習フレームワークとしてグラフリカレントニューラルネットワーク(GRNN)を導入する。 勾配の消失問題に対処するため,時間,ノード,エッジゲートの3つの異なるゲーティング機構でGRNNを前進させた。 数値的な結果は、GRNNがGNNやRNNよりも優れており、グラフプロセスの時間構造とグラフ構造の両方を考慮することが重要であることを示している。
  論文  参考訳（メタデータ） (2020-02-03T22:35:14Z)

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

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