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

Institute of Electrical and Electronics Engineers
Publication Type:
Journal Article
IEEE Transactions on Knowledge and Data Engineering, 2020, 32, pp. 1459-1474
Issue Date:
Filename Description Size
08673587 (1).pdfPublished version1.13 MB
Adobe PDF
Answering Top-k Graph Similarity Queries in Graph Databases. (Submitted Manuscript Version).pdfSubmitted Manuscript Version1.85 MB
Adobe PDF
Full metadata record
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: