论文标题
可证明表达的时间图网络
Provably expressive temporal graph networks
论文作者
论文摘要
作为嵌入动态相互作用的模型，时间图网络（TGNS）已获得突出性，但对其理论基础知之甚少。我们建立了有关TGN两个主要类别的代表力和限制的基本结果：汇总时间步行的那些（WA-TGN），以及那些通过复发记忆模块（MP-TGN）增强本地消息传递的局部消息。具体而言，新颖的结构揭示了MP-TGN和WA-TGNS的不足，证明这两个类别都不包含另一个。我们将1-WL（Weisfeiler-Leman）测试扩展到时间图，并表明最强大的MP-TGN应该使用注射式更新，因为在这种情况下，它们变得像时间WL一样具有表现力。另外，我们表明，足够深的MP-TGN无法从内存中受益，并且MP/WA-TGN无法计算图形属性，例如周围。 这些理论上的见解使我们获得了品脱 - 一种新型的架构，利用了外观的时间信息传递和相对位置特征。重要的是，品脱的表现力比MP-TGN和WA-TGN更具表现力。品脱在几个现实世界的基准测试上大大优于现有的TGN。
Temporal graph networks (TGNs) have gained prominence as models for embedding dynamic interactions, but little is known about their theoretical underpinnings. We establish fundamental results about the representational power and limits of the two main categories of TGNs: those that aggregate temporal walks (WA-TGNs), and those that augment local message passing with recurrent memory modules (MP-TGNs). Specifically, novel constructions reveal the inadequacy of MP-TGNs and WA-TGNs, proving that neither category subsumes the other. We extend the 1-WL (Weisfeiler-Leman) test to temporal graphs, and show that the most powerful MP-TGNs should use injective updates, as in this case they become as expressive as the temporal WL. Also, we show that sufficiently deep MP-TGNs cannot benefit from memory, and MP/WA-TGNs fail to compute graph properties such as girth. These theoretical insights lead us to PINT -- a novel architecture that leverages injective temporal message passing and relative positional features. Importantly, PINT is provably more expressive than both MP-TGNs and WA-TGNs. PINT significantly outperforms existing TGNs on several real-world benchmarks.
