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

• URL: http://arxiv.org/abs/2505.24438v2
• Date: Fri, 13 Jun 2025 20:29:04 GMT
• Title: 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,
• Abstract summary: We introduce the notion of consistent event graph isomorphism, which utilizes a time-unfolded representation of time-respecting paths in temporal graphs.<n>We derive a novel message passing scheme for temporal graph neural networks that operates on the event graph representation of temporal graphs.
• Score: 2.9561405287476177
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Beyond Message Passing: Neural Graph Pattern Machine [50.78679002846741]
  We introduce the Neural Graph Pattern Machine (GPM), a novel framework that bypasses message passing by learning directly from graph substructures.<n>GPM efficiently extracts, encodes, and prioritizes task-relevant graph patterns, offering greater expressivity and improved ability to capture long-range dependencies.
  arXiv  Detail & Related papers  (2025-01-30T20:37:47Z)
• Inference of Sequential Patterns for Neural Message Passing in Temporal Graphs [0.6562256987706128]
  HYPA-DBGNN is a novel two-step approach that combines the inference of anomalous sequential patterns in time series data on graphs. Our method leverages hypergeometric graph ensembles to identify anomalous edges within both first- and higher-order De Bruijn graphs. Our work is the first to introduce statistically informed GNNs that leverage temporal and causal sequence anomalies.
  arXiv  Detail & Related papers  (2024-06-24T11:41:12Z)
• Self-Explainable Temporal Graph Networks based on Graph Information Bottleneck [21.591458816091126]
  Temporal Graph Networks (TGNN) have the ability to capture both the graph topology and dynamic dependencies of interactions within a graph over time. There has been a growing need to explain the predictions of TGNN models due to the difficulty in identifying how past events influence their predictions. This is the first work that simultaneously performs prediction and explanation for temporal graphs in an end-to-end manner.
  arXiv  Detail & Related papers  (2024-06-19T04:55:34Z)
• An embedding-based distance for temporal graphs [3.703194328049199]
  We use embeddings based on time-respecting random walks to introduce a new notion of distance between temporal graphs. This distance is well-defined for pairs of temporal graphs with different numbers of nodes and different time spans. We show that the distance we introduce discriminates graphs with different topological and temporal properties.
  arXiv  Detail & Related papers  (2024-01-23T15:25:21Z)
• Graph-Level Embedding for Time-Evolving Graphs [24.194795771873046]
  Graph representation learning (also known as network embedding) has been extensively researched with varying levels of granularity. We present a novel method for temporal graph-level embedding that addresses this gap.
  arXiv  Detail & Related papers  (2023-06-01T01:50:37Z)
• Deep Temporal Graph Clustering [77.02070768950145]
  We propose a general framework for deep Temporal Graph Clustering (GC) GC introduces deep clustering techniques to suit the interaction sequence-based batch-processing pattern of temporal graphs. Our framework can effectively improve the performance of existing temporal graph learning methods.
  arXiv  Detail & Related papers  (2023-05-18T06:17:50Z)
• Dynamic Causal Explanation Based Diffusion-Variational Graph Neural Network for Spatio-temporal Forecasting [60.03169701753824]
  We propose a novel Dynamic Diffusion-al Graph Neural Network (DVGNN) fortemporal forecasting. The proposed DVGNN model outperforms state-of-the-art approaches and achieves outstanding Root Mean Squared Error result.
  arXiv  Detail & Related papers  (2023-05-16T11:38:19Z)
• Temporal Aggregation and Propagation Graph Neural Networks for Dynamic Representation [67.26422477327179]
  Temporal graphs exhibit dynamic interactions between nodes over continuous time. We propose a novel method of temporal graph convolution with the whole neighborhood. Our proposed TAP-GNN outperforms existing temporal graph methods by a large margin in terms of both predictive performance and online inference latency.
  arXiv  Detail & Related papers  (2023-04-15T08:17:18Z)
• Learning the Evolutionary and Multi-scale Graph Structure for Multivariate Time Series Forecasting [50.901984244738806]
  We show how to model the evolutionary and multi-scale interactions of time series. In particular, we first provide a hierarchical graph structure cooperated with the dilated convolution to capture the scale-specific correlations. A unified neural network is provided to integrate the components above to get the final prediction.
  arXiv  Detail & Related papers  (2022-06-28T08:11:12Z)
• Spatio-Temporal Joint Graph Convolutional Networks for Traffic Forecasting [75.10017445699532]
  Recent have shifted their focus towards formulating traffic forecasting as atemporal graph modeling problem. We propose a novel approach for accurate traffic forecasting on road networks over multiple future time steps.
  arXiv  Detail & Related papers  (2021-11-25T08:45:14Z)
• On the Equivalence Between Temporal and Static Graph Representations for Observational Predictions [10.759470206355145]
  We show that node representations in temporal graphs can be cast into two distinct frameworks: time-and-graph and time-then-graph. We show that time-then-graph methods are capable of achieving better performance and efficiency than state-of-the-art time-and-graph methods in some real-world tasks.
  arXiv  Detail & Related papers  (2021-03-12T00:31:33Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.