On Valid Optimal Assignment Kernels and Applications to Graph Classification
The success of kernel methods has initiated the design of novel positive semidefinite functions, in particular for structured data. A leading design paradigm for this is the convolution kernel, which decomposes structured objects into their parts and sums over all pairs of parts. Assignment kernels, in contrast, are obtained from an optimal bijection between parts, which can provide a more valid notion of similarity. In general however, optimal assignments yield indefinite functions, which complicates their use in kernel methods. We characterize a class of base kernels used to compare parts that guarantees positive semidefinite optimal assignment kernels. These base kernels give rise to hierarchies from which the optimal assignment kernels are computed in linear time by histogram intersection. We apply these results by developing the Weisfeiler-Lehman optimal assignment kernel for graphs. It provides high classification accuracy on widely-used benchmark data sets improving over the original Weisfeiler-Lehman kernel.
The paper describes an approach to construct valid (symmetric and p.s.d.) optimal assignment kernels that are built on strong base kernels. Therefore they introduce the properties of strong kernels and show, that they are induced by a hierarchy on a set of elements with increasing weights (from root to leaves) and, vice versa, every strong kernel induces such a hierarchy. Thus, on every set, by building a hierarchy, e.g. on the set of vertices of a graph, a strong kernel is induced. Using this hierarchy they derive a feature mapping and show that the scalar product of this feature mapping equals the strong kernel which therefore proofs that the strong kernel is a valid kernel. Subsequently they show that the optimal assignment can be calculated by a histogram intersection kernel where the histograms are calculated using the earlier introduced feature mapping. This allows for efficient calculation of the optimal assignment kernel once the hierarchy is built.  They experimentally show that by integrating their optimal assignment kernel into existing methods one can reach higher accuracies for graph classification than state-of-the-art methods.  
The novelty and clarity of the work seem limited.   ------- Weisfeiler Lehman-OA -------  The least convincing part of the paper is the description of the Weisfeiler-Lehman OA kernel:  - the second argument in equation (2) should be v not u. - the authors miss to cite Shervashidze et al. (JMLR 2011) which already presents variants of the Weisfeiler Lehman kernel, that outperform the classic one. It would have been appropriate to compare to the best of these variants. - If the proposed algorithm just counts all matching labels in the refinement sequence of all pairs of nodes, then it is completely unclear whether it actually differs from the classic Weisfeiler-Lehman kernel (which takes the linear product between the refinement sequence histograms, which is the sum over the dirac kernels on the refinement sequence of all pairs of nodes). The authors have to make this difference much clearer, define all functions/variables used (k_delta) and give an intuition will this - at best minor modification - of the WL kernel should lead to better results.     ------------------ Proof Theorem 1 ------------------ The proof of Theorem 1 is not very clear. It is only shown that the histogram intersection kernel is equal to W(B) but it is not explicitly shown that this bijection B is necessarily the one maximising W(B). From my understanding this follows from the construction of the hierarchy which assures that the kernel between to nodes is maximised. However, this must be shown explicitly in the proof of Theorem 1 in order to proof that the histogram intersection kernel is equal to the optimal assignment kernel. Otherwise the proof is not complete. This missing link makes the paper also very hard to follow and requires to first understand lemma 2 in order to follow the reasoning.  ------------------ Proof Lemma 2 ------------------ Fig. 1 is supposed to illustrate the proof of lemma 2, but it contains labels that are not mentioned in the text of the main article (e.g. b_1, b_2, p',c). I suggest to either modify Fig. 1 such that it fits the sketch of the proof outlined in the main article or to move the figure to the supplement. Since the construction of the hierarchy is essential for the proof of the main theorem 1, I would strongly suggest to add the complete proof to the main paper. Furthermore, there are two typos in the proof: 1. in line 128 main article, change X_{i} to \chi_{i} 2. in line 24 supplement, I suppose it should say 'since z is above LCA(B)'  ------------------ Figure 3 ------------------ The caption of figure 3 is unclear to me. It would be helpful to mention, that the elements in X and Y can be represented by the hierarchy in Fig. 2.   I am not sure what is meant by 'there are three vertices in X that are children of a in the hierarchy, but not represented explicitly'. As far as I understand the method, \chi = {a,b,c}, and one can build a tree T on \chi as in Fig. 2. Together with the weights w, this results in the  hierarchy in Fig. 2. Now, using that X = {a,a,a,b,c} and Y = {a,b,b,c,c} and applying the definition of the histogram kernel, one can arrive at the histograms in Fig. 3b. I don't see the link between the above sentence in the figure caption. Furthermore, in Fig. 3a, I guess the edges between elements in X and Y are supposed to represent the bijections. Still, their link to the histogram kernels remains unclear to me, and it would be good to explain this detail in the caption as well.   ------------------ Missing references ------------------ 1. In the paper, the Hungarian method is mentioned twice. Please add a citation or a definition. 2. The chapters 2 and 3 in the supplement are not referred to in the main article. 3. Outline difference between optimal assignment kernels and convolution kernels in more detail, or add reference