論文の概要: EDiS: Edge Disjoint Subgraph Sparsification Framework for Graph Neural Networks
- arxiv url: http://arxiv.org/abs/2610.09059v1
- Date: Tue, 06 Oct 2026 20:09:02 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-08 21:58:22.591354
- Title: EDiS: Edge Disjoint Subgraph Sparsification Framework for Graph Neural Networks
- Title（参考訳）: EDiS: グラフニューラルネットワークのためのエッジ分離部分グラフスパーシフィケーションフレームワーク
- Abstract要約: EDiS (Edge-Disjoint Subgraph Sparsification framework) を導入する。
EDiSは平均ベンチマークスコア(精度/ROC-AUC)が最も高く、ランク付けされたメソッドの中では平均ランクとギャップ・ツー・ベストが低い。
- 参考スコア（独自算出の注目度）: 66.67492452029822
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Sparse GNN training reduces computation, but deciding which edges to keep can be costly. Reusing one sparse graph is cheap, but locks training to a fixed topology, while varying it across epochs can require repeated sampling or recomputation. We introduce EDiS (Edge-Disjoint Subgraph sparsification framework), which separates one-time structural extraction from per-epoch graph composition. EDiS decomposes the graph once into cacheable edge-disjoint subgraphs, then recombines them into graphs with edge-budget constraints across epochs and retention ratios without re-extracting structure. Our default construction uses feature-based scores and successive maximum score covering forests, while the same composition mechanism also supports alternative edge selection rules. We provide a combinatorial analysis of the per-epoch sampler, the composition step that draws a training graph from the cached decomposition. We show that, under the default covering-forest selector, the stored decomposition deterministically preserves high-score cut edges, and we derive a selector-agnostic conditional bound on high-score cut survival in composed training graphs. Across 19 homophilic, heterophilic, and large-scale node classification benchmarks against 17 baselines under the same edge budget, EDiS achieves the highest mean benchmark score (accuracy/ROC-AUC) and the lowest average rank and gap-to-best among ranked methods. Ablations show the clearest benefits of structural decomposition and epoch variation at tight edge budgets.
- Abstract（参考訳）: スパースGNNトレーニングは計算を減らしますが、どのエッジを保持するかを決めるにはコストがかかります。
1つのスパースグラフの再利用は安価だが、トレーニングを固定トポロジにロックする一方で、エポック間で変更するには繰り返しサンプリングや再計算が必要になる。
EDiS (Edge-Disjoint Subgraph Sparsification framework) を導入する。
EDiSは一度グラフをキャッシュ可能なエッジ分離部分グラフに分解し、そのグラフをエポック間のエッジ予算制約と保持率で再抽出することなくグラフに再結合する。
我々のデフォルト構成では、特徴ベースのスコアと連続する最大スコアが森林をカバーし、同じ構成機構が代替エッジ選択ルールもサポートしています。
キャッシュされた分解からトレーニンググラフを描画する合成ステップであるエポック・サンプルの組合せ解析を行う。
既定のカバーフォレストセレクタでは,保存された分解は高スコアカットエッジを決定的に保存し,高スコアカットサバイバルに基づくセレクタ非依存条件を合成学習グラフに導出する。
EDiSは、同じエッジ予算の下で17のベースラインに対して19のホモ親和性、ヘテロ親和性、大規模ノード分類ベンチマークを行い、最も高い平均ベンチマークスコア(精度/ROC-AUC)を達成し、最も低い平均ランクとギャップ・ツー・ベストをランク付けした。
アブレーションは、厳密な予算における構造的分解とエポック変動の最も明確な利点を示す。
関連論文リスト
- Scaffold: Support Graph Theory Based Sparsification for Graph Neural Networks [33.313101633897894]
グラフニューラルネットワークは、グラフエッジ上のメッセージパッシングに依存している。
エッジを無差別に除去することは、重要な通信構造を歪曲し、予測性能を低下させる。
トポロジに基づく教師なしグラフスパース化フレームワークであるScaffoldを紹介する。
論文 参考訳（メタデータ） (2026-09-25T16:17:09Z) - Scaffold-Constrained Subset Dynamic Programming for Exact SSE Clustering [1.76179873429447]
我々は、データ由来の幾何グラフを用いて、正確なサブセットの動的プログラムをプリコンディションする。
残集合の反復最小化は固定(K) またはペナル化 SSE であり、各残集合の連結成分に対する正確な分解である。
本稿では,スキャフォールドプレコンディショニングを用いて,分割マージ提案の効率を向上させる方法について述べる。
論文 参考訳（メタデータ） (2026-09-24T19:16:51Z) - Moment-guided edge sampling [3.685453775072903]
エッジサンプリングは、構造的特性の保存など、グラフレベルの目的を達成するための局所的な決定を行う。
我々はこの課題に,テキストモメント誘導エッジサンプリングフレームワークを用いて対処する。
2つの相補的手法により正確なモーメント変化を計算する。
論文 参考訳（メタデータ） (2026-09-24T19:11:48Z) - Global-Aware Edge Prioritization for Pose Graph Initialization [58.77851776918465]
画像がノードとして機能し、エッジが相対的なポーズをエンコードするStructure-from-Motion(SfM)のコアコンポーネントである。
幾何的検証は高価であるため、SfMパイプラインはポーズグラフを候補エッジのスパース集合に制限する。
本稿では、この制限をエッジ優先順位付けの概念によって解決し、SfMの実用性によって候補エッジをランク付けする。
提案手法は,(1)一貫したエッジ信頼性を予測するために,SfMから指導を受けたGNN,(2)これらのランクで案内されるマルチミニマルスパンニングツリーに基づくポーズグラフ構築,(3)弱い領域を補強する接続性を考慮したスコア変調,の3つの構成要素を有する。
論文 参考訳（メタデータ） (2026-02-25T14:44:53Z) - AEGIS: Authentic Edge Growth In Sparsity for Link Prediction in Edge-Sparse Bipartite Knowledge Graphs [0.8594140167290097]
AEGISは、既存のトレーニングエッジを再サンプリングする、エッジのみの拡張フレームワークである。
テキストリッチGDPグラフでは、セマンティックKNNが最大のAUC改善とBrierスコアの削減を実現している。
論文 参考訳（メタデータ） (2025-09-26T07:51:40Z) - SSHPool: The Separated Subgraph-based Hierarchical Pooling [47.78745802682822]
グラフ分類のための新しい局所グラフプーリング法,すなわち分離部分グラフベース階層プール(SSH)を開発した。
局所グラフ畳み込み単位を局所構造として個別に用いて各部分グラフをより粗いノードに圧縮する。
我々は、グラフ分類のためのSSHPoolモジュールに関連するエンドツーエンドのGNNフレームワークを開発する。
論文 参考訳（メタデータ） (2024-03-24T13:03: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) - Graph Signal Sampling for Inductive One-Bit Matrix Completion: a
Closed-form Solution [112.3443939502313]
グラフ信号解析と処理の利点を享受する統合グラフ信号サンプリングフレームワークを提案する。
キーとなる考え方は、各ユーザのアイテムのレーティングをアイテムイットグラフの頂点上の関数(信号)に変換することである。
オンライン設定では、グラフフーリエ領域における連続ランダムガウス雑音を考慮したベイズ拡張(BGS-IMC)を開発する。
論文 参考訳（メタデータ） (2023-02-08T08:17:43Z) - Graph Partitioning and Sparse Matrix Ordering using Reinforcement
Learning [0.13999481573773068]
本稿では,強化学習とグラフ畳み込みニューラルネットワークに基づくグラフ分割手法を提案する。
提案手法はMETISやスコッチと同様の仕切り品質を実現する。
この方法は、あるクラスのグラフから別のグラフに一般化し、 suitesparse sparse matrix collectionの様々なグラフでうまく機能する。
論文 参考訳（メタデータ） (2021-04-08T06:54:24Z) - Sequential Graph Convolutional Network for Active Learning [53.99104862192055]
逐次グラフ畳み込みネットワーク(GCN)を用いた新しいプールベースアクティブラーニングフレームワークを提案する。
少数のランダムなサンプル画像がシードラベル付き例であるので、グラフのパラメータを学習してラベル付きノードと非ラベル付きノードを区別する。
我々はGCNの特性を利用してラベル付けされたものと十分に異なる未ラベルの例を選択する。
論文 参考訳（メタデータ） (2020-06-18T00:55:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。