Top-K Diversification for Path Queries in Knowledge Graphs

Christian Aebeloe, Vinay Setty, Gabriela Montoya, Katja HoseInternational Semantic Web Conference (P&D/Industry/BlueSky) 2018 · OpenReview

Introduction

Standard query languages for Knowledge Graphs (KGs), such as SPARQL 1.1, often treat reachability as a binary property: two entities are either connected or they are not. While property paths can identify connections, they frequently fail to provide the intermediate nodes that explain the relationship. When engines do return these paths, users are often overwhelmed by a high volume of redundant results—paths that differ by only a single minor node.

This paper addresses the challenge of selecting a "Top-K" list of paths that are both relevant (short) and diverse (distinct). The authors propose moving beyond simple set-based similarity measures like Jaccard similarity, which ignores the sequence of entities and relations, to a sequence-aware approach using Levenshtein distance.

Methodology

The researchers propose a generalized top-k ranking framework governed by an objective function, $DivP(R)$, which balances relevance and diversity:

  1. Relevance ($Rel$): Defined by path length, where shorter paths are prioritized. Scores are normalized against the shortest path in the result set.
  2. Diversification Parameter ($\lambda$): A user-defined parameter ranging from 0 to 1. A value of 0 prioritizes relevance (shortest paths), while a value of 1 prioritizes maximum diversity.
  3. Similarity Measures ($Sim$):
    • Jaccard Similarity: A baseline that treats paths as unordered sets of resources.
  4. Levenshtein Similarity: A novel application for KG paths that treats them as sequences. It calculates the minimum number of edits (insertions, deletions, substitutions) required to transform one path into another, thereby preserving the semantic order of the graph.

Due to the NP-hard nature of finding the optimal set of diverse paths, a greedy heuristic is employed to solve the optimization problem.

Experimental Setup

The framework was evaluated using the YAGO Knowledge Graph, which contains over 1 billion triples. The researchers conducted experiments on 10 randomly selected queries, comparing the performance of Jaccard and Levenshtein metrics as the diversification parameter $\lambda$ was varied.

Key Results

The evaluation focused on "Novelty"—the fraction of unseen elements in the results—and average path length.

Table 1: Performance metrics ($Nov_R$, $Nov_T$, and Path length) comparing Jaccard and Levenshtein similarity measures as the diversification parameter $\lambda$ increases.

As shown in the results, both methods behave identically when $\lambda = 0$, defaulting to the shortest paths (average length of 2.00). However, as $\lambda$ increases, significant differences emerge:

  • Path Length Efficiency: At maximum diversity ($\lambda = 1.0$), the Levenshtein-based approach maintains a relatively short average path length of 3.92. In contrast, the Jaccard-based approach results in significantly longer paths, averaging 5.95.
  • Triple Novelty ($Nov_T$): Levenshtein similarity generally outperforms Jaccard in capturing unique triples (subject-predicate-object units) at higher values of $\lambda$.
  • Resource Novelty ($Nov_R$): Interestingly, Jaccard achieves higher novelty when considering individual resources. This suggests that for very short paths, the sequence awareness of Levenshtein is less impactful due to fewer possible permutations.

Discussion and Insights

The primary insight is that order matters in Knowledge Graphs. Paths are sequences, and the direction and sequence of relationships carry the underlying logic of the connection. By utilizing Levenshtein distance, the framework captures "path semantics" more effectively than traditional set-based methods.

Furthermore, Levenshtein similarity proves more efficient in the length-diversity trade-off. Because it recognizes that reordering nodes creates a distinct path, it can identify high-novelty results without resorting to the excessively long, convoluted paths that Jaccard similarity often selects when it exhausts unique resource sets.

Limitations and Future Work

While the results are promising, the study was limited to 10 queries. Future work will involve larger-scale benchmarks to confirm these trends across diverse KG structures. Additionally, the authors plan to investigate specific scenarios where Jaccard might still be preferable and refine similarity measures to better handle complex KG schemas.

Summary updated

BibTeX
@inproceedings{aebeloe2018top,
  author = {Christian Aebeloe and Vinay Setty and Gabriela Montoya and Katja Hose},
  title = {{Top-K Diversification for Path Queries in Knowledge Graphs}},
  booktitle = {International Semantic Web Conference (P\&D/Industry/BlueSky)},
  year = {2018},
  url = {https://openreview.net/forum?id=CCfSMHNw6Ls},
}
Figure