We describe a novel approach to exploratory semantic search applied to the problem domain of e-discovery. In this domain, as in many others, we need to support non-expert users in composing queries over a complex and heterogeneous knowledge base. We achieve this by enabling users to initiate a query through a few seed concepts and terms, and then guide them in incrementally refining the query and exploring the dataset without requiring prior knowledge of the ontology. This is achieved through a query refinement service which suggests and ranks queries which connect the initial seed concepts (and an optional result type), and then suggests query refinements based on the instance data and associated ontology. This service is enabled by an abstract query representation which reflects the user exploration model and simplifies the interface between the refinement service and the user-facing components.