Counting HyperGraphlets via Color Coding: a Quadratic Barrier and How to Break It

We study the problem of counting k-hyper graphlets, an interesting but surprisingly ignored primitive, with the aim of understanding if efficient algorithms exist. To this end we consider color coding , a well-known technique for approximately counting k -graphlets in graphs. Our first result is that, on hypergraphs, color coding encounters a quadratic barrier : under the Orthogonal Vector Conjecture, no implementation of it can run in time sub-quadratic in the size of the input. We then introduce a simple property, ( α, β )-niceness, that hypergraphs from real-world datasets appear to satisfy for small values of α and β. Intuitively, an ( α, β )-nice hypergraph can be split into two sub-hypergraphs having respectively rank at most α and degree at most β. By applying different techniques to each sub-hypergraph and carefully combining the outputs, we show how to run color coding in time 2 ^{O ( k )} · [2*| V | + α ^k | E | + α ² β || H ||), where H = ( V, E ) is the input hypergraph. Afterwards, we can sample colorful k -hypergraphlets uniformly in expected k ^{O ( k )} · ( β ² + ln | V |) time per sample. Experiments on real-world hypergraphs show that our algorithm neatly outperforms the naive quadratic algorithm, sometimes by more than an order of magnitude.