Sci. et al. News
Image: Official image by Queen Mary University of London
A PhD position for UK Home students is available in the School of Electronic Engineering and Computer Science at Queen Mary University of London, under the supervision of Marc Roth. The research project will focus on the parameterized and fine-grained complexity of computational counting problems related to the analysis of large networks.
Application Deadline: 3 January 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” represents a family of computational challenges central to large-scale network analysis, with applications across data mining, bioinformatics, genetics, and artificial intelligence. In essence, a motif counting problem involves identifying a small pattern (the motif), ( P ), within a larger network ( N ), and calculating the number of occurrences of ( P ) within ( N ). For example, if ( P ) is a triangle, then counting its instances in ( N ) equates to calculating the global clustering coefficient. Recent research has advanced our theoretical understanding of the computational complexity of these problems, revealing insights into the theoretical limitations of graph neural networks. However, existing studies primarily address graph-like data, leaving a gap in understanding motif counting for data organized in higher-arity relations, as in relational databases. This project aims to bridge this gap by exploring the complexity and expressiveness of Motif Counting Problems in higher-order structures. Project goals include:
- Identifying Motif Counting Problems in Higher-Order Structures: Which high-order motif counting problems are practically relevant but computationally intensive? Which patterns capture global properties in data organized with higher-arity relations?
- Complexity Analysis of Identified Patterns: Using advanced algorithmic frameworks and techniques in parameterized and fine-grained complexity theory, what are the most efficient algorithms for these problems?
- Approximation Algorithms for Complex Motif Counting Problems: Designing efficient approximation algorithms for motif counting problems that are computationally hard, potentially using established methods like Markov-Chain Monte Carlo or developing new techniques tailored to these problems.
- Descriptive Complexity Theory and (Hyper-)Graph Neural Networks: Investigating the expressive power needed to model higher-order motif counting in logical frameworks with counting capabilities. This includes translating findings to study the expressive limitations of higher-order or hypergraph neural networks.
The selected candidate will contribute to one or more of these objectives and may have the opportunity to explore new, related directions. Candidates should have a solid foundation in algorithm design and analysis and graph theory. Knowledge of parameterized algorithms, fine-grained complexity theory, randomized and approximation algorithms, descriptive complexity theory, or graph neural networks is an advantage.
How to Apply
Queen Mary University is committed to developing future research leaders and is investing in key research areas.
To apply, candidates should work closely with their prospective supervisor and follow the instructions at Queen Mary’s application page.
Application requirements:
- CV (max 2 pages)
- Cover letter (max 4,500 characters) clearly stating eligibility for a UK resident scholarship on the first page (see eligibility criteria)
- Research proposal (max 500 words)
- Two references
- English language certificate (for non-native speakers)
- Other relevant certificates
Eligibility for home student scholarships requires unrestricted UK residency for at least three years before the studentship start date. For details, refer to the EPSRC guidelines.
For general questions, contact Mrs. Melissa Yeo at [email protected] (administrative) or Dr. Arkaitz Zubiaga at [email protected] (academic) with the subject “EECS 2025 PhD scholarships enquiry.”
