{"id":"ea5ef72a-bdcb-4c9d-9342-ea7d70f59061","arxiv_id":"2501.09856","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A new algorithm, t-NeSt, samples random temporal networks that preserve the time-respecting (causal) neighborhood structure up to a chosen depth d, with theoretical guarantees for temporal Katz centrality.","lead":"This paper introduces a way to randomize temporal networks, whose connections change over time, while keeping the multi-step 'causal' structure that determines how information or disease can spread. The method, temporal color refinement plus rewiring, gives network scientists a null model for testing which temporal patterns are meaningful.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4.1's proof that t-NeSt reaches exactly N^d_G rests on an unverified subset argument for undirected swaps; Theorem 4.2's uniformity also relies on an unproven regular-out-degree claim.","rationale":"The reader's weakest_assumption (infinite look-ahead) is a legitimate modeling limitation and is acknowledged in Section 6, but it does not threaten the internal correctness of the stated theorems. The load-bearing issue is the unproven reachability and uniformity claims in the proofs of Theorems 4.1 and 4.2. After careful analysis, the claims are plausible and likely true: depth-d temporal colors essentially fix the per-time colored degree sequence, and the rewiring chain is a standard colored configuration-model chain with a constant number of choices, so a direct proof could replace the flawed causal-completion argument. Because the current text does not provide that proof, the conditional verdict is appropriate; the concern can be settled by exhaustive enumeration on tiny graphs. This does not change the reader's CONDITIONAL verdict, so verdict_should_be is UNCHANGED.","tokens_in":138,"tokens_out":28306,"duration_ms":548956,"concrete_test":"Write a brute-force enumerator for all temporal graphs with V≤4 vertices and T≤3 timestamps, with uniform initial colors. For each graph G and d∈{1,2,∞}, compute (i) the set N^d_G by directly applying the temporal color refinement recursion, and (ii) the set O(G,d) of graphs reachable by Algorithms 3/4 with in-time rewirings. Also build the exact transition matrix of the MCMC with one rewiring step and compute its stationary distribution. If any instance has O(G,d)≠N^d_G, or the stationary distribution is not uniform over N^d_G, then Theorem 4.1/4.2 is false. If all small instances agree, the proof gap is likely a presentation issue that can be fixed by a direct colored-degree-sequence argument.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central sampling claim depends on Theorem 4.1 (reachability O(G,d)=N^d_G) and Theorem 4.2 (uniform stationary distribution). In the proof of Theorem 4.1 (Appendix A.3, Case ⊆), the authors assert that the rewiring moves are a subset of static NeSt moves on the causal completion graph. For undirected temporal graphs, an in-time swap ({x,y},t),({r,s},t) → ({x,s},t),({r,y},t) corresponds in the directed causal completion to a simultaneous change of two pairs of arcs (x,t)→(y,t), (y,t)→(x,t) and (r,t)→(s,t), (s,t)→(r,t). This is not a single static NeSt switch, so the cited invariance from [40] does not directly apply. If temporal colors are not invariant under the moves, the chain can leave N^d_G and the sample set is wrong. Theorem 4.2 further asserts 'uniform out degree' without proof; whether the number of valid moves is state-independent is not demonstrated. Both gaps concern the exactness of the uniform sampler, which is the paper's main theoretical contribution.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper extends color refinement to temporal networks by defining colors on temporal nodes (v,t) via the multisets of colors of their causal successors, i.e., all later-time neighbors. It introduces two rewiring mechanisms (swaps for undirected graphs, tilts for directed graphs) and an MCMC scheme (t-NeSt) intended to sample approximately uniformly from the set N^d_G of temporal graphs that share the same depth-d temporal colors with an input graph. The main theoretical claims are: Theorem 4.1 (the rewiring moves reach exactly N^d_G), Theorem 4.2 (the chain converges to the uniform distribution on N^d_G), and Theorem 4.4 (nodes with the same stable temporal color have identical temporal Katz centrality). The paper also presents a linear-memory, O(d E log E) algorithm for temporal color refinement and an experimental comparison on ten real-world temporal networks showing that t-NeSt preserves edge persistence, causal triangles, and burstiness better than several existing randomization methods.","tokens_in":20888,"tokens_out":24389,"duration_ms":251939,"significance":"If the technical gaps are repaired, this is a timely and useful contribution. The idea of lifting the static NeSt framework to temporal networks via causal successors is natural but novel, and the fast color-refinement algorithm (Algorithm 1) is likely of independent interest. The paper makes precise, falsifiable claims: Theorems 4.1, 4.2, and 4.4 are explicit statements about reachable sets, stationary distributions, and centralities, and the experiments on real datasets provide a clear comparison against existing null models. The main weakness is that several load-bearing steps in the proofs are asserted rather than demonstrated, so the exactness of the sampler is not yet established as rigorously as the paper's claims require.","major_comments":[{"comment":"The statement of Theorem 4.1 has an off-by-one indexing error relative to the algorithm and the proof. Algorithm 2 obtains colors c^{(d-1)} and the swap conditions in Definitions 4.1-4.2 use those colors, while the proof of Theorem 4.1 defines the multisets C^{d,\\geq}_G using c^{d-1} (Appendix A.3). With this convention, using depth-(d-1) colors in the rewirings preserves depth-d colors, so the reachable set should be O(G,d-1)=N^d_G, not O(G,d)=N^d_G as stated. As written, the theorem overstates the invariant by one level; please reconcile the indexing of d in the theorem statement, in Algorithm 2, and in the claim in Figure 1 that using depth-d colors preserves (d+1)-hop trees.","section":"Section 4 / Theorem 4.1 and Appendix A.3"},{"comment":"The assertion that the rewiring moves are a subset of static NeSt moves on the causal completion is not justified for undirected temporal swaps. An undirected in-time swap ({x,y},t),({r,s},t) → ({x,s},t),({r,y},t) changes four arcs in the directed causal completion simultaneously: (x,t)→(y,t), (y,t)→(x,t), (r,t)→(s,t), (s,t)→(r,t) are replaced by (x,t)→(s,t), (s,t)→(x,t), (r,t)→(y,t), (y,t)→(r,t). This is not a single static NeSt switch in the directed causal completion; it is a composition of two directed switches. The invariance of temporal colors under this move is therefore not a direct consequence of [40] and must be proved explicitly. The same gap affects Theorem 4.4, whose proof relies on the same subset claim.","section":"Appendix A.3, Case ⊆ of Theorem 4.1"},{"comment":"The proof of Theorem 4.2 is a single sentence asserting that the chain has 'uniform out degree' and therefore converges to the uniform distribution. This is not the correct condition: a symmetric transition matrix would suffice, and the asserted property is not demonstrated. The transition probabilities are symmetric only if the swap/tilt operations are involutions on the state space and if color-class sizes and per-time-slice edge counts are invariant under the moves; the latter depends on the color-preservation claim in Theorem 4.1 (see previous comment). Please provide a rigorous proof of the stationary distribution or make the required involution/invariance conditions explicit.","section":"Section 4, Theorem 4.2"}],"minor_comments":[{"comment":"The claim 'Let d ≥ 0, and G′ ∈ N^d_G then for all temporal nodes (v,t), d_G(v,t)=d_{G′}(v,t)' is false for d=0, since N^0_G contains all graphs on the same temporal node set. The statement holds only for d ≥ 1; please correct the range.","section":"Section 4.1"},{"comment":"The phrase 'we further proof that' should read 'we further prove that'.","section":"Abstract"},{"comment":"The pseudocode says 'for (v,t) in increasing order of cs hash', but the iteration is over hash values, not over temporal nodes; please rephrase to 'in increasing order of hash value' to avoid ambiguity.","section":"Algorithm 1, line 13"},{"comment":"The caption states 'For both measures we highlight the values closest to the original graph', but no highlighting is visible in the text. In addition, the phrase 'We omit valeswhen' contains a typo ('valeswhen' should be 'values when').","section":"Table 2 caption"},{"comment":"The sentence 'it would be if interest to characterize' contains a typo ('if' should be 'of').","section":"Section 6"},{"comment":"The general tilt in Definition 4.2 allows changing the time from t to t′, but Algorithm 4 implements only in-time tilts. The text asserts that only in-time rewirings are needed; this is a central fact and should be stated as an explicit proposition with a proof reference, not just as an informal remark.","section":"Appendix A.2 / Definition 4.2"}],"recommendation":"major_revision","confidential_remarks":"The manuscript depends heavily on the authors' own static NeSt paper [40], but the statements of the static results used are not made self-contained; in particular, the exact version of the static reachability and centrality-preservation theorems should be stated. The off-by-one issue in Theorem 4.1 and the unproven subset claim for undirected swaps are fixable but require a careful rewrite of the proof appendix. I would also recommend that the authors provide a mixing-time discussion or at least diagnostics for the MCMC sampler, since the abstract's phrase 'efficiently sample uniformly' goes beyond the asymptotic statement of Theorem 4.2."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Read this paper if you care about null models for temporal networks. The main idea is clean: generalize color refinement to temporal graphs by defining successors through time-respecting edges, then rewire within color classes to sample graphs with the same d-hop causal structure. The algorithmic contribution is real—the incremental multiset hash trick brings refinement to O(dE log E), and the experiments on ten real datasets show t-NeSt preserves edge persistence, causal triangles, and burstiness better than the standard baselines. That part deserves referee time.\n\nThe theoretical core is where I'd push. Theorem 4.1 claims reachability of exactly the identically colored graphs. The proof of the ⊆ direction says the temporal moves are a subset of static NeSt moves on the causal completion graph. I don't buy that as written. An undirected in-time swap changes two pairs of arcs in the directed causal completion simultaneously; that is not one static NeSt switch, and the invariance from [40] doesn't directly transfer. The ⊇ direction is more convincing—induction on time slices and a reduction to static NeSt on the first slice—but the subset direction needs a real argument, not an assertion.\n\nTheorem 4.2 also asserts \"uniform out degree\" without proof. The chain is undirected and aperiodic, sure, but state-independent transition counts are not shown. If the number of valid moves varies across states, the stationary distribution isn't uniform. That's a load-bearing gap for the \"approximately uniform\" claim, though it may be fixable.\n\nMinor issues: the d=0 statement in Section 4.1 doesn't match the definitions—N^0_G with uniform initial colors is too broad for instant degree preservation. And the whole setup assumes infinite look-ahead in Definition 2.2; the authors flag this in Section 6, but it means the preserved \"causality\" includes arbitrarily distant future edges, which may not be what a process model wants. Code is withheld \"for anonymity,\" which is annoying for a reproducibility-sensitive paper.\n\nNet: the method is worth publishing after revision. The algorithmic contribution and experimental evaluation are strong. The proof gaps are not obviously fatal—the claims are plausible and the Katz reduction via the causal completion is elegant—but they need to be addressed. I'd send this to a serious referee and ask for a tightened proof of Theorems 4.1 and 4.2.","headline":"Temporal NeSt is a genuinely useful null model with a quasi-linear algorithm, but the paper needs to fix two proof gaps (reachability subset argument and uniform out-degree) before I'd trust the exact sampling claim.","tokens_in":21451,"tokens_out":2588,"would_cite":true,"duration_ms":26651,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper extends graph color refinement to temporal networks, making it possible to randomize a network while preserving the time-respecting (causal) paths that can reach any node within d hops, and proves the randomization is…","keywords":["temporal networks","color refinement","causal paths","time-respecting walks","graph sampling","null models","Markov chain Monte Carlo","centrality preservation"],"falsifier":"Run t-NeSt($\\infty$) on a temporal graph with two far-apart time slices and compare finite-horizon reachability (counting only time-respecting paths with waiting times at most h) between the original and sampled graphs; whenever edges are separated by a gap larger than h, the sample can preserve all infinite-look-ahead colors yet differ in which nodes are reachable within h.","tokens_in":20442,"feed_emoji":"🕸️","tokens_out":7140,"duration_ms":70540,"temperature":0.7,"pith_summary":"Synthetic temporal networks are usually randomized by preserving degrees or aggregates, but the causal order of interactions—who can reach whom along time-respecting paths—is what drives spreading and influence. This paper shows that the classical color-refinement idea can be adapted to temporal networks: color each time-stamped node by the multiset of colors of all its future neighbors, recursively, which encodes the causal out-unraveling up to depth d. The authors prove that a simple rewiring scheme using only same-time swaps and tilts that respect these colors reaches exactly the set of temporal graphs with identical depth-d colors, so Markov Chain Monte Carlo sampling from this set is asymptotically uniform. They further prove that at the stable coloring, nodes with identical colors have identical temporal Katz centrality, and they show experimentally on ten real networks that edge persistence, causal triangles, and burstiness are better preserved than by existing randomization methods. The algorithms run in near-linear time, so the method scales to real-world temporal networks.","feed_headline":"Rewiring keeps temporal networks' causal paths intact","feed_subtitle":"A color-refinement sampler randomizes graphs while preserving d-hop time-respecting neighborhoods, beating earlier null models.","key_machinery":"The machinery is the temporal color-refinement recursion $c^{(d+1)}_G(v,t) = \\operatorname{hash}\\big(c^{(d)}_G(v,t), \\{\\{ c^{(d)}_G(w,t') : (w,t') \\in S_G(v,t) \\}\\}\\big)$, where $S_G(v,t)$ collects every node reachable from $v$ by an edge at time $t' \\ge t$. This colors a temporal node by its causal out-unraveling—the depth-$d$ tree of time-respecting successors rooted at $(v,t)$. Two structural facts carry the proof: the successor sets of one node over time are nested (earlier times have supersets of later times), which lets Algorithm 1 accumulate multiset hashes incrementally in $O(dE\\log E)$; and the rewiring moves (undirected swaps, directed tilts) that respect colors need only be performed within single time slices, which lets the proof lift the static NeSt result to temporal graphs via the causal-completion graph. The combined procedure is called temporal NeSt, or t-NeSt.","core_discovery":"At its core, the paper establishes that the causal structure of a temporal graph—the tree of time-respecting successors rooted at each time-stamped node—can be turned into an equivalence relation via a temporal version of color refinement, and that this equivalence is exactly what a local rewiring chain can randomize under. Theorem 4.1 states that the temporal NeSt rewiring procedure reaches precisely the set $\\mathcal{N}_G^d$ of temporal graphs whose temporal nodes carry the same depth-$d$ refinement colors, and Theorem 4.2 turns this into asymptotically uniform sampling from $\\mathcal{N}_G^d$. Theorem 4.4 goes further: for the stable (converged) coloring, any two nodes with the same color in the original and sampled graphs have equal temporal Katz centrality, because the rewirings are a subset of static NeSt moves on the causal-completion graph. Empirically the samples preserve edge persistence, causal triangles, and burstiness more faithfully than existing randomization methods on real-world directed and undirected temporal networks.","pith_inferences":["If finite look-ahead matters, the same machinery should carry over: replace $S_G(v,t)$ with successors at times in $[t, t+h]$; the nested-set structure and rewiring proofs still hold, giving a sampler for delay-bounded causal structure.","The exact Katz preservation theorem suggests that any centrality expressible as a function of causal-completion walk counts is invariant under stable-color sampling; communicability is the paper's own conjecture, and reachability-based centralities are a natural next test.","Because t-NeSt($\\infty$) preserves all causal trees, a temporal network statistic that survives this randomization is attributable to the causal neighborhood structure itself—this gives researchers a sharper null model for judging whether motifs or community signals reflect causality rather than timing noise.","The same rewiring idea could be adapted to exact samplers such as curveball-style chains, potentially removing the MCMC burn-in and giving uniform samples in closed form."],"forward_implications":["Every sampled graph has the same depth-$d$ causal out-unraveling at every temporal node, so time-respecting walks up to length $d$ are preserved exactly.","Runtime is $O(dE\\log E + V + T + Tr)$: for the small $d$ observed in real networks, randomization is quasi-linear in the number of edges.","At stable colors, nodes with identical colors in the original and sampled graphs have identical temporal Katz centrality; experiments indicate communicability behaves the same way as depth grows.","On ten real datasets, t-NeSt($\\infty$) reproduces edge persistence, causal triangles, and burstiness more closely than randomized-edge, degree-snapshot-shuffling, random-times, and randomized-contacts baselines, with t-NeSt(1) second-best in most cases.","$\\mathcal{N}_G^1$ is the temporal analog of fixed-degree configuration models, and for static graphs ($T=1$) the method recovers graphs with a fixed degree sequence, so the framework unifies degree- and neighborhood-preserving null models."],"supporting_citations":[{"why":"supplies the static NeSt rewiring procedure and reachability proof that the temporal construction generalizes","marker":"[40]"},{"why":"defines temporal Katz centrality and the product-matrix form Q used in Theorem 4.4","marker":"[14]"},{"why":"provides the incremental multiset hash that makes Algorithm 1 run in O(dE log E) time","marker":"[4]"},{"why":"introduces the classical color refinement that the temporal recursion extends","marker":"[44]"},{"why":"establishes time-respecting paths as the causal backbone of temporal networks and supplies baseline randomization notions","marker":"[19]"},{"why":"defines temporal and causal triangle counting used as experimental benchmark measures","marker":"[34]"},{"why":"reviews randomized reference models and frames the experimental comparison against existing null models","marker":"[11]"}],"fun_headline_variants":["Time-respecting paths survive temporal rewiring","Color refinement preserves temporal causal paths","Rewire temporal networks, keep causal structure intact","Sampling temporal graphs that hold onto causality","Causal paths stay safe under temporal network rewiring"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The paper assumes a node at time t is causally connected to any of its edges at any later time, no matter how distant; if real processes only care about edges within a finite time window, the preserved structure may not be the one that matters.","fun_headline_variants_meta":{"raw":{"variants":["Time-respecting paths survive temporal rewiring","Color refinement preserves temporal causal paths","Rewire temporal networks, keep causal structure intact","Sampling temporal graphs that hold onto causality","Causal paths stay safe under temporal network rewiring"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000487,"raw_usage":{"total_tokens":2362,"prompt_tokens":872,"completion_tokens":1490,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":488,"completion_tokens_details":{"reasoning_tokens":1423}},"tokens_in":488,"tokens_out":1490,"duration_ms":16292,"temperature":1.0,"reasoning_tokens":1423,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T19:39:55.660376+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run t-NeSt($\\infty$) on a temporal graph with two far-apart time slices and compare finite-horizon reachability (counting only time-respecting paths with waiting times at most h) between the original and sampled graphs; whenever edges are separated by a gap larger than h, the sample can preserve all infinite-look-ahead colors yet differ in which nodes are reachable within h.","supporting_citations":[{"cited_title":"Neighborhood structure configuration models","cited_arxiv_id":null,"evidence_quote":"supplies the static NeSt rewiring procedure and reachability proof that the temporal construction generalizes"},{"cited_title":"Communicability across evolving networks","cited_arxiv_id":null,"evidence_quote":"defines temporal Katz centrality and the product-matrix form Q used in Theorem 4.4"},{"cited_title":"Incremental multiset hash functions and their application to memory integrity checking","cited_arxiv_id":null,"evidence_quote":"provides the incremental multiset hash that makes Algorithm 1 run in O(dE log E) time"},{"cited_title":"Faster and generalized temporal triangle counting, via degeneracy ordering","cited_arxiv_id":null,"evidence_quote":"defines temporal and causal triangle counting used as experimental benchmark measures"},{"cited_title":"Randomized reference models for temporal networks","cited_arxiv_id":null,"evidence_quote":"reviews randomized reference models and frames the experimental comparison against existing null models"}],"review_version":1}