{"id":"33694ce5-f950-4379-897d-a1f19c8b5674","arxiv_id":"2508.18052","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Continuous-time dynamic GNNs built from static universal approximators and recurrent updates match a new continuous-time 1-WL test and inherit universal approximation guarantees, even on disconnected asynchronous graphs.","lead":"This paper extends graph neural network expressivity theory from discrete-time snapshots to continuous-time dynamic graphs that can split into disconnected pieces. It introduces a continuous-time Weisfeiler-Lehman test, proves it equivalent to unfolding trees, and shows a class of dynamic GNNs can approximate any measurable target function on such graphs.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Thm 3 rests on an asserted adaptation of [3, Lem. A.5.1] to timestamp-augmented, possibly disconnected snapshots; the finite-partition step is unverified and load-bearing.","rationale":"The central claim is only as strong as the constructive reduction to [3]. The proof has to build a finite partition of the continuous-time dynamic graph domain and then simulate the resulting finite-state recursion with a one-dimensional RNN. The authors state that appending timestamps preserves the conditions of [3, Lem. A.5.1], but the lemma is not reproduced and the verification is not carried out. This is the exact step where continuous time and arbitrary connectivity enter; if it fails, the 2N-1 layer / hidden-dimension-1 construction does not follow. Bamberger's bounded-degree lemma is a real irritant but not the deeper issue: the first part of Thm. 2 can likely be obtained by applying the connected depth bound componentwise, so that gap is repairable. The partition step, however, is load-bearing for both distinguishing power and universality. The proof's final probability manipulation is also wrong as written, but a corrected union bound could fix it once approximation on each cell is established. Therefore the reader's CONDITIONAL verdict is appropriate: the high-level claim is plausible and supported by the equivalence machinery, but the main construction has an unverified core. My concern does not require rejection; it requires the authors to supply the missing partition-lemma derivation.","tokens_in":11324,"tokens_out":30209,"duration_ms":343340,"concrete_test":"Re-derive the proof of Theorem 3 with the exact statement of [3, Lem. A.5.1] in hand. Write down the finite partition of D=T×G×V that results from appending timestamps to node attributes, and verify each of the lemma's conditions (2)-(6) when snapshots are disconnected, have unbounded degree, and carry real-valued attributes that are only required to be bounded by Def. 1. If any condition fails, for example because the lemma needs connected snapshots or a compact attribute/time domain, or because the partition's error must be controlled on sets of total P-measure 1-lambda, then the asserted adaptation does not go through and Thm. 3 is unproved in its current form.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 3's proof does not itself establish the approximation claim. It says (Sec. 4, proof of Thm. 3) that the proof follows [3, Thm. 5.2.4] except for the 'graph partitioning step,' and that appending timestamps to node attributes ensures conditions (2)-(6) of [3, Lem. A.5.1] still hold. Those conditions are not stated, and the verification is not given. 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 the snapshot feature h and the transition f are nearly constant; only then can a scalar-state recurrence simulate the resulting finite-state update. G (Def. 1) is only assumed to have bounded node and timestamp sets, and [3]'s prior result was stated for connected snapshots. The paper's only bridge to disconnected graphs is Thm. 2, whose proof invokes Bamberger's bounded-degree lemma [2], although no degree bound appears in Thm. 2 or Thm. 3. Even if that depth bound is repairable directly by components, the partition lemma itself has not been shown to survive timestamp augmentation and arbitrary connectivity. The final probability inequality in the proof (P>=sum P) is also reversed as written; curing it needs exactly the same per-cell bounds. The main theorem is therefore supported by an assertion about a lemma that is never stated or checked.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":11669,"tokens_out":2218,"duration_ms":24062,"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":[{"comment":"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.","section":"§4, proof of Theorem 3"},{"comment":"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.","section":"§3, Theorem 2 and Lemma 1"},{"comment":"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.","section":"§4, proof of Theorem 3, probability inequality"}],"minor_comments":[{"comment":"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.","section":"§2, Definition 1"},{"comment":"The statement of CWL equivalence contains a typo: 'u∼CWL u' should be 'u∼CWL v'.","section":"§3, Definition 7"},{"comment":"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.","section":"§3, proof of Theorem 2"},{"comment":"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.","section":"§4, Definition 9 and Proposition 1"},{"comment":"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.","section":"§4, Theorem 4"}],"recommendation":"major_revision","confidential_remarks":"The paper relies heavily on [3] and [4], both by Beddar-Wiesing and co-authors, but this is a transfer of established results rather than circular reasoning; the issue is that the adaptation is not proved. If the authors can supply the missing partition lemma for timestamp-augmented, disconnected, unbounded-degree graphs and fix the probability bound, the paper may be suitable for publication. In the current state, the central theorem is not self-contained."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nQuick take: this paper is a genuine extension of the 1-WL/GNN expressivity story to continuous-time dynamic graphs with arbitrary connectivity, and the definitions (1-CWL test, continuous unfolding trees, CUT equivalence) are clean. But the central theorem is not actually proved in the text: the proof of Thm 3 delegates the load-bearing partitioning step to [3, Lem. A.5.1], asserts that appending timestamps preserves conditions (2)-(6), and never states or checks those conditions. The final probability inequality is also reversed as written. Thm 2 silently extends a bounded-degree lemma from [2] to all disconnected graphs. The paper deserves a serious referee, but the results should not be treated as established yet.\n\nWhat's genuinely new: the continuous-time WL test and unfolding-tree equivalence, and the attempt to handle disconnected snapshots, which prior work explicitly excluded. The architecture guidance (2N-1 layers, scalar state) follows from the construction if the construction works. The paper is also honest about building on [3] and [4]; the self-citations are appropriate, not circular.\n\nThe soft spots are real but not necessarily fatal. Thm 2's proof applies [2, Lem. 1] to components without a degree bound; the authors' own Lemma 1 states bounded degree. That's a missing hypothesis in the statement or a missing argument. Thm 3's core is an assertion about [3, Lem. A.5.1] that is not reproduced; a referee would need that lemma and the verification of conditions (2)-(6) with timestamp-augmented attributes. And the probability step P(||cdyn-phi||<=epsilon) >= sum P(||cdyn_j-phi_j||<=epsilon/T) is simply wrong as written; the union bound gives the needed 1-lambda. These are all repairable, but they are load-bearing.\n\nBottom line: this is a paper for the dynamic-GNN expressivity community, and a serious referee should engage. I'd send it to review, but I'd expect a major revision with the proofs filled in. For my own work, I wouldn't cite Thm 3 until it's fixed.","headline":"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.","tokens_in":12128,"tokens_out":2183,"would_cite":false,"duration_ms":22441,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68T07","05C60","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["continuous-time dynamic graphs","graph neural networks","Weisfeiler-Lehman test","unfolding trees","universal approximation","disconnected graphs","expressivity","dynamic graph neural networks"],"falsifier":"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.","tokens_in":11143,"feed_emoji":"⏱️","tokens_out":9078,"duration_ms":85559,"temperature":0.7,"pith_summary":"This paper aims to move graph neural network expressivity theory from discrete-time snapshot sequences to asynchronous continuous-time dynamic graphs that may split into disconnected pieces. Its central assertion is that a continuous-time version of the 1-WL color-refinement test—the 1-CWL test—produces exactly the same node and graph partitions as continuous-time dynamic unfolding trees, and that this equivalence is faithfully inherited by a concrete class of continuous-time GNNs. If true, it means that any measurable dynamic graph function that respects unfolding-tree equivalence can be approximated in probability by a CGNN with just one hidden dimension, $2N-1$ layers, and a one-dimensional recurrent state, no matter how the graph's connectivity evolves. The result also sharpens the earlier depth bound for disconnected graphs, so the theory covers systems that split into components.","feed_headline":"Continuous-time GNNs inherit the full power of the 1-WL test","feed_subtitle":"Even on disconnected, asynchronous graphs, a compact CGNN can approximate any function that respects unfolding-tree equivalence.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the discrete-dynamic 1-WL test, unfolding-tree equivalence, and constructive universal-approximation proof that this paper adapts to continuous time.","marker":"[3]"},{"why":"Provides the $2N-1$ unfolding-tree depth bound and the unfolding-tree/WL correspondence for connected graphs that Theorem 2 extends.","marker":"[4]"},{"why":"Provides the decomposition of color-indistinguishable graphs into matched connected components used to extend the depth bound to disconnected graphs.","marker":"[2]"},{"why":"Supplies the universal-cover depth lower bound used for the tightness statement in Theorem 2.","marker":"[5]"},{"why":"Gives the characterization of functions of unfolding trees used in Proposition 1 to define the target function class.","marker":"[8]"},{"why":"Establishes the 1-WL upper bound on GNN distinguishing power, the starting point for the expressivity argument.","marker":"[11]"}],"fun_headline_variants":["1-WL test goes continuous-time for dynamic GNNs","Continuous-time GNNs match 1-WL on disconnected graphs","CGNNs get 1-WL power for asynchronous dynamic graphs","Even disconnected graphs now fit the 1-WL unfolding tree","1-WL test now covers asynchronous, disconnected graphs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["1-WL test goes continuous-time for dynamic GNNs","Continuous-time GNNs match 1-WL on disconnected graphs","CGNNs get 1-WL power for asynchronous dynamic graphs","Even disconnected graphs now fit the 1-WL unfolding tree","1-WL test now covers asynchronous, disconnected graphs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000706,"raw_usage":{"total_tokens":3176,"prompt_tokens":936,"completion_tokens":2240,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":552,"completion_tokens_details":{"reasoning_tokens":2154}},"tokens_in":552,"tokens_out":2240,"duration_ms":16196,"temperature":1.0,"reasoning_tokens":2154,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T16:58:04.917949+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Neural Networks173, 106213 (2024)","cited_arxiv_id":null,"evidence_quote":"Supplies the discrete-dynamic 1-WL test, unfolding-tree equivalence, and constructive universal-approximation proof that this paper adapts to continuous time."},{"cited_title":"In: Topological, Algebraic and Geometric Learning Workshops 2022","cited_arxiv_id":null,"evidence_quote":"Provides the decomposition of color-indistinguishable graphs into matched connected components used to extend the depth bound to disconnected graphs."},{"cited_title":"In: 2015 30th annual ACM/IEEE symposium on logic in computer science","cited_arxiv_id":null,"evidence_quote":"Supplies the universal-cover depth lower bound used for the tightness statement in Theorem 2."},{"cited_title":"IEEE Transactions on Neural Networks 20(1), 81–102 (2008)","cited_arxiv_id":null,"evidence_quote":"Gives the characterization of functions of unfolding trees used in Proposition 1 to define the target function class."}],"review_version":2}