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.

为了解决图分析中广泛研究的三角形和四个环这两个基本问题，我们提出了数据驱动的单通量流算法。我们还探索了在多个图边流模型中使用 “重边” 预言家的能力，并展示了该方法相对于现有流算法的优势。