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.
Fard,H Moumivand and Bagherpour,N . (2026). Beyond Local Descriptors: Exposing the Expressive and Computational Limits of Graph Evaluation. Journal of Algorithms and Computation, 58(1), 101-111. doi: 10.22059/jac.2026.107820
MLA
Fard,H Moumivand, and Bagherpour,N . "Beyond Local Descriptors: Exposing the Expressive and Computational Limits of Graph Evaluation", Journal of Algorithms and Computation, 58, 1, 2026, 101-111. doi: 10.22059/jac.2026.107820
HARVARD
Fard H Moumivand, Bagherpour N. (2026). 'Beyond Local Descriptors: Exposing the Expressive and Computational Limits of Graph Evaluation', Journal of Algorithms and Computation, 58(1), pp. 101-111. doi: 10.22059/jac.2026.107820
CHICAGO
H Moumivand Fard and N Bagherpour, "Beyond Local Descriptors: Exposing the Expressive and Computational Limits of Graph Evaluation," Journal of Algorithms and Computation, 58 1 (2026): 101-111, doi: 10.22059/jac.2026.107820
VANCOUVER
Fard H Moumivand, Bagherpour N. Beyond Local Descriptors: Exposing the Expressive and Computational Limits of Graph Evaluation. J. Algo. Comp.. 2026;58(1):101-111. doi: 10.22059/jac.2026.107820
