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

Denis Gallo, Matteo Lissandrini, Yannis Velegrakis

Download a digital copy (PDF) or see the Poster (PDF)

and

watch the presentation (YouTube)

The final authenticated version is available online at 10.5441/002/edbt.2020.54.

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 (447-450). 

@inproceedings{gallo2020personalized,
  title={Personalized page rank on knowledge graphs: Particle Filtering is all you need!},
  author={Gallo, Denis and Lissandrini, Matteo and Velegrakis, Yannis},
  booktitle = {Proceedings of the 23rd International Conference on Extending Database Technology, {EDBT} 2020},
  volume={2020},
  pages={447--450},
  doi = {10.5441/002/edbt.2020.54},
  year={2020},
  organization={OpenProceedings.org}
}