[
    {
        "id": "osp-16774",
        "type": "article-journal",
        "title": "EDiS: Edge Disjoint Subgraph Sparsification Framework for Graph Neural Networks",
        "author": [
            {
                "family": "Navuluru",
                "given": "Sai Karthik"
            },
            {
                "family": "Das",
                "given": "Siddhartha Shankar"
            },
            {
                "family": "Dernoncourt",
                "given": "Franck"
            },
            {
                "family": "Ferdous",
                "given": "S M"
            },
            {
                "family": "Rossi",
                "given": "Ryan A."
            },
            {
                "family": "Ahmed",
                "given": "Nesreen K."
            },
            {
                "family": "Coskunuzer",
                "given": "Baris"
            },
            {
                "family": "Pothen",
                "given": "Alex"
            },
            {
                "family": "Tamil",
                "given": "Lakshman"
            },
            {
                "family": "Halappanavar",
                "given": "Mahantesh M"
            }
        ],
        "URL": "https://omanscience.com/en/articles/edis-edge-disjoint-subgraph-sparsification-framework-for-graph-neural-networks",
        "language": "en",
        "issued": {
            "date-parts": [
                [
                    2026
                ]
            ]
        },
        "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."
    }
]