Pivoted subgraph isomorphism: The optimist, the pessimist and the realist

Ehab Abdelhamid, Ibrahim Abdelaziz, Zuhair Khayyat, Panos Kalnis

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

3 Scopus citations


Given query graph Q with pivot node v, Pivoted Subgraph Isomorphism (PSI) finds all distinct nodes in an input graph G that correspond to v in all matches of Q in G. PSI is a core operation in many applications such as frequent subgraph mining, protein functionality prediction and in-network node similarity. Existing applications implement PSI as an instance of the general subgraph isomorphism algorithm, which is expensive and under-optimized. As a result, these applications perform poorly and do not scale to large graphs. In this paper, we propose SmartPSI; a system to efficiently evaluate PSI queries. We develop two algorithms, called optimistic and pessimistic, each tailored for different instances of the problem. Based on machine learning, SmartPSI builds on-the-fly a classifier to decide which of the two algorithms is appropriate for evaluating each graph node. SmartPSI also implements a machine learning-based optimizer to generate low-cost execution plans. Our experimental evaluation with large-scale real graphs shows that SmartPSI outperforms existing approaches by up to two orders of magnitude and is able to process significantly larger graphs. Moreover, SmartPSI is shown to achieve up to 6 times performance improvement when it replaces standard subgraph isomorphism in the state-of-the-art distributed frequent subgraph mining system.

Original languageEnglish (US)
Title of host publicationAdvances in Database Technology - EDBT 2019
Subtitle of host publication22nd International Conference on Extending Database Technology, Proceedings
EditorsCarsten Binnig, Irini Fundulaki, Berthold Reinwald, Zoi Kaoudi, Helena Galhardas, Melanie Herschel
PublisherOpenProceedings.org, University of Konstanz, University Library
Number of pages12
ISBN (Electronic)9783893180813
StatePublished - 2019
Event22nd International Conference on Extending Database Technology, EDBT 2019 - Lisbon, Portugal
Duration: Mar 26 2019Mar 29 2019

Publication series

NameAdvances in Database Technology - EDBT
ISSN (Electronic)2367-2005


Conference22nd International Conference on Extending Database Technology, EDBT 2019

Bibliographical note

Publisher Copyright:
© 2019 Copyright held by the owner/author(s).

ASJC Scopus subject areas

  • Information Systems
  • Software
  • Computer Science Applications


Dive into the research topics of 'Pivoted subgraph isomorphism: The optimist, the pessimist and the realist'. Together they form a unique fingerprint.

Cite this