提出一种新度量方法,高效评估动态图生成模型质量。
Quality Measures for Dynamic Graph Generative Models
- 基于约翰逊-林德斯特拉姆引理,用随机投影直接衡量动态图相似性。
- 相比传统方法,该度量更敏感、更统一,且为单一标量结果。
- 适合需要快速、可扩展评估动态图生成模型的研究者使用。
深度生成模型在图数据建模方面取得显著进展,包括动态图(拓扑与特征随时间演化)。然而,由于难以可视化输出,动态图生成模型的评估面临挑战,定量度量尤为关键。现有方法通常将连续演化过程离散化为静态快照,再应用传统图相似性度量,存在四大局限:(a) 将时序相关事件视为独立同分布样本,无法捕捉非均匀演化;(b) 缺乏同时敏感于结构与特征的统一度量;(c) 无法提供标量结果,需多个指标且无明确优劣;(d) 需显式构建每个快照,导致运行效率低下,难以规模化评估。本文提出一种基于约翰逊-林德斯特拉姆引理的新度量,直接对动态图数据进行随机投影,实现表达性强、标量、应用无关的动态图相似性度量,克服传统方法缺陷。我们还对连续时间动态图的度量进行了全面实证评估,验证了所提方法的有效性。代码已开源:https://github.com/ryienh/jl-metric。
原文摘要 · Abstract (English)
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 \textit{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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。