acceptodds
Under review as a conference paper at ICLR 2027

Localized Graphlet Correlation for Evaluating Graph Generative Models

Abstract

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.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
graph generative models evaluation, local substructure correlations, graphlets, motifs, graph kernel

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_DVNROpenReview ↗
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
  1. 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.

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

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

  4. 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
  1. 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.

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

  3. 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
  1. 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?

  2. 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?

  3. 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
AuthorsOpenReview ↗

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-o14A_{o_{14}\text{-}o_{14}} (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.

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.

Reviewer_piBjOpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper proposes a new descriptor (combined with PGD results in a metric) for evaluating structural similarity between (unlabeled) graphs. The paper is motivated that such a metric be used for evaluation of graph generative models. The manuscript argues that while current commonly used metrics, with most emphasis on graphlet based methods such as the graphlet correlation matrix (GCM), provide an interpretable and somewhat discriminative notion of structural (diss)similarity, they aggregate globally over the entire graph topology and thus fail tok take into account local or node conditioned notions of similarity and are thus limited in expressiveness. To overcome such a concern, the manuscript proposes a correlation that is conditioned on the structural relationships between nodes. Such an insight is implemented as a so-called localized graphlet correlation that is built from encoding how often pairs of nodes co-occur in specific orbit positions within graphlets. The paper argues analytically and empirically that such a method is in some ways more expressive than metrics that aggregate at a global level.

Critical strengths
  1. The paper identifies a meaningful deficiency in some commonly used classical graph descriptors: The central contribution is the sound formation of a descriptor based metric that is conditioned on the individual nodes. The paper argues, generally soundly, and shows empirically, that such a metric overcomes the expressivity issues inherent to several methods with global averaging or readout operations.
  2. The method is also seemingly practical to use and has some appealing qualities: despite conditioning on each member node, the metric may be used to compare graphs of different vertex set sizes, which is an elegant feature. Moreover, the computational complexity does not seem worse than many comparable classical metrics. Moreover, the metric is obviously still descriptor based and thus still interpretable, somewhat comparable to other classical methods, etc.
Critical weaknesses
  1. There seem to be many, sometimes significant, inconsistencies between the primary experimental results and subsequent ablation, which, when taken together, undermine the purported effectiveness of the proposed metric, eg: (a) Section 3.1 states that the reported assort. descriptor uses the standard GCM + 5 orbit adj. conditionings and thus reduces the number of eigendecompositions from 19 to 5. Yet, the results in Table 1 seem to mainly correspond (when comparing raw values) to the 20-conditioning config that seems to be described in the appendix instead of the motivated method in Section 3.1. (b) as another numerical example -- the all-20-conditioning results for the LOBSTER-L/GRAN and LOBSTER-L/ESGG data in Appendix E are 89.7 and 90.3. whereas the corresponding Assort. values in Table 1 are 88.3 and 88.4. There are also numerical several miscellanious improvements discussed in the main text that seem to be absent in the main results table.

  2. Both theoretical and empirical evidence is insufficient to claim that many of the observed improvements arise specifically from the proposed localized assortativity approach: (a) the perturbation experiments demonstrate primarily and convincingly that the proposed method can outperform orbit count descriptors over edge rewiring and edge swapping perturbations while the advantage of Assort. over the (existing) unconditioned GCM (GCM4) descriptor seems to be modest at best. Thus the experiments seem more convincing on the claim that GCM-based descriptors in general should be used for these specific augmentations rather than the manuscripts claimed that Assort. is more expressive in a general sense. (b) On the analytical side there are also soundness problems, eg: spectral filtering generally results in a (dense) PSD matrix, including when the original orbit adjecency is sparse. Thus, the final descriptor is not simply an assortativity coef over directly co-occuring points as implied in the manuscript but rather a function of the relationships of the retained spectral components. The manuscript should not ignore such relationships in the analytical analysis. (c) Appendix I treats the filtered matrix as positive definite, although Section 2.3 constructs only a positive-semidefinite matrix. nontrivial vectors can therefore have zero quadratic forms, and the proof's assumption of a strictly positive denominator does not hold in the general case.

Questions for authors
  1. Could the authors please clarify the configuration that was used for the results in Table 1, reconcile the inconsistencies with Table 4, and provide the corrected main benchmark and runtime comparisons?
  2. The spectral filter discussed above produces a PSD and potentially low-rank matrix. How are zero denominators handled when a non-constant orbit-count vector lies in the nullspace?
  3. Also, given that spectral filtering can assign weights to node pairs without direct orbit co-occurrence, in what sense should the final statistic be interpreted as localized assortativity?
  4. Could the authors isolate the specific contributions from topology conditioning from that of adding additional correlation features? The experiments seems to mangle the two
2 comments
AuthorsOpenReview ↗

Response to reviewer piBj

Q1 and Q4 are addressed in the shared response above.

Q2: Zero denominators and positive semi-definiteness.

We thank the reviewer for catching this. Appendix G already states that zero denominators are handled by setting ρloc=0\rho_{loc} = 0 by convention, identically to undefined standard correlation. The proof in Appendix I has been corrected: we now state that H^oa-ob\hat{H}_{o_a\text{-}o_b} is positive semi-definite (not positive definite), handle the degenerate case explicitly by the convention of Appendix G, and apply Cauchy-Schwarz in the non-degenerate case where both quadratic forms are strictly positive.

Q3: Interpretation after spectral filtering.

We agree that after spectral filtering the descriptor is no longer a direct assortativity over co-occurring nodes. Section 2.4 has been revised to clarify this explicitly: whereas Newman's assortativity measures correlation between directly connected nodes, and the unfiltered form (Equation 7) measures correlation between nodes that directly co-occur in a graphlet instance, the filtered version measures correlation between nodes that belong to the same spectral community in the orbit adjacency — nodes that never directly co-occur may still receive nonzero weight if they share the same spectral community. We retain the assortativity framing for the unfiltered form and are explicit about this shift in Section 2.4.

Thanks for the thorough and constructive response and revision. The corrected experimental configuration, treatment of positive semi-definteness, and clarification of the descriptor interpretation after the spectral filtering step address the majority of my original concerns. While I remain somewhat unconvinced the experimental analysis sufficiently isolates the localization contribution (especially given that the calibration experiment does not seem to establish this), I modestly increase my score and recommend acceptance.

Reviewer_wEZCOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper introduces localized graphlet correlation, a structural descriptor for evaluating graph generative models. It extends standard graphlet correlations by incorporating orbit adjacency, capturing how orbit counts co-vary across structurally related nodes. The method uses a Hermitian construction and spectral filtering to obtain normalized correlations, which are combined into graph-level features. Validation uses PolyGraph Discrepancy across three synthetic datasets and four generative models, supplemented by ablations, perturbation experiments, hyperparameter sensitivity analysis, and runtime comparisons. The results suggest that localized correlations reveal structural discrepancies missed by conventional descriptors, particularly on stochastic block model graphs.

Critical strengths
  1. A well-motivated approach to capturing structural dependencies. Conditioning graphlet correlations on orbit adjacency addresses a meaningful limitation of both average orbit counts and global graphlet correlations: they do not explicitly capture how orbit counts relate across structurally connected nodes. This offers a useful direction for diagnosing graph-generation failures beyond marginal statistics.

  2. Promising evidence of complementary discriminative power. On SBM-L, the proposed descriptor substantially improves discrimination for AutoGraph and DiGress over the evaluated alternatives. Together with the ablations and perturbation analyses, these results suggest practical value as an additional evaluation tool, even though the precise mechanism and consistency of the reported configurations require clarification.

Critical weaknesses
  1. Inconsistent configurations undermine the central empirical claims. The main text recommends concatenating five conditioned GCMs with the standard GCM, but Table 1 contains values corresponding to different configurations in the ablation table. Meanwhile, the hyperparameter analysis evaluates the maximum score across individual descriptors rather than the recommended concatenation. These inconsistencies prevent a clear determination of which method produces the reported gains and whether its robustness claims hold.

  2. The evidence does not isolate the claimed benefit of localization. Rewiring and edge swapping preserve edge counts or degree sequences, but do not guarantee unchanged graphlet orbit-count distributions. Moreover, comparisons against GCM4 simultaneously introduce topology conditioning, additional features, and concatenation, without controls such as direct orbit-adjacency endpoint correlations or concatenated existing descriptors. Consequently, the experiments establish promising discriminative gains but do not adequately substantiate the paper’s central explanation for those gains.

Questions for authors
  1. Which configuration produced the main results? Section 3.1 recommends five conditioned GCMs concatenated with the standard GCM, yet Table 1 contains values matching different configurations in Table 4, while Appendix K evaluates the maximum over individual descriptors. Can you reconcile these discrepancies and provide consistent results for one fixed configuration? This is necessary to assess whether the central performance and robustness claims hold.

  2. What isolates the contribution of localization? Rewiring and edge swapping do not preserve graphlet orbit-count distributions. What evidence demonstrates that the gains specifically reflect local co-occurrence differences rather than residual marginal differences, feature concatenation, or increased dimensionality? In particular, how does the method compare with direct orbit-adjacency endpoint correlations and concatenated existing descriptors?

  3. How is the descriptor defined in degenerate cases? Spectral truncation produces a positive semidefinite, generally low-rank matrix, whereas Appendix I assumes positive definiteness. How are nonconstant orbit-count vectors lying in its null space handled? Please also clarify whether eigenvalues are ordered by value or absolute magnitude, since these choices define different filters.

2 comments
AuthorsOpenReview ↗

Response to reviewer wEZC

Q1 and Q2 are addressed in the shared response above.

Q3: Degenerate cases, positive semi-definiteness, and eigenvalue ordering.

The handling of zero denominators and the PSD correction to the proof in Appendix I are addressed in the response to piBj Q2 above. On eigenvalue ordering: Section 2.3 has been clarified to state that eigenvalues are ordered by decreasing algebraic value (not magnitude), reflected in the updated preamble to Equation 5. Concretely, the filter discards the largest eigenvalue (whose eigenvector is constant for a fully connected graph), retains the kk next largest eigenvalues algebraically clipped to ≥0\geq 0, and sets all remaining eigenvalues to zero. Ordering by magnitude would retain large negative eigenvalues, capturing anti-clustering structure; algebraic ordering deliberately discards these, retaining only the dominant positive spectral components that correspond to cluster structure in the orbit adjacency.

Thank you for the revisions and detailed responses. The revised manuscript uses a consistent configuration for the main results and robustness analysis, resolving my concern in Q1. The clarifications on eigenvalue ordering and zero-denominator handling also resolve Q3. I have no further major concerns on those points.

The GCM4/GCM5 comparisons and reference-versus-reference calibration provide useful evidence, but they do not rule out alternative explanations. Rewiring and edge swaps do not guarantee that graphlet orbit-count distributions remain unchanged. Moreover, the comparison between LGCM and GCM4 changes conditioning, feature concatenation, and dimensionality at the same time. The results establish improved discriminative performance, but do not yet isolate local co-occurrence as its cause.

I appreciate the progress made in the revision. Because Q2 concerns the interpretation of the paper’s core contribution and the evidence remains insufficient, I will keep my original score unchanged.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Shared response to the reviewers

We thank reviewers piBj, wEZC, and DVNR for their careful and constructive engagement with our work. We are encouraged that all three reviewers recognized the core contribution, and we address each concern directly below.

Several strengths were highlighted across reviews.

Meaningful motivation. Reviewer piBj noted that "the paper identifies a meaningful deficiency in some commonly used classical graph descriptors" and that "the central contribution is the sound formation of a descriptor based metric that is conditioned on the individual nodes." Reviewer wEZC similarly observed that "conditioning graphlet correlations on orbit adjacency addresses a meaningful limitation of both average orbit counts and global graphlet correlations: they do not explicitly capture how orbit counts relate across structurally connected nodes."

Discriminative power on SBM-L. Reviewer wEZC highlighted "promising evidence of complementary discriminative power," noting that "on SBM-L, the proposed descriptor substantially improves discrimination for AutoGraph and DiGress over the evaluated alternatives." Reviewer DVNR echoed this: "the improvements on SBM-L are particularly interesting, as the proposed descriptor detects structural differences that the compared baselines largely miss."

**Interpretability and practical usability. **Reviewer piBj observed that "the metric may be used to compare graphs of different vertex set sizes, which is an elegant feature" and that it "is obviously still descriptor based and thus still interpretable." Reviewer DVNR noted that "the connection to assortativity also provides some interpretability to the proposed features" and praised the inclusion of "ablations of several design choices, perturbation experiments, and computational cost comparisons."

Below we address the concerns shared by the reviewers.

Shared concern 1: configuration inconsistency (piBj Q1, wEZC Q1, DVNR Q3)

Reviewers noted that the results in Table 1 appear to match the 20-conditioning configuration described in the appendix rather than the configuration recommended in Section 3.1. The same inconsistency affects Figure 3 and Appendix K.

We acknowledge this inconsistency and have corrected it throughout. We have also renamed the descriptor from "Assort." to "LGCM" (Localized Graphlet Correlation Matrix) to make the naming more descriptive. All results now use a single consistent configuration (the five generative orbit adjacencies concatenated with the standard GCM), updated in Table 1, Figure 3 (discriminatory power vs. computational cost), and Appendix K (robustness to kk, showing stable scores across multipliers 0.50.5 to 2.02.0 of n/2\sqrt{n/2}).

Shared concern 2: isolation of the localization contribution (piBj Q4, wEZC Q2, DVNR Q2)

Reviewers asked whether the gains come from conditioning specifically or simply from adding more correlation features.

Table 1 already includes GCM4 and GCM5 as unconditioned baselines. GCM5 has strictly more features than GCM4 yet does not close the gap with LGCM on SBM-L, suggesting that feature count alone does not explain the improvement. Appendix J shows that all descriptors score approximately 00 on reference-vs-reference splits, ruling out that higher dimensionality inflates scores. The residual gap on SBM-L is therefore attributable to conditioning rather than feature count.

We note that the natural strict control, correlating orbit counts conditioned directly on the sparse orbit adjacency without spectral filtering, does not satisfy the Cauchy-Schwarz inequality and is thus not a valid baseline.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.