An Efficient Streaming Algorithm for Approximating Graphlet Distributions
Proceedings of the ACM on Management of Data · 18.05.2026 · 4 (3) · 1-26
DOI: 10.1145/3802010 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 18.05.2026. Verfasst von Marco Bressan und 3 weiteren Autor:innen. Die Arbeit nennt 44 Literaturangaben. Gefördert von: Hong Kong Research Grants Council.
Abstract (Originalsprache)
In recent years, the problem of computing the frequencies of the induced k -vertex subgraphs of a graph, or k-graphlets, has become central. One approach for this problem is to sample k -graphlets randomly. Classic algorithms for k -graphlet sampling require loading the entire graph into main memory, making them impractical for massive graphs. To bypass this limitation, Bourreau et al. (NeurIPS 2024) introduced a streaming algorithm that through nontrivial techniques makes only O (log n ) passes using O ( n log n ) memory. In this work we break their O (log n )-pass bound by giving an algorithm that, for any fixed c > 0, makes O (1/ c ) passes using Õ( n 1+ c ) memory. As a consequence of their lower bound, our algorithm is optimal up to a factor of Õ (n c ) in the memory usage. We use this sampling algorithm to obtain an efficient method of approximating k -graphlet distributions. Experiments on real-world and synthetic graphs show that our algorithm is always at least as good as the one of Bourreau et al., and outperforms it by orders of magnitude on mildly dense graphs.
Förderung
- Hong Kong Research Grants Council
Zitieren
APA
Bressan, M., Chan, T. H., Kuang, Q., & Sozio, M. (2026). An Efficient Streaming Algorithm for Approximating Graphlet Distributions. Proceedings of the ACM on Management of Data, 4(3), 1-26. https://doi.org/10.1145/3802010
Vancouver
Bressan M, Chan TH, Kuang Q, Sozio M. An Efficient Streaming Algorithm for Approximating Graphlet Distributions. Proceedings of the ACM on Management of Data. 2026;4(3):1-26. doi:10.1145/3802010
BibTeX
@article{Bressan2026,
author = {Bressan, Marco and Chan, T-H. Hubert and Kuang, Qipeng and Sozio, Mauro},
title = {An Efficient Streaming Algorithm for Approximating Graphlet Distributions},
journal = {Proceedings of the ACM on Management of Data},
year = {2026},
volume = {4},
number = {3},
pages = {1--26},
doi = {10.1145/3802010}
}
EUVIMED