Overall project objective
An interesting connection has been recently discovered between the symbolic and sub-symbolic AI paradigms for data management, specifically between computational logics and Graph Neural Networks (GNNs). In particular, it was shown that certain GNN architectures are able to express some fragments of first-order logic, but fail to do so with others due to lack of enough expressive power. Here, expressivity of a logic fragment by a GNN architecture means that every function on graphs given by a formula in the logical fragment can be written as a GNN model in the architecture. Yet, the fact that there exists such a GNN model does not immediately mean that we can train that model in practice with a satisfactory precision. Such trainability of a GNN for logical functions is an open empirical research question, and this is the question that the master student will investigate in their work.
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; however, this connection is not really practical, because expressivity does not immediately imply trainability, which is a research topic of this project. 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].
Tasks
- Read scientific papers in the area of interest, in particular about known connections between GNNs and logic fragments
- Generate training and testing data by labelling graphs (and graph nodes) from known graph sets using logic formulas
- Implement several GNN architectures (e.g., using Pytorch) and train them on the generated data
- Design and run experiments comparing the ability of GNN architectures to learn functions from various logic fragments
- Interpret the experiments’ results and make adjustments to the architectures based on the interpretation
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, design and experiments, interpreted the results, made adjustments based on the results
- Researched in an underexplored area of high interest to the research community
- Developed practical abilities for working with deep learning (e.g., using Pyhton and Pytorch)
References
[1] Barceló, Pablo, 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] Zhou, Jie, 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.