Edinburgh Research Explorer

Catching Numeric Inconsistencies in Graphs

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

Related Edinburgh Organisations

Open Access permissions



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
CountryUnited States
Internet address


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.

    Research areas

  • numeric errors, graph dependencies, incremental validation


2018 ACM SIGMOD/PODS International Conference on Management of Data


Houston, United States

Event: Conference

Download statistics

No data available

ID: 64279860