HESM: A Hyperedge Embedding-Based Subhypergraph Matching Method

Hypergraphs generalize traditional graphs by allowing hyperedges to connect any number of vertices, enabling the representation of complex relationships. Subhypergraph matching queries aim to identify all subhypergraphs within a hypergraph that are isomorphic to a given query hypergraph. However, existing subhypergraph matching methods often fail to leverage the higher-order structure of hypergraphs efficiently. At the same time, these methods typically require traversing each hyperedge in the data hypergraph to find candidate sets for query hyperedges, leading to high computational and time costs. In this paper, we introduce a lossless transformation structure called the hypergraph mapping graph. Leveraging this structure, we propose a hyperedge embedding method that ensures if a hyperedge in the query hypergraph matches one in the data hypergraph, the embedding of the data hyperedge dominates that of the query hyperedge. We then apply spatial indexing to the hyperedge embeddings of the data hypergraph, enabling direct retrieval of query candidate sets without requiring traversal of the data hypergraph. Finally, we present a parallel matching method that capitalizes on GPU parallelism to accelerate the enumeration process. Experimental results demonstrate that our proposed method significantly outperforms existing approaches.