Efficient subgraph similarity search on large probabilistic graph databases
Authors:
Open Access
- 1 May 2012
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the VLDB Endowment
- Vol. 5 (9) , 800-811
Abstract
Many studies have been conducted on seeking the efficient solution for subgraph similarity search over certain (deterministic) graphs due to its wide application in many fields, including bioinformatics, social network analysis, and Resource Description Framework (RDF) data management. All these works assume that the underlying data are certain. However, in reality, graphs are often noisy and uncertain due to various factors, such as errors in data extraction, inconsistencies in data integration, and privacy preserving purposes. Therefore, in this paper, we study subgraph similarity search on large probabilistic graph databases. Different from previous works assuming that 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 filter-and-verify framework to speed up the search. In the filtering phase, we develop tight lower and upper bounds of subgraph similarity probability based on a probabilistic matrix index, PMI. PMI is composed of discriminative subgraph features associated with tight lower and upper bounds of subgraph isomorphism probability . Based on PMI, we can sort out a large number of probabilistic graphs and maximize the pruning capability. During the verification phase, we develop an efficient sampling algorithm to validate the remaining candidates. The efficiency of our proposed solutions has been verified through extensive experiments.Keywords
All Related Versions
This publication has 34 references indexed in Scilit:
- Query Evaluation on Probabilistic RDF Databases2009
- Network motif identification in stochastic networksProceedings of the National Academy of Sciences, 2006
- Exploiting indirect neighbours and topological weight to predict protein function from protein–protein interactionsBioinformatics, 2006
- A (sub)graph isomorphism algorithm for matching large graphsIEEE Transactions on Pattern Analysis and Machine Intelligence, 2004
- Predicting Protein Complex Membership Using Probabilistic Network ReliabilityGenome Research, 2004
- Gaining confidence in high-throughput protein interaction networksNature Biotechnology, 2003
- Interaction generality, a measurement to assess the reliability of a protein-protein interactionNucleic Acids Research, 2002
- Inference in belief networks: A procedural guideInternational Journal of Approximate Reasoning, 1996
- Weighted and unweighted maximum clique algorithms with upper bounds from fractional coloringAlgorithmica, 1996
- Efficient algorithm for finding all minimal edge cuts of a nonoriented graphCybernetics and Systems Analysis, 1986