EDiS: Edge Disjoint Subgraph Sparsification Framework for Graph Neural Networks

EDiS. Edge Disjoint Subgraph Sparsification Framework for Graph Neural Networks. By Sai Karthik Navuluru and nine others, from the University of Texas at Dallas, the Pacific Northwest National Laboratory, and four other institutions. Published on the sixth of October.

Training a graph neural network on a sparse version of its graph saves computation, but choosing which edges to keep has a cost of its own. There are two obvious options, and each gives something up. Reuse a single sparse graph, and the choice is cheap, but training is locked to one fixed topology. Vary the sparse graph from epoch to epoch, and training sees more of the structure, but that can mean sampling or recomputing over and over.

EDiS, the Edge-Disjoint Subgraph sparsification framework, separates the two jobs. Extracting structure happens once. Composing a training graph happens every epoch. The graph is decomposed a single time into edge-disjoint subgraphs that can be cached, and those pieces are then recombined into training graphs that respect an edge budget, across epochs and across retention ratios, without extracting the structure again.

By default, the decomposition is built from feature-based scores and successive maximum score covering forests, though the same composition step also accepts other rules for selecting edges. The authors analyse the per-epoch sampler combinatorially: that is the step that draws a training graph from the cached decomposition. Two results come out. Under the default covering-forest selector, the stored decomposition deterministically preserves cut edges with high scores. And independent of the selector, they derive a conditional bound on how well high-score cut edges survive in the composed training graphs.

The comparison spans nineteen node classification benchmarks, homophilic, heterophilic and large-scale, against seventeen baselines held to the same edge budget. EDiS achieves the highest mean benchmark score, measured as accuracy or ROC-AUC, along with the lowest average rank and the smallest gap to the best method among those ranked. Ablations show that the benefits of structural decomposition and of varying the graph across epochs are clearest when the edge budget is tight.

The design dissolves a trade-off by splitting it in time. The expensive structural work is paid for once and cached, and variety across epochs comes from recombining what is already stored, so training no longer has to choose between a cheap fixed graph and a costly changing one.