REVIEW 3 major objections 6 minor 46 references
Efficient Sampling of Temporal Networks with Preserved Causality Structure
T0 review · 3 major / 6 minor · reviewed 2026-08-10 · deepseek-v4-flash
Pith's one-line read 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…
desk verdict 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. 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 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.
What would settle it
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.
Extended reading notes
Core claim
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.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (3)
- [Section 4 / Theorem 4.1 and Appendix A.3] 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.
- [Appendix A.3, Case ⊆ of Theorem 4.1] 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 4, Theorem 4.2] 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.
minor comments (6)
- [Section 4.1] 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.
- [Abstract] The phrase 'we further proof that' should read 'we further prove that'.
- [Algorithm 1, line 13] 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.
- [Table 2 caption] 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 6] The sentence 'it would be if interest to characterize' contains a typo ('if' should be 'of').
- [Appendix A.2 / Definition 4.2] 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.
Circularity Check
No circularity: the temporal color refinement and t-NeSt sampling theorems are genuine extensions of the separately published static NeSt result, with no fitted parameter or definitional equivalence at the core.
full rationale
The paper's derivation chain is not circular. Temporal color refinement (eq. 3.2) is a standalone recursive definition over temporal successors, and the set N^d_G is defined by those colors; Theorem 4.1's subset direction is an invariant of moves that are explicitly constrained by the colors, while the superset direction is a nontrivial reachability induction whose base case is the separately published static NeSt result [40]. Although [40] shares authors with the present paper, it is an external, independently argued WWW 2023 result and does not assume the temporal claims, so the self-citation is load-bearing but not circular. No parameter is fitted to make a theorem true: d and r are user-chosen, alpha is the standard Katz downweighting parameter, and the empirical quantities (edge persistence, causal triangles, burstiness) are not used as fitting targets. The paper openly flags its infinite look-ahead modeling assumption in Section 6, which is a scope limitation rather than a circular reduction. Correctness concerns noted elsewhere, such as Theorem 4.2's asserted uniform out-degree and Appendix A.3's identification of undirected temporal swaps with static NeSt moves on the causal completion graph, are proof-completeness issues rather than cases where a prediction reduces by construction to its input; they therefore do not raise the circularity score.
Assumptions & free parameters
free parameters (3)
- depth d
- number of rewirings r
- Katz downweighting alpha (and communicability beta)
assumptions (3)
- domain assumption Static NeSt reachability theorem from [40]
- domain assumption Perfect hash functions with no collisions
- domain assumption Infinite look-ahead in successor definition
Cite this review
Pith. "Pith review of Efficient Sampling of Temporal Networks with Preserved Causality Structure." pith.science (2026). https://pith.science/paper/HAVCAKYG
@misc{pith2026250109856,
author = {Pith},
title = {Pith review of: Efficient Sampling of Temporal Networks with Preserved Causality Structure},
year = {2026},
howpublished = {\url{https://pith.science/paper/HAVCAKYG}},
note = {Machine review of arXiv:2501.09856}
}
abstract
In this paper, we extend the classical Color Refinement algorithm for static networks to temporal (undirected and directed) networks. This enables us to design an algorithm to sample synthetic networks that preserves the $d$-hop neighborhood structure of a given temporal network. The higher $d$ is chosen, the better the temporal neighborhood structure of the original network is preserved. Specifically, we provide efficient algorithms that preserve time-respecting ("causal") paths in the networks up to length $d$, and scale to real-world network sizes. We validate our approach theoretically (for Degree and Katz centrality) and experimentally (for edge persistence, causal triangles, and burstiness). An experimental comparison shows that our method retains these key temporal characteristics more effectively than existing randomization methods.
Figures
Reference graph
Works this paper leans on
-
[40]
Neighborhood structure configuration models
Felix I Stamm, Michael Scholkemper, Markus Strohmaier, and Michael T Schaub. Neighborhood structure configuration models. In Proceedings of the ACM Web Conference 2023, pages 210–220, 2023
work page 2023
-
[1]
Generating uni- formly distributed random networks
Yael Artzy-Randrup and Lewi Stone. Generating uni- formly distributed random networks. Physical Review E, 72(5):056708, 2005
work page 2005
-
[2]
A. Cardon and M. Crochemore. Partitioning a graph in O(AlogV). Theoretical Computer Science, 19(1):85– 98, 1982
work page 1982
-
[3]
CJ Carstens. Proof of unif. sampling of binary matrices with fixed row and column sums for the curveball algorithm. Phys Rev E, 2015
work page 2015
-
[4]
Incremental multiset hash functions and their application to memory integrity checking
Dwaine Clarke, Srinivas Devadas, Marten Van Dijk, et al. Incremental multiset hash functions and their application to memory integrity checking. In ASI- ACRYPT 2003, pages 188–207. Springer, 2003
work page 2003
-
[5]
https: //networkrepository.com/email-dnc.php, October 2017
Dnc emails network dataset – KONECT. https: //networkrepository.com/email-dnc.php, October 2017
work page 2017
-
[6]
The mixing time of the switch Markov chains: a unified approach
PL Erdos et al. The mixing time of the swap (switch) markov chains: a unified approach. arXiv preprint arXiv:1903.06600, 2019
work page Pith review arXiv 1903
-
[7]
Communicability in temporal net- works
Ernesto Estrada. Communicability in temporal net- works. Physical Review E, 88(4):042811, 2013
work page 2013
Show all 46 references
-
[8]
Regular equivalence: General theory
Martin G Everett and Stephen P Borgatti. Regular equivalence: General theory. Journal of mathematical sociology, 19(1):29–52, 1994
1994
-
[9]
others Fosdick
Bailey K. others Fosdick. Configuring Random Graph Models with Fixed Degree Sequences. SIAM Review, 60(2):315–355, 2018
2018
-
[10]
Mining (maximal) span-cores from temporal networks
Edoardo Galimberti, Alain Barrat, Francesco Bonchi, Ciro Cattuto, and Francesco Gullo. Mining (maximal) span-cores from temporal networks. In Proceedings of the 27th ACM international Conference on Infor- mation and Knowledge Management, pages 107–116, 2018
2018
-
[11]
Randomized reference models for temporal networks
Laetitia Gauvin, Mathieu G´ enois, M´ arton Karsai, et al. Randomized reference models for temporal networks. SIAM Review, 64(4):763–830, 2022
2022
-
[12]
Detectability Thresholds and Optimal Algorithms for Community Structure in Dynamic Networks
Amir Ghasemian, Pan Zhang, Aaron Clauset, Cristo- pher Moore, and Leto Peel. Detectability Thresholds and Optimal Algorithms for Community Structure in Dynamic Networks. Physical Review X, 6(3):031005, 2016
2016
-
[13]
Generating graphs randomly
Catherine Greenhill. Generating graphs randomly. arxiv, 2022
2022
-
[14]
Communicability across evolving networks
Peter Grindrod, Mark C Parsons, Desmond J Higham, et al. Communicability across evolving networks. Physical Review E, 83(4):046120, 2011
2011
-
[15]
A Survey on Temporal Graph Representation Learning
Shubham Gupta and Srikanta Bedathur. A Survey on Temporal Graph Representation Learning. arxiv, 2022
2022
-
[16]
Data on face-to-face contacts in an office building suggest a low-cost vaccination strategy based on community linkers
Mathieu G´ enois et al. Data on face-to-face contacts in an office building suggest a low-cost vaccination strategy based on community linkers. Network Science, 3:326–347, 9 2015
2015
-
[17]
Network reachability of real-world con- tact sequences
Petter Holme. Network reachability of real-world con- tact sequences. Physical Review E—Statistical, Non- linear, and Soft Matter Physics, 71(4):046119, 2005
2005
-
[18]
Epidemiologically Optimal Static Net- works from Temporal Network Data
Petter Holme. Epidemiologically Optimal Static Net- works from Temporal Network Data. PLoS Comput. Biol., 9(7):e1003142, 2013
2013
-
[19]
Temporal networks
Petter Holme and Jari Saram¨ aki. Temporal networks. Physics reports, 519(3):97–125, 2012
2012
-
[20]
What’s in a crowd? analysis of face-to-face behavioral networks
Lorenzo Isella et al. What’s in a crowd? analysis of face-to-face behavioral networks. Journal of Theoreti- cal Biology, 271(1):166–180, 2011
2011
-
[21]
Con- nectivity and inference problems for temporal net- works
David Kempe, Jon Kleinberg, and Amit Kumar. Con- nectivity and inference problems for temporal net- works. In Proceedings of the thirty-second annual ACM symposium on Theory of computing, pages 504–513, 2000
2000
-
[22]
Multi- scale analysis of spreading in a large communication network
Mikko Kivel¨ a, Raj Kumar Pan, Kimmo Kaski, J´ anos Kert´ esz, Jari Saram¨ aki, and M´ arton Karsai. Multi- scale analysis of spreading in a large communication network. Journal of Statistical Mechanics: Theory and Experiment, 2012(03):P03005, 2012
2012
-
[23]
Temporal motifs
Lauri Kovanen, M´ arton Karsai, Kimmo Kaski, J´ anos Kert´ esz, and Jari Saram¨ aki. Temporal motifs. In Temporal Networks, pages 119–133. Springer, 2013
2013
-
[24]
KONECT – The Koblenz Network Collection
J´ erˆ ome Kunegis. KONECT – The Koblenz Network Collection. In Proc. Int. Conf. on World Wide Web Companion, pages 1343–1350, 2013
2013
-
[25]
9 From networks to optimal higher-order models of com- plex systems
Renaud Lambiotte, Martin Rosvall, and Ingo Scholtes. 9 From networks to optimal higher-order models of com- plex systems. Nature physics, 15(4):313–320, 2019
2019
-
[26]
SNAP Datasets: Stanford large network dataset collection
Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. http:// snap.stanford.edu/data, June 2014
2014
-
[27]
The fundamental advantages of temporal networks
Aming Li, Sean P Cornelius, Y-Y Liu, Long Wang, and A-L Barab´ asi. The fundamental advantages of temporal networks. Science, 358(6366):1042–1046, 2017
2017
-
[28]
Erdem Sarıy¨ uce
Penghang Liu and A. Erdem Sarıy¨ uce. Using Motif Transitions for Temporal Graph Generation. In 29th ACM SIGKDD, pages 1501–1511, 2023
2023
-
[29]
Dynamic Erd¨ os-R´ enyi Graphs
Michel Mandjes, Nicos Starreveld, Ren´ e Bekker, and Peter Spreij. Dynamic Erd¨ os-R´ enyi Graphs. InCom- puting and Software Science: State of the Art and Per- spectives, pages 123–140. Springer, 2019
2019
-
[30]
Brendan D. McKay. Practical graph isomorphism. online, 1981
1981
-
[31]
Graph metrics for temporal networks
Vincenzo Nicosia, John Tang, Cecilia Mascolo, Mirco Musolesi, et al. Graph metrics for temporal networks. Temporal networks, pages 15–40, 2013
2013
-
[32]
T. Opsahl. Triadic closure in two-mode networks: Redefining the global and local clustering coefficients. Social Networks, 2011
2011
-
[33]
Motifs in temporal networks
Ashwin Paranjape, Austin R Benson, and Jure Leskovec. Motifs in temporal networks. In ACM WSDM conference, pages 601–610, 2017
2017
-
[34]
Faster and generalized temporal triangle counting, via degeneracy ordering
Noujan Pashanasangi and C Seshadhri. Faster and generalized temporal triangle counting, via degeneracy ordering. In 27th ACM SIGKDD, pages 1319–1328, 2021
2021
-
[35]
Perra, B
N. Perra, B. Gon¸ calves, R. Pastor-Satorras, and A. Vespignani. Activity driven modeling of time vary- ing networks. Sci Rep, 2(1):469, 2012
2012
-
[36]
Analytical Models for Motifs in Temporal Networks
Alexandra Porter, Baharan Mirzasoleiman, and Jure Leskovec. Analytical Models for Motifs in Temporal Networks. In Companion Proceedings of the Web Conference 2022, pages 903–909, 2022-08-16
2022
-
[37]
Structural control- lability of temporal networks
M´ arton P´ osfai and Philipp H¨ ovel. Structural control- lability of temporal networks. New Journal of Physics, 16(12):123055, 2014
2014
-
[38]
Jennifer JH et. al. Reynolds. Raccoon contact networks predict seasonal susceptibility to rabies outbreaks and limitations of vaccination. Journal of Animal Ecology, 84(6):1720–1731, 2015
2015
-
[39]
Rossi and Nesreen K
Ryan A. Rossi and Nesreen K. Ahmed. The network data repository with interactive graph analytics and visualization. In AAAI, 2015
2015
-
[41]
Wikipedia talk (eo) network dataset – KONECT
Jun Sun, J´ erˆ ome Kunegis, and Steffen Staab. Wikipedia talk (eo) network dataset – KONECT. https://zenodo.org/record/49561/files/ wiki-talk-dataset.tar.gz , January 2018
2018
-
[42]
Contrasting effects of strong ties on sir and sis processes in temporal networks
Kaiyuan Sun, Andrea Baronchelli, and Nicola Perra. Contrasting effects of strong ties on sir and sis processes in temporal networks. The European Physical Journal B, 88:1–8, 2015
2015
-
[43]
Cooperative investment in public goods is kin directed in communal nests of social birds
Rene van Dijk et al. Cooperative investment in public goods is kin directed in communal nests of social birds. Ecology letters, 17(9):1141–1148, 2014
2014
-
[44]
The reduction of a graph to canonical form and the algebra which appears therein
Boris Weisfeiler and Andrei Leman. The reduction of a graph to canonical form and the algebra which appears therein. nti, Series, 2(9):12–16, 1968
1968
-
[45]
Xu and Alfred O
Kevin S. Xu and Alfred O. Hero. Dynamic Stochas- tic Blockmodels for Time-Evolving Social Networks. IEEE JSTSP, 8(4):552–562, 2014
2014
-
[46]
causal completion
Xiao Zhang, Cristopher Moore, and Mark E. J. New- man. Random graph models for dynamic networks. European Physical Journal B, 90(10):200, 2017. A Appendix A.1 Additional Definitions Definition A.1. Mathematically, we may define the causal-tree (out-unraveling) of temporal node...
2017
Reviewed August 10, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.