Joint Edge-Model Sparse Learning is Provably Efficient for Graph Neural Networks
Joint Edge-Model Sparse Learning is Provably Efficient for Graph Neural Networks
复制标题
DOI：
10.48550/arxiv.2302.02922
复制
发表时间：
2023-02
期刊：
影响因子：
--
通讯作者：
Shuai Zhang;M. Wang;Pin-Yu Chen;Sijia Liu;Songtao Lu;Miaoyuan Liu
中科院分区：
文献类型：
--
作者：
Shuai Zhang;M. Wang;Pin-Yu Chen;Sijia Liu;Songtao Lu;Miaoyuan Liu
由于训练大规模图神经网络（GNN）的重大计算挑战，因此已经利用了各种稀疏的学习技术来降低记忆和存储成本。示例包括\ textIt {Graph Sparsification}，该案例示例了一个子图，以减少数据聚合的量和\ textIt {模型稀疏}，该{模型稀疏}可以减少神经网络以减少可训练的权重的数量。尽管在降低训练成本的同时保持了测试准确性方面取得了经验成功，但GNNS稀疏学习的理论概括分析仍然难以捉摸。据我们所知，本文从样本复杂性和收敛速率的角度实现了零概括误差的角度，提供了关节边缘模型稀疏学习的第一个理论表征。从分析上证明，取样重要的节点和最低含量的修剪神经元都可以降低样品复杂性并改善收敛性，而不会损害测试准确性。尽管该分析集中于具有数据结构限制的两层GNN，但洞察力适用于更通用的设置，并通过合成和实用的引用数据集证明。
Due to the significant computational challenge of training large-scale graph neural networks (GNNs), various sparse learning techniques have been exploited to reduce memory and storage costs. Examples include \textit{graph sparsification} that samples a subgraph to reduce the amount of data aggregation and \textit{model sparsification} that prunes the neural network to reduce the number of trainable weights. Despite the empirical successes in reducing the training cost while maintaining the test accuracy, the theoretical generalization analysis of sparse learning for GNNs remains elusive. To the best of our knowledge, this paper provides the first theoretical characterization of joint edge-model sparse learning from the perspective of sample complexity and convergence rate in achieving zero generalization error. It proves analytically that both sampling important nodes and pruning neurons with the lowest-magnitude can reduce the sample complexity and improve convergence without compromising the test accuracy. Although the analysis is centered on two-layer GNNs with structural constraints on data, the insights are applicable to more general setups and justified by both synthetic and practical citation datasets.