Paper Info
Title
Strict and Flexible Rule-Based Graph Repairing
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 <i>Graph-Repairing Rules</i> ( <inline-formula><tex-math notation="LaTeX">${\sf GRR}$</tex-math></inline-formula> s). 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 <inline-formula><tex-math notation="LaTeX">$\delta$</tex-math></inline-formula> <i>-GRR</i> ). We study three fundamental problems associated with both <inline-formula><tex-math notation="LaTeX">${\sf GRR}$</tex-math></inline-formula> s and <inline-formula><tex-math notation="LaTeX">$\delta$</tex-math></inline-formula> <i>-GRR</i> s, consistency, implication, and termination, which show whether a given set of rules make sense. Repairing the graph data using <inline-formula><tex-math notation="LaTeX">${\sf GRR}$</tex-math></inline-formula> s or <inline-formula><tex-math notation="LaTeX">$\delta$</tex-math></inline-formula> <i>-GRR</i> s 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.
Year
DOI
Venue
2022
10.1109/TKDE.2020.3019817
IEEE Transactions on Knowledge and Data Engineering
Keywords
DocType
Volume
Rule,graph repair,flexible,semantics,repair algorithms
Journal
34
Issue
ISSN
Citations 
7
1041-4347
0
PageRank 
References 
Authors
0.34
21
6
Name
Order
Citations
PageRank
Yurong Cheng11098.90
Lei Chen26239395.84
Ye Yuan311724.40
Guoren Wang41366159.46
Boyang Li58212.61
Fusheng Jin652.88