WWW 2019 Tutorial: Scalable Subgraph Counting: The Methods Behind The Madness

C. Seshadhri and Srikanta Tirthapura


This webpage contains various resources from the WWW 2019 tutorial on subgraph counting. We have put up a pdf of the slides themselves, a bib file of all the references, and a pdf listing out all the references with a short description of the paper.

If you use any of this, please cite our tutorial! If you have suggestions/corrections or want to thank/flame us, please contact us at sesh[at]ucsc[dot]edu and snt[at]iastate[dot]edu. 

@inproceedings{SeTi19,
  author    = {C. Seshadhri and Srikanta Tirthapura},
  title     = {Scalable Subgraph Counting: The Methods Behind The Madness: {WWW} 2019 Tutorial},
  booktitle = {Proceedings of the Web Conference (WWW)},
  year      = {2019}
}
Slides: Part 1     Part 2

Bib file: bib

Description of references: pdf

This is a list of codes/packages referenced in the tutorial. We have omitted some of the older packages which are superseded by newer algorithms. (The tutorial contains a list of these as well.) We have listed the details of the associated subgraph counting paper.

• FEASTPACK
Wedge sampling for computing clustering coefficients and triangle counts on large graphs
C. Seshadhri, Ali Pinar, and Tamara Kolda
Statistical Analysis and Data Mining, 2014

• Orca
A combinatorial approach to graphlet counting
Tomaz Hocevar and Janez Demsar
Bioinformatics, 2014

• PGD
Efficient graphlet counting for large networks
Nesreen K. Ahmed, Jennifer Neville, Ryan A. Rossi, and Nick Duffield
International Conference on Data Mining (ICDM), 2015

• ESCAPE
ESCAPE: Efficiently counting all 5-vertex subgraphs
Ali Pinar, C Seshadhri, and Vaidyanathan Vishal
Conference on World Wide Web (WWW) 2017

• MOSS
MOSS-5: A fast method of approximating counts of 5-node graphlets in large graphs
Pinghui Wang, Junzhou Zhao, Xiangliang Zhang, Zhenguo Li, Jiefeng Cheng, John C. S. Lui, Don Towsley, Jing Tao, and Xiaohong Guan
IEEE Transactions on Knowledge and Data Engineering, 2018

• Turan Shadow
A Fast and Provable Method for Estimating Clique Counts Using Turan's Theorem
Shweta Jain and C. Seshadhri
Conference on World Wide Web (WWW) 2017

• Color coding beyond 5 vertices
Motif counting beyond 5 vertices
Marco Bressan, Flavio Chierichetti, Ravi Kumar, Stefano Leucci, and Alessandro Panconesi
ACM Transactions on Knowledge Discovery from Data (TKDD), 2018

• kClist
Listing k-cliques in sparse real-world graphs
Maximilien Danisch, Oana Denisa Balalau, and Mauro Sozio
In Conference on World Wide Web (WWW), 2018