PhD Studentship Vacancy

I am very happy to announce the following opportunity of a PhD Studentship on "Motif Counting in Higher Order Networks" for UK home students at the School of Electronic Engineering and Computer Science, Queen Mary University of London.

Application Deadline: 4 July 2025

Salary: The PhD student will receive tuition fees and a London stipend at UKRI rates (currently in 2024/25 of £21,237 per year, to be confirmed for 2025/26) annually during the PhD period, which can span for 3 years.

Motif Counting in Higher Order Networks

“Motif Counting” describes a family of computational problems that arise in the context of large-scale network analysis, and that have found numerous applications in datamining, bioinformatics, genetics, and artificial intelligence. More concretely, an instance of a motif counting problem is a pair of a small pattern (called the motif) P, and a large network N, and the task is to compute the number of occurrences of P in N. For example, if P is a triangle, then the corresponding motif counting problem is essentially equivalent to the computation of the global clustering coefficient. Recent years have shown remarkable progress in our theoretical understanding of the computational complexity of those problems, including implications for the theoretical limitations of the expressive power of graph neural networks. However, most existing results apply only for graph-like data, and thus not for data organised in higher arity relations such as provided in (relational) database systems. This project aims to address this gap by investi-gating the complexity and the expressive power of Motif Counting Problems that arise in higher order structures. Concretely, the objectives of the project are:

1. Identification of Motif Counting Problems on Higher Order Structures: Which higher order motif counting problems are already used in practice, but computationally too costly? Which patterns have the potential to describe global properties of data organised in higher arity rela-tions?

2. Complexity Analysis of Motif Counting Problems for patterns identified in 1.: Using modern algorithmic toolkits and lower bound techniques such as parameterised algorithmics and fine-grained complexity theory, what are the theoretically best algorithms for solving those problems?

3. Approximation Algorithms for Hard Motif Counting Problems: Design of efficient approximation algorithms for Motif Counting Problems that have been established to be hard in 2. This can include the application and adaptation of well-established tools in classical approximation algo-rithm engineering such as Markov-Chain-Monte-Carlo approaches, as well as the development of new tools tailored to Motif Counting Problems.

4. Descriptive Complexity Theory and (Hyper-)Graph Neural Networks: Analysis of the expressive power required to model Higher Order Motif Counting problems in selected extensions of first-order logic that incorporate the ability to “count”. Translation of the logical characterisation to the study of the theoretical limitations of the expressiveness of Higher Order Graph Neural Networks or “Hypergraph Neural Networks”.

The successful candidate will work on some of the above objectives, and there will also be opportunities to work on new (but related) directions. The candidate is expected to have a strong background in the design and analysis of algorithms, as well as in graph theory. Prior knowledge in one or more of the following topics is advantageous but not necessary: Parameterised Algorithms / Fine-grained Complexity Theory / Randomised and Approximation Algorithms / Descriptive Complexity Theory / Graph Neural Networks. 

How to apply

Queen Mary University is interested in developing the next generation of outstanding researchers and decided to invest in specific research areas.

Applicants should work with their prospective supervisor and submit their application following the instructions at: http://eecs.qmul.ac.uk/phd/how-to-apply/   

The application should include the following: 

• CV (max 2 pages)  

• Cover letter (max 4,500 characters) stating clearly in the first page whether you are eligible for a scholarship as a UK resident (https://epsrc.ukri.org/skills/students/guidance-on-epsrc-studentships/eligibility)   

• Research proposal (max 500 words) 

• 2 References  

• Certificate of English Language (for students whose first language is not English)  

• Other Certificates  

Please note that to qualify as a home student for the purpose of the scholarships, a student must have no restrictions on how long they can stay in the UK and have been ordinarily resident in the UK for at least 3 years prior to the start of the studentship.  For more information please see: (https://epsrc.ukri.org/skills/students/guidance-on-epsrc-studentships/eligibility)

For general enquiries contact Mrs Melissa Yeo at m.yeo@qmul.ac.uk (administrative enquiries) or Dr Arkaitz Zubiaga at a.zubiaga@qmul.ac.uk (academic enquiries) with the subject “EECS 2025 PhD scholarships enquiry”. 

For specific enquiries please contact me directly.