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, +2 more
Organizations: University of Texas at Dallas · Pacific Northwest National Laboratory · Adobe Research · University of North Carolina at Charlotte · Cisco · Purdue University
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.
Figures & tables
Figure 1: EDiS generates sparse training graphs under a fixed edge budget.
Figure 2: Overview of the EDiS pipeline.
Method
Cora
CiteSeer
Amazon Photo
WikiCS
Amazon Comp.
Coauthor CS
PubMed
Chameleon
Squirrel
Minesweeper
Ref.
MLP (No graph)
60.14 ±2.62
57.00 ±1.13
92.16 ±0.24
73.10 ±0.19
86.99 ±0.39
95.11 ±0.05
69.82 ±1.86
36.59 ±3.32
39.77 ±1.59
51.34 ±0.77
Spanning Tree
80.86 ±1.17
70.50 ±0.64
92.46 ±0.12
75.05 ±0.23
89.76 ±0.30
94.68 ±0.14
80.40 ±0.99
34.72 ±2.81
36.93 ±1.58
70.73 ±0.21
Full GCN
84.26 ±0.66
72.50 ±0.36
95.95 ±0.14
80.57 ±0.06
93.70 ±0.31
95.61 ±0.36
80.76 ±0.55
44.67 ±3.84
44.79 ±1.82
97.49 ±0.18
EDiS-Full (Ours)
84.08 ±0.83
70.88 ±0.78
96.14 ±0.19
80.39 ±0.29
93.59 ±0.05
95.98 ±0.15
80.20 ±0.46
43.13 ±2.53
43.26 ±2.43
82.62 ±1.09
Topology-guided
Random
73.40 ±0.51
65.86 ±0.95
94.38 ±0.16
77.04 ±0.63
91.05 ±0.15
94.71 ±0.04
74.26 ±0.62
37.85 ±3.35
40.90 ±1.70
72.39 ±1.04
Rank Deg.
76.34 ±0.78
65.10 ±0.24
93.79 ±0.05
76.13 ±0.53
88.04 ±0.28
94.68 ±0.06
76.38 ±0.46
40.35 ±3.82
40.17 ±1.89
71.09 ±0.21
Table 1: Mean ± standard deviation (%) at retention ratio 0.30. The metric is accuracy, except ROC-AUC on Minesweeper, Questions, and Proteins. Best, second-best, and third-best results are shaded blue/bold, gray/underlined, and tan, respectively. AM and GM denote the arithmetic and geometric means across all 19 datasets. The first four reference rows are excluded from ranking.
ρ=0.3
ρ=0.5
Method
Score ↑
Rank ↓
Gap ↓
Score ↑
Rank ↓
Gap ↓
Topology-guided
Random
73.71
8.50
3.49
75.95
7.55
3.04
Local Degree
74.03
7.05
3.17
76.60
7.18
2.39
Rank Degree
70.95
10.24
6.26
73.36
9.87
5.63
Forest Fire
74.36
7.08
2.84
77.10
4.42
1.89
SCAN
72.77
8.79
4.43
75.71
8.08
3.28
Table 2: Summary of Table 1 over all 19 datasets at ρ=0.3 / 0.5 . Score is the mean of per-dataset accuracy or ROC-AUC. Rank and Gap are to the best ranked method per dataset, averaged; shading as in Table 1 .
Figure 3: Full-graph evaluation across regimes. MaxCF with cosine scores.
Figure 4: Decomposition and resampling across edge budgets.
Figure 5: Selector and score sensitivity. GCN at ρ=0.3 . Cells show the gap to the best mean per row and panel (pp, lower is better). Outlines mark defaults. N/A marks PubMed–MLP-score, which is not applicable.
Figure 6: Extraction depth at ρ=0.3 . Reported means with standard-deviation bars. Proteins uses ROC-AUC, others accuracy. Each panel has its own scale.
Figure 7: Backbone comparison within EDiS-Lite.
Appendix figures & tables3 assets
Supplementary material from the paper’s appendix.
Appendix
Symbol
Meaning
Graph and edge-budget
G=(V,E,X)
Attributed undirected graph ( V,X fixed; only the edge set varies below)
n=∣V∣ , m=∣E∣
Number of nodes and edges
ρ
Edge-retention ratio
B=⌈ρm⌉
Number of active edges per epoch
One-time edge decomposition
Appendix
Table 3: Main notation used in EDiS .
Method
Type
Edge budget
Reusable
Multi- struct.
Edge- disjoint
t -Spanner ( Peleg and Schäffer, 1989 )
Sparsification
✓
✓
✗
N/A
Forest Fire ( Leskovec and Faloutsos, 2006 )
Sampling
✗
✗
✗
N/A
SCAN ( Xu et al., 2007 )
Sparsification
✓
✓
✗
N/A
Spectral ( Spielman and Srivastava, 2008 )
Sparsification
✓
✓
✗
N/A
L-Spar ( Satuluri et al., 2011 )
Sparsification
✓
✓
✗
N/A
G-Spar ( Satuluri et al., 2011 )
Sparsification
✓
✓
✗
N/A
Appendix
Table 4: Comparison of graph sampling, sparsification, and multi-structure training methods surveyed in Section 2 and Appendix B . Budget : exposes an explicit target edge count or ratio. Reusable : the structure is computed once and reused rather than resampled from scratch every step. Multi-struct. : training exposes the GNN to more than one structural view. Edge-disjoint : multiple structures, when used, share no edges. “N/A” marks a column that does not apply to a given method.
Figure 8: Structural selection and exact-budget composition in EDiS. Colors and line styles identify edge-disjoint subgraphs, extracted in order (1,2,3) and reused across epochs. The two illustrative epochs sample subgraph orders (3,1,2) and (1,2,3) , adding subgraphs until six edges are reached and trimming any excess uniformly from the lowest-weight subgraph. Samples may overlap and are not guaranteed to differ. These examples illustrate the rules, not predictive rankings.
School of Artificial Intelligence, South China Normal University · School of Computer Science, South China Normal University · Academy of Mathematics and Systems Science, Chinese Academy of Sciences