Efficient Hypergraph Pattern Matching via Match-and-Filter and Intersection Constraint

RAIDS Lab Authors

Zhengyi Yang

Director

Details

Research Area

Tags

Resources

Abstract

A hypergraph is a generalization of a graph, in which a hyperedge can connect multiple vertices, modeling complex relationships involving multiple vertices simultaneously. Hypergraph pattern matching, which is to find all isomorphic embeddings of a query hypergraph in a data hypergraph, is one of the fundamental problems. In this paper, we present a novel algorithm for hypergraph pattern matching by introducing (1) the intersection constraint, a necessary and sufficient condition for valid embeddings, which significantly speeds up the verification process, (2) the candidate hyperedge space, a data structure that stores potential mappings between hyperedges in the query hypergraph and the data hypergraph, and (3) the Match-and-Filter framework, which interleaves matching and filtering operations to maintain only compatible candidates in the candidate hyperedge space during backtracking. Experimental results on real-world datasets demonstrate that our algorithm significantly outperforms the state-of-the-art algorithms, by up to orders of magnitude in terms of query processing time.

Author Affiliations

@inproceedings{song2026efficient,
  title = {Efficient Hypergraph Pattern Matching via Match-and-Filter and Intersection Constraint},
  author = {Song, Siwoo and Shin, Wonseok and Park, Kunsoo and Italiano, Giuseppe F. and Yang, Zhengyi and Zhang, Wenjie},
  url = {http://dx.doi.org/10.1109/ICDE65706.2026.00052},
  doi = {10.1109/icde65706.2026.00052},
  booktitle = {2026 IEEE 42nd International Conference on Data Engineering (ICDE)},
  publisher = {IEEE},
  year = {2026},
  month = May,
  pages = {615-628}
}