BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1675
DTSTAMP:20260122T084352Z
SUMMARY:Aggregating maximal cliques in real-world graphs
DESCRIPTION:Speaker: Sabyasachi Basu (Microsoft Research)\n\nAbstract: \nMa
 ximal clique enumeration is a fundamental graph mining task\, but its util
 ity is often limited by computational intractability and highly redundant 
 output. To address these challenges\, we introduce $\\rho$-dense aggregato
 rs\, a novel approach that succinctly captures maximal clique structure. I
 nstead of listing all cliques\, we identify a small collection of clusters
  with edge density at least $\\rho$ that collectively contain every maxima
 l clique.In contrast to maximal clique enumeration\, we prove that for all
  $\\rho < 1$\, every graph admits a $\\rho$-dense aggregator of sub-expone
 ntial size\, $n^{O (\\log 1/\\rho n)}$\, and provide an algorithm achievin
 g this bound. For graphs with bounded degeneracy\, a typical characteristi
 c of real-world networks\, our algorithm runs in near-linear time and prod
 uces near-linear size aggregators. We also establish a matching lower boun
 d on aggregator size\, proving our results are essentially tight. In an em
 pirical evaluation on real-world networks\, we demonstrate significant pra
 ctical benefits for the use of aggregators: our algorithm is consistently 
 faster than the state-of-the-art clique enumeration algorithm\, with media
 n speedups over 6$\\times$ for $\\rho = 0.1$ (and over 300$\\times$ in an 
 extreme case)\, while delivering a much more concise structural summary.Ba
 sed on joint work with Noga Alon\, Shweta Jain\, Haim Kaplan\, Jakub Lacki
 \, and Blair D. Sullivan.\nShort Bio: Sabyasachi Basu is a postdoctoral re
 searcher at Microsoft Research India\, where he works with the vector sear
 ch 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 decomp
 ositions. Previously\, he completed his undergraduate studies in Mathemati
 cs at IISc Bangalore. His research interests include using theoretical ins
 ights to design algorithms for real-world data and exploring theoretical q
 uestions arising from empirical observations.\n
URL:https://www.tcs.tifr.res.in/web/events/1675
DTSTART;TZID=Asia/Kolkata:20260123T140000
DTEND;TZID=Asia/Kolkata:20260123T150000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR