EUVIMEDEUVIMED entdecken
Crossref

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

Marco Bressan, Stefano Clemente, Giacomo Fumagalli

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →