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 $\rho$-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 $\rho$ that collectively contain every maximal clique.
In contrast to maximal clique enumeration, we prove that for all $\rho < 1$, every graph admits a $\rho$-dense aggregator of sub-exponential size, $n^{O (\log 1/\rho 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 $\rho = 0.1$ (and over 300$\times$ in an extreme case), while delivering a much more concise structural summary.
Based on joint work with Noga Alon, Shweta Jain, Haim Kaplan, Jakub Lacki, and Blair D. Sullivan.
Short Bio: Sabyasachi Basu is a postdoctoral researcher at Microsoft Research India, where he works with the vector search team (DiskANN) on problems in quantization and retrieval. He earned his PhD in Computer Science from the University of California, Santa Cruz, where he worked with C. Seshadhri on sublinear algorithms and graph decompositions. Previously, he completed his undergraduate studies in Mathematics at IISc Bangalore. His research interests include using theoretical insights to design algorithms for real-world data and exploring theoretical questions arising from empirical observations.
