  Real-world graphs often manifest as a massive temporal stream of edges. The
need for real-time analysis of such large graph streams has led to progress on
low memory, one-pass streaming graph algorithms. These algorithms were designed
for simple graphs, assuming an edge is not repeated in the stream. Real graph
streams however, are almost always multigraphs i.e., they contain many
duplicate edges. The assumption of no repeated edges requires an extra pass
*storing all the edges* just for deduplication, which defeats the purpose of
small memory algorithms.
  We describe an algorithm for estimating the triangle count of a multigraph
stream of edges. We show that all previous streaming algorithms for triangle
counting fail for multigraph streams, despite their impressive accuracies for
simple graphs. The bias created by duplicate edges is a major problem, and
leads these algorithms astray. Our algorithm avoids these biases through
careful debiasing strategies and has provable theoretical guarantees and
excellent empirical performance. Our algorithm builds on the previously
introduced wedge sampling methodology.
  Another challenge in analyzing temporal graphs is finding the right temporal
window size. Our algorithm seamlessly handles multiple time windows, and does
not require committing to any window size(s) a priori. We apply our algorithm
to discover fascinating transitivity and triangle trends in real-world graph
streams.
