Semantic Conflict Detection and CRDT-based Synchronization for Collaborative Knowledge Graphs

Semantic Conflict Detection and CRDT-based Synchronization for Collaborative Knowledge Graphs Download job offer in PDF format Contract type : Internship Level of qualifications required : Master's or equivalent Fonction : Internship Research Context 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. Assignment 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: 10.1007/978-3-642-24550-3_29. HAL: hal-00932836 [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: 10.1007/978-3-319-63962-8_185-1. HAL: hal-01793586 [3] P. S. Almeida, A. Shoker, C. Baquero. Delta State Replicated Data Types. Journal of Parallel and Distributed Computing, 111, 2018. DOI: 10.1016/j.jpdc.2017.08.003 [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: 10.18420/ecscw2017_p5. HAL: hal-01655438 [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: 10.1504/IJMSO.2013.056605. HAL: hal-00903377 [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: 10.1007/978-3-319-11964-9_21. HAL: hal-01061493 [7] W3C CRDT for RDF Community Group. https://www.w3.org/groups/cg/crdt4rdf/ [8] H. Knublauch, D. Kontokostas (eds.). Shapes Constraint Language (SHACL). W3C Recommendation, 20 July 2017. https://www.w3.org/TR/2017/REC-shacl-20170720/ [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.14778/2735508.2735509 [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: 10.1145/2741948.2741972. HAL: hal-01248191 [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: 10.1145/274444.274447 Main activities • 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. Skills 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. Benefits package • 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 Remuneration 4.50 €/hour Apply for this position Share • Facebook • Linkedin • Twitter • Email General Information • Theme/Domain : Distributed Systems and middleware Information system (BAP E) • Town/city : Villers lès Nancy • Inria Center : Centre Inria de l'Université de Lorraine • Starting date : 2027-02-01 • Duration of contract : 6 months • Deadline to apply : 2026-11-20 Warning : you must enter your e-mail address in order to save your application to Inria. Applications must be submitted online on the Inria website. Processing of applications sent from other channels is not guaranteed. Instruction to apply Defence Security : This position is likely to be situated in a restricted area (ZRR), as defined in Decree No. 2011-1425 relating to the protection of national scientific and technical potential (PPST).Authorisation to enter an area is granted by the director of the unit, following a favourable Ministerial decision, as defined in the decree of 3 July 2012 relating to the PPST. An unfavourable Ministerial decision in respect of a position situated in a ZRR would result in the cancellation of the appointment. Recruitment Policy : As part of its diversity policy, all Inria positions are accessible to people with disabilities. Contacts • Inria Team : LORELEY • Recruiter : Ignat Claudia-lavinia / claudia.ignat@inria.fr The keys to success The internship is intended for a Master 2 or final-year engineering student in Computer Science with an interest in distributed systems, databases or Semantic Web technologies. About Inria Inria, the French national institute for research in digital science and technology, supports the French government in national research and innovation strategies in the digital field, acting as Digital Programs Agency. Inria leads over 300 research and innovation projects with its 3,500 scientists, engineers, and support staff, in partnership with universities and the digital ecosystem (businesses, entrepreneurs, and public stakeholders). Together, we explore strategic fields such as artificial intelligence, cybersecurity, quantum computing, cloud technologies, digital transformation in healthcare, digital twins, and digital technologies for defence. We develop practical solutions such as software, tech startups, partnerships with national companies, and cutting-edge training programmes. Our goal is to drive scientific, technological, and industrial excellence to ensure France’s digital sovereignty.