1. A method implemented in a device, the method comprising: receiving a named entity input; identifying a target sense for which the named entity input is to be extracted from a set of documents; and generating, based at least in part on both the named entity input and the set of documents, an extraction complexity feature that indicates how difficult it is deemed to be to identify the named entity input for the target sense in the set of documents, the generating including building an undirected graph based on the named entity input and the set of documents and looking for contexts in the undirected graph that are related to the target sense, the undirected graph including multiple vertices and multiple edges.