发现稀疏图神经网络也能保持强表达能力，为高效模型设计提供理论支持。
A Unifying Relational Perspective on Expressive Lottery Tickets
- 用关系魏斯费勒-莱曼框架统一分析多关系与时序图网络的表达能力
- 证明充分参数化的模型中存在保持1阶表达能力的稀疏子网，且可计算其出现概率下界
- 揭示稀疏子网的表达力与优化行为、预测性能的内在关联，适合图学习研究者
图神经网络（GNNs）广泛应用，但参数稀疏性对关系型（RGNNs）和时序型（TGNNs）变体表达能力的影响尚不明确。强表达彩票券假设（SELTH）提出，在静态图上存在保持魏斯费勒-莱曼（WL）表达能力的稀疏GNN。本文通过关系魏斯费勒-莱曼（RWL）框架，将该存在性结果推广至多关系与时序领域，并证明充分参数化的RGNN包含保持1-RWL表达能力的稀疏子网，同时推导出随机剪枝获得此类子网的概率下界。我们进一步表明，常见TGNN及跨图消息传递机制可重构成RGNN形式，从而继承上述保证；且稀疏RGNN的表达能力与其在常规优化策略下的表现密切相关。实验验证了该概率下界，对比了合成数据上的理论与实际概率，并研究了预训练表达能力如何影响时序与分子基准上的优化效果与预测质量。
原文摘要 · Abstract (English)
Graph neural networks (GNNs) are widely used, but how parameter sparsity affects the expressivity of relational (RGNNs) and temporal (TGNNs) variants is poorly understood. The Strong Expressive Lottery Ticket Hypothesis (SELTH) posits the existence of sparse GNNs that preserve Weisfeiler-Leman (WL) expressivity on static graphs. We generalize this existence result to a probabilistic statement for multi-relational and temporal domains via the relational WL (RWL). We prove that sufficiently parameterized RGNNs contain sparse subnetworks that maintain 1-RWL expressivity and derive a lower bound on the probability that a random pruning yields such a subnetwork. We show that common TGNNs and cross-graph message passing schemes admit RGNN reformulations such that they inherit these guarantees and, moreover, that the expressivity of a sparse RGNN is connected to its optimization behavior under common update regimes. Experiments instantiate the bound, compare it to empirical probabilities on synthetic data, and study how pre-training expressivity relates to optimization and prediction quality metrics on temporal and molecular benchmarks.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。