Knowledge Graphs capture the semantic relations between realworld entities and can thus, allow end-users to explore different aspects of an entity of interest by traversing through the edges in the graph. Most of the state-of-the-art methods in entity recommendation are limited in the sense that they allow users to search only in the immediate neighborhood of the entity of interest. This is majorly due to efficiency reasons as the search space increases exponentially as we move further away from the entity of interest in the graph. Often, users perform the search task in the context of an information need and we investigate the role this context can play in overcoming the scalability issue and improving knowledge graph exploration. Intuitively, only a small subset of entities in the graph are relevant to a users' interest. We show how can we efficiently select this sub-set by utilizing contextual clues and using graph-theoretic measures to further re-rank this set to offer highly relevant graph exploration capabilities to end-users.