Quality Measures for Dynamic Graph Generative Models
Authors: Ryien Hosseini
Filippo Simini
Venkatram Vishwanath
Rebecca Willett
Henry Hoffmann
Venue: ICLR 2025 Spotlight (2025)
Keywords: generative models
dynamic graphs
evaluation metrics
Primary area: learning on graphs and other geometries & topologies
TL;DR: We introduce a novel metric leveraging random projections to evaluate generative models for dynamic graphs.

Abstract: Deep generative models have recently achieved significant success in modeling graph data, including dynamic graphs, where topology and features evolve over time. However, unlike in vision and natural language domains, evaluating generative models for dynamic graphs is challenging due to the difficulty of visualizing their output, making quantitative metrics essential. In this work, we develop a new quality metric for evaluating generative models of dynamic graphs. Current metrics for dynamic graphs typically involve discretizing the continuous-evolution of graphs into static snapshots and then applying conventional graph similarity measures. This approach has several limitations: (a) it models temporally related events as i.i.d. samples, failing to capture the non-uniform evolution of dynamic graphs; (b) it lacks a unified measure that is sensitive to both features and topology; (c) it fails to provide a scalar metric, requiring multiple metrics without clear superiority; and (d) it requires explicitly instantiating each static snapshot, leading to impractical runtime demands that hinder evaluation at scale. We propose a novel metric based on the Johnson-Lindenstrauss lemma, applying random projections directly to dynamic graph data. This results in an expressive, scalar, and application-agnostic measure of dynamic graph similarity that overcomes the limitations of traditional methods. We also provide a comprehensive empirical evaluation of metrics for continuous-time dynamic graphs, demonstrating the effectiveness of our approach compared to existing methods. Our implementation is available at https://github.com/ryienh/jl-metric.

Published as a conference paper at ICLR 2025
QUALITY MEASURES FOR DYNAMIC GRAPH GENERATIVE MODELS
Ryien Hosseini', Filipppo Simini?, Venkatram Vishwanath', Rebecca Willett 33.4, Henry Hoffmann'
Deppartment of Computer Science. University of Chicago
21 "Leadership Computing Facility, Argonne National Laboratory
3 DDeaarment of Statistics, University of Chicago
4 NSF-Simonn National Institute for Theory and Mathematics in Biology (ryien, wi willert, hankho fankhoffmann quchi www.wchwiccccocoooocccoooooooo edu, {fsimini, venkat) @anl gov
ABSTRACT
Deep generative models have recently achieved significant success in modeling graph data, including dynamic graphs, where topology and features evolve over time. However, unlike in vision and natural language domains, evaluating gener- ative models for dynamic graphs is challenging due to the difficulty of visualizing their output, making quantitative metrics essential. In this work, we develop new quality metric for evaluating generative models of dynamic graphs. Current met- ries for dynamic graphs typically involve discretizing the continuous-evolutin of graphs into static snapshots and then applying conventional graph similarity measures. This approach has several limitations:
(a) models temporally re- lated events as i.i.d. samples, failing to capture the non-uniform evolution of dy- namic graphs; (b) it lacks a unified measure that is sensitive to both features and topology; (c) it fails to provide a scalar metric, requiring multiple metrics without clear superiority; and (d) it requires explicitly instantiating each static snapshot, leading to impractical runtime demands that hinder evaluation at scale. We pro- pose novel metric based on the folnson-Lindenstraat. lemma, applying random projections directly to dynamic graph data. This results in an expressive, scalar, and application-agnostic measure of dynamic graph similarity that overcomes the limitations of traditional methods. We also provide comprehensive empirical evaluation metrics for continuous-tin time dynamic graphs, demonstrating the ef- fectiveness of our approach compared to existing methods. Our implementation is available at hhttp://iitua.ccm//reeen///innnt
INTRODUCTION
Recent research in the generative graph domain has increasingly focused on dynamic graphs, or graphs whose topologies and features change over time. Dynamic graph generation has applications
in diverse areas, including social network analysis (Patel et al,, 2018 Aldhaheri & Lee| (017)). biology (Mathur & Chakka 2020 Choudhury & Chowdhury 2018), and financial fraud detection (Rajput& & Singh [022 Wang et al. 2021). Unlike image or natural language data, graph data can be challenging visualize, making subjective evaluation of generative samples difficult. Consequently, quality metrics for assessing these generative models are vitally important.
Current metries for dynamic graph generative models (DGGMs) generally rely on computing (static) graph statistics, such as node degree, number of connected components, or edge entropy, and aggre- gating them in a way that facilitates scalar comparison between synthetically generated and ground truth graphs. These metrics can be can be categorized into discrete and continuous. Discrete metrics treat a dynamic graph as a series of static graph snapshots, first calculating static graph statistics for each snapshot and then aggregating these values using summary statistic, such mean, or, more rigorously, a distance metric for high-dimensional distributions such as Maximum Mean Discrep- ancy (MMD) (Gretton et al., 2006). Such a method treats each snapshot of the evolving graph as independently and identically distributed (i.id.) and thus fails to capture the temporal dependencies often present in real world graphs (Sizemore & Bassett 2018). Despite this limitation, we find that

---

Published as a conference paper at ICLR 2025
Continuous graph discrete metrics are commonly used in the DGGM literature (See Section 2.2
metrics attempt to remedy this issue by directly incorporating temporal dependencies into the eval- uation process, such as by measuring the rate of change of graph attributes over time (Sizemore & Bassett 2018 Nicosia et al. 2013). However, both discrete and continuous approaches suffer from the topological properties of graphs, neglecting the equally important evolution of node and edge features. While standard statistical methods such as Jensen-Shannon Divergence (Fuglede & Topsoe, 2004) can measure the fidelity of generated fea- tures to the ground truth, capturing dependencies both between individual features and between feature evolution and topology- remannss non-trive non-trivial, yet essential because these dependencies are precisely what make dynamic graphs interesting and important. Second, these topological metrics depend on a variety of graph statistics, making the evaluation of DGGMs challenging: The rank- ing of generative models can vary depending on the specific statistic used, and there is no clear, application sorioondddmm-i--gag -annosicc method for determining which metric should take precedence. Finally, since most of these metrics require explicit construction of graph snapshots at each interaction time, their memory and runtime demands can quickly become impractical at scale.
limitations: First, these metrics focus exclusively
To remedy similar issues in other domains, untrained neural networks have recently been used in image generative model evaluation (Xu et al. 2018). Naeem et al.) (020) and static graph information extraction (Kipf & Welling, 6b1 Morris at. | (209)) Building on these advancements, [Thomsson et al. 2022 introduces the use of such a random network as a viable approach for generative model evaluation in the static graph domain. They demonstrate that a random graph neural network can be used as feature extractor to embed synthetic and ground truth graphs. These embeddings are then compared using standard distance metries such as Fréchet Distance (Heusel et al. 2017b) or MMD in order to produce a scalar metric. Though this work stops short of theorizing why such a method may be reasonable, they show empirically that these neural network- metrics effectively capture both graph topology and features, yielding unified scalar score. However, because this approach is designed for static graphs, it does not account for the temporal evolution crucial to dynamic graphs.
Inspired by this work in the image and static graph domain, we develop similar approach for con- tinuous time dynamic graphs (CTDGs). Specifically. we first argue that the success of random net- works as feature extractors may be due to the famed Lindenstrauss) 1984), which proves that data transformation via random linear maps approximately preserves similarity with high probability. Leveraging this insight, introduce novel DGGM metric by combining random feature extraction via the JL lemma with standard vector similarity measures. Another major contribution of this work is the first comprehensive empirical evaluation of DGGM metrics. Through extensive experiments, we assess the metrics' ability to meet key prop- erties established as essential for generative metries (Thompson et al. 2022 Xu et al., 2018): fidelity diversity, sample efficiency, and computational efficiency. Finally, we show that our proposed metric addresses limitations of existing methods, providing a more robust solution for evaluating DGGMs.
(JL) lemma (Johnson &
2 BACKGROUND AND RELATED WORK
The evaluation of generative models in terms of their alignment to the training distribution can be classified into two categories: likelihood-based methods (Heusel al. 2017b) and sample-based methods (Theis et al. 2015). Likelihood- based methods are often intractable (Theis et al. 2015
including for autoregressive graph generative models (Chen et al. 202T] Thompson et 2022
Therefore, we follow recent analogous work in the static graph domain by Thompson et al. 2022 and focus on sample-based methods. Specifically, sample- based metrics estimate a distance p between real and synthetic distributions P. and Pa using empirical samples S, {x[ ...,...... x
P. and Sy {x{,... } Pa 0 Thus, we have the distance estimator p(Sg S,) R p( Pt). Here, functioo descriptor x; is Teature vector that characterizes a single sample. Next, we turn to graph representation and demonstrate how such sample-based measures can be applied to dynamic graphs.
2.1 CONTINUOUS TIME DYNAMIC GRAPHS
Early work in dynamic graph generation focused on learning distributions over discrete-time dy- namic graphs (DTDGs). A DTDG consists of a sequence static graphs which are equally spaced
For ease of comparison, we adopt notation consistent with Thompson et al. 2022 wherever possible.
2

---

Published as a conference paper at ICLR 2025
in time. While DTDGs useful in applications where data is captured at regular time intervals Kazemi 2022). contimuous time dynamic graphs (CTDGs) generalize DTDGs, offering greater flexibility and efficiency. The literature has thus progressively shifted towards CTDG generation due to their ability to capture temporal dependencies more accurately and to handle data with irregular time intervals. This work concentrates as a sequence of timestamped event:] where each event is a change in graph topology (c.g., node or edge creation or deletion) or change in features. Formally, given initial graph state 9o, set of nodes V = {l..... 2 and sequence length k our CTDG sequence is:
metrics for evaluating CTDGs. A CTDG is represented
g =((())), c(L)), where c(4)) (sre, dsl, lis dst.)
Each event E 9 parameterized by timestamp i, is characterized by source and destination nodes of the event sre, dsl E V and @sra,ss(44)) a directed edge between sre and dsl at time 4 and that is represented by its feature vector. Thus, unlike DTDGs,, an evolving graph with k events can be compactly represented with sequence length @([+:). ) An induced static graph, or static snapshot, G at t can be explicitly computed by sequentially updating Go with events up to time T. Thus, given temporal resolution & we can discretize G" as Gliserete = =g(0))
g(o), (g(0),g(" GiL////////
Most generative models for CTDGs, including the aforementioned baselines, are trained on a single ground-truth graph consisting of many events. Implicitly, these methods assume that the covariance between events decays rapidly as the time interval between them increases and their joint probability distribution does not change when all the events are shifted in time, akin to the properties of wide- sense stationary process. This assumption allows models to treat different temporal segments of the CTDG as approximately independent, enabling pattern extraction and generalization from single graph. For consistency with existing literature, our empirical evaluation focuses on a model's ability to measure similarity between a generated and ground-truth CTDG in this single graph, many interactions setting. However, our methodology is sufficiently general to extend to settings involving multiple CTDGG. In such cases, we assume the different CTDGs are i.i.d., allowing for straightforward aggregation of the scalar metric across graphs using simple distance measures like MMD. This flexibility ensures that our metric can also be used to compare sets of dynamic graphs.
When using sample-based metrics, the goal is to create a function descriptor for each event or snapshot in the CTDG, forming an empirical sample S = (x1,..., X²). Individual events c(t) E g or induced static graphs /*/ E galiserete are analogous to graphs in the static graph domain. Unlike
static graphs, where each graph (and thus each x;) is assumed i.i.d., our function descriptor x, or distance estimator أ must account for temporal dependencies between events or snapshots.
2.2 CURRENT METRICS FOR DGMMS
We now overview common choices for function descriptor and distance estimator p. To do so, we summarize metrics used for four popular CTDG generative models: TagGen (Zhou al. 2020). TIGGER (Gupta et al., 2022), Dymond (Zeno et al., 2021), and TG-GAN {Zhang et al.) 2021)
The most common choice of function descriptor x; is based on static graph topology. Specifically, the ground truth graph G. and the synthetic graph G. are discretized into a set of induced static graphs. Gdiscrese and Gaiscrese using the method described in Section 2.1 For each graph snapshot G E Gdiserete, scalar metrics such as average node degree, number of connected components, and edge entropy are calculated. Thus, S,. and Sy are sets of scalar values representing a specific static graph statistic. All aforementioned basclines evaluate using such static approaches. Such function descriptor choices may lack the expressiveness needed to capture continuous dynamic behavior (Sizemore & Bassett 2018). To address this, Dymond and TG-GAN incorporate additional metrics that attempt to capture temporal dependencies and finer-grained dynamics in the evolution of graph structures. Specifically, they develop so-called node behavior metrics wherein function descriptor x; is based on nodes V = (1,.... }} rather than induced static graphs. These function descriptors are calculated using classical statistical measures such as activity rate and degree distribution. A comprehensive summary and discussion of all graph statistics reviewed is provided in Appendix A
Events are also referred to observations contacts in the literature.
3

---

Published as a conference paper at ICLR 2025
As discussed above, given real and generated function descriptor sequences S, {xq...... ..... Xm, Pr and S =
~ Pg. we require distance estimator p(S S,) ~ p( P+). TagGen and TIGGER limit evaluation to graphs with the same number of snapshots and use mean and me- dian absolute error between S, and S.. Dymond and TG-GAN use Kolmo -Smrroo (KS-test) (Massey Jr T95T) and Maximum Mean Discrepancy (MMD) (Gretton al.. 2006), respectively. Critically, these choices of f assume an i.i.d. relationship between the function descriptors in S, and S, However, for the function descriptors described, this assumption is unlikely to hold, as temporal dependencies between snapshots are often present, challenging the validity of these estimators.
Additionally, the function descriptors found in the literature are limited graph topology and fail to incorporate node or edge features. As discussed in Section I] a wide range of distance measures, such as Jensen-Shannon divergence (Fuglede & Topsoe 2004), can be used to evaluate the fidelity of generated features. However, these measures are unable to capture dependencies between the topology and the evolution of features. Thus, current metrics are not expressive enough to model temporal dependencies, topological-featte world graphs. Without a method that can capture these complex relationships, existing approaches remain insufficient for fully assessing the sample quality of DGGMs.
interactions, and the intricate dynamies observed in real-
2.3 UNTRAINED NEURAL NETWORKS AS FEATURE EXTRACTORS
Recent work in the vision and static graph domains has sought to address similar issues in develop- ing metrics for evaluating generative models. Drawing inspiration from the use of pretrained con- volutional neural networks (CNNs) to derive function descriptors x, for sumple-based metrics (e.g., Binkowski et al. (2088;; |Heusel et al.] (2017a)), recent work (Xu et al. 2018; Naeem et al., 2020) explores applying untrained neural networks, or random networks, for the same task. They find that function descriptors derived from forward propaattin data through random CNN yield met- rics of comparable quality to those obtained from a trained CNN across several choices of distance estimator p. Similarly, Thompson et al. (202)) explores the use of random graph neural networks (GNNs) to produce metrics for static graph data, showing that this method provides more expressive and computationally efficient metries than those based on classical graph descriptors. In this work, we first investigate why these approaches work, hypothesizing a connection to orthogonal random projections, and then propose a new method for evaluating dynamic graphs based these insights.
2.4 SCORING GENERATIVE METRICS
major contribution of our work an empirical study of the quality of various sample-based metrics for CTDGs. Here, we enumerate the established attributes of good quality metric and detail how such attributes are measured for metrics in the vision and static graph domain. In Section we propose an approach for measuring these attributes for CTDGs.
An expressive metric should capture the fidelity of generated samples, meaning it can distinguish between empirical samples S, and S. drawn from different distributions, with the empirical distance measure و changing monotonically with the dissimilarity between the two data sets. Xu et al. (2018); O' et al. (202T): Thompson al. (2022) empirically study this property for images and static graphs using sensitivity analysis. In these studies, a reference sample S, and a generated sample S, are initially calculated from identical real-world datasets D, and Dz, Then, samples in D, are gradually replaced with data from a different distribution (e.g., random data or data from a generative model) and Sg is re-calculated, parameterizing Sg as S,(p) and Dy as Dg(p), where is the probability of real data replacement in D [Thompson et al. (2022) also explores edge perturbation static graphs, where edges are rewired with probability P. The metric response is then studied. Xu et al. (2018) does so subjectively. [O (rBaa et al. (2021) quantifies the response by reporting the Pearson correlation coefficient between p and p(S,, S. (p)). Recognizing that Pearson correlation favors linear relationships, [Thompson et al. (2022) instead reports the Spearman rank correlation coefficient. We adopt this approach and report Spearman rank correlation in our analysis.
An expressive metric should also capture the diversity of generated samples, ensuring that dataset D,, contains samples from different regions of the probability mass of reference distribution P,, rather than being confined to limited subset of it. This is particularly crucial in real-world scenarios where the underlying distribution is multi modal. In generative models, Xu et al. (2018) identifies two common failure points: (1) mode dropping, where some modes of P, are underrepresented or
4

---

Published as a conference paper at ICLR 2025
ignored by the generative model, and (2) mode collapse, where there is insufficient diversity within the modes. Thus, a quality metric should be sensitive to such phenomena. To detect such issues, Xu et al. (2018) and and Thompson et al. (2022) again employ sensitivity analysis. Data is first clustered into k modes using k-means or offinity propagation Frey & Dueck (2007). Starting with identical D, and Dg samples in Dg are progressively replaced with their cluster centers to measure mode collapse. Thus, we can again calculate S, and S,(p)) from D, and (p), where indicates the probability of replaced data in Dy. To simulate mode dropping, modes are gradually removed from Da (p) and data from other modes is duplicated to keep (p)) and thus (p)), constant. The metric's 's response is again quantified using the Spearman rank correlation between p and p(S,, (y))).
A quality metric should also be sample efficient. That is, it should be able to discriminate be- tween distinct distributions P. and Pg even when X = min([Dr], (Pyl) is small. Thompson et al. (2022) evaluates the sample efficiency of metric by creating two disjoint subsets Dr and DD from real-world data D,., and one subset D' from random static graph distribution Pg. with [D]] = [D"] = [D']= = À and therefore corresponding function descriptors |S|] | = S The sample efficiency measured as the smallest À for which the metric (( S.)) < P(S) S indicating the number of samples needed for the metric to discrimate between P. and Pg.
Finally, quality metric must be computationally efficient to allow for repeated use during tasks like model training and hyperparameter optimization. Computational efficiency is typically assessed by measuring runtime performance on standard computing hardware.
A JOHNSON-LINDEASTRAIE APPROACH TO VALIDATING DGGMS
Though the random network-based metrics described in Section 2.3 have found widespread use in the image and static graph domains, these works stop short of explaining why such methods may be effective. We argue that their success may be partially attributed to the famed Johnson- Lindenssssssss (JL) lemma (Johnson & Lindenstrauss) 1984 Dasgupta & Gupta 2003), which posits that random orthogonal linear projections approximately preserve data similarity with high probability. Notably, under mild conditions randomly initialized fully connected neural network (FCNN) layer with identity activation can be viewed as a direct instance of a JL projection (Nachum et al. 202I). Moreover, recent studies on neural network initialization have shown that FCNNs with ReLU acti- vation and convolutional neural networks (CNNs) modify the JL result in a predictable way, where data similarity is preserved but scaled by derivable contraction factor (Daniely et al., 2016 Giryes jet al. 2016) Nachum et al., 2021). This theoretical foundation may explain the success of random CNN networks feature extractors in the image domain. While no formal theoretical extension of the JL. lemma to the static graph domain has been established, several classes of graph neural networks (GNNs) (e.g., Defferrard et al. (2016); Kipf & Welling (2016a); Wu et al. (2019) have been rigorously shown to generalize the convolution operation to non-Euclidean structures. Given that the core principle of the JL lemma applies to preserving distances under random projection, we posit that random GNN layers can preserve graph topology and features in manner analogous to how CNNs preserve data similarity in Euclidean space. This suggests a plausible extension of the lemma's 's applicability to the graph domain, where the effectiveness of random GNNs as feature extractors may stem from the same underlying principles.
Notably, the distance preservation property, and therefore embedding quality, of the Johnson- Lindenstrauss lemma does not depend on the dimensionality of the original data, leading to widespread use in dimensionality reduction tasks (Bingham & Mannila 2001 Choromanski et al.) 2017]. wherein data in N embedded into a lower-dimensional space IR"", < N. Namely, the lemma states that given distortion factor 0 < < dataset X {ai, a2, ......... ......., agg 1gg,0n a, E R,, and embedding dimensionality 8(In e)2, there is linear map f N R such that:
(1 - e]lla 6112 < (I - f(b])2 < e)+a) aa bll2
(2)
for all a, b E X, where early proofs of the lemma show that linear map f : R + IR" can be a random orthogonal projection from R subspace T....
We argue that this lack of dependence embedding quality on N is a crucial characteristic that makes
embeddings effective method for transforming the veriable-length node interactions in a CTDG (Equation ! into a dineeniimnsio vector space. Unlike traditional applications of the JI. lemma, where the goal is to reduce dimensionality, key insight in our work
5

---

Published as a conference paper at ICLR 2025
to use it to transform data of varying dimensionality into consistent dimensional representation. We now turn our attention to creating a Johnson- Liinsson-Lieddentttausss based metric for CTDGs.
construct an alternative representation I at time as sequence of nodes V {vi...., Vzy. where each node is characterized by the time-ordered concatenation of events it participated in:
Starting from our CTDG representation in Equation L
(((4)))(((2))...1(())))) ((2(mm))))
where my is the number of events involving node j up to time т. Since each v, E V only contains events involving node j. the node identifier (either src or dst) is redundant, and simplify the event representation e(t,) from Equation [ to ö(t.), dropping the node identifier and capturing only the timestamp and the associated event features
t(4.) = (Li, (ine,da(44))
As nodes generally participate in different numbers of interactions, the resulting vectors vj will have variable lengths, |yyl m |2(4))
However, since the JL embedding quality is agnostic to vector length, we can apply random pro- jections to map each V, into consistent-dimensionaal space I". To achieve this, we instantiate a random projection matrix W.Mxx, where M = ((x))( We then apply WMMx* to each vec- tor Vj. adjusting for variable lengths by ignoring unused rows of the matrix where necessary. This process yields linensiinniiinall function descriptors for each node, {XI....,X, where each x; characterizes node V, and together they provide a representation for G.
Finally, we note that different CTDGs will generally have different numbers of nodes, resulting in varying number of function descriptors. To facilitate comparison between CTDGs, apply an additional transformation that maps the set of node embeddings into a consistent dimensional space. Specifically, for a of CTDGs GI...., Ik. each with 2, nodes, we instantiate a second random projection matrix 2 where Z max(21 11, =*) is the maximum number of nodes across the CTDGs, and is the desired number of function descriptors for each Gi- This transformation yields a consistent representation of each G as 9 = {xI....,x.) ,,), where each x, E R". This represen- tation now has consistent dimensionality G. E m for all GI.... Gt. Unlike the sequences of function descriptors discussed in Section 2 which each represents individual graph snapshots, G; is matrix representation of the entirety G. Thus, GI...., , Gu can compared directly using familiar notions of similarity such as cosine distance, i.e. given any pair G, P. and Gg Pg. we have:
(gy, G.)F 10y1l=119H11
p(rr Pa) RJ ((
where ||:1e the Frobenius norm and ( p the Frobenious inner product. Due the implicit assumption that the correlation between events decreases rapidly with the time between the events (Section 2.1). this distance estimate between distributions can be accurate even with single sample from each distribution, as is common in the CTDG literature.
While early works using LinnesstLnndesssauuss transforms employed random orthogonal projec- tion matrices, our approach may use structured random matrix (SRM) discussed by Choromanski ct al. (017)), which combines normalized Hadamard matrix with a random Rademacher diagonal matrix (Appendix B for details). This method has been shown to outperform standard orthogonal projection matrices in dimensionality reduction tasks. By using such SRMs for W,M and W we also achieve significant computational and memory benefits: we avoid explicitly instantiating the matrices, reducing storage requirements to O(M) and O(Z) for W1 and W2, respectively. More- over, matrix- vector multiplication can be performed O(M log M) and ( log Z) time, without additional memory overhead. This improved complexity is particularly advantageous when dealing with data of varying dimensionality, such as cases where max((v,)) > mean([v)),
This JL-metric addresses the shortcomings of classical CTDG metrics described in Section 2.2
Assumption of i.i.d. relationships: Many classical metrics assume an i.i.d. relationship between graph snapshots, which we have demonstrated is not true in practice. In contrast, our method makes
In practice, we also normalize timestamps and event features using standard techniques. See Appendix

---

Published as a conference paper at ICLR 2025
no such assumption. The transformation W/ linearly combines the events that constitute vi, effectively capturing dependencies between events and ensuring that interactions within each node are not treated as independent. A similar effect is achieved by the transformation W2 which combines node-level descriptors to produce the final metric, preserving dependencies across nodes.
Joint modeling of topology and features: Current metrics typically fail to jointly model topological and feature properties of the graph. In contrast, the metrie produced by our method is sensitive to both topologiaal and feature changes, as is discussed above and demonstrated in our experiments.
Unified metric: Classical metrics often sensitive to only specific graph properties, resulting in mul- tiple metrics with no clear hierarchy for choosing the best model when conflicts arise. Conversely, method provides single scalar metric, offering more comprehensive assessment.
Many classical metrics require explicit instantiation of discrete graph snapshots, resulting in impractical memory and runtime demands for large graphs. In contrast, our method requires only O(M + 2) memory and O(max M, 2) log max M, 2)) runtime.
Efficiency in memory and runtime:
4 EXPERIMENTS
We now turn to an empirical evaluation of CTDG metrics, comparing several existing metrics with proposed
metric (JL-Metric). The comparison focuses on com- mon desiderata of generative metries outlined in Section 2.4 fidelity, diversity, sample efficiency, and computational efficiency. We follow the experimental framework of studies for metrics in the image (Xu al. 2018) and static graph [Tommson et al. 2022 domains, adapting them for CTDGs.
Metric Baselines: In addition to the JL-Metric introduced in Section we evaluate the following topological commonly used function descriptors x; from Section 2.2 average node degree, largest connected component (L.CC), number of components (NC), power law exponent (PLE) (static met- rics), and average node activity rate (node behavior metric). These metrics are computed using standard definitions, which are also provided in Appendix A A more comprehensive review of function descriptors and motivation for selecting these descriptors can also be found in Appendix A As described in Section 2.2 static metrics are evaluated for a specific temporal resolution. We evaluate each static metric at the Nyquist rate, the minimum temporal resolution required to create snapshots without information loss. In practice, these metries can be evaluated at lower resolution, but this often comes at the cost of reduced accuracy and loss of important temporal details.
For choice of distance estimator Ó. we use Maximum Mean Discrepancy (MMD) (Gretton et al, 2006) and Kolmogorov-Smiroov (KS) (Massey Jr| 1951) for all metric baselines. Cosine distance is used for our JL-Metric, as motivated in Section 3 Lastly, we evaluate feature-based metrics, where features are compared independently of topology, using Kullback-Leibler divergence (Kullback) 1951], Tensen-Shannow divergence (Fuglede & Topsoe 2004), as well as KS and MMD.
Datasets: We evaluate each metric on four real-world datasets and one synthetic dataset. The real- world datasets are adapted from user interactions on online platforms: Reddit, Wikipedia, LastFM, and MOOC. We use subset of these data (details in Appendix C). which were originally introduced by Jodie (Kumar et al. 2019) and have become standard CTDG benchmarks. We note that the LastFM dataset does not include event features. The synthetic dataset, Ggrid. is a grid-like graph where each node is connected to its neighboring nodes at regular time intervals t = (.,...., tn... The event feature esc,,s((t.) is heuristically generated function of the timestamp and the source and destination node IDs, i.e., csc, design explicitly introduces temporal and topological dependencies to the event features.
h(sre, dst, tt), with h detailed in Appendix C This
Experimental Setup: Building on analogous work from the image and static graph domains (see Section 2.4), we evaluate each metric's 's ability to capture fidelity (Section 4. and diversity (Section 4.2) using sensitivity analysis. In each experiment, we compare real CTDG G, ~ P, with a perturbed CTDG G2 ~ Pg. the latter serving as a proxy for a DGGM-
graph. Initially, G. = Gg, so P. Pg. meaning two identical copies of the real CTDG are instantiated. The events in Gy are then subjected to increasing perturbation probability p E [0. 1], quantifying the dissimilarity between P, and P,.. We compare G, and (p) for several p, computing descriptors S, and (p) for each graph and assessing each metric's 's response by calculating the Spearman rank correlation between metric score j(S,, Sy (p)) and perturbation probability p.
7

---

Published as a conference paper at ICLR 2025
Fest. Distance (o, (hv)
Rost. Distancc (MAN))
Node Degree (MND)
Node Degree IKS)
(5)
Feat. Distamce (KS)
Activiyy Rate
LCC (KS)
NC NICIMMD)
(SS)
PLE (MWD)
Metric
LCC
1.00
0.75
Correlation
0.50
0.25
0.00
-0.50
Edge Rewiring
1.00
0.75
Correlation
0.50
0.25
0.00
-0.50
Time Perturbation
0.75
0.50
Correlation
0.25
0.00
0.25
Event Permutation
1.00
Correlation
0.50
0.25
0.00
-0.25
-0.50
Mode Dropping
1.00
0.75
Correlation
0.50
0.00
-0.25
-0.50
Mode Collapse
Figure 1: Distributions of Spearman rank correlations across all datasets and random seeds. Cor- relation measured between metric response ((G,,Gg()) and perturbation probability Each subplot corresponds to distinct perturbation scheme, outlined in Sections 4.1 and 4.2 White lines represent median values, and thick black bars indicate the interquartile range. For classical metrics, colors mapped based the function descriptor, independent of the distance estimator.
8

---

Published as a conference paper at ICLR 2025
The experiments for fidelity and diversity follow this common setup, differing only in the types of perturbation applied. Each metric is evaluated across 10 random seeds, which affect both the weights Wi and W2 in the JL-based metries and the applied perturbations. We report the average rank correlation across all 10 seeds and datasets, with dataset-specific results provided in Appendix B Additionally, the hyperparameters and for the J[.-based metric selected via grid search, as detailed in Appendix [ The experiments on sample and computational efficiency (Section 4.3) are not evaluated via sensitivity analysis; their setup detailed in the respective section.
4.1 MEASURING FIDELITY
The primary goal of a metric is to assess fidelity, or how closely generated Gg resembles the ground truth G.. To evaluate a metric's 's fidelity, we apply three perturbations: edge rewiring, where edges are rewired to new destination node with probability p. altering the topology; time perturbation, where, with probability p. a timestamp t; is replaced by a uniformly selected one tand ~ Uni f++1), altering temporal relationships while preserving event order; and event permutation,, where event feature dszc (1+) is replaced by that of another randomly selected event with probability p. modify- ing the feature-topology relationship but preserving the features themselves.
Results: Figure (top 3 rows) presents violin plots showing the distributions of correlations across all datasets and random seeds, for all tested metrics. Median values are summarized in Table [] These results show that commonly used topology-based metrics are comparatively sensitive to edge rewiring, which only alters graph topology. However, they are less sensitive to time perturbation, and show no sensitivity to feature perturbation.
In the edge rewiring task, the quality of classical metries vary significantly depending on the function descriptor and distance measure. For example, using activity rate with KS distance outperforms MMD, as KS is more sensitive to large deviations cumulative distributions. In contrast, MMD smooths out these localized shifts, reducing sensitivity. The NC descriptor performs comparatively poorly across all measures, as the statistic often remains unchanged when edges are rewired.
In the time perturbation task, the JL-Metric outperforms all baseline metrics. Many traditional metries assume i.idd relationships between function descriptors, limiting their ability to capture temporal changes unless these are indirectly reflected through topological shifts. The JL-Metric, by contrast, is more expressive, capturing both temporal and topological changes directly.
In the event perturbation task, the JL-Metric is the only metric sensitive to the perturbation. This is expected: Event permutation preserves topology, rendering classical metrics ineffective. Addi- tionally, because the perturbation alters feature-topology relationships while keeping the features themselves unchanged, feature-basee based baselines fail to detect differences, as they are insensitive to feature order. In contrast, the JL.-Metric captures dependencies between features and topology.
is important to note that feature- metrics are inherently insensitive to changes in topology, just topological metrics are insensitive changes in features. However, the JL--Metric shows robust sensitivity to both types of perturbation. Unlike traditional methods, our approach is agnostic specific topological details and consistently performs well across all three types of perturbations.
4.2 MEASURING DIVERSITY
We assess each metric's ability to capture the diversity of generated data by focusing on the failure modes outlined in Section 2.4, mode droppiong and mode collapse.
To simulate these phenomena, we first train a Temporal Graph Network (TGN) (Rossi et al. 2020). a widely used discriminative model for CTDGs, on each dataset 9, (see Appendix [ for training details). The trained TGN includes memory bank that contains learned embeddings for each node. We apply affinity propagation (Frey & Dueck 2007) to cluster these node embeddings into k modes.
For mode dropping, we generate perturbed graph G3(p) by removing modes with probability p from Gr and replacing events c(t,) involving those modes with randomly selected events from the remaining modes. Specifically, for each event c(t,) (src, dst, t,, Care (t,)) (Equation Dp. if either the source node (sre) or the destination node (dst) belongs to a mode that is being removed, the event is replaced with randomly selected event from nodes in modes that are not dropped.

---

Published as a conference paper at ICLR 2025
Table I:
Summary of metric performance across experiments. Values represent median standard
enror, with error bars omitted from first five columns in favor of distributional details in Figure 1
Perturbation Correlation (Median Spearman Score)
Sample Efficiency (min. events)
Comp-
Metric
Efficiency
Edge Rewiring
Time Perturbation
Event Permulation
Mode Drupping
Mode Collapse
(s/100 events)
Topological Metrics
Node Degree (KS)
0.976
0.903
0.794
0.963
3
8.41 + 0.51
Node Degree (MMD)
1.000
0.927
0.733
1.000
3
8.56 + 0.35
LCC (KS)
0.976
0.830
0.818
5-1
LCC (MMD)
0.952
0.842
0.806
0.770
4=
10.08 1: 0.74
NC (KS)
0.915
0.830
0.718
0.927
3 1
10.25 1: 0.08
NC (MMD)
0.988
0.685
0,552
0.976
3 1
10.77
PLE (KS)
0.964
0.915
0.745
0,963
7=1
0.10
PLE (MMD)
0.976
0.830
0.685
0,976
8=1
10.03 + 0.21
Activity Rate (KS)
0.985
0.903
1,000
3
0.12 0.01 0.01
Activity Rate (MMD)
0.645
0.176
0,522
3 1
0.21 + 0.01
Feature Metries
Kullback-Leibler Div.
0.103
0.649
0.72 + 0.02
Bansen-Shanoon Div.
0.685
0.842
0.09 + 0.04
KS
0.488
0.713
0.54 0.04
MMD
0.286
0.494
0.82 + 0.05
JL-Metric (Ours)
0.976
0.944
0.988
0.915
0.988
3
1.05 0.09
For mode collapse, we construct Gy (p) by replacing randomly selected event c(t;) with the cluster centroid's event with probability p. In this process, nodes of c(t.)) are rewired those of the nearest mode centroid, and feature esre (4:) is replaced by the mean feature all events in that mode.
Figure I (bottom two rows) visualizes the distributions of correlations across all datasets and random seeds, with median correlations shown Table In the mode dropping experiment, many classical metries show suboptimal performance, with median correlations often below 0.80. However, certain metrics, such as activity rate (KS) and LCC, perform better, likely due to their ability to capture long-term temporal dependencies and global topological structure, respectively. These global perspectives are important for detecting subtle perturbations like mode dropping. The JL.-Metric consistently achieves high correlations across both experiments.
Results:
4.3 SAMPLE AND COMPUTATIONAL EFFICIENCY
To evaluate sample efficiency, we follow the approach described in Section 2.4 We let G¹, and G" be subsets of each real-world dataset and G be a subset of the Grid dataset. The sample efficiency results are summarized in Table Overall, all tested metrics demonstrate strong sample efficiency, consistent with results seen in the static graph domain (Thompson al., (022). However, topological metrics that rely on global features, such as LCC and PLE, exhibit comparatively lower sample efficiency. This outcome is intuitive, these global structures typically require larger number events to manifest in the induced static graph.
The final property we examine is computational efficiency. To provide practical comparisons, benchmark each metric's runtime across the entirety of each dataset, reporting results in seconds per 100 events, with hardware details in Appendix D Results, summarized in Table I, show that classical snapshot-based metrics are slower due to the need for explicit snapshot instantiation. In contrast, the activity rate and JL-Metric are much faster, as they avoid snapshot instantiation.
CONCLUSION
In this work, we introduced novel approach for evaluating generative models of dynamic graphs by applying
transformations directly to dynamic graph data. Our method addresses key limitations of traditional metrics, providing an efficient, unified, and scalar measure that is sensitive to changes in both graph topology and features. Through comprehensive empirical evaluation, we demonstrated its effectiveness in capturing the essential properties of dynamic graphs.
10

---

Published as a conference paper at ICLR 2025
REPRODUCIBILITY STATEMENT
We take several steps to ensure that our work is fully reproducible. The JL-metric algorithm is clearly defined in Section 3 with additional details in Appendix described, with mathematical definitions provided in Appendix A Experimental details, including hyperparameter search and the software and hardware used, are discussed in Appendix D We use Additionally, the supplementary
Baseline methods are fully
open source datasets with detailed descriptions in Appendix [ material includes an anonymized version of the code used for our experiments.
ACKNOWLEDGMENTS
This research used resources of the Argonne Leadership Computing Facility, U.S. Department of Energy (DOE) Office of Science user facility at Argonne National Laboratory and based on research supported by the U.S. DOE Office of Science-Advanced Scientific Computing Research Additional funding support comes from the National Science Foundation (CCF-211918) CNS-23131 13130 CCF-1822949 CNS-19561 180). RW gratefully acknowledges the support of NSF DMS- 2022100, DOE DE-SC0022232, the NSF-Simons National Institute for Theory and Mathematics in Biology (NITMB) through NSF (DMS-2235451) and Simons Foundation IMP-TMMS-00005330 and the Margot and Tom Pritzker Foundation.
Program, under Contract No. DE-AC02-00CHI1333
REFERENCES
Abdulrahman Aldhaheri and Jeongkyu Lee. Event detection large social media using temporal analysis. In 2017 IEEE 7th Annual Computing and Communication Workshop and Conference (CCWC), pp. 1-6. IEEE, 2017.
Ella Bingham and Heikki Mannila. Random projection in dimensionality reduction: applications to image and text data. In Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 245-250, 2001.
Mikolaj Binkowski, Danica J Sutherland, Michael Arbel, and Arthur Gretton, Demystifying mmd gans. arXiv preprint arXiv: 401, 2018.
Xiaohui Chen, Xu Han, Jiajing Hu, Francisco JR Ruiz, and Liping Liu. Order matters: Probabilistic modeling of node sequence for graph generation. arXiv preprint arXiv:2106.06189 2021.
Krzysztof M Choromanski, Mark Rowland, and Adrian Weller. The unreasonable effectiveness of structured random orthogonal embeddings. Advances in neural information processing systems, 30, 2017.
Anirban Dutta Choudhury and Ananda S Chowdhury. Change: Cardiac health analysis using graph eigenvalues. In 2018 40th Annual International Conference of the IEEE Engineering Medicine and Biology Society (EMBC), pp. 4025-4022 IEEE, 2018.
Amit Daniely, Roy Frostig, and Yoram Singer. Toward deeper understanding of neural networks: The power of initialization and dual view expressivity. Advances in neural information processing systems, 29, 2016.
Sanjoy Dasgupta and Anupam Gupta. An elementary proof of a theorem of johnson and linden- strauss. Random Structures & Algorithms, 22(1):60-65, 2003.
Michael Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. Advances neural information processing systems, 29, 2016.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint arXiv: 190:::9903002228 2019.
Brendan Frey and Delbert Dueck. Clustering by passing messages between data points. science, 315(5814)9972-976, 2007.
11

---

Published as a conference paper at ICLR 2025
Bent Fuglede and Flemming Topsoe. Jensen-shannon divergence and hilbert space embedding. In International symposium onInformation theory, 2004. ISIT 2004, Proceedings., pp. 31. IEEE, 2004.
Raja Giryes, Guillermo Sapiro, and Alex M Bronstein. Deep neural networks with random gaussian weights: A universal classification strategy? IEEE Transactions on Signal Processing, 64(13); 3444-3457, 2016.
Arthur Gretton, Karsten Borgwardt, Malte Rasch, Bernhard Schölkopf, and Alex Smola. A kernel method for the coo-sample-probler Advances in neural information processing systems, 19, 2006.
Shubham Gupta, Sahil Manchanda, Srikanta Bedathur, and Sayan Ranu. Tigger: Scalable generative modelling for temporal interaction graphs. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 6819-6828, 2022.
Aric Hagberg, Pieter Swart, and Daniel A Schult. Exploring network structure, dynamics, and function using networkx. Technical report, Los Alamos National Laboratory (LANL), Los Alamos, NM (United States), 2008.
Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. Gans trained by a two time-scale update rule converge to local nash equilibrium. Advances in neural information processing systems, 30, 2017a.
Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. Gans trained by a two time-scale update rule converge to local nash equilibrium. Advances in neural information processing systems, 30, 2017b.
William B Johnson and Joram Lindenstrauss. Extensions of lipschitz mapping into hilbert space. Contemporary mathematics, 26(189-206):32 1984.
Seyed Mehran Kazemi. Dynamic graph neural networks. Graph Neural Networks: Foundations, Frontiers, and Applications, pp. 323-349, 2022.
Thomas N Kipf and Max Welling. supersupe classification with graph convolutional net- 2016a.
works. arXiv preprint
Thomas N Kipf and Max Welling. Supi-supe classification with graph convolutional net- works. arXiv preprint arXiv: arXiv:1609.02907 2016b.
Solomon Kullback. Kullback-leibler divergence, 1951.
Srijan Kumar, Xikun Zhang, and Jure Leskovec. Predicting dynamic embedding trajectory in tem- poral interaction networks. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery data mining, pp. 1269-1278, 2019.
Frank J Massey Jr. The kolmogonov-smirnov test for goodness of fit. Journal of the American statistical Association, 46(253):68-78, 1951.
Priyanka Mathur and Vijay Kumar Chakka. Graph signal processing eeg signals for detection of epilepsy. In 2020 7th International Conference Signal Processing and Integrated Networks (SPIN), pp. 0-99-833. IEEE, 2020.
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 neural networks. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pp. 4602-4609, 2019.
Ido Nachum, Jan Hazla, Michael Gastpar, and Anatoly Khina. A johnson--lnndensrraus framework for randomly initialized cnns. arXiv preprint 1.Xi:22111.02155 2021.
Muhammad Ferjad Naeem, Seong Joon Oh, Youngjung Uh, Yunjey Choi, and Jacjun Yoo. Reliable fidelity and diversity metrics for generative models. In International Conference on Machine Learning, pp. 7176-7185. PMLR, 2020.
12

---

Published as a conference paper at ICLR 2025
Vincenzo Nicosia, John Tang, Cecilia Mascolo, Mirco Musolesi, Giovanni Russo, and Vito Latora. Graph metrics for temporal networks. Temporal networks, pp. 15-40, 2013.
Leslie O'Bray, Max Horn, Bastian Rieck, and Karsten Borgwardt. Evaluation metrics for graph generative models: Problems, pitfalls, and practical solutions. arXiv preprint 1rXiiv2106.01096 2021.
Hardik Patel, Pavlos Paraskevopoulos, and Matthias Renz. Geotegra: A system for the creation of knowledge graph based on social network data with geographical and temporal information. In 2018 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), pp. 617-620. IEEE, 2018.
S Patro. Normalization: preprocessing stage. arXiv preprint arXiv: 100.vv5503306422 2015.
Nitendra Rajput and Karamjit Singh. Temporal graph learning for financial world: Algorithms, scalability, explainability fairness. Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 4818-4819, 2022.
Emanuele Rossi, Ben Chamberlain, Fabrizio Frasca, Davide Eynard, Federico Monti, and Michael Bronstein. Temporal graph networks for deep learning on dynamic graphs. arXiv preprint arXiv:2006.10637, 2020.
Ryoma Sato. A survey on the expressive power of graph neural networks. arXiv preprint arXiv:2003.04078, 2020.
Ann E Sizemore and Danielle S Bassett. Dynamic graph metrics: Tutorial, toolbox, and tale. Neu- rolmage, 180:417-475 2018.
Lucas Theis, Aäron van den Oord, and Matthias Bethge. A note on the evaluation of generative models. arXiv preprint arXiv:1511.01844 2015.
Rylee Thompson, Boris Knyazev, Elahe Ghalebi, Jungtaek Kim, and Graham W Taylor. On evalua- tion metrics for graph generative models. arXiv preprint arXiv:2201.099% 2022.
Daixin Wang, Zhiqiang Zhang, Jun Zhou, Peng Cui, Jingli Fang, Quanhui Jia, Yanming Fang, and Yuan Qi. Temporal-awee aware graph neural network for credit risk prediction. In Proceedings of the 2021 SIAM International Conference on Data Mining (SDM), pp. 702-710. SIAM, 2021.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Sim- plifying graph convolutional networks. In International conference on machine learning, pp- 6861-6871. PMLR, 2019.
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanie Jegelka. How powerful graph neural networks? In International Conference on Learning Representations, 2019. URL https: //openrevien west:/formmidddryyoeette A5Kml
Qiantong Xu, Gao Huang, Yang Yuan, Chuan Guo, Yu Sun, Felix Wu, and Kilian Weinberger. An empirical study on evaluation metrics of generative adversarial networks. arXiv preprint (xXiv:/006.0775: 2018.
Giselle Zeno, Timothy La Fond, and Jennifer Neville. Dymond: Dynamic motif-nodes network generative model. In Proceedings of the Web Conference 2021, pp. pp. 718-729, 2021.
Liming Zhang, Liang Zhao, Shan Qin, Dieter Pfoser, and Chen Ling. Tg-gan: Continuous-time temporal graph deep generative models with time-validity constraints. In Proceedings of the Web Conference 2021, pp. 2104-2116. 2021.
Dawei Zhou, Lecheng Zheng, Jiawei Han, and Jingrui He. A data-driven graph generative model for temporal interaction networks. In Proceedings of the 26th ACM SIGKDD International Con- ference on Knowledge Discovery & Data Mining, pp. 401-411, 2020.
13

---

Published as a conference paper at ICLR 2025
A ADDITIONAL DETAILS ON CLASSICAL DGGM METRICS
Here, we overview the statistics used to compute function descriptor x; for the baseline generative models discussed in Section 2.2 of the main text: TagGen (Zhou al. 2020), TIGGER (Cupta et al. 2022), Dymond (Zeno et al, 2021). and TG-GAN (Zhang et al. 2021). J. As discussed Sec- tion 2.2 TagGen and TIGGER use only snapshot-based metrics while Dymond and TG-GAN use both snapshot-based and node behavior metrics. TagGen uses mean node degree, claw count, wedge count, power law exponent of degree distribution (PLE), largest connected component (LCC), and number of components (NC). TIGGER uses mean node degree, wedge count, triangle count, relative edge distribution entropy, global clustering coefficient, mean betweenness centrality, mean closeness centrality, PLE,, I.C,, and NC. Dymond uses the following snapshot- based statistics: density, aver- age local clustering coefficient, s-metric, and LCC. Additionally, Dymond uses the following node behavior metrics: node activity rate, node temporal degree distribution, node clustering coefficient, node closeness centrality, node connected component size. TG-GAN uses the following snapshot- based metrics: mean node degree, average group size, average group number, and mean coordination number. TG-GAN additionally uses the following node behavior metrics: group size, average group size, mean coordination number, mean group number, mean group notation. It is important that Dymond additionally uses a two-dimensional KS distance calculation on the first and third quartile of the node behavior statisties, in order to attempt align the node distributions of the generated and ground-truth graph. Additional details are included in their work.
In our work, we choose representative baselines that are both used commonly and capture different attributes of the graph. We select average node degree as a way of capturing local topology. In contrast, we select LCC and NC to capture more global features of the graph. We select PLE in order to explicitly capture edge behavior of the graphs. We select the node behavior metric node activity rate due to ease of calculation and its demonstrated high sensitivity in prior work.
Next, we provide formal definitions for each of the baseline metrics used in our main work. These definitions are standard the literature but are repeated here for convenience.
Let G = (V, E) be an undirected static graph, where V is the set of nodes and E is the set of edges. For node e E V. let d(v) denote its degree. Let F denote the set of all connected components in G, where each component f F is set of connected nodes.
Mean Degree:
The mean node degree for all nodes in the graph is defined as:
Σ d(v).
VEV
Largest Connected Component (LCC)::
The LCC represents the size of the largest connected
component in the graph, defined as:
max
|[]l]
JEF
where || represents the size of a connected component f.
Number of Connected Components (NC):
The number of connected components is simply [F]-
Power-Law Exponent (PLE): The power-law exponent quantifies the scale of the power-law dis-
tribution the degree sequence of the graph, computed as:
1 1+ 1+IV|
Σ log VEE
dmmn
where dmin is the minimum degree.
The node activity rate is defined as the number of events involving each node in the graph. Formally, for a given node E V, the activity rate a<()) is computed as:
Node Activity Rate:
a(v) = Σ 180 src:) + 5(v, dst;)),
14

---

Published as a conference paper at ICLR 2025
where & is the total number of events in the temporal graph, sre; is the source node of event i, dst, is the destination node of event i, and 6(z, y) is the Kronecker delta function. The activity rate for all nodes can be represented as ID tensor where the i-th entry is the number of events involving node
B ADDITIONAL DETAILS FOR JL-METRIC
B. ADDITIONAL IMPLEMENTATION DETAILS
Here, we describe how normalization may be applied to the JL-Metric algorithm presented in Section 3 of the main work and provide more information regarding the structured random matrix (SRM) class used our experiments.
In practice, representation č(t;) introduced in Section 3 and reproduced below for convenience:
normalize the event features and time stamps of the CTDG. Thus, the event
ē(t.) = (ti, ds (t:))
can be modified by normalization function Ç:
Ec (t.) = ((er.))((e
Here, the normalization function is applied separately to the time stamp and each feature channel in feature vector (t)) Relevant statistics for the normalization CTDG representation (Equation D For our experiments, we apply min-max normalization (Patro) 2015) and thus collect min and max values from the timestamp and each feature channel.
be collected from the original
We find normalization improves performance as it aides balancing the importance of each feature and the timestamps, decoupling the magnitude of an attribute from performance.
As discussed in Section while orthogonal random matrices may be used for W1 and W2 in our JL- metric calculation, practice we prefer use structured random matrix (SRM). We specifically experiment with using the SR-product matrices introduced by Choromanski et al. (2017). These matrices take the form diagonal matrix with Rademacher random variables on the diagonal.
HD, where H IR is normalized Hadamard matrix and is
The normalized Hadamard matrix H, defined recursively as:
1
Hyz
Hy2 -H12
=1= H.
V2
H1p2
The diagonal matrix D is populated with i.i.d. Rademacher random variables, i.e., Dis 1ni)([-1,1)). Note that this definition produces square matrix. However, rows or columns can be removed as needed to achieve the desired dimensions. Together, the product of these matrices W == HD forms the structured random matrix we use in place of fully random orthogonal matrices. Choromanski et al. (2017) demonstrates that such matrix has performance similar to better than orthogonal random baselines. We find empirically that for the JL-metric, choice of random matrix has negligible effect metric sensitivity. Thus, described in main work, recommend the use of SRMs due their computational advantages.
B.2 LIMITATIONS
Throughout our experiments, we identified potential limitations to our approach, which we summa- rize here.
While our metric is designed to domain-ane domain-agnostic, providing a unified assessment of dynamic graphs across application domains, it may not replace specialized metrics that important for capturing specific graph properties in certain applications. For instance. in molecular and protein studies, metrics such ring counts and other specialized structural features may be of particular
15

---

Published as a conference paper at ICLR 2025
importance. In such cases, classical commain-specifie metrics remain important for thorough analysis. Our method is intended to complement these specialized metrics by offering a general framework for evaluating dynamic graphs, rather than to replace them.
Our method relies on ordering nodes based on the timestamp of their first appearance to create a consistent representation of the dynamic graph. In rare situations where multiple nodes first appear at the exact same timestamp, this could introduce ordering ambiguity, similar to the graph isomor- phism problem encountered in static graph analysis (Sato 2020 Xu al. (019). However, CTDGs typically have continuous timestamps with high precision, making such instances uncommon. If nodes do share the same initial timestamp, secondary attributes such as node feature values could be used to establish consistent ordering. Addressing this scenario is beyond the scope of our current work but represents an area for potential future exploration.
Our approach involves two hyperparameters related to the dimensions of the node and graph descrip- tors used the random projections. Similar to prior random network-based methods (Thompson) al., 2022; Xu et al.) 2018), there is no universally optimal choice for these hyperparameters. In our work, we perform grid search to select reasonable values for our experiments as described in Appendix D.I However, practitioners should be aware that the choice of descriptor dimensions can affect metric performance and ensure consistent dimensions when comparing metric performance. Future work could focus developing automatic methods for hyperparameter selection.
C DATASET DETAILS
The Reddit, Wikipedia, LastFM, and MOOC datasets are bipartite temporal interaction graphs pub- licly released by Kumar et al. 2019
In the Reddit dataset, the two node types are users and subreddits (communities within Reddit). An interaction (edge) is formed when user engages with a subreddit, such as by posting. The Wikipedia dataset similarly contains users and pages as node types, with edges representing user edits to pages. For both datasets, interactions are timestamped, and event features are derived from text data.
The LastFM dataset captures user interactions with songs and thus has two node types: users and songs. Unlike the others, this dataset does not include specific feature attributes for interactions.
In the MOOC dataset, nodes represent users (students) taking "massive open online course" and actions (interactions with course material). Edges form when a user interacts with a course, such as by clicking videos interactive content.
We make two major changes to the JODIE datasets: First, we shorten all datasets to the first 1,000 interactions, calculating many classical graph metrics at the Nyquist rate is impractical otherwise. Second, we augment the LastEM dataset, which lacks features, by assigning a feature value of to each event. This allows
compute the JL--Merric (Section 3) without modifying the algorithm.
The Grid dataset, described in Section 4 is a grid-like CTDG where each node connects to its neighbors regular time intervals (.,,...,f.. fm). The event features Case as (t,) h(sre, dst, f,) introduce explicit dependencies on both the temporal and topological aspects of the graph. Specif- ically, for our experiments, define h(src, dst, 4.) produce two features based the temporal and node information: hisrc, dst, 4,) = (src 4, dst + 4.).
Table statistics for each dataset regarding these datasets after preprocessing described above. Additionally, our accompanying code contains tool that provides detailed dataset statistics for given interaction count. Finally, we refer interested readers Kumaar al., 2019 for additional dataset details.
D EXPERIMENTAL DETAILS
Here, detail hyperparameter search for the JL-Metric, training and hyperparameters for the Temporal Graph Network (TGN) (Rossi et al. 2020) used in the diversity experiments (Section 4.2). and provide information on the hardware and software used.
16

---

Published as a conference paper at ICLR 2025
Dataset
Nodes
# Interactions
Snapshots (Nyquist)
esrc.dat
Reddit
852
1,000
4.887
172
Wikipedia
377
1,000
27,365
172
MOOC
147
1,000
71,233
LastFM
385
1,000
848,680
Grid
539
1,000
9,000
2
Table Statistics of Dynamic Graph Datasets
D.1 JL-METRIC HYPERPARAMETER SEARCH
As discussed in Section 3 the JL-metric has two tunable hyperparameters: node event embedding size and descriptor size o. In our experiments, we conduct a progressive search for reasonable values of and o by gradually increasing both until performance gains begin to stagnate (< 1% change). Starting with n 25, we incrementally test values up 200 in steps of 25. For each pair, monitor the median Spearman score across all perturbation experiments (Sections 4.1 and 4.2). Once performance improvements plateau-indicating diminishing returns with higher values- select the smallest and that yield near-optimal results. In case, select n = 100 and o = 100. As anticipated from the Beanson-Lindenstrenn expect the required n to grow with the number of nodes and required to grow with the number of graphs being compared. Future work should empirically verify these scaling relationships.
lemma (Section 3 we
D.2 TEMPORAL GRAPH NETWORK TRAINING DETAILS
As detailed in the main work, in order cluster nodes into modes for the diversity experiments in Section 4.2 we train a Temporal graph network (TGN) (Rossi et al. 2020). To do so, we train on the supervised task of link prediction, as detailed the original work. We additionally keep all training details the same: We use the Adam optimizer, binary cross entropy loss, and a 70% 15% 15% chronological train-validation-teel split. Given that Rossi et al. (2020) experiments with the same datasets
(Jodie (Kumar et al. 2019)). values from that work. These are repeated here for convenience: memory dimension = 172, node embedding dimension 100, time embedding dimension 100, number of attention heads 2, and dropout- = 0.1. We select the model with the best validation loss.
forgo hyperparameter search and use the reported
D.3 SOFTWARE AND HARDWARE TOOLS
We primarily rely on the Pytorch geometric (Fey & Lenssen 2019) and NetworkX (Hagberg al. 2008) open-source Python libraries for static graph representations. Given its importance to runtime benchmarking and overall reproducability, we provide full list software libraries used in our experiments, well their respective versions, in the Supplementary material. We additionally provide an anonymized version of our code in the Supplementary material. All metries are tested on AMD EPYC 7713 64-Core Processor and the Red Hat Enterprise Linux 9.3 operating system.
E DATASET SPECIFIC RESULTS
The results presented in Figure 1 and Table in the main work aggregated across all tested datasets. Here, we include results of the sensitivity analysis (measuring fidelity and diversity) for individual datasets. Tables 7 present the results for the Grid, Reddit, Wikipedia, MOOC, and LastFM datasets, respectively. As noted in the main work, the LastFM dataset does not contain features and thus the Event Permutation values left N/A in Table
17

---

Published as a conference paper at ICLR 2025
Table 3: Perturbation Correlation results for the Grid dataset.
Perturbation Correlation (Median Spearman Score)
Metric
Edge Rewiring
Event Permutation
Time Porturhation
Mode Collapse
Mode Dropping
Grid Dataset
Node Degree (KS)
0.988
0.988
0.879
0.755
Node Degree (MMD)
0.988
0.988
1,000
0.782
LCC (KS)
0.988
0,903
1.000
0.915
LCC (MMD)
0.867
1,000
0,952
(KS)
0.927
0.877
0.514
0.623
NC. (MMD)
0.976
0.886
0.830
0.527
PLE (KS)
0.976
0.988
0.891
0,298
PLE (MMD)
0.976
0.976
1.000
0.879
Activity Rate (KS)
0.988
1.000
0.297
Activity Rate (MMD)
0.603
0.522
0.378
Feature Metries
Kullback-Leibe Div.
Masen-SShannon Div.
0.796
0.522
KS
0.960
0.123
MMD
JL--Merric (Ours)
1.000
0.988
0.979
1.000
0.503
Table 4: Perturbation Correlation results for the Reddit dataset.
Perturbation Correlation (Median Spearman Score)
Metric
Edge Rewiring
Event Pennutation
Time Perturbation
Mode Collapsc
Mode Dropping
Grid Dataset
Node Degree (KS)
0.988
0.527
0.964
0.855
Node Degree (MMD)
1,000
0.491
0.976
0.806
L.C. (KS)
0.988
0.729
0.231
0.815
LCC (MMD)
0.988
0.782
0.782
NC (KS)
0.891
0.370
0.985
0.988
NC (MMD)
0.988
0.455
0.988
0.976
PLE (KS)
0.988
0.539
0.963
0.745
PLE (MMD)
0.758
0.539
0.976
0,248
Activity Rate
0.952
1.000
1.000
Activity Rate (MMD)
0.748
0.498
0.097
Feature Metries
Kullback-Leible Div.
0.915
0.782
Casen-SSaanoo Div.
0.927
0,903
KS
0.742
0.488
MMD
0.781
0.535
JL-Metric (Ours)
0.903
1.000
0.960
0.976
0.988
Table 5: Perturbation Correlation results for the Wikipedia dataset.
Perturbation Correlation (Median Spearman Score)
Metric
Edge Rewiring
Event Penmutation
Time Perturbation
Mode Collapse
Mode Dropping
Grid Dataset
Node Degree (KS)
0.924
0.902
0.648
Node Degree (MMD)
1.000
0.782
0.491
LCC (KS)
0.939
0.794
0.172
0.782
LCC (MMD)
0.794
0.733
0.733
NC (KS)
0.952
0.717
0.988
0,939
NC (MMD)
0.988
0.600
0.988
0.830
PLE (KS)
0.867
0.957
0.806
PLE (MMD)
1.000
0.806
0.988
0.661
Activity Rate (KS)
0.976
1.000
0.988
Activity Rate (MMD)
0.733
0.793
Feature Metries
Kullback-Leibler Div.
0.830
0.273
Div.
0.879
0.879
KS
0.778
0.711
MMD
0.637
0.661
JL-Metric (Ours)
0.867
0.988
0.944
0.952
0.952
18

---

Published as a conference paper at ICLR 2025
Table Perturbation Correlation results for the MOOC dataset.
Perturbation Correlation (Median Spearman Score)
Metric
Edge Rewiring
Event Permutation
Time Perturbation
Mode Collapse
Mode Dropping
Grid Dataset
Node Degree (KS)
0.939
0.891
0.964
0.721
Node Degree (MMD)
0.867
0,939
1.000
0.685
LCC (KS)
0.720
0.709
0.976
0.815
TCC. (MMD)
0.964
0.745
0.770
0.600
NC (KS)
0.333
0.719
0,921
0.588
NC (MMD)
0.418
0,603
0.906
0.406
PLE (KS)
0.879
0.842
0.842
0.673
PLE (MMD)
0.842
0.782
0.915
0.648
Activity Rate (KS)
0.967
1.000
0.624
Activity Rate (MMD)
0.348
0.522
0.350
Feature Metries
Kullback-Leibi Div.
0.648
0.697
Jensen Shannon Div.
0.830
0.806
KS
0.569
0.731
MMD
0.541
0.695
JL-Metric (Ours)
0.952
0.988
0.527
0.964
0.661
Table 7: Perturbation Correlation results for the LasIFM dataset.
Perturbation Correlation (Median Spearman Score)
Metric
Edge Rewiring
Event Permotation
Perturbation
Mode Collupse
Mode Dropping
Grid Dataset
Node Degree (KS)
0.988
0,964
1.000
0.888
Node Degree (MMD)
1.000
0.939
1.000
0.818
LCC (KS)
1.000
0.976
1.000
0.952
LCC (MMD)
0.988
0.964
1,000
0.939
(KS)
0.952
0.891
0.915
0.612
NC (MMD)
0.939
0.891
0.939
0.491
PLE (KS)
0.988
0.927
0.988
0.842
PLE (MMD)
1.000
0.867
0.964
0.903
Activity Rate (KS)
1.000
1.000
0.952
Activity Rate (MMD)
0.603
0.711
Feature Metries
Kullback-Leibler Div.
Shasnn-Saanoon Div.
KS
MMD
JL Embedding (Ours)
1.000
N/A
0.985
0.988
0.927
19


Reviews:
[{"review_id": "q7M7CLcXKa", "reviewer": "Reviewer_MPcg", "summary": "The primary motivation behind the proposed work is to address the limitations of existing metrics for evaluating generative models for dynamic graphs.\nThe authors provide various limitation such as: Lack of consideration for temporal dependencies, lacking a unified measure that is sensitive to both features and topology, Absence of a unified scalar metric.\n\nThe authors propose Johnson-Lindenstrauss (JL) metric to overcome above limitations.\nThey leverage the Johnson-Lindenstrauss lemma to project dynamic graphs into a lower-dimensional space. It  allows for comparison of generated and ground-truth graphs using standard distance metrics.\n\n\nThe authors perform evaluation on datasets:  Reddit, Wikipedia, LastFM,\nand MOOC.  They compared their proposed JL-Metric with several traditional metrics based on topological and feature-based properties. idelity: Also, they did evaluation w.r.t Diversity,  Sample Efficiency , and Computational Efficiency.  \nThe authors used real-world and synthetic datasets to test the metrics under various conditions, including perturbations like edge rewiring, time perturbation, and event permutation.", "questions": "Please see weakness section.\n\n1. Dataset statistics seem to be missing.\n\"We use a subset of these data (details in Appendix C), which were originally introduced\nby Jodie (Kumar et al., 2019) and have become standard CTDG benchmarks\"\n\nIt is not clear what subset for each dataset? The authors should specify clearly.\n\n\nCheck [A]  Table 1 on what information could be useful to add in terms of dataset statistics.\n\n2. Could authors throw some more light on how evolution is capture in their metric? \". The JL-Metric, by\ncontrast, is more expressive, capturing both temporal and structural changes directly\". Can the authors clarify it better. structural + temporal?\nI may be missing something. \n\n[A] TIGGER: Scalable Generative Modelling for Temporal Interaction Graphs\nhttps://aaai.org/papers/06819-tigger-scalable-generative-modelling-for-temporal-interaction-graphs/", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Novel Approach to Evaluating Dynamic Graph Generative Models.\n\n2. Strong Empirical Evaluation.\n\n3. Code is shared.\n\n4. Background work is very well cited and explained. Limitations are clearly highlighted and justified by experiments.", "weaknesses": "1. In 4.1 evaluation:\n\nAre all the types of perturbations independent? Can't the perturbations happen jointly? i.e edge rewiring and time perturbation together? Or have I misunderstood it? Is there any assumption. Kindly clarify. If they are independent, can we understand the impact if they occur jointly? Since in reality, it could happen right?\n\n2. \"a timestamp ti is replaced by a uniformly selected one trand ∼ Unif(ti−1, ti+1)\"\nWhy is the range so small? just 3 possibilities? Is there any specific reason for this? Can we increase this range while also preserving the order?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8EUmDZ2YIB", "reviewer": "Reviewer_zdbk", "summary": "The paper introduces a novel quality metric, JL-Metric, for evaluating generative models of dynamic graphs, addressing limitations in current metrics that treat temporal events as independent and fail to capture the integrated evolution of both graph topology and features. By leveraging the Johnson-Lindenstrauss lemma, the authors propose a method that uses random projections to measure similarity between dynamic graphs, resulting in an expressive, scalar metric applicable to continuous-time dynamic graphs. Empirical results suggest this metric achieves high fidelity and computational efficiency compared to traditional metrics.", "questions": "I am not highly specialized in this dynamic graph metric research area, but I do have a few general questions:\n\n\nQ1: How does the method ensure robust sensitivity to subtle changes in node and edge features, especially when applied to simpler dynamic graphs or those with more complex interactions beyond temporal events? In theory, how do graph scale and interaction complexity influence the performance of this metric?\n\nQ2: This paper covers a range of metrics and theoretical concepts. As a minor suggestion, it might enhance clarity to include a high-level figure illustrating the differences between the proposed metric and others, beyond just presenting post-experimental results.", "limitations": "", "rating": 8, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "S1: Unified Metric for Temporal Dynamics: The proposed metric overcomes the limitations of traditional methods by capturing dependencies between events and integrating both topological and feature dynamics, specifically for CTDG, which looks rational to me.\n\nS2: High Efficiency and Practicality: The method’s use of random projections reduces runtime and memory demands, making it feasible for large-scale graph evaluation tasks, along with extensive evaluations, which looks comprehensive to me.", "weaknesses": "See questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "f4L6onni9e", "reviewer": "Reviewer_eyCj", "summary": "The paper proposes a new metric for measuring similarities between temporal graphs, utilizing the input dimension agnostic property of random projection certified by the JL lemma. The metric is based on a node interaction history representation of a temporal graph, computed via first projecting individual node histories, followed by another random projection that fuses nodes. Experimental results demonstrate that the proposed metric achieves better fidelity and diversity than classic metrics, while being computationally efficient and sample efficient.", "questions": "- As the authors use JL as their motivation for representation construction, I think it would be interesting if the authors provide the exact JL bounds that incurred during empirical evaluations: How well does JL compresses real world temporal graphs, according to the standard JL bound?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Defining a suitable metric for assessing generation quality of temporal graphs is an important problem in graph generative modeling. The proposed metric is a novel approach that goes beyond the traditional way of using statistical summaries as quality measures.\n- The proposed JL metric is shown to behave well empirically, especially in the event permutation sensitivity analysis.", "weaknesses": "- The proposed JL metric is stated to accommodate both topological information and feature information. While the overall assessments using sensitivity analysis have shown that JL indeed performs better than baselines, it would be more intuitive if the authors provide concrete evidences illustrating the sensitivity to some topological structures that exists in the evaluation datasets.\n- In line 277 the authors proposed to use a simplified version of node history as node level presentation. The simplification essentially drops (some) interaction information, i.e., the interaction nodes' identity information. According to my understanding, this simplification inevitably looses capability to account for topological information.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "88zrGq0llu", "reviewer": "Reviewer_f4HN", "summary": "The paper presents a novel metric designed for evaluating generative models of dynamic graphs, where both topology and features evolve over time. The authors propose a new metric based on the Johnson-Lindenstrauss (JL) lemma, which leverages random projections to create an expressive, scalar measure that captures the complex dependencies in dynamic graphs, overcoming limitations in current evaluation methods.\n\nCurrent metrics for evaluating dynamic graph generative models (DGGMs) rely on static snapshots, and therefore lose the temporal dependencies. Moreover, current metrics fail to capture node and edge features and their relation to the graph topology. They are also only sensible to specific properties resulting to the need of multiple metrics. Many of these metrics are also computationaly inefficient. \n\nTo address these limitations, the authors propose a new Johnson-Lindenstrauss-based (JL) metric, inspired by work in the static graph domain and image-based evaluations. The metric applies random projections directly to continuous-time dynamic graph data, effectively embedding the variable-length sequence of graph events into a fixed-dimensional vector space. This transformation preserves the similarity of data across temporal interactions and node features while avoiding the computational cost of explicit snapshot instantiation.\n\nThe author justify the use of random projections on the Johnson-Lindenstrauss lemma, which asserts that random orthogonal projections can approximately preserve the distance between data points. This property allows the proposed metric to map dynamic graph events of varying lengths into a unique dimension. \n\nExperiments are conducted on both real-world datasets (e.g., Reddit, Wikipedia, LastFM) and synthetic datasets. They show that the JL metric provides consistent, high-fidelity measurements across topological and temporal changes, with reduced computational overhead.", "questions": "Please, could you comment on the limitations mentioned above? On the fact that the metric only evaluates changes rather than the graph distribution itself and on the scalability issue. \n\nCould you also comment on the small number of dynamic graph generative models?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well written and structured, making it easy for readers to follow.\n\nBy leveraging the Johnson-Lindenstrauss lemma for random projections, this method offers several advantages, including the ability to capture temporal dependencies, unify topology and feature changes into a single scalar metric, and reduce computational cost. \n\nThe empirical evaluation demonstrates the effectiveness of the new metric. The experiments validate the interest of the method and its practical utility.\n\nAdditionally, Section 3 provides new theoretical insights into why random-network-based metrics may be effective in general, and for dynamic graphs in particular.", "weaknesses": "The methodological novelty of the proposed approach is somewhat limited, as similar frameworks have already been applied, including to static graphs. The authors themselves acknowledge this by stating that they \"follow recent analogous work in the static graph domain by Thompson et al., 2022.\" The contribution is therefore limited.\n\nThe applicability of the proposed metric is focused on continuous-time dynamic graph generative models (CTDGs) with a given initial graph. It is a relatively small field within dynamic graph research, where most studies adopt a supervised learning setting. Moreover, new metrics for CTDGs can be integrated within papers introducing novel generative models, as it have been the case for instance in Zhang et al. (2021). The potential impact of this work may be limited.\n\nThe paper does not include a discussion of the limitations of the method. For instance, it does not address the fact that the metric evaluates only the changes in the graph over time rather than the graph structure itself, limiting the possible application of the metric. Scalability could be an issue, for example, when applying the method to large graphs. These are just examples and a paragraph on some limitations of the method would be insight full. \n\nThe paper does not provide practical recommendations for applying the metric to common datasets. Specifically, there is no guidance on selecting the optimal number of samples, events, or the dimensions of descriptors, which could help in effectively using the metric on various datasets.\n\nMinor comment:\nI think that there is a small typo in the formula at the end of line 119.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Spotlight)