In a knowledge graph, a referring expression is logical formula that can uniquely identify an entity. Referring expressions have applications in the fields of disambiguation, data anonymization, query response or data binding. There can potentially be many logical expressions to uniquely identify an entity. In this work, we discover referring expressions by focusing on those that cannot be found by instantiating the keys. The results of the first experiments showed that we can scale up to datasets of several millions of RDF triples and that the discovered ER can be used to discover identity links with a high recall and precision.