Hypergraph pattern detection using matrix multiplication: A general framework

Boolean conjunctive queries are a fundamental problem in database theory and also subsume (hyper)graph pattern detection as a special case. When restricted to the class of combinatorial algorithms, the best known complexity for answering a query Q is given by the “submodular width” of Q. However, beyond combinatorial algorithms, some isolated queries are known to admit faster algorithms that often involve a clever combination of fast matrix multiplication and data partitioning. Nevertheless, there is no systematic way to derive and analyze the complexity of such algorithms for arbitrary queries Q.

In this talk, we introduce a general framework that captures the best complexity for answering any Boolean conjunctive query Q, and by extension any hypergraph pattern detection problem, using matrix multiplication. Our framework unifies both combinatorial and non-combinatorial techniques under the umbrella of information theory. It generalizes the submodular width to naturally incorporate matrix multiplication, and offers a matching algorithm. We show that our general algorithm matches or improves upon the best known custom algorithms for queries that have been studied in the literature. This talk is based on joint work with Xiao Hu and Dan Suciu.