| title | EDiS: Edge Disjoint Subgraph Sparsification Framework for Graph Neural Networks |
|---|---|
| authors | 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 |
| date | 2026-10-06 |
| venue | arXiv (preprint, not peer reviewed) |
| id | arXiv:2610.09059 |
| upvotes | 3 (Hugging Face Daily Papers, 2026-11-01) |
| links | abs pdf hf |
| 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. |
cite
@misc{navuluru2026edis,
title={EDiS: Edge Disjoint Subgraph Sparsification Framework for Graph Neural Networks},
author={Sai Karthik Navuluru and Siddhartha Shankar Das and Franck Dernoncourt and S M Ferdous and Ryan A. Rossi and Nesreen K. Ahmed and Baris Coskunuzer and Alex Pothen and Lakshman Tamil and Mahantesh M Halappanavar},
year={2026},
eprint={2610.09059},
archivePrefix={arXiv},
url={https://arxiv.org/abs/2610.09059}
}