  This paper studies the discovery of approximate rules in property graphs. We
propose a semantically meaningful measure of error for mining graph entity
dependencies (GEDs) at almost hold, to tolerate errors and inconsistencies that
exist in real-world graphs. We present a new characterisation of GED
satisfaction, and devise a depth-first search strategy to traverse the search
space of candidate rules efficiently. Further, we perform experiments to
demonstrate the feasibility and scalability of our solution, FASTAGEDS, with
three real-world graphs.
