Answering Top-$k$ k Graph Similarity Queries in Graph Databases.

Zhu, Y; Qin, L; Yu, JX; Cheng, H

Answering Top-$k$ k Graph Similarity Queries in Graph Databases.

Zhu, Y Qin, L

Yu, JX Cheng, H

Permalink

Publisher:: Institute of Electrical and Electronics Engineers
Publication Type:: Journal Article
Citation:: IEEE Transactions on Knowledge and Data Engineering, 2020, 32, pp. 1459-1474
Issue Date:: 2020

Closed Access

	Filename	Description	Size
	08673587 (1).pdf	Published version	1.13 MB	Adobe PDF	View/Open
	Answering Top-k Graph Similarity Queries in Graph Databases. (Submitted Manuscript Version).pdf	Submitted Manuscript Version	1.85 MB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Zhu, Y
dc.contributor.author	Qin, L https://orcid.org/0000-0001-6068-5062
dc.contributor.author	Yu, JX
dc.contributor.author	Cheng, H
dc.date.accessioned	2021-03-09T19:34:24Z
dc.date.available	2021-03-09T19:34:24Z
dc.date.issued	2020
dc.identifier.citation	IEEE Transactions on Knowledge and Data Engineering, 2020, 32, pp. 1459-1474
dc.identifier.issn	1041-4347
dc.identifier.uri	http://hdl.handle.net/10453/146966
dc.description.abstract	Searching similar graphs in graph databases for a query graph has attracted extensive attention recently. Existing works on graph similarity queries are threshold based approaches which return graphs with distances to the query smaller than a given threshold. However, in many applications the number of answer graphs for the same threshold can vary significantly for different queries. In this paper, we study the problem of finding top- $k$ k most similar graphs for a query under the distance measure based on maximum common subgraph (MCS). Since computing MCS is NP-hard, we devise a novel framework to prune unqualified graphs based on the lower bounds of graph distance, and accordingly derive four lower bounds with different tightness and computational cost for pruning. To further reduce the number of MCS computations, we also propose an improved framework based on both lower and upper bounds, and derive three new upper bounds. To support efficient pruning, we design three indexes with different tradeoffs between pruning power and construction cost. To accelerate the index construction, we explore bound relaxation techniques, based on which approximate indexes can be efficiently built. We conducted extensive performance studies on real-life graph datasets to validate the effectiveness and efficiency of our approaches.
dc.language	en
dc.publisher	Institute of Electrical and Electronics Engineers
dc.relation.ispartof	IEEE Transactions on Knowledge and Data Engineering
dc.relation.isbasedon	10.1109/TKDE.2019.2906608
dc.rights	info:eu-repo/semantics/closedAccess
dc.subject	08 Information and Computing Sciences
dc.subject.classification	Information Systems
dc.title	Answering Top-$k$ k Graph Similarity Queries in Graph Databases.
dc.type	Journal Article
utslib.citation.volume	32
utslib.for	08 Information and Computing Sciences
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Strength - AAII - Australian Artificial Intelligence Institute
utslib.copyright.status	closed_access	*
pubs.consider-herdc	false
dc.date.updated	2021-03-09T19:34:23Z
pubs.publication-status	Published
pubs.volume	32

Abstract:

Searching similar graphs in graph databases for a query graph has attracted extensive attention recently. Existing works on graph similarity queries are threshold based approaches which return graphs with distances to the query smaller than a given threshold. However, in many applications the number of answer graphs for the same threshold can vary significantly for different queries. In this paper, we study the problem of finding top- $k$ k most similar graphs for a query under the distance measure based on maximum common subgraph (MCS). Since computing MCS is NP-hard, we devise a novel framework to prune unqualified graphs based on the lower bounds of graph distance, and accordingly derive four lower bounds with different tightness and computational cost for pruning. To further reduce the number of MCS computations, we also propose an improved framework based on both lower and upper bounds, and derive three new upper bounds. To support efficient pruning, we design three indexes with different tradeoffs between pruning power and construction cost. To accelerate the index construction, we explore bound relaxation techniques, based on which approximate indexes can be efficiently built. We conducted extensive performance studies on real-life graph datasets to validate the effectiveness and efficiency of our approaches.

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

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