Personalized Page Rank on Knowledge Graphs: Particle Filtering is all you need!

Denis Gallo, Matteo Lissandrini, Yannis Velegrakis

Abstract:

Graphs are everywhere. Personalized Page Rank (PPR) is a particularly important task to support search and exploration within such datasets. PPR computes the proximity between query nodes and other nodes in the graph. This is used, among others, for entity exploration, query expansion, and product recommendation. Graph databases are used for storing knowledge graphs. Unfortunately, the exact computation of PPR is computationally expensive. While different solutions have been proposed to compute PPR values with high precision, these are extremely complex to implement, and in some cases require heavy pre-processing. In this work we sustain that a better approach exists: particle filtering. Particle filtering methods produce ranks with sufficient precision while exploiting what graph databases architectures are already optimized for: navigating local connections. We present the implementation of such approach in a popular commercial database, and show how this outperforms the already implemented functionality. With this, we aim to motivate future research to optimize and improve upon this research direction.

Cite:

and
Personalized Page Rank on Knowledge Graphs: Particle Filtering is all you need!.”
Proceedings of the 23th International Conference on Extending Database Technology, EDBT 2020 (169-180).