Repairing Entities using Star Constraints in Multirelational Graphs

This paper studies a class of neighborhood constraints to characterize and repair erroneous entity information in multi-relational graph data. (1) We propose a class of constraints called star functional dependencies (StarFDs). Unlike conventional integrity constraints, a StarFD enforces value dependencies conditioned by entities and their relevant neighbors, which are identified by a star pattern that incorporates conjunctive regular path queries. StarFDs achieve a balance between expressiveness and complexity: the validation of StarFDs is tractable, and the satisfiability and implication of StarFDs are NP-complete and coNP-complete, respectively. (2) Given a set of StarFDs Σ and a graph G, the entity repair problem is to compute a minimum repair of G by enforcing Σ with the smallest amount of changes. Although this problem is NP-complete and hard to approximate, we show it is feasible to compute repairs in large graphs. Our approach (a) discriminately detects and resolves errors with optimal, approximable and cost-bounded solutions whenever possible, and (b) incurs a time cost determined by Σ and the size of inconsistencies, for all cases. Using real world data, we show that StarFD-based techniques effectively identify and repair errors. We also show that our repairing algorithms benefit other tasks such as fact checking.

Index Terms-data cleaning, knowledge graphs.

• R 1 = (playsFor • operates) ∪ (coachedBy • worksAt)

• R 2 = (playsFor • operates) ∪ (teammate ≤1 • trainsAt) Given football player "Van Persie", R 1 specifies stadiums relevant to him as those "either operated by his club, or those where his coach works at". Similarly, R 2 identifies his relevant facilities as those "operated by his club, or those where he or 229