Seminar: Provenance of Graph Queries and Applications

Queries on graphs are rich and ongoing research domain: for example, regular path queries (RPQ) ongraphs are a building block of graph query languages and are part of the on-going new graph querylanguage standard, GQL.

In parallel, the notion of database provenance is used to explain the internal structure of a queryresult, 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 fewimportant questions that need to be answered in tandem: 1) which algorithms can be used?, and 2) which semirings can be effi ciently 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 queryevaluation algorithms. Finally, we touch on extensions to Datalog queries on graphs, the infl uence ofthe graph structure on the efficiency of the algorithms, and how graph provenance can be used forexplainability.

Silviu Maniu is a Professor of Computer Science at Université Grenoble Alpes (France), where heheads the Data Analytics Intelligent and Scalable (DAISY) team. Previously, he held positions asassociate professor at Université Paris-Saclay, visiting researcher at Inria and École NormaleSupérieure, and researcher at Huawei Hong Kong. He earned his Ph.D. in computer science fromTélécom Paris, Institut Polytechnique de Paris (France) in 2012, and a engineering diploma fromPolitehnica University in Timisoara, Romania in 2005. His research interests are in data mining ingeneral, in particular in graph data (recommender systems, provenance algorithms) and sequentiallearning for social network applications, having multiple publications in top-tier conferences andjournals (KDD, SDM, IJCAI, TKDD, TODS, ICDT, etc.).