Context
Currently, there are two main AI paradigms. On the one hand, there is the classical symbolic AI, which takes a top-down approach: problems are formulated in a high-level human-readable way, and solved by methods such as logical reasoning and combinatorial optimisation, taking into account expert knowledge in structured machine-readable format. On the other hand, there is statistical, or sub-symbolic, AI, which has recently become extremely popular in practice. This one is bottom-up and data-driven: problems are formulated in terms of examples, and an AI tool numerically generalises the examples—that is, learns a model—and makes decisions using this model.
It is now widely understood that each of these two paradigms has its own fundamental limitations; for example, logic-based methods often fall short in applications dealing with large volumes of unstructured and noisy data, while learning-based methods have difficulties with interpretability of learned models, as well as with dealing with structured input and expert knowledge. Thus, one of the main current AI research directions is to efficiently combine and integrate these paradigms so that the resulting hybrid neuro-symbolic systems may exploit their strengths while mitigating their weaknesses.
One of the recent bridges between symbolic and sub-symbolic paradigms is the connection between various fragments of first-order logics and GNN architectures: as explained above, some architectures can express some logics and some not; moreover, some of the expressible logic functions can be trained for and some not. Here, first-order logic is the well-established mathematical basis for many Symbolic AI areas, such as Knowledge Representation and the Semantic Web, with relevant fragments being Description Logics and Modal Logics. In turn, GNNs are a relatively novel class of deep learning architectures that can process graph-structured data and that are applicable to a wide range of tasks [2]. However, the picture is by far not complete, and the two relations between GNN architectures and logics are in many cases not known. The goal of this project is to advance in completing the picture by studying one or both relationships for certain GNN architectures and logics.
Tasks
- Read scientific papers in the area of interest, in particular about known connections between GNNs and logic fragments
- Formulate and prove theorems about the expressivity connections between GNN architectures and logic (if the theory path is taken)
- Demonstrate the worst-case efficiency of the translations (if the theory path is taken)
- Generate training and testing data by labelling graphs and graph nodes from known graph sets using logic formulas (if the experimental path is taken)
- Design, run, and interpret the experiments comparing the ability of GNN architectures to learn functions from various logic fragments (if the experimental path is taken)
Why should you take this project?
After working on this master project, the student will have:
- Got basic understanding of logic-based and GNN-based approaches to AI as well as connections between them
- Pursued full cycle of research: find and read relevant scientific papers, prove theorems, and/or run experiments
- Researched in an under-explored area of high interest to the research community
References
[1] Pablo Barceló, Egor V. Kostylev, Mikael Monet, Jorge Pérez, Juan Reutter, and Juan Pablo Silva. 2019. “The Logical Expressiveness of Graph Neural Networks.” https://openreview.net/pdf?id=r1lZ7AEKvB.
[2] Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. 2020. “Graph Neural Networks: A Review of Methods and Applications.” AI Open 1 (January): 57–81.