Quality Measures for Dynamic Graph Generative Models
Not on the map. Why?
Abstract (arXiv)
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 textitJohnson-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.
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 23 of its 44 references that are in the map. First posted on arXiv 3 Mar 2025.
Builds on
23 of 44 references.
References · 23
- 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
- 2018How Powerful are Graph Neural Networks?cited by 4,355
- 2019Fast Graph Representation Learning with PyTorch Geometriccited by 2,414
- 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,085
- 2019Simplifying Graph Convolutional Networkscited by 1,470
- 2018Demystifying MMD GANscited by 1,268
- 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
- 2020Temporal Graph Networks for Deep Learning on Dynamic Graphscited by 521
- 2019Predicting Dynamic Embedding Trajectory in Temporal Interaction Networkscited by 443
- 2020Reliable Fidelity and Diversity Metrics for Generative Modelscited by 425
- 2015A note on the evaluation of generative modelscited by 291
- 2016Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivitycited by 138
11 more
- 2020A Survey on The Expressive Power of Graph Neural Networkscited by 111
- 2018An empirical study on evaluation metrics of generative adversarial networkscited by 81
- 2022On Evaluation Metrics for Graph Generative Modelscited by 44
- 2017The Unreasonable Effectiveness of Structured Random Orthogonal Embeddingscited by 43
- 2015Deep Neural Networks with Random Gaussian Weights: A Universal Classification Strategy?cited by 40
- 2021Evaluation Metrics for Graph Generative Models: Problems, Pitfalls, and Practical Solutionscited by 38
- 2021Order Matters: Probabilistic Modeling of Node Sequence for Graph Generationcited by 32
- 2022TIGGER: Scalable Generative Modelling for Temporal Interaction Graphscited by 18
- 2023DYMOND: DYnamic MOtif-NoDes Network Generative Modelcited by 10
- 2013Graph Metrics for Temporal Networkscited by 6
- 2017Dynamic Graph Metrics: Tutorial, Toolbox, and Talecited by 3
Built on by
Citing papers per year: 2025: 1.
1 paper.