Provenance of Graph Queries and Applications
Abstract:
Queries on graphs are rich and ongoing research domain: for example, regular path queries (RPQ) on graphs are a building block of graph query languages and are part of the ongoing new graph query language standard, GQL.
In parallel, the notion of database provenance is used to explain the internal structure of a query result, by using annotations on elements that are members of a semiring. Our research aims to extend the notion of database provenance to queries on graphs. Importantly, this results in a few important questions that need to be answered in tandem: 1) which algorithms can be used?, and 2) which semirings can be efficiently used and for which types of queries.
We present in this talk our results, both theoretical and practical, on algorithms for provenance of graph queries. We establish complexity results and a taxonomy of semiring classes and their query evaluation algorithms. Finally, we touch on extensions to Datalog queries on graphs, the influence of the graph structure on the efficiency of the algorithms, and how graph provenance can be used for explainability.
This work is a collaboration with Y. Ramusat, P. Senellart, A. Groudiev (Inria & École normale supérieure) and Arkaprava Saha (Université Grenoble Alpes).
Bio:
Silviu Maniu is a Professor of Computer Science at Université Grenoble Alpes (France), where he heads the Data Analytics Intelligent and Scalable (DAISY) team. Previously, he held positions as associate professor at Université Paris-Saclay, visiting researcher at Inria and École Normale Supérieure, and researcher at Huawei Hong Kong. He earned his Ph.D. in computer science from Télécom Paris, Institut Polytechnique de Paris (France) in 2012, and an engineering diploma from Politehnica University in Timisoara, Romania in 2005. His research interests are in data mining in general, in particular in graph data (recommender systems, provenance algorithms) and sequential learning for social network applications, having multiple publications in top-tier conferences and journals (KDD, SDM, IJCAI, TKDD, TODS, ICDT, etc.).