学界|伦敦玛丽女王大学招募理论计算机科学博士

Position: PhD in Computational Counting Problems

School: School for Electronic Engineering and Computer Science

Supervisor: Marc Roth

Location: Queen Mary University of London, UK

The project will focus on the parameterised and fine-grained complexity of computational counting problems in the analysis of large 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:

• 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?

• 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?

• 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.

• 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: Parameterised Algorithms / Fine-grained Complexity Theory / Randomised and Approximation Algorithms / Descriptive Complexity Theory / Graph Neural Networks. 

To qualify for the scholarship, students must:

Have no restrictions on their stay in the UK.

Have been ordinarily resident in the UK for at least 3 years prior to the start of the studentship.

For more details on eligibility, refer to EPSRC studentship eligibility.

https://www.ukri.org/councils/epsrc/

Administrative Enquiries: Mrs Melissa Yeo at m.yeo@qmul.ac.uk

Academic Enquiries: Dr Arkaitz Zubiaga at a.zubiaga@qmul.ac.uk

Project-specific Queries: Marc Roth at m.roth@qmul.ac.uk

Application Deadline: 3 January 2025