Fast Random Walk Graph Kernel

Abstract

Previous chapter Next chapter Full AccessProceedings Proceedings of the 2012 SIAM International Conference on Data Mining (SDM)Fast Random Walk Graph KernelU Kang, Hanghang Tong, and Jimeng SunU Kang, Hanghang Tong, and Jimeng Sunpp.828 - 838Chapter DOI:https://doi.org/10.1137/1.9781611972825.71PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAboutAbstract Random walk graph kernel has been used as an important tool for various data mining tasks including classification and similarity computation. Despite its usefulness, however, it suffers from the expensive computational cost which is at least O(n3) or O(m2) 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(n2) 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. Previous chapter Next chapter RelatedDetails Published:2012ISBN:978-1-61197-232-0eISBN:978-1-61197-282-5 https://doi.org/10.1137/1.9781611972825Book Series Name:ProceedingsBook Code:PRDT12Book Pages:1-1150

Keywords

Affiliated Institutions

• Carnegie Mellon University US

Related Publications