# Triangle and Four Cycle Counting with Predictions in Graph Streams

arXiv: https://arxiv.org/abs/2203.09572 · HTML: https://mlsanity.com/paper/2203.09572/

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- Builds on 35 of its 83 references that are in the map.
- First posted on arXiv 17 Mar 2022.

## Builds on (most cited first, 30 of 35)

- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Multi-scale Attributed Node Embedding](https://mlsanity.com/paper/1909.13021/) (2019)
- [Predicting Dynamic Embedding Trajectory in Temporal Interaction Networks](https://mlsanity.com/paper/1908.01207/) (2019)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [The Case for Learned Index Structures](https://mlsanity.com/paper/1712.01208/) (2017)
- [Algorithms with Predictions](https://mlsanity.com/paper/2006.09123/) (2020)
- [The Primal-Dual method for Learning Augmented Algorithms](https://mlsanity.com/paper/2010.11632/) (2020)
- [Community Interaction and Conflict on the Web](https://mlsanity.com/paper/1803.03697/) (2018)
- [Near-Optimal Bounds for Online Caching with Machine Learned Advice](https://mlsanity.com/paper/1910.12172/) (2019)
- [A Model for Learned Bloom Filters, and Optimizing by Sandwiching](https://mlsanity.com/paper/1901.00902/) (2019)
- [Faster Matchings via Learned Duals](https://mlsanity.com/paper/2107.09770/) (2021)
- [Scheduling with Predictions and the Price of Misprediction](https://mlsanity.com/paper/1902.00732/) (2019)
- [Learning to Hash for Indexing Big Data - A Survey](https://mlsanity.com/paper/1509.05472/) (2015)
- [Training Gaussian Mixture Models at Scale via Coresets](https://mlsanity.com/paper/1703.08110/) (2017)
- [Better and Simpler Learning-Augmented Online Caching](https://mlsanity.com/paper/2005.13716/) (2020)
- [Dispersion for Data-Driven Algorithm Design, Online Learning, and Private Optimization](https://mlsanity.com/paper/1711.03091/) (2017)
- [Learning-Theoretic Foundations of Algorithm Configuration for Combinatorial Partitioning Problems](https://mlsanity.com/paper/1611.04535/) (2016)
- [Learning-based Support Estimation in Sublinear Time](https://mlsanity.com/paper/2106.08396/) (2021)
- [Learning to Link](https://mlsanity.com/paper/1907.00533/) (2019)
- [Dimensionality Reduction for Wasserstein Barycenter](https://mlsanity.com/paper/2110.08991/) (2021)
- [Size bounds and query plans for relational joins](https://mlsanity.com/paper/1711.03860/) (2017)
- [Meta-Learning Neural Bloom Filters](https://mlsanity.com/paper/1906.04304/) (2019)
- [Partitioned Learned Bloom Filter](https://mlsanity.com/paper/2006.03176/) (2020)
- [Composable Sketches for Functions of Frequencies: Beyond the Worst Case](https://mlsanity.com/paper/2004.04772/) (2020)
- [On Sampling from Massive Graph Streams](https://mlsanity.com/paper/1703.02625/) (2017)
- [WRS: Waiting Room Sampling for Accurate Triangle Counting in Real Graph Streams](https://mlsanity.com/paper/1709.03147/) (2017)
- [Streaming Complexity of SVMs](https://mlsanity.com/paper/2007.03633/) (2020)
- [An Optimal Algorithm for Triangle Counting in the Stream](https://mlsanity.com/paper/2105.01785/) (2021)

## Built on by (most cited first, 20 of 20)

- [Learning-Augmented Algorithms for Online Linear and Semidefinite Programming](https://mlsanity.com/paper/2209.10614/) (2022)
- [Learning-augmented Maximum Independent Set](https://mlsanity.com/paper/2407.11364/) (2024)
- [Improved Learning-augmented Algorithms for k-means and k-medians Clustering](https://mlsanity.com/paper/2210.17028/) (2022)
- [Improved Frequency Estimation Algorithms with and without Predictions](https://mlsanity.com/paper/2312.07535/) (2023)
- [The Predicted-Updates Dynamic Model: Offline, Incremental, and Decremental to Fully Dynamic Transformations](https://mlsanity.com/paper/2307.08890/) (2023)
- [Learning-Augmented Search Data Structures](https://mlsanity.com/paper/2402.10457/) (2024)
- [Learning-Based Algorithms for Graph Searching Problems](https://mlsanity.com/paper/2402.17736/) (2024)
- [Improved Approximations for Hard Graph Problems using Predictions](https://mlsanity.com/paper/2505.23967/) (2025)
- [On the Power of Learning-Augmented Search Trees](https://mlsanity.com/paper/2211.09251/) (2022)
- [Sub-quadratic Algorithms for Kernel Matrices via Kernel Density Estimation](https://mlsanity.com/paper/2212.00642/) (2022)
- [Fast and Accurate Triangle Counting in Graph Streams Using Predictions](https://mlsanity.com/paper/2409.15205/) (2024)
- [Optimal Algorithms for Augmented Testing of Discrete Distributions](https://mlsanity.com/paper/2412.00974/) (2024)
- [Learning-Augmented Frequent Directions](https://mlsanity.com/paper/2503.00937/) (2025)
- [Learning-Augmented Moment Estimation on Time-Decay Models](https://mlsanity.com/paper/2603.02488/) (2026)
- [On Approximability of ℓ22 Min-Sum Clustering](https://mlsanity.com/paper/2412.03332/) (2024)
- [Learning-Augmented Streaming Algorithms for Correlation Clustering](https://mlsanity.com/paper/2510.10705/) (2025)
- [A Simple Learning-Augmented Algorithm for Online Packing with Concave Objectives](https://mlsanity.com/paper/2406.03574/) (2024)
- [Efficient Approximate Temporal Triangle Counting in Streaming with Predictions](https://mlsanity.com/paper/2506.13173/) (2025)
- [On multiagent online problems with predictions](https://mlsanity.com/paper/2507.12486/) (2025)
- [Transductive and Learning-Augmented Online Regression](https://mlsanity.com/paper/2510.03917/) (2025)

## Abstract (arXiv)

We propose data-driven one-pass streaming algorithms for estimating the number of triangles and four cycles, two fundamental problems in graph analytics that are widely studied in the graph data stream literature. Recently, (Hsu 2018) and (Jiang 2020) applied machine learning techniques in other data stream problems, using a trained oracle that can predict certain properties of the stream elements to improve on prior "classical" algorithms that did not use oracles. In this paper, we explore the power of a "heavy edge" oracle in multiple graph edge streaming models. In the adjacency list model, we present a one-pass triangle counting algorithm improving upon the previous space upper bounds without such an oracle. In the arbitrary order model, we present algorithms for both triangle and four cycle estimation with fewer passes and the same space complexity as in previous algorithms, and we show several of these bounds are optimal. We analyze our algorithms under several noise models, showing that the algorithms perform well even when the oracle errs. Our methodology expands upon prior work on "classical" streaming algorithms, as previous multi-pass and random order streaming algorithms can be seen as special cases of our algorithms, where the first pass or random order was used to implement the heavy edge oracle. Lastly, our experiments demonstrate advantages of the proposed method compared to state-of-the-art streaming algorithms.