Efficient and Tractable Conflict Detection in Knowledge Graphs via Path Analysis

Knowledge graphs (KGs), which utilize graph structures to represent real-world facts, are pivotal in information retrieval and artificial intelligence. However, heuristic knowledge graph construction methods will produce errors. Some conflicts, such as expression ambiguities, are challenging to detect at triple granularity and require semantic analysis together with other triples. In this paper, we propose an approach for conflict detection at path granularity in large-scale knowledge graphs. It is based on rules on a specific pattern. Different from previous rules, our rules are defined with a ring pattern to extend error detection from triple granularity to path granularity. We prove that indicating whether a triple brings such conflicts only requires dealing with any one of its related ring structures, which can significantly reduce the complexity. We propose <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">${\mathsf {{RingE}}}$</tex-math></inline-formula>, a novel Ring Embedding method, to detect ring-pattern conflicts, and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">${\mathsf {{DeCon}}}$</tex-math></inline-formula>, a CONflict DEtection framework suitable for both static and incremental scenes. This framework divides the ring-pattern conflict detection task in KGs into ring discovery and conflict detection. We also design a pruning strategy for ring discovery that reduces the time complexity from the exponential level to the polynomial level. Using real-world graphs, we experimentally verify that our algorithms are effective and feasible for large graphs. Our case study also verifies that <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">${\mathsf {{DeCon}}}$</tex-math></inline-formula> can detect real conflicts.