HyperISO: Efficiently Searching Subgraph Containment in Hypergraphs

Lingling Zhang, Zhiwei Zhang*, Guoren Wang, Ye Yuan, Shuai Zhao, Jianliang Xu

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review


Searching subgraph containment, also called subgraph matching in hypergraphs, is to enumerate all the embeddings of a data hypergraph with a given query hypergraph, which plays an important role in the analysis of hypergraph-modeled applications. However, existing subgraph matching frameworks mainly focus on pairwise graphs and the existing techniques can not efficiently be applied to search subgraph containment at low costs. Therefore, this paper proposes HyperISO to efficiently search subgraph containment that consists of three parts: 1) new filtering techniques driven by exploring the properties and connections of hyperedges to reduce unpromising products for the sake of low matching costs, 2) a novel ordering strategy that is able to generate an optimized matching process by considering both the sizes of hyperedge candidates and the unmatched vertices of the hyperedges, and 3) a dual enumeration algorithm to list both the vertex and hyperedge mappings. Extensive experiments on both real and synthetic data show that HyperISO outperforms the best among the sophisticated subgraph matching frameworks and meanwhile verify the efficiency of HyperISO in various types of hypergraphs.
Original languageEnglish
Pages (from-to)8112-8125
Number of pages14
JournalIEEE Transactions on Knowledge and Data Engineering
Issue number8
Early online date2 Sept 2022
Publication statusPublished - 1 Aug 2023

Scopus Subject Areas

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

User-Defined Keywords

  • Hypergraphs
  • Searching subgraph containment
  • Subgraph isomorphism


Dive into the research topics of 'HyperISO: Efficiently Searching Subgraph Containment in Hypergraphs'. Together they form a unique fingerprint.

Cite this