Aggregating Maximal Cliques in Real-World Graphs

Maximal clique enumeration is a fundamental graph mining task, but its utility is often limited by computational intractability and highly redundant output. To address these challenges, we introduce ρ-dense aggregators , a novel approach that succinctly captures maximal clique structure. Instead of listing all cliques, we identify a small collection of clusters with edge density at least ρ that collectively contain every maximal clique.

In contrast to maximal clique enumeration, we prove that for all ρ < 1, every graph admits a ρ -dense aggregator of sub-exponential size, n ^O (log ₁ / ρ ⁿ ), and provide an algorithm achieving this bound. For graphs with bounded degeneracy, a typical characteristic of real-world networks, our algorithm runs in near-linear time and produces near-linear size aggregators. We also establish a matching lower bound on aggregator size, proving our results are essentially tight. In an empirical evaluation on real-world networks, we demonstrate significant practical benefits for the use of aggregators: our algorithm is consistently faster than the state-of-the-art clique enumeration algorithm, with median speedups over 2.5× for ρ = 0.1 (and over 300× in an extreme case), while delivering a much more concise structural summary.