This is a collaborative project between Queen’s University Belfast, United Kingdom and Tezpur University, Assam, India. It was primarily sponsored by the Ministry of Education, Government of India.
The subgraph isomorphism search problem is a computational task in which two graphs G and H are given as input, and one must determine whether G contains a subgraph that is isomorphic to H.
The project addresses the computational challenges of the Subgraph Isomorphism (SI) search problem, which involves identifying all embeddings of a smaller pattern graph within a larger data graph. Because this problem is NP-complete, it is highly computationally intensive. The thesis explores adaptive, high-performance solutions using machine learning, heuristic development, and parallel computing. It is divided into three main contributions:
- Machine Learning-Based Algorithm Selection: Developing a framework that uses graph-specific features (summary statistics, local topological information, and label distributions) to dynamically predict the most efficient SI heuristic for a given pair of graphs.
- OrbitSI Algorithm: A heuristic algorithm that exploits the local topological properties (orbits of 4-vertex graphlets) during preprocessing to reduce the search space and eliminate redundant computations.
- NI-ORCA Algorithm: A parallel algorithm for efficiently counting the orbits of non-induced graphlets, distributing computational workloads across multiple processing units to improve execution times and scalability.
List of Publications
The research led to the following publications:
- Tauhidi, S.I., Karmakar, A., Mai, T.S. and Vandierendonck, H., 2024, December. OrbitSI: An Orbit-based Algorithm for the Subgraph Isomorphism Search Problem. In 2024 IEEE International Conference on Knowledge Graph (ICKG) (pp. 360-369). IEEE.
- Tauhidi, S.I., Karmakar, A., Mai, T.S. and Vandierendonck, H., 2023, Graphlet-based Filtering for High-Performance Subgraph Isomorphism Search. HiPEAC 12th International Summer School on Advanced Computer Architecture and Compilation for High-Performance Embedded Systems.
- Tauhidi, S.I., Karmakar, A., Mai, T.S. and Vandierendonck, H., 2023, November. Machine Learning-Based Per-Instance Algorithm Selection for High-Performance Subgraph Isomorphism Enumeration. In International Conference on Metaheuristics and Nature-Inspired Computing (pp. 214-229). Cham: Springer Nature Switzerland.
People
- Syed Ibtisam Tauhidi
- Prof. Hans Vandierendonck
- Dr. Thai Son Mai
- Dr. Arindam Karmakar
Funding
The research was supported by the following:
- The Ministry of Education, Govt. of India.
- The Kelvin Living Lab under Grant No. EP/Z531054/1.
- The EPSRC under Grant No. EP/T022175/1.
Latest News
- OrbitSI is now on PyPi
OrbitSI is an open-source Python framework designed to efficiently solve the subgraph isomorphism enumeration problem, i.e., identifying all subgraphs within a data graph that are structurally… Read more: OrbitSI is now on PyPi - Poster presentation on NI-ORCA at the CLUSTER 2025 conferenceWe attended the CLUSTER 2025 conference organised at the University of Edinburgh, Scotland, United Kingdom, between 2 and 5 September 2025. Syed Tauhidi presented a poster… Read more: Poster presentation on NI-ORCA at the CLUSTER 2025 conference
- Paper presentation on OrbitSI at ICKG 2024, Abu Dhabi, UAESyed Ibtisam Tauhidi recently attended the 2024 IEEE International Conference on Knowledge Graph (ICKG) in Abu Dhabi, United Arab Emirates, held from December 11 to December… Read more: Paper presentation on OrbitSI at ICKG 2024, Abu Dhabi, UAE
- Poster presentation at NI-HPC user conference 2023The NI-HPC user conference was organised at Riddel Hall, Queen’s University, Belfast, on 7 November 2023. Syed Tauhidi attended the conference and presented his work on… Read more: Poster presentation at NI-HPC user conference 2023
- Paper presentation at META 2023 in Marrakech, MoroccoI recently travelled to Marrakech, Morocco, to present my research at the 9th International Conference on Metaheuristics and Nature-Inspired Computing (META 2023). Held from November 1–4,… Read more: Paper presentation at META 2023 in Marrakech, Morocco
- Poster Presentation at the ACACES Summer School by HiPEACSyed Tauhidi presented a poster on “Graphlet-based Filtering for High-Performance Subgraph Isomorphism Search” at the 19th International Summer School on Advanced Computer Architecture and Compilation for… Read more: Poster Presentation at the ACACES Summer School by HiPEAC
- (Winner: Research Culture Poster Competition: EPS faculty) Enhancing Subgraph Isomorphism with Machine Learning-Powered HeuristicsThis 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,… Read more: (Winner: Research Culture Poster Competition: EPS faculty) Enhancing Subgraph Isomorphism with Machine Learning-Powered Heuristics
- High-Performance Distributed Graph Analytics | Sub-graph Isomorphism | Initial ReviewIn this post, I’ll be introducing the core aspects of my research, discussing the significance of subgraph isomorphism search in graphs, and outlining the objectives and… Read more: High-Performance Distributed Graph Analytics | Sub-graph Isomorphism | Initial Review
