We argue that when comparing two graphs, the distribution of node structural features is more informative than global graph statistics which are often used in practice, especially to evaluate graph generative models. Thus, we present GraphDCA - a framework for evaluating similarity between graphs based on the alignment of their respective node representation sets. The sets are compared using a recently proposed method for comparing representation spaces, called Delaunay Component Analysis (DCA), which we extend to graph data. To evaluate our framework, we generate a benchmark dataset of graphs exhibiting different structural patterns and show, using three node structure feature extractors, that GraphDCA recognizes graphs with both similar and dissimilar local structure. We then apply our framework to evaluate three publicly available real-world graph datasets and demonstrate, using gradual edge perturbations, that GraphDCA satisfyingly captures gradually decreasing similarity, unlike global statistics. Finally, we use GraphDCA to evaluate two state-of-the-art graph generative models, NetGAN and CELL, and conclude that further improvements are needed for these models to adequately reproduce local structural features.

本文提出GraphDCA——基于节点表示集对图之间相似度评估的框架，使用Delaunay分量分析对集合进行比较。通过对不同结构的图示例和公开真实数据集的实验，显示GraphDCA成功捕捉到局部结构相似和不相似的图，并证明其胜于全局统计方法，应用到NetGAN和CELL这两个最新图生成模型的实验进一步表明有必要提高图生成模型对局部结构特征的再现。

GraphDCA - 实现真实和合成图中节点分布比较的框架