  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.
