MMD Graph Kernel: Effective Metric Learning for Graphs via Maximum Mean Discrepancy

W1: The motivation of the two unsupervised loss functions (eq.10 and eq.11) in Section 4 haven’t been sufficiently explained.

Response: Thanks for your suggestion. We would further explain the motive behind the unsupervised loss function.

• Supervised Contrastive Loss (SCL) equation is designed to enhance the model's ability to learn from graph labels when they are available. By adopting the supervised version of the InfoNEC loss function SCL focuses on maximizing the agreement between embeddings of graphs that share the same label (indicated by $C_i = C_j$). The equation reflects this by encouraging similarity (high $s\_{ij}$) between graphs of the same class while penalizing similarity between graphs of different classes. The component $\alpha \sum\_{k}\mathbb{I}{[C\_i \ne C\_i]}s_{ik}$ in the denominator acts as a regularizing term to control the influence of dissimilar pairs.
• Unsupervised Contrastive Loss (UCL) equation provides a mechanism for learning the MMD graph kernel when graph labels are not available. This loss function is a modification of SCL where the distinction between similar and dissimilar graph pairs is made based on their similarity rather than their labels. UCL focuses on selecting the most similar pairs ($S\_+$) and the least similar pairs ($S\_-$) within each training epoch. The loss function encourages the model to distinguish between these two sets in the absence of explicit labels.

W2: For graph clustering, GNN-based clustering method should be compared in Table 1.

Response: Thanks for your suggestion. Following your recommendation, we have updated the table to incorporate results from two notable GNN methods [1][2] for clustering. We use the two methods to obtain graph representations and then conduct spectral clustering. Our methods outperformed these two baselines.

[1] You, Yuning, et al. "Graph contrastive learning with augmentations." NeurIPS 2020 [2] Sun, Fan-Yun, et al. "InfoGraph: Unsupervised and Semi-supervised Graph-Level Representation Learning via Mutual Information Maximization." ICLR 2020.

Q1: In Definition 5, for the generalized MMD, how to efficiently determine $k$ in practice? It may have infinite choices.

Response: Thanks for your inquiry. A common way to determine the $k$ is to set the parameter range with limited sparse choices such as using an RBF kernel family with bandwidths like $[1e-1, 1e0, 1e1]$. This method provides a balance between computational efficiency and the ability to capture different scales of features in the data.

Q2: In Theorem 1, it seems that if $h$ is close to zero, the bound is loose. How to avoid small $h$ in practice?

Response: Thanks for bringing up this point. To address this issue in practice, the most straightforward way is avoid including a minimal (e.g. smaller than $1e-3$) bandwidth in the kernel family.

Q3: 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.

Response: Thanks for your question. In the case of UCL, employing a diverse set of negative samples (i.e., non-similar pairs) can prevent the model from trivially maximizing similarity scores. In practice, we found the non-similar pairs could ensure a representative sample of dissimilar pairs discourages the model from collapsing towards uniform similarity scores. For KL loss, we have implemented regularization techniques to prevent extreme values in the model weights.

Q4: More explanation about the usefulness of (11) and (12) are required.

Response: Thanks for your suggestions. Both UCL and KL serve crucial roles in our approach to unsupervised learning from unlabeled data. The primary benefit of UCL is that it facilitates the learning of discriminative features from a set of graphs. By minimizing the KL Divergence, the model learns to adjust its embeddings to better reflect the natural clustering of the data. We have added the explanation to Section 4 in the manuscript.

Q5: In Section 4.2, suppose $\beta$ can be computed, how to obtain the stability parameter $w$ ?

Response: Thanks for your query. We provide the explicit formulation for the stability parameter $\omega$ in Appendix F.

W1: The time cost comparison is missing.

Response: Thanks for your comments. We have added the complexity analysis in Section 4.3 of the paper with proof in Appendix G.1. We also show them below.

Theorem 3. The MMD-GK using a kernels $\mathcal{K}$ on a pair of graphs $G$ and $G'$, both with $L$-level of $d$-dimensional node features, can be computed in $O(Lmd+\kappa n^2d)$, where $n$ is the number of nodes, $m$ is the number of edges, and $\kappa$ is the size of the kernel family, i.e. $\kappa=|\mathcal{K}|$. For $N$ graphs, all pairwise MMD-GKs are computed in $O(NLmd+N^2\kappa n^2d)$.

Theorem 4. Suppose the widths of the hidden layers of the neural network are $O(d)$. The Deep MMD-GK using a kernels $\mathcal{K}$ on a pair of graphs $G$ and $G'$, both with $L$-level of $d$-dimensional node features, can be computed in $O(Lnd^2+Lmd+\kappa n^2d)$, where $n$ is the number of nodes, $m$ is the number of edges and $\kappa$ is the size of the kernel family, i.e. $\kappa=|\mathcal{K}|$. For $N$ graphs, all pairwise Deep MMD-GKs are computed in $O(Nnd^2+NLmd+N^2\kappa n^2d)$.

We compare the theoretical efficiency of the proposed kernel with other baselines in Table 3. Our MMD-GK is competitive with kernels, such as the Shortest Path and Graphlet with a $k>2$. Generally, we set $\kappa$ such that $\kappa d<n$, so the MMD-GK is better in complexity than the Wasserstein Weisfeiler-Lehman graph kernel, when holding $L$ equal to $h$. We note that the Weisfeiler-Lehman Subtree graph kernels scale linearly with the number of nodes; therefore, this method is faster than our approach.

Above is the summary of selected graph kernels regarding support for node-labeled and node-attributed graphs, and computational complexity. Notations not been introduced yet: $k$: size of largest subgraph considered; $h$: maximum distance between root of neighborhood subgraph/subtree pattern and its nodes.

We also add runtimes analysis in Appendix G.2. Following the setting of Togninalli et al. [1], 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 dimension $d=20$. For each graph, we generate the number of nodes based on a normal distribution centered on a average node number. For each level of node features $L\in\{1, 2, 3, 4, 5\}$, we applied the MMD-GK with a single Radial Basis Function (RBF) kernel (i.e. $|\mathcal{K}|=1$) to measure and compare runtimes over different average number of nodes $n$. As shown by Figure 3 in the Appendix F of the manuscript, the runtime increases with the square of the number of nodes $n^2$, which is modulated by the number of levels $L$.

We also compare our approaches to four graph kernels on the synthetic graphs with node features $d=1$. For the Graphlet kernel, $k=5$; for the Weisfeiler-Lehman Subtree kernel, $h=5$; for our MMD-GK and Deep MMD-GK, $L=h$, $\kappa=1$ and $d=1$. $m$ is held constant across the kerenls. All methods are performed ten times. Refer to the Table 4, we report the total computation time for 10 runs on 1000 synthetic graphs with average of 20 nodes 50 edges, which indicates our approaches are competitive with the existing graph kernel methods.

[1] Togninalli, Matteo, et al. "Wasserstein weisfeiler-lehman graph kernels." NeurIPS 2019

W2: Deep MMD-GK is more effective than the vanilla MMD-GK but the corresponding algorithm (Algorithm 2) is in the appendix.

Response: Thanks for your suggestions. We certainly incorporate your feedback into our manuscript, ensuring that Algorithm of Deep MMD-GK is more accessible by including it in the main body of the text.

Overview of Responses:

Dear Reviewer,

Thank you for your insightful feedback. In response to your comments, we have implemented the following enhancements to our manuscript:

1. Enhanced Related Work: We have expanded the discussion in the related work section to better position our study within the existing body of research.

2. Elaboration of Motivation and Implications: We have enriched the Section 3.3 and 4.1 on the motivation behind our robustness analysis.

3. Improved Clarity and Readability: We have carefully revised the manuscript refining the language, streamlining the narrative, and ensuring a more coherent presentation of our research.

We believe these improvements strengthen the manuscript and look forward to your further feedback.

W1: The reader is not guided well through the paper.

Response: Thanks for your comments. In response, we have undertaken a thorough revision to improve the flow and structure.

W2: 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.

Response: Thank you for pointing this out. We have revised this section to explicitly state why these analyses are crucial.

We conduct the robust analysis for the following reasons.

• First, since real data are often noisy, we would like to theoretically show the upper bound of the gap between the distance of clean graphs and the distance of corrupted graphs. By the way, the robustness is also useful when considering differential privacy, i.e., adding noises to the graphs to protect the data or user privacy in some scenarios.
• Second, the robust analysis is useful for quantifying the generalization ability of the model. For instance, given a test pair $\tilde{G}_1$ and $\tilde{G}_2$, suppose their closest graphs in the training dataset $\mathcal{G}$ are $G_1, G_2$ respectively. Then according to Theorem 1, $\hat{d}_K^2(\tilde{G}_1^{(l)}, \tilde{G}_2^{(l)}) \leq \hat{d}_K^2(G_1^{(l)}, G_2^{(l)})+\bar{\Delta}$, where $\bar{\Delta}$ is small provided that $G_1, G_2$ are similar to $\tilde{G}_1, \tilde{G}_2$ in terms of the adjacency matrices and node features. A smaller $\bar{\Delta}$ implies a stronger generalization ability.

These discussions have been added to Section 3.2 and Section 4.1.

In the revised paper, we provide more explanation about the assumption (e.g. the norm upper bounds and $\Delta_{A_i}$) in the theorems. They can be found in Section 3.3.

W3: 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".

Response: Thanks for your feedback. What we mean by "GCN: updating" is that the deep model requires training and updating parameters, while the vanilla version only goes through the process one time. We changed this figure and its caption to clarify the meaning of terms like "GCN" and "vanilla: done. GCN: updating". Additionally, we will reference the work of [1] to provide context.

[1] Kipf, Thomas N., and Max Welling. "Semi-Supervised Classification with Graph Convolutional Networks." ICLR. 2016.

W1: 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.

Response: Thanks for your comments. We have added the complexity analysis in Section 4.3 of the paper with proof in Appendix G.1. We also show them below.

Theorem 3. The MMD-GK using a kernels $\mathcal{K}$ on a pair of graphs $G$ and $G'$, both with $L$-level of $d$-dimensional node features, can be computed in $O(Lmd+\kappa n^2d)$, where $n$ is the number of nodes, $m$ is the number of edges, and $\kappa$ is the size of the kernel family, i.e. $\kappa=|\mathcal{K}|$. For $N$ graphs, all pairwise MMD-GKs are computed in $O(NLmd+N^2\kappa n^2d)$.

Theorem 4. Suppose the widths of the hidden layers of the neural network are $O(d)$. The Deep MMD-GK using a kernels $\mathcal{K}$ on a pair of graphs $G$ and $G'$, both with $L$-level of $d$-dimensional node features, can be computed in $O(Lnd^2+Lmd+\kappa n^2d)$, where $n$ is the number of nodes, $m$ is the number of edges and $\kappa$ is the size of the kernel family, i.e. $\kappa=|\mathcal{K}|$. For $N$ graphs, all pairwise Deep MMD-GKs are computed in $O(Nnd^2+NLmd+N^2\kappa n^2d)$.

We compare the theoretical efficiency of the proposed kernel with other baselines in Table 3. Our MMD-GK is competitive with kernels, such as the Shortest Path and Graphlet with a $k>2$. Generally, we set $\kappa$ such that $\kappa d<n$, so the MMD-GK is better in complexity than the Wasserstein Weisfeiler-Lehman graph kernel, when holding $L$ equal to $h$. We note that the Weisfeiler-Lehman Subtree graph kernels scale linearly with the number of nodes; therefore, this method is faster than our approach.

Above is the summary of selected graph kernels regarding support for node-labeled and node-attributed graphs, and computational complexity. Notations not been introduced yet: $k$: size of largest subgraph considered; $h$: maximum distance between root of neighborhood subgraph/subtree pattern and its nodes.

In addition, we add runtimes analysis in Appendix G.2. Following the setting of Togninalli et al. [1], 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 dimension $d=20$. For each graph, we generate the number of nodes based on a normal distribution centered on a average node number. For each level of node features $L\in\{1, 2, 3, 4, 5\}$, we applied the MMD-GK with a single Radial Basis Function (RBF) kernel (i.e. $|\mathcal{K}|=1$) to measure and compare runtimes over different average number of nodes $n$. As shown by Figure 3 in the Appendix F of the manuscript, the runtime increases with the square of the number of nodes $n^2$, which is modulated by the number of levels $L$.

We also compare our approaches to four graph kernels on the synthetic graphs with node features $d=1$. For the Graphlet kernel, $k=5$; for the Weisfeiler-Lehman Subtree kernel, $h=5$; for our MMD-GK and Deep MMD-GK, $L=h$, $\kappa=1$ and $d=1$. $m$ is held constant across the kerenls. All methods are performed ten times. Refer to the Table 4, we report the total computation time for 10 runs on 1000 synthetic graphs with average of 20 nodes 50 edges, which indicates our approaches are competitive with the existing graph kernel methods.

[1] Togninalli, Matteo, et al. "Wasserstein weisfeiler-lehman graph kernels." NeurIPS 2019

Hope this response can solve your concerns. We thank the reviewer again for recognizing our work.