MMD Graph Kernel: Effective Metric Learning for Graphs via Maximum Mean Discrepancy
Authors: Yan Sun
Jicong Fan
Venue: ICLR 2024 spotlight (2024)
Keywords: graph kernel
graph metric learning
maximum mean discrepancy
Primary area: metric learning, kernel learning, and sparse coding
TL;DR: This paper presents MMD-based graph kernels for improved graph metric learning with proven effectiveness in clustering and classification tasks.

Abstract: This paper focuses on graph metric learning. First, we present a class of maximum mean discrepancy (MMD) based graph kernels, called MMD-GK. These kernels are computed by applying MMD to the node representations of two graphs with message-passing propagation. 
Secondly, we provide a class of deep MMD-GKs that are able to learn graph kernels and implicit graph features adaptively in an unsupervised manner. Thirdly, we propose a class of supervised deep MMD-GKs that are able to utilize label information of graphs and hence yield more discriminative metrics. Besides the algorithms, we provide theoretical analysis for the proposed methods. The proposed methods are evaluated in comparison to many baselines such as graph kernels and graph neural networks in the tasks of graph clustering and graph classification. The numerical results demonstrate the effectiveness and superiority of our methods.

Published as a conference paper ICLR 2024
MMD GRAPH KERNEL: EFFECTIVE METRIC LEARNING FOR GRAPHS VIA MAXIMUM MEAN DISCREPANCY
Yan Sun 1.2
Jicong F.n
School of Data Science, The Chinese University of Hong Kong, Shenzhen, China Schooo of Computing, National University of Singapore, Singapore
3 Shenzhen Research Institute of Big Data, Shenzhen, China cansun@comp nus. edu. .g fanj i cangiccoucchh edu. cn
ABSTRACT
This paper focuses graph metric learning. First, we present a class of maximum discrepancy (MMD) based graph kemnels, called MMD-GK. These kernels are computed by applying MMD to the node representations of two graphs with message-passing prop- agation. Secondly, we provide class of deep MMD-GKs that are able to learn graph kernels and implicit graph features adaptively in an unsupervised manner. Thirdly, we propose class of supervised deep MMD-GKs that are able to utilize label informa- tion of graphs and hence yield more discriminative metrics. Besides the algorithms, we provide theoretical analysis for the proposed methods. The proposed methods are evaluated in comparison to many baselines such as graph kernels and graph neural net- works in the tasks of graph clustering and graph classification. The numerical results demonstrate the effectiveness and superiority of our methods. Our code is available at https://githun com
www.ccomo/coo/eeeeeeee yan--nnn---- -tt.o//aaaa---///------r-er Kernel
INTRODUCTION
Graphs, as mathematical structures, represent entities and their interrelationships. They are indispensable in various domains such as bioinformatics for representing proteins molecules (Aittokalioo & Schwikowski
2006 Huber et al.] 2007), and social networks for identifying communities (Girvan & Newman 2002
Cuvelier & Aufaure 2012). Graph comparison, with explicit distance similarity metric, has been
topic of great interest beyond merely classifying graphs. Graph kernels have emerged as class of effective
methods for measuring the similarities between graphs (Nikolentzos et al., 2021). They often recursively
break down graphs into substructures -like paths (Borgwardt & Kriegel| 2005). graphlets (Shervashidze
et al. 2009). walks (Vishwanathan et al. 2010), and subtrees (Shervashidze et al. 2011). and then compare these substructures between two graphs (Kiieee et al. 2018).
However, early graph kernels face notable limitations. Firstly, the substructures derived from graphs share nodes or edges, leading to overlapping features within the generated feature map, which inflates the dimensionality of the feature space and may reduce the efficiency of the kernel method (Ye et al. 2020). Secondly, these kernels often depend on manually crafted features, missing the nuanced relationships be- tween vertices, thus not integrating higher-level vertex information into the graph feature maps. To address the first limitation, Yanardag & Vishwanathan (2015) proposed the Deep Graph Kernels (DGK) that lever- age natural language processing techniques to get latent substructure representations and create a similarity matrix between these substructures for graph kernel matrix calculations. However, if there is a large number
*Corresponding author

---

Published as a conference paper at ICLR 2024
of substructures, calculating the similarity matrix is time-consuming. The second limitation of graph kernels can be partially addressed by Graph Neural Networks (GNNs) (Kipf & Welling 2016 Veličković et al.
2017 Gilmer al.] 2017] |aamilon et al. 2017 [u et al. 2018 Sun et al. [019 You et [020] [Sun et al.,
2023), that have shown promising performance in both level tasks (e.g. node classification and link prediction) and graph-level tasks (e.g- graph classification). While GNNs may not capture more substructure patterns than WL kernels, they can learn complex functions of features across graph neighborhoods that can be more useful for certain prediction tasks. However, for graph-level tasks, GNNs have to use a readout function or operation (c.g. summation averaging) to convert the nodes' representations (a matrix) of cach graph to a single vector that can be used as the representation of the entire graph. The readout functions operations are generally heuristic, potentially leading to the loss of structural information and further lowering the classification accuracy. Although there have been many efforts and algorithms for better graph representation learning such as Infograph (Sun et al. 2019), GraphCL (You al., 2020), Lovász Principle (Sun et al., 2023), and GCKM (Wu et al. 2023), the final graph representation vector is still obtained by a readout operation on the node representations.
Rather than investigating substructure and graph-level representations, we can regard each graph as discrete distribution or sample from distribution, to be more specific, all nodes in a graph are sampled from a population. Thus, the similarity between two distributions is a proxy to graph similarity or graph kernel. Without prior knowledge about how each graph behaves, we cannot rely on any parametric distribution to describe the graph. Fortunately, Maximum Mean Discrepancy (MMD) (Smola et al., 2006) provides an effective and efficient solution to measure the difference between two parameter-free distributions, though one may consider other integral probability metrics such Wasserstein distance (Sriperumbudur et al., 2012 [Panaretos & Zemel, 2019). The MMD-based approach can be applied: 1) even when the two graphs have unequal sizes (number of nodes) which is often the case in real data; 2) without relying on permutation on nodes; 3) for unsupervised settings where graph labels are missing.
In this study, we develop novel approach to graph metric learning, Maximum Mean Discrepancy-Gii Graph Kernel (MMD-GK), and its extension Deep MMD-GK. The experimental results of graph clustering and graph classification benchmarks demonstrate our methods surpass many baselines. Additionally, we analyze the theoretical robustness of our methods and provide practical guidance on model configurations.
2 PRELIMINARY
We present the following definitions for convenience.
Definition 1. (Artributed Labeled Graph) An attributed labeled graph is graph G (V,E,X,Y) with vertices, endowed with an attribute function f V + X E Rxxd that assigns d-dimensional real-valued vectors to the vertices of the graph and with a label function Ç V + Y E Tk that assigns labels the vertices of the graph from a discrete set of labels. The adjacency matrix of G is denoted as A E {0, 1] 1
In many settings, we represent the discrete labels as one-hot vectors, then Y becomes matrix. Note that we separate the labels from the attributes of graph, since many graph datasets (e.g. protein structure) include both attributes and labels.
Definition 2. (l-Level Node Features) Given an attributed labeled graph G, the l-level features of node aggregate all features in its l-order neighbors, including edges, node attributes, and labels. Mathematically, let U = D- à AD 1 where À = A + I and D = diag Ti Aij.... E3 Anj), all l-level features of a graph are (0) = U X, (1) = U.Y
Message propagation gives rise to 1-level node attributes. The representations (!) and Y()) can better capture the local structure and node features (attributes and labels). The choice of l depends the case.
2

---

Published as conference paper ICLR 2024
== X
2: Y CA
7
(X,Y) (1.0)
of (P. Q sup 1iee mollf A K.}
graph kernel
Tosks:
1. clustering
G
2. classification
CC Gj)
MMD-GK (G,, Gj)
C.O
uusparniedd
reporiianl
G
H
CKL
LSCL
WD
Main Steps
Vanilla: U'z
Vanilla:
k(.-JVk E IC
(GG
GCN: U'DWD
GCN: update W
Figure 1: Architecture of MMD-Graph Kernel (MMD-GK) in vanilla and deep version, where the model is Graph Convolutional Networks (GCN) (Kipf & Welling 2016). The main steps consist of embedding aggregation, kernel mapping. distance-tor restancett--smilkaee to-similartty and for GCN, updating parameters. MMD-GK can be evaluated downstream tasks such as graph clustering and classification.
Definition 3. (Maximum Mean Discrepancy, MMD) Given two distributions P, Q and a kernel k, the square of MMD distance between P and Q is defined as
(PP. Q) = 11 μn l Eplk(x, - 2Ep,q|k(z,, v)1 + Bolk(y,
(1)
where pi and μıR represent the means of distributions IP and Q in the reproducing kernel Hilbert space (RKHS), from which x, x' and yf are sampled respectively.
Note that kernel is characteristic if the mapping IP μrz is injective and then de (IP 0
holds. There are many classes of characteristic kernels, such as the Gaussian kernel K. = fe-1e-v18/1 I, y E Rdd h E J. Fukumizu et al. (2009) generalized the MMD families of unnormalized kernels. Definition 4. (Generalization of MMD) Give family of positive definite kernels K., the generalized MMD between and Q over K. is
(P, Q) sup(d Q) k KEK) =sup(l/a mall:: 1 A: E K.).
In practice, distinguish distributions by Two-Sample Test and estimate MMD from finite samples a distance metric. The estimator of (I,, Q) is defined as follows.
Definition 5. (Estimated MMD) With finite samples X {x:)2x and Y {u>),r
one
estimator of (PP Q) with a kernel family K. is
YX = sup kEK.
+ -
k B3)
2
Σ
k(o,, vy)
(3)
X 2,1=1
nl
=-
1x
w==1
3

---

Published as conference paper ICLR 2024
Note that the kernel family contains the same class of kernel, such as a group of Gaussian kernels with different bandwidths (Rx h E R+}. Compared to the single-kemel MMD, the generalized MMD has the following advantages in practice: 1) auto-search for a suitable and robust bandwidth; 2) avoid the distance collapse as & + 0 or + leads to df + 0 (Fukumizu et al. 2009).
3
VANILLA MMD GRAPH KERNEL
3.1 MMD BETWEEN GRAPHS
Graphs stand apart due their node attributes, labels, and edge structures. This distinctiveness suggests that each graph can be viewed as a manifestation of a specific distribution, especially for graphs sharing identical labels. Therefore,
consider set of graphs emerging from specific distribution when they share the same label. From this perspective, we propose the concept graph distribution.
Definition (Graph Distribution) Consider a collection of attributed labeled graphs G == {G; = (V, E,, N,,Y, Y:) Each graph is assigned label through a surjective function G C. The la- bels E (CI....,C ,Ck} represent distinct distributions of node attributes and labels. For a given label C, the graph distribution ppc. is defined with respect to node attribute X, label Y and their combined feature (X,Y) at a specific level I.
We make assumption regarding the properties of node features various levels. Assumption 1. For any I E Rt, the I-level node features in graphs with the same label follow specific distributions. This is represented as:
(x C, CC=
(Y: ( :
((x)0 ((y) c = CC= (x.y)
(4)
To quantify the differences between graph distributions, extend Definition a below.
Definition 7. (MMD between Two Graphs) Given two attributed labeled graphs G1, G2 and a family of positive definite kernels Kc, the l-level squared Maximum Mean Discrepancy between the graph distributions induced by G1, G2 over K. is defined as follows
(G l = (P12 p/(2) sup
1uy0s 1 kex).
(5)
For Z = (x, Y). the squared MMD captures overall discrepancy between graphs by considering both node attributes and labels. The distance focuses the discrepancy between node attributes when Z X or node labels when Z Y.
3.2 VANILLA MMD-GK
(see Appendix C to estimate In this section, we introduce MMD-Graph Kernel, delineated in Algorithm (see
the similarity between two graphs without information in graph labels. For convenience, we denote the graphs by G, = (X,, YI, and G2 = (X,, Y2, U2). where the graph structures or the edge information are encoded by the normalized and self-looped adjacency matrices U1 and U2 (see Definition
Key Steps: The model employs an embedding aggregation mechanism to iteratively update these node representations till L levels. Specifically, at each level the node representations to the normalized adjacency matrix. Subsequently, the model utilizes MMD to quantify the dissimilarity
updated according
between two sets of node representations, z((0) with size of n, and z(!) with size of n2. The squared
4

---

Published as conference paper ICLR 2024
MMD is estimated using family of Gaussian kernels K. described as follows:
1 a1 Σ 2,1=1
n2
2 n1.
(Z )
sup kEk
Σ 12 a,==1
k( 23.2)
(6)
1 35'=1
Note that dx a distance metric that satisfies the metric space axioms (e.g. triangle inequality). By default, a Gaussian kernel parameterized by bandwidth h > 0 is employed for this purpose. The kernel function measures the similarity between two node representations 2; and 2j, and defined as k(z;, = exp
E: R;=a; hx
Finally, we obtain graph kernel as
SL (G1, G2) exp (Z )
(7)
where > 0 is a hyperparameter. This kernel serves as a metric for comparing and quantifying the similarity between different graphs. Since dæ is a distance metric in Hilbert space and the exponential function positive and monotonic increasing, $L is strictly positive-definite kernel.
3.3 ROBUSTNESS ANALYSIS
We conduct the robustmess analysis of the vanilla MMD-GK. As mentioned by O O'Bray et al. (2021), a suitable metric such as MMD should be robust to small perturbations. We need to find an ideal upper- bound function of the amplitude of the perturbation taking effects in the metric. Let Ax, Ay. and A be some perturbations
node attributes, node labels, and graph structure and denote the perturbed graph as G (A + AA,AAAAAA X + Ax,Y Y + Av). To simply notations, we let Z = =X,Y) and AS =
Theorem 1. For any two graphs G1, G2. without loss of generality, suppose n1 122 and the minimum node degrees of G1, G2 are both a. Suppose ||Aillss BA. |Xill2 fx, ||ill2s By, and [Zills n7. = 1,2. Denote the effects of structural perturbation as k min(1TA and DD; = diag(1 (A, +
A Ax) - ior 1,2. Then the following inequality for MMD-GK holds
RG < (G ,,! +
2eah
(242, +242, + +n(A + +c,)) + E (Aa, + Acs))
122
hT
V
where A 000 2n 1B1l 1ta
(0 l12) Il |F for 1,2 c 2(1 + ((1
(Bx + By), ), and h is the optimal kernel bandwidth among family K..
In the theorem, the norm assumptions by fx. By, and 1) are quite standard. AD, quantifies the perturba- tion on node degrees and is zero if A = 0. The bound is bi-quadratically with r). Due to space limitation and the presence of Theorem 2
we defer the detailed discussion to Appendix C.I
4 DEEP MMD-GRAPH KERNEL
We propose an extension termed Deep MMD-Graph Kernel (Deep MMD-GK), which enhances the model's
flcxibility and expressiveness. In Algorithm it introduces trainable parameters W := {[w()) ) into the embedding aggregation step, allowing the model to leam optimal transformations of node representations based on the graph structure. The loss function of Deep MMD-GK depends on the availability of graph labels. To train the model in supervised manner, we adopt the supervised version of InfoNEC loss function.
5

---

Published as conference paper ICLR 2024
Algorithm 1: Deep MMDD-Graph Kernel
Input : : ( L, K (with parameters {h+))e) 2, [C (0 if unsupervised), o. Output: Similarities {s(G,, G2) (,,)), Jizy and model parameters (W(H).
Initialize [ and _ (X,, Y,), for i ,, N.
2 repeat
3
for = 1 to L do
for to N do
2 t U (1 w(()
// Embedding Propagation with Parameters w(()
end for end for
7
for 1 to N 1 do
for j = to do
Compute (Z 1) using Eq. with z _2 K. // MDD (G,,, G,)² exp (2) 2/41) // Distance-to-Siiilariyy
11
end for end for
(W(0)2 Backpropagation((4. (( G;) (C.) // Update Parameters until stop criterion is reached 16 return {s(Gr, Jies and {WO)
Specifically, inspired by (Oord et al. 2018),
the following Supervised Contrastive Loss (SCL):
LSCL. (o), = ETo=c
log Sij - log TiC.Eo + Σ IIa.cc.jsu
(8)
When all training graphs unlabeled, can still learn Deep MMD-GK using the following two loss functions. The first one an Unsupervised Contrastive Loss (UCL), which modification of SCL. where the negative samples come from the least similar pairs in each epoch, i.e.,
LECL (W)== = Σ Tayes Ilog Sij - log TI + Σ 11o
(9)
b
where the sets S. and S_ contain the most and the least similar pairs, respectively. training data B, there is hyparameter À balancing the sizes as |= | of UCL is that it facilitates the learning of discriminative features from of graphs. The second choice of unsupervised loss is the following KL Divergence adapted from (Xie et al. 2016)
For each batch of [B The primary benefit
(w)(WW) (L(s,
(10)
2 En Tfy and f, E, Sij are soft cluster frequencies. By minimizing the KL Divergence, the model learns to adjust its embeddings to better reflect the natural cluster property the data.
where b/g
4.1 ROBUSTNESS ANALYSIS
analyze the robustness of Deep MMD-GK. For Deep MMD-GK, the robust- ness not only shows the sensitivity of the kernel to noise or perturbation but also implies the generalization ability new graph pairs. For the detailed proof, please refer to Appendix
Similar to Section 3.
D.2 D.2
6

---

Published as a conference paper ICLR 2024
Theorem For any two graphs G1, G2. without loss of generality, suppose n1 = n2 = 72 and the minimum node degrees of G1, G2 are both a. Suppose for iori=1 = 1, || 8A. X2 3x.1lVil22 By, | t,,
continuous. Denote the effects of structural perturbation as min(1 A..). Then the inequality for Deep MMD-GK holds:
|| 1125 Swes. 11, L, and the activation funicioiionfunctionn a is p-pisschitz
Re & ,.!
2ca
(24)) +240. + +n(AG, +G,)) 6 vn
(Ac, + AAa))
1 +
h4
where Ac. = =( (Ttttic) ) IT BuCc (BA 112) 1122 (V(BA+ 14A.12)) B3 1-1
<= a0(1+a)=(11 Bax + By), and h is the optimal kernel bandwidth among kernel family K.
The theorem implies how the perturbed distance metric deviates from the original: 1) the deviation in Deep MMD-GK grows bi bi-quadratically with || 2) the deviation would be affected by || || growing expo- nentially with power of 3) when A A occurs, also amplifies the perturbation | ; 4) Dg, and DGa take an interaction effect in contaminating Deep MMD-GK; 5) the deviation is the most significant when
n +A,,1 6) larger h implies smoother kernel that may be more robust perturbations.
Besides, the bound can be used evaluate the generalization ability of Deep MMD-GK. Specifically, given a test pair G₁, Gz,, we find their closest graphs, denoted by G1, G2 in g. Then according to Theorem 2 + A, where Á is small provided that G1, G2 are similar to G₁ G2 in terms of the adjacency matrices and node features. Note that the robustness-based generalization framework (Xu & Mannor 2012) is not applicable to our method, where the training data (graph pairs) are non-i.i.d
(GT) G2 S (G G.
4.2 GENERALIZATION ERROR BOUND OF SUPERVISED LEARNING
Suppose W are known, Algorithm| I with SCL is guaranteed with uniform stability parameter w (see Theo- rem 5 of Appendix F Let [[()) be the empirical risk, defined by Eq. (E [<(W)] N(N-1) CSCL (W))
and Tet E [[(W)] be the true risk. According to (Bousquet & Elisseeff 2002; Feldman & Vondrak 2019).
the estimation error of supervised loss has a high-probability generalization bound that for some constant e and any 8 (0, 1). the following inequality holds:
Pr [[([])]] E [((W)]] 2 (
log (1/)) N
+
<
(11)
We see that a smaller w (higher stability) leads to a tighter generalization error bound. Note that the objective is highly nonconvex and the optimal W are hard to obtain, thus will work in the future find the explicit form of the generalization bound.
4.3 COMPUTATIONAL COMPLEXITY ANALYSIS
The theoretical computational complexity of vanilla and Deep MMD-GKs shown by the following two theorems (proved in Appendix G
Theorem 3. The MMD-GK using kernels KC on a pair of graphs G and G', with L-level of d-dimensional node features, can be computed in ( + xn? where n is the number of nodes, m is the number of edges, and is is the size of the kernel family, Le. k = [K] For N graphs, all pairwise MMD-GKs are computed in ON Lmdd xn??d d).
7

---

Published as conference paper ICLR 2024
Table 1: Comparison the computational complexity of selected graph kernels regarding support for node- labeled and node-attributed graphs. & is the size of the largest subgraph considered. h is the maximum distance between the root of the neighborhood subgraph/subtree pattern and its nodes.
Graph Kereel
Node Labels
Node Attributes
Complexity
Graphlet
O(n*) O(n") O(hm + hn) O n log(n))
Shortest Path
Weisfeiler-Lehmann Subtrce (Shervashidze et al. 2011
Wasserstein Weisfeiler-Lchman ( (Togninall al. 2019
MMD-GK
V
OiLmd xn'd)
Deep MMD-GK
O Lmnd + kn
Theorem 4. Suppose the widths of the hidden layers of the neural network are (dd). The Deep MMD- GK using kernels K. a pair of graphs G and G', with L-level of d-dimensional node features, can be computed in O( + Landd + kn²d), where n is the number of nodes, m is the number of edges, and k. is the size of the kernel family, i.e. |K]. For N graphs, all pairwise Deep MMD- GKs computed in ONN Lnd? + Lmmd + _22RRnn Rndd).
Table 0 shows that our MMD-GK and Deep MMD- MMD-GK competitive with other kernels in terms of com- putational complexity. Generally, we set a K s.t. Rd < n, so the MMD-GK better in complexity than the Wasserstein Weisfeiler-Lehman graph kernel, when holding equal h. Note that the Weisfeiler-Lehman Subtree graph kernels scale linearly with the number of nodes; therefore, this method is faster than our kernels. The time cost comparison reported in Appendix
5 RELATED WORK
The contents in Appendix A
6 EXPERIMENTS
The proposed methods are compared with state-of-the-art graph kemells and GNNs in both graph classifica- tion and graph clustering, on five benchmarks including DHFR, BZR, MUTAG, PTC_FM, and PROTEINS from (Kersting et al. 2016). Please see Appendix H for more details on configurations. We tuned the hyperparameters of all methods and report their best performances (detailed in Appendix(K)
Classification Accuracy Table 2 shows that our methods always score high in graph classification. The vanilla MMD-GK, while not always achieving top scores, is competitive, especially on DHFR and MUTAG. The unsupervised and supervised Deep MMD-GKs generally demonstrate superior performance. They not only outperform traditional graph kernel methods but also surpass some of the advanced deep learning-basee models on BZR, MUTAG, and PTC_FM.
Clustering Scores Table the clustering accuracy (ACC), Normalized Mutual Information (NMI, and Adjusted Rand Index (ARI). Our MMD-GK and Deep MMD-GK, show significant improvement over graph kernels and GNN-based methods InfoGraph (Sun et al. (019)) and GraphCL (You et al., 2020) fol- lowed by spectral clustering. Particularly, the Deep MKD-GK (unsupervised) exhibits consistently high performance across all datasets. On BZR, it achieves 0.757 NMI and 0.809 in ARI while the baselines failed provide meaningful clustering results in terms of NMT and ART.
Practical Insights /) MMD-GK: In general, as increases, the performance tends to improve at first, reaching peak. Beyond certain value of I, the performance starts to decline plateau. For all three
8

---

Published as a conference paper ICLR 2024
Table 2: Graph classification accuracy. Deep MMD-GK (unsupervised) is trained by LKL or LUCL. of which the better is showed. Deep MMD-GK (supervised) is trained by LSCL. The best score each dataset is underlined. We highlight our methods that exceed the baseline by using bold text.
Method
BZR
DHFR
MUTAG
PTC_FM
PROTHINS
Gruphlet Kernel
0.788 + 0.005
0.609 +: 0.001
0.665 0.009
0.610 0.002
0.714 0.003
Shortest Path
0.788 1 0.033
0.603 1 0.006
0.782 0.041
0.639 0.022
0.758 1 0.006
Seisfeiler-eehmae
0.785 1 0.006
0.683 0.111
0.788 1 0.048
0.645 0.030
0.755 1 0.002
Wasserstein WL WL (Togninalli et al. 2019
0.785 + 0.006
0.793 + 0.029
0.788 + 0.048
0.663 + 0.030
0.755 + 0.002
DGCNN (Zhang et al. 2018
0,844 # 0.002
0.793 # 0.056
0.873 + 0.015
0.603 00066
0.772 = 0.009
DGK Yanardag & Vishwanalhhan 2015
0.831 1 0,005
0.6411 0.009
0.874. 0.003
0.645 1.000
0,726 1 0.005
GNTK Dur 2019
0,836 + 0.029
0.735 1: 0.007
0.890 0.009
0.699 0.001
0,756 + 0.042
DeepMap Ye al. 2020
0.890 + 0.048
0.022 0.852
0.895 0.031
0.652 0.056
0.762 + 0.029
MMD-GK
0.788 + 0,005
0,828 + 0.034
0.819
0.073
0.665
0.009
0.750 = 0.015
Deep MMD-GK (unsupervised)
+ 0.111
0.836 + 0.042
0.910 0.026
0.667
0.028
0.754 + 0.023
Deep MMD-GK (supervised)
0.910 0.111
0.848 0.091
0.915 0.065
0.668 0.031
0.776 0.025
measures (ACC, NMI, and ARI) in the graph clustering task, Figures 4 and 6 in Appendix T illustrate that there's 's a notable fluctuation in performance concerning changes in T. The sensitivity to / indicates that the method captures different levels of structural and attribute information from the graph / changes. 2) Deep MMD-GK: When graph labels are unavailable, unsupervised Deep MMD-GKs outperform vanilla MMD-GK. In addition, unsupervised Deep MMD-GKs trained by the loss LKL at higher (e.g. 4) is more effective and stable than LUCL across all benchmarks.
7 CONCLUSION
We have proposed MMD-baser graph kernels for calculating the similarity be- tween graphs. MMD-GK and Deep MMD-GK directly compare the intrin- sic distribution between two graphs via Maximum Mean Discrepancy. The key steps of our approaches are embedding aggregation, distance-to ceatnne-tt-ssmmiie tomiiiaarr, and for the deep model, updating parameters a supervised or unsupervised manner. The empirical results show that our mod- els outperform the classical graph kernel and even GNN methods significantly in the tasks of graph clustering and classifi- cation. We also contribute theoretically by providing upper bounds for MMD- GK and Deep MMD-GK in robustness analysis and analyzing the generaliza- tion error bound for supervised learning. Future work may focus on improving the scalability of our methods and providing better generalization error bounds.
Table 3: Graph clustering results. The best score on each dataset is underlined. We highlight our methods that exceed the baseline by using bold text.
Method
Metric
BZR
DHFR
MUTAG
PTC.FM
PROTEINS
ACC
0.753
0.567
0.771
0.928
0.622
Graphlet Kernel
NMI
0.020
0.003
0.143
0.036
0.053
ARI
0.079
0.006
0.234
0.039
0.027
ACC
0.654
0.679
0.676
0.962
0.604
Shortest
0.005
0.027
ARI
.0.199
.0.07
00.188
0.021
0.041
ACC
0.767
0.666
0,548
0.928
0.582
Weisteiker-Lehman
NMI
0.014
0.007
0.136
0.036
0.021
ARI
0.035
0.000
0.176
0.039
0.026
ACC
0.735
0.658
0.726
0.620
0.732
InfoGruph
NMI
0.036
0.032
0.287
0.021
0.132
ARI
0.050
0.005
0.199
0.046
0.124
ACC
0.729
0.652
0.732
0.621
0.728
GraphCL.
0.140
ARI
0.035
0.003
0.234
0.034
0.115
ACC
0.807
0.614
0.707
0.633
0.730
MMD-GK
NMI
0.095
0.042
0,141
0.034
0.144
ARI
0.232
0.004
0.168
0.060
0.207
Deep MMD-GK
ACC
0.952
0.689
0.846
0.647
0.752
(unsupervised)
NMI
0.757
0.182
0.468
0.076
0.333
ARI
0.809
0.137
0.476
0.066
0.345
9

---

Published as a conference paper ICLR 2024
ACKNOWLEDGEMENTS
This work was supported by the National Natural Science Foundation of China under Grant 6o.62376236, the General Program 11220200324130200000 of Shenzhen Fundamental Research, the research funding T00120210002 of Shenzhen Research Institute of Big Data, and the funding UDF01001770 of The Chinese University of Hong Kong, Shenzhen.
REFERENCES
Tero Aittokallio and Benno Schwikowski. Graph-based methods for analysing networks in cell biology. Briefings in bioinformatics, 7(3):243-255, 2006.
László Babai. Graph isomorphism quasipolynomial time. Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pp. 684-697, 2016.
Karsten M Borgwardt and Hans-Peter Kriegel. Shortest-paid -atts kernels on graphs. In Fifth IEEE international conference on data mining (ICDM pp. 8-pp. IEEE, 2005.
Karsten Michael Borgwardt. Graph kernels. PhD thesis, Imu, 2007.
Olivier Bousquet and André Elisseeff. Stability and generalization. The Journal of Machine Learning Research, 2:499-522 526, 2002.
Chih-Chung Chang and Chih-Jen Lin. Libsvm: a library for support vector machines. ACM transactions on intelligent systems and technology (TIST), 203 2011.
Samantha Chen, Sunhyuk Lim, Facundo Mémoli, Zhengchao Wan, and Yusu Wang. Weisfeiler-lehman meets gromov-wasserstci. In International Conference on Machine Learning, pp. 3371-3416. PMLR, 2022.
Xiaohui Chen, Xu Han, Jiajing Hu, Francisco Ruiz, and Liping Liu. Order matters: Probabilistic modeling of node sequence for graph generation. In International Conference on Machine Learning, pp. 1630-1639. PMLR, 2021.
Etienne Cuvelier and Marie-Aude Aufaure. Graph mining and communities detection. Business Intelligence: First European Summer School, eBISS 2011, Paris, France, July 3-8, 2011, Tutorial Lectures 1, pp. 117- 138. 2012.
Hanjun Dai, Azade Nazi, Yujia Li, Bo Dai, and Dale Schuurmans. Scalable deep generative modeling for sparse graphs. In International conference on machine learning, pp. 2302-2312. PMLR, 2020.
Simon S. Du, Kangcheng Hou, Barnabás Póczos, Ruslan Salakhutdinov, Ruosong Wang, and Keyulu Xu. Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernels, chapter 0, pp. 1. Curran Associates Inc., Red Hook, NY, USA, 2019.
Vitaly Feldman and Jan Vondrak. High probability generalization bounds for uniformly stable algorithms with nearly optimal rate. In Conference on Learning Theory, pp. 1270-1279. PMLR, 2019.
Holger Fröhlich, Jörg K Wegner, Florian Sieker, and Andreas Zell. Optimal assignment kernels for attributed molecular graphs. In Proceedings of the 22nd international conference on Machine learning, pp. 2005.
Kenji Fukumizu, Arthur Gretton, Gert Lanckriet, Bernhard Schölkopf, and Bharath K Sriperumbudur. Ker- nel choice and classifiability for rkhs embeddings of probability distributions. Advances in neural infor- mation processing systems, 22, 2009.
10

---

Published as a conference paper ICLR 2024
Thomas Gärtner, Peter Flach, and Stefan Wrobel. On graph kernels: Hardness results and efficient alter- natives. In Learning Theory and Kernel Machines: 16th Annual Conference on Learning Theory and 7th Kernel Workshop, COLT/Kernel 2003, Washington, DC, USA, August 24-27, 2003. Proceedings, pp. Springer, 2003.
Hashem Ghanem, Nicolas Keriven, and Nicolas Tremblay. Fast graph kernel with optical random fea- tures. In ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 3575 3575-3579. IEEE, 2021.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pp. 1263-1272. PMLR, 2017.
Michelle Girvan and Mark EJ Newman. Community structure in social and biological networks. Proceedings of the national academy of sciences, 99(12):7821-7826, 2002.
Arthur Gretton, Karsten M Borgwardt, Malte Rasch, Bernhard Schölkopf, and Alexander Smola. A kernel two-sample test. The Journal of Machine Learning Research, 13(1):723-773, 2012.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
Linus Hermansson, Fredrik Johansson, and Osamu Watanabe. Generalized shortest path kernel on graphs In Discovery Science: 18th International Conference, DS 2015, Banff, AB, Canada, October 4-6, 2015. Proceedings 18, pp. 78-85. Springer, 2015.
Wolfgang Huber, Vincent J Carey, Li Long, Seth Falcon, and Robert Gentleman. Graphs in molecular biology. BMC bioinformatics, 8(6):1-14, 2007.
Kristian Kersting, Nils M. Kriege, Christopher Morris, Petra Mutzel, and Marion Neumann. Benchmark data sets for graph kernels, 2016. / cs tortdorrmundd... de
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Yoshua Bengio and Yann LeCun (eds.), 3rd International Conference Learning Representations, ICLR 2015. San Diego, CA, USA May 7-9, 2015, Conference Track Proceedings, 2015. URI. httt::://axxwv.org///aaa
1412. 6980
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference Learning Representations, 2016.
Nils Kriege and Petra Mutzel. Subgraph matching kernels for attributed graphs. In Proceedings of the 29th International Coference on International Conference on Machine Learning, pp. 291-298, 2012.
Nils M Kriege, Pierre-Louis Giscard, and Richard Wilson. On valid optimal assignment kernels and appli- cations to graph classification. Advances in neural information processing systems, 29, 2016.
Nils M Kriege, Christopher Morris, Anja Rey, and Christian Sohler. A property testing framework for the theoretical expressivity graph kernels. In IJCAI, pp. 2348-2354, 2018.
AA Leman and Boris Weisfeiler. A reduction of a graph to a canonical form and an algebra arising during this reduction. Nauchno- aecniceeTee Informatsiya, 2(9):12-16, 16, 1968.
Giannis Nikolentzos, Giannis Siglidis, and Michalis Vazirgiannis. Graph kernels: A survey. Journal of Artificial Intelligence Research,
2021.

---

Published as a conference paper ICLR 2024
Leslie O' O'Bray, Max Horn, Bastian Rieck, and Karsten Borgwardt. Evaluation metries for graph generative models: Problems, pitfalls, and practical solutions. In International Conference on Learning Representa- tions, 2021.
Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding. arXiv preprint 1007.0:8007.0722 2018.
Victor M Panaretos and Yoav Zemel. Statistical aspects of wasserstein distances. Annual review of statistics and its application, 6:405-431, 2019.
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn Machine learning in Python. Journal of Machine Learning Research, 12:2825-2888 2011.
Andrea Roncoli, Aleksandra Ciprijanović, Maggie Voetberg, Francisco Villaescusa-Navaro and Brian Nord. Domain adaptive graph neural networks for constraining cosmological parameters across multi- ple data sets. arXiv preprint arXiv:2311.00 2tth:23311.018888 2023.
Till Hendrik Schulz, Tamás Horváth, Pascal Welke, and Stefan Wrobel. A generalized weisteiler-Iehman graph kernel. Machine Learning, 111(7):2001-229) 2022.
Nino Shervashidze, SVN Vishwanathan, Tobias Petri, Kurt Mehlhorn, and Karsten Borgwardt. Efficient graphlet kernels for large graph comparison. In Artificial intelligence and statistics, pp. 388-495. PMLR, 2009.
Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mehlhorn, and Karsten M Borgwardt. Weisfeiler-lehman graph kernels. Journal of Machine Learning Research, 12(9), 2011.
Alexander Smola, A Gretton, and K Borgwardt. Maximum mean discrepancy. In 13th international conference, ICONIP, pp. 3-6, 2006.
Bharath K. Sriperumbudur, Kenji Fukumizu, Arthur Gretton, Bernhard Schölkopf, and Gert G. Lanckriet. On the empirical estimation of integral probability metrics. Electronic Journal of Statistics, 6(none): : 1599, 2012.
Mahito Sugiyama and Karsten Borgwardt. Halting in random walk kernels. Advances in neural information processing systems, 28, 2015.
Fan-Yun Sun, Jordan Hoffman, Vikas Verma, and Jian Tang. Infograph: Unsupervised and semi-supervised graph-level representation learning via mutual information maximization. In International Conference on Learning Representations, 2019.
Ziheng Sun, Chris Ding, and Jicong Fan. Lovász principle for unsupervised graph representation learning. In seirth-eeventh Conference Neural Information Processing Systems, 2023.
Matteo Togninalli, Elisabetta Ghisu, Felipe LJinzres-López, Bastian Rieck, and Karsten Borgwardt. Wasser- stein Leimmnn graph kernels. Advances in neural information processing systems, 32, 2019.
Vladimir Vacic, Lilia M lakoucheva, Stefano Lonardi, and Predrag Radivojac. Graphlet kernels for predic- tion of functional residues in protein structures. Journal of Computational Biology, 17(1)555-2,, 2010.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint ar:iv: 1700v: 2017.
12

---

Published as a conference paper ICLR 2024
S Vichy N Vishwanathan, Nicol N Schraudolph, Risi Kondor, and Karsten M Borgwardt. Graph kernels. Journal of Machine Learning Research, 11:10111124,, 2010.
Zhihao Wu, Zhao Zhang, and Jicong Fan. Graph convolutional kernel machine versus graph convolutional networks. Thirty-seventh Conference on Neural Information Processing Systems, 2023.
Junyuan Xie, Ross Girshick, and Ali Farhadi. Unsupervised deep embedding for clustering analysis. In International conference machine learning, pp. 478-487. PMLR, 2016.
Huan Xu and Shie Mannor. Robustness and generalization. Machine learning, 86:391-423, 2012.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanic Jegelka. How powerful are graph neural networks?
arXiv preprint arXiv:1810.0022 2018.
Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. In Proceedings of the 21th ACM SICKDD international conference knowledge discovery and data mining, pp. 1365-1374, 2015.
Wei Ye, Omid Askarisichani, Alex Jones, and Ambuj Singh. Learning deep graph representations via con- volutional neural networks. IEEE Transactions on Knowledge and Data Engineering, 34(5):2288-2279, 2020.
Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. Advances in neural information processing systems, 13:5812-5823, 2020.
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification, In Proceedings of the AAAI conference on artificial intelligence, volume 32, 201 88
A RELATED WORK
A.1 GRAPH SIMILARITY
Graph Similarity is a fundamental concept in graph theory and deals with the problem of determining how alike two or more graphs are. A foundational notion here is Graph Isomorphism (Babai] 2016). Two graphs are deemed isomorphic if they contain a one-to-one correspondence between their vertices, such that the adjacency between vertices is preserved. Delving into Graph Kernels, several kernels exist with different methods of operation. The Shortest Path Kernel (Borgwardt Kriegel| 2005 Hermansson et al. 2015), for instance, examines all pairs of shortest paths in two graphs and identifies paths of the same length. Graphlet Kernels (Siervashidze et al., 2009; Vacie et al. 2010 work by counting the number of small subgraphs, known as graphlets, that are isomorphic between two larger graphs. Considering attributed graphs, Kriege and Mutzel Mutzel|Kriege & Mutzel (012)) proposed the subgraph matching kernel which is based on structure- preserving bijections between subgraphs. Another interesting method is the Random Walk Kernel (Gärtner let al.) 20033 Sugiyama & Borgwardi 2015) which gauges similarity based on the number of random walks two graphs can share, effectively calculating the likelihood that random walk in one graph mirrors a walk Kernel (Shervashidze et al., 2011) employs the Weisfeiler-Lehman isomorphism test (Leman & Weisfeiler, 1968). This involves a continuous refinement of vertex labels based on the labels of neighboring vertices, and the kernel then counts the common labels between the two graphs. Besides, the idea identify the best possible matching has been used in graph kernels, from early optimal assignment kernel (Fröhlich et al. (2005), to many variants such Weisfeiler-Lehnee kernel (Kriege et al., 2016). A notable trend in recent research has been the modification of Weisfeiler- Lehman (WL. kernels using Wasserstein distances (Togninalli et al. 2019 Chen et al. 2022 Schulz et al.) 2022). [Tgninalli et al. (2019) integrated the Wasserstein distance into the WL framework, allowing for a more refined comparison of graphs, particularly those with continuous node attributes. Chen et al. (2022)
in the other. The
optimal assignment
13

---

Published as a conference paper at ICLR 2024
proposed a novel concept of WL distance, polynomial time computable metric that is sensitive to more subtle graph differences than traditional WL methods
With the advent and dominance of deep learning, efforts have been made to harness neural networks for deriving learned representations of graphs. The likeness between two graphs can then be determined by comparing these overarching representations. A notable subtype of graph neural networks is the Graph Convolutional Networks (GCNs) (Kipf & Welling (016) which employ form of convolution to assimilate information from neighboring nodes. Another method, Deep Graph Kernels (DGK) (Yanardag & Vish- wanathan 2015), combines deep learning's ' expressive power with the interpretability of traditional graph kernels by utilizing deep learning for graph representation and subsequently applying traditional kernel methods to these representations, Du et al. (219)) presented Graph Neural Tangent Kernels (GNTK) which correspond to infinitely wide multi-layer GNNs trained by gradient descent. Theoretically, GNTKs prov- ably learn class of smooth functions on graphs. Ye et al. (2020) proposed a framework called MeepMap learn deep representations for graph feature maps. DeepMap generates aligned vertex sequences and builds each vertex's receptive field learn a dense and low-dimensional vector that captures complex high-order interactions in a vertex neighborhood.
A.2 MAXIMUM MEAN DISCREPANCY
At its core, MMD (Smola al. 2006) measures the distance between two distributions, providing lens through which we can compare them. It leverages the power of Reproducing Kernel Hilbert Space (RKHS), enabling a non- con-aarmettric comparison between distributions. The distance computed by taking samples from two distributions and evaluating their difference in the RKHS. With the aid of a kernel function (often Gaussian), MMD evaluates how close the mean embeddings of these samples are in the RKHS. If the em- beddings are similar, it's an indication that the two samples likely come from the same distribution. Taking advantage of it, Gretton et al. (2012) demonstrated that MMD forms the basis for a kernel-based two-sample test. In situations where traditional methods, such as the Kolmogorov-Smiroo may struggle (especially in high-dimensional settings), the MMD-based test can offer greater power. Com- bining with graph kernel, Borgwardt (2007) obtain the two-sample test for sets of graphs. It is important to note that, Borgwardt| (2007) just proposed to estimate the MMD for two-sample test with existing graph kernels, rather than to design graph kernel with MMD) method. When it comes designing a novel graph kernel, a recent work focusing on speeding up Graphlet kernels, incorporated an MMD metric when showing the effectiveness of their kernel design (Ghanem et al. 2021). However, the kernel itself does not require calculating MMD. Instead, MMD is only used to demonstrate the classification power of their embeddings.
or Mann- Mann-Whitney Whitney U test,
Some recent studies have integrated MMD into the realm of GNNs. One key application is in the comparison of graph strucustt data to evaluate generated graphs (Dai et al.) 2020 Chen al.) a (021). for instance, when determining if two graphs exhibit similar structural properties or when comparing the node embeddings generated by GNNs from different graphs. MMD also aids in the training of GNNs (Roncoli et al., 2023). ensuring that the distribution of the generated node embeddings aligns well with the target distribution. This can be especially crucial semi-supervised settings where labeled data is sparse but there's s a need to ensure that the graph's 's overall structure is well captured. Recently, O' O'Bray et al. (202T) critically evaluated the use of MMD in graph generative model comparison, proposing practical recommendations for its effective application.
In our approach, we introduce a novel graph kernel that uniquely integrates the concept of Maximum Mean Diserepancy (MMD) with Graph Neural Networks (GNNs), differing from existing efforts that either apply MMD for two-sample tests using traditional graph kernels or use MMD to evaluate the performance of GNNs without directly incorporating it into the kernel design.
14

---

Published as conference paper ICLR 2024
B
EXAMPLE ILLUSTRATION
G1
G2
G3
G4
G5
G6
v11
v21
v31
v41
v51
v61
v12
v22
v32
v42
v43
v:2
v62
v13
V23
v33
v44
v45
v46
v47
V53
v63
v14
v24
v34
v54
v64
v35
v55
v65
Figure 2: Graph Illustration: common scenario and counter-examples
To illustrate the concept of Maximum Mean Discrepancy (MMD) between graphs and its behavior, we present some toy examples. In each example, consider a pair of attributed labeled graphs and estimate the supremum over MMDs (dx) using class of Gaussian kernels with different bandwidths.
Consider two graphs, G1 and G2, with the same graph structure but different node features. Both graphs have the same edges (E1 Ez), but the attributes of their nodes are different (X1 * X2). When estimating the MMD between their node attributes X1 and X2, the supremum over the Gaussian kernel may cause dx to be relatively large, indicating notable discrepancy between the node attributes.
Common Scenario:
The MMD measures the discrepancy between the distributions of node features and labels of two graphs the 1-level, using the kernel family K. to compare individual node features. two graphs are identical, their MMD will be zero, there will be difference in the node characteristies between the graphs. However, the estimated MMD may appear very close to zero even when the two graphs are actually distinct, i.e. dx se 0 when X1 * X2 or Y1 * Y2 or En * Eg. This is because the limited number of nodes and edges the graphs might not fully capture all the differences between them, leading potentially underestimated MMD values. Let's consider the counter-examples.
Counter-example 1: Consider two graphs, G3 and G4. where G3 contains a cycle and G4 contains structure. Although they have different graph structures (Es j E4), when estimating the MMD between their node features X3 and X4, the supremum over the Gaussian kernel with very large bandwidth may lead to small dæ due to the smoothing effect. This can mistakenly suggest that G3 and G4 are similar in terms of their node features.
have attributed labeled graphs, Gs and GG. with the same node features (X;- = X&) and almost identical labels (Y/s x Y6). Additionally, the edge structures of the two graphs also very similar, but there exist few edges that differ between them (Es Eg
Counter-example 2: Suppose
15

---

Published as a conference paper ICLR 2024
with some minor differences). Now, let's consider the MMD different levels compare the distributions of node features, labels, and edge structures:
At a low level, when ((Xs. Ys). (Xs, Y6)) might still be very close to zero, indicating high similarity at the local neighborhood level.
1: this case, the MMDs Re) (Y,, Ya), and
2. At a higher level, c.g. = 5: As we increase the level I, the aggregated node features and labels capture a more global perspective of the graph structure. However, since the graphs have almost identical node features and labels in most parts, the MMD might still not be able fully capture the differences due to the few differing edges.
These counter-examples demonstrate that the behavior of MMD between graphs can be influenced by the level 1 of aggregation and the choice of kemell bandwidth. To alleviate the problem in the first counter- example, it is better to choose the kernel family K. with large set of bandwidths. As for the paradox within the second counter-example, there is no "one-size-fits-ll solution, because in some cases (e.g. unsuper- vised tasks), higher levels of aggregation might provide more informative comparisons, while in others (e.g. supervised tasks), local neighborhood information could sufficient. It is worth noting that an increase in level | may hurt the performance of the MMD graph kernel, since aggregation power would lost when the level exceeds the graph size itself.
C ALGORITHM OF MMD-GK
Algorithm 2: MMD-M Graph Kernel
Input : GGraphs G₁ and G2, number of level T., kernel family IC with parameters (h, [ gamma
Output: Estimated similarity between G1 and G2
1 7 + (X1, Y1) or 2 + +x or z + Y1; (0) + (X2, Y2) or 2 +- X2 or 2 + Y2
2 // kmbeddi ng Propgation
3 for 1= T. do
z(¹) + U, 2 (1-1) and _ Uz 11
5 end for
// Kernel Mapping
7 (2(1)) -(4² Eq. 6 with 200) - K. and (
8 // Destance-to-Simllae
(G1, G2) (- (2 )2)
return 81 (G1,
C.I ROBUSTNESS ANALYSIS
The bound in Theorem 1 provides insights into how the perturbed distance metric (G ) deviates from the original distance metric (G (()). Specifically:
1) the deviation MMD-GK grows bi-quadratically with ||
2) the deviation would be affected by |Alle growing exponentially with power of I;
3) when AA occurs, it also amplifies the perturbation |
4) Ac; and Ac, take interaction effect in contaminating MMD-GK.
16

---

Published as conference paper ICLR 2024
5) the deviation in MMD-GK is the most significant when n 8(Ac; + A
Reason: we take the derivative of Á w.r.t n and observe the critical point.
Ön n(AG, + A + vn (Aa, + Aas)) = (Ac, + AG2 2/n"
(Ac, + AG2) (12)
As I tAo, the increase in leads to larger A, which implies that the error due to e perturbations becomes larger. And n 2 8|āa; +o, the error due to perturbations becomes less significant when increases.
6) larger h implies a smoother kernel that may be more robust to perturbations.
D PROOF FOR THEOREMS
D.I PROOF OF THEOREM II
Proof. For perturbations to node label Y Y + By and node attributes X = X Ax. we can define the perturbation on node features as - = Z + Az, where Az = (Ax. Ay). When we introduce perturbation Aa in A, it will also occurs in D, U, and ultimately takes effect on Z(1 as
z(0 U' A2) 42)= (U') Z + (U')'Az,
(13)
I
where U" = Dr (À + AA)D' and the perturbation D' = diag(1
T (A + AA)). To simplify the further analysis, we denote (1)) = U Z + A za: where the deviation can be expressed as
Az ((U') - U*) Z (U')'AZ.
For this deviation, we have the following lemma (proved in Section E.I
Lemma 1. Suppose the minimum node degrees of G1, G2 are both a, ||A:1|25 BA, ||xill25 3x, |Yillas By, and ||
9,, = 1,2 Denote the effects of structural perturbation as k = min,))AA,)) and
AD. diag(1 T (A; + AA.)) diag(( A,) for 1,2. Then the following inequality holds:
[,3 /llla//laatAAalla) +
+ ((21++1AAA))) ||Az|le-
2 lles 2n
(14)
1 a
1+
Given kernel family K. the estimated generalized MMD between the perturbed G and G/ is (G )()) = supkex de (G() G. where
d1 Σ
22
2 ngg k
d l (
k KZ
KZZ 12.
k(Z k
(15)
72
For the original graphs G and _ the distance can be expressed by replacing Ž with Z in the equation above. Thus, we have the following inequality:
(G ) (G ,,(²)) sup de() (()) sup de (G "
KER
kEK'
(16)
<dh- (G()) ((0) d.- (C , - ) و A
17

---

Published as a conference paper ICLR 2024
where k- arg max dg (G G. Since the difference primarily comes from the perturbation in kernel values, we can expand the expression as
A
2,1
2 + A (1,17)
213
+
n2
Σ
(= 3/27
2/22)) + A (1.5)
2/3)
1,1==1
2
R1,82
<' 23222 + A
7(0 (8,5")
(17)
72
+==1
(1:2)
1
12
2
A
7(1)
(1,2')
k
7 (2)
(J,5")
A
2(1) (i.j)
(1)
22
j.
i,j=1
(1.2)
where Ak* 2 (2, k- (2 2,00 k0 (Z ())
? and A
(1.))
= k- (2 (1) 222) - k2 kz 23²)
(1.2)
Without loss of generality, we take the Gaussian kernel example further discuss the bound. The
bandwidth of k* is denoted as h.
Next, we examine the basic components within the Gaussian kernel as Lemma 2
shows.
Lemma 2. Suppose VG. ||Al2s5 | 3x. Mills By. Then all pairwise distances between l-level nodes of one graph are bounded as
|| _ - 2(1 - a1 + (ax + By).
And all pairwise distances between I-level nodes of two graphs are bounded
| =Sallss 2(1 + a) '(1 + 13,((xx + BB))
Given this and Lemma 4 in later context, both intra- and inter- exponential terms range between
8 4r (1+ (11 (a) + By
since | exp( 11 (1)
0 for all nodes.
Now, let's delve into the deviation in each kernel pairs as below.
Lemma 3. Denote EjaØf = - 20 - e
1|=-2 * (n) - A (0)
A,0 ||. The following inequalities 20,
hold for an arbitrary Gaussian kernel with its bandwidth hyi (a) Ak 20 (i,)')
Fiis'' lx
x 2 2n
exp
== 2 12
j 1,2.
(b) Ak (0) (1,5) (11-
+
e IP)) (1
2 Tx
||
= 20 + + -1)
(.2)
Note that the bound for Σ and its squared term is
Σ E.P 2 4(1++)) + 10) -ا
D S. < | @ A [ (1 3l + 1 @ - A.0
18

---

Published as a conference paper at ICLR 2024
Consequently, the inequalities in Lemma can be expressed as
A 20 (1,
+
8
(1+a) "1 + 3a) + 33
(2)
2
1
(18)
h
[1 + a)
(1+ By B1) 20: -A
200
11+
1
-
A
11
4112
4
+ 1
(1+ 3A) (3x + 3r)
10 - A 4 1p)
and
AK 20 (i.j) 2 (1+
8 Te (1+ (1+ (Bx + +Br)*)
(+14 i1
+ +Agg2
(19)
(122
+ +4(1+a) - + (1 Br 2i,1
+4 00)
Denote E (1+++) By). We can summarize the inequalities as
2 li+te
Ak 200 (1,8) - (1+
kellA ب - a 11 ?1
00 - 200 x..
2/
(20)
Ak* (i.j) 2 [ (1.2)
+
1o2
+ |1+t)
2
2n
By substituting Eq. 20 into Eq.
17
the deviation bounded by a function of Agi
1
n1
2
S
11
+ 2ht
A
n²
2n²
1
+
ngh2
1
+
2ngh4
n2
2
11
-
A
e
112-6
+
2h1
A 2.
A m
(21)
2
d
2
+4
11
2
ningh
ningh3
(0) +,1
Based on Equation 35
and || 12,15 v /nl
A
Il, we can obtain the following inequalities which apply
to every individual graph G. and pair (G1, G2).
Σ
11.
A
n
|1
a
||
e 1))
= 2m. | 2001 12,,1 S 2n Ag.
(22a)
1,37
1,3
12.
n.
2 11
1
A
00
12
<
||A
||
|
m
2n.
| 2000 112 +21 2000 11,,1 S 4n. (An. )22b)
R2.
n2
m2
+
112
A
i
+
Σ
||
A
--
ni
A 2 11,,1 + n2 A 2,00 112,1
(22c)
2,2
< n4
Ag
G2
122 m2
19

---

Published as conference paper ICLR 2024
where Åg. = =2n is bounded
A 1
(
(2 1ta+e
|1Az. I|.. To sum up, the deviation in MMD-GK
1+a
) (G
G2 S
(1
1
+ +
et
[
220 +
m1 )
252 +2252 +
2
62
2
122
2h
112
ni
n
Ac.
G2
+ 4he
(a +
et
(vTido + vT2AG, + Vnina.
2
e2
+
13
72
(23)
If 12 n, we can simplify it
G -.") - - (G
G
2
+
h3 )
et)
)
(252, + tc/n)² + (24 + t//n)
6²
h
2h
n²h
(24)
+
2E
(a. + +ca)) + (Vi(dos + Aoa) +
+-
E) 2)
2
vn
11
n
After further simplification, we eventually have
R - (G c.1) -
(
2ea
(242) +242, +n(AG, + + - (Ac, + Acs)
+
2 h4
vn
(25)
D.2 PROOF THEOREM
Proof. For Deep MMD-GK,
20) = oU ... .U Zww) ... w())
(26)
times
times
Similar to proof of Theorem
D.I
perturbation Aa A, will ultimately takes effect on 2 as
こ OU Az) W())..... ....()))
(27)
times
times
Denote ~ ((1) + A Aza) where the deviation can be expressed as Agn - z( Let a be the minimum node degree of G. we have | & ك (1 aa)
Assume that the norm and ||A (3^ + 1),
so that |U (1 a BA. |1') (1 + a a) (9A + | | where min(1 T AA). and |
UIBS (1 +*)++)*** (18s + |14))2)) - 88). Suppose 2 ك 7,, || Bwnn and the activation
20

---

Published as conference paper ICLR 2024
function p-Lipschitz continuous. Based on Eg. 26 we derive that
12(11))
F (14a)
y-1 II 1-1
Bwio || then
|| 200 |= -
||
Sp (1U')1alA2z 10lp-11++UUU - -U11a112( |
Spswa (1 (1+a+ (Bx + ||a1|12) 12 (3A (Aaul1) -3% 19
1-1
Sp Bw (1 + +k) (Bx
||a122) x0A +
(1A2|IF)
1=1
V(B + 22 33 p² (1+atk)
BA
Σ 1=0
II Swi) 1=+
II 1=1
Swrc 12
1
1-)
II Bww
AzllE++ (BA+ |
Σ 31
(V(AA+1AAall)
*1+ K
(28)
Other things being equal that of Theorem I the deviation in Deep MMD-GK satisfies the following inequality if n1 T/2 n,
2et (242) +242. nn(A +ca) Vn
G - (C c S
(Ac. + Ac.))
112 h4
(29)
where Ag. -(1+0 (1+00=) )TT: Bw()
(1') 1eelle (V(BA AA. 22)
13 1-)
The implications are similar Theorem D that
1) the deviation in Deep MMD-GK grows bi-quadratically with ||Az|l::
2) the deviation would be affected by |Aal|2 growing exponentially with power of
3) when Aa occurs, it also amplifies the perturbation ||az|e IP
4) AG, and Ac, take an interaction effect in contaminating Deep MMD-GK.
5) the deviation in Deep MMD-GK is the most significant when 8(Aa; +Aog)*
6) larger h implies a smoother kernel that may more robust to perturbations.
E PROOF FOR LEMMAS
E.I PROOF FOR LEMMA N
Let a be the minimum node degree of G, we have | 2|555 (1 + -/2
1/2. Suppose ||A||/ SA, then
A (1 + BA). We can obtain
| D 1| (1+a)- BA).
(30)
21

---

Published as a conference paper ICLR 2024
Similarly, we have
11 S II(D)) 113 (1All++++) ( (1+a++)))
(1 + AA + -11All1))
(31)
where = min(1 AA). It follows that
-112=11 (Ā + - AD b112
D-
=1D AD - b:' A - DV ~ AAD 2/ $122
<| A(D -- -D $112 112
<(1 + Ba)((1 ",,,
+| ||all (32)
$2(1+ 22(1+8))(0 300-- 1
||all2
22 ",,,,-/0000000000,,,"000""""""""
$2(1+ + =40001000000bb00000++++11111111
where ||-D112=11 122
/ D D- 2112.
1 BA + A
1-1
x)) 1((aalll))))
1+a -
1-1
1+
1+ BA
1 + BA + A
+ [|21--200000001lllll(0+-+++=1110 112)
Σ
1+a
1+a+0 K
2(1 + BA)lIAD11 12
1 1 3A + ||41l2
1 1 3A
[-i
1 1 3A 11all))))
))
1+a
1+a+*)
1+a+k
1+a
1 l+a+N
2(1 + ADDll
1+ BA
1+ 3A + +|All H-1
<2
+
1+a
1+a+N
1+
1
(33)
The Frobenius norm of the deviation in Azos is bounded as
| z00 |F
-
(34)
22

---

Published as conference paper ICLR 2024
Given Eq. 31 33
and assume || 7), the bound could be expressed as
2(1 + BA)ll l2
|
)
(1+-24
1+a + 1+ BA + +1 + ) + ) I
| g(0) 22
1+a
1 1+a+x
1+a+k
lta+x
2(11 + BA)ll |221114l1
2(1 + 3A) + -|AAal2)) )
1-1
1 DA+ PAtllAlll))
22n
+
1+
1+a
1+a+k
2(1 B^)l D0l1Abl12+1aa0 |A
+ +1 I1+ LAzlle
22
1+a a
1ta+k
4.3 A 1/0|++1|1110 ~||| +
2B3 + ||Aall2)
22n
||az|Lr,
1+a
1+a++
(35)
where inequality used the fact that 34 2
E.2
PROOF FOR LEMMA 3
Lemma 4. ex <1+x+ when x S
First, based on Lemma
we can bound Aliz. (1, as follows:
(1)
||
(1)
(27.1
(1)
(
)|1
||
23r 11?
(0)
Akz00 (i, exp (1)
2,11
211
exp
h&
h&
|| 20) 21
A (
2
(1)
2/.1
(1)
|I||
A 4.
A
201 11
||
(1) (1)
23
11?
< exp
exp
h&
h4
A
A
2
21
11,1
28
(1)
III|
A
A
11 229211
exp
-
exp
hx
he..
E15.9
x
||
(1)
2 112
(
exp
hg
4h2
ha
(36)
where E1.
A
1|
-2,
2,,1
aIIIA 2.
- A mg
The related deduction for Ak Ak2
(j.j")
(2)
is almost the same
36 and hence is omitted.
23

---

Published as a conference paper ICLR 2024
For Aiig (i.j), we have (1,2)
(1)
A
(0)
5.2
(9)
A
1
|| 2/121
Ak 2
(i.5) = exp
1,1
exp
h&
h&
| 2//211 12 + ||
+
A
(0)
|2+1111 (1)
||
(1)
2 exp
2,1
3.3
-2,1
3322
exp
h&
h&
c 3.2
12)
= (1-
2
23,2111
(1)
10 + + 20
11
11
1. 12
h&
312
(37)
where inequality i used the fact ex 1
E.3 PROOF FOR LEMMA 4
Proof. We want to show f(x) > for all x, where f (-00, 0] + R is the function defined by f(x) = x² 1+ + 21 +... xn e" Since f(x) + 00 as -00, f must attain an absolute minimum somewhere on the interval (-.,,
"
1. If f has an absolute minimum at 0, then for all x. fx) 2 f(0)
e 0, so it is proved.
2. If f has an absolute minimum at y for some y < 0, then f(()) = 0. But differentiating f.
('(v) + y + y²
(n 1)1 e -(()) y"
nn
2!
Set n = 2. For all x f.)) f(y) = x + (()
L > 0. Then f(x) = 1 + x + =2
4 - >>
-e>>> 0, which
means that
x² 4
e² 1+++
E.4 PROOF FOR LEMMA 2
Proof. Given that |X | 3x, || By, |D 1/2 2 aa) 1 1125 ||l|
(1 + BA), and
|0|25 (1+a)- (A) in Eq. 30
we then obtain the following upper bound step by step:
||=!0-- ( ||
= -1U,,,0--12 2 - U2,1"1111 211
<IIU, U
<|| <10 1/2 1/-1/2 122 112|2
(38)
<10 -
-1 12112
52(1 + + Br)
24

---

Published as conference paper ICLR 2024
Suppose |X 9x, |Yille By, |1A.1I AA and 1255 (1 a) 1/2 Vi 1,2, we have ||Ul
(1 (1+ BA). Consequently, we then find the same upper bound for || -2j.2 1:
(0)
|| - -
= -IUi,,.U9--- Zi - U2
< |,11,,
< 1P2,:1|||40000010000000111111113 ||00011 11Z2112
(39)
<
== 1 + (y)
<2(1 (0
F GENERALIZATION ERROR FOR SUPERVISED Loss
For the convenience, we write LSCL = I(W,r r) to highlight its dependence on W and r r= (Zu, Cu, Zu, Co), a pair of graph u and v in the training data. Let Wi == {W be the parameters learned from the By removing the i-th element in D with N total pairs of graphs, define D) {ri, Ti-1, Ti+1, r'N] }. To get bounds on the generalization error, consider that stronger notion of stability will allow us to get tighter bounds, one of which is the uniform stability (Bousquet & Elisseeff] 2002 Feldman & Vondrak 2019). The uniform stability of an algorithm determines its stability when one of the training data is removed. The goal is to find w such that for any training set 'D and any pair Tú, the following inequality holds:
training data D through Algorithm |
sup [(W Zu, Z.) ((W Zu. Zo)l5 w {u,0}
Vi (1, (N, .N}
(40)
Theorem 5. Given the parameters are known, and (WD) S T for any pairs of grgrpss u, v, Algorithm 1 with the supervised contrastive loss (Eq. 8) is guaranteed with a uniform stability parameters w as below
4th + 27T 2 log (1++1) 4D,
(41)
where V 7
1/2
d
22 2n + Ao). and the deviation in graph via learned parameters
denoted as AG =1
p
E/=o (liemtss Swite Il w-(') ||F)
1to
bit
Proof. Given that Sue = exp(->dEg) we denote squared MMD & = (WD)) as a function of the parameters learned from the training dataset D.
I(W 2n) 2(W Zu, 2o)l= 7. (Wo.)) - (- (Wz)) +
(42)
Σx exp( 1oap--yda 1 (W + a: Σx CC, exp(->de, (WD))))
log
Σx CC. 1...C exp( -d?, (W))) + a Σx 1 1[ exp( exp(-7d², (W))((WW) (W)))
25

---

Published as conference paper ICLR 2024
Similar to the Eq.
28 we derive that
| 20 S 11 n w
w
Dir
5p(1 + 13 (1 (/Az--nll=l111 Di 11l "|,,0//""0001--"""""=""""1"""""1 - w
Sp(1 + 1/x
&w-0 |l borenlll+++wwe - 1
Sp'
3A
II
B
Wwto zx
||az||+
Σ
d (T+
Ba
II
wio II Ilw Due - w |1
1+
1=1
1=0
1=1+)
PBA
IIll- Du. - w |1
Wit
1+
j=0
1=++)
(43)
And eventually, we obtain the worst-case difference as
E sup {a
d (WDw) - (WD)
2ct
(24d) + +240, + +n(AG, + +
(Ac, + Aoi))
$ sup
h22
+
h4
vn
(44)
{,
4
+
2ea
(2
+200, +n(Aa, + 20 Vn
(Dcr + Acx))
h
where Ac. =
p&A
Σ/=
(II'=14) P Pwio Di
II Di - w || for all i = 1, 2. The worst-
1+a
case scenario for the logarithmic term would be when the numerator is maximized, and the denominator minimized, or vice versa. Let's denote this worst-case ratio as Ez:
Σx II..
+ a Σn [Ic. Σx [[c. A.. exp( xd (Wx)) + Σn I(c.)/C))
(WDv)) (WD))
E2 - sup log
(45)
Based on Lemma the exponential term in Eq. has the following inequality:
exp(-7dux (W S exp (->( (W DV)) duu /exp(p>chxxlee
- 7 (W (w))) ( pw)) + (W (W))) di. di (W>)))) encha(
72
4
2
<
1 + (oh (w) - Lh (W
+
Let (WD)) - ( (Wa
1
1
Id, (WDx) -. 2
(Wp)
2
< + ?
2ct
(246. + +20 + n(Ac, + +GG,) h4
e (Do, + +cc.))
))
e (dba
2 12
vn
(46)
For arbitrary two graphs u, U, assume their pairwise squared distance &i (Wp) S т. Denote 6 as the number of other graphs with the same label as graph u, and 0,, as the number of other graphs with a different label from graph then rewrite the expression for Eg:
26

---

Published as conference paper ICLR 2024
Eg s sup u
yT - log(O% + +a0,))
2log
1
7
4
26a)
(246) +20g, +n(AG, +
(Ao, + Aciz) )
2
h
h
Vn
+ + - log a
2yT + 2log
1+
4
2cth
24/,
+24 +n(Ac, + + vn
c (Ac, + Aci))
2
h22
ha
(47)
By combining Eq.
44
the supremum of the entire expression would be
sup
[[(DD. Zn, Z.)
I(W DV:, Zu Z,) 7Ei + E2
(48)
{
2
(Do, Aoa)) +
7
2A +246, + +n(AG, Aoz) + VI
112
h
+2yr + 2log
1
7
+
2c
244 + +24 + +n(AG, + +Aog)²+ + vn
(Ac, + Aco)))
2
h
ht
44y
2
2
+
2
+
Ac
+2yT+2log 1+7
(2
+ d")
(2 +2n vn Ac) )
h22
h4
vn
1/2
h4
-
where AG = 17
(
0
p32
E/
Pwo Di
Ii- Di. - wo(llE))
Ita
G THEORETICAL AND EMPIRICAL COMPLEXITY
G.1 COMPLEXITY ANALYSIS
Proof for Theorem 3
Proof. For the embedding propagation step, it requires O(Lmd) runtimes. In the kernel mapping step, we get pairwise kernel value by calculating the generalized MMD. With single kemel, it needs O(n²d) runtimes. Consider a kernel family with a size of k, the complexity of this part O(endd) Overall, the pairwise MMD-GK is computed in O(Lmd + xn? and for N graphs, the complexity of all pairs is ONN Lmnd + 22 kn)ddd.
Proof for Theorem 4
Proof. For the embedding propagation step, requires ([Ind + Lmd) runtimes. Other things being equal to MMD-GK, one pairwise Deep MMD-GK is therefore computed in ( + Lmd + an²d). For N graphs, the complexity of all pairs is Ond + NLmd N kndd).
27

---

Published as a conference paper ICLR 2024
2000
200m
1750
1300
Swcond 10
1250
100
Sccind 50
167
500
250
100
202
400
900
500
1000
101
12a
Avg. Nam of Nodes
Num hodee
Figure 3: Runtimes Performance MMD-GK computation with 1000 synthetic graphs and one RBF kernel
|C| 1. We report both normal and log-scale runtime with different levels (L) of node features, where E (1,2,3,455)
G.2 RUNTIME ANALYSIS
Following the setting of Togninalli et al. (2019), we conducted a simulation using a consistent number of graphs while varying the average node number per graph, to assess the performance of our MMD-GK approach with respect to the average number of nodes. Specifically, we generated 1000 synthetic graphs with the same node feature's 's dimension d 20. For each graph, we generate the number of nodes (n) based on normal distribution centered on an average node number, and the number of edges m is controlled between n and 5n. For each level of node features L. E 21, 4, 5], we applied the MMD-GK with a single Radial Basis Function (RBF) kernel (i.e. |K|= 1) to measure and compare runtimes over the different average number of nodes n. From Figure 3 the runtimes increase the runtimes increase with the square of the number of nodes n²? which is modulated by the number of levels L. In practical terms, the graph on normal scales suggests a linear trend, especially for graphs with a smaller number of nodes. As the number of nodes increases, the complexity term involving n² might become more dominant, which could explain the superlinear growth observed, particularly at higher levels of L. This is consistent with the theoretical complexity, which posits that as L and n increase, the runtimes should increase correspondingly. The log scale also helps to visualize the dramatic impact of the n² term as the number of nodes grows.
We also compare our approaches to four graph kernels on the synthetic graphs. For the Graphlet kernel, k = 5; for the Weisfeiler-Lehmar Subtree kernel, h = 5; for our MMD-GK and Deep MMD-GK, L h. k 1 and 1. m held constant across the kernels. All methods are performed ten times. Table indicates that our approaches are competitive with the existing graph kernel methods.
H EXPERIMENT SETTINGS
Configuration DHFR, BZR, and PROTEINS have node attributes whereas MUTAG and PTC.FM only contain node labels. For GNN-related methods, we transform the categorical node label to one-hot embed- ding. We evaluate our approaches exhaustively
all possible graph distributions for each dataset in Table 5) i.c. for datasets without node labels, Z = Y; and for datasets with node labels, Z = X or Z = or 10) for MMD-GKs
set the number of level L {1, 2,, and L E {1,2, 2, 3, 4} for Deep MMD-GKs and adopt a Gaussian kernel family with bandwidth h E (le-2, le-1, le0, lel, le2). For simmillarity explore scenarios when 7 E fle-1, Ie0, lel). For
(X, Y). To avoid over-smoothing,
28

---

Published as conference paper ICLR 2024
Table 4: Total computation time for 10 runs on 1000 synthetie graphs with an average of 20 nodes and 50 edges.
Graph Kernel
Total Runtime
Graphlet
120.4s
Shortest Path
30.3.s
Weisfeiler-Lehman Subtree
26.4 s
Wasserstein Weisfeiler-Lehme
211.0s
MMD-GK
29.2s
Deep MMD-GK
31.2s
Table 5: Description of the benchmark datasets DHER, BZR, MUTAG, PTC_FM and PROTEINS
Dataset
DHFR
BZR
MUTAG
PTC.FM
PROTEINS
Num. of graphs
467
405
188
349
1113
Num. of graph labels
2
2
2
Dim. of node attributes
3
/
/
29
Num. of node labels
9
10
7
18
Avg. number of nodes
42.43
35.75
17.93
14.11
39.06
Avg. number of edges
44.54
38.36
19.79
14.48
72.82
Label Proportion
461/295
319/86
125/63
206/143
663/450
Deep MMD-GK, implement the algorithm in Pytorch with set LeakyRelu activation and À fixed to be 0.33 which means there are around one-third of pairs selected as negative samples in unsupervised contrastive loss. All Deep MMD-GKs
trained for 300 epochs with a batch size of 128, using Adam optimizer (Kingma & Ba 2015) at le-2 initial learning rate. For graph clustering, we adopt MMD-GK and unsupervised Deep MMD-GK the precomputed affinity matrix run Spectral Clustering (Pedregosa iet al. 2011). For graph classification, we use a binary C-SVM (Chang & Lin 2011 and report the average of test accuracy across the 10 folds within the cross-validation. The parameter for each fold tuned from {le0, lel, le2}. For the graph kernel baselines, we report the best performances across all parameters: depth of the subtree
{1, 2, 3, 4, 5) for WI. Kernel; graphlet size E (3, 4, 5, 6} for Graphlet Kernel. For other baselines, we set their parameters according to their original papers.
Evaluation Metrics For the graph classification task, we use the accuracy which defined as ratio of the correct predictions. For the graph clustering task, we use the following scores evaluate the result: 1) ACC (Accuracy): Represents the proportion of the total number of predictions that are correct; 2) NMI (Normalized Mutual Information): Mcasures the mutual information of the true and predicted clusterings, normalized to have values between 0 (no mutual information, or independent labelings) and 1 (perfect cor- relation); ART (Adjusted Rand Index): Evaluates the similarity of clusterings, adjusted for chance. ARI ranges between- -1 and 1, with indicating perfect match, indicating random labeling, and negative values indicating bad match.
29

---

Published as conference paper ICLR 2024
I PARAMETER SENSITIVITY
(a) Clustering Accuracy
(b) Clustering NMI
(c) Clustering
Figure 4: Parameter Sensitivity of MMD-GK the dataset BZR; comparison of scores with change in level
(x-axis) and graph distribution iz (Z X blue, Z Y in green and Z = (X, Y) in red).
Clustering Accuracy
(b) Clustering NMT
(c) Clustering ARI
Figure 5: Parameter Sensitivity of MMD-GK on the dataset DHFR; Comparison of scores with change in level (x-axis) and graph distribution Pz (Z X blue, Z Y in green and Z (X, Y) red).
(a) Clustering Accuracy
(b) Clustering NMI
(c) Clustering ARI
Figure 6: Parameter Sensitivity MMD-GB on the dataset FM; Comparison of scores with change in level (in x-axis).
30

---

Published as conference paper ICLR 2024
J
DEEP MMD-GK CONVERGENCE
0.91
5.4
0.88
5.2
0.85
0.83
4.8
0.81
50
100
150
250
300
300
(a) Training Loss (loss-iteration)
Test SVM Accuracy(soorc-teratin
Figure 7: Convergence in training supervised Deep MMD-GK on the benchmark dataset MUTAG.
K ADDITIONAL RESULTS
this section, we present detailed tables showcasing the performance evaluation of both supervised and unsupervised models on two datasets: MUTAG and PTC_FM. These tables provide a comprehensive break- down of the results, factoring in various parameters such loss type (SCL. KL. UCL), levels (I-level), and tuning parameters (a and 7). Each table is accompanied by caption that highlights the best performance metrics in bold, aiding in the quick identification of the most effective parameter configurations.
Performance Trends Increasing values generally lead to better performance in supervised models on the MUTAG dataset, suggesting that this parameter positively influences the model's ability to learn from this particular dataset. The 1-level seems to have less consistent impact, but higher levels do not always equate better performance, indicating a complex interaction with the dataset's characteristics. Supervised models outperform unsupervised models in most configurations, which could be due to the additional guidance provided by labeled data.
For graph classification, simpler models (lower (-levels) may perform better, whereas, for graph clustering, more complex ones with KL loss (higher I-levels) may perform better. The varying per- formance across different I-levels and hyperparameter settings for the two datasets (MUTAG and PTC FM) implies that these models respond differently to distinct data characteristics, such as graph distribution and class imbalances.
Model Behavior
31

---

Published as conference paper ICLR 2024
Table 6: Supervised Model Evaluation on MUTAG, The best performance is highlighted in bold.
Loss
I-level
a
7
SVC
SCL
0.1
0.1
0.665 + 0.009
SCL
0.1
1
0.808 + 0.060
SCL
1
0.1
10
0.883 + 0.054
SCL
1
1
0.1
0.665 + 0.009
SCL
1
1
1
0.830 + 0.041
SCL
1
10
0.904 0.032
SCL
10
0.1
0.670 + 0.011
SCL
10
1
0.835 + 0.049
SCL
I
10
10
0.915 + 0.065
SCL
2
0.1
0.1
0.681 + 0.028
SCL
2
0.1
10
0.909 + 0.054
SCL
2
0.1
1
0.819 + 0.025
SCL.
2
1
0.1
0.665 + 0.009
SCL
2
1
1
0.814 + 0.040
SCL
2
1
10
0.893 + 0.029
SCL
2
10
0.1
0.670 + 0.009
SCL
2
10
1
0.819 + 0.025
SCL
2
10
10
0.888 + 0.040
SCL
0.1
0.1
0.676 0.009
SCL
0.1
1
0.825 + 0.038
SCL.
0.1
10
0.857 + 0.035
SCL
0.1
0.686 + 0.0169
SCL
3
1
1
0.819 + 0.054
SCL
3
1
10
0.840 0.031
SCL
3
10
0.1
0.713 + 0.039
SCL
10
0.851 + 0.043
SCL
3
10
10
0.888 + 0.085
SCL
0.1
0.1
0.734 0.043
SCL
4
0.1
1
0.841 0.075
SCL
0.1
10
0.745 0.044
SCL
1
0.1
0.719 0.027
SCL
1
1
0.792
SCL
4
1
10
4.745
SCL
10
0.1
0.857 0.063
SCL
4
10
1
0.872 + 0.061
SCL
10
10
0.761 + 0.022
32

---

Published as conference paper ICLR 2024
Table 7: Unsupervised Model Evaluation on MUTAG. The best performance across each loss is highlighted in bold.
Loss
1-level
?
ACC
NMI
ARI
SVC
KL
1
0.1
0.713
0.147
0.177
0.665 + 0.009
KL
1
1
0.718
0.152
0.186
0.873 + 0.026
KL
1
10
0.750
0.172
0.244
0.899 + 0.019
KL
2
0.1
0.702
0.148
0.159
0.873 + 0.026
KL
2
1
0.723
0.157
0.195
0.893 + 0.029
KL
2
10
0.723
0.152
0.186
0.873 + 0.026
KL
3
0.1
0.745
0.249
0.236
0.665 + 0.009
KL
3
1
0.840
0.459
0.461
0.893 + 0.009
KL
3
10
0.840
0.432
0.454
0.894 + 0.021
KL
4
0.1
0.846
0.468
0.476
0.713 + 0.009
KL
0.819
0.440
0.405
0.883 + 0.009
KI
4
10
0.840
0.459
0.461
0.910 + 0.047
UCL
1
0.1
0.1
0.713
0.141
0.177
0.665 + 0.009
UCL
I
0.1
1
0.713
0.141
0.177
0.819 + 0.054
UCL
0.1
10
0.750
0.172
0.244
0.893 + 0.058
UCL
1
0.1
0.713
0.141
0.177
0.665 + 0.009
UCL
0.713
0.141
0.177
0.83 0.066
UCL.
10
0.745
0.166
0.233
0.910 + 0.026
UCL
10
0.1
0.713
0.147
0.177
0.665 + 0.009
UCL
1O
1
0.713
0.141
0.177
0.824 + 0.049
UCL
10
10
0.745
0.166
0.233
0.910 + 0.045
UCL
2
0.1
0.1
0.713
0.167
0.177
0.665 + 0.009
UCL
0.1
1
0.729
0.172
0.205
0.814 + 0.079
2
UCL
2
0.1
10
0.750
0.181
0.240
0.878 + 0.068
UCL
2
0.1
0.734
0.167
0.214
0.665 + 0.009
UCL
2
1
0.745
0.175
0.234
+ 0 0.072
UCL
2
10
0.750
0.164
0.241
0.888 + 0.048
UCL
2
10
0.1
0.729
0.152
0.204
0.665 + 0.009
UCL
2
10
1
0.713
0.167
0.176
0.815 +.117
UCL
2
10
10
0.750
0.170
0.243
0.910 + 0.052
UCL
0.1
0.1
0.766
0.207
0.276
0.665 + 0.009
UCL
0.1
1
0.750
0.207
0.246
0.830 + 0.046
UCL
8
0.1
10
0.771
0.174
0.274
0.856 + 0.039
UCL
0.1
0.761
0.221
0.268
0.665 + 0.009
UCL
8
0.750
0.233
0.246
0.846 + 0.046
UCL
8
10
0.739
0.211
0.217
0.861 1 0.054
UCL
10
0.1
0.739
0.175
0.225
0.665 + 0.009
UCL
3
10
1
0.761
0.234
0.268
0.798 + 0.098
UCL
3
10
10
0.761
0.237
0.255
0.836 + 0.049
UCL
4
0.1
0.1
0.787
0.320
0.324
0.676 + 0.018
UCL
4
0.1
1
0.798
0.252
0.345
0.824 + 0.027
UCL
4
0.1
10
0.787
0.252
0.314
0.761 + 0.035
UCL 4
1
0.1
0.793
0.249
0.328
0.670 + 0.009
UCL 4
I
1
0.787
0.248
0.312
0.803 + 0.029
UCL
4
1
10
0,787
0.247
0.323
0.740 + 0.019
UCL
4
10
0.1
0.771
0.266
0.291
0.692 + 0.009
UCL
4
10
1
0.787
0.338
0.327
0.819 + 0.059
UCL
4
10
10
0.798
0.244
0.345
0.868 + 0.034

---

Published as conference paper ICLR 2024
Table 8: Supervised Model Evaluation on PMC.FM. The best performance highlighted in bold.
Loss
I-level
a
SVC
SCL 1
0.1
0.639 0.014
SCL
1
1
0.659 0.029
SCL
1
10
0.613 + 0.027
SCL
1
10
10
0.633 0.031
SCL
1
10
0.667 + 0.032
SCL
2
1
0.1
0.648 + 0.025
SCL
2
1
0.662 0.043
SCL
2
1
10
0.633 + 0.030
SCL
2
10
0.663 0.045
SCL
2
10
10
0.605 = 0.019
SCL
3
0.659 0.040
SCL
3
1
10
0.613 + 0.027
SCL
10
0.665 0.026
SCL
3
10
10
0.619 + 0.047
SCL
4
1
0.662 = 0.047
SCL
4
10
0.625 0.032
SCL
4
10
0.656 + 0.026
SCL
4
10
10
0.610 0.029
Table 9: Unsupervised Model Evaluation PTC.FM. The best performance across each loss is highlighted bold.
Loss
I-level
a
Y
ACC
NMI
ARI
SVC
KL
1
0.567
0.009
0.014
0.659 + 0.032
KL
10
0.625
0.076
0.035
0.610
0.023
KL
1
0.619
0.022
0.042
0.653 0.028
KL
1
10
0.616
0.044
0.025
0.636 + 0.032
KL
1
1
0.599
0.014
0.030
0.650 + 0.006
KL
10
0.648
0.073
0.065
0.653 + 0.048
KL
4
1
0.642
0.042
0.066
0.633 + 0.019
KL
10
0.599
0.021
0.007
0.619 + 0.027
UCL
1
0.630
0.031
0.057
0.668 0.028
UCL
10
0.625
0.052
0.035
0.616 + 0.043
UCL
1
0.625
0.029
0.054
0.665 + 0.053
UCL
10
0.607
0.040
0.016
0.636 0.014
UCL
1
0.616
0.024
0.046
0.650
0.028
UCL
10
0.599
0.021
0.007
0.607 0.021
UCL
1
0.625
0.028
0.053
0.651
0.017
UCL
4
10
0.599
0.021
0.007
0.630 + 0.013
34


Reviews:
[{"review_id": "uGjyPc9QS6", "reviewer": "Reviewer_9SJd", "summary": "This paper proposes a new graph kernel to calculate the maximum mean discrepancy (MMD) which measures the similarity of two graphs. The main idea is to regard each graph as a sampling distribution from a latent metric space where a similarity kernel can be designed for efficiency. Based on such an MMD-based graph kernel, two methods are designed for unsupervised and supervised graph metric learning, respectively.", "questions": "See weaknesses.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "+ The paper is well-written, and I find it a joy to read. The authors present a nice and coherent story to introduce the current gap and motivation of the idea.\n\n+ The proposed MMD-based kernels are technically sound and will have a significant impact on the graph metric learning domain.\n\n+ In-depth and well-organized theoretical analysis is provided to justify the approach in a principled manner.", "weaknesses": "- The major limitation is the lack of theoretical and empirical study of the efficiency of the proposed kernel. As highlighted in the introduction the proposed method aims to address the computation and memory cost of existing methods, no evidence shows this goal is achieved.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "t1nTXT1NOA", "reviewer": "Reviewer_a9u9", "summary": "This paper discusses graph kernels based on maximum mean discrepancy (MMD) on the (empirical) distribution of embedded nodes. An extension of this MMD graph kernel similar to the deep graph kernel (Yanardag and Vishwanathan 2015) is proposed. For both graph kernel variants the authors provide a theoretical robustness/perturbation analysis. Finally, first experimental results on standard benchmark datasets are presented.", "questions": "Why do the authors not use the standard unbiased MMD estimator e.g. in Eq. (4)? I.e. the one normalized with $(n\\cdot(n-1))$ in the in-distribution sums, cf. Gretton et al. 2012.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 1, "strengths": "* First empirical results on (arguably simple) benchmark datasets are promising.\n* Theoretical robustness analysis.", "weaknesses": "While the paper is interesting, I vote for rejection in its current form, due the following issues.\n\nBadly written and hard to follow paper:\n* The reader is not guided well through the paper. \n* While the robustness analyses might be interesting, they are completely unmotivated. The assumptions made and the achieved bounds are hard to interpret and set into context. It is not clear why the authors decided to include them and what the significance of them is. Please guide the reader more and put the results into context, e.g. discuss similar bounds. \n* The architecture overview in Fig. 1 is rather confusing and not explained well. Also the \"GCN\" probably stands for the GCN of Kipf&Welling, however it's not clear what it is doing in the Figure and what is meant e.g. with \"vanilla: done. GCN: updating\". \n* The central definition 6 and Assumption 1 are difficult to understand.\n\n\nDiscussion of related work is insufficient\n* Most of the actually related work is not discussed. E.g. many papers exist discussing MMD in the context of graph kernels and GNNs. E.g. [1, 2, Borgwardt's thesis, ... ] Similarly many related work exist that perform graph matching / optimal assignment [Kriege et al., survey, etc.], or modify WL using Wasserstein distances [3-5]. This makes the novelty difficult to assess. Please discuss.\n\nMisleading and wrong claims:\n* The authors claim that the proposed kernel has \"much lower computational cost\" then e.g. the WL kernel. This seems to be wrong. The WL kernel can be computed in near-linear time if the height is fixed. This is similar to the parameter $l$ here in $X^l$. In fact, the computation of WL up to height $l$ should be essentially the same as computing the $X^l$s. \n* two of the three main benefits of the proposed approach are (1) dealing with unequal sizes and (2) permutation-invariance. This is however the case for almost all graph kernels, including the popular ones like the WL-kernel, walk kernels, pattern-based kernels etc. \n* the claims about degree + power law distributions are unclear. Why should non-power law distributed degrees lead to \"inaccurate substructure representations\".  Also, the authors claim that GNNs resolve the previously mentioned issue and \"capture intricate higher-level interactions\". This is however rather misleading as most common GNNs (MPNNs) are bounded in their expressivity by WL and hence cannot capture \"more\" than the WL kernel (Xu et al., 2019, Morris et al 2019).\n* The cited \"MMD GAN\" paper is mentioned as \"MMD also aids in the training of GNN\", while the paper actually discussed training of *GANs* and does not deal with graphs at all.\n\nA lot of sentences are vague, handwavy, and unnecessarily wordy, e.g.\n* what should \"substructures derived from graphs are intertwined\" even mean exactly.\n* $X^l$ and $X^{(l)}$ are probably the same thing, but the latter is not defined.\n\nTypos and minor issues:\n* $\\mu_P$ is not defined. Similarly, most readers probably don't know what a characteristic kernel is in the context of MMD. Please make the paper self-contained.\n* \"to learn graph metric*s*\"\n* \"(2012) . \" the space before the dot \".\"\n\nI am happy to change my score if my concerns are addressed and the contribution/novelty is made clearer.\n\n[1] Ghanem, Hashem et al. \"Fast graph kernel with optical random features.\" ICASSP 2021\n\n[2] O'Bray, Leslie, et al. \"Evaluation metrics for graph generative models: Problems, pitfalls, and practical solutions. ICLR 2022\n\n[3] Togninalli, Matteo, et al. \"Wasserstein weisfeiler-lehman graph kernels.\" NeurIPS 2019\n\n[4] Samantha Chen et al. \"Weisfeiler-Lehman Meets Gromov-Wasserstein\" ICML 2022\n\n[5] Till Schulz et al. \"A generalized Weisfeiler-Lehman graph kernel\" Machine Learning 2022", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "SkaB5pJvvZ", "reviewer": "Reviewer_avjd", "summary": "This work proposed a class of (deep) MMD based graph kernels, coupled with theoretical results. The proposed kernels are applied to graph classification and graph clustering on a few benchmark datasets.", "questions": "* Section 3.1 can be made more compact to provide more space for Section 4 and Section 5.\n* What is the advantage of the general MMD compared to the single-kernel MMD?\n* In Algorithm 1, for the input, the authors mentioned bandwidth. Does this mean the algorithm only use RBF kernels?\n* In formula (11), how to determine $S_+$ and $S_-$?\n* In Theorem 2, the influence of $n$ and $h$ hasn’t been discussed.\n* What is the labeling rate in Table 2?\n* In Table 2, on BZR, the values given by supervised and unsupervised Deep MMD-GKs are the same. Is it a typo?\n* In Appendix G, are there any explanation for the additional results?", "limitations": "", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The paper proposed a class of (deep) MMD based graph kernels (MMD-GKs). The novelty is high. Different from classical graph kernels that have fixed features, the proposed Deep MMD-GKs are learnable, with or without labels.\n* The authors provided some theoretical analysis, which are useful and explainable. \n* The deep MMD-GKs outperformed the baselines in supervised learning and unsupervised learning on several graph datasets.", "weaknesses": "* The time cost comparison is missing. \n* Deep MMD-GK is more effective than the vanilla MMD-GK but the corresponding algorithm (Algorithm 2) is in the appendix.\n* The analysis of the experimental results should be strengthened.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "AaNayDAUzb", "reviewer": "Reviewer_CP9G", "summary": "The paper introduced a class of MMD based graph kernels. It also introduced a class of deep MMD graph kernels that have learnable parameters. Some theoretical analysis such as robustness have been done. The experiments of graph clustering and classification showed the effectiveness of the proposed methods.", "questions": "It would be great if the authors could improve the aforementioned weaknesses and answer the following questions.\n1. In Definition 5, for the generalized MMD, how to efficiently determine $k$ in practice? It may have infinite choices.\n2. In Theorem 1, it seems that if $h$ is close to zero, the bound is loose. How to avoid small $h$ in practice?\n3. In unsupervised learning with loss functions (11) and (12), will model collapse (all $s_{ij}$ are zero or one) happen? This may be caused by zero or infinity weights in the deep model.\n4. More explanation about the usefulness of (11) and (12) are required.\n5. In Section 4.2, suppose $\\beta$ can be computed, how to obtain the stability parameter $\\omega$?\n6. In Table 1, the NMIs and ARIs given by all methods on datasets DHFR and PTC are very low. What is the possible reason?", "limitations": "", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "1. Measuring the similarity between graphs is a practical and challenging problem.\n2. The proposed shallow and deep MMD graph kernels are novel and interesting. The deep MMD graph kernel is learnable in both supervised and unsupervised ways. \n3. The paper studied the robustness and generalization of the graph kernels. \n4. In the experiments, the proposed deep MMD graph kernel is more effective than classical graph kernels and graph neural networks. The superior performance in clustering is quite impressive.\nIn sum, this is a good work with solid theoretical analysis and numerical evaluation. The unsupervised deep MMD graph kernel makes a breakthrough in the area.", "weaknesses": "The paper has the following weaknesses.. \n1. The motivation of the two unsupervised loss functions (eq.10 and eq.11) in Section 4 haven’t been sufficiently explained. \n2. For graph clustering, GNN-based clustering method should be compared in Table 1.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (spotlight)