- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This work proposes a new method for evaluating generative models for graphs. Some classical metrics propose small substructure counting across the whole graph; they do not consider the locality and relations between these substructures, and the differences might cancel out when averaging across the graph. This paper proposes localized graphlet correlation for evaluating graph generative models. The main idea is to extend standard Graphlet Correlation Matrices by considering how nodes with different structural roles are connected through graphlet adjacency. The authors use spectral filtering to construct the resulting descriptors and evaluate them using PolyGraph Discrepancy. Experiments on three synthetic datasets and four generative models show improvements over several existing graph statistics.
Critical strengths
-
Evaluating graph generative models remains challenging, and understanding which structural properties are not captured by generated graphs is important. The paper addresses a meaningful limitation of commonly used graph statistics.
-
The idea of considering how graphlet roles are connected, rather than only their counts or global correlations, is reasonable. The connection to assortativity also provides some interpretability to the proposed features.
-
The improvements on SBM-L are particularly interesting, as the proposed descriptor detects structural differences that the compared baselines largely miss. This suggests that localized graphlet information can provide useful additional signals.
-
The paper includes ablations of several design choices, perturbation experiments, and computational cost comparisons, which help understand the behavior of the proposed descriptor.
Critical weaknesses
-
My main concern about this work is a weak related work analysis, especially since some previous work has also mentioned similar problems and proposed methods to solve them. The evaluation mainly focuses on traditional graph statistics and a randomly initialized GIN. However, Shirzad et al. (NeurIPS 2022) studied contrastively learned graph representations and GSN-based structural features for the same evaluation problem. In particular, GSNs can incorporate substructure information into message passing and may capture similar local structural dependencies. More recent masked-autoencoder-based evaluation (Wang and Kantarcioglu, 2025) and curvature-filtration-based evaluation (Southern et al., NeurIPS 2023) are also missing. These are relevant alternatives, and it is unclear whether the improvements would remain when compared against them.
-
Novelty relative to existing graphlet-based methods could be better explained. Previous works on graphlet Laplacians (Windels et al., 2019) and motif adjacency (Benson et al., 2016) already use graphlet or motif co-occurrence to capture higher-order structural relationships. Although the proposed correlation-based descriptor is different, the paper should better explain its relationship to these approaches.
-
All experiments are conducted on three synthetic datasets. While these datasets are useful for controlled evaluation, it is unclear whether the improvements generalize to real-world graphs, such as molecular graphs, which are important applications of graph generative models. Also, testing failure modes such as mode collapse and mode dropping, as previously studied by Thompson et al. (2022), would provide a more complete evaluation of the proposed descriptor.
Shirzad et al. (2022). Evaluating Graph Generative Models with Contrastively Learned Features. NeurIPS.
Wang and Kantarcioglu (2025). Graph Generative Models Evaluation with Masked Autoencoder.
Southern et al. (2023). Curvature Filtrations for Graph Generative Model Evaluation. NeurIPS.
Windels et al. (2019). Graphlet Laplacians for Topology-Function and Topology-Disease Relationships. Bioinformatics.
Benson et al. (2016). Higher-Order Organization of Complex Networks. Science.
Thompson et al. (2022). On Evaluation Metrics for Graph Generative Models. ICLR.
Questions for authors
-
Since GSNs can combine substructure counts with message passing, could a GSN using the same orbit-count features capture the structural differences identified by the proposed method? What additional information does localized graphlet correlation provide?
-
How much of the improvement comes from graphlet adjacency conditioning itself, rather than the particular spectral construction? Would a simpler adjacency-conditioned GCM or graphlet-Laplacian-based descriptor perform similarly?
-
Can the authors clarify which configuration was used in the main experiments and whether the approach provides similar improvements on real-world graph datasets (such as molecular ones)?
2 comments
Thank you for your time and effort in preparing the rebuttal and revising the paper. I appreciate the additional explanations and clarifications.
I am convinced of the interpretability aspect of the model in comparison with GSN, and the real-world examination setup arguments. However, after reading the other reviewers' comments and the corresponding rebuttals, I share the concerns raised by Reviewer wEZC. In addition, I believe the discussion of related work and potential failure modes, particularly mode dropping and mode collapse in generative models, could be explored more thoroughly.
While I appreciate the authors' efforts to address the concerns, I remain unconvinced on these points and will therefore maintain my original score.
Response to reviewer DVNR
Q2 is addressed in the shared response above.
Q1: GSN comparison.
We agree that a GSN using orbit-count features could potentially be discriminative. However, discriminative power alone is not the goal: Section 3.2 shows that the grouped permutation importance analysis identifies Ao14-o14 (4-clique co-occurrence) as accounting for 58% (AutoGraph) and 62% (DiGress) of LGCM's discriminative signal on SBM-L. This directly reveals why these models fail: they fail to reproduce community-level co-occurrence structure. A GSN embedding, being a learned representation, cannot provide this structural diagnosis. We have rewritten Section 3.2 to better emphasize that LGCM's features are directly interpretable as structural properties and how this interpretability can be used to diagnose specific generative model failure modes, something not possible with learned embeddings regardless of their discriminative power.
Q3: Real-world datasets.
We agree that real-world evaluation is a natural direction. However, the focus of this work is structural diagnosis: identifying which structural properties a generative model fails to reproduce. This requires a setting where the ground truth generative structure is known, so that detected failure modes can be verified rather than merely hypothesized. We have made this motivation explicit in three places.
• In the abstract: "Applied to three synthetic benchmark datasets, a controlled setting where the generative structure is known and diagnoses can be verified, localized graphlet correlation uncovers a new class of failure modes." • In the introduction: "This diagnostic perspective motivates the use of synthetic datasets, where known generative structure allows detected failure modes to be verified against ground truth." • In the Scope paragraph of the Limitations: "All experiments are conducted on synthetic, unlabeled graphs, where known generative structure allows detected failure modes to be verified against ground truth. The framework is not specific to orbit counts: any real-valued node label vector can be substituted as the signal to localise, enabling a straightforward extension to attributed graphs and other domains," covering for instance molecular graphs with atom-type or physicochemical node features. We consider a full molecular benchmark an important direction for future work.