Scalable kernels for graphs with continuous attributes
While graphs with continuous node attributes arise in many applications, stateof-the-art graph kernels for comparing continuous-attributed graphs suffer from a high runtime complexity. For instance, the popular shortest path kernel scales as O(n 4 ), where n is the number of nodes. In this paper, we present a class of graph kernels with computational complexity O(n 2 (m + log n + δ 2 + d)), where δ is the graph diameter, m is the number of edges, and d is the dimension of the node attributes. Due to the sparsity and small diameter of real-world graphs, these kernels typically scale comfortably to large graphs. In our experiments, the presented kernels outperform state-of-the-art kernels in terms of speed and accuracy on classification benchmark datasets.
This paper proposed a new kernel function and its fast 
      computation algorithm for graphs with continuous attribute values. The 
      proposed algorithm is much more efficient than competitive methods. The 
      advantages of proposed method was proved by theoretically and evaluated by 
      numerical experiments. Quality: The efficiency of the proposed 
      method was through investigated both by theory (proved the computational 
      complexity) and by numerical experiments, which shows the proposed method 
      is much better than related works. But the new kernel function itself was 
      not analyzed enough, which was only evaluated by performance results on 
      classification tasks. One might have the question which pairs of graphs 
      are similar/dissimilar on the proposed kernel (similarity measure). The 
      comparison with other kernel functions using toy graph examples would be 
      necessary. Clarity: The paper is well organized and 
      understandable for readers. Originality: This paper proposed a 
      novel method, with a new kernel for graphs and furthermore proposed a fast 
      computation algorithm for the new kernel. The proposed method can manage 
      massive datasets of graphs with continuous attribute values, which cannot 
      be managed by conventional methods. Significance: The proposed 
      method and results would be interesting. Because the result is general, 
      this method could be applicable in a lot of applications. 
      Other comments: 1. The proposed computation might 
      evaluate the kernel values for same pairs of paths multiple times, which 
      means that the algorithm might assume the path from $v_a$ to $v_b$ and the 
      path from $v_b$ to $v_a$ as different paths. If it is true, analyzing how 
      it could affect to the similarity measure would be important. 2. 
      The caption in Table 2 should mention the meaning of the real values 
      even if it is mentioned in the main sentence. And, what are the values in 
      the parentheses in the row of SP? If it is average runtimes, they are less 
      than 24 hours. Then the runtime of SP should not be OUT OF TIME.