← Publications
conference2023ICORE 2026 A*CORE 2023 A*CCF A

HGMatch: A Match-by-Hyperedge Approach for Subgraph Matching on Hypergraphs

Zhengyi Yang, Wenjie Zhang, Xuemin Lin*, Ying Zhang, Shunyang Li

IEEE International Conference on Data Engineering (ICDE)

RAIDS Lab Authors

Zhengyi Yang
Zhengyi Yang
Director

Details

Year
2023
Venue
IEEE International Conference on Data Engineering (ICDE)
Publisher
Institute of Electrical and Electronics Engineers (IEEE)
Rankings
ICORE 2026 A* · CORE 2023 A* · CCF A

Research Area

Scalable Data Systems

Tags

HypergraphMatching

Resources

arXiv ↗DOI ↗

Abstract

Hypergraphs are generalisation of graphs in which a hyperedge can connect any number of vertices. It can describe n-ary relationships and high-order information among entities compared to conventional graphs. In this paper, we study the fundamental problem of subgraph matching on hypergraphs (i.e, subhypergraph matching). Existing methods directly extend subgraph matching algorithms to the case of hypergraphs. However, this approach delays hyperedge verification and underutilises the high-order information in hypergraphs, which leads to large search space and high enumeration cost. Furthermore, with the growing size of hypergraphs, it is becoming hard to compute subhypergraph matching sequentially. Thus, we propose an efficient and parallel subhypergraph matching system, HGMatch, to handle subhypergraph matching in massive hypergraphs. We proposes a novel match-by-hyperedge framework to utilise high-order information in hypergraphs and uses set operations for efficient candidates generation. Moreover, we develop an optimised parallel execution engine in HGMatch based on the dataflow model, which features a task-based scheduler and fine-grained dynamic work stealing to achieve bounded memory execution and better load balancing. Experimental evaluation on 10 real-world datasets shows that HGMatch outperforms the extended version of the state-of-the-art subgraph matching algorithms (CFL, DAF, CECI and RapidMatch) by orders of magnitude when using a single thread, and achieves almost linear scalability when the number of threads increases.

Author Affiliations

Zhengyi Yang
University of New South Wales
Wenjie Zhang
University of New South Wales
Xuemin Lin
Shanghai Jiao Tong University
Ying Zhang
University of Technology Sydney
Shunyang Li
University of New South Wales

BibTeX

@inproceedings{yang2023hgmatch,
  title = {HGMatch: A Match-by-Hyperedge Approach for Subgraph Matching on Hypergraphs},
  author = {Yang, Zhengyi and Zhang, Wenjie and Lin, Xuemin and Zhang, Ying and Li, Shunyang},
  url = {http://dx.doi.org/10.1109/ICDE55515.2023.00160},
  doi = {10.1109/icde55515.2023.00160},
  booktitle = {2023 IEEE 39th International Conference on Data Engineering (ICDE)},
  publisher = {IEEE},
  year = {2023},
  month = Apr,
  pages = {2063-2076}
}