Efficient Probabilistic Supergraph Search

Publication Type:
Journal Article
IEEE Transactions on Knowledge and Data Engineering, 2016, 28 (4), pp. 965 - 978
Issue Date:
Filename Description Size
TKDE_2016_uncertain_graph.pdfAccepted Manuscript Version960.28 kB
Adobe PDF
Full metadata record
© 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 gu from D such that the probability of q containing gu 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: