Fast and accurate triangle counting in graph streams using predictions

Full abstract

Read the full abstract

Abstract In this work, we present the first efficient and practical algorithms for estimating the number of triangles in a graph stream using predictions . Our algorithms combine waiting room sampling and uniform sampling schemes with a predictor for the heaviness of edges, that is, the number of triangles in which an edge is involved. As a result, our algorithms are fast, provide guarantees on the amount of memory used, and exploit the additional information provided by the predictor to produce highly accurate estimates. We also propose a simple and domain-independent predictor, based on the degree of nodes, that can be easily computed with one pass on a stream of edges when the stream is available beforehand. Our analytical results show that, when the predictor provides useful information on the heaviness of edges, it leads to estimates with reduced variance compared to the state-of-the-art, even when the predictions are far from perfect. Our experimental results show that, when analyzing a single graph stream, our algorithms are faster than the state-of-the-art for a given memory budget, while providing significantly more accurate estimates. Even more interestingly, when sequences of hundreds of graph streams are analyzed, our algorithm significantly outperforms the state-of-the-art using our simple degree-based predictor built by analyzing only the first graph of the sequence. We also present a method to dynamically update the degree-based predictor to maintain high-quality predictions as the streams in the sequence are processed, leading to improved estimates.