analiza aiqbench
This research introduces EDiS, a framework that optimizes sparse Graph Neural Network training by decoupling structural extraction from per-epoch graph composition to reduce computational overhead. By caching edge-disjoint subgraphs, the method enables dynamic topology variation without repeated sampling costs while maintaining high accuracy across diverse benchmarks. The work offers significant theoretical insights into preserving critical cut edges under strict budget constraints, directly advancing efficient machine learning on graphs.
EDiS: Edge Disjoint Subgraph Sparsification Framework for Graph Neural Networks
arXiv:2610.09059v1 Announce Type: new 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.
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.
Machine Learning (cs.LG)
arXiv:2610.09059 [cs.LG]
(or arXiv:2610.09059v1 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2610.09059 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Text integral sub licența deschisă a publicației · 298 cuvinte
Subiecte conexe
Towards Faithful Graph Explanations with Synergistic Edge Effects via Granular Balls
arXiv · 24 iul. 2026
Equivariant Neural Primal-Dual Assignment for Maximum Common Edge Subgraphs
arXiv · 30 sept. 2026
Scaffold: Support Graph Theory Based Sparsification for Graph Neural Networks
arXiv · 28 sept. 2026
Subgraph Filtering for Fair Graph Neural Networks
arXiv · 28 aug. 2026