Seminars
View all Seminars | Download ICal for this eventAggregating maximal cliques in real-world graphs
Series: Bangalore Theory Seminars
Speaker: Sabyasachi Basu Microsoft Research India
Date/Time: Dec 05 11:00:00
Location: CSA Auditorium, (Room No. 104, Ground Floor)
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 $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.
Microsoft teams link:
Link
We are grateful to the Kirani family (Link and the Walmart Center for Tech Excellence (Link for generously supporting this seminar series
Hosts: Rameesh Paul, Nirjhar Das, KVN Sreenivas, Debajyoti Kar, Rahul Madhavan