Triangle and Four Cycle Counting with Predictions in Graph Streams
  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.
