K-Ary Tree Hashing for Fast Graph Classification

Wu, W; Li, B; Chen, L; Zhu, X; Zhang, C

K-Ary Tree Hashing for Fast Graph Classification

Wu, W

Li, B

Chen, L

Zhu, X Zhang, C

Permalink

Publication Type:: Journal Article
Citation:: IEEE Transactions on Knowledge and Data Engineering, 2018, 30 (5), pp. 936 - 949
Issue Date:: 2018-05-01

In Progress

	Filename	Description	Size
	2CF23C19-80F0-4064-AC1A-3EDAF30EC244 am.pdf	Accepted manuscript Version	1.66 MB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is being processed and is not currently available.

Full metadata record

Field	Value	Language
dc.contributor.author	Wu, W https://orcid.org/0000-0002-0975-4613	en_US
dc.contributor.author	Li, B https://orcid.org/0000-0002-9633-0033	en_US
dc.contributor.author	Chen, L https://orcid.org/0000-0002-6468-5729	en_US
dc.contributor.author	Zhu, X	en_US
dc.contributor.author	Zhang, C https://orcid.org/0000-0001-5715-7154	en_US
dc.date.issued	2018-05-01	en_US
dc.identifier.citation	IEEE Transactions on Knowledge and Data Engineering, 2018, 30 (5), pp. 936 - 949	en_US
dc.identifier.issn	1041-4347	en_US
dc.identifier.uri	http://hdl.handle.net/10453/121848
dc.description.abstract	© 1989-2012 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 -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 times of matrix indexing to generate all (r-1)-depth K -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.	en_US
dc.relation.ispartof	IEEE Transactions on Knowledge and Data Engineering	en_US
dc.relation.isbasedon	10.1109/TKDE.2017.2782278	en_US
dc.subject.classification	Information Systems	en_US
dc.title	K-Ary Tree Hashing for Fast Graph Classification	en_US
dc.type	Journal Article
utslib.citation.volume	5	en_US
utslib.citation.volume	30	en_US
utslib.for	0804 Data Format	en_US
utslib.for	08 Information and Computing Sciences	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/DVC (International)
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology/School of Computer Science
pubs.organisational-group	/University of Technology Sydney/Strength - AAI - Advanced Analytics Institute Research Centre
pubs.organisational-group	/University of Technology Sydney/Strength - ACRI - Australia China Relations Institute
pubs.organisational-group	/University of Technology Sydney/Strength - CAI - Centre for Artificial Intelligence
pubs.organisational-group	/University of Technology Sydney/Students
utslib.copyright.status	in_progress
pubs.issue	5	en_US
pubs.publication-status	Published	en_US
pubs.volume	30	en_US

Abstract:

© 1989-2012 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 -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 times of matrix indexing to generate all (r-1)-depth K -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.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/121848