  Fact-centric information needs are rarely one-shot; users typically ask
follow-up questions to explore a topic. In such a conversational setting, the
user's inputs are often incomplete, with entities or predicates left out, and
ungrammatical phrases. This poses a huge challenge to question answering (QA)
systems that typically rely on cues in full-fledged interrogative sentences. As
a solution, we develop CONVEX: an unsupervised method that can answer
incomplete questions over a knowledge graph (KG) by maintaining conversation
context using entities and predicates seen so far and automatically inferring
missing or ambiguous pieces for follow-up questions. The core of our method is
a graph exploration algorithm that judiciously expands a frontier to find
candidate answers for the current question. To evaluate CONVEX, we release
ConvQuestions, a crowdsourced benchmark with 11,200 distinct conversations from
five different domains. We show that CONVEX: (i) adds conversational support to
any stand-alone QA system, and (ii) outperforms state-of-the-art baselines and
question completion strategies.
