Seminar: The Power of Pivoting for Exact Clique Counting

Shweta Jain, a recent Ph.D. graduate in Computer Science from the University of California, Santa Cruz will present a seminar titled "The Power of Pivoting for Exact Clique Counting".

Seminar Video with Slides: View on our YouTube Channel

Abstract:

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=13.

In this talk, I will present a somewhat surprising result: a simple but powerful algorithm called Pivoter that gives the exact k-clique counts for all k and is orders of magnitude faster than even other parallel algorithms. It also improves the worst case running time of clique counting from O(2^n) to O(3^(n/3)). It uses a classic technique called pivoting that drastically cuts down the search space for cliques and builds a structure called the Succinct Clique Tree from which global and local (per-vertex and per-edge)  k-clique counts can be easily read off. The algorithm makes clique counting feasible for a number of graphs for which clique counting was infeasible before. This paper won the Best Paper Award at WSDM, 2020.

Joint work with C. Seshadhri.

Bio:

Shweta's Professional Website. 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.