Stay Informed:
Baskin Engineering COVID-19 Information and Resources
Campus Roadmap to Recovery
Zoom Links: Zoom Help | Teaching with Zoom | Zoom Quick Guide

Defense: Counting Cliques in Real-World Graphs

Speaker Name: 
Shweta Jain
Speaker Title: 
Ph.D. Candidate
Start Time: 
Thursday, January 9, 2020 - 3:00pm
Engineering 2, Room 280

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 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, and it is not known how one can count them without enumerating. Obtaining global k-clique counts is challenging. Obtaining local (per-vertex and per-edge) k-clique counts is even more so.

In this work, we present a set of techniques to efficiently count the number of k-cliques in large real-world graphs. Our first method is a randomized approximation algorithm that constructs an object called the Turán shadow which allows for efficient random sampling of (and hence estimation of the counts of) k-cliques, with provable guarantees. It outperforms all other algorithms for clique counting on real-world graphs for k up to 10. We also demonstrate how TuránShadow can be extended to efficiently count near-cliques - cliques that are missing a few edges.

Our second method is an exact clique counting algorithm called Pivoter that uses a technique called pivoting to drastically cut down the search space for cliques and shows remarkable improvement over the state-of-the-art. It builds a structure called the Succinct Clique Tree from which global as well as local k-clique counts can be easily read-off. Using this algorithm, k-clique counts of several graphs for which clique counting was infeasible before were obtained for the first time.

Finally, we highlight some open problems and future directions to explore to make clique counts even more accessible on large, real-world graphs.

Event Type: 
Prof. Seshadhri Comandur
Graduate Program: 
Computer Science, Ph.D.