EDiS：图神经网络的边不相交子图稀疏化框架

arXiv:2610.09059v1 公告类型：new 摘要：稀疏 GNN 训练能够减少计算量，但决定保留哪些边可能代价高昂。复用同一个稀疏图成本较低，却会使训练受限于固定拓扑；而在不同 epoch 间改变拓扑，则可能需要重复采样或重新计算。我们提出 EDiS（边不相交子图稀疏化框架），将一次性结构提取与逐 epoch 图组合分离开来。EDiS 仅对图进行一次分解，将其划分为可缓存的边不相交子图，随后在不同 epoch 和保留率下，依据边预算约束重新组合成图，而无需重新提取结构。我们的默认构造使用基于特征的分数和连续最大分数覆盖森林；同时，同一图组合机制也支持其他边选择规则。我们对逐 epoch 采样器（即从缓存分解中抽取训练图的组合步骤）进行了组合分析。我们证明，在默认的覆盖森林选择器下，所存储的分解能够确定性地保留高分割边，并推导出一个与选择器无关的条件界，用于刻画组合训练图中高分割边的存活概率。在相同边预算下，针对 19 个同质、异质和大规模节点分类基准，与 17 个基线方法进行比较，EDiS 在参与排名的方法中取得最高的基准平均得分（准确率/ROC-AUC），并实现最低的平均排名和与最佳结果的差距。消融实验表明，在边预算较紧的情况下，结构分解和 epoch 间变化带来的收益最为明显。