发现稀疏图网络的表达能力是找到高性能彩票票的关键。
Weisfeiler and Leman Go Gambling: Why Expressive Lottery Tickets Win
- 以图同构判别能力为标准，分析稀疏子网的表达性能。
- 证明初始化阶段高表达能力可加速收敛并提升泛化性。
- 适用于药物发现等图学习任务，理论指导模型剪枝。
彩票票假设（LTH）在卷积神经网络中研究深入，但对图神经网络（GNNs）仅获经验验证，缺乏理论支撑。本文指出，稀疏子网的表达能力——即区分非同构图的能力——是找到保留预测性能的获胜彩票票的关键。我们建立了稀疏初始化的GNN表达能力与完整网络相当的条件，特别对比了Weisfeiler-Leman测试，并在此基础上提出并证明了强表达力彩票票假设。随后表明，初始化时更高的表达能力可加速模型收敛并改善泛化性能。研究成果为LTH与GNN研究提供了新的理论基础，强调在稀疏初始化中保持表达力的重要性。我们通过药物发现中的实例展示了这些结果。
原文摘要 · Abstract (English)
The lottery ticket hypothesis (LTH) is well-studied for convolutional neural networks but has been validated only empirically for graph neural networks (GNNs), for which theoretical findings are largely lacking. In this paper, we identify the expressivity of sparse subnetworks, i.e. their ability to distinguish non-isomorphic graphs, as crucial for finding winning tickets that preserve the predictive performance. We establish conditions under which the expressivity of a sparsely initialized GNN matches that of the full network, particularly when compared to the Weisfeiler-Leman test, and in that context put forward and prove a Strong Expressive Lottery Ticket Hypothesis. We subsequently show that an increased expressivity in the initialization potentially accelerates model convergence and improves generalization. Our findings establish novel theoretical foundations for both LTH and GNN research, highlighting the importance of maintaining expressivity in sparsely initialized GNNs. We illustrate our results using examples from drug discovery.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。