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

Siwoo Song, Wonseok Shin, Kunsoo Park, Giuseppe F. Italiano, Zhengyi Yang, Wenjie ZhangarXiv 2025 · DOI · arXiv

Hypergraph pattern matching is a fundamental but computationally expensive task in modeling complex systems. This paper introduces MaCH, a high-performance algorithm that utilizes a novel "Match-and-Filter" framework and a mathematically rigorous "Intersection Constraint." MaCH prunes the massive search space of these NP-hard problems more effectively and with significantly lower memory overhead than previous approaches, outperforming existing state-of-the-art methods by up to several orders of magnitude.

Introduction

While traditional graphs model pairwise relationships (like a friendship between two people), hypergraphs allow an edge to connect any number of vertices simultaneously. This flexibility makes them ideal for modeling complex systems such as electronic circuits, chemical reaction networks, and social groups. For instance, in a circuit, a single net can connect multiple components—a relationship naturally captured by a hyperedge.

Hypergraph representation of an electronic circuit.

The Challenge of Hypergraph Matching

Finding a specific "pattern" (a query hypergraph) within a massive "data" hypergraph is an NP-hard problem. Previous solutions often struggled with structural complexity—either losing unique properties by transforming hypergraphs into standard graphs or suffering from redundant computations due to vertex symmetries. Furthermore, recent hyperedge-based methods were often slow during verification or required prohibitive amounts of memory for large-scale datasets.

The MaCH Algorithm

The authors propose the MaCH (Match-and-Filter for Hypergraph Pattern Matching) algorithm, which rests on three primary pillars:

  • The Intersection Constraint: This mathematical foundation provides a necessary and sufficient condition to verify if a mapping is valid without explicitly computing every vertex-to-vertex mapping. Using bitwise operations and "Incident Hyperedge Bitmaps," verification time is reduced to linear complexity relative to hyperedge size.
  • Candidate Hyperedge Space (CHS): Instead of storing potential matches for every vertex, MaCH stores matches for every hyperedge. This approach naturally handles vertex automorphisms (symmetries) and reduces the initial search space.
  • Match-and-Filter Framework: Unlike traditional "filter-then-match" sequences, MaCH interleaves these steps. As a partial match is built, the algorithm immediately filters out impossible candidates for remaining edges, preventing exploration of dead-end paths.
Query hypergraph q and data hypergraph H.

Key Results and Performance

MaCH was evaluated on 17 real-world datasets, including labeled hypergraphs like amazon-reviews and large-scale benchmarks like coauth-DBLP. The results demonstrate:

  • Massive Speedups: On the StackOverflow (SA) dataset, MaCH was over 500,000x faster than bipartite-transformation methods and 4,000x faster than the previous leading hyperedge-based algorithm (HGMatch).
  • Memory Efficiency: MaCH is significantly leaner; in one instance (HB dataset), a rival algorithm consumed 1,700x more memory than MaCH.
  • Search Space Reduction: Initial connectivity filtering alone removed up to 99.3% of invalid candidates before the backtracking search even began.

Conclusion

MaCH represents a significant advancement in hypergraph processing. By prioritizing hyperedge signals and interleaving matching with dynamic pruning, it overcomes the efficiency and memory bottlenecks of previous methods. Future work may extend the "Intersection Constraint" to related problems like hypergraph isomorphism and cardinality estimation.

Summary updated

BibTeX
@misc{song2025efficient,
  author = {Siwoo Song and Wonseok Shin and Kunsoo Park and Giuseppe F. Italiano and Zhengyi Yang and Wenjie Zhang},
  title = {{Efficient Hypergraph Pattern Matching via Match-and-Filter and Intersection Constraint}},
  year = {2025},
  eprint = {2512.10621},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2512.10621},
}
Figure