提出连续时间动态图神经网络理论框架，解决异步断连图建模难题。
Weisfeiler-Lehman meets Events: An Expressivity Analysis for Continuous-Time Dynamic Graph Neural Networks
- 引入连续时间1-WL测试，匹配动态展开树等价类
- 证明连续时间图神经网络具备区分力与通用逼近能力
- 设计可处理异步断连图的紧凑表达式架构
图神经网络（GNN）在离散动态图上的表现可媲美1-Weisfeiler-Lehman（1-WL）测试，其划分结果与图的展开树等价类一致。该理论适用于属性化离散动态图，即作为连接图快照序列表示的系统。然而，现实世界中的通信网络、金融交易网络和分子相互作用等系统往往异步演化且可能分裂为不连通组件。本文将属性化离散动态图理论扩展至具有任意连通性的属性化连续时间动态图。为此，我们提出连续时间动态1-WL测试，证明其与连续时间动态展开树等价，并识别一类基于离散动态GNN架构的连续时间动态图神经网络（CGNN），其保留了区分能力和通用逼近保证。构造性证明进一步提供了实用设计指南，强调采用分段连续可微的时序函数构建紧凑而表达力强的CGNN架构，以处理异步、断连图结构。
原文摘要 · Abstract (English)
Graph Neural Networks (GNNs) are known to match the distinguishing power of the 1-Weisfeiler-Lehman (1-WL) test, and the resulting partitions coincide with the unfolding tree equivalence classes of graphs. Preserving this equivalence, GNNs can universally approximate any target function on graphs in probability up to any precision. However, these results are limited to attributed discrete-dynamic graphs represented as sequences of connected graph snapshots. Real-world systems, such as communication networks, financial transaction networks, and molecular interactions, evolve asynchronously and may split into disconnected components. In this paper, we extend the theory of attributed discrete-dynamic graphs to attributed continuous-time dynamic graphs with arbitrary connectivity. To this end, we introduce a continuous-time dynamic 1-WL test, prove its equivalence to continuous-time dynamic unfolding trees, and identify a class of continuous-time dynamic GNNs (CGNNs) based on discrete-dynamic GNN architectures that retain both distinguishing power and universal approximation guarantees. Our constructive proofs further yield practical design guidelines, emphasizing a compact and expressive CGNN architecture with piece-wise continuously differentiable temporal functions to process asynchronous, disconnected graphs.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。