图神经网络稀疏化新突破！首次证明时序图也能中“彩票”，随机剪枝保性能
A Unifying Relational Perspective on Expressive Lottery Tickets
👨💼 主理人解读 · 为什么值得关注
将强表达性彩票假设推广到关系型和时间型GNN，揭示参数稀疏性对WL表达性的影响，帮助设计更高效的稀疏图模型。
📖 AI 总结
该研究针对图神经网络（GNN）中参数稀疏性对表达能力影响的理解空白，将强表达彩票假设（SELTH）从静态图推广至多关系图（RGNN）与时间图（TGNN）领域。作者通过关系型Weisfeiler-Lehman（RWL）框架，证明了充分参数化的RGNN中存在保持1-RWL表达能力的稀疏子网络，并给出了随机剪枝成功概率的下界。研究还表明，常见TGNN与跨图消息传递机制可重构为RGNN形式，从而继承上述理论保证，且稀疏RGNN的表达能力与其在常见更新规则下的优化行为存在关联。实验在合成数据上验证了理论界，并在时间与分子基准上考察了预训练表达能力对优化及预测质量的影响。该工作为理解稀疏图模型的理论性质提供了统一视角，对设计高效且表达能力强的图神经网络具有指导意义。
🔑 关键词速览
| Strong Expressive Lottery Ticket Hypothesis (SELTH) | 强表达性彩票假设，认为存在稀疏子网络能保持原始网络的表达能力。 |
| Weisfeiler-Leman (WL) expressivity | WL表达能力，衡量图神经网络区分非同构图的能力，基于WL图同构测试。 |
| Relational WL (RWL) | 关系型WL，将WL测试扩展到多关系图，用于评估关系型GNN的表达能力。 |
| Relational GNNs (RGNNs) | 关系型图神经网络，处理具有多种边类型或关系的图数据。 |
| Temporal GNNs (TGNNs) | 时序图神经网络，处理随时间演化的图结构数据。 |
📱 每天一份 AI 前沿日报
关注公众号，每天 09:00 推送 · 不错过任何重磅