Edge disjoint subgraphs improve sparse graph neural network training
EDiS: Edge Disjoint Subgraph Sparsification Framework for Graph Neural Networks
Machine Learning
Summary
Training graph neural networks (GNNs) faster often means using fewer connections (edges) between nodes, but picking which edges to keep can be slow. The authors present EDiS, a method that splits the graph into separate edge sets once and then mixes these sets differently in each training round without having to redo the splitting. This approach keeps important connections and lets the training vary the graph structure over time, which leads to better performance across many tests compared to other methods. The framework works well especially when the number of edges allowed is very small.
What this means in practice
- •For machine learning engineers: Train graph neural networks efficiently with limited edges by reusing edge-disjoint subgraphs to reduce computation while preserving key graph structure.
- •For social network analysts: Analyze large social graphs by training GNNs that vary subgraph connections across training rounds without costly recomputation of edges.
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
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.