Ye Yuan, Guoren Wang, Lei Chen, and Haixun Wang
Many studies have been conducted on seeking an efﬁcient solution for subgraph similarity search over deterministic (certain) graphs due to its wide application in many ﬁelds, including bioinformatics, social network analysis, and RDF data management. All these works assume that the underlying data are deterministic. However, in reality, graphs are often noisy and uncertain due to various factors, such as errors in data extraction, inconsistencies in data inte- gration, and privacy preserving purposes. Therefore, in this paper, we study subgraph similarity search over large probabilistic graph databases. Different from previous works that assume edges in an uncertain graph are independent of each other. We study the uncertain graphs where edges' occurrences are correlated. We formally prove that subgraph similarity search over probabilistic graphs is #P-complete, thus, we employ a ﬁltering-and-veriﬁcation framework to speed up the search. In the ﬁltering phase, we develop tight lower and upper bounds of subgraph similar probability based on a probabilistic matrix index, PMI. PMI is composed of discriminative subgraph features associated with tight lower and upper bounds of subgraph isomorphic probability. Based on PMI, we can sort out a large number of probabilistic graphs and maximizes the pruning capability. During the veriﬁcation phase, we develop an efficient sampling algorithm to validate the remaining candidates. The efficiency of our proposed solutions has been veriﬁed through extensive experiments.