Evaluating graph generative models with graph kernels: what structural characteristics are captured?

Thank you for the thorough review and useful suggestions! We address your concerns below.

W4. The experimental evaluation is not fully convincing because all the generated graphs consist of 50 nodes and 190 edges (in expectation). It is not thus clear whether the results generalize to graphs of different sizes. I would suggest the authors construct other datasets where graphs are of different size and different density.

Thank you for this suggestion, the experiments on larger graphs (1000 nodes) are currently running, we will update the paper when they are ready.

The main reason that we focus on small graphs, is that these methods (evaluating graph generative models using graph kernels) are typically applied to relatively small networks. For example, in molecular modeling, the graphs consist of a relatively small number of atoms. Other applications where small graphs are relevant include modeling ego networks in sociology.

Additionally, let us note that not all kernels are scalable: for instance, the graphlet kernel has a prohibitively high computational cost. We chose these smaller graphs so that we can include all popular graph kernels in our experiment.

Also, as suggested, we conduct additional experiments where we consider density as a characteristic that we vary. The results are the following:

We see that detecting density is an easy task for most of the kernels, while there are some exceptions, e.g., NSPDK.

W1. The paper claims that graph kernels are commonly used to evaluate the performance of graph generative models, however, no references are given. The authors should add some references and also motivate the use of graph kernels for this task. What are the advantages of graph kernels over competing evaluation approaches?

We refer to Section 2.2 which discusses the evaluation of graph generative models. In particular, O’Bray et al. (2022) focus on this pipeline of evaluating generative models (but they use very simple kernels). Thompson et al. (2022) go beyond kernel-based evaluation, but their proposed approach can also be fitted to the kernel-based framework as we do in the paper.

W2. The paper focuses on 7 graph properties, but it is not clear why those 7 specific properties were chosen and not others. Are there any applications of graph generative models where graphs that exhibit those properties need to be generated? Please provide more details.

We have chosen high-level properties that are meaningful, diverse, and easy to interpret. Of course, one can expect a good graph kernel to be sensitive to all of them, but there is usually a trade-off. Regarding potential applications, for molecular modeling it can be important that the measure is sensitive to clustering or complementarity as the presence of certain small substructures is crucial. For ego-network modeling, heterogeneity, and community structure are important.

W3. Since no theoretical results are provided, I would expect the authors to provide some explanation or intuitions about why some kernels fail to capture some of the considered properties. An explanation is provided in the case of the WL kernel, but not for all the kernels.

Let us note that most of the kernels are intractable for theoretical analysis. For Graphlet3, we might be able to provide the expected values of kernel values, but getting the variances is already much less tractable. Regarding the intuitive explanations, we will try to improve this part in the revised version.

Q1. In page 9, it is mentioned that "there are only two different graphlets of size k=3: wedges and triangles". This is true if connected graphlets are only considered. However, the standard graphlet kernel also counts disconnected graphlets and there are 4 such graphlets for k=3. Did the authors use an implementation that counts connected graphlets?

Yes, we use the GraKeL implementation that counts connected graphlets.

Thank you for the review! We address your concerns below.

W1. With n = 50 nodes and m = 190 edges, the size of the graphs is hardly what we see in practice, where datasets contain [hundreds of] thousands of nodes and many more edges. While this does not disqualify this paper's potential application, it limits the applicability of the insights provided.

Thank you for this suggestion, the experiments on larger graphs (1000 nodes) are currently running, we will update the paper when they are ready. Let us note that graphs significantly larger than this size are rarely considered in settings we focus on, where one needs to compare two sets of graphs (and not just two graphs).

The main reason that we focus on small graphs, is that these methods (evaluating graph generative models using graph kernels) are typically applied to relatively small networks. For example, in molecular modeling, the graphs consist of a relatively small number of atoms. Other applications where small graphs are relevant include modeling ego networks in sociology.

Additionally, let us note that not all kernels are scalable: for instance, the graphlet kernel has a prohibitively high computational cost. We chose these smaller graphs so that we can include all popular graph kernels in our experiment.

Q1. What would be your main argument to ensure the method is generalizable to larger graphs?

To extend our previous reply, let us also note that our method (framework for comparison of graph kernels) is applicable to graphs of any size. The only bottleneck here is that not all popular kernels are computationally efficient.

W2. For instance, the Chung Lu models require the use of very heavy parameterization where every node's weight is used for modeling the degree distribution of a graph. and Q2. What is the effect of using Chung Lu models computationally?

As we describe in Section 3.2, for the Chung Lu model the weights are drawn from a Pareto distribution with some power-law exponent. Thus, this version of the Chung-Lu model takes only one additional parameter, which is used for the interpolation. Then, a naive implementation for generating a graph requires O(n^2) time (and there exist more efficient approaches). Note that this is faster than computing many graph kernels, thus this part is not a bottleneck of our analysis.

W3. Another weakness is that the concept of dimensionality, in page 5, is introduced in the paper in a very general manner and without sufficient rigor to incorporate it in the framework. Thus, something like a pseudocode could be useful to clarify some of these imprecisions. and Q3. Can you describe algorithmically how you incorporated/modeled dimensionality in your framework?

To model latent geometry, we consider a random geometric graph, as described in “Latent geometry” above. The only modification we make in “Dimensionality” is varying the height of the torus from 1 to 0. We will add more details to the text, but if you have any specific questions - please, tell us as it will help us to improve the readability. Note that the code of our models and transformations is also available.

Q4. How did you encoded these graph characteristics in the kernels?

Let us note that we take popular graph kernels and do not modify them in any way. Our aim is to assess what graph characteristic each kernel is sensitive to.

Thank you for the review! We address your concerns below.

W1. I find the paper shows some relationship between generative models of graphs and kernels, it is hard to see what are the applications of these findings in real life. The conclusion is rather qualitative.

Kernels can be used to evaluate graph generative models. However, some kernels are insensitive to certain graph characteristics. For example, our experiments show that the widely-used Weisfeiler-Lehman kernel is insensitive to geometry. In turn, geometry can be especially relevant, e.g., for the application of molecular modeling because atoms have spatial locations. Such findings help practitioners decide which kernels they should and shouldn't use for their evaluations.

W2. One of the key step of the paper is to interpolate between generative models, its formula is not clearly stated. It seems to "interpolate" probabilities of different models, and the idea of "interpolating graph characteristics" has to be properly defined as the characteristics are not mutually exclusive. It is difficult to understand what it means by having "100%" of a characteristic and "0%" of another when the two are related.

We agree that varying one characteristic may also affect other graph properties as it can be hard (or even impossible) to vary only one property in isolation. For each property, we have chosen a graph generator that produces graphs in which this property is strongly present (we try to consider the simplest possible model). Then, we fix a starting point (usually the ER graph) and an ending point (a given model where the property is present to some extent) and make a transition between the two. Section 3.2 states how the parameters of the graph generators depend on the interpolation parameter. If some particular transitions are not clear, we are happy to clarify.

W3. The "performance" of kernels is difficult to grasp and it is related to what is needed to be performed as in also the last point. Overall, I'd suggest to go on this direction with a clear, deeper study of what exactly are the different between generative models. At the moments, it doesn't show concrete conclusion yet for any practical purpose.

Following your suggestions, we will extend the discussion to clearly state some practical conclusions that follow from our analysis. For instance, we observe that random GIN is insensitive to communities, while WL is insensitive to latent geometry. If the generator is supposed to generate graphs that match a certain sample of graphs in terms of having a similar community structure or geometry, then these kernels should be avoided.

Thank you for the thorough review and useful suggestions! We will improve the paper accordingly. We address the questions and concerns below.

W1. The only results presented concern graphs with 50 nodes and 190 edges (on average). We would like to know whether the results obtained are robust when we vary the size of the graph (in number of nodes and number of edges).

Thank you for this suggestion, the experiments on larger graphs (1000 nodes) are currently running, we will update the paper when they are ready.

The main reason that we focus on small graphs, is that these methods (evaluating graph generative models using graph kernels) are typically applied to relatively small networks. For example, in molecular modeling, the graphs consist of a relatively small number of atoms. Other applications where small graphs are relevant include modeling ego networks in sociology.

Additionally, let us note that not all kernels are scalable: for instance, the graphlet kernel has a prohibitively high computational cost. We chose these smaller graphs so that we can include all popular graph kernels in our experiment.

W2. Another limitation is that the results obtained depend on the probabilistic models chosen. For instance, each may introduce random features other than the one targeted, which may bias the results obtained. Figure 2 gives some interesting examples of this phenomenon. This may be an intrinsic limitation of the approach, but it can be overcome by considering different probabilistic models for the same feature.

We agree with this comment and plan to add a clarification about this limitation in the revised text. Our aim was to model each of the properties in the most straightforward way, and in a way that minimally affects other graph characteristics. For some graph characteristics, it can be challenging (or even impossible) to vary them in isolation from everything else.

The idea of considering different models for the same property is interesting - we already do this for clustering: this property can be modeled via triadic closure, latent geometry, or community structure. Other possible variations we can think of are: modeling complementarity by disassortative community structure and modeling degree inhomogeneity by preferential attachment. We consider adding these experiments in the revised version of the paper. However, we may not have time to finalize them during the discussion period as we also need to conduct experiments on larger graphs, as discussed above.

Q1. To have a self-contained paper, the Erdös-Rényi and Chung-Lu models should be described.

Thank you for pointing this out, we will add the definitions in the revised version.

Q2. For some models, the authors explain precisely the link between the parameters and the average number of edges (triadic closure in Appendix B.1 and dimensionality in Appendix B.2). For others (e.g. latent geometry) there is no explanation at all.

The result for latent geometry also follows from Appendix B.2 by setting h=1. We will add a reference to Appendix B.2 to the paragraph about latent geometry.

Q3. As a reader, we are left a little disappointed by the two correlation measures. A single indicator would greatly simplify the statement of results. The data suggest that, in most cases, they are equal.

Thank you for this comment - we agree that having two numbers can be somewhat inconvenient and that they are in most cases consistent. We decided to simplify the presentation by reporting the average value in the main table (or average±difference/2). We will update the table in the revised version.

Q4. On page 2, one reads that computing a distance is as hard as graph isomorphism, while a few lines down, it says that any kernel can be easily transformed to a distance measure. Can the authors address this apparent contradiction?

Thanks for noticing! As we write above, graph ‘distances’ usually violate the positivity axiom, and if we apply the mentioned transformation - positivity can also be violated. We will clarify this in the text.

We hope that our response addresses your concerns. We are happy to answer any further questions.

I would like to thank the authors for their response.

I am curious to see what additional numerical results they will be able to offer to the paper, both on larger graphs and on the study of one feature from several models.

In my opinion, with such further outcomes, the paper could be published at the conference.

I also agree with Reviewer oaCD: beyond the size of the graphs, it is important to see the results over a wide range of graphs. It could be the case with the new experiments if they do not impose a single number of edges in the simulated graphs.

EDIT: Comments from other reviewers are taken into account.