  Graph entity dependencies (GEDs) are novel graph constraints, unifying keys
and functional dependencies, for property graphs. They have been found useful
in many real-world data quality and data management tasks, including fact
checking on social media networks and entity resolution. In this paper, we
study the discovery problem of GEDs -- finding a minimal cover of valid GEDs in
a given graph data. We formalise the problem, and propose an effective and
efficient approach to overcome major bottlenecks in GED discovery. In
particular, we leverage existing graph partitioning algorithms to enable fast
GED-scope discovery, and employ effective pruning strategies over the
prohibitively large space of candidate dependencies. Furthermore, we define an
interestingness measure for GEDs based on the minimum description length
principle, to score and rank the mined cover set of GEDs. Finally, we
demonstrate the scalability and effectiveness of our GED discovery approach
through extensive experiments on real-world benchmark graph data sets; and
present the usefulness of the discovered rules in different downstream data
quality management applications.
