Towards Subgraph Isomorphism Counting with Graph Kernels

• I would suggest the authors give some context or motivate why it is important to count subgraphs/substructures. Are there any individuals or communities interested in this task? For the experiments, the authors construct some synthetic datasets and they also employ datasets whose inherent task is different from the one considered in this paper (graph classification datasets from the TUDataset repository). Thus, it is not clear to me whether there is interest into this task.

• The originality of the paper is limited. The idea of re-embedding the input graphs into a second feature space and the proposed implicit schemes are not new and have been proposed in prior work [1]. However, in [1] the kernels are evaluated in a different task (graph classification). Furthermore, the neighborhood-aware color assignment algorithm is a trivial modification of the color assignment algorithms of WL kernels.

• The study is purely empirical and no theoretical results are provided. Although this is not generally a weakness, I would expect such a paper to provide more extensive experimental results, ablation studies, etc. In my view, the experimental evaluation is limited and thus not fully convincing.

• The baseline methods are weak. While high-order WL algorithms are included into the list of kernels, only GNNs that are at most as powerful as 1-WL are considered. The results would be more convincing if higher-order models such as the ones proposed in [2],[3] and [4] were included into the list of baselines.

• Definition 3.4 is wrong. For a function to be a kernel, it needs to be symmetric and positive semi-definite.

[1] Nikolentzos, G., & Vazirgiannis, M. "Enhancing graph kernels via successive embeddings". In Proceedings of the 27th ACM International Conference on Information and Knowledge Management, pp. 1583-1586, 2018.
[2] Morris, C., Ritzert, M., Fey, M., Hamilton, W. L., Lenssen, J. E., Rattan, G., & Grohe, M. "Weisfeiler and leman go neural: Higher-order graph neural networks". In Proceedings of the 33rd AAAI Conference on Artificial Intelligence, pp. 4602-4609, 2019.
[3] Morris, C., Rattan, G., & Mutzel, P. "Weisfeiler and Leman go sparse: Towards scalable higher-order graph embeddings". Advances in Neural Information Processing Systems, pp. 21824-21840, 2020.
[4] Maron, H., Ben-Hamu, H., Serviansky, H., & Lipman, Y. "Provably powerful graph networks. Advances in Neural Information Processing Systems, pp. 2156-2167, 2019.

I think this paper fails to present any advantages of graph kernel methods for solving subgraph isomorphism counting problems over the other existing methods.

• For homogeneous data, this paper demonstrates that the 3-WL kernel combined with the proposed neighborhood information extraction outperforms the existing learning approach where neural network is used directly. However, for homogeneous data, as described in Section 2, there are various non-learning approximation algorithms like sampling (Jha et al., 2015) and color coding (Bressman et al, 2019). Thus, for homogeneous data, the performance should also be compared with these methods.
• For heterogeneous data, the best of the kernel method exhibits comparable results to neural network-based methods (RGIN, Liu et al., 2020). However, the best kernel used in the kernel method differs for different topologies: "GR, Ridge, RBF" for ENZYMES, and "2-WL, Ridge, Linear, NIE" for NC1109. The author says that the fact that the 3-WL kernel (working well for homogeneous data) fails for heterogeneous data "serve as a foundation for further research and advancements in the field of graph kernels," but there are almost no consideration and examination for this fact in this paper.

To facilitate the research on graph kernel methods, at least some considerations and examinations are needed to explain:

• Why 3-WL kernel, which works well for homogeneous data, does not work well on heterogeneous data?
• Why neighborhood information extraction, which is effective for homogeneous data, is less effective for heterogeneous data?

Minor comment: The descriptions for Weisfeiler-Leman algorithm in pages 3 and 4 are hard to grasp, since there are almost no descriptions for the $`Color`$ procedure; it is only said as "a function to assign colors to to vertices." $`Color`$ seems to have two arguments, but it cannot be understood that what are given as arguments and what is returned as a result. Please improve the description for WL algorithm since it relates to the neighborhood information extraction that is one of the core contributions of this paper.

1. The paper could benefit from the inclusion of a clearly defined real-world application or use case to highlight the practical significance of the problem and its solution. While the paper discusses various applications of subgraph isomorphism counting, a concrete application or case study would better illustrate the real-world relevance of the research.

2. The complexity and computational efficiency of the proposed method are not adequately discussed. It is essential to conduct a thorough analysis of the runtime complexity and compare it with existing models to provide insights of its efficiency.

3. The proposed method inherits the high computational cost associated with graph kernels, which limits its scalability, particularly when dealing with large graphs. Discussing potential strategies to mitigate this limitation would be beneficial.

4. The inconsistency in the y-axis scaling of Figure 4a compared to other subfigures should be rectified for clarity and to prevent any potential misunderstanding.

5. The experiments show that GNN-based methods consistently outperform kernel-based methods on ENZYMES and NCI109 datasets. It would be valuable to expand the experimental scope to determine whether similar conclusions hold for other heterogeneous datasets.

6. In terms of baseline selection, the best performing model CompGCN was proposed in 2020. It is desirable and more convincing to compare with recent stronger models.

7. Consider adding a comparison with higher-order GNNs, such as the references [1], [2], and [3], to provide a more comprehensive assessment of the proposed approach.

[1] Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. AAAI 2019 [2] Bouritsas G, Frasca F, Zafeiriou S, Bronstein MM. Improving graph neural network expressivity via subgraph isomorphism counting. TPAMI 2022 [3] Li J, Peng H, Cao Y, Dou Y, Zhang H, Philip SY, He L. Higher-order attribute-enhancing heterogeneous graph neural networks. TKDE 2021