提出可证明高阶表达能力的动态图神经网络，突破现有模型局限
Towards Dynamic Graph Neural Networks with Provably High-Order Expressive Power
- 引入k维动态WL测试衡量模型表达能力，发现现有模型上限为1-DWL
- 设计HopeDGN模型，通过节点对交互历史聚合实现2-DWL级表达能力
- 基于Transformer的变体在多个数据集上提升达3.12%，适合动态图建模任务
动态图神经网络（DyGNN）在学习演化图表示方面受到广泛关注。尽管其有效，但现有DyGNN的表达能力有限，难以捕捉动态图的重要演化模式。虽然部分工作尝试通过启发式特征增强表达能力，但缺乏具有可证明和可量化高阶表达能力的框架。为此，我们首次提出k维动态WL测试（k-DWL）作为参考标准，量化DyGNN的表达能力，并证明现有DyGNN的表达能力上限为1-DWL测试。为提升表达能力，我们提出高阶表达能力动态图神经网络（HopeDGN），通过聚合中心节点对与邻近节点对的交互历史来更新表示。理论分析表明，HopeDGN可达到等价于2-DWL测试的表达能力。进一步提出基于Transformer的局部变体实现。实验结果表明，HopeDGN在多个数据集上性能提升最高达3.12%，验证了其有效性。
原文摘要 · Abstract (English)
Dynamic Graph Neural Networks (DyGNNs) have garnered increasing research attention for learning representations on evolving graphs. Despite their effectiveness, the limited expressive power of existing DyGNNs hinders them from capturing important evolving patterns of dynamic graphs. Although some works attempt to enhance expressive capability with heuristic features, there remains a lack of DyGNN frameworks with provable and quantifiable high-order expressive power. To address this research gap, we firstly propose the k-dimensional Dynamic WL tests (k-DWL) as the referencing algorithms to quantify the expressive power of DyGNNs. We demonstrate that the expressive power of existing DyGNNs is upper bounded by the 1-DWL test. To enhance the expressive power, we propose Dynamic Graph Neural Network with High-order expressive power (HopeDGN), which updates the representation of central node pair by aggregating the interaction history with neighboring node pairs. Our theoretical results demonstrate that HopeDGN can achieve expressive power equivalent to the 2-DWL test. We then present a Transformer-based implementation for the local variant of HopeDGN. Experimental results show that HopeDGN achieved performance improvements of up to 3.12%, demonstrating the effectiveness of HopeDGN.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。