TY - JOUR
T1 - HyperISO: Efficiently Searching Subgraph Containment in Hypergraphs
AU - Zhang, Lingling
AU - Zhang, Zhiwei
AU - Wang, Guoren
AU - Yuan, Ye
AU - Zhao, Shuai
AU - Xu, Jianliang
N1 - Funding Information:
This work was supported in part by the National Key Research and Dvelopment Program of China under Grants 2020YFB1707900 and 2021YFB2700700
Publisher Copyright:
© 1989-2012 IEEE.
PY - 2023/8/1
Y1 - 2023/8/1
N2 - 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.
AB - 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.
KW - Hypergraphs
KW - Searching subgraph containment
KW - Subgraph isomorphism
UR - http://www.scopus.com/inward/record.url?scp=85137938771&partnerID=8YFLogxK
U2 - 10.1109/TKDE.2022.3203856
DO - 10.1109/TKDE.2022.3203856
M3 - Journal article
AN - SCOPUS:85137938771
SN - 1041-4347
VL - 35
SP - 8112
EP - 8125
JO - IEEE Transactions on Knowledge and Data Engineering
JF - IEEE Transactions on Knowledge and Data Engineering
IS - 8
ER -