Parallel Subgraph Matching

  • Parallel Subgraph Matching

School of Electronics, Electrical Engineering and Computer Science
& ECIT Global Research Institute

Proposed Project Title: Parallel Subgraph Matching

Principal Supervisor:   Hans Vandierendonck


Project Description:

Subgraph matching has numerous use cases in cybersecurity and knowledge discovery through problems such as graph partitioning, finding frequent graph patterns, graph colouring, graph-based anomaly detection, etc. Considering the massive growth of data, applying subgraph matching is challenging as it is inherently an NP-complete problem, even though many subgraph matching algorithms terminate in polynomial time for “easy” graphs. Subgraph matching algorithms moreover use backtracking and require a large amount of state to be kept at each backtracking step. These characteristics make it hard to efficiently parallelise subgraph matching algorithms.

The goal of this PhD is to investigate parallel subgraph matching algorithms and develop novel approaches to the parallelisation that are time- and space-efficient. One potential avenue of research is to investigate formulations of subgraph matching using Pregel-like models for graph analytics. These models express graph algorithms in an abstract manner while providing a highly-optimised domain-specific parallel runtime system that provides memory management and controls parallel execution.

Contact details

Supervisor Name: Hans Vandierendonck                                                                     Tel: +44 (0)28 9097
QUB Address: Computer Science Building, 18 Malone Road, Belfast BT9 5BN                  Email: