A referring expression (RE) is a description in natural language or a logical formula that can uniquely identify an entity. For instance, the 44th president of the United States unambiguously characterizes Barack Obama. Referring expressions find applications in disambiguation, data anonymization, query answering, or data linking. There may potentially exist many logical expressions for uniquely identifying an entity. Generation of referring expressions is a well-studied task in natural language generation [1]. Hence, various algorithms with different objectives have been proposed to automatically discover REs. These approaches vary depending on the expressivity of the logical formulas they can generate. For instance in [1, 2], REs that are created are conjunctions of atoms. While in [3], more complex REs represented in description logics are discovered that can involve the universal quantifier. In this work our focus lies on automatically discovering REs for each entity within a class of a knowledge graph. Keys of a class are sets of properties whose values can uniquely identify one entity of that class. Hence, if the properties for the keys are instantiated, they can each be considered as a referring expression. What interests us in this work, is to efficiently discover REs by focusing on the ones that cannot be found by instantiating the keys. It should be noted that the quality of REs we discover is very dependent on the dataset. The completeness, correctness and lack of noise in the knowledge graph plays a pivotal role in how good and interpretable REs are.
In this work, we discover minimal REs existing in a class. By minimality, we mean that there is no other RE that we discover and that can be logically entailed by the minimal one. The REs we mine always consist of conjunctions that specify the classes the entities belong to.
To generate REs for a given class C, we start by creating the maximal non-keys
of C (the set of properties such that addition of a property will make it a key for that
class) using SAKey [
Copyright c 2019 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
Khajeh Nassiri et al. description E will still uniquely identify the instance i, just making it more complex. Hence, we remove the REs (e.g. p(i; v)) found at the end of this step and reduce the search space. Then, the remaining candidate expressions are taken into account with one more property at each step, until either the search space is empty or there is no more set of non-keys to consider. To increase the depth of subgraph, we have to consider the class of the new individual and obtain its corresponding set of maximal non-keys so that the process can be reiterated. Some pruning techniques can be applied to limit the size and the complexity of the REs discovered by our approach. For instance the depth of the graph pattern and number of allowed variables can be limited. 3
We chose YAGO as the knowledge graph on which we discover the REs and used 10
different classes such as Actor, City and Book (same data used in VICKEY [
This approach can discover RE such as: made in heaven is the album created by Queen in the year 1991. Among the actors, only George Clooney has been born in LexingtonKentucky in the year 1961. When we ran the algorithm with depth 2, we obtained REs like Alfred Werner is a scientist who has won the Nobel Prize in Chemistry and has graduated from a university located in Zurich. 4
In this paper, we proposed an approach that can efficiently discover REs by reducing the search space thanks to maximal non-keys. Due to the incompleteness of knowledge graphs, entity linking using keys may be insufficient to link all individuals. We expect that using REs will increase the recall of rule-based data linking methods.