Using Colors and Sketches to Count Subgraphs in a Streaming Graph

Shirin Handjani, Douglas Jungreis, Mark Tiefenbruck

Suppose we wish to estimate $\#H$, the number of copies of some small graph $H$ in a large streaming graph $G$. There are many algorithms for this task when $H$ is a triangle, but…