Leveraging graph dimensions in online graph search

Publication Type:
Journal Article
Proceedings of the VLDB Endowment, 2014, 8 (1), pp. 85 - 96
Issue Date:
Full metadata record
Files in This Item:
Filename Description Size
Thumbnailp85-zhu.pdfAccepted Manuscript493.66 kB
Adobe PDF
Graphs have been widely used due to its expressive power to model complicated relationships. However, given a graph database D G = {g 1 ; g 2 ; ··· , g n }, it is challenging to process graph queries since a basic graph query usually involves costly graph operations such as maximum common subgraph and graph edit distance computation, which are NP-hard. In this paper, we study a novel DS-preserved mapping which maps graphs in a graph database D G onto a multidimensional space M G under a structural dimension Musing a mapping function φ(). The DS-preserved mapping preserves two things: distance and structure. By the distance-preserving, it means that any two graphs g i and g j in D G must map to two data objects φ(g i ) and φ(g j ) in M G , such that the distance, d(φ(g i ); φ(g j ), between φ(g i ) and φ(g j ) in M G approximates the graph dissimilarity δ(g i ; g j ) in D G . By the structure-preserving, it further means that for a given unseen query graph q, the distance between q and any graph g i in D G needs to be preserved such that δ(q; g i ) ≈ d(φ(q); φ(g i )). We discuss the rationality of using graph dimension M for online graph processing, and show how to identify a small set of subgraphs to form M efficiently. We propose an iterative algorithm DSPM to compute the graph dimension, and discuss its optimization techniques. We also give an approximate algorithm DSPMap in order to handle a large graph database. We conduct extensive performance studies on both real and synthetic datasets to evaluate the top-k similarity query which is to find top-k similar graphs from D G for a query graph, and show the effectiveness and efficiency of our approaches. © 2014 VLDB.
Please use this identifier to cite or link to this item: