Discovery of Keys for Graphs

Keys for graphs specify the topology and value constraints to uniquely identify entities in a graph in applications such as object identification, knowledge fusion, deduplication, and social network reconciliation. Despite their prevalence, existing key mining algorithms do not consider graph keys with recursive key definitions, which capture dependence between entities. We introduce GKMiner$$\mathsf {GKMiner}$$, an algorithm that mines recursive keys over graphs. We show the efficiency and utility of our discovered keys using large-scale, real data graphs.