Fast and accurate triangle counting in graph streams using predictions
Knowledge and Information Systems · 2026-12 · 68 (1)
DOI: 10.1007/s10115-026-02702-8 ↗Kurz gefasst
Fachartikel in der Zeitschrift Knowledge and Information Systems, online erschienen am 16.06.2026. Verfasst von Cristian Boldrin und 2 weiteren Autor:innen. Die Arbeit nennt 43 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Ministero dell’Università e della Ricerca, Università degli Studi di Padova.
Abstract (Originalsprache)
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.
Förderung
- Ministero dell’Università e della Ricerca
- Università degli Studi di Padova
Zitieren
APA
Boldrin, C., Bulat, N., & Vandin, F. (2026). Fast and accurate triangle counting in graph streams using predictions. Knowledge and Information Systems, 68(1). https://doi.org/10.1007/s10115-026-02702-8
Vancouver
Boldrin C, Bulat N, Vandin F. Fast and accurate triangle counting in graph streams using predictions. Knowledge and Information Systems. 2026;68(1). doi:10.1007/s10115-026-02702-8
BibTeX
@article{Boldrin2026,
author = {Boldrin, Cristian and Bulat, Nikola and Vandin, Fabio},
title = {Fast and accurate triangle counting in graph streams using predictions},
journal = {Knowledge and Information Systems},
year = {2026},
volume = {68},
number = {1},
doi = {10.1007/s10115-026-02702-8}
}
EUVIMED