Rising Stars 2020:

Shweta Jain

Postdoctoral Scholar

University of Illinois Urbana-Champaign

PhD '20 University of California, Santa Cruz

Areas of Interest

  • Artificial Intelligence
  • Theory


Counting cliques in real-world graphs


Cliques are important structures in network science that have been used in numerous applications including spam detection, graph analysis, graph modeling, community detection among others. Obtaining the counts of k-cliques in real-world graphs with millions of nodes and edges is a challenging problem due to combinatorial explosion. Essentially, as k increases, the number of k-cliques goes up exponentially. Existing techniques are (typically) able to count k-cliques for only up to k=5. In this poster, I will present two algorithms, TuránShadow and Pivoter, for obtaining k-clique counts that vastly improve the state of the art, both in theory and in practice. These papers won the Best Paper Awards at WWW, 2017 and WSDM, 2020, respectively.


Shweta Jain received her Ph.D. in Computer Science from the University of California, Santa Cruz where she was advised by Prof. Seshadhri Comandur. She also has a Masters degree in Computer Science from the University of Chicago. Her work aims to bridge the gap between practice and theory by designing provably efficient algorithms that work well in practice, esp. graph algorithms, and algorithms for massive data. Her work has received Best Paper Awards at WWW and WSDM.

Personal home page