This submission won the first prize in the ‘Faculty of Engineering and Physical Sciences’ category at the ‘Research Culture Poster Competition’ organised by the Graduate School, Queen’s University Belfast in 2021.
Two seemingly unrelated fields – biomedical research and road planning – have found common ground through subgraph isomorphism search. This unlikely connection has given rise to a fascinating application: the use of machine learning-powered heuristics to optimize the search for specific patterns within complex data graphs.
Unveiling the Challenge
Imagine a biomedical researcher searching to identify the presence of a specific amino acid within a particular protein molecule. Or, picture a town planner identifying hazardous road interconnections within an extensive road network. Despite the apparent differences, both challenges share a fundamental characteristic – the data, in each case, can be represented as graphs in computer science and requires graph pattern finding.
When represented as graphs, these problems boil down to what’s known as the ‘subgraph isomorphism problem’. In essence, it’s the challenge of finding a small pattern graph within a much larger data graph. Unfortunately, this problem falls into the NP-complete category, indicating that as the pattern and data graphs grow, the search process can become a daunting task, taking weeks, months, or even years to complete.
The Quest for Efficient Solutions
Historically, researchers have grappled with this computational bottleneck, but the absence of a universal algorithm capable of tackling the subgraph isomorphism problem left them with limited options. However, they have proposed heuristics that try to reduce the runtime by pruning the search space.
Heuristics are shortcuts or rules of thumb that aim to find approximate solutions to complex problems. While they provide a way to navigate the subgraph isomorphism problem more efficiently, it’s essential to understand that there’s no one-size-fits-all solution. Different pattern graphs demand different heuristics to achieve optimal performance.
Bridging the Gap with Machine Learning
This brings us to our research question: Can we leverage machine learning to predict the best heuristic for a given pattern graph?
Machine learning techniques allows us to train models that can analyse the properties of a pattern graph and identify which heuristic is most likely to yield the best performance.
Understanding the Machine Learning Magic
The real wonder behind this innovation lies in understanding how machine learning models make these decisions. The details can be complex, but at a high level, they rely on a wealth of training data. This data includes a diverse range of pattern graphs and corresponding heuristic-performance data.
By using machine learning-powered heuristics to solve the subgraph isomorphism problem, we can accelerate the search process.
As we look to the future, it’s exciting to think about the further applications of machine learning and heuristics, as they continue to transform the way we approach complex problems and find solutions that were once thought to be out of reach.