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

Marco Bressan, Stefano Clemente, Giacomo Fumagalli · 2026

Read Counting HyperGraphlets via Color Coding: A Quadratic Barrier and How to Break It by Marco Bressan, Stefano Clemente, Giacomo Fumagalli (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-08278.txt.

Introduction

Bressan, Clemente, and Fumagalli study counting k-hypergraphlets, a surprisingly ignored primitive, asking if fast algorithms exist. They consider color coding, a standard technique for counting graphlets in graphs. First: on hypergraphs, color coding hits a quadratic barrier, with no implementation running sub-quadratically under the Orthogonal Vector Conjecture. They then introduce (alpha, beta)-niceness, a property real-world data satisfy for small alpha and beta. An (alpha, beta)-nice hypergraph splits into two parts, one of rank at most alpha, one of degree at most beta.

Catalog record

CREATORMarco Bressan, Stefano Clemente, Giacomo Fumagalli
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE96329
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.08278

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Counting HyperGraphlets via Color Coding: A Quadratic Barrier and How to Break It Marco Bressan, Stefano Clemente, Giacomo Fumagalli Abstract We study the problem of counting k 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 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, ( α , β ) (\alpha,\beta) -niceness, that hypergraphs from real-world datasets appear to satisfy for small values of α \alpha and β \beta . Intuitively, an ( α , β ) (\alpha,\beta) -nice hypergraph can be split into two sub-hypergraphs having respectively rank at most α \alpha and degree at most β \beta . 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 ∥ ) 2^{O(k)}\cdot\big(2^{\beta}|V|+\alpha^{k}|E|+\alpha^{2}\beta\lVert{H}\rVert\big) , where H = ( V , E ) H=(V,E) is the input hypergraph. Afterwards, we can sample colorful k k -hypergraphlets uniformly in expected k O ⁡ ( k ) ⋅ ( β 2 + ln ⁡ | V | ) k^{O(k)}\cdot(\beta^{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. Code availability: https://github.com/gfumagalli9/hyper-motivo/tree/hyper-motivo 1 Introduction Hypergraphs, the higher-order generalization of graphs, are emerging as expressive and powerful models to represent complex interactions. Recent work suggests that many real-world phenomena that have been traditionally analysed using graphs should rather be analysed using hypergraphs, in particular by looking at the frequency of small induced substructures (called hypergraphlets or hypermotifs ). For example, in collaboration networks, the classic phenomenon of triadic closure actually extends to its higher-order cousin, simplicial closure , the tendency of a group to spawn sub-groups as well 20 ; 4 . Similarly, 17 shows that the frequency vector of hypergraph motifs is correlated with the domain of the hypergraph, something that was previously known of graph motifs. Other examples where hypergraph motif statistics carry fundamental information come from biology 12 , chemistry 2 , social networks 13 , and machine learning 3 . Clearly, in order to make all of this actionable, we need good algorithms to compute hypergraph motif statistics. Unfortunately, this is still an unsolved challenge. According to 12 , already a decade ago we lacked “sophisticated algorithms for mining” hypergraph motifs, and the picture seems to not have changed since then. The goal of our work is to make a first step towards the development of such algorithms. To discuss the matter, let us define the problem more formally. A hypergraph is a pair H=(V,E) where V is a finite set and E\subseteq 2^{V}\setminus\{\emptyset\} . The sub-hypergraph of H=(V,E) induced by U\subseteq V , denoted by H[U] , is the hypergraph with vertex set U and edge set \{e\cap U:e\in E\}\setminus\{\emptyset\} . 1 1 1 There are other notions of induced sub-hypergraphs, but the corresponding problem is computationally even harder, see below. A k -hypergraphlet of H is an induced connected sub-hypergraph H[U] of H with |U|=k . The Hypergraphlet Counting problem (HC for short) asks, given a hypergraph H and an integer k\geq 2 , to compute 2 2 2 We actually allow for approximate counts (exact counts are computationally hard in a strong sense), but we avoid being too precise for now. the number t_{i} of k -hypergraphlets of H that are isomorphic to H_{i} , where H_{i} for i=1,2,\ldots ranges over all isomorphism-distinct k -vertex hypergraphs. In the special case of graphs , HC boils down to Graphlet Counting (GC), the problem of counting connected k -vertex subgraphs. For GC, the state-of-the-art algorithms are built on the celebrated color-coding technique of Alon, Yuster and Zwick 1 . This technique yields sampling and approximate graphlet counting algorithms that for every fixed k run in time linear in the input. More precisely, there is a preprocessing phase that takes time O(\lVert{H}\rVert) where \lVert{H}\rVert=|V|+\sum_{e\in E}|e| , followed by random sampling in O(\lg|V|) -time per sample. Besides being elegant and clean, this approach yields formal statistical guarantees through concentration bounds. An optimized implementation, Motivo , can easily manage graphs with billions of edges 8 . Quite surprisingly, the picture for HC is completely different: we have basically no efficient algorithm, except for the brute-force ones that take time |V|^{\Theta(k)} 16 . Our goal is to explore this gap, and answer the following question: Can we devise algorithms for HC as good as those for GC? If yes, how? If not, why? Given the success of color coding for counting graphlets, it seems compelling to try adapting it to hypergraphlets. The Gaifman graph or primal graph G=\mathsf{Gaif}(H) of H is the graph where u,v are adjacent if they share a hyperedge of H . It is easy to see that H[U] is a k -hypergraphlet if and only if G[U] is a k -graphlet. This observation can be exploited as follows. First, compute G=\mathsf{Gaif}(H) ; we call this step projection . 3 3 3 In the literature, this is also called Clique Expansion (CE). Then, use an O(\lVert{G}\rVert) -time color-coding algorithm on G to sample random k -graphlets G[U] ; each graphlet can then be converted into its corresponding k -hypergraphlet H[U] in H . The same sample weighting techniques of Motivo then yield unbiased hypergraphlet count estimates with concentration guarantees. This looks great, but there is a big catch: the size of G can be quadratic in \lVert{H}\rVert . Indeed, every edge e\in E(H) implies at least {|e|\choose 2} edges of G . Thus, while for graphs this approach yields an O(\lVert{H}\rVert) -time algorithm, for hypergraphs it only yields a much worse O(\lVert{H}\rVert^{2}) -time algorithm. Needless to say, this is prohibitive for large hypergraphs. Is this unavoidable, or can we do better? Our contributions 1) A quadratic barrier. We show that, when the input is a hypergraph, the \Omega(\lVert{H}\rVert^{2}) barrier above is unavoidable for the color-coding approach. More precisely we prove that, under the well-known Orthogonal Vectors Conjecture, 4 4 4 To be precise we use the Moderate-Dimension Orthogonal Vector Conjecture, which says that there is no O(n^{2-\epsilon}\operatorname{poly}(d)) -time algorithm for the following problem: given n vectors from \{0,1\}^{d} , decides if there are two of those vectors that are orthogonal. the output of color-coding’s dynamic program cannot be computed in time O(n^{2-\epsilon}) for any \epsilon>0 . Thus, without further assumptions, color coding cannot yield linear-time algorithms for HC, as it does for GC. We also show that, under another classic definition of induced sub-hypergraph, even deciding if H contains at least one k -hypergraphlet is \#\mathrm{W}[1] -hard and unlikely to be solvable time |V|^{o(\sqrt[3]{k})} . Thus, our definition is arguably the only one that possibly allows for efficient algorithms. 2) A new algorithm. We introduce

Read the complete text