Subgraph Isomorphism

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:

  1. 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.
  2. 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.
  3. 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 funding agencies:

  • 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 Posts