Catching Numeric Inconsistencies in Graphs

Wenfei Fan, Xueli Liu, Ping Lu, Chao Tian

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

Numeric inconsistencies are common in real-life knowledge bases and social networks. To catch such errors, we propose to extend graph functional dependencies with linear arithmetic expressions and comparison predicates, referred to as NGDs. We study fundamental problems for NGDs. We show that their satisfiability, implication and validation problems are Σp2 -complete, Πp2 -complete and coNP-complete, respectively. However, if we allow non-linear arithmetic expressions, even of degree at most 2, the satisfiability and implication problems become undecidable. In other words, NGDs strike a balance between expressivity and complexity.
To make practical use of NGDs, we develop an incremental algorithm IncDect to detect errors in a graph G using NGDs, in response to updates ∆G to G. We show that the incremental validation problem is coNP-complete. Nonetheless, algorithm IncDect is localizable, i.e., its cost is determined by small neighbors of nodes in ∆G instead of the entire G. Moreover, we parallelize IncDect such that it guarantees to reduce running time with the increase of processors. Using real-life and synthetic graphs, we experimentally verify the scalability and efficiency of the algorithms.
Original languageEnglish
Title of host publicationProceedings of the 2018 International Conference on Management of Data (SIGMOD'18)
Place of PublicationTexas, USA
Number of pages13
ISBN (Electronic)978-1-4503-4703-7
Publication statusPublished - 27 May 2018
Event2018 ACM SIGMOD/PODS International Conference on Management of Data - Houston, United States
Duration: 10 Jun 201815 Jun 2018


Conference2018 ACM SIGMOD/PODS International Conference on Management of Data
Abbreviated titleSIGMOD'18
Country/TerritoryUnited States
Internet address

Keywords / Materials (for Non-textual outputs)

  • numeric errors
  • graph dependencies
  • incremental validation


Dive into the research topics of 'Catching Numeric Inconsistencies in Graphs'. Together they form a unique fingerprint.

Cite this