Fast random walk graph kernel

Random walk graph kernel has been used as an important tool for various data mining tasks including classi fication and similarity computation. Despite its usefulness, however, it suffers from the expensive computational cost which is at least O(n³) or O(m²) for graphs with n nodes and m edges. In this paper, we propose Ark, a set of fast algorithms for random walk graph kernel computation. Ark is based on the observation that real graphs have much lower intrinsic ranks, compared with the orders of the graphs. Ark exploits the low rank structure to quickly compute random walk graph kernels in O(n ²) or O(m) time. Experimental results show that our method is up to 97,865× faster than the existing algorithms, while providing more than 91.3% of the accuracies.