Efficient Probabilistic Supergraph Search
- Publication Type:
- Journal Article
- IEEE Transactions on Knowledge and Data Engineering, 2016, 28 (4), pp. 965 - 978
- Issue Date:
© 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 gufrom D such that the probability of q containing guis 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: