Counting HyperGraphlets via Color Coding: a Quadratic Barrier and How to Break It
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917405950738432 |
|---|---|
| author | Bressan, Marco Clemente, Stefano Fumagalli, Giacomo |
| author_facet | Bressan, Marco Clemente, Stefano Fumagalli, Giacomo |
| contents | We study the problem of counting $k$-hypergraphlets, an interesting but surprisingly ignored primitive, with the aim of understanding whether 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 can run in sub-quadratic time in the input size. 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)} \cdot (2^β|V| + α^k |E| + α^2 β\|H\|)$, where $H=(V,E)$ is the input hypergraph. Afterwards, we can sample colorful $k$-hypergraphlets uniformly in expected $k^{O(k)} \cdot (β^2 + \ln |V|)$ time per sample. Experiments on real-world hypergraphs show that our algorithm significantly outperforms the naive quadratic algorithm, sometimes by more than an order of magnitude. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_08278 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Counting HyperGraphlets via Color Coding: a Quadratic Barrier and How to Break It Bressan, Marco Clemente, Stefano Fumagalli, Giacomo Data Structures and Algorithms Databases Discrete Mathematics Social and Information Networks 68W05, 68R10 H.2.8; H.2.4; F.2.2 We study the problem of counting $k$-hypergraphlets, an interesting but surprisingly ignored primitive, with the aim of understanding whether 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 can run in sub-quadratic time in the input size. 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)} \cdot (2^β|V| + α^k |E| + α^2 β\|H\|)$, where $H=(V,E)$ is the input hypergraph. Afterwards, we can sample colorful $k$-hypergraphlets uniformly in expected $k^{O(k)} \cdot (β^2 + \ln |V|)$ time per sample. Experiments on real-world hypergraphs show that our algorithm significantly outperforms the naive quadratic algorithm, sometimes by more than an order of magnitude. |
| title | Counting HyperGraphlets via Color Coding: a Quadratic Barrier and How to Break It |
| topic | Data Structures and Algorithms Databases Discrete Mathematics Social and Information Networks 68W05, 68R10 H.2.8; H.2.4; F.2.2 |
| url | https://arxiv.org/abs/2604.08278 |