Localized Graphlet Correlation for Evaluating Graph Generative Models

Evaluating graph generative models requires understanding which structural pat- terns a model captures and which it fails to reproduce. To gain such insight, models are typically evaluated on their ability to generate graphs structurally similar to a reference set of procedurally generated graphs with known properties, using hand-crafted structural descriptors to quantify the similarity. Empirically, the most discriminative graph descriptor is the average orbit count vector, the mean, over all nodes, of how often each node participates in each automorphism orbit of small non-isomorphic induced subgraphs known as graphlets. However, averaging dis- cards how orbit counts co-vary across nodes, and computing correlations globally fails to account for local structural relationships, such as whether nodes co-occur in the same graphlet instance. We introduce localized graphlet correlation, a family of 20 structural descriptors that condition pairwise orbit count correlations on orbit adjacency, a matrix encoding how often two nodes co-occur in the same graphlet instance, with each node at a specific orbit. Each feature is interpretable as an assortativity coefficient for a pair of orbit positions. Applied to three synthetic benchmark datasets and four generative models, localized graphlet correlation is the most discriminative descriptor overall, and reveals that current models can preserve marginal orbit count distributions while disrupting local co-variation: failures undetectable using existing descriptors.