Supervisor: Dr Marc Roth
Project Description “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 prob-lem 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 investigating 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 re-lations?2. Complexity Analysis of Motif Counting Problems for patterns identified in 1.: Using mod-ern 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 approxi-mation 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 approxi-mation algorithm 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 ex-pressive power required to model Higher Order Motif Counting problems in selected exten-sions 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 opportu-nities to work on new (but related) directions. The candidate is expected to have a strong back-ground 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: Parameterised Algorithms / Fine-grained Complexity Theory / Randomised and Approximation Algorithms / Descriptive Complexity Theory / Graph Neural Networks. 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.For more information about the project, please contact Marc Roth.
SupervisorDr Marc Roth (he/his) – m.roth@qmul.ac.uk
Centre for Fundamental Computer Science Personal Homepage Google Scholar
How to apply Queen Mary is interested in developing the next generation of outstanding researchers and decided to invest in specific research areas. For further information about potential PhD projects and super-visors please see the list of the projects at the end of this page.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)
Application Deadline The deadline for applications is the 3rd January 2025.
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 contact Dr Marc Roth at m.roth@qmul.ac.uk