Human-Powered Data Cleaning for Probabilistic Reachability Queries on Uncertain Graphs

Xin Lin, Yun Peng*, Byron Choi, Jianliang Xu

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

11 Citations (Scopus)


Uncertain graph models are widely used in real-world applications such as knowledge graphs and social networks. To capture the uncertainty, each edge in an uncertain graph is associated with an existential probability that signifies the likelihood of the existence of the edge. One notable issue of querying uncertain graphs is that the results are sometimes uninformative because of the edge uncertainty. In this paper, we consider probabilistic reachability queries, which are one of the fundamental classes of graph queries. To make the results more informative, we adopt a crowdsourcing-based approach to clean the uncertain edges. However, considering the time and monetary cost of crowdsourcing, it is a problem to efficiently select a limited set of edges for cleaning that maximizes the quality improvement. We prove that the edge selection problem is #P-hard. In light of the hardness of the problem, we propose a series of edge selection algorithms, followed by a number of optimization techniques and pruning heuristics for reducing the computation time. Our experimental results demonstrate that our proposed techniques outperform a random selection by up to 27 times in terms of the result quality improvement and the brute-force solution by up to 60 times in terms of the elapsed time.

Original languageEnglish
Pages (from-to)1452-1465
Number of pages14
JournalIEEE Transactions on Knowledge and Data Engineering
Issue number7
Early online date17 Mar 2017
Publication statusPublished - 1 Jul 2017

Scopus Subject Areas

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics


Dive into the research topics of 'Human-Powered Data Cleaning for Probabilistic Reachability Queries on Uncertain Graphs'. Together they form a unique fingerprint.

Cite this