The Multiscale Laplacian Graph Kernel
Many real world graphs, such as the graphs of molecules, exhibit structure at multiple different scales, but most existing kernels between graphs are either purely local or purely global in character. In contrast, by building a hierarchy of nested subgraphs, the Multiscale Laplacian Graph kernels (MLG kernels) that we define in this paper can account for structure at a range of different scales. At the heart of the MLG construction is another new graph kernel, called the Feature Space Laplacian Graph kernel (FLG kernel), which has the property that it can lift a base kernel defined on the vertices of two graphs to a kernel between the graphs. The MLG kernel applies such FLG kernels to subgraphs recursively. To make the MLG kernel computationally feasible, we also introduce a randomized projection procedure, similar to the Nyström method, but for RKHS operators.
The paper proposes a new graph kernel called the Multiscale Laplacian Graph (MLG) Kernel, which is itself based on the Feature space Laplacian Graph (FLG) kernel, still presented by the authors. The MLP graph kernel relies on the graph spectral decomposition, having the advantage to account for learning similarities at multiple different scales, considering both the overall and local structures. The mathematical formulations and intuitive steps leading to the novel approach are well presented in the paper. Experiments are also conducted for comparison with the state of the art. The MLG outperforms existing methods in 4 out of 6 datasets analysed, and it is competitive in the remaining 2. 
---------------- Overall Opinion ----------------  The paper is overall well written, and the methods are technically well presented. My main concerns are relative to the missing intuition and unclear explanations in some parts of the paper, as well as to provide more details in the experimental section. More specific information are given in the comments below.     ------- Novelty -------  The authors propose a new graph kernel, which appears to be competitive with the state of the art. I would overall consider the paper as based on a novel idea.     ----------------- Minor comments -----------------  Style and language issues:  - Line 20: "have been appeared" is formally incorrect, the authors could use (for instance) "have appeared" or "have been proposed" - Line 46: the meaning of "it can take structure into account at multiple different scales" is not fully clear, possibly the authors could correct with "it can take into account structures at multiple different scales" - Line 218: the neighbourhoods ... "have" to be defined, rather than "are".   References:  - Reference [10] is poorly written: rather than "jmlr" a clear statement as in reference [5] would be preferable.     ----------------- Major comments -----------------  Include unclear definitions, notation, technical incongruences and poor intuitive explanations.    Section 2:  - It would be nice to better clarify the notation, in particular regarding graphs, before describing the method. For instance: are the words node's attributes, features and labels used with the same meaning? How are these exactly defined?  - Lines 81, 84 and 95: the "low eigenvalue eigenvectors" is unclear, one could just say the "low eigenvalues" or "the low eigenvalues with corresponding eigenvectors". This might have been considered as minor concern, but since is often repeated it makes its meaning unclear; I therefore consider it as a major comment.   - Line 149-152: the sentence is not clear. Though the mathematics formulation well defines the differences between the two kernels, some more effort should be done here to better explain the intuition behind.    Section 3:  - It would be nice to give more intuitive explanation on what the "level L" represents and how this affects the algorithm. Possibly, also the similarity with the WL kernel should be highlighted.    Section 4:  - The pseudocode algorithm is provided in the Supplementary Materials. I would suggest to include it in the main paper, as it provides the reader with an intuitive and detailed description of the method proposed.    Section 5:  - Are the authors using a stratified cross validation? If this is the case, it should be explicitly stated in the paper, otherwise it is advised to repeat the experiments with a stratified approach to avoid overfitting.  - It would be nice to include the FLG kernel, defined by the author themselves, as a further baseline comparison. This would help to strengthen the real advantages of the proposed MLG kernel.     ----------- Next Steps -----------  I would suggest to revise the paper according to the comments and modifications that I stated above. After that, I would consider the paper to be at an appropriate level for a NIPS publication.