Egor Kostylev

• Cucala, David Tena; Grau, Bernardo Cuenca; Motik, Boris & Kostylev, Egor V. (2026). From monotonic graph neural networks to datalog and back: Expressive power and practical applications. Artificial Intelligence. ISSN 0004-3702. 357. doi: 10.1016/j.artint.2026.104545. Full text in Research Archive Show summary

  Many tasks over knowledge graphs, such as link prediction, can be conceptualised as a problem of learning a transformation of sets of relational facts. Machine learning models such as graph neural networks (GNNs) can be used to realise this transformation, allowing the transformation to be learned from examples. However, it is often difficult to verify formally the properties of such a transformation, or understand why it derives a specific fact. Alternatively, such a transformation can be realised using a set of rules expressed in a knowledge representation language such as Datalog. Formal properties of such a transformation can be verified using symbolic means, and each derived fact can be justified by a rule; however, writing and curating the rules is costly and requires expertise in both the application domain and the formal language. To bridge the gap between these two approaches, in this paper we study the relationship between transformations realised by monotonic max-sum GNNs, a subclass of GNNs with nonnegative weights and max and sum aggregation functions, and transformations realised by Datalog rules. First, we provide an algorithm that can verify whether a given Datalog rule is sound for a network, in the sense that the GNN always derives all consequences of the rule on any input dataset. Second, we provide an algorithm that allows us to justify any fact derived by a GNN by computing a rule that is sound for the GNN and that derives the fact. Third, we study the expressive power of monotonic max-sum GNNs and show that, for each such GNN, one can compute a Datalog program where applying the GNN to any dataset produces the same facts as a single round of application of the program’s rules to the dataset; we also sharpen our result to the subclass of monotonic maxGNNs, which use only the max aggregation function, and identify a corresponding class of Datalog programs. Finally, we carry out a practical evaluation and show that monotonic max-sum GNNs can be successfully trained in practice on common knowledge graph tasks, and that extracting rules from max-sum GNNs is practically feasible.

• Kamburjan, Eduard; Klungre, Vidar Norstein; Qu, Yuanwei; Schlatte, Rudolf; Kostylev, Egor V. & Giese, Martin [Show all 7 contributors for this article] (2026). Semantically Reflected Programs. Transactions on Graph Data and Knowledge (TGDK). 4(1), p. 3:1–3:52. doi: 10.4230/TGDK.4.1.3. Full text in Research Archive Show summary

  This paper addresses the dichotomy between the formalization of structural and the formalization of executable behavioral knowledge by means of semantically lifted programs, which explore an intuitive connection between imperative programs and knowledge graphs. While knowledge graphs and ontologies are eminently useful to represent formal knowledge about a system’s individuals and universals, programming languages are designed to describe the system’s evolution. To address this dichotomy, we introduce a semantic lifting of the program states of an executing progam into a knowledge graph, for an object-oriented programming language. The resulting graph is exposed as a semantic reflection layer within the programming language, allowing programmers to leverage knowledge of the application domain in their programs during execution. In this paper, we formalize semantic lifting and semantic reflection for a small imperative programming language, SMOL, explain the operational aspects of the language, and consider type correctness and virtualization for runtime program queries through the semantic reflection layer. We illustrate semantic lifting and semantic reflection through a case study of geological modeling and discuss different applications of the technique. The language implementation is open source and available online.

• Cucala, David J. Tena; Grau, Bernardo Cuenca; Motik, Boris & Kostylev, Egor V. (2025). Expressive Power of Monotonic Graph Neural Networks via Datalog. In Hitzler, Pascal (Eds.), Handbook on Neurosymbolic AI and Knowledge Graphs. IOS Press. ISSN 9781643685786. p. 780–807. doi: 10.3233/faia250232. Full text in Research Archive Show summary

  Graph Neural Networks (GNNs) are often used to learn transformations of graph data. While effective in practice, GNN-based approaches make predictions via numeric manipulations, and so their expressive power (i.e., a logical description of what they can do) is difficult to understand. In this chapter, we describe our recent research into monotonic max GNNs, a sub-family of GNNs that correspond to a class of programs expressed in Datalog, a well-known rule-based formalism. These GNNs are subject to restrictions ensuring that no prediction made by them is lost when extending or renaming their input. As a result, each monotonic max GNN is equivalent to a round of application of a finite and computable set of tree-shaped Datalog rules. Furthermore, these GNNs can be effectively trained in practice for tasks such as knowledge graph completion, achieving performance similar or superior to other state-of-the-art rule-learning systems.

• Kostylev, Egor V. (2025). Foundations of Graph Neural Networks (A Logician’s View) (Invited Paper). OpenAccess Series in Informatics. 138, p. 3:1–3:19. doi: 10.4230/OASICS.RW.2024/2025.3. Full text in Research Archive Show summary

  Graph Neural Networks (GNNs) are a family of neural architectures that are naturally suited to learning functions on graphs. They are now used in a wide range of applications. It has been observed that GNNs share many similarities with classical computer science (CS) formalisms, such as the Weisfeiler-Leman graph isomorphism test, bisimulation, and logic. Most notably, both GNNs and these formalisms deal with functions on graphs and graph-like structures. This observation opens up an opportunity to compare GNN architectures with these formalisms in terms of different kinds of expressibility, thus positioning these architectures within the well-established landscape of theoretical CS. This, in turn, helps us better understand the fundamental capabilities and limitations of various GNN architectures, enabling more informed choices about which architecture to use - if any at all. In these lecture notes, I give an introduction to the state-of-the-art foundations of GNNs - specifically, our current understanding of their expressibility in terms of the classical formalisms, considering several notions of expressive power.

• Zhou, Dongzhuoran; Kharlamov, Evgeny & Kostylev, Egor V. (2025). GLoRa: A Benchmark to Evaluate the Ability to Learn Long-Range Dependencies in Graphs. International Conference on Learning Representations. doi: https:/proceedings.iclr.cc/paper_files/paper/2025/file/e779d5a98058b5c9f3df9059a3137647-Paper-Conference.pdf. Full text in Research Archive Show summary

  Learning on graphs is one of the most active research topics in machine learning (ML). Among the key challenges in this field, effectively learning long-range dependencies in graphs has been particularly difficult. It has been observed that, in practice, the performance of many ML approaches, including various types of graph neural networks (GNNs), degrades significantly when the learning task involves long-range dependencies—that is, when the answer is determined by the presence of a certain path of significant length in the graph. This issue has been attributed to several phenomena, including over-smoothing, over-squashing, and vanishing gradient. A number of solutions have been proposed to mitigate these causes. However, evaluation of these solutions is currently challenging because existing benchmarks do not effectively test systems for their ability to learn tasks based on long-range dependencies in a transparent manner. In this paper, we introduce GLoRa, a synthetic benchmark that allows testing of systems for this ability in a systematic way. We then evaluate state-of-the-art systems using GLoRa and conclude that none of them can confidently claim to learn long-range dependencies well. We also observe that this weak performance cannot be attributed to any of the three causes, highlighting the need for further investigation.

• Wold, Sondre; Simon, Étienne; Charpentier, Lucas Georges Gabriel; Kostylev, Egor V.; Velldal, Erik & Øvrelid, Lilja (2024). Compositional Generalization with Grounded Language Models, Findings of the Association for Computational Linguistics ACL 2024. Association for Computational Linguistics (ACL). ISSN 9798891760998. p. 3447–3460. doi: 10.18653/v1/2024.findings-acl.205. Full text in Research Archive Show summary

  Grounded language models use external sources of information, such as knowledge graphs, to meet some of the general challenges associated with pre-training. By extending previous work on compositional generalization in semantic parsing, we allow for a controlled evaluation of the degree to which these models learn and generalize from patterns in knowledge graphs. We develop a procedure for generating natural language questions paired with knowledge graphs that targets different aspects of compositionality and further avoids grounding the language models in information already encoded implicitly in their weights. We evaluate existing methods for combining language models with knowledge graphs and find them to struggle with generalization to sequences of unseen lengths and to novel combinations of seen base components. While our experimental results provide some insight into the expressive power of these models, we hope our work and released datasets motivate future research on how to better combine language models with structured knowledge representations.

• Benedikt, Michael; Kostylev, Egor V. & Tan, Tony (2024). Two variable logic with ultimately periodic counting. SIAM journal on computing (Print). ISSN 0097-5397. 53(4), p. 884–968. doi: 10.1137/22M1504792. Full text in Research Archive
• Walega, Przemyslaw Andrzej; Cucala, David Jaime Tena; Grau, Bernardo Cuenca & Kostylev, Egor V. (2024). The Stable Model Semantics of Datalog with Metric Temporal Operators. Theory and Practice of Logic Programming. ISSN 1471-0684. 24(1), p. 22–56. doi: 10.1017/S1471068423000315. Full text in Research Archive Show summary

  We introduce negation under the stable model semantics in DatalogMTL—a temporal extension of Datalog with metric temporal 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 rational timeline, and decidable in EXPSPACE in data complexity over the integer timeline. We also show that, if we restrict our attention to forward-propagating programs, reasoning over the integer timeline becomes PSPACE-complete in data complexity, and hence, no harder than over positive programs; however, reasoning over the rational timeline in this fragment remains undecidable.

• Pflueger, Maximilian; Cucala, David Jaime Tena & Kostylev, Egor V. (2024). Recurrent graph neural networks and their connections to bisimulation and logic. In Wooldridge, Michael; Dy, Jennifer & Natarajan, Sriraam (Ed.), Proceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI 2024). AAAI Press. ISSN 9781577358879. p. 14608–14616. doi: 10.1609/AAAI.V38I13.29377. Full text in Research Archive
• Pflueger, Maximilian; Marti, Johannes & Kostylev, Egor V. (2024). A characterisation theorem for two-way bisimulation-invariant monadic least fixpoint logic over finite structures. In Sobocinski, Pawel; Lago, Ugo Dal & Esparza, Javier (Ed.), Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2024). Association for Computing Machinery (ACM). ISSN 9798400706608. p. 63:1–63:14. doi: 10.1145/3661814.3662107. Full text in Research Archive Show summary

  A seminal theorem by van Benthem characterises the bisimulation-invariant fragment of First Order Logic (FOL) in terms of Modal Logic. Similarly, Janin and Walukiewicz have shown that the bisimulation-invariant fragment of Monadic Second Order Logic (MSO) corresponds precisely to the (modal) mu-calculus. Notably, neither argument immediately carries over when only considering finite structures. In the case of FOL, Rosen provided an alternative proof, which also works over finite structures. However, such characterisations for any logic more expressive than FOL over finite structures have remained long-standing open problems. In this paper, we prove such a characterisation for parameter-free Monadic Least Fixpoint Logic, a well-known logic in between FOL and MSO. In particular, we show that, over finite structures, every two-way bisimulation-invariant formula in this logic is equivalent to a formula in the two-way mu-calculus and vice versa.

• Cucala, David Tena; 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. Full text in Research Archive
• 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. p. 461–471. doi: 10.24963/KR.2023/45. Full text in Research Archive
• 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 Hasan, Mohammad Al & Xiong, Li (Ed.), CIKM'22: Proceedings of the 31st ACM International Conference on Information & Knowledge Management. Association for Computing Machinery (ACM). ISSN 9781450392365. p. 5074–5078. doi: 10.1145/3511808.3557214. Full text in Research Archive 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.

• 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. Full text in Research Archive
• 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(13384), p. 299–302. doi: 10.1007/978-3-031-11609-4_45. Full text in Research Archive Show summary

  In the context of Industry 4.0 and Internet of Things (IoT), modern manufacturing and production lines are equipped with software systems and sensors that constantly collect and send a high volume of data.

• Kamburjan, Eduard & Kostylev, Egor (2021). Type Checking Semantically Lifted Programs via Query Containment under Entailment Regimes. CEUR Workshop Proceedings. 2954. Full text in Research Archive Show summary

  Semantically lifted programs integrate declarative ontologybased knowledge modelling into imperative programming. In this approach, each state of a program is mapped into an OWL knowledge base (KB) and enriched with user-dfined knowledge; the resulting KB can be accessed from the program using standard SemanticWeb queries. The result of a query, however, should conform the type system of the program. We present a technique for checking type conformance statically, which is based on query containment over OWL KBs. We then discuss an approximation method for type checking, which exploits concept subsumption rather than containment and hence allows for an effcient implementation using existing tools. Finally, we describe our implementation of semantically lifted programs with static type checking in language SMOL.

• Kostylev, Egor; Wałęga, Przemysław; Cucala, David Tena & 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 9781956792997. doi: 10.24963/kr.2021/58. Full text in Research Archive 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.

• Cucala, David Tena; 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 9781577358664. p. 6488–6495. Full text in Research Archive 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; 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. Full text in Research Archive

View all works in NVA

• Kostylev, Egor V. (2025). Uniform expressivity of Graph Neural Networks. doi: https:/iris-ai.org. Full text in Research Archive
• Kostylev, Egor V. (2025). Foundations of Graph Neural Networks. doi: https:/phdopen.mimuw.edu.pl/index.php?page=l25w2. Full text in Research Archive
• Kostylev, Egor V. (2024). Foundations of Graph Neural Networks (Tutorial Lecture). Full text in Research Archive
• Zhou, Dongzhuoran; Zhou, Baifan; Zheng, Zhuoxun; Tan, Zhipeng; Kostylev, Egor & Kharlamov, Evgeny (2022). Towards Executable Knowledge Graph Translation. Full text in Research Archive
• 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. Full text in Research Archive
• Kostylev, Egor; Liu, Shuwen; Horrocks, Ian & Grau, Bernardo Cuenca (2021). INDIGO: GNN-Based Inductive Knowledge Graph Completion Using Pair-Wise Encoding. Full text in Research Archive 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. Full text in Research Archive 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.

• Søberg, Anders; Giese, Martin & Kostylev, Egor V. (2025). Description Logics with Epsilon Individuals (long version). Universitetet i Oslo. ISSN 9788273686077. Full text in Research Archive Show summary

  We investigate the extension of description logics (DLs) with definite descriptions—that is, references to individuals based on descriptions of their properties. Specifically, we introduce the syntax and semantics for ε-individuals, modelled on the ε-terms that Hilbert introduced for first-order logic. We present sound and complete reasoning algorithms for the logics that result from adding ε-individuals to several well-known DLs. In particular, for the extension of the basic DL ALC with ε-individuals, we provide a tableau calculus and show that the language without TBoxes is as expressive as the language with TBoxes; both also share EXPTIME-completeness of reasoning. In the case of the extension ALCO of the language with nominals, we give a reduction to the language ALCOu with the universal role and show that reasoning remains EXPTIME-complete. Finally, for the lightweight DL ΕLO, we show that the usual saturation calculus can be extended for ε-individuals, while maintaining the PTIME complexity.

• Snilsberg, Erik; Karlsen, Leif Harald; Kostylev, Egor V. & Skjæveland, Martin G (2024). Foundations of ontology template language OTTR (extended abstract), in proceedings of the 37th International Workshop on Description Logics (DL 2024). CEUR-WS.org. Full text in Research Archive
• Pop, Roxana & Kostylev, Egor V. (2023). Inductive future time prediction on temporal knowledge graphs with interval time (In Proceedings of the 17th International Workshop on Neural-Symbolic Learning and Reasoning, NeSy 2023). CEUR-WS.org. Full text in Research Archive

View all works in NVA