FastAGEDs+: Fast Approximate Graph Entity Dependency Discovery

ABSTRACT This paper addresses the novel and challenging domain of graph entity dependencies (GEDs) discovery, which aims to identify dependencies in large graphs that are nearly satisfied despite the presence of errors, exceptions and ambiguities in real‐world data. We propose a unique error measure specifically designed for GED semantics and innovatively adapts concepts of disagreement and necessary sets to the realm of graph dependencies. Furthermore, we introduce the FastAGEDs+ algorithm, which significantly enhances efficiency in discovering approximate GEDs, employing a depth‐first search strategy for optimal candidate space traversal. Incorporating an innovative pruning strategy, F ast AGEDs+ efficiently narrows down the search space, significantly reducing computational overhead while maintaining accuracy. Through extensive experimentation on real‐world graphs, we demonstrate the feasibility and scalability of our approach, offering substantial improvements in data quality and management practices.