{"ID":2833593,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.03960","arxiv_id":"2512.03960","title":"Aggregating maximal cliques in real-world graphs","abstract":"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 \\emph{$ρ$-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 $ρ\u003c 1$, every graph admits a $ρ$-dense aggregator of \\emph{sub-exponential} size, $n^{O(\\log_{1/ρ}n)}$, 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 $6\\times$ for $ρ=0.1$ (and over $300\\times$ in an extreme case), while delivering a much more concise structural summary.","short_abstract":"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 \\emph{$ρ$-dense aggregators}, a novel approach that succinctly captures maximal clique structure. Instead of listing all...","url_abs":"https://arxiv.org/abs/2512.03960","url_pdf":"https://arxiv.org/pdf/2512.03960v1","authors":"[\"Noga Alon\",\"Sabyasachi Basu\",\"Shweta Jain\",\"Haim Kaplan\",\"Jakub Łącki\",\"Blair D. Sullivan\"]","published":"2025-12-03T16:55:17Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.DM\",\"cs.SI\"]","methods":"[]","has_code":false}