K-Ary Tree Hashing for Fast Graph Classification

Institute of Electrical and Electronics Engineers
Publication Type:
Journal Article
IEEE Transactions on Knowledge and Data Engineering, 2017
Issue Date:
Full metadata record
Files in This Item:
Filename Description Size
2CF23C19-80F0-4064-AC1A-3EDAF30EC244 am.pdfAccepted manuscript Version1.66 MB
Adobe PDF
IEEE Existing graph classification usually relies on an exhaustive enumeration of substructure patterns, where the number of substructures expands exponentially w.r.t. with the size of the graph set. Recently, the Weisfeiler-Lehman (WL) graph kernel has achieved the best performance in terms of both accuracy and efficiency among state-of-the-art methods. However, it is still time-consuming, especially for large-scale graph classification tasks. In this paper, we present a < formula > < tex > $k$ < /tex > < /formula > -Ary Tree based Hashing (KATH) algorithm, which is able to obtain competitive accuracy with a very fast runtime. The main idea of KATH is to construct a traversal table to quickly approximate the subtree patterns in WL using < formula > < tex > $k$ < /tex > < /formula > -ary trees. Based on the traversal table, KATH employs a recursive indexing process that performs only < formula > < tex > $r$ < /tex > < /formula > times of matrix indexing to generate all < formula > < tex > $(r-1)$ < /tex > < /formula > -depth < formula > < tex > $k$ < /tex > < /formula > -ary trees, where the leaf node labels of a tree can uniquely specify the pattern. After that, the MinHash scheme is used to fingerprint the acquired subtree patterns for a graph. Our experimental results on both real world and synthetic datasets show that KATH runs significantly faster than state-of-the-art methods while achieving competitive or better accuracy.
Please use this identifier to cite or link to this item: