Egor Kostylev

• Tena Cucala, David; Grau, Bernardo Cuenca; Motik, Boris & Kostylev, Egor (2023). On the Correspondence Between Monotonic Max-Sum GNNs and Datalog, Proceedings of the 20th International Conference on Principles of Knowledge Representation and Reasoning, KR 2023. ACM Digital Library. ISSN 9781956792027. p. 658–667. doi: 10.24963/KR.2023/64.
• Liu, Shuwen; Grau, Bernardo Cuenca; Horrocks, Ian & Kostylev, Egor (2023). Revisiting Inferential Benchmarks for Knowledge Graph Completion, Proceedings of the 20th International Conference on Principles of Knowledge Representation and Reasoning, KR 2023. ACM Digital Library. ISSN 9781956792027. doi: 10.24963/KR.2023/45.
• Zhou, Dongzhuoran; Zhou, Baifan; Zheng, Zhuoxun; Soylu, Ahmet; Savkovic, Ognjen & Kostylev, Egor [Show all 7 contributors for this article] (2022). ScheRe: Schema Reshaping for Enhancing Knowledge Graph Construction. In Al Hasan, Mohammad & Xiong, Li (Ed.), CIKM'22: Proceedings of the 31st ACM International Conference on Information & Knowledge Management. Association for Computing Machinery (ACM). ISSN 978-1-4503-9236-5. p. 5074–5078. doi: 10.1145/3511808.3557214. Show summary

  Automatic knowledge graph (KG) construction is widely used for e.g. data integration, question answering and semantic search. There are many approaches of automatic KG construction. Among which, an important approach is to map the raw data to a given domain KG schema, e.g., domain ontology or conceptual graph, and construct the entities and properties according to the domain KG schema. However, the existing approaches to construct KGs are not always efficient enough and the resulting KGs are not sufficiently user-friendly. The main challenge arises from the trade-off: the domain KG schema should be knowledge-oriented, to reflect the general domain knowledge; while a KG schema should be dataoriented, to cover all data features. If the former is directly used for KG construction, this can cause issues like a high load of blank nodes, which are technical nodes in the KGs that represent unknown entities. To this end, we propose our ScheRe system in the demo, which relies on a schema reshaping algorithm and other two semantic modules for enhancing KG construction. The demo attendees will use ScheRe to reshape a domain KG schema to data specific KG schema, build KGs with industrial data, and experience more user-friendly querying.

• Zhou, Dongzhuoran; Zhou, Baifan; Zheng, Zhuoxun; Kostylev, Egor; Cheng, Gong & Jimenez-Ruiz, Ernesto [Show all 8 contributors for this article] (2022). Enhancing Knowledge Graph Generation with Ontology Reshaping – Bosch Case. Lecture Notes in Computer Science (LNCS). ISSN 0302-9743. 13384, p. 299–302. doi: 10.1007/978-3-031-11609-4_45. Full text in Research Archive
• Kaminski, Mark; Kostylev, Egor; Grau, Bernardo Cuenca; Motik, Boris & Horrocks, Ian (2022). The Complexity and Expressive Power of Limit Datalog. Journal of the ACM. ISSN 0004-5411. 69(1). doi: 10.1145/3495009.
• Tena Cucala, David; Wałęga, Przemysław; Grau, Bernardo Cuenca & Kostylev, Egor (2021). Stratified Negation in Datalog with Metric Temporal Operators. In Leyton-Brown, Kevin & Mausam, Mausam (Ed.), Proceedings of the 35th National Conference on Artificial Intelligence‚ AAAI 2021 (volume 35 no. 7). AAAI Press. ISSN 978-1-57735-866-4. p. 6488–6495. Show summary

  We extend DatalogMTL—Datalog with operators from met- ric temporal logic—by adding stratified negation as failure. The new language provides additional expressive power for representing and reasoning about temporal data and knowledge in a wide range of applications. We consider models over the rational timeline, study their properties, and establish the computational complexity of reasoning. We show that, as in negation-free DatalogMTL, fact entailment in our language is PSPACE-complete in data and EXPSPACE-complete in combined complexity. Thus, the extension with stratified negation does not lead to higher complexity.

• Kostylev, Egor; Wałęga, Przemysław; Tena Cucala, David & Grau, Bernardo Cuenca (2021). DatalogMTL with Negation Under Stable Models Semantics. In Bienvenu, Meghyn; Gerhard, Lakemeyer & Erdem, Esra (Ed.), Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning (KR2021) . International Joint Conferences on Artificial Intelligence Organization (IJCAI). ISSN 978-1-956792-99-7. doi: 10.24963/kr.2021/58. Show summary

  We introduce negation under stable models semantics in DatalogMTL—a temporal extension of Datalog with metric operators. As a result, we obtain a rule language which combines the power of answer set programming with the temporal dimension provided by metric operators. We show that, in this setting, reasoning becomes undecidable over the rationals and decidable in EXPSPACE in data complexity over the integers. We also show that, if we restrict our attention to forward-propagating programs (where rules propagate information in a single temporal direction), reasoning over integers becomes PSPACE-complete in data complexity and hence no harder than over positive programs; however, reasoning over the ra- tionals in this fragment remains undecidable.

• Kamburjan, Eduard & Kostylev, Egor (2021). Type Checking Semantically Lifted Programs via Query Containment under Entailment Regimes. CEUR Workshop Proceedings. ISSN 1613-0073. 2954. Full text in Research Archive
• Kostylev, Egor; Barceló, Pablo; Monet, Mikaël; Pérez, Jorge; Reutter, Juan L. & Silva, Juan Pablo (2020). The Logical Expressiveness of Graph Neural Networks. In Rush, Alexander (Eds.), Proceedings of the 8th International Conference on Learning Representations, ICLR 2020. OpenReview.net. ISSN 9781713872740.

View all works in Cristin

• Zhou, Dongzhuoran; Zhou, Baifan; Zheng, Zhuoxun; Tan, Zhipeng; Kostylev, Egor & Kharlamov, Evgeny (2022). Towards Executable Knowledge Graph Translation.
• Zhou, Dongzhuoran; Zhou, Baifan; Zheng, Zhuoxun; Soylu, Ahmet; Cheng, Gong & Jimenez-Ruiz, Ernesto [Show all 8 contributors for this article] (2022). Ontology Reshaping for Knowledge Graph Construction: Applied on Bosch Welding Case.
• Kostylev, Egor; Liu, Shuwen; Horrocks, Ian & Grau, Bernardo Cuenca (2021). INDIGO: GNN-Based Inductive Knowledge Graph Completion Using Pair-Wise Encoding. Show summary

  The aim of knowledge graph (KG) completion is to extend an incomplete KG with missing triples. Popular approaches based on graph embeddings typically work by first representing the KG in a vector space, and then applying a predefined scoring function to the resulting vectors to complete the KG. These approaches work well in transductive settings, where predicted triples involve only constants seen during training; however, they are not applicable in inductive settings, where the KG on which the model was trained is extended with new constants or merged with other KGs. The use of Graph Neural Networks (GNNs) has recently been proposed as a way to overcome these limitations; however, existing approaches do not fully exploit the capabilities of GNNs and still rely on heuristics and ad-hoc scoring functions. In this paper, we propose a novel approach, where the KG is fully encoded into a GNN in a transparent way, and where the predicted triples can be read out directly from the last layer of the GNN without the need for additional components or scoring functions. Our experiments show that our model outperforms state-of-the-art approaches on inductive KG completion benchmarks.

• Zhou, Dongzhuoran; Zhou, Baifan; Chen, Jieying; Cheng, Gong; Kostylev, Egor & Kharlamov, Evgeny (2021). Towards Ontology Reshaping for KG Generation with User-in-the-Loop: Applied to Bosch Welding. Show summary

  Knowledge graphs (KG) are used in a wide range of applications. The automation of KG generation is very desired due to the data volume and variety in industries. One important approach of KG generation is to map the raw data to a given KG schema, namely a domain ontology, and construct the entities and properties according to the ontology. However, the automatic generation of such ontology is demanding and existing solutions are often not satisfactory. An important challenge is a trade-off between two principles of ontology engineering: knowledge-orientation and data-orientation. The former one prescribes that an ontology should model the general knowledge of a domain, while the latter one emphasises on reflecting the data specificities to ensure good usability. We address this challenge by our method of ontology reshaping, which automates the process of converting a given domain ontology to a smaller ontology that serves as the KG schema. The domain ontology can be designed to be knowledge-oriented and the KG schema covers the data specificities. In addition, our approach allows the option of including user preferences in the loop. We demonstrate our on-going research on ontology reshaping and present an evaluation using real industrial data, with promising results.

View all works in Cristin