Counting HyperGraphlets via Color Coding: a Quadratic Barrier and How to Break It
Proceedings of the VLDB Endowment · 01.05.2026 · 19 (9) · 2073-2085
DOI: 10.14778/3819518.3819535 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the VLDB Endowment, online erschienen am 19.08.2026. Verfasst von Marco Bressan und 2 weiteren Autor:innen. Die Arbeit nennt 22 Literaturangaben.
Abstract (Originalsprache)
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 | + α 2 β || H ||), where H = ( V, E ) is the input hypergraph. Afterwards, we can sample colorful k -hypergraphlets uniformly in expected k O ( k ) · ( β 2 + 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.
Zitieren
APA
Bressan, M., Clemente, S., & Fumagalli, G. (2026). Counting HyperGraphlets via Color Coding: a Quadratic Barrier and How to Break It. Proceedings of the VLDB Endowment, 19(9), 2073-2085. https://doi.org/10.14778/3819518.3819535
Vancouver
Bressan M, Clemente S, Fumagalli G. Counting HyperGraphlets via Color Coding: a Quadratic Barrier and How to Break It. Proceedings of the VLDB Endowment. 2026;19(9):2073-2085. doi:10.14778/3819518.3819535
BibTeX
@article{Bressan2026,
author = {Bressan, Marco and Clemente, Stefano and Fumagalli, Giacomo},
title = {Counting HyperGraphlets via Color Coding: a Quadratic Barrier and How to Break It},
journal = {Proceedings of the VLDB Endowment},
year = {2026},
volume = {19},
number = {9},
pages = {2073--2085},
doi = {10.14778/3819518.3819535}
}
EUVIMED