Semantic Conflict Detection And Crdt-Based Synchronization For Collaborative Knowledge Graphs H/F INRIA

Semantic Conflict Detection and CRDT-based Synchronization for Collaborative Knowledge Graphs
Le descriptif de l'offre ci-dessous est en Anglais
Type de contrat : Stage

Niveau de diplôme exigé : Bac +4 ou équivalent

Fonction : Stagiaire de la recherche

Contexte et atouts du poste

This Master 2 internship is part of KGTWIN (Neuro-symbolic Collaborative Editing), a research project funded by the PEPR eNSEMBLE programme (France 2030). KGTWIN investigates a new paradigm of neuro-symbolic collaborative editing in which a set of textual documents and a shared Knowledge Graph (KG) co-evolve: edits to the text may change the knowledge represented in the KG; edits to the KG may in turn affect several textual fragments.

The project brings together three teams: GDD (LS2N, Nantes Université), which coordinates the project; Wimmics (Inria, Université Côte d'Azur, CNRS, I3S); and LORELEY (Inria, Université de Lorraine, LORIA).

The internship will take place in the LORELEY team at the Inria Centre at Université de Lorraine in Nancy. It will be supervised by: Claudia-Lavinia Ignat, Research Director at Inria and head of the LORELEY team, and, Gérald Oster, Associate Professor at Université de Lorraine.

The Inria Centre at Université de Lorraine is one of Inria's nine research centres. It has about twenty project-teams in Nancy, Strasbourg and Saarbrücken and employs more than 400 people of 45 nationalities, including scientists and research and innovation support staff. The Centre belongs to a rich R&D and innovation ecosystem that includes innovative SMEs, large industrial groups, competitiveness clusters, universities, laboratories of excellence and technological research institutes.

Mission confiée

Knowledge Graphs are increasingly used to represent structured, machine-processable knowledge. In collaborative settings, several users or applications may modify the same graph concurrently. Replication improves availability and responsiveness, but concurrent updates must then be reconciled so that all replicas eventually converge.

Conflict-free Replicated Data Types (CRDTs) [1,2,3] offer a principled approach to this problem. Replicas are updated independently, without coordination, and are guaranteed to converge once they have received the same set of updates. CRDTs have been applied successfully to collaborative text editing [4] and to RDF graphs [5,6], and the W3C CRDT for RDF Community Group is working on their standardisation [7].

However, convergence alone does not guarantee that the merged graph is semantically correct. Two concurrent updates may each be valid and syntactically compatible, while their combination violates constraints expressed in an ontology or in a validation language such as SHACL [8]. For example, two users may concurrently: assign different values to a property that admits a single value (a cardinality violation); add an ex:headOf link to a team while another user deletes the team (a dangling reference); type the same entity with two disjoint classes.

Such invariants generally cannot be preserved without some form of coordination [9,10]. A semantics-aware replication model must therefore decide which conflicts to prevent, which to repair automatically, and which to report to users.

In KGTWIN, many KG updates come from text through knowledge extraction. A semantic conflict in the graph therefore often reflects an inconsistency between text fragments written by different users. Detecting such conflicts and tracing them back to their textual origin is a prerequisite for the bidirectional text-KG synchronization targeted by KGTWIN.

The objective of this internship is to study the detection of semantic conflicts in concurrently edited RDF Knowledge Graphs, and to design mechanisms that integrate this detection into a CRDT-based replication model. The work will explore the trade-offs between three properties:

- convergence of the replicated Knowledge Graphs;
- preservation of semantic constraints, expressed as SHACL shapes or as ontology axioms;
- preservation of user intentions [11], i.e. the effect each user expected their update to have.

Expected outcomes

- A classification of semantic conflicts arising from concurrent RDF updates, with a benchmark of concurrent-edit scenarios.
- A CRDT-based synchronization model with semantic conflict detection.
- An open-source prototype and its experimental evaluation.
- A research report, which may lead to a scientific publication.

The internship may be followed by a PhD in the KGTWIN project.

References

[1] M. Shapiro, N. Preguiça, C. Baquero, M. Zawirski. Conflict-Free Replicated Data Types. In Proc. 13th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2011), LNCS 6976, Springer, 2011. DOI: . HAL:

[2] N. Preguiça, C. Baquero, M. Shapiro. Conflict-free Replicated Data Types (CRDTs). In S. Sakr, A. Zomaya (eds.), Encyclopedia of Big Data Technologies, Springer, 2018. DOI: . HAL:

[3] P. S. Almeida, A. Shoker, C. Baquero. Delta State Replicated Data Types. Journal of Parallel and Distributed Computing, 111, 2018. DOI:

[4] M. Nicolas, V. Elvinger, G. Oster, C.-L. Ignat, F. Charoy. MUTE: A Peer-to-Peer Web-based Real-time Collaborative Editor. In Proc. 15th European Conference on Computer-Supported Cooperative Work (ECSCW 2017) - Panels, Posters and Demos, EUSSET, 2017. DOI: . HAL:

[5] L.-D. Ibáñez, H. Skaf-Molli, P. Molli, O. Corby. Live Linked Data: Synchronising Semantic Stores with Commutative Replicated Data Types. International Journal of Metadata, Semantics and Ontologies, 8(2), 2013. DOI: . HAL:

[6] L.-D. Ibáñez, H. Skaf-Molli, P. Molli, O. Corby. Col-Graph: Towards Writable and Scalable Linked Open Data. In The Semantic Web - ISWC 2014, LNCS 8796, Springer, 2014. DOI: . HAL:

[7] W3C CRDT for RDF Community Group.

[8] H. Knublauch, D. Kontokostas (eds.). Shapes Constraint Language (SHACL). W3C Recommendation, 20 July 2017.

[9] P. Bailis, A. Fekete, M. J. Franklin, A. Ghodsi, J. M. Hellerstein, I. Stoica. Coordination Avoidance in Database Systems. Proceedings of the VLDB Endowment, 8(3), 2014. DOI:

[10] V. Balegas, S. Duarte, C. Ferreira, R. Rodrigues, N. Preguiça, M. Najafzadeh, M. Shapiro. Putting Consistency Back into Eventual Consistency. In Proc. EuroSys 2015, ACM, 2015. DOI: . HAL:

[11] C. Sun, X. Jia, Y. Zhang, Y. Yang, D. Chen. Achieving Convergence, Causality Preservation, and Intention Preservation in Real-Time Cooperative Editing Systems. ACM Transactions on Computer-Human Interaction, 5(1), 1998. DOI:

Principales activités
- State of the art. Study CRDTs and their application to RDF; constraint validation with SHACL and OWL, including the difference between closed-world validation and open-world reasoning; and invariant preservation under weak consistency.
- Conflict modelling. Identify and classify the semantic conflicts that concurrent RDF updates can cause, for example by type of SHACL constraint violated, and build a set of reference concurrent-edit scenarios.
- Design. Propose a CRDT-based synchronization mechanism that detects these conflicts, records their provenance (which concurrent operations caused them) and makes them available for resolution, either automatic or by the users.
- Implementation. Develop a prototype of a replicated RDF Knowledge Graph with SHACL validation.
- Evaluation. Using the scenarios from task 2 and a realistic dataset, assess convergence, conflict-detection precision and recall, the semantic consistency of the merged graph, and the overhead of the mechanism.

Compétences

Knowledge of some of the following topics will be appreciated:

- distributed systems and consistency models;
- CRDTs and optimistic replication;
- RDF and SPARQL;
- Knowledge Graphs, ontologies and SHACL;
- programming in Python, Java or another suitable language.

Prior experience with Semantic Web technologies is a plus but is not required.

Avantages

- Subsidized meals
- Partial reimbursement of public transport costs
- Leave: 7 weeks of annual leave + 10 extra days off due to RTT (statutory reduction in working hours) + possibility of exceptional leave (sick children, moving home, etc.)
- Possibility of teleworking (after 6 months of employment) and flexible organization of working hours
- Professional equipment available (videoconferencing, loan of computer equipment, etc.)
- Social, cultural and sports events and activities
- Access to vocational training
- Social security coverage

Rémunération

4.50 €/hour