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.
Keywords
Publication details
- Journal
- Not available
- Open access
- Green open access
Cite this article
APA 7
Navuluru, S. K., Das, S. S., Dernoncourt, F., Ferdous, S. M., Rossi, R. A., Ahmed, N. K., Coskunuzer, B., Pothen, A., Tamil, L., & Halappanavar, M. M. (2026). EDiS: Edge Disjoint Subgraph Sparsification Framework for Graph Neural Networks. https://omanscience.com/en/articles/edis-edge-disjoint-subgraph-sparsification-framework-for-graph-neural-networks
MLA 9
Navuluru, Sai Karthik, et al. "EDiS: Edge Disjoint Subgraph Sparsification Framework for Graph Neural Networks." https://omanscience.com/en/articles/edis-edge-disjoint-subgraph-sparsification-framework-for-graph-neural-networks.
Chicago (author–date)
Navuluru, Sai Karthik, Siddhartha Shankar Das, Franck Dernoncourt, S M Ferdous, Ryan A. Rossi, Nesreen K. Ahmed, Baris Coskunuzer, Alex Pothen, Lakshman Tamil, and Mahantesh M Halappanavar. 2026. "EDiS: Edge Disjoint Subgraph Sparsification Framework for Graph Neural Networks." https://omanscience.com/en/articles/edis-edge-disjoint-subgraph-sparsification-framework-for-graph-neural-networks.
Harvard
Navuluru, S. K., Das, S. S., Dernoncourt, F., Ferdous, S. M., Rossi, R. A., Ahmed, N. K., Coskunuzer, B., Pothen, A., Tamil, L. and Halappanavar, M. M. (2026) 'EDiS: Edge Disjoint Subgraph Sparsification Framework for Graph Neural Networks', Available at: https://omanscience.com/en/articles/edis-edge-disjoint-subgraph-sparsification-framework-for-graph-neural-networks.
Vancouver
Navuluru SK, Das SS, Dernoncourt F, Ferdous SM, Rossi RA, Ahmed NK, et al. EDiS: Edge Disjoint Subgraph Sparsification Framework for Graph Neural Networks. https://omanscience.com/en/articles/edis-edge-disjoint-subgraph-sparsification-framework-for-graph-neural-networks
IEEE
S. K. Navuluru, S. S. Das, F. Dernoncourt, S. M. Ferdous, R. A. Rossi, N. K. Ahmed, B. Coskunuzer, A. Pothen, L. Tamil, and M. M. Halappanavar, "EDiS: Edge Disjoint Subgraph Sparsification Framework for Graph Neural Networks," https://omanscience.com/en/articles/edis-edge-disjoint-subgraph-sparsification-framework-for-graph-neural-networks.