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

Franziska Heeg; Jonas Sauer; Petra Mutzel; Ingo Scholtes

cs.LGMay 30, 2025

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

Authors: Franziska Heeg, Jonas Sauer, Petra Mutzel, Ingo Scholtes

Organizations: Chair of Machine Learning for Complex Networks, Center for AI and Data Science (CAIDAS), University of Würzburg, Würzburg, Germany · Karlsruhe Institute of Technology, University of Karlsruhe, Karlsruhe, Germany · Chair of Computational Analytics, Institute for Computer Science 1, University of Bonn, Bonn, Germany

Abstract

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.

Figures & tables

Panel of Figure 1 — Figure 1: A temporal graph $G^{\tau}$ (left) and the corresponding augmented event graph $G^{\text{aug}}$ (right). In $G^{\text{aug}}$ , gray nodes have label $0$ and white nodes have label $1$ . Timestamped edges $(u,v;t)$ are represented as nodes $uv^{t}$ .

Panel of Figure 2 — Figure 2: Example illustrating different temporal graph isomorphism definitions for maximum waiting time $\delta=2$ . Edges are labeled with timestamps. $G_{1}$ is time-concatenated isomorphic to $G_{2}$ , consistent event graph isomorphic to $G_{2}$ and $G_{3}$ , and time-aggregated isomorphic to $G_{2}$ , $G_{3}$ and $G_{4}$ .

Data		Our Model	GAT	TGAT	TGN	CAW	PINT
ants-1-1	[ 3 ]	1.00 $\pm$ 0.00	$0.52\pm 0.04$	$0.54\pm 0.05$	$0.86\pm 0.03$	$0.94\pm 0.01$	$0.86\pm 0.03$
ants-1-2	[ 3 ]	1.00 $\pm$ 0.00	$0.54\pm 0.02$	$0.54\pm 0.04$	$0.85\pm 0.03$	$0.91\pm 0.02$	$0.83\pm 0.04$
sp-workplace	[ 7 ]	1.00 $\pm$ 0.00	$0.53\pm 0.03$	$0.55\pm 0.04$	$0.75\pm 0.04$	$0.92\pm 0.02$	$0.83\pm 0.04$
sp-hospital	[ 30 ]	1.00 $\pm$ 0.00	$0.53\pm 0.04$	$0.55\pm 0.03$	$0.75\pm 0.04$	$0.98\pm 0.01$	$0.95\pm 0.01$
eu-email-dept2	[ 20 ]	1.00 $\pm$ 0.00	$0.54\pm 0.07$	$0.52\pm 0.03$	$0.74\pm 0.04$	$0.76\pm 0.03$	$0.91\pm 0.02$

Table 1: Mean accuracy for binary classification in real-world temporal graphs. For each dataset, we split the timeline into windows of 500 timestamps, generate 400 graphs per window via the shuffling procedures ( Appendix E ), performed 10 runs per window, and report the average over all runs.

Figure 3: Mean classification accuracy for temporal graphs generated with $\sigma_{1}$ vs. $\sigma_{2}$ (25 runs each).

Appendix figures & tables12 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 4 — Figure 4: The temporal graph $G^{\tau}$ (left) and corresponding augmented event graph $G^{\text{aug}}$ (center) from Figure 1 , as well as the compressed augmented event graph $G^{\text{comp}}$ (right). In $G^{\text{aug}}$ and $G^{\text{comp}}$ , gray nodes have label $0$ and white nodes have label $1$ . Timestamped edges $(u,v;t)$ are represented as nodes $uv^{t}$ . In $G^{\text{comp}}$ , edge weights represent the number of connected components of $G^{\text{aug}}$ in which the edge appears.

Panel of Figure 5 — Figure 5: An example of two temporal graphs $G^{\tau}_{1}$ and $G^{\tau}_{2}$ which are consistent event graph isomorphic, but there is no node-consistent isomorphism between the compressed event graphs.

Dataset		$\|V\|$	$\|E\|$	$\|E^{\tau}\|$	$\delta$ in sec.
ants-1-1	[ 3 ]	89	947	1,911	30
ants-1-2	[ 3 ]	72	862	1,820	30
sp-workplace	[ 7 ]	92	755	9,827	3,600
sp-hospital	[ 30 ]	75	1,139	32,424	3,600
eu-email-dept2	[ 20 ]	162	1,772	46,772	3,600

Appendix

Table 2: Statistics of empirical temporal graphs used in our evaluation.

|V|

is the number of nodes,

|E^{\tau}|

the number of timestamped edges, and

\delta

the maximum waiting time used to construct the augmented event graph.

	Our model	GAT
batch size	200	50
weight_decay	0.0001	0
learning rate	0.001	0.001
DirGNN layers	32 $\rightarrow$ 16 $\rightarrow$ 8	–
GatConv layers	–	8 $\rightarrow$ 64 $\rightarrow$ 64
dense layers	8 $\rightarrow$ 4 $\rightarrow$ 1	64 $\rightarrow$ 1

Appendix

Table 3: Optimal hyperparameter values and number of tunable model parameters (i.e., model size) for our model and GAT.

	ants-1-1	ants-1-2	workplace	hospital	eu-email-dept2
batch size	1	1	1	1	1
weight decay	0	0	0	0	0
learning rate	0.001	0.001	0.01	0.001	0.001
layers	64 $\rightarrow$ 128 $\rightarrow$ 1	64 $\rightarrow$ 128 $\rightarrow$ 64 $\rightarrow$ 1	64 $\rightarrow$ 128 $\rightarrow$ 1	64 $\rightarrow$ 128 $\rightarrow$ 1	64 $\rightarrow$ 128 $\rightarrow$ 64 $\rightarrow$ 1
aggr. node embeddings	mean	-	-	mean	-
pooling	-	-	-	-	max

Appendix

Table 4: Optimal hyperparameter values and number of tunable model parameters for CAW.

	ants-1-1	ants-1-2	workplace	hospital	eu-email-dept2
batch size	1	1	1	1	1
weight decay	0	0	0	0	0
learning rate	0.001	0.001	0.01	0.001	0.001
layers	64 $\rightarrow$ 128 $\rightarrow$ 1	64 $\rightarrow$ 128 $\rightarrow$ 64 $\rightarrow$ 1	64 $\rightarrow$ 128 $\rightarrow$ 1	64 $\rightarrow$ 128 $\rightarrow$ 1	64 $\rightarrow$ 128 $\rightarrow$ 64 $\rightarrow$ 1
aggr. node embeddings	mean	-	mean	-	-
pooling	-	-	max	-	-

Appendix

Table 5: Optimal hyperparameter values and number of tunable model parameters for PINT.

	ants-1-1	ants-1-2	workplace	hospital	eu-email-dept2
batch size	1	1	1	1	1
weight decay	0	0	0	0	0
learning rate	0.01	0.001	0.001	0.01	0.001
layers	64 $\rightarrow$ 128 $\rightarrow$ 1	64 $\rightarrow$ 128 $\rightarrow$ 1	64 $\rightarrow$ 128 $\rightarrow$ 1	64 $\rightarrow$ 128 $\rightarrow$ 1	64 $\rightarrow$ 128 $\rightarrow$ 1
aggregation node embeddings	mean	mean	last	mean	mean
pooling	-	max	max	max	max

Appendix

Table 6: Optimal hyperparameter values and number of tunable model parameters for TGAT.

	ants-1-1	ants-1-2	workplace	hospital	eu-email-dept2
batch size	1	1	1	1	1
weight decay	0	0	0	0	0
learning rate	0.001	0.001	0.001	0.001	0.001
layers	64 $\rightarrow$ 128 $\rightarrow$ 1	64 $\rightarrow$ 128 $\rightarrow$ 1	64 $\rightarrow$ 128 $\rightarrow$ 1	64 $\rightarrow$ 128 $\rightarrow$ 1	64 $\rightarrow$ 128 $\rightarrow$ 1
aggregation node embeddings	-	-	-	mean	-
pooling	max	mean	mean	-	max

Appendix

Table 7: Optimal hyperparameter values and number of tunable model parameters for TGN.

Library/Software	Version
CUDA	cu121
torch	2.4.1+cu121
torch_cluster	1.6.3+pt24cu121
torch_scatter	2.1.2+pt24cu121
torch_sparse	0.6.18+pt24cu121
torch_geometric	2.5.1

Appendix

Table 8: Version of key dependencies used in the implementation of our experimental evaluation

Figure 6: Standard deviation of accuracies of our TGNN model for classification of temporal graphs with $\sigma_{1}$ vs. $\sigma_{2}$ for all pairs of $\sigma_{1},\sigma_{2}$ (associated with Figure 3 ).

Panel of Figure 7 — Figure 7: Mean accuracies of a GAT model on the time-concatenated static graph for classification of temporal graphs with $\sigma_{1}$ vs. $\sigma_{2}$ for all pairs of $\sigma_{1},\sigma_{2}$ . The mean standard deviation across all runs is $0.048$ .

Experiment	Accuracy
Compressed augmented event graph	0.95 $\pm$ 0.03
No node labels	0.66 $\pm$ 0.20
Message passing only in one direction	0.63 $\pm$ 0.18
No edge weights	0.81 $\pm$ 0.22

Appendix

Table 9: Results of ablation study for the classification task in the synthetic cluster model, using

\sigma_{1}=0

and

\sigma_{2}=0.9

Temporal GNNs

Temporal graph neural networks model how node relationships, graph structure, and features change over time to support prediction on evolving networks.

See all 82 papers

Temporal Motif Signatures for Temporal Graph Neural Networks
May 31, 2026Dylan Sandfelder, Mihai Cucuringu, Xiaowen DongTemporal GNNs GNN Expressivity
University of Oxford · University of California, Los Angeles
RAFT: Redundancy-Aware Input Filtering for Temporal Graph Neural Network Training
Oct 17, 2026Yue Dai, Sarah Zhou, Youtao ZhangTemporal GNNs
Department of Computer Science, Illinois Institute of Technology, Chicago, USA · BASIS Independent Silicon Valley, San Jose, CA, USA · Department of Computer Science, University of Pittsburgh, Pittsburgh, USA
TemporalGraphLLM: Temporal Graph Neural Networks with Large Language Models for Dynamic Text-Attributed Graphs
Sep 25, 2026Moran Beladev, Or Eitan, Gilad Katz +1Text-Attributed Graph Learning LLMs for Graph Learning
Department of Information Systems Engineering Ben-Gurion University of the Negev, Israel

May 31, 2026J/K move · Enter open · S save

Temporal Motif Signatures for Temporal Graph Neural Networks

Dylan Sandfelder, Mihai Cucuringu, Xiaowen Dong

University of Oxford · University of California, Los Angeles

Temporal GNNs GNN Expressivity Temporal Link Prediction

Open paper AskPDF arXiv

Real temporal interaction streams carry predictive structure in short-horizon motif patterns -- repetition, reciprocity, star diversity, triadic flow -- that vanilla temporal graph neural networks (TGNNs) often fail to expose to their edge scorers. We show this concretely on MOOC interaction prediction, where a small four-feature family of past-window star counts already delivers most of the lift over a strong static GNN. Across a wide set of real and synthetic temporal datasets we find that motif activity organizes consistently along three scale-stable axes (dyadic recency/reciprocity, star diversity, triadic flow), and we use this empirical structure to design a compact 13-coordinate, leakage-safe, candidate-local motif feature map h(u, v, t) that linearly embeds into any static or temporal encoder without architectural changes. A temporal Weisfeiler-Leman (WL) analysis places the augmentation relative to the first level of an anchored temporal-WL hierarchy and exhibits a candidate-anchored pair on which motif features distinguish. We demonstrate empirically that the same augmentation consistently lifts performance across heterogeneous tasks: TGB link-property prediction across all five baselines, edge classification on Bitcoin Alpha/OTC and MOOC, and graph-level classification of synthetic temporal generators.

Abstract

Temporal GNNs

Explore similar work

Temporal Motif Signatures for Temporal Graph Neural Networks

RAFT: Redundancy-Aware Input Filtering for Temporal Graph Neural Network Training

TemporalGraphLLM: Temporal Graph Neural Networks with Large Language Models for Dynamic Text-Attributed Graphs