Evaluating Graph Generative Models with Graph Kernels: What Structural Characteristics Are Captured?
Authors: Martijn Gösgens
Alexey Tikhonov
Liudmila Prokhorenkova
Venue: Accepted by TMLR ()

Abstract: For many practical problems, it is important to measure similarity between graphs. This can be done via graph kernels. One particular application where the choice of a graph kernel is essential is assessing the quality of graph generative models. However, despite the vast number of graph kernels available in the literature, only basic kernels are usually considered for generative model evaluation. In this paper, we fill this gap and analyze how different graph kernels perform as an ingredient in the pipeline of generative model performance evaluation. To conduct a detailed analysis, we propose a framework for comparing graph kernels in terms of which high-level structural properties they are sensitive to: heterogeneity of degree distribution, the presence of community structure, the presence of latent geometry, and others. For this, we design continuous transitions between random graph models that affect a particular property and measure which graph kernel is sensitive to the corresponding change. We show that using such diverse models with the corresponding transitions is crucial for evaluation: many kernels can successfully capture some properties and fail on others. We also found some well-known kernels that show good performance in our experiments but have been previously overlooked in the literature on evaluating graph generative models.

Published in Transactions on Machine Learning Research (12/2024)
Evaluating Graph Generative Models with Graph Kernels: What Structural Characteristics Are Captured?
Martijn Gösgens*
reseorck@marrinnggeenssss
Alexey Tikhonov Independent researcher
altsoph@gmaii. com
Liudmila Prokhorenkova Yander Research
ostroumova-la www.rraaaaayaddeeeetee.mommm
Reviewed OpenReview: https: oppnreve/pee..veee. net/ formmu id= J9MhajJJOO
Abstract
For many practical problems, it is important to measure similarity between graphs. This can be done via graph kernels. One particular application where the choice a graph kernel essential is assessing the quality of graph generative models. However, despite the vast mumber of graph kernels available the literature, only basic kernels are usually considered for generalive model evaluation. In this paper, we fill this gap and analyze how different ingredient in the pipeline of generative model performance
graph kernels perform evaluation. To conduct detailed analysis, propose framework for comparing graph kernels in terms of which high-level structural properties they are sensitive to: heterogeneity of degree distribution, the presence of community structure, the presence of latent geometry, and others. For this, we design continuous transitions between random graph models that affect particular property and measure which graph kernel is sensitive to the corresponding change. We show that using such diverse models with the corresponding transitions is crucial for evaluation: many kernels can successfully capture some properties and fail others. We also found some well-known kernels that show good performance in our experiments but have been previously overlooked in the literature on evaluating graph generative models.
1 Introduction
Many real-world objects can be represented as graphs: social and citation networks, molecules, the Internet, transportation networks, and so on. For a number of practical problems, it is important to mcasure similarity or distance between graphs, e.g., graph classification, graph clustering, or evaluating graph generative models.
A number of graph kernels have been proposed in the literature to evaluate the similarity between graphs (Kriege et al.) 2020 Nikolentzos et al. 2021). Graph kernels are often based on some graph statistics like node degrees, shortest path lengths, small subgraph counts, and so on. Thus, different kernels capture different graph properties. However, it is not obvious which properties are captured by given kernel. This makes it challenging to choose suitable kernel for particular problem.
One important application of graph kernels is evaluating the performance of graph generative models. To evaluate such a model, one needs a measure that compares a generated set of graphs with a reference set, which is a non-trivial task (O'Bray et al. 2022 Thompson et al. 2022). A standard approach to convert graphs to some vector representations or to compute similarities (kernel values) for pairs of graphs and then aggregate the values into a similarity measure. The most widespread measure of (dis)similarity is maximum mean discrepancy (MMD) which measures the distance between sets of clements given the
*This research was conducted while Martijn Gäsgens was employed by Findhoven University of Technology.

---

Published in Transactions on Machine Learning Research (12/2024)
pairwise kernel values. The problem of choosing the right mcasure for graph generative model evaluation has gained significant. attention recently (O'Bray et al. 2022 Thompson et al. 2022 Shirzad et al. 2022 In particular, it was shown that the choice of kernel (or even a particular parameter for a given kernel) for MMD computation may drastically affect the outcome of the model comparison OO'rray et al. 2022
Despite recent research, the problem of choosing the right graph kernel for evaluating graph generative models is under-explored. Indeed, despite the vast number of graph kernels available in the literature, only very basic options usually considered for generative model evaluation, e.g.; based on the degree distribution clustering coefficient. In this paper, fill this gap and analyze how different graph kernels perform an ingredient of the generative model performance evaluation pipclinc. To conduct a detailed analysis, we propose a framework for comparing graph kernels in terms of their sensitivities to different graph properties. For this, we choose several pairs of random graph models that are different in a particular graph property the presence of community structure, degree distribution, latent geometry, etc. Then, we design continuous transitions between the models: in each transition, the presence of a given property gradually increascs. To evaluate whether a particular kernel is sensitive to particular lype of change, we generale several sets of graphs at different points of the transition and check whether the kernel is able to distinguish these different sets. As a result, we provide a detailed comparison of graph kernels that can help practitioners in choosing the best one for their application. Our framework aligns well with how the performance of graph generative models is evaluated and thus can help in the development of better measures for this task.
One of our main observations that many kernels are sensitive to some the properties while being insensi- tive others. For example, our experiments show that the popular Weisfeiler-Leman kernel is insensitive geometry, which makes it unsuitable for tasks like molecular modeling, where the nodes (atoms) have spatial locations. This shows the importance of using different structural properties for assessing which charac- teristics a kernel is sensitive to. Among the best-performing kernels in our experiments is the long- ong--nown Shortest Path kernel that has not been used previously in the context of evaluating the performance of graph generative models. Other good-performing kernels are the Graphlet kernel, the Pyramid Match kernel, and the kernel based on the Neve graph representation.
The proposed framework and the obtained results can help practitioners in choosing suitable kernels for graph generative model analysis.
2
Preliminaries
In this work, we analyze graph kernels and focus on undirected graphs G (V, with no node/edge attributes since most of the known kernels can be applied to such graphs.
2.1 Measuring graph similarity
Various approaches can be used to mcasure similarity or dissimilarity between graphs. Two major rescarch directions are concentrated graph distances and graph kernels.
Graph distances measure dissimilarity between graphs and are supposed to satisfy the metric axioms. How- ever, the positivity axiom is usually violated in the sense that the distance between two different graphs can be equal to zero. Indeed, if we guarantee that D'G,G") = 0 if and only if and G' are isomorphic, then computing such distance is least as hard as graph isomorphism testing, which is infeasible for most applications.
In turn, a graph kernel is symmetric, positive semidefinite function defined on the space of graphs. This function can be expressed as an inner product in some Hilbert space. A survey of many graph kernels can be found in, e.g.; Kriege et al. (2020); Nikolentzos et al. (021)).
We conduct a comparative analysis graph kernels. Let us note that any kernel K(..) can be transformed / /K(G,,G) + K(2,, G2) (K( G2). Similarly, there are multiple ways of transforming graph dis- fance to graph kernel.
a distance mcasure (up the positivity axiom) as, e.g., D(GI,G))
2

---

Published in Transactions on Machine Learning Research (12/2024)
A typical approach to defining kernel distance for graphs is to describe each graph based its char- acteristics: degree distribution, substructure counts, shortest path lengths, spectral properties, and so on. The obtained descriptors can then be used to compute a graph kernel or graph distance. Some kernels are defined for graphs with discrete node labels. However, they can be applicd to unlabeled graphs as well: for this, we assume that all node labels are equal.
Let us now define several known graph kernels.
Degree histogram (DH) kernel A graph G is represented by vector fa, where the i-th coordinate is the number of nodes of degree i. Then, the degree histogram kernel is computed as the scalar product of fa and for Equivalently, the degree histogram kernel given by
G2)
E Σ VEV
1(deg(u) deg(v)),
where deg(u) be the degree of u.
Weisfeiler-Leman (WL) subtree kernel was proposed in Shervashidze et al. (2011) and is based on the WL color refinement procedure. This procodure works as follows. Initially, all nodes have their labels (or fixed label for unlabelled graphs). At each iteration, node's label is replaced by another label identifying multiset of labels of its neighbors. The procedure stops when it converges. Based on that, the WL kernel for / iterations is
WL(GI,
Σ E
Σ
1( (u) (1)),
I=0 (EV(G;) vEV((2)
where wl', (u) is the label at i-th iteration of the WL procedure.
The Shortest Path (SP) kernel was introduced in Borgwardt & Kriegel 2005 Each shortest path is described by the following triplet: its length and labels of starting and ending nodes. Then, the graph is represented by a vector Sa, where each coordinate is the frequency the kernel is scalar product of fG and fø. In our setting, where each node has the same label, the SP kernel compares the shortest-path histograms. Thus, the vector fa can be interpreted signature of the topology described by the network.
particular triplet in graph. Then,
The Graphlet kernel was proposed in Pržulj 2007). Graphlels are small connected subgraphs of a graph. Consider graphlets of size k. We assign an index to each graphlet and let fa be a vector such that its i-th entry is equal to the frequency of occurrence of i-th graphlet Then, the kernel can computed as the scalar product of fo and for
Weisfeiler-Lehmar optimal assignment (WL-OA) kernel introduced by Kriege et al. (016 and it improves the WL kernel by finding the optimal matching of nodes. Formally,
WL--OAGG,, G2)
max BEB(V, V3)
Σ
k(0,, U2),
ULE
where B(V,, V22) is the set of all bijections between the node sets and
k(2,, 02) = Ei(wl (v1) = wl',
Since WT-OAA requires bijections between the nodes, it can be applied only to graphs of the size.
3

---

Published in Transactions on Machine Learning Research (12/2024)
The Neighborhood Subgraph Pairwise Distance (NSPDK) kernel proposed in Costa & De Grave (2010) considers pairs of rooted subgraphs of radius r' s r whose roots are located at distance d' S d from each other. A kernel k (G1, G2) counts the number of such pairs of rooted subgraphs in the first graph that are identical to pairs in the second graph. Then,
k (G1, G2)
NSPD(G1, G2) = Σ
d'=0d==0 a (G Gi) a (G2, G2)
To make the computation of this kernel feasible, graph invariants can be employed to encode cach rooted subgraph. Then, these invariants can be compared instead of graph isomorphism checking.
NetLSD treats a graph as a dynamical system and simulates heat and wave diffusion processes on nodes and edges of given graph, followed by measuring system conditions fixed timestamps (Tsitsulin et all 2018). More formally, let Ag be the j-th smallest eigenvalue of the normalized Laplacian of graph G. For timestamp define the heat trace h and wave trace Wt of graph G as follows:
he =
Ee-th
e
Wt = Σ e-t
(1)
Here & for the heat, trace and t [0, 2T) for the wave trace.
Then, the heat trace signature and wave Irace signature of G are defined as the sequences of the corresponding traces at different timestamps, ie., h(G) {he HET, and w(G) {we)ee hET. As in the original article, we use 250 log-spaced time stamps between 10-2 and 102 for Th and 250 equally-spaced time stamps between 0 and 2n for Tw, respectively.
Finally, the NetLSD distance (heat or wave) between two graphs G and G' can computed as any distance measure between the corresponding signatures. In our comparison, we use NetLSD representations to obtain graph kernel. For this, we measure the cosine similarity between the graph representations.
Pyramid Match kernel proposed in Nikolentzos et al. (0017) first embeds the vertices of each graph into a low-dimensional vector space using the cigenvectors of the d largest (in magnitude) eigenvalues of the graph's 's adjacency matrix. Since the signs of these eigenvectors are arbitrary, it replaces all their components by their absolute values. Each vertex is thus a point in the d-dimensional unit hypercube. To find an approximate correspondence between the sets of vertices of two graphs, the kernel maps these points to multi-resolution histograms, and compares the emerging histograms with weighted histogram intersection function, Nikolentzos et al. (2017) for more details.
2.2 Kernels for evaluating graph generative models
To evaluate a graph generative model, one needs compare a set of graphs produced by the model with some reference set of graphs (not available to the model during training). Typically, the comparison consists of two steps. First, each graph is described as a point in vector space, or for each pair of graphs their similarity is defined. Then, two sets of points or two sets of similarity values are compared. Arguably the most widely-used approach is to define a kernel (-,,-) for measuring the similarity of graphs and then use mazimum mean discrepancy (MMD) to measure the distance between two sets of graphs G1 and Gz:
(G |2 G1GG2E5,
Σ G2) + G2l G1.GgE02
Σ K(G1,
Σ Σ K(G1, GLER: G2ES2
Gill
If K(GI, G2) is a kernel, then it can be expressed as K(G,, tation f(G). Then, MMD = || 1 /2]12, where 14 = Go Eces, (G).. Thus, MMD indeed a distance.
(J(G)),/ =
for some vector represen-
Besides MMD, there are other approaches to compare distributions: Fréchet Distance (Heusel et al. 2017) Improved Precision & Recall [Kynkäānienii et al. 2019), Density & Coverage (Naeem et al. 2020 there are many ways to compare two distributions of graphs.
Overall,
The work by O'Bray et al. (2022) is the most relevant to our study. The authors consider graphs without node
features and labels and compare several typically used MMD--based measures. To define kernel, O O'Bray
4

---

Published in Transactions on Machine Learning Research (12/2024)
et al. 2022) describe each graph by vector via simple structural characteristics: histogram of the degree distributtonn histogram of local clustering coefficients, or eigenvalues of the Taplacian. Then, different transformations for obtaining a kernel are considered: the first Wasserstein distance (EMD), total variation distance (TV), and the radial basis function kernel (RBF). Each transformation has a paramcter that needs to be specified. The main conclusion of their paper is that for different kernels and their hyperparameters, the outcome of the models' comparison may drastically differ. In the present paper; we note that the two- step procedure of first computing a graph representation and then applying a transformation to get a kernel can be replaced by considering any of the kernels available in the literature such as the shortest path or the graphlet kernels described above. Thus, we cover various graph kernels and compare their performance.
Another contribution of Bray et al. (2022) is their approach to comparing measures: they propose to make perturbations to a given set of graphs and measure whether MMD correlates with the degree change. The considered modifications are the following: random edge insertions, random edge deletions, random rewiring operations, and random node additions. The key distinction of our paper is that we design specific graph distribution changes that largel particular graph properties and allow us to give a much more detailed understanding of what can be captured by particular kernel.
Thompson et al. (0022) also compares evaluation measures for graph generative models and assumes that graphs may have features of nodes and edges. They consider two types of measures: classic (as in O'Bray et al. 2022 and based on neural representations. Thompson et al. (2022) suggest adopting the widely used measures from image generation literature (Fréchet Distance, Improved Precision & Recall, Density & Coverage). But for graphs (in contrast to images), this would require training a neural network for each dataset. Instead, the authors suggest using representations obtained via. randomly initialized Graph Isomorphism Network (GIN) (Xu et al. 2019). To obtain a graph representation, readout function is applied to aggregate node representations at each GIN layer and then the obtained vectors are concatenated. In the experiments, Thompson et al. (2022) measure the rank correlation between the degree of perturbation and the mcasure and show that the proposed randomly initialized GNNs work well. Several aspects are lested: fidelity (whether a measure can delect random graphs added to a set of graphis or detect randomly rewired edges): diversity (a measure should be sensitive to mode dropping and mode collapse); sensitivity node and edge features; sample efficiency (the minimum number of samples to discriminate a set of random graphs from real samples). However, in terms of graph structure, only random rewiring and the Erdös Erdös-Rényí Rényi random graph model are considered. Finally, (hirzad et al. (002)) propose replacing a randomly initialized GIN model with a contrastively trained GNN model, which makes the obtained evaluation measure dataset- depondent.
3 Comparing graph kernels
In this section, we describe the proposed framework for comparing graph kernels. The main questions we want to address is 'What structural characteristics captured by what kernel?' With 'captured', we mean that the kernel can distinguish two sets of graphs if they differ in that particular aspect. To measure the sensitivity of a kernel to a graph characteristic, we consider a sequence of graph generators where, at each step, the considered graph characteristic is more present. To that end, we consider graph generators that include a step parameter 0 which we vary between 0 and 1 to increase the value of the characteristic. We describe below which graph generators we consider and how we interpolate between them.
In all of our generators, we keep the number of nodes n constant, and we also preserve the expected number of edges (except when the target characteristic is density). We use the Erdös-Rénn (ER) random graph model as baseline generator. In the Rrdös-Rényi model, each edge is added independently with probability p0mm(() m/(r).
As we discussed above, previous studies (O'rray et al. 2022 Thompson et al. 2022 measured the sensitivity of graph kernels by perturbing a given (rcal) datasct. Instcad, we use random graph generators since they allow us to gradually increase or decrease specific characteristics and thus conduct detailed analysis of kernels' sensitivity to various structural shifts.
5

---

Published in Transactions on Machine Learning Research (12/2024)
3.1 Structural graph characteristics
In this section, we discuss structural graph characteristics that we consider in our research and introduce the generative models that are used for each of these characteristics.
Density Density is the simplest graph characteristic. We model this by varying the probability p in the basic Erdös-Rényi model.
The degree distribution of an ER graph differs from what is observed in real-world networks: ER graphs have Binomially distributed degrecs, leading to a variance that is lower than the mean degree. However, many real-world networks have a much more helerogeneous degree distribution, where the variance is often many times larger than the mean degree. Many networks even seem to have power-law degree distributions, Icading many hubs and a high degree variance (Barabási & Bonabcau 2003). Several generalive models incorporate degree heterogeneity by prescribing an (expected) degree sequence, can be done with the Configuration Model and the Chung-La model (Chung & Lu 2002 Van der Hofstad 2016). We use the Chung-Lu model because it is generalization of ER and is simple to work with. The input to this model is the vector of the expected degrees (WI,..., wn,"". Given the expected degrees, an edge independently of all other edges. We sample the between two nodes u and e is added with probability Σ. we
Degree heterogencity
prescribed degrees from Pareto distribution with power-law exponent ? 2 2 and scale parameter chosen to ensure that the expected number of edges equals m. In the limit + co, this is equivalent to the ER model, while small finite values lead to degree sequences with high variance.
Clustering In many real-world networks, nodes with common neighbors are more likely to be connected to each other (Watts & Strogatz, 1998 Van der Hofstad 2016). This phenomenon is often referred to as
clustering (Holland & Leinhardt] 1971 Peixoto 2022). and it results in an abundance of triangles, which is often quantified by the clustering coefficient. Social networks and many other real graphs are well-known for having a high degree of clustering (Holland & Leinhardt 1971 McPherson al. 2001).
There two main mechanisms that used to explain and model clustering: community structure and lalent geomeiry. In our analysis, we treat these as two different graph characteristics.
Community structure Many real-workd networks contain groups of nodes that are more densely con- nected to each other than to the rest of the network. In network science, these groups are referred to communities (Fortunato) 2010), and they often have a natural interpretation, like friend groups in social networks or subject areas in citation networks. In addition, the presence of community structure can ex- plain the clustering that is observed in real networks: the presence densely connected groups leads to an increased number of triangles.
The simplest generative model for community structure is the Planted Partition (PP) model HHolland al,, 1983), where we are given a partition of the network nodes into communities, and node pairs of the same community connect with probability Pin; while node pairs of different communities connect with probability Pout- We consider two communities of size n/2 each, and we parameterize Pin. Poat as
Pin (A) = n² + 4mn
4m
2Xn' Poua
(2)
n² A) 2
so that the expected number of edges equals m, while Pin/Pout A. This paranctrization of the PP model reduces to the ER model for X = 1, and the (expected) global clustering coefficient increases monotonously with
Latent geometry Community structure explains clustering by assuming a certain (finite) set of types, and that nodes of the same type have a higher likelihood of connecting than nodes of different types. The Random Geometric (RG) model generalizes this notion by considering a continuous type space and assuming that nodes whose types are similar each other have a larger probability of connecting to each other. In citation networks, for example, papers tend to cite papers related topics. This continuous type space can
6

---

Published in Transactions on Machine Learning Research (12/2024)
be thought of as some feature space, and the (dis)similarity may be quantified by some distance measure in this space. However, often one only has access to the network connections, and not the positions in the feature space. In such cases, we say that the network has a latent geometry.
The simplest way to model this is by assigning to each node a coordinate in some latent space, and connecting two nodes if their distance is lower than some threshold. This model referred to as a random geometric graph (Penrose) 2003). We consider a two-dimensional torus geometry, where each node is assigned a coor- dinate in [0, 1) uniformly at random, and two nodes connected whenever their distance is below some threshold r. We choose to ensure that the network has m edges in expectation, see Appendix A.1
Dimensionality Whenever a network has latent geometry, its connections depend highly on the character- istics of that geometry. For example, networks with hyperbolic geometry tend to have a high level of degree heterogencity (Krioukov et al.) 2010). In particular, the dimension of the latent space heavily affects both the local propertics (e.g., clustering) and global characteristics (c.g., diameter). In general, the clustering coelficient decreases with dimension.
To model varying dimensionality, we use the random geometric graph model: we consider a torus with width and height h E (0. For h = 1, this corresponds to the standard two-dimensional torus, while the limit h + 0 results in a one-dimensional torus, i.e., a circle. Note that the radius r that leads to m edges in expectation, depends on h. The desired value of r(h, m) is derived in Appendix A.1
Complementarity In some particular types of networks, such as protein-protein interaction networks and economic networks (Talaga & Nowak 2022 Mattsson et al. 2021), it has been observed that the clustering coefficient is siguificantly lower than that of an ER graph with the same number of edges. Instead, these graphs have a large mumber of quadrangles (cycles of length four), leading to a locally bipartite structure (Estrada, (006)- This phenomenon is usually explained by complementarity (Talaga & Nowak, ) in these networks, nodes do not connect if they are similar to each other, but they differ in some specific way. In economic nelworks, for example, companies that produce a cerlain product will trade with companies that are in need of that particular product. This leads 'similar' nodes to have many common neighbors, but rarely direct connection. In turn, dissimilar nodes have high likelihood of connecting.
There are several random graph models for complementarity: one option is disassorlalive community struc- ture, e.g., by a PP model with Pmn < Pout, but there are also ways to model complementarity using latent geometry. We model complementarity by a latent spherical geometry (Talaga & Nowak 2022). This has the nice property that each point in the latent space has a unique antipodal point at maximum distance. We assign each node to a point on the hypersphere (with radius 1) uniformly at random and connect two nodes if their distance exceeds - r for some value of r, chosen to ensure m edges in expectation. We refer this generator the Spherical Complementarity (SC) model.
3.2 Interpolating graph characteristics
For each graph characteristic, we define an interpolation between two graph generators, that the strength of that characteristic changes monotonously along the transition. We parametrize each of these interpolations by a step parameter 0 E [0, 1], so that 0 = O leads to the 'left' generator, while f = 1 leads to the 'right' generator. We make use of the fact that most of the generating models introduced in Section 33.1 are generalizations of the ER model. In these cases, we simply parameterize a transition away from the ER model. The ER model chosen with p = m/( so that the expected number of edges equals m. For the geometric models used for latent geometry and complementarity, we will take a different approach to interpolate between generators.
Density (ER(p)) We use the ER model with the edge probability p(0 + 1). Thus, when f changes from to 1, the edge probability increases from p to 2p.
Heterogencity CER+CL) We use the Chung-Lu (CL) model with weights drawn from a Pareto distri- bution with power-law exponent 1+ 1/0 and scale chosen such that the expected number of edges equals m. Note that 0- 0 leads to power-law exponent oa, i.e., all the weights are constant and the corresponding
7

---

Published in Transactions on Machine Learning Research (12/2024)
Fg - 0.947
0.946
0.08
0.27
0.25
0.05
0.04
MNO
0.04
0.63
0.02
0.41
0.50
0.00
(a) Comparison with
0
(b) Comparison with
Figure 1: Scatter plots of the MMD values of the SP kernel for the ER+CL interpolation.
CL model is equivalent to the ER model. The values 0 > 0.5 give weight distributions with infinite variance, which leads to a high variance in the degree distribution.
Communities (ER+PP) We use the PP model with Pin. Pout as given in equation 2 for À = 1 + c(n, where c(n, m) is a constant so that = 0 leads to Piu Pout while 0 = 1 leads to every verlex having (in expectation) one neighbor outside its community. This value is derived in Appendix A.2
Latent geometry (ER+Torus) For this transition, we take the mizture of an ER graph and RG torus graph: we generate a graph from each generator and denote their adjacency matrices by (EER) and A A We construct the adjacency matrix A as follows: for each node pair with indices 1 S i < j S n we draw an independent Bernoulli random variable Bú, with success probability 0 and set A;j = A
(RG) (ER) + B (4,
A Hence, 0 leads to A = (ER)) while 0 = 1 leads to A A(GG), We complete the adjacency matrix symmetrically: Aij = Ajs for > and A₃ = 0.
Dimensionality, (Torust+ (torus+CCircle) To interpolate between two- and one-dimensional torus, consider torus of height h 1 - 0 and connection radius r(h,m) as derived in Appendix A.1 This way, 0 0 leads to torus on [0, 1)² while h O leads to onc-dimensional torus (a circle).
Complementarity (ER+SSC For this transition, we take the same approach for the interpolation ER construct graph by taking mixture of graphs generated by the ER and SC models, such that 0 = 0 results in an ER graph, while 0 = results in a SC graph.
3.3 Measuring the sensitivity of a kernel
We now explain how we quantify the sensitivity of a kernel w.r.t. an interpolation between graph generators. We consider a discretization θ C [0, 1] of the interpolation such that {0,1} C o. For f E O, let Go denote a set of g graphs sampled independently from the interpolation generator at step 0. Furthermore, lct MMD(Ge, Go,; K) denote the MMD value between Go, and Go, w.r.t. the kernel K. We compare cach 0 θ to each endpoint 0" E 10. For each endpoint 0" E {0, 1}, we quantify the sensitivity of the kernel K w.r.t. the interpolation is close to 1, it mcans that the MMD values tend to increase when transitioning 0 away from 6*. But if this value is close to zero, it indicates that there is no clear monotone relation between and MMD(Ge, Ge.5 K). This leads to two different correlation coefficients and rı, corresponding to the different values of 0*. See Figure for an illustration.
the Speorman correlation between MMD(Gg. Go; K) and 0 - 0* If this value
To ensure the independence of the different MMD values that are used to compute a correlation coefficient, we sample two different sets of graphs for each MMD value. Between each pair of 0's that compare, we
8

---

Published in Transactions on Machine Learning Research (12/2024)
compute MMD values. This results in sampling graphs for each 0 E @ {0, 1), and (1 + (+]) s.g graphs for each 0* (0,
4 Experiments
4.1 Setup
We follow the framework described in the previous section. In most of our experiments, consider graphs with = 50 nodes and (in expectation) m = 190 edges. We discretize the interpolation interval [0,1] by e = {0.0, 0.1,0..1..... 1.0). Thus, we have [ = 11 steps in our interpolation. We consider sets of g = 100 graphs and compute = 30 different MMD values for each pair of interpolation steps that we compare.
In this work, we mostly focus on small graphs since evaluating graph generative models typically applied to small networks: e-g-, in molecular modeling, the graphs consist of relatively small number of atoms. Additionally, let us note that not all kernels are scalable: for instance, the graphlet kernel has prohibitively high computational cost. Thus, for smaller graphs, we can include all popular graph kernels in our experi- ments. However, for the completeness of the study, we also consider larger graphs with n = 1000 nodes and (in expoctation) m = 3800 edges, so that the average degree is the same in both experiments.
In our experiments, we use the following kernels and representations:
Node degree histogram kernel (Degree);
Shortest Path (SP) kernel (Borgwardt Kriegel, 2005
Weisfeiler-Teman (WL) kernel (Shervashidze al. 2011) with 1 5;
Weiseeiler-Lchman optimal assignment (WL-OA) kernel (Kicge al. 2016) with ==
Graphlet kernel (Präulj 2007) with k = and k 4 (referred to as Graphlet-3 and Graphlet-4, respectively);
Neighborhood Subgraph Pairwise Distance kernel (NSPDK) (Costa & De Grave 2010 with 3, d = 4;
Pyramid Match (PM) kernel (Nikolentzos et al. 2017 with Pyramid histogram level and the dimension of the hypercube 6;
NetLSD graph representations (Tsitsulin et al. 2018 with heat and wave diffusion process;
Random GIN (RandGIN) representations TTompson al. 2022).
These kernels are described in Section
For most graph kernels, we use the GraKeL python library (Siglidis al.) 2020). Following Nikolentzos al. (2021), normalize the kernel values (GG,, G2)/ /K(G, ( G2). Since our rescarch compares graph kernels as ingredients of evaluation measures, experiments. For the considered kernels, we use their default. hyperparameters listed above (that are either the default parameters of the implementation or the most commonly used parameters in the literature). For the Graphlet kernel, however, the considered values of are limited by 4 duc to high computational complexity of the kernel. For this kernel, we consider and compare its performance for two parameter values: For NetLSD and RandGIN we use the implementation provided by the authors with
have to fix their hyperparameters before running the
k 3 and h the default parameters. In both cases, we use cosine similarity convert graph representations to kernel values. Thus, for all the obtained kernels we have KGG,G) 1. Our code and experiments available at hwtp:h/ww.oo//aMariiiieeg//a/aap
4.2 Results and discussion
The results are shown in Table and the respective computation times are reported in Appendix B that most kernels perform well on some of the interpolations while performing badly on others. This shows the importance of using different interpolations for assessing the sensitivity of kernels. Recall that in this aspect, our framework extends the works by O' O'Bray et al. (2022) Thompson et al. (022)
We see

---

Published in Transactions on Machine Learning Research (12/2024)
Table 1: Sensitivity kernels to various structural characteristics measured via the Spearman correlation as described in Section 3.3 We measure two sensitivity values ro and ri for two endpoints and report their average (ro r1)/2. The top three results are colored.
Density ER(p)
Heterogeneity Communities (ER++P)
Geometry (ER++ Torus
Dimensionality Complementarity (Torust+Circle)
(ER+>CL)
(ER++SC)
Degree
0.996
0.992
0.332
0.073
0.229
0.083
SP
0.994
0.953
0.959
0.957
0.985
0.929
WL
0.996
0.993
0.387
0,150
0.468
0.097
WL-OA
0.996
0.993
0.408
0.601
0.549
0.428
Graphlet-3
0.996
0.988
0.979
0.972
0.721
0.972
Graphlet-4
0.996
0.991
0.973
0,980
0.843
0.970
NSPDK
0.365
0.956
0.373
0.854
0.589
0.580
PM 0.981
0.990
0.950
0.922
0.826
0.923
NetLSD-heatt
0.996
0.939
0.948
0.956
0.950
0.794
NetLSD-wave 0.996
0.943
0.970
0.983
0.614
0.955
RandGIN 0.938
0.947
0.132
0.527
0.067
0.285
We note that some transitions are easier to detect by all the kernels: for heterogeneity, all kernels show relatively good and stable performance. contrast, for communities, geometry, dimensionality, and com- plementarity the difference in performance between different kernels is large: some kernels have correlations larger than 0.97, while others may have near-zero performance, which suggests that these kernels are com- plctely insensitive to these characteristics. Finally, while most kernels perform well the density transition, this turns out to be challenging for NSPDK. Let us go over each kernel individually and summarize the results.
The Degree histogram kernel is added to analysis as it is similar to the degree kernel used in previous studies O' O'Bray et al. (2022): Thompson et al. (2022). As expected, this kernel can perfectly detect the transformations of density and heterogeneity since they directly affect the degree distribution. However, the degree histogram kernel is not sensitive to all other transformations. This shows the limitations using simple graph characteristics to compare graph distributions and motivates the analysis of more advancod kernels that we conduct in our study.
The Leisneilor-Leman kernel and the related WL-OA kernel are considered to be powerful graph kernels. However, in our experiments, observe that they only perform well interpolations that well detected by the degree histogram kernel. Indeed, WL and WL-OA are the best kernels for heterogeneity, which is expected as the first step of the WL procedure is based on node degrees. Similarly, both of them can detect the density transformation well. In contrast, for all the remaining interpolations, the Spearman correlation coefficient quite small. Based on these results, we can assume that. WT.-based kernels are mostly sensitive to the degree distributions. However, it is worth noting that both WL and WL-OA dominate the degree histogram kernel for all interpolations since they are based on more advanced graph statistics that go beyond immediate neighbors.
Comparing WL and WL-OA, we note that the latter dominates for all considered transformations. This confirms that the procedure of node matching improves the sensitivity of this kernel.
The Shortest Path kernel has quite stable performance. Indeed, its correlation values always exceed 0.9 (in fact, it is the only kernel with this property), even for the most difficult transitions communi- ties, geometry, dimensionality, complementarity. Interestingly, SP is not among the best kernels for simple transitions (heterogeneity and density), while still having good performance. Notably, SP is the best for dimensionality, which arguably the most subtle transition. This can be explained by the fact that short- est path lengths capture both local and global information of the graphs, making this kernel sensitive non-trivial transitions.
10

---

Published in Transactions on Machine Learning Research (12/2024)
Shortest /
Shortest distribution inhorogenneus
Shortest distrbuttion
6.7-
05
0.4
0.3
0.2
0.1
61
(a) Erdös Rényi
(b) Chung-Lii
(c) PPM
Shortest distribtiion
Shortest distribution dirde
0.10
0.01
6.60
0.00
15
(d) Torus
(e) Circle
Figure 2: The distribution shortest path lengths for different graph generators, -1 corresponds to discon- nected node pairs.
Figure g shows the shortest path distribution for different graph generators. It can be clearly seen that all models are distinguishable. In particular, see that the SP kernel is sensitive dimensionality: the Circle results in much longer path lengths than the Torus.
The Graphlet kernel another good option in terms of the overall performance: it is among the best-performing kernels for all interpolations but dimensionality, where the difference with the SP kernel is noticeable. The poorer performance for dimensionality may be explained by the fact that the graphlet kernel is not able to capture the global properties of graphs which are affected when vary the dimension (e.g., its diameter). Figure 3 additionally illustrates the difficulty of the dimensionality transition: it turns out that for small values of 0 (when the height is not too small), the distribution of graphlets does not change much, and thus the MMD values are close to zero up to = 0.7. We also see that increasing the kernel sizes from to significantly improves the performance for dimensionality since this change makes the considered neighborhoods larger. For all other interpolations, increasing graphlet sizes does not lead noticeable improvements.
The Neighborhood Subgraph Pairwise Distance kernel was previously used in the analysis by Thompson ct al.) (002)) and has shown reasonably good results in their experiments. In contrast, our analysis with diverse transformations shows certain shortcomings of this kernel. In particular, NSPDK turns out to be insensitive to community structure and density, Other interpolations that hard to detect for this kernel are dimensionality and complementarity. We hypothesize that such poor performance for some of the transitions can be explained by a particular graph invariant used to compare two rooted subgraphs (as the exact. graph isomorphism is infeasible). Unfortunately, this graph invariant also makes this kernel harder to theoretically analyze or intuitively explain.
Let us note that NSPDK has the advantage that it can be used for graphs with node attributes. However, when graphs do have node labels attributes, do not advise using this kernel.
11

---

Published in Transactions on Machine Learning Research (12/2024)
ft 0.721
1s 0.707
0.12
0.10
0.08
0.00
1000
0.04
0.00
0.02
1.0
(a) Comparison with 0" =
(b) Comparison with 0*
Figure 3: Scatter plots of the MMD values of the Graphlet-3 kernel for the torust+circle interpolation.
The Pyramid Match kernel is another kernel that seems be sensitive to all the characteristics. Similarly to the graphlet kernel, PM does not perform well dimensionality. Let also note that PM is dominated by Graphlet-4 for each interpolation. On the other hand, this kernel is scalable and thus it is a good option for larger graphs where the Graphlet kernel cannot be applied. Similarly to NSPDK, the pyramid match kernel has a complex construction procedure and thus its performance is hard to intuitively interpret. Still, our diverse transformations allow us to get some insights into such complex graph kernels.
The NetLSD representations are also sensitive to most of the properties. On almost all the transitions, NetLSD-wer wave outperforms NetLSD-heat. The notable exception is Dimensionalityy, which is arguably the most challenging interpolation. Here, NetLSD-heat is the second-best, while the performance of NetL.D- wave is quite poor. We illustrate the difference between NetLSDDheeat and NetLSD-wave for this transition in Figure 5 where each cell shows the MMD value for two samples of graphs: corresponding to steps 0 and lg. As expected, in both cases we see near-zero MMD values on the diagonal 0 = 02 since the distributions are the same. For a good kernel, we also expect that MMD increases monotonically as we move away from the diagonal while keeping 0, (or 02) fixed since the distributions become more different. In particular, for 8g 1, expect the distance to monotonically increase when we move from 0, 1 to 0 = 0. This is indeed the case for NetLSD-heat, but surprisingly not the case for NetLSDD-wave.
Figure 5b shows that the distance between graph samples for 01 = 0.6 and 0₂ = larger than the distance between 0, = 0 and 02 = 1, which is quite unexpected. To additionally illustrate this phe- nomenon, Figure 4 shows the NetL.SD-wave traces from which the graph representations are obtained. One can see that the trace for 0 = 0 is indeed closer to 0 = 1.0 than 0 = 0.6. Taking into account quite complex nature of NetLSD-wave graph repro- sentation, we currently cannot explain this behavior. However, our framework allows one to detect such peculiar properties of graph representations.
0 0.0
0.5
0 0.6
-0.5
Timescales
Figure 4: NetLSD-wave traces for Dinensionality.
Random GIN representations were proposed in Thompson et al. (2022) in the context of evaluating graph generative models. We note that there are some differences in our selup. First, our graphs do not have node features, while being able to process such features one the main advantages of RandGIN. Second, Thompson et al. (2022) use GIN representations to compute measures like precision, recall, or Fréchet Distance. Instead, we use RandGIN construct graph kernel that can be used with the MMD framework: do this to compare all kernels and representations in the unified setup. Our results show that when
12

---

Published in Transactions on Machine Learning Research (12/2024)
00- 0.205
38-
0.02
0.000
52-
6 0.5
3.
08-
34
(a) NetLSD-heal
(b) NetLSD-wave
Figure 5: Heatmap of MMD values for Dimensionality transition. MMD measures the distance between two samples of graphs corresponding to steps 02 and 02.
Table 2: Sensitivity of kernels to various structural characteristios for graphs on 1000 nodes.
Heterogeneity Communities (ER++P)
Geometry (ER+
Dimensionality Complementarity (Toruse+Circle) (ER++SC)
(ER+>CL)
WL
0.996
-0.030
0.741
0.226
0.561
WL-OA
0.996
0.099
0.948
0.210
0.871
PM
0.975
0.931
0.989
0.238
0.981
NetLSD Heat
0.910
0.530
0.985
0.631
0.958
NetLSD Wave
0.957
0.648
0.993
0.211
0.981
RandGIN
0.931
-0.041
0.849
0.219
-0.080
Degree
0.996
-0.034
-0.009
-0.015
0.132
used within our framework, the kernel based on RandGIN not sensitive interpolations as communities, geometry, dimensionality, and complementarity. We see that the performance of RandGIN is dominated by the performance of WL-OA. This can be expected since the expressive power of message-passing neural networks is known to be upper-bounded by the WL test (Xu et al. 2019
4.3 Experiments on larger graphs
Results for scalable kernels on larger graph datasets with 1000 nodes are shown in Table 2 To reduce the computation time of these experiments, we set the number of packs to a = 10 instead of 30. We see that these results are consistent with those discussed above for smaller graphs. In particular, NetLSDDhheat is better than NetLSD-wave for all transitions but Dimensionality, while NetLSD-heat is the best scalable kernel for Dimensionality transition.
5 Conclusion
In this paper, we analyze the expressivity of graph kernels in the context of evaluating the performance of graph generative models. We first note that previous research this subject used only limited set of graph kernels. We significantly extend this set and consider list of long- graph kernels. To conduct detailed analysis of the kernels, we develop framework that allows us to check whether a kernel is insensitive to a particular high-level structural graph property. For this, we carefully design an experimental setup based on interpolations between random graph generators differing in a particular structural property.
The results of our experiments confirm the main points of our paper. First, is important to consider graph kernels beyond those usually considered for evaluating the performance of graph generative models. Indeed,
13

---

Published in Transactions on Machine Learning Research (12/2024)
some well-known kernels that show good performance in experiments have been previously overlooked in the urterature on this subject. Examples of such kernels include Shortest Path and Pyramid Match kernels. Second, we observe that the wide diversity of the considered structural properties is critical for a thorough evaluation: is often the case that a particular graph kernel is sensitive to some characteristics while being insensitive to others.
The results shown in Table I can be useful when deciding which graph kernel is most suitable when evaluating generative models in particular application. For example, our experiments show that the popular Weisfeiler- Lehman kernel is insensitive to geometry. In certain applications, geometry can be especially relevant, e.g., for the application of molecular modcling because atoms have spatial locations. In this case, our analysis shows that using the WL kernel is not a good option. Let us also note that kernels with different properties can potentially be combined with each other by, e.g,, averaging their values. Indeed, if one kernel is sensitive to a particular characteristic while another kernel sensitive to another characteristic, then their combination is expected to be sensitive to both of them. However, a detailed analysis of such combinations beyond the scope of the current paper.
Limitations
It is important to keep in mind that it can be challenging (or even impossible) to change one graph character- istic keeping all other properties fixed. While we attempl to isolate the characteristic of interest, it likely that some other properties are affected to some extent. However, let us note that if kernel turns out to be insensitive to particular interpolation this implics that it is insensitive to the underlying characteristics. Also, for clustering consider two different ways to increase it, thus reducing the possible bias from a particular generator.
Another limitation of our work is that we only consider graphs without attributes. Our general framework easily extends to attributed graphs, but the main challenge would be to design meaningful graph genera- tors for this scenario: there are many ways to combine standard graph generators with different attribute distributions.
Additionally, study considers relatively small graphs. Our main motivation is that evaluating graph generative models using graph kernels is typically applied to such 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, we note that not all kernels are scalable: for instance, the graphlet kernel has a prohibitively high computational cost on large networks. We consider smaller graphs so that we can include all popular graph kernels in our experiments.
Finally, we note that our work is an empirical study of the sensitivity of graph kernels to some structural shifts. Theoretical analysis supporting the obtained conclusions would be beneficial. However, for some kernels, such an analysis would be trivial, e.g., the degree histogram is clearly sensitive to shifts in the degree distribution, but not sensitive to shifts in other characteristies that keep the degree distribution unchanged. On the other hand, for most of the kernels, such an ana analysis seems intractable due to their complex structures.
References
Albert-László Barabási and Eric Bonabeau. Scale-free networks. Scientific American, 288(5):60 69, 2003.
Karsten M Borgwardt and Hans-Peter Kriegel. Shortest-pathe kernels on graphs. In Fifth IEEE International Conference on Data Mining. IEEE, 2005.
Fan Chung and Linyuan Lu. Connected components in random graphs with given expected degree sequences. Annals of Combinatorics, 6(2):125 145, 2002.
Fabrizio Costa and Kurt De Grave. Fast neighborhood subgraph pairwise distance kernel. In Proceedings of the 26th International Conference on Machine Learning, pp. 255-262, 2010.
Ernesto Estrada. Protein bipartivity and essentiality in the yeast protein-protede interaction network. Journal of Proteome Research, 509):2177-2188) 2006.
14

---

Published in Transactions on Machine Learning Research (12/2024)
Santo Fortunato. Community detection in graphs. Physics Reports, 486(3-6):75-174, 2010.
Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. GANs trained by two time-scale update rule converge to local nash equilibrium. Advances in Newral Infor- mation Processing Systems, 30, 2017.
Paul W Holland and Samuel Leinhardt. Transitivity in structural models small groups. Group Studies, 2(2):107-124, 1971.
Comporative
Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps.
Social Networks, 132) 1983.
Nils M Kriege, Pierre-Louis Giscard, and Richard Wilson. On valid optimal assignment kernels and appli- cations to graph classification. Advances in Newral Information Processing Systems, 29, 2016.
Nils M Kriege, Fredrik D Johansson, and Christopher Morris. A survey graph kernels. Applied Network Science, 5(1):1-42, 2020.
Dmitri Krioukov, Fragkiskos Papadopoulos, Maksim Kitsak, Amin Vahdat, and Marián Boguná. Hyperbolic geomelry of complex networks. Physical Review E, 82(3):036106, 2010.
Tuomas Kynkäänniemi, Tero Karras, Samuli Laine, Jaakko Lehtinen, and Timo Aila. Improved precision and recall metric for assessing generative models. Advances in Neural Information Processing Systems, 32, 2019.
Carolina ES Mattsson, Frank W Takes, Eelke M Heemskerk, Cees Diks, Gert Buiten, Albert Faber, and Peter MA Sloot. Functional structure in production networks. Frontiers in Big Dala, 4:666712, 2021.
Miller McPherson, Lynn Smith- and James M Cook. Birds of feather: Homophily in social networks. Annwal Review of Sociology, 27(1):415 444, 2001.
Muhammad Ferjad Naeem, Seong Joon Oh, Youngjung Uh Yunjey Choi, and Jaejun Yoo. Reliable fidelity and diversity metrics for generative models. In International Conference on Machine Learning, pp. 7176- 7185. PMLR, 2020.
Giannis Nikolentzos, Polykarpos Mcladianos, and Michalis Vazirgiannis. Matching node emboddings for graph similarity. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017.
Giannis Nikolentzos, Giannis Siglidis, and Michalis Vazirgiannis. Graph kernels: A survey. Journal of Artificial Intelligence Research, 72:943 1027, 2021.
Leslie O'Bray, Max Horn, Bastian Rieck, and Karsten Borgwardt. Evaluation metries for graph generative models: Problems, pitfalls, and practical solutions. In International Conference Learning Representa- lions, 2022.
Tiago P Peixoto.
Disentangling homophily, community structure, and triadic closure in networks. Physical Review X, 12(1):011004, 2022.
Mathew Penrose. Random geometric graphs, volume 5. OUP Oxford, 2003.
Nataša Pržulj. Biological network comparison using graphlet degree distribution. Bioinformatics, 23(2): e177-e183, 2007.
Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mehlhorn, and Karsten M Borgwardt. Weisfeller-Ichman graph kernels. Journal of Machine Learning Research, 12(9), 2011.
Hamed Shirzad, Kaveh Hassani, and Danica J Sutherland. Evaluating graph generative models with con- trastively learned features. Advances in Neural Information Processing Systems, 35:7783 7795, 2022.
15

---

Published in Transactions on Machine Learning Research (12/2024)
Giannis Siglidis, Giannis Nikolentzos, Stratis Limnios, Christos Giatsidis, Konstantinos Skianis, and Michalis Vazirgiannis. Grakel: A graph kernel library in python. Journal of Machine Learning Research, 21 (54): 1 1-5, 2020.
Szymon Talaga and Andrzej Nowak. Structural measures of similarity and complementarity in complex networks. Scientific Reports, 12(1))16580, 2022.
Rylee Thompson, Boris Kuyazev, Elahe Ghalebi, Jungtaek Kim, and Graham W Taylor. On evaluation metrics for graph generative models. In International Conference on Learning Representations, 2022.
Anton Tsitsulin, Davide Mottin, Panagiotis Karras, Alexander Bronstein, and Emmanuel Müller. NetLSD:
hearing the shape of a graph. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 2347 2356, 2018.
Remco Van der Hofstad. Random graphs and compler networks, volume 43. Cambridge University Press, 2016.
Duncan J Watts and Steven H Strogatz. Collective dynamics of wooldd-world" networks. Nature, 393(6684): 440-442, 1998.
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanic Jegelka. How powerful are graph neural networks? In International Conference on Leurning Represenlations, 2019.
A Derivations for graph generators
A.1 Random geometric models
For two-dimensional torus with width 1 and height h < 1, find the radius that leads to edges in expectation. Two nodes are connected when their distance is smaller than r, i.e., whenever the second node is inside a circle with radius r around the first node. If h 2 2r, then the surface area of this circle is simply 2r² while the total area of the torus h. Therefore, the expected edge density is 2r2. Solving (?) g = m leads
h
which is valid long 2r < h, i.e., whenever h smaller surface area, given by the following intogral
4m x-(3)
Otherwise, the circle overlaps itself, which leads
N/2 VP-82
1drdy 2r / VI-w?du u2du /I-had=-Phya
h 2 1-
h 2r
A(h,r)
2r aresin
2r
h/22
To obtain edges in expectation, we need to choose such that A(h, r)h, = mm
After substituting
we get
2
h 1+ 22
h f(2)
arcsin())
-
We then use Newton-Raphson iteration to solve f(=)
2m ((3)
Let us denote the obtained value by
Finally, we take the radius r = 22'
summary, we choose the radius as
(())
h-m
if >
4m
(-(3)
r(b, m)
else.
(3)
2
22m
((C)
16

---

Published in Transactions on Machine Learning Research (12/2024)
Heterogeneity (ER++LL)
Communities (ER+PP)
Geometry (ER++Torus)
Dimensionality Complementarity (irrus++Circle)
(ER++SC)
Degree
0.14
0.15
0.13
0.14
0.14
SP
1.13
1.13
1.13
1.05
1.13
WL
0.15
0.19
0.18
0.19
0.19
WL-OA
1.16
1.27
1.11
1.03
1.18
Graphlet-3
11.32
8.70
7.68
5.97
9.00
Graphlet-4
150.86
85.37
70.08
35.75
91.08
NSPDK
41.37
40.46
36.70
24.83
38.48
PM
0.63
0.64
0.62
0.60
0.63
NetL.SD-hhat
0.74
0.78
0.73
0.89
0.81
NetLSD-wave
0.88
0.89
0.85
1.04
0.96
RandGIN 0.43
0.46
0.43
0.44
0.45
Table 3: The average computation times (in seconds) for comparing two sets of g 100 graphs, each
consisting of 50 vertices. The shown times are averaged over the |e] 11 interpolation steps. The experiments were conducted laptop with AMD Ryzen 7 8840HS CPU and 16GB RAM.
The one-dimensional torus (the circle) is approximated as For circle, we need
obtain
((5)
m edges in expectation. In the remainder, we show that f-1 r(h, m) 7 m first, note that f(z) ~ 2/2 as 2 + 0, so that 2G)
2m (
h (n)
2
as h J 0, so that indeed
= + f-1 11 2m + o(h 1)
2m
h "
o(h-1))
f
f
2
11(2)
2
Next, take the Taylor expansion of f-1 around / ( (2)):
r (1 h 12 + o(h1 ((((()))
-5- -
11 2
o(h
h
n
ohh
+ S' (f- (f(
2
h
Finally, the derivative is given by (z) -2 aresin(s)) have
2 so that the second term is o(h). In conclusion,
2m
h
n2
+ +o(h)
h(2)
m
2
required.
A.2 Planted partition model
For the transition between ER and PP, we want 0 - to lead to every node having one connection to the other community in expectation. We use equation 2 with À + c(n,m) 8. We compute
n 2 (2 c(n, m)) - 2(1 + c(n,m))
2m
1 = = (1 + c(n, m))
This leads to the solution
c(n, m) 2. +
11
2
B Computation times
Table 3 shows the average computation time for comparing two graph sets for each the kernels and graph transitions. Note that the experiments of Table require s s|0] 330 such comparisons for each transition and kernel.
17


Reviews:
[{"review_id": "D6OZzvhGp5", "reviewer": "Reviewer_9owH", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n\n1. Relevancy: The problem addressed is relevant to the community and is considered an important issue. There is no clear solution regarding which metric is proper, and this work takes a step in a direction that helps to clarify this problem.\n2. Accessible and adequate descriptions: The authors provide clear and comprehensible descriptions of the graph kernels and random graph generation methods used in the study.\n3. Selection of methods: The choice of graph kernels and random graph generators appears well-reasoned and appropriate for the research questions addressed.\n4. Thorough analysis: The analysis covers major characteristics of the graphs considered in the context of learning on graphs, with experiments on all these aspects.\n5. Clarity: The paper is well-written, with a clear structure and coherent argumentation, making it easy for the reader to follow the authors' line of thought.\n\n## Weaknesses\n\n1. Lack of theoretical analysis: The paper does not present or discuss any theory related to these topics. What is the theoretical expressivity of each of these kernels? Why or why not should these kernels be sensitive to some characteristics of the graph datasets?\n\n2. Absence of computational analysis: There is no analysis of the time complexity or experimental computation time of the graph kernels considered. Generally, there is a trade-off between the speed of calculating the metric and its effectiveness. For instance, with infinite time, we could exactly calculate the edit distances of the graphs, providing a very accurate metric.\n\n3. Limited graph size: The experiments focus on graph datasets that are smaller than many real-world graphs. Both the graph sizes and the number of samples are very small, and since the graphs are synthetic, the analysis could be adapted for any size.\n\n4. Insufficient sampling: The use of only 30 sets of graphs and 100 MMD samples may not provide a sufficiently robust statistical basis for the conclusions drawn.\n\n5. Absence of node and edge features: Real-world graphs often have node and edge features, which can be crucial for many applications. However, the methods presented focus solely on graph structure.\n\n6. Lack of real-world data analysis: The paper does not include any analysis of real-world datasets, which could provide valuable insights into the practical applicability of the methods.\n\n7. Limited comparison with classical metrics: Apart from node degree, the paper does not compare the presented methods with other classical metrics, such as clustering coefficient vectors or graph Laplacian eigenvalues introduced in [1].\n\n8. Omission of sensitivity analysis: The paper does not include a sensitivity analysis, which has been shown to be crucial and to provide important insights into the robustness of the methods, similar to the analysis conducted in [2].\n\n\n[1] Liao, Renjie, et al. \"Efficient graph generation with graph recurrent attention networks.\" Advances in neural information processing systems 32 (2019).\n\n[2] Leslie O’Bray, Max Horn, Bastian Rieck, and Karsten Borgwardt. Evaluation metrics for graph generative\nmodels: Problems, pitfalls, and practical solutions. In International Conference on Learning Representations, 2022.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors investigate the sensitivity of various Graph Kernels, employed in graph learning, for graph generative model evaluation tasks. They examine diverse graph characteristics and generate Erdős-Rényi graphs as reference points, alongside alternative random graph methods that vary in properties such as density, degree heterogeneity, and clustering. These random graph families are chosen such that their characteristics are controllable via a parameter. The sensitivity of these methods is assessed by computing the correlation coefficients between this parameter and the Maximum Mean Discrepancy (MMD) distance derived using these kernels. Experiments are conducted on graphs without node or edge features, with two sets of graphs differing in size: one set of smaller graphs and another set of larger graphs with 1000 nodes.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Computational Analysis: Please include an analysis of both the theoretical time complexity and wall-clock computation time of the graph kernels. Addressing at least one of these aspects is necessary, including both is recommended for a comprehensive evaluation.\n\n2. Comparison with Graph Laplacian Metric: Please compare the presented methods with the graph Laplacian metric. This comparison is essential for a thorough assessment of the methods' performance.\n\n3. Formatting Improvement: The numbers and texts in the figures are too small, and the quality of the figures is low when zoomed in. Please correct these figures. Additionally, the figures on page 11 have excess space, and the formatting could be improved for better presentation.", "broader_impact_concerns": "This does not seem to be applicable to this work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "sBUH5OAnnd", "reviewer": "Reviewer_f1sq", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Overall Evaluation:**\n\nThis paper presents a solid contribution to the study of graph kernels for measuring graph similarity, offering several strengths but also some limitations.\n\n**Strengths:**\n\n1. **Systematic Approach:** The paper provides a comprehensive study on the effectiveness and sensitivity of various graph kernels with respect to key structural characteristics. The unified framework proposed helps to ensure fairness in evaluation, which is valuable for consistent comparisons.\n   \n2. **Practical Insights:** The findings offer valuable insights for practitioners by highlighting the impact of graph kernel selection on model evaluation outcomes. This provides practical guidance for choosing appropriate kernels based on specific structural characteristics relevant to their use cases.\n\n**Weaknesses:**\n\n1. **Lack of Deterministic Solutions:** While the paper presents interesting findings, it lacks concrete recommendations for practitioners on how to measure graph similarity in real-world applications. For example, if practitioners are looking for a direct method, should they consider combining multiple kernels into an ensemble? Furthermore, the paper does not address the practicality of these kernels in terms of computational efficiency.\n\n2. **Applicability to Node Features:** It is unclear whether the findings and framework extend to graphs with node features (e.g., vector or text features). While this limitation seems inherent to graph kernels rather than the study itself, it does restrict the practical applicability of the results in real-world scenarios where node features are present.\n\n**Presentation Comments:**\n\n1. **Abstract:** In the abstract, the phrase \"using such graph modifications\" is unclear, as the term \"modification\" is not well-defined earlier in the text. A clearer explanation is needed to enhance reader understanding.\n\n2. **Introduction:** The transition between the second and third paragraphs feels abrupt. The discussion moves from explaining why graph kernels are proposed for evaluating graph similarity to evaluating graph generative models without sufficient flow. A smoother transition or clearer connection between these topics would improve the readability of the introduction.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper focuses on the properties of different graph kernels used for measuring graph similarity. The study empirically assesses the effectiveness of various graph kernels in evaluating graph generative models, with a particular emphasis on their sensitivity to key structural characteristics such as degree distribution, community structure, and latent geometry. The authors highlight the limited number of graph kernels previously considered for model evaluation and propose a framework that includes a broader range of established kernels. They assess which kernels best capture specific structural features by conducting experiments with continuous transitions between random graph models. The findings indicate that some kernels, such as the Shortest Path and Pyramid Match kernels, perform well but are underutilized in current research. This study emphasizes the importance of selecting appropriate kernels that correspond to specific structural properties for more effective model evaluation, providing valuable insights for practitioners.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. **Addition of a Deterministic Solution:** I suggest the authors include at least one additional section that proposes a deterministic solution based on the empirical findings presented in the current experiments section. This section could summarize key insights and offer concrete guidance for practitioners. Additionally, I recommend including another section that empirically justifies the proposed deterministic solution in practical scenarios, with respect to both performance and computational efficiency.\n\n2. **Presentation Improvements:** As highlighted in the weaknesses section, certain modifications to the presentation would enhance clarity. In particular, refining the transitions between sections and providing clearer definitions  would improve the overall readability and flow of the paper.", "broader_impact_concerns": "I do not have any ethical concerns regarding this paper.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "jIKkUj6aXM", "reviewer": "Reviewer_oYiU", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros:\n1. Graph kernels are widely adopted in graph-level tasks, but systematic studies of the properties of different kinds of graph kernels were lacking. The paper fills the gap and contributes to the understanding of which graph kernels are suitable for evaluating generative models by highlighting the strengths and weaknesses of different kernels in capturing specific graph properties.\n2. The design of the evaluation framework appears to be reasonable and original.\n3. The benchmark results and the corresponding analyses might be valuable for researchers on graph-level tasks.\n4. The overall structure is clear and well-organized.\n\nCons:\n1. The evaluation and proposed interpolation method are based on synthetic graphs. While this is perfectly fine for controlled experiments, it would be more beneficial to see how the proposed framework and insights generalize to real-world datasets such as OGB.\n2. Some of the graph kernels have hyperparameters (such as $l$ of the WL kernel) and are described in Section 4.1, but the reason why they are chosen remains unstated. Besides, it's unclear if the benchmark results generalize to other hyperparameter settings.\n3. The result discussions are mostly qualitative and lack theoretical guarantees.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper addresses the important problem of evaluating graph generative models using graph kernels. It conducts comprehensive benchmarks to analyze the sensitivity of different graph kernels to various high-level structural properties of graphs, such as heterogeneity of degree distribution, community structure, and latent geometry. It's worth noting that this is a benchmark paper and no new models are proposed.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Please state how the graph kernel hyperparameters are chosen, and provide additional results for other hyperparameter settings if feasible.\n2. The notations for the numbers of iterations of WL{,-OA} kernels $l$ and MMD values $\\ell$ are not obvious to distinguish, consider replacing one of them.", "broader_impact_concerns": "n/a", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: I suggest following suggestions by the Reviewers and updating the manuscript:

- Explain the rationale for the evaluation using synthesis data and discuss the evaluation on real-world graph data as a limitation or future work.
- Discuss theoretical guarantees (e.g., representation capabilities of graph kernels) as a limitation or future work.

We ask the authors to add **Statement of Broader Impact.** (see [Author guidelines](https://jmlr.org/tmlr/author-guide.html)). Although the reviewers did not point out any broader impact concern, I suggest discuss it in the manuscript.

I suggest fixing the following minor typos:
- *Weisfeiler-Lehman optimal assignment (WL-OA) kernel was introduced by (Kriege et al., 2016)* -> Kriege et al. (2016)
- a dynamic system → dynamical system
Decision: Accept (poster)