REVIEW 3 major objections 5 minor 11 references
Weisfeiler-Lehman meets Events: An Expressivity Analysis for Continuous-Time Dynamic Graph Neural Networks
T0 review · 3 major / 5 minor · reviewed 2026-08-15 · deepseek-v4-flash
Pith's one-line read A continuous-time analogue of the 1-WL test pins down the expressive power of dynamic GNNs, and a compact CGNN can approximate any measurable dynamic function that respects the resulting equivalence.
desk verdict Extends WL expressivity to continuous-time dynamic graphs with a clean framework, but the main theorem's proof rests on an unverified adaptation and a wrong probability bound; worth refereeing, not yet established. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing identity is the equivalence between continuous-time unfolding trees and the 1-CWL test: two nodes in a CDG are CUT-equivalent if and only if their 1-CWL color sequences agree at every timestamp. The proof machinery also relies on the dynamic unfolding tree itself, defined recursively from node attributes, edge attributes, and neighbor subtrees at each event time; on the decomposition lemma for color-indistinguishable graphs, which splits such disconnected graphs into connected components matchable by color-preserving bijections; and on the depth bound $2N-1$, which lets infinite trees be replaced by finite ones in the approximation construction. Timestamps are appended to node attributes to partition the continuous-time domain into pieces on which the static universal GNN can be applied.
What would settle it
Exhibit two disconnected continuous-time dynamic graphs with at most $N$ nodes but unbounded degrees whose infinite unfolding trees agree through depth $2N-1$ and differ only beyond it; such a pair would refute the depth bound. Alternatively, show that attaching timestamps to node attributes identifies two CUT-inequivalent graphs, which would break the partitioning step in the approximation construction.
Extended reading notes
Core claim
The paper establishes Theorem 3: for any measurable continuous-time dynamic system on bounded continuous-time dynamic graphs that preserves continuous-time unfolding tree (CUT) equivalence, there exists a CGNN—a universal static GNN with $2N-1$ layers and hidden dimension 1 feeding a piecewise continuously differentiable RNN with state dimension 1—that approximates the system in probability to any precision. The proof routes through Theorem 1, which identifies CUT equivalence with equivalence under the new 1-CWL color-refinement test, and Theorem 2, which carries the depth-$2N-1$ unfolding-tree bound from connected to disconnected graphs via a decomposition of color-indistinguishable graphs into matched connected components. Consequently the CGNN class exactly inherits the distinguishing power of 1-CWL on asynchronous, arbitrarily connected dynamic graphs, and the construction is explicit enough to serve as a design template.
Load-bearing premise
The load-bearing premise is that two technical steps carry over unchanged from prior settings: the decomposition lemma for color-indistinguishable graphs applies even when degrees are unbounded, and appending timestamps to node attributes preserves the partitioning argument used in the discrete-dynamic approximation proof; if either fails, the depth bound and the universal approximation guarantee lose support.
Editorial extensions
If this is right
- Any CGNN built from a universal static GNN and a recurrent temporal function can distinguish exactly the pairs that 1-CWL distinguishes; adding more layers or higher dimensions cannot increase its distinguishing power beyond this ceiling.
- For graphs with at most $N$ nodes, truncating dynamic unfolding trees at depth $2N-1$ loses no information about CUT equivalence, even when the graph is disconnected; the same bound governs how many message-passing rounds a CGNN needs.
- The universal approximation guarantee holds in probability for any measurable system preserving CUT equivalence, so the architecture is a valid template for learning tasks on asynchronous event streams such as transaction or communication networks.
- Piecewise continuous differentiability of the temporal function between events is sufficient for the approximation result, so simple RNN-style updates with one-dimensional state do not sacrifice expressivity.
Reading between the lines
- Editorial inference: the CUT/CWL equivalence provides a training-free diagnostic—compute 1-CWL color sequences on a benchmark of dynamic graphs to predict which differences a CGNN can ever detect, without running the model.
- Editorial inference: the decomposition argument suggests a divide-and-conquer strategy for disconnected dynamic graphs: run color refinement per connected component with the tighter bound $2|C|-1$, which could reduce memory and computation on fragmented graphs.
- Editorial inference: the timestamp-augmentation step in the proof raises a testable design question—whether alternative temporal encodings such as relative inter-event times, decay functions, or attention over time preserve CUT equivalence, or whether they change the expressivity ceiling.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper extends the theory of 1-WL expressivity and universal approximation from attributed discrete-time dynamic graphs to continuous-time dynamic graphs (CTDGs) with arbitrary connectivity. It introduces a continuous-time dynamic 1-WL test (1-CWL) and continuous-time unfolding trees (CUT), proves their equivalence (Theorem 1), extends unfolding-tree depth bounds to disconnected graphs (Theorem 2), and claims a constructive universal approximation theorem for a class of continuous-time dynamic GNNs (CGNNs) composed of a static universal GNN and a recurrent temporal function (Theorem 3). The authors further discuss practical design guidelines, emphasizing single hidden/state dimensions and piecewise differentiable temporal functions.
Significance. If the results hold, the paper would provide the first expressivity and universality guarantees for GNNs on continuous-time dynamic graphs with disconnected snapshots, a setting relevant to many real-world applications. The constructive proof style also yields concrete architectural guidance (2N-1 layers, hidden and state dimension 1), which is valuable. The paper builds on and extends established prior work by Beddar-Wiesing et al. and D'Inverno et al., and the conceptual contribution of linking 1-CWL to CUT equivalence is a natural and useful step. However, the central universal approximation theorem (Theorem 3) is not actually proved in the manuscript: the key partitioning step is delegated to an external lemma whose adaptation to the continuous-time, timestamp-augmented, possibly disconnected setting is asserted without verification. The depth bound for disconnected graphs (Theorem 2) also relies on a bounded-degree lemma without the required assumption. These gaps are load-bearing for the main claim, so the paper in its current form does not fully support its conclusions, although the underlying ideas are plausible and potentially repairable.
major comments (3)
- [§4, proof of Theorem 3] The proof of Theorem 3 does not establish the central claim. The text states that the proof follows [3, Thm. 5.2.4] except for the graph partitioning step [3, Lem. A.5.1], and that appending timestamps to node attributes ensures conditions (2)–(6) of that lemma still hold. However, those conditions are never stated, and the verification is not given. This step is load-bearing: the construction of a CGNN with 2N-1 SGNN layers and a 1-dimensional recurrent state depends on partitioning the domain D=T×G×V into finitely many cells on which h and f are nearly constant, and without a complete proof of the adapted partitioning lemma, Theorem 3 is unsupported. The authors must provide a full statement of the lemma and a detailed proof that it survives timestamp augmentation and arbitrary connectivity.
- [§3, Theorem 2 and Lemma 1] Lemma 1 is stated for graphs of bounded degree, but no degree bound is assumed in Theorem 2, Theorem 3, or Definition 1. The proof of Theorem 2 for disconnected graphs invokes Lemma 1 to decompose indistinguishable graphs into connected components, thereby inheriting an unstated bounded-degree assumption. Since the application of Theorem 2 is essential for the finite-depth reduction in the proof of Theorem 3, this assumption must either be proved to be unnecessary (by extending Bamberger's decomposition lemma to arbitrary degree) or be added as a hypothesis to Theorem 2 and Theorem 3, with the consequences for the main claims stated explicitly.
- [§4, proof of Theorem 3, probability inequality] The final probability bound in the proof of Theorem 3 is reversed as written. After the display 'P(∥cdyn−φ∥≤ε) ≥ Σ_j P(∥cdyn_j−φ_j∥≤ε/T)', the text concludes '(†) ≥ Σ_j (1−λ/T) = T−λ ≥ 1−λ.' This is a union-bound error: from the per-interval bounds one obtains P(∥cdyn−φ∥≤ε) ≥ 1 − Σ_j P(∥cdyn_j−φ_j∥>ε/T), not a sum of successes. A correct derivation requires the per-cell bounds from the missing partition lemma, so this issue is not merely cosmetic. The proof must be corrected with a valid probability argument.
minor comments (5)
- [§2, Definition 1] The notation G is introduced informally as the domain of CDGs with bounded node and timestamp sets, but it is not precisely defined; it should be stated whether attribute values, degrees, or other quantities are also bounded, since Lemma 1 and Theorem 3 depend on boundedness assumptions.
- [§3, Definition 7] The statement of CWL equivalence contains a typo: 'u∼CWL u' should be 'u∼CWL v'.
- [§3, proof of Theorem 2] In the final displayed derivation of the tightened bound, the expression 'T(2(N−1)−1) x = T(2N−3) x = T(2N−3) y = T(2(N−1)−1) y' is garbled; the chain of equalities should be written cleanly, and the variable x appearing on both sides of 'T(2N−3) x' should be y in the middle equality.
- [§4, Definition 9 and Proposition 1] Proposition 1 is essentially a restatement of the definition of preserving CUT equivalence and does not require the full 'if and only if' proof; this is acceptable, but the notation 'cdyn(·,·,·)' and the argument 'u∼CUT v for u,v∈G' in the forward direction are imprecise because u and v should be nodes in the same graph, not graphs.
- [§4, Theorem 4] The proof of Theorem 4 is only a sketch and refers to 'adapting [3, Thm.A.5.2]' without a precise argument; given that Theorem 3's proof is already incomplete, this sketch does not provide additional assurance.
Circularity Check
No significant circularity: the central theorem is a continuous-time transfer of externally published results; the timestamp-augmentation and bounded-degree issues are proof gaps, not circular reductions.
full rationale
The paper's central claim (Theorem 3) is not circular. The continuous-time dynamic system class F(D) is defined by preservation of CUT equivalence, and the proof imports the discrete-dynamic universality theorem from [3], which is an external published result, rather than assuming the paper's own conclusion. The new 1-CWL test and CUT equivalence are defined independently, and their equivalence is reduced per timestamp to the attributed static WL/unfolding-tree equivalence of [3] and [4]; this is a valid transfer of external theorems, not a definition of the target in terms of itself. The only load-bearing points where the text relies on unverified adaptations are (i) Theorem 2's use of Bamberger's bounded-degree decomposition lemma for graphs without a stated degree bound, and (ii) Theorem 3's assertion that appending timestamps to node attributes preserves conditions (2)-(6) of [3, Lem. A.5.1]. Both are proof gaps or missing verifications, not circular reductions: neither defines an output as an input, nor fits a parameter to a predicted quantity. Self-citations to [3] point to a peer-reviewed published paper, and the continuous-time/disconnected extension is independent content, so this does not meet the standard for circularity. Score 1 reflects the absence of definitional or fitted-input circularity, with minor reservations about load-bearing imported lemmas.
Assumptions & free parameters
assumptions (4)
- standard math Stone-Weierstrass and universal approximation theorems for MLPs and RNNs
- domain assumption CDG domain G is bounded in node count and timestamps, and comparison of two CDGs requires identical timestamp sets
- ad hoc to paper Appending timestamps to node attributes preserves the graph partitioning argument of [3, Apx. A.5]
- ad hoc to paper Bamberger's decomposition lemma applies to disconnected graphs with unbounded degree
Cite this review
Pith. "Pith review of Weisfeiler-Lehman meets Events: An Expressivity Analysis for Continuous-Time Dynamic Graph Neural Networks." pith.science (2026). https://pith.science/paper/ICFDUFEO
@misc{pith2026250818052,
author = {Pith},
title = {Pith review of: Weisfeiler-Lehman meets Events: An Expressivity Analysis for Continuous-Time Dynamic Graph Neural Networks},
year = {2026},
howpublished = {\url{https://pith.science/paper/ICFDUFEO}},
note = {Machine review of arXiv:2508.18052}
}
read the original abstract
Graph Neural Networks (GNNs) are known to match the distinguishing power of the 1-Weisfeiler-Lehman (1-WL) test, and the resulting partitions coincide with the unfolding tree equivalence classes of graphs. Preserving this equivalence, GNNs can universally approximate any target function on graphs in probability up to any precision. However, these results are limited to attributed discrete-dynamic graphs represented as sequences of connected graph snapshots. Real-world systems, such as communication networks, financial transaction networks, and molecular interactions, evolve asynchronously and may split into disconnected components. In this paper, we extend the theory of attributed discrete-dynamic graphs to attributed continuous-time dynamic graphs with arbitrary connectivity. To this end, we introduce a continuous-time dynamic 1-WL test, prove its equivalence to continuous-time dynamic unfolding trees, and identify a class of continuous-time dynamic GNNs (CGNNs) based on discrete-dynamic GNN architectures that retain both distinguishing power and universal approximation guarantees. Our constructive proofs further yield practical design guidelines, emphasizing a compact and expressive CGNN architecture with piece-wise continuously differentiable temporal functions to process asynchronous, disconnected graphs.
Reference graph
Works this paper leans on
-
[2]
In: Topological, Algebraic and Geometric Learning Workshops 2022
Bamberger, J.: A Topological Characterisation of Weisfeiler-Leman Equivalence Classes. In: Topological, Algebraic and Geometric Learning Workshops 2022. pp. 17–27. PMLR (2022)
work page 2022
-
[3]
Neural Networks173, 106213 (2024)
Beddar-Wiesing, S., D’Inverno, G.A., Graziani, C., Lachi, V., Moallemy-Oureh, A., Scarselli, F., Thomas, J.M.: Weisfeiler–Lehman Goes Dynamic: An Analysis of the Expressive Power of Graph Neural Networks for Attributed and Dynamic Graphs. Neural Networks173, 106213 (2024)
work page 2024
-
[4]
arXiv preprint arXiv:2106.08992 (2021)
D’Inverno,GiuseppeA.andBianchini,MonicaandSampoli,MariaL.andScarselli, Franco: On the approximation capability of GNNs in node classification/regression tasks. arXiv preprint arXiv:2106.08992 (2021)
arXiv 2021
-
[1]
Azizian, W., marc lelarge: Expressive power of invariant and equivariant graph neural networks. In: International Conference on Learning Representations (2021), https://openreview.net/forum?id=lxHgXYN4bwl
work page 2021
-
[5]
In: 2015 30th annual ACM/IEEE symposium on logic in computer science
Krebs, A., Verbitsky, O.: Universal Covers, Color Refinement, and Two-Variable Counting Logic: Lower Bounds for the Depth. In: 2015 30th annual ACM/IEEE symposium on logic in computer science. pp. 689–700. IEEE (2015) 14 S. Beddar-Wiesing and A. Moallemy-Oureh
work page 2015
-
[6]
Physical Chemistry Chemical Physics 22(45), 26478–26486 (2020)
Nikitin, F., Isayev, O., Strijov, V.: DRACON: Disconnected Graph Neural Network for Atom Mapping in Chemical Reactions. Physical Chemistry Chemical Physics 22(45), 26478–26486 (2020)
work page 2020
-
[7]
Rossi, E., Chamberlain, B., Frasca, F., Eynard, D., Monti, F., Bronstein, M.M.: Temporal graph networks for deep learning on dynamic graphs (2020), https: //arxiv.org/abs/2006.10637
arXiv 2020
-
[8]
IEEE Transactions on Neural Networks 20(1), 81–102 (2008)
Scarselli, F., Gori, M., Tsoi, A.C., Hagenbuchner, M., Monfardini, G.: Compu- tational Capabilities of Graph Neural Networks. IEEE Transactions on Neural Networks 20(1), 81–102 (2008)
work page 2008
Show all 11 references
-
[9]
iEEE Access9, 79143– 79168 (2021)
Skarding, J., Gabrys, B., Musial, K.: Foundations and Modeling of Dynamic Net- works Using Dynamic Graph Neural Networks: A Survey. iEEE Access9, 79143– 79168 (2021)
2021
-
[10]
In: 7th International Conference on Learning Representa- tions, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019
Trivedi, R., Farajtabar, M., Biswal, P., Zha, H.: Dyrep: Learning representations over dynamic graphs. In: 7th International Conference on Learning Representa- tions, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net (2019), https://openreview.net/forum?id=HyePrhR5KX
2019
-
[11]
Xu, K., Hu, W., Leskovec, J., Jegelka, S.: How Powerful are Graph Neural Net- works? arXiv preprint arXiv:1810.00826 (2018)
2018 arXiv
Reviewed August 15, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.