GraphDCA -- a Framework for Node Distribution Comparison in Real and Synthetic Graphs

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 ba...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2022-02
Main Authors: Ceylan, Ciwan, Poklukar, Petra, Hultin, Hanna, Kravchenko, Alexander, Varava, Anastasia, Kragic, Danica
Format: Article
Language:English
Subjects:
Datasets
Feature extraction
Feature recognition
Graphs
Nodes
Perturbation
Representations
Similarity
State-of-the-art reviews
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2331-8422