Document Type : Research Paper
Authors
Department of Engineering Sciences, University of Tehran
Abstract
The evaluation of graph generative models currently relies on a fragmented ecosystem of distance metrics that fundamen
tally misalign with advanced likelihood-based training objectives. This paper presents a systematic critique and adver
sarial benchmark of the prevailing evaluation paradigms. We demonstrate that standard local statistical descriptors, such
as Degree MMD, suffer from severe structural colorblind ness, failing to penalize macro-structural collapse. Further
more, metrics reliant on learned representations via Graph Neural Networks (GNNs) are theoretically capped by the 1
Weisfeiler-Lehman isomorphism test, rendering them incapable of differentiating distinct global topologies. While ex
act spectral methods utilizing Laplacian eigenvalues resolve these expressive limitations, our scaling analysis proves they
introduce an intractable O(N3) computational bottleneck. Finally, we expose the extreme statistical variance of modern
classifier-based discrepancy metrics in small-sample regimes. By isolating theoretical and algorithmic failure modes, this
study establishes the critical necessity for a paradigm shift toward continuous, scalable, and geometry-aware evaluation
frameworks in constrained graph generation.
Keywords
)