Towards finding relational redescriptions

This paper introduces relational redescription mining, that is, the task of finding two structurally different patterns that describe nearly the same set of object tuples in a relational dataset. By extending redescription mining beyond propositional and real-valued attributes, it provides a powerful tool to match different relational descriptions of the same concept. As a first step towards solving this general task, we introduce an efficient algorithm that mines one description of a given binary concept. A set of graph patterns is built from frequent path patterns connecting example pairs. Experiments in the domain of explaining kinship terms show that this approach can produce complex descriptions that match explanations by domain experts, while being much faster than a direct relational query mining approach.acceptance rate 47.8%status: publishe