conference2026ICORE 2026 A*CORE 2023 A*CCF A

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

Siwoo Song, Wonseok Shin, Kunsoo Park, Giuseppe Italiano, Zhengyi Yang, Wenjie Zhang

IEEE International Conference on Data Engineering (ICDE)

RAIDS Lab Authors

Zhengyi Yang

Director

Details

Year

2026

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

Resources

Code ↗arXiv ↗

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

Siwoo Song

Samsung Research

Wonseok Shin

Standigm Inc

Kunsoo Park

Seoul National University

Giuseppe Italiano

LUISS University

Zhengyi Yang

University of New South Wales

Wenjie Zhang