Syed 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 12, 2024. At the event, he presented the paper, titled “OrbitSI: An orbit-based algorithm for the subgraph isomorphism search problem“, co-authored with Arindam Karmakar, Thai Son Mai, and Hans Vandierendonck. Their research addresses the Subgraph Isomorphism (SI) search problem, an NP-complete challenge that involves finding embeddings of a small pattern graph within a larger data graph. While traditional heuristic algorithms rely on basic vertex properties to filter out impossible matches and determine search order, this work takes a step further by leveraging the graph’s local topological information to make the search process significantly more efficient.
To solve the complex challenges of SI search, OrbitSI utilises the orbit counts of 4-vertex graphlets to characterise local graph topology. This rich structural information enables a powerful filtering strategy to eliminate false positives among candidate vertices, alongside an advanced ordering strategy that forces earlier detection of failing constraints. The study empirically evaluated OrbitSI across eight diverse datasets, each containing a data graph and 1,800 pattern graphs. The algorithm significantly enhanced runtime efficiency, outperforming four state-of-the-art baseline algorithms by speedup factors ranging from 2.69 to 11.49
The paper is available at:
S. I. Tauhidi, A. Karmakar, T. S. Mai and H. Vandierendonck, “OrbitSI: An Orbit-based Algorithm for the Subgraph Isomorphism Search Problem,” in 2024 IEEE International Conference on Knowledge Graph (ICKG), Abu Dhabi, United Arab Emirates, 2024, pp. 360-369, doi: 10.1109/ICKG63256.2024.00052.
