TL;DR

We consider the task of exploratory search through graph queries on knowledge graphs. We propose to assist the user by expanding the query with intuitive suggestions that can retrieve more detailed and relevant answers.

In this paper:

• We formally define the problem of Suggesting Graph-Query Expansions (Section 3) and provide a model based on intuitions from language-modelling and relevance feedback.
• We propose two unsupervised methods to estimate the relevance of expansions based on edge frequency and compare them with two strong baselines: surprise and Markov models.
• We show that our framework outperforms other methods even when the query contains just one edge, obtaining an NDCG score between 0.5 and 0.6 on the top-10 suggestions.
• We show with a user-study that our framework provides useful suggestions quickly by exploiting only edge frequency. Yet, the framework can integrate more complex structures if needed.