Research map / Graph learning / Graph self-supervised learning
Quality Measures for Dynamic Graph Generative Models
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a Johnson-Lindenstrauss random-projection metric (JL-Metric) for evaluating continuous-time dynamic graph generative models, and provides the first comprehensive empirical comparison of CTDG metrics on fidelity, diversity, sample efficiency and runtime.
Problem
Evaluating generative models of dynamic graphs is hard: existing metrics discretize graphs into snapshots treated as i.i.d., cover topology but not features, require multiple non-comparable scores, and are slow because they instantiate every snapshot.
Approach
Represent each node by the time-ordered concatenation of its timestamped event features, apply structured random projections (normalized Hadamard times Rademacher diagonal) to map variable-length node histories to fixed size, then a second random projection across nodes, and compare the resulting matrices with cosine distance to yield a single scalar that is sensitive to both topology and features
Key results
- JL-Metric achieves median Spearman 0.944 on time perturbation and 0.988 on event permutation, the only metric sensitive to event permutation among those tested.
- JL-Metric reaches 0.915 on mode dropping and 0.988 on mode collapse, while classical metrics often fall below 0.80 on mode dropping.
- JL-Metric runs at 1.05 s per 100 events versus roughly 8 to 12 s for snapshot-based topological metrics, and matches the best sample efficiency (3 events).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use JL-Metric instead of classical snapshot-based metrics | Dynamic graph metric evaluation · Time perturbation | Spearman correlation: 0.915 -> 0.944 | Helped |
| Use JL-Metric instead of topology-based or feature-based metrics | Dynamic graph metric evaluation · Event permutation | Spearman correlation: 0.988 | Helped |
| Use JL-Metric instead of the strongest classical baseline | Dynamic graph metric evaluation · Mode dropping | Spearman correlation: 0.903 -> 0.915 | Helped |
| Use JL-Metric instead of the strongest classical baseline | Dynamic graph metric evaluation · Edge rewiring | Spearman correlation: 1.000 vs 0.976 | No clear effect |
| Use JL-Metric instead of the strongest classical baseline | Dynamic graph metric evaluation · Mode collapse | Spearman correlation: 0.988 vs 1.000 | No clear effect |
| Use JL-Metric rather than Activity Rate (KS) | Dynamic graph metric evaluation · Computational efficiency | Seconds per 100 events: 0.12 ± 0.01 vs 1.05 ± 0.09 | Hurt |
| Normalize timestamps and event features (ablation) | JL-Metric · Dynamic graph metric evaluation | Metric performance | Helped |
| Use structured random matrices instead of orthogonal random matrices (ablation) | JL-Metric · Fidelity and diversity sensitivity | Metric sensitivity | No clear effect |
Surprising findings
- Feature-based metrics (KL, JS, KS, MMD) are insensitive to event permutation, since they ignore feature-topology alignment.
- Activity rate with MMD performs poorly (0.645 on edge rewiring), while activity rate with KS is strong, showing that distance estimator choice strongly changes metric quality.
Limitations
- Two descriptor dimension hyperparameters (n, o) must be chosen by grid search, with no universal setting.
- Node ordering by first-appearance timestamp can be ambiguous when several nodes first appear at the same time.
- Does not replace domain-specific metrics such as ring counts for molecular graphs.
Experimental setup
Datasets: Reddit Wikipedia LastFM MOOC Grid (synthetic)
Benchmarks: Reddit Wikipedia LastFM MOOC Grid
Metrics: Spearman rank correlation sample efficiency (min events) runtime (s/100 events)
Baselines: Node Degree (KS/MMD) LCC (KS/MMD) NC (KS/MMD) PLE (KS/MMD) Activity Rate (KS/MMD) Kullback-Leibler divergence Jensen-Shannon divergence
Builds on: Johnson-Lindenstrauss lemma random graph neural network metrics Temporal Graph Network
Closest papers by meaning
- A Deep Probabilistic Framework for Continuous Time Dynamic Graph Generation (AAAI 2025 · similarity 0.90)
- A Non-Asymptotic Convergent Analysis for Scored-Based Graph Generative Model via a System of Stochastic Differential Equations (ICML 2025 · similarity 0.89)
- State Space Models on Temporal Graphs: A First-Principles Study (NeurIPS 2024 · similarity 0.88)
- On the Role of Edge Dependency in Graph Generative Models (ICML 2024 · similarity 0.88)
- Geometric Generative Modeling with Noise-Conditioned Graph Networks (ICML 2025 · similarity 0.88)
- No Metric to Rule Them All: Toward Principled Evaluations of Graph-Learning Datasets (ICML 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.