arXiv：cs.LG· Sai Karthik Navuluru, Siddhartha Shankar Das, Franck Dernoncourt, S M Ferdous, Ryan A. Rossi, Nesreen K. Ahmed, Baris Coskunuzer, Alex Pothen, Lakshman Tamil, Mahantesh M Halappanavar·· 4 小时前AI 评分36
EDiS：面向图神经网络的边不相交子图稀疏化框架
EDiS: Edge Disjoint Subgraph Sparsification Framework for Graph Neural Networks
AI 导读
EDiS 将图一次性分解为可缓存的边不相交子图，再按边预算跨 epoch 重组训练图，无需重复采样或重新提取结构。在 19 个同质、异质及大规模节点分类基准上对比 17 个基线，EDiS 取得最高平均分数（accuracy/ROC-AUC）及最低平均排名与差距。消融显示结构分解与 epoch 变化在紧凑边预算下收益最明显。
正文
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.
| Comments: | 46 pages, including references and appendices |
| Subjects: | Machine Learning (cs.LG) |
| Cite as: | arXiv:2610.09059 [cs.LG] |
| (or arXiv:2610.09059v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2610.09059 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Sa Karthik Navuluru [view email]
[v1]
Tue, 6 Oct 2026 20:09:02 UTC (1,411 KB)
来源：arXiv：cs.LG · arxiv.org