pith. sign in

arxiv: 2505.24438 · v3 · pith:3TIVFXXZnew · submitted 2025-05-30 · 💻 cs.LG

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 This is my paper

Pith reviewed 2026-05-22 02:27 UTC · model grok-4.3

classification 💻 cs.LG
keywords temporal graphsevent graphsgraph isomorphismWeisfeiler-Leman algorithmmessage passingtemporal graph neural networkstime-respecting pathscausal topology
0
0 comments X

The pith

Consistent event graph isomorphism captures causal topology in temporal graphs via time-unfolded paths.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper sets out to equip temporal graph neural networks with a formal way to respect the directed flow of time when assessing their ability to tell graphs apart. It defines consistent event graph isomorphism through a time-unfolded representation of time-respecting paths, then builds a temporal Weisfeiler-Leman procedure on that foundation. A reader would care because most current TGNNs overlook which nodes can actually influence others through valid sequences, limiting their power on real timed data. The authors further turn the isomorphism into a concrete message-passing scheme that runs directly on the event-graph view of a temporal network.

Core claim

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.

What carries the argument

consistent event graph isomorphism, defined via a time-unfolded representation of time-respecting paths that encodes the causal topology of a temporal graph

If this is right

  • The temporal Weisfeiler-Leman procedure distinguishes a larger class of non-isomorphic temporal graphs than standard methods.
  • Message passing on the event-graph representation respects the arrow of time by construction.
  • The resulting networks improve classification accuracy on temporal graph datasets where timing determines reachability.
  • Existing notions of temporal isomorphism are shown to be either too coarse or too strict relative to causal paths.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • This definition could be extended to continuous-time event streams by replacing discrete unfolding with interval-based reachability checks.
  • Models trained under the new scheme may transfer better to downstream tasks such as link prediction in contact or citation networks.
  • The same unfolding idea might apply to other temporal operators beyond message passing, such as attention or pooling layers.

Load-bearing premise

The time-unfolded representation of time-respecting paths fully captures the causal topology that matters for distinguishing non-isomorphic temporal graphs.

What would settle it

Two temporal graphs that receive identical consistent event graph isomorphism labels yet produce observably different sets of time-respecting paths or different outcomes on a causal prediction task.

Figures

Figures reproduced from arXiv: 2505.24438 by Franziska Heeg, Ingo Scholtes, Jonas Sauer, Petra Mutzel.

Figure 1
Figure 1. Figure 1: A temporal graph Gτ (left), the corresponding augmented event graph Gaug (center) and the compressed augmented event graph Gcomp (right). In Gaug and Gcomp, gray nodes have label 0 and white nodes have label 1. Timestamped edges (u, v;t) are represented as nodes uvt . In Gcomp , edge weights represent the number of connected components of Gaug in which the edge appears. (ii) πE is a graph isomorphism betwe… view at source ↗
Figure 2
Figure 2. Figure 2: Example illustrating different temporal graph isomorphism definitions for maximum wait [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Results of classification experiments A (left) and B (middle) where we use our TGNN [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: An example of two temporal graphs Gτ 1 and Gτ 1 which are consistent event graph isomor￾phic, but there is no node-consistent isomorphism between the compressed event graphs. is adjacent to (a, b) has an earlier timestamp than the other one, but in other components the order is flipped. The cardinality of the equivalence classes differs between GE 1 and GE 2 , and therefore the edge weights of the represen… view at source ↗
Figure 5
Figure 5. Figure 5: Standard deviation of accuracies of our TGNN model for classification of temporal graphs [PITH_FULL_IMAGE:figures/full_fig_p017_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Mean accuracy of accuracies of a GAT model for classification of temporal graphs with [PITH_FULL_IMAGE:figures/full_fig_p018_6.png] view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper introduces consistent event graph isomorphism for temporal graphs, defined via a time-unfolded representation of time-respecting paths to capture causal topology under the arrow of time. It compares this to prior temporal isomorphism notions, presents a temporal Weisfeiler-Leman algorithm to distinguish non-isomorphic cases, derives a corresponding message-passing scheme for TGNNs on the event-graph representation, and reports positive results on a temporal graph classification task.

Significance. If the unfolding construction and its invariance properties hold, the work supplies a principled way to analyze TGNN expressivity that respects temporal causality, potentially guiding design of more powerful temporal models and providing a benchmark for distinguishing causal influence patterns.

major comments (2)
  1. [§3] §3 (definition of consistent event graph isomorphism): the time-unfolded representation is claimed to fully capture causal topology distinctions, yet the construction does not explicitly address cases where multiple time-respecting paths share nodes or timings and unfold to identical event multisets; a counter-example or invariance lemma showing that distinct causal branching patterns remain non-isomorphic after unfolding is required to support the central claim.
  2. [§5] §5 (derivation of the message-passing scheme): the claim that the derived MP scheme inherits the expressive power of the new isomorphism is load-bearing, but the mapping from the unfolded event-graph WL colors to the temporal MP update rule is only sketched; an explicit proof or reduction showing that the scheme separates exactly the pairs distinguished by consistent event graph isomorphism (and no more) is needed.
minor comments (2)
  1. [Experimental evaluation] The experimental section reports performance on temporal graph classification but does not list the precise baselines, dataset statistics, or statistical significance tests; adding these would improve reproducibility.
  2. [§3] Notation for the time-unfolded graph (e.g., how simultaneous events or node re-identification across slices are encoded) should be formalized with a small diagram or pseudocode for clarity.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their detailed and constructive comments on our manuscript. We address each major comment below with clarifications and revisions to strengthen the presentation of consistent event graph isomorphism and the derived message-passing scheme.

read point-by-point responses

  1. Referee: [§3] §3 (definition of consistent event graph isomorphism): the time-unfolded representation is claimed to fully capture causal topology distinctions, yet the construction does not explicitly address cases where multiple time-respecting paths share nodes or timings and unfold to identical event multisets; a counter-example or invariance lemma showing that distinct causal branching patterns remain non-isomorphic after unfolding is required to support the central claim.

    Authors: We thank the referee for this observation. The time-unfolded representation creates distinct event instances for each occurrence of a node along time-respecting paths, thereby encoding causal branching even when nodes or timings are shared across paths. To make the invariance explicit, we will add a formal lemma to Section 3 in the revised manuscript proving that distinct causal topologies yield non-isomorphic unfolded event graphs. revision: yes

  2. Referee: [§5] §5 (derivation of the message-passing scheme): the claim that the derived MP scheme inherits the expressive power of the new isomorphism is load-bearing, but the mapping from the unfolded event-graph WL colors to the temporal MP update rule is only sketched; an explicit proof or reduction showing that the scheme separates exactly the pairs distinguished by consistent event graph isomorphism (and no more) is needed.

    Authors: We agree that the current derivation sketches the correspondence. In the revised Section 5 we will supply an explicit reduction establishing that the message-passing updates on the event-graph representation separate precisely the pairs distinguished by consistent event graph isomorphism, by showing equivalence to the color refinement process of the temporal Weisfeiler-Leman algorithm. revision: yes

Circularity Check

0 steps flagged

No circularity: new isomorphism and message-passing scheme are independent definitions

full rationale

The paper introduces consistent event graph isomorphism as a fresh definition built on a time-unfolded representation of time-respecting paths, then compares it to prior notions, generalizes the Weisfeiler-Leman algorithm, and derives a message-passing scheme on the resulting event-graph representation. These steps constitute standard theoretical construction rather than any reduction of a claimed result to its own inputs by construction, fitted parameters renamed as predictions, or load-bearing self-citations. The derivation chain remains self-contained because the core isomorphism is stipulated directly and the subsequent algorithm and GNN scheme are built outward from it without circular equivalence to the inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The central claims rest on the background assumption that time-respecting paths are the appropriate objects for capturing causal topology in temporal graphs; no free parameters or invented physical entities are mentioned.

axioms (1)
  • domain assumption Time-respecting paths define the causal topology of temporal graphs
    Invoked when defining consistent event graph isomorphism via time-unfolded representation (abstract).
invented entities (1)
  • consistent event graph isomorphism no independent evidence
    purpose: Formal notion that captures causal topology via time-unfolded time-respecting paths
    New definition introduced to generalize graph isomorphism to temporal graphs

pith-pipeline@v0.9.0 · 5718 in / 1277 out tokens · 33125 ms · 2026-05-22T02:27:25.621449+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

  • IndisputableMonolith/Foundation/ArrowOfTime.lean arrow_from_z echoes
    ?
    echoes

    ECHOES: this paper passage has the same mathematical shape or conceptual pattern as the Recognition theorem, but is not a direct formal dependency.

    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. ... consistent event graph isomorphism, which utilizes a time-unfolded representation of time-respecting paths

  • IndisputableMonolith/Foundation/ArithmeticFromLogic.lean LogicNat ≃ Nat (recovery theorem) echoes
    ?
    echoes

    ECHOES: this paper passage has the same mathematical shape or conceptual pattern as the Recognition theorem, but is not a direct formal dependency.

    We show that time-respecting path isomorphism is equivalent to static graph isomorphism on the augmented event graph ... temporal generalization of the Weisfeiler-Leman algorithm

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

41 extracted references · 41 canonical work pages · 2 internal anchors

  1. [1]

    The surprising power of graph neural networks with random node initialization

    Ralph Abboud, ˙Ismail ˙Ilkan Ceylan, Martin Grohe, and Thomas Lukasiewicz. The surprising power of graph neural networks with random node initialization. In Proceedings of the Thir- tieth International Joint Conference on Artificial Intelligence, IJCAI 2021, pages 2112–2118. ijcai.org, 2021

    work page 2021

  2. [2]

    Directed percolation in temporal networks

    Arash Badie-Modiri, Abbas K Rizi, M ´arton Karsai, and Mikko Kivel ¨a. Directed percolation in temporal networks. Physical Review Research, 4(2):L022047, 2022

    work page 2022

  3. [3]

    Weisfeiler–Lehman goes dynamic: An analysis of the expressive power of graph neural networks for attributed and dynamic graphs

    Silvia Beddar-Wiesing, Giuseppe Alessio D’Inverno, Caterina Graziani, Veronica Lachi, Alice Moallemy-Oureh, Franco Scarselli, and Josephine Maria Thomas. Weisfeiler–Lehman goes dynamic: An analysis of the expressive power of graph neural networks for attributed and dynamic graphs. Neural Networks, 173:106213, 2024

    work page 2024

  4. [4]

    Bronstein

    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

    work page 2023

  5. [5]

    Fast Graph Representation Learning with PyTorch Geometric

    Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with PyTorch Geomet- ric. arXiv preprint arXiv:1903.02428, 2019

    work page internal anchor Pith review Pith/arXiv arXiv 1903

  6. [6]

    Weisfeiler-Leman at the margin: When more expressivity matters

    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

    work page 2024

  7. [7]

    On the equivalence between temporal and static equivariant graph representations

    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

    work page 2022

  8. [8]

    Modern temporal network theory: a colloquium

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

    work page 2015

  9. [9]

    Temporal motifs in time-dependent networks

    Lauri Kovanen, M ´arton Karsai, Kimmo Kaski, J ´anos Kert´esz, and Jari Saram ¨aki. Temporal motifs in time-dependent networks. Journal of Statistical Mechanics: Theory and Experiment, 2011(11):P11005, 2011

    work page 2011

  10. [10]

    Unfolding accessibility provides a macroscopic approach to temporal networks

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

    work page 2013

  11. [11]

    Graph neural networks for temporal graphs: State of the art, open challenges, and opportunities

    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. 10

    work page 2023

  12. [12]

    Bronstein, Martin Grohe, and Stefanie Jegelka

    Christopher Morris, Fabrizio Frasca, Nadav Dym, Haggai Maron, Ismail Ilkan Ceylan, Ron Levie, Derek Lim, Michael M. Bronstein, Martin Grohe, and Stefanie Jegelka. Position: Future directions in the theory of graph machine learning. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Resear...

    work page 2024

  13. [13]

    Kriege, Martin Grohe, Matthias Fey, and Karsten Borgwardt

    Christopher Morris, Yaron Lipman, Haggai Maron, Bastian Rieck, Nils M. Kriege, Martin Grohe, Matthias Fey, and Karsten Borgwardt. Weisfeiler and Leman go machine learning: The story so far. Journal of Machine Learning Research, 24(333):1–59, 2023

    work page 2023

  14. [14]

    Weisfeiler and leman go sparse: To- wards scalable higher-order graph embeddings

    Christopher Morris, Gaurav Rattan, and Petra Mutzel. Weisfeiler and leman go sparse: To- wards scalable higher-order graph embeddings. Advances in Neural Information Processing Systems, 33:21824–21840, 2020

    work page 2020

  15. [15]

    Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe

    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 neu- ral networks. In Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence and Thirty-First Innovative Applications of Artificial Intelligence Conference and Nint...

    work page 2019

  16. [16]

    Kriege, Christopher Morris, and Petra Mutzel

    Lutz Oettershagen, Nils M. Kriege, Christopher Morris, and Petra Mutzel. Temporal graph kernels for classifying dissemination processes. InProceedings of the 2020 SIAM International Conference on Data Mining, SDM 2020, pages 496–504. SIAM, 2020

    work page 2020

  17. [17]

    TGLib: An open-source library for temporal graph anal- ysis

    Lutz Oettershagen and Petra Mutzel. TGLib: An open-source library for temporal graph anal- ysis. In IEEE International Conference on Data Mining Workshops, ICDM 2022, pages 1240–

    work page 2022

  18. [18]

    Path lengths, correlations, and centrality in temporal net- works

    Raj Kumar Pan and Jari Saram ¨aki. Path lengths, correlations, and centrality in temporal net- works. Physical Review E, 84:016105, Jul 2011

    work page 2011

  19. [19]

    EvolveGCN: Evolving graph con- volutional networks for dynamic graphs

    Aldo Pareja, Giacomo Domeniconi, Jie Chen, Tengfei Ma, Toyotaro Suzumura, Hiroki Kanezashi, Tim Kaler, Tao Schardl, and Charles Leiserson. EvolveGCN: Evolving graph con- volutional networks for dynamic graphs. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 5363–5370, 2020

    work page 2020

  20. [20]

    Tessone, and Frank Schweitzer

    Ren ´e Pfitzner, Ingo Scholtes, Antonios Garas, Claudio J. Tessone, and Frank Schweitzer. Betweenness preference: Quantifying correlations in the topological dynamics of temporal networks. Physical Review Letters, 110:198701, May 2013. https://doi.org/10.1103/ PhysRevLett.110.198701

    work page 2013

  21. [21]

    De Bruijn goes neural: Causality-aware graph neural networks for time series data on dynamic graphs

    Lisi Qarkaxhija, Vincenzo Perri, and Ingo Scholtes. De Bruijn goes neural: Causality-aware graph neural networks for time series data on dynamic graphs. InLearning on Graphs Confer- ence, pages 51–1. PMLR, 2022

    work page 2022

  22. [22]

    Temporal Graph Networks for Deep Learning on Dynamic Graphs

    Emanuele Rossi, Ben Chamberlain, Fabrizio Frasca, Davide Eynard, Federico Monti, and Michael Bronstein. Temporal graph networks for deep learning on dynamic graphs. CoRR, abs/2006.10637, 2020

    work page internal anchor Pith review Pith/arXiv arXiv 2006

  23. [23]

    Bronstein

    Emanuele Rossi, Bertrand Charpentier, Francesco Di Giovanni, Fabrizio Frasca, Stephan G¨unnemann, and Michael M. Bronstein. Edge directionality improves learning on heterophilic graphs. In Learning on Graphs Conference 2023 , volume 231 of Proceedings of Machine Learning Research, page 25. PMLR, 2023

    work page 2023

  24. [24]

    Memory in network flows and its effects on spreading dynamics and community detec- tion

    Martin Rosvall, Alcides V Esquivel, Andrea Lancichinetti, Jevin D West, and Renaud Lam- biotte. Memory in network flows and its effects on spreading dynamics and community detec- tion. Nature Communications, 5(1):4630, 2014

    work page 2014

  25. [25]

    Weighted Temporal Event Graphs, pages 107–128

    Jari Saram ¨aki, Mikko Kivel ¨a, and M ´arton Karsai. Weighted Temporal Event Graphs, pages 107–128. Springer International Publishing, Cham, 2019. 11

    work page 2019

  26. [26]

    When is a network a network? Multi-order graphical model selection in path- ways and temporal networks

    Ingo Scholtes. When is a network a network? Multi-order graphical model selection in path- ways and temporal networks. In Proceedings of the 23rd ACM SIGKDD International Con- ference on Knowledge Discovery and Data Mining, KDD ’17, pages 1037–1046. ACM, 2017. http://doi.acm.org/10.1145/3097983.3098145

    work page doi:10.1145/3097983.3098145 2017

  27. [27]

    Higher-order aggregate networks in the analysis of temporal networks: path structures and centralities.The European Physical Journal B, 89(3):61, 2016

    Ingo Scholtes, Nicolas Wider, and Antonios Garas. Higher-order aggregate networks in the analysis of temporal networks: path structures and centralities.The European Physical Journal B, 89(3):61, 2016. http://dx.doi.org/10.1140/epjb/e2016-60663-0

    work page doi:10.1140/epjb/e2016-60663-0 2016

  28. [28]

    Causality-driven slow-down and speed-up of diffusion in non-markovian temporal networks

    Ingo Scholtes, Nicolas Wider, Rene Pfitzner, Antonios Garas, Claudio Juan Tessone, and Frank Schweitzer. Causality-driven slow-down and speed-up of diffusion in non-markovian temporal networks. Nature Communications, 5:5024, September 2014. https://doi.org/10.1038/ ncomms6024

    work page 2014

  29. [29]

    Provably expressive temporal graph networks

    Amauri Souza, Diego Mesquita, Samuel Kaski, and Vikas Garg. Provably expressive temporal graph networks. Advances in Neural Information Processing Systems, 35:32257–32269, 2022

    work page 2022

  30. [30]

    Graph attention networks

    Petar Veli ˇckovi´c, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Li `o, and Yoshua Bengio. Graph attention networks. In 6th International Conference on Learning Rep- resentations, ICLR 2018. OpenReview.net, 2018

    work page 2018

  31. [31]

    Building powerful and equivariant graph neural networks with structural message-passing

    Cl ´ement Vignac, Andreas Loukas, and Pascal Frossard. Building powerful and equivariant graph neural networks with structural message-passing. In Advances in Neural Information Processing Systems 33: Annual Conferencemon Neural Information Processing Systems 2020, NeurIPS 2020, 2020

    work page 2020

  32. [32]

    Expressive power of temporal message passing

    Przemyslaw Andrzej Walega and Michael Rawson. Expressive power of temporal message passing. In AAAI-25, Sponsored by the Association for the Advancement of Artificial Intelli- gence, pages 21000–21008. AAAI Press, 2025

    work page 2025

  33. [33]

    Inductive representation learning on temporal graphs

    Da Xu, Chuanwei Ruan, Evren K ¨orpeoglu, Sushant Kumar, and Kannan Achan. Inductive representation learning on temporal graphs. In 8th International Conference on Learning Rep- resentations, ICLR 2020. OpenReview.net, 2020

    work page 2020

  34. [34]

    How powerful are graph neural networks? In 7th International Conference on Learning Representations, ICLR 2019

    Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In 7th International Conference on Learning Representations, ICLR 2019 . Open- Review.net, 2019

    work page 2019

  35. [35]

    ROLAND: Graph learning framework for dy- namic graphs

    Jiaxuan You, Tianyu Du, and Jure Leskovec. ROLAND: Graph learning framework for dy- namic graphs. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 2358–2366, 2022. 12 A Equivalence of Temporal Graph Isomorphism Notions In the following we give the proof of Theorem 1. Theorem. Let Gτ 1 = ( V1, Eτ 1 ) and Gτ 2 =...

    work page 2022

  36. [36]

    , πE(ek−1), πV (vk))

    We denote the corresponding sequence in Gτ 2 that is induced by πV and πE as π(p) = (πV (v0), πE(e1), πV (v1), . . . , πE(ek−1), πV (vk)). We say that πV and πE are path-preserving be- tween Gτ 1 and Gτ 2 if for each sequence p as defined above, p is a path in Gτ 1 if and only if π(p) is a path in Gτ

    work page

  37. [37]

    Assume therefore that πV and πE are path-preserving between Gτ 1 and Gτ

    It is easy to see that πV and πE are path-preserving between Gτ 1 and Gτ 2 if and only if πE is node-consistent with πV . Assume therefore that πV and πE are path-preserving between Gτ 1 and Gτ

    work page

  38. [38]

    We show that πE is a graph isomorphism between the temporal event graphs GE 1 and GE 2 if and only if it is time- preserving, i.e., a path p in Gτ 1 is time-respecting iff π(p) is time-respecting in Gτ

    work page

  39. [39]

    If k ≥ 2, then p is time-respecting if and only if (e1, (e1, e2), e2,

    If k = 1 , this holds trivially because all paths of length1 are time-respecting. If k ≥ 2, then p is time-respecting if and only if (e1, (e1, e2), e2, . . . ,(ek−2, ek−1), ek−1) is a path in GE 1 . Hence, πE is time-preserving if and only if it is path-preserving betweenGE 1 and GE 2 . Because the event graphs are unlabeled, this is the case if and only ...

    work page

  40. [40]

    and Ga 2 = (V2, Es 2, ℓa

    work page

  41. [41]

    and time-concatenated graphs Gc 1 = (V1, Es 1, ℓc 1) and Gc 2 = (V2, Es 2, ℓc 2). Then the following holds: (i) If there exists an isomorphism πV : V1 → V2 between Gc 1 and Gc 2, then πE : Eτ 1 → Eτ 2 with πE(u, v; t) = ( π(u), π(v); tmin(Gτ 2 ) − tmin(Gτ 1 ) + t) ∀(u, v; t) ∈ Eτ 1 is a consistent event graph isomorphism. (ii) If there exists a consistent...

    work page