HyperISO: Efficiently Searching Subgraph Containment in Hypergraphs

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.