# Dichotomy Graph Sketch: Summarizing Graph Streams with High Accuracy Based on Deep Learning +
## 2 Related Work
### Data Stream Sketches  
Data stream sketches are designed for data stream summarization. Differently from graph streams, data streams are modeled as isolated items, and thus data stream sketches  
Figure 1: Existing graph sketch stores all edges in a single matrix. Figure 2: Average relative error (ARE) of querying light edges and querying heavy edges using TCM on dataset _subelj_jung_ and _subelj_jdk_. cannot answer graph topology queries. C-sketch [8] utilized several hash tables to record data streams, but suffered from both overestimation and underestimation in the frequency estimation task. [PERSON] et al. then proposed CM-sketch [5], which only suffered from overestimation. [PERSON] et al. designed CU-sketch [9] which improved CM-sketch's query accuracy at the cost of not supporting item deletions. The above sketches focused on solving the problem of frequency estimation. However, in various scenarios, we need to find lots of other important information in data streams. For instance, in financial markets, a burst of trading volume may indicate the happening of financial fraud or illegal market manipulation. For another example, persist items in the data streams can be used to detect malicious behaviors in the network security field [10]. [PERSON] et al. designed a generic algorithm, WavingSketch [11], and considered four query tasks: finding top-k frequent items, finding top-k heavy changes, finding top-k persistent items and finding top-k superspreaders. [PERSON] et al. proposed On-Off sketch [12] which focused on the problem of persistence estimation and finding persistent items by a technique to separate persistent and non-persistent items. Similar to CM-Sketch, On-Off sketch adopted \(d\) hash tables to simultaneously summarize data stream. The difference is that a bucket of On-Off sketch can be updated at most once in one time window to avoid overestimation. More recently, [PERSON] et al. proposed BurstSketch [13] to detect bursts accurately in real time. BurstSketch used several hash tables to record a data stream, and find the potential bursts based on the records. Finally, BurstSketch utilized other two hash tables to record the frequency of potential bursts in two consecutive time windows to find real bursts. [PERSON] et al. proposed the concept of perodic batch, namely \(\alpha\) consecutive batches of the same item, where these batches arrive periodically, and they designed HyperCalm Sketch [14] to detect perodic batches in data streams. Different from most data streams sketches which found local top-k frequent items in a single data stream, Double-Anonymous Sketch [15] was designed to find global top-k frequent items in multiple disjoint data streams. Double-Anonymous Sketch consisted of two parts: a Randomized Admission Policy (RA) [16] as the top-k part and a CMM sketch [17] as the count part. RA was used to report top-k items, while CMM sketch was used to report an item's frequency. [PERSON] et al. proposed JoinSketch [18] for inner-product estimation. JoinSketch considered the high skewness of real data, and recorded items with different frequencies in different components to improve accuracy. [PERSON] et al. designed SteadySketch [19] to find the steady items in data streams. SteadySketch was comprised of SteadyFilter and RollingSketch. SteadyFilter was responsible for continuity checking of small flows, while RollingSketch was responsible for continuity checking of large flows. [PERSON] et al. proposed PISketch [20; 21] to find persistent but infrequent item in data streams. Its key idea was to define a weight and its Reward and Penalty System for each flow to combine and balance the information of both persistency and infrequency, and to keep high-weighted flows in a limited space through a strategy. Recently, researchers proposed a new research problem, i.e., summarizing data streams in a sliding window, since--in some scenarios--older data are less valuable. In [22], [PERSON] et al.