FastAGEDs+: Fast Approximate Graph Entity Dependency Discovery

Sibo Zhao

doi:10.1111/exsy.70152

FastAGEDs+: Fast Approximate Graph Entity Dependency Discovery

2025-10-08

0

PRE

AI

Vincent Mwintieru Nofong

DOI：10.1111/exsy.70152

Original

Original request for help

Save

Abstract

En 中文

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, FastAGEDs+ 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.

Keywords:

approximate dependency discovery

depth-first search

error measurement in graphs

pruning strategy

FastAGEDs+: Fast Approximate Graph Entity Dependency Discovery

Abstract

Journal

Organization