Strict and Flexible Rule-Based Graph Repairing

Yurong Cheng, Lei Chen, Ye Yuan*, Guoren Wang, Boyang Li, Fusheng Jin

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)

Abstract

Real-life graph datasets extracted from the Web are inevitably full of incompleteness, conflicts, and redundancies, so graph data cleaning shows its necessity. Although rules like data dependencies have been widely studied in relational data repairing, very few works exist to repair graph data. In this article, we introduce a repairing semantics for graphs, called Graph-Repairing Rules (GRRs). This semantics can capture the incompleteness, conflicts, and redundancies in graphs and indicate how to correct these errors. However, this graph repairing semantics can only repair the graphs strictly isomorphic to the rule patterns, which decreases the utility of the rules. To overcome this shortcoming, we further propose a flexible rule-based graph repairing semantics (called δ-GRR). We study three fundamental problems associated with both GRRs and δ-GRRs, consistency, implication, and termination, which show whether a given set of rules make sense. Repairing the graph data using GRRs or δ-GRRs involves a problem of finding isomorphic subgraphs of the graph data, which is NP-complete. To efficiently circumvent the complex calculation of subgraph isomorphism, we design a decomposition-and-join strategy to solve this problem. Extensive experiments on real datasets show that our two graph repairing semantics and corresponding repairing algorithms can effectively and efficiently repair real-life graph data.

Original languageEnglish
Pages (from-to)3521-3535
Number of pages15
JournalIEEE Transactions on Knowledge and Data Engineering
Volume34
Issue number7
DOIs
Publication statusPublished - 1 Jul 2022

Keywords

  • Rule
  • flexible
  • graph repair
  • repair algorithms
  • semantics

Fingerprint

Dive into the research topics of 'Strict and Flexible Rule-Based Graph Repairing'. Together they form a unique fingerprint.

Cite this