Efficient Probabilistic Supergraph Search

Publication Type:
Journal Article
Citation:
IEEE Transactions on Knowledge and Data Engineering, 2016, 28 (4), pp. 965 - 978
Issue Date:
2016-04-01
Full metadata record
Files in This Item:
Filename Description Size
TKDE_2016_uncertain_graph.pdfAccepted Manuscript Version960.28 kB
Adobe PDF
© 2015 IEEE. Given a query graph q, retrieving the data graphs g from a set D of data graphs such that q contains g, namely supergraph containment search, is fundamental in graph data analysis with a wide range of real applications. It is very challenging due to the NP-Completeness of subgraph isomorphism testing. Driven by many real applications, in this paper, we study the problem of probabilistic supergraph search; that is, given a set D of uncertain data graphs, a certain query graph q and a probability threshold θ, we retrieve the data graphs g u from D such that the probability of q containing g u is not smaller than θ. We show that besides the NP-Completeness of subgraph isomorphism testing, the problem of calculating probabilities is #P-Complete; thus, it is even more challenging than the supergraph containment search. To tackle the computational hardness, we first propose two novel pruning rules, based on probabilistic connectivity and features, respectively, to efficiently prune non-promising data graphs. Then, efficient verification algorithms are developed with the aim of sharing computation and terminating non-promising computation as early as possible. Extensive performance studies on both real and synthetic data demonstrate the efficiency and effectiveness of our techniques in practice.
Please use this identifier to cite or link to this item: