Weisfeiler and Leman Follow the Arrow of Time: Expressive Power of Message Passing in Temporal Event Graphs

arXiv:2505.24438 · cs.LG · Submitted 2025-05-30 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Today's paper: "Weisfeiler and Leman Follow the Arrow of Time".

Jane: The gist The authors introduce consistent event graph isomorphism,

Tom: First, who's behind it and why it matters.

Paper summary: Tom: So we're diving into this paper today, "Weisfeiler and Leman Follow the Arrow of Time: Expressive Power of Message Passing in Temporal Event Graphs." It looks like they are tackling a big problem in how we model things that happen over time on graphs.

Jane: Exactly. The main point here is they introduce a new way to define graph isomorphism specifically for temporal graphs, which is different from standard graph isomorphism because it has to respect the direction of time and causality.

Lu: What's really interesting is that they use these time-respecting paths in temporal graphs to analyze their causal topology, which isn't something that most existing temporal graph neural networks focus on <ref:2505.24438#pg1>.

Meng: So what does this mean practically? Are we talking about a way to make the AI models actually understand the cause-and-effect in a time series data?

Tom: Right. They claim that they lack a generalization of graph isomorphism for temporal graphs that really captures this causal topology, and they introduce consistent event graph isomorphism to fill that gap <ref:2505.24438#pg1>.

Jane: It seems like the authors argue that the correct temporal order of edges is necessary for causal influence, but it's not enough—you also need to consider which order of events is impossible because it goes backwards in time <ref:2505.24438#pg2>.

Lalam: The paper suggests that if you have a path from node u to node v in graph one, there has to be a corresponding time-respecting path between the same nodes in any isomorphic graph two <ref:2505.24438#pg1>.

Tom: That sounds like they are trying to define what it means for two temporal graphs to be structurally identical in terms of their temporal flow, not just their static connections <ref:2505.24438#pg1>.

Jane: They contrast this with timewise isomorphism, which is stricter because it also cares about the actual timestamp values, meaning two graphs can have the same time-respecting paths but still be considered different if the timestamps are different <ref:2505.24438#pg1>.

Lu: Then they connect this idea back to something familiar by showing that time-respecting path isomorphism is equivalent to static graph isomorphism on an augmented event graph <ref:2505.24438#pg1>.

Meng: An augmented graph sounds like a lot of extra computation, but if it lets them generalize the Weisfeiler-Leman algorithm to the temporal setting, that’s significant for testing model expressivity <ref:2505.24438#pg1>.

Tom: Right. And they then use this foundation to build a novel message passing scheme for temporal graph neural networks that operates on this augmented event graph <ref:2505.24438#pg1>.

Jane: This new scheme is designed specifically to generate representations that allow the model to distinguish between non-isomorphic temporal graphs based on those time-respecting paths <ref:2505.24438#pg1>.

Lu: They show that this model, M1, has at least as much expressive power as another model, M2, if M1 can distinguish all the node pairs that M2 can distinguish <ref:2505.24438#pg2>.

Tom: The experimental evaluation shows their TGNN architecture in a temporal graph classification setting perfectly distinguishes Class one graphs from Class two graphs Experimental Evaluation.

Jane: That means the model is able to separate causal topologies that are preserved from those that are destroyed by shuffling, which supports their theoretical results Experimental Evaluation.

Meng: I wonder if this helps us in a practical sense. They also mention that their model achieves superior performance compared to baseline models which struggle to identify how timestamp differences affect time-respecting paths Experimental Evaluation.

Lu: And they confirm that their model reliably distinguishes graphs with random patterns from non-random patterns, even when cross-cluster time-respecting paths are either overrepresented or underrepresented Experimental Evaluation.

Tom: It sounds like the core idea here is that neural message passing can be expressive enough to see those subtle differences in path ordering caused by time, which was previously overlooked Conclusion.

Jane: So, to wrap up on this paper, "Weisfeiler and Leman Follow the Arrow of Time: Expressive Power of Message Passing in Temporal Event Graphs," the authors provide a theoretical foundation for causality-aware message passing architectures by using a natural generalization of graph isomorphism based on time-respecting paths Conclusion.

Lu: They conclude that their model achieves the best performance compared to other approaches, supporting arguments about how expressive power relates to model performance Conclusion.

Meng: For us on the engineering side, this suggests that if we build our temporal models around this concept of event graphs and message passing on them, we should see better results in real-world applications involving time series data Conclusion.

Tom: So the paper ends by suggesting that neural message passing is expressive enough to see differences in path ordering caused by time, which is what makes these models powerful for temporal data Conclusion.

Conclusion: Tom: So we're wrapping up this look at "Weisfeiler and Leman Follow the Arrow of Time: Expressive Power of Message Passing in Temporal Event Graphs." Basically, these authors are showing how to define graph isomorphism for time-respecting paths in temporal graphs.

Jane: Right. They’ve introduced this new way to check if two temporal graphs are structurally the same while respecting the flow of time and causality.

Lu: It all boils down to using those time-respecting paths to figure out a causal topology, which is a really important part of how these systems work over time.

Meng: So they’re taking something from static graph isomorphism and making it work for temporal data by looking at an augmented event graph, which sounds like a lot of extra structure.

Lalam: From my view, this new framework gives us a way to make AI models actually understand the cause-and-effect in time series data, which is pretty cool for how we model culture or behavior.

Tom: And the results they show are solid—their neural message passing scheme can perfectly separate graphs that have the right causal structure from those that don't.

Jane: It means these AI models can get much better at distinguishing real patterns from random noise when dealing with time-ordered data, even when things look superficially similar.

Lu: The paper points out that their model M1 has expressive power equal to another one, M2, if M1 can see all the differences that M2 can see between node pairs.

Meng: That suggests we can design more powerful AI architectures specifically tailored to detect these subtle temporal ordering issues in the data.

Lalam: If this translates into better models for understanding complex cultural flows or economic patterns, it could really help us map out how things evolve over time in a more accurate way.

Tom: And while they show this works well for classification, they do flag that extending this method to link prediction or node classification is something they plan to look at next.

Jane: Exactly. It's a solid foundation for understanding temporal graphs, but the real test is how far we can take these ideas into predicting specific events within that time structure.

Lu: So the big picture here is proving that neural message passing isn't just about static connections; it can learn to respect and analyze the direction of time itself.

University of Würzburg · Karlsruhe Institute of Technology · Institute for Computer Science 1

cs.LG

Submitted: 2025-05-30

Updated: 2026-10-13

Code: https://github.com/StatsDLMathsRecomSys/Inductive-representation-learning-on-temporal-graphs

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 80/100

The gist: The gist The authors introduce consistent event graph isomorphism, a new generalization of graph isomorphism for temporal graphs that utilizes time-unfolded representations of time-respecting paths

Key concepts

Time-Respecting Path Isomorphism: This is a new measure for comparing two temporal graphs based on whether they preserve the order of time-respecting paths. A path is 'time-respecting' if the edges along it follow a specific chronological sequence. This concept focuses only on preserving these ordered paths, ignoring other potential differences in edge timestamps.
Augmented Event Graph: This is an auxiliary graph created to simplify the comparison of temporal graphs. It combines the original nodes and edges with a static line graph expansion that captures time-respecting paths. This allows researchers to treat the complex temporal path structure as a simpler, static graph problem, making isomorphism testing easier.
Novel Message Passing Scheme: This is a new way to use neural networks (TGNNs) to analyze temporal graphs. The scheme operates on the augmented event graph and is designed specifically to learn and detect differences in time-respecting paths. It allows the model to distinguish between temporal graphs that might look identical but have different causal structures.
Causality-Aware Learning: This refers to learning patterns in temporal data by respecting the direction of time. In a temporal graph, not just the sequence of events matters, but also which event can causally influence another based on their relative timestamps. This concept ensures that the learned representations capture the true causal topology of the system.

Terminology

Generalization — 2× in this paper · explained in 13 episodes

Summary

The gist The authors introduce consistent event graph isomorphism, a new generalization of graph isomorphism for temporal graphs that utilizes time-unfolded representations of time-respecting paths in temporal graphs to analyze their causal topology and develop a novel message passing scheme for temporal event graphs.

Motivation

Graph neural networks (GNNs) have been generalized to temporal GNNs (TGNNs) that capture patterns in time series data on temporal graphs, which can be categorized into discrete-time and continuous-time types. An important additional characteristic of temporal graphs is how the directed arrow of time influences which nodes can possibly causally influence each other via time-respecting paths. This causal influence is a precondition that enables causality-aware learning in temporal graphs, as the correct temporal order of edges is necessary but not sufficient for causal influence. Numerous works in network science have studied how the temporal ordering of edges influences connectivity, dynamical processes like spreading or diffusion, node centralities, cluster patterns, or controllability. These patterns are often neglected by TGNNs, which can limit their performance in high-resolution time series data on temporal graphs.

Proposed Isomorphism and Theoretical Foundation

The authors propose a new temporal generalization of graph isomorphism called time-respecting path isomorphism, which focuses on the preservation of time-respecting paths between temporal graphs. This definition preserves temporal reachability: if there is a time-respecting path from u to v in G1, there must also be one between the corresponding nodes in any isomorphic G2. Time-respecting paths impose a partial ordering on timestamped edges—if a path passes e before e′, then e must precede e′; otherwise their relative order is irrelevant. They contrast this with timewise isomorphism, showing that it is stricter because it also considers the timestamp values, meaning two temporal graphs with identical time-respecting paths can be timewise non-isomorphic.

Equivalence to Static Graph Isomorphism

The authors show that time-respecting path isomorphism is equivalent to static graph isomorphism on the augmented event graph, a newly proposed auxiliary graph that captures time-respecting paths through a static line graph expansion and is augmented by the original nodes in the temporal graph. Theorem 1 establishes the equivalence between (i) Gτ1 and Gτ2 are time-respecting path isomorphic, (ii) Gτ1 and Gτ2 are consistent event graph isomorphic, and (iii) Gaaug1 and Gaaug2 are isomorphic. This equivalence is crucial for generalizing the Weisfeiler-Leman (WL) algorithm to the temporal setting.

Novel Message Passing Scheme

Building on this theoretical foundation, they derive a novel message passing scheme for TGNNs that operates on the augmented event graph and generates representations that allow to distinguish non-isomorphic temporal graphs. This approach is specifically tailored towards detecting time-respecting path isomorphism. The model M1 is at least as expressive as another model M2 if M1 distinguishes all node pairs that are distinguished by M2, and Dir-GNN on the augmented event graph has the same expressive power as D-WL on the augmented event graph if f(t)com, →f(t)agg and ←−f(t)agg are injective.

Experimental Evaluation

The authors experimentally evaluate their TGNN architecture in a temporal graph classification setting, comparing it to existing TGNNs based on timewise isomorphism. The model perfectly distinguishes Class 1 graphs (preserved causal topology) from Class 2 (destroyed by shuffling), supporting their theoretical results. Their model achieves superior performance compared to baseline models, which struggle to identify which timestamp differences affect time-respecting paths, whereas their model achieves perfect performance by modeling this explicitly in the augmented event graph. Furthermore, the results confirm that their model reliably distinguishes graphs with random patterns from non-random patterns, independent of whether cross-cluster time-respecting paths are over- (σ > 0) or under-represented (σ < 0).

Conclusion

The work provides a theoretical foundation for causality-aware message passing architectures for temporal graphs by introducing a natural generalization of graph isomorphism to temporal graphs based on time-respecting paths. This suggests that neural message passing is expressive enough to distinguish temporal graphs with identical static topology but different time-respecting paths. The authors conclude that their model achieves the best performance compared to other approaches, supporting arguments in Morris et al. [16], which highlights a complex relationship between expressivity and model performance.

Limitations and Open Issues

The work evaluates expressivity via temporal graph classification, but they note that extending this framework to node classification or link prediction is an interesting future work. They also did not compare their definition of temporal graph isomorphism to the notion of isomorphism on temporal computation trees, which is the basis for Souza et al. [29].

References

[1] Arash Badie-Modiri, Abbas K Rizi, Márton Karsai, and Mikko Kivelä. Directed percolation in temporal networks. Physical Review Research, 4(2):L022047, 2022

[3] Benjamin Blonder and Anna Dornhaus. Time-ordered networks reveal limitations to information flow in ant colonies. PloS one, 6(5):e20298, 2011

[4] Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M. Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(1):657–668, 2023

[5] Billy Joe Franks, Christopher Morris, Ameya Velingker, and Floris Geerts. Weisfeiler-Leman at the margin: When more expressivity matters. In Forty-first International Conference on Machine Learning, ICML 2024. OpenReview.net, 2024

[6] Jianfei Gao and Bruno Ribeiro. On the equivalence between temporal and static equivariant graph representations. In International Conference on Machine Learning, ICML 2022, volume 162 of Proceedings of Machine Learning Research, pages 7052–7076. PMLR, 2022

[7] Mathieu Génois and Alain Barrat. Can co-location be used as a proxy for face-to-face contacts? EPJ Data Science, 7(1):1–18, 2018

[8] Abigail J. Hayes, Tobias Schumacher, and Markus Strohmaier. What do temporal graph learning models learn?, 2025. URL https://arxiv.org/abs/2510.09416

[9] Franziska Heeg and Ingo Scholtes. Using time-aware graph neural networks to predict temporal centralities in dynamic graphs. In Advances in Neural Information Processing Systems, volume 37, pages 30149–30178. Curran Associates, Inc., 2024

[10] Petter Holme. Modern temporal network theory: a colloquium. The European Physical Journal B, 88:1–30, 2015

[11] Hartmut HK Lentz, Thomas Selhorst, and Igor M Sokolov. Unfolding accessibility provides a macroscopic approach to temporal networks. Physical Review Letters, 110(1):7-3024987, 2013

[12] Antonio Longa, Veronica Lachi, Gabriele Santin, Monica Bianchini, Bruno Lepri, Pietro Lio, Franco Scarselli, and Andrea Passerini. Graph neural networks for temporal graphs: State of the art, open challenges, and opportunities. Transactions on Machine Learning Research, 2023

[13] Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence and Thirty-First Innovative Applications of Artificial Intelligence Conference and Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, AAAI’19/IAAI’19/EAAI’19. AAAI Press, 2019

[14] Christopher Morris, Gaurav Rattan, and Petra Mutzel. Weisfeiler and leman go sparse: Towards scalable higher-order graph embeddings.

Improvements for AI systems

Bold header: Temporal Graph Neural Networks (TGNNs) with Causality-Aware Message Passing

This improved system will operate on an augmented event graph and utilize a Dir-GNN [25] architecture, allowing it to explicitly model time-respecting path isomorphism. This enables the system to distinguish between temporal graphs that share the same static topology but differ in causal structure, as demonstrated by its ability to identify Class 1 graphs from Class 2.

Bold header: Distinguishing Causal Topology via Time-Respecting Paths

The system can perform causality-aware learning by leveraging the definition of time-respecting path isomorphism, which is equivalent to static graph isomorphism on augmented event graphs. This allows the model to predict a single class for a temporal graph rather than multiple classes across different times, directly addressing the core challenge of distinguishing structures that affect time-respecting paths.

Bold header: Enhanced Expressivity for Link Prediction and Node Classification

By using the Dir-GNN [25] on the augmented event graph, the system achieves expressive power equivalent to D-WL (directed 1-WL test), which is strictly more expressive than undirected 1-WL and GNNs. This suggests it can better distinguish non-isomorphic temporal graphs for downstream tasks like link prediction or node classification by capturing causal motifs that other models miss.

Bold header: Robustness Against Timestamp Perturbations

The model will be robust against transformations that destroy time-respecting path structure (like Method C shuffling) while remaining sensitive to those that preserve it (like Method A). This allows the system to reliably classify graphs based on their underlying causal topology, even when the specific values or relative ordering of timestamps are altered.