Knowledge graphs (KGs) allow organizations to store huge amounts of data from multiple heterogeneous sources in one place. To accommodate the heterogeneity and the rapid growth of the data into unanticipated domains, these KGs intentionally lack a schema. A major problem in the era of “Big Data” is effectively exploring these KGs. Users typically start exploring a KG by combining a few query conditions and iteratively refining them. During this tedious process, a user will execute multiple queries. Some of these queries will fail to return any answers, while others will return only some answers. Oftentimes, users will find that their information need is satisfied by combining the answers of several of these queries where one or more condition is replaced by a very similar one. To facilitate effective exploration of KGs, we may resort to query relaxation where the query engine judiciously replaces a query condition by similar ones using weighted relaxation rules mined from the KG. This poses the problem that the space of possible relaxations is potentially too large to fully explore. We may use a top-k approach to query processing but the downside of top-k query processing is the extra overhead introduced by the bookkeeping it requires. This talk aims at introducing a probabilistic query planning framework that speculatively determines when top-k joins can be safely replaced by inner joins, thereby, reducing the overheads and leading to faster response times.