{"id":2753,"date":"2023-12-02T03:03:22","date_gmt":"2023-12-02T03:03:22","guid":{"rendered":"https:\/\/blogs.qub.ac.uk\/dipsa\/?page_id=2753"},"modified":"2026-04-30T00:54:49","modified_gmt":"2026-04-29T23:54:49","slug":"si-search","status":"publish","type":"page","link":"https:\/\/blogs.qub.ac.uk\/dipsa\/si-search\/","title":{"rendered":"Subgraph Isomorphism"},"content":{"rendered":"\n<div class=\"wp-block-media-text is-stacked-on-mobile\" style=\"grid-template-columns:34% auto\"><figure class=\"wp-block-media-text__media\"><img fetchpriority=\"high\" decoding=\"async\" width=\"1024\" height=\"485\" src=\"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-content\/uploads\/sites\/14\/2026\/04\/1613328156791-1024x485.png\" alt=\"\" class=\"wp-image-3694 size-full\" srcset=\"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-content\/uploads\/sites\/14\/2026\/04\/1613328156791-1024x485.png 1024w, https:\/\/blogs.qub.ac.uk\/dipsa\/wp-content\/uploads\/sites\/14\/2026\/04\/1613328156791-300x142.png 300w, https:\/\/blogs.qub.ac.uk\/dipsa\/wp-content\/uploads\/sites\/14\/2026\/04\/1613328156791-768x364.png 768w, https:\/\/blogs.qub.ac.uk\/dipsa\/wp-content\/uploads\/sites\/14\/2026\/04\/1613328156791.png 1280w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure><div class=\"wp-block-media-text__content\">\n<p>The <strong>subgraph isomorphism search<\/strong> problem is a computational task in which two graphs <strong><em>G<\/em><\/strong> and <strong><em>H<\/em><\/strong> are given as input, and one must determine whether <strong><em>G<\/em><\/strong> contains a subgraph that is isomorphic to <strong><em>H<\/em><\/strong>.<\/p>\n<\/div><\/div>\n\n\n\n<p id=\"p-rc_36bdaa7e6c5279d0-51\">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<sup><\/sup>. Because this problem is NP-complete, it is highly computationally intensive<sup><\/sup>. The thesis explores adaptive, high-performance solutions using machine learning, heuristic development, and parallel computing<sup><\/sup>. It is divided into three main contributions:<\/p>\n\n\n\n<ol start=\"1\" class=\"wp-block-list\">\n<li><strong>Machine Learning-Based Algorithm Selection<\/strong>: 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.<\/li>\n\n\n\n<li><strong>OrbitSI Algorithm<\/strong>: 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.<\/li>\n\n\n\n<li><strong>NI-ORCA Algorithm<\/strong>: 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.<\/li>\n<\/ol>\n\n\n\n<h3 class=\"wp-block-heading\">List of Publications<\/h3>\n\n\n\n<p id=\"p-rc_36bdaa7e6c5279d0-55\">The research led to the following publications<sup><\/sup>:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>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 <em>2024 IEEE International Conference on Knowledge Graph (ICKG)<\/em> (pp. 360-369). IEEE.<\/li>\n\n\n\n<li>Tauhidi, S.I., Karmakar, A., Mai, T.S. and Vandierendonck, H., 2023, Graphlet-based Filtering for High-Performance Subgraph Isomorphism Search. <em>HiPEAC 12th International Summer School on Advanced Computer Architecture and Compilation for High-Performance Embedded Systems<\/em>.<\/li>\n\n\n\n<li>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 <em>International Conference on Metaheuristics and Nature Inspired Computing<\/em> (pp. 214-229). Cham: Springer Nature Switzerland.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">People<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Syed Ibtisam Tauhidi<\/strong><\/li>\n\n\n\n<li><strong>Prof. Hans Vandierendonck<\/strong><\/li>\n\n\n\n<li><strong>Dr. Thai Son Mai<\/strong><\/li>\n\n\n\n<li><strong>Dr. Arindam Karmakar<\/strong><\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">Funding<\/h3>\n\n\n\n<p id=\"p-rc_36bdaa7e6c5279d0-64\">The research was supported by the following funding agencies<sup><\/sup>:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>The Ministry of Education, Govt. of India.<\/li>\n\n\n\n<li>The Kelvin Living Lab under Grant No. EP\/Z531054\/1.<\/li>\n\n\n\n<li>The EPSRC under Grant No. EP\/T022175\/1.<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\">Latest Posts<\/h2>\n\n\n<ul class=\"wp-block-latest-posts__list has-dates wp-block-latest-posts\"><li><a class=\"wp-block-latest-posts__post-title\" href=\"https:\/\/blogs.qub.ac.uk\/dipsa\/orbitsi-is-now-on-pypi\/\">OrbitSI is now on PyPi<\/a><time datetime=\"2025-11-05T01:08:43+00:00\" class=\"wp-block-latest-posts__post-date\">5 November 2025<\/time><\/li>\n<li><a class=\"wp-block-latest-posts__post-title\" href=\"https:\/\/blogs.qub.ac.uk\/dipsa\/machine-learning-based-per-instance-algorithm-selection-for-high-performance-subgraph-isomorphism-enumeration\/\">Machine learning-based per-instance algorithm selection for high-performance subgraph isomorphism enumeration<\/a><time datetime=\"2023-11-06T00:27:00+00:00\" class=\"wp-block-latest-posts__post-date\">6 November 2023<\/time><\/li>\n<li><a class=\"wp-block-latest-posts__post-title\" href=\"https:\/\/blogs.qub.ac.uk\/dipsa\/poster-presentation-graphlet-based-filtering-for-high-performance-subgraph-isomorphism-search\/\">Poster Presentation | Graphlet-based Filtering for High-Performance Subgraph Isomorphism Search<\/a><time datetime=\"2023-07-10T10:04:00+01:00\" class=\"wp-block-latest-posts__post-date\">10 July 2023<\/time><\/li>\n<li><a class=\"wp-block-latest-posts__post-title\" href=\"https:\/\/blogs.qub.ac.uk\/dipsa\/enhancing-biomedical-research-and-road-planning-with-machine-learning-powered-heuristics\/\">Enhancing Biomedical Research and Road Planning with Machine Learning-Powered Heuristics<\/a><time datetime=\"2021-10-02T01:02:00+01:00\" class=\"wp-block-latest-posts__post-date\">2 October 2021<\/time><\/li>\n<li><a class=\"wp-block-latest-posts__post-title\" href=\"https:\/\/blogs.qub.ac.uk\/dipsa\/high-performance-distributed-graph-analytics-sub-graph-isomorphism-initial-review\/\">High-Performance Distributed Graph Analytics | Sub-graph Isomorphism | Initial Review<\/a><time datetime=\"2021-05-24T10:04:00+01:00\" class=\"wp-block-latest-posts__post-date\">24 May 2021<\/time><\/li>\n<\/ul>\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>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 [&hellip;]<\/p>\n","protected":false},"author":1149,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-2753","page","type-page","status-publish","czr-hentry"],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/pages\/2753","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/users\/1149"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/comments?post=2753"}],"version-history":[{"count":3,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/pages\/2753\/revisions"}],"predecessor-version":[{"id":3697,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/pages\/2753\/revisions\/3697"}],"wp:attachment":[{"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/media?parent=2753"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}