Back to Search
Start Over
$K$ -Ary Tree Hashing for Fast Graph Classification.
- Source :
-
IEEE Transactions on Knowledge & Data Engineering . May2018, Vol. 30 Issue 5, p936-949. 14p. - Publication Year :
- 2018
-
Abstract
- 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 -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 $K$-ary trees. Based on the traversal table, KATH employs a recursive indexing process that performs only $r$ <alternatives><inline-graphic xlink:href="wu-ieq3-2782278.gif"/></alternatives> times of matrix indexing to generate all $(r-1)$<alternatives> <inline-graphic xlink:href="wu-ieq4-2782278.gif"/></alternatives>-depth $K$<alternatives><inline-graphic xlink:href="wu-ieq5-2782278.gif"/></alternatives> -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 data sets show that KATH runs significantly faster than state-of-the-art methods while achieving competitive or better accuracy. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 10414347
- Volume :
- 30
- Issue :
- 5
- Database :
- Academic Search Index
- Journal :
- IEEE Transactions on Knowledge & Data Engineering
- Publication Type :
- Academic Journal
- Accession number :
- 128843681
- Full Text :
- https://doi.org/10.1109/TKDE.2017.2782278