提出时间图同构新定义，提升时序图神经网络的因果建模能力。
Weisfeiler and Leman Follow the Arrow of Time: Expressive Power of Message Passing in Temporal Event Graphs
- 基于时间展开路径定义一致事件图同构，捕捉因果拓扑
- 设计时序版图同构检测算法，可区分非同构时序图
- 构建事件图消息传递机制，适合建模时序因果关系
时序图的重要特征在于时间方向如何影响其因果拓扑，即哪些节点可能通过时间尊重路径相互影响。现有时序图神经网络常忽略此类模式。为系统分析其表达能力，亟需一个能完整刻画因果拓扑的时序图同构推广。本文提出一致事件图同构，利用时序图中时间展开路径的表示进行建模。与现有时序图同构定义对比，该方法更准确反映因果结构。在此基础上，我们开发了一种时序版的Weisfeiler-Leman算法，用于启发式区分非同构时序图。进一步，基于此理论框架，设计了在事件图表示上运行的新消息传递方案。实验表明，该方法在时序图分类任务中表现良好。
原文摘要 · Abstract (English)
An important characteristic of temporal graphs is how the directed arrow of time influences their causal topology, i.e., which nodes can possibly influence each other causally via time-respecting paths. The resulting patterns are often neglected by temporal graph neural networks (TGNNs). To formally analyze the expressive power of TGNNs, we lack a generalization of graph isomorphism to temporal graphs that fully captures their causal topology. Addressing this gap, we introduce the notion of consistent event graph isomorphism, which utilizes a time-unfolded representation of time-respecting paths in temporal graphs. We compare this definition with existing notions of temporal graph isomorphisms. We illustrate and highlight the advantages of our approach and develop a temporal generalization of the Weisfeiler-Leman algorithm to heuristically distinguish non-isomorphic temporal graphs. Building on this theoretical foundation, we derive a novel message passing scheme for temporal graph neural networks that operates on the event graph representation of temporal graphs. An experimental evaluation shows that our approach performs well in a temporal graph classification experiment.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。