# Undergraduate and Postgraduate Student Projects at QMUL

This page is intended for students at the School for Electrical Engineering and Computer Science at Queen Mary University of London who are considering to write their Undergraduate or Postgraduate Project Thesis in the academic year 2024/2025 with me.

Depending on your skills and interests, projects will generally focus on either implementation and experimentation, or on research in form of mathematical problem solving, but there might of course be an overlap between both types. It is recommended that you took and enjoyed some of the following modules:

ECS407U - Logic and Discrete Structures

ECS421U - Automata and Formal Languages

ECS529U - Algorithms and Data Structures

ECS651U - Computability, Complexity and Algorithms

ECS7018U - Logic in Computer Science

Below are examples of possible thesis projects, and this page will be expanded with further examples in the coming weeks. All projects are scalable to either an UG or a PG project and the expectations and goals will be set accordingly. You are also very welcome to approach me with an individual suggestion of a project. Feel free to contact me if you would like to learn more about one or more of these projects and my research, or if you would like to chat about your own project ideas.

## Counting 3-matchings in subcubic time

### Type: Implementation and Experimentation

A 3-matching in a graph is a set of three edges that do not share common endpoints:

Given a large graph (think of a social network), the number of 3-matchings reveals information about its clustering behaviour. A naive algorithm for counting all 3-matchings in a graph takes cubic time; given a network with millions or billions of nodes, this is infeasible, even with modern hardware. Recent progress in the area of parameterised algorithmics implies the existence of a quite intricate algorithm for counting 3-matchings with subcubic running time that relies on fast matrix multiplication. The goal of this project is thus the implementation of this algorithm and an evaluation of its performance on (large) benchmark instances.

## CFI Graphs: Generation and Experimentation

### Type: Implementation and Experimentation

CFI Graphs (named after Cai, Führer, and Immermann) are mathematical tools for the investigation of the expressiveness of Graph Neural Networks and heuristics for comparing large networks. Concretely, CFI Graphs always come in pairs where one graph is obtained by "twisting" the other; below is an example:

A function f from graphs to natural numbers distinguishes a pair of CFI graphs G and H if f(G) ≠ f(H). For example, the function that counts triangles distinguishes the two graphs above since the left graph contains two triangles, but the right graph does not contain a triangle. It is known that (Message-Passing) Graph Neural Networks "MPGNNs" are unable to compute functions that distinguish CFI graphs. Hence, even the relatively small example given by the two graphs above already implies the quite powerful result that MPGNNs cannot count triangles.

The first goal of this project is the implementation of a system that generates CFI graphs specified by various input parameters. The second goal is then the evaluation of a series of functions and graph parameters on CFI graphs generated in the first goal with the aim of enhancing our understanding of the expressivity of MPGNNs.

## Counting k-cycles in restricted graphs

### Type: Research and Mathematical Problem Solving

A k-cycle in a graph is a sequence of k pairwise distinct vertices v1,v2,...,vk such that for all i ∈ {1,...,k-1} the vertices vi and vi+1, as well as vk and v1, are connected by an edge. See the example below for the illustration of some 5-cycles in a graph.

In this project, we are interested in the computational complexity of counting k-cycles in a graph G. In less formal terms, this means that we either want to find a (theoretically) fast algorithm that counts k-cycles in an input graph, or that we want to prove that no such algorithm can exist under assumptions from complexity theory such as "P ≠ NP".

Unfortunately, it has been known for about 20 years that there is no fast algorithm for counting k-cycles in arbitrary graphs G. For this project, we will therefore restrict the problem to special graphs G (the description of these special graphs is out of the scope of this project description but you are welcome to contact me if you are interested in this project and if you would like to learn more).

Concretely, the goals of this project are twofold:

The (theoretical) development of fast algorithms for counting k-cycles in restricted graphs, or

The construction of rigorous mathematical proofs that no such algorithms exist under assumptions from complexity theory such as "P ≠ NP".