# Dichotomy Graph Sketch: Summarizing Graph Streams with High Accuracy Based on Deep Learning +
## 3 Preliminaries  
Some formal definitions are provided in this section, as well as a preliminary introduction to the basic idea of summarizing a graph stream using graph sketches. **Definition 1** (Graph stream). : _A graph stream is a consecutive sequence of items \(S=\{e_{1},e_{2},\)\(\ldots,e_{n}\}\), where each item \(e_{i}=(s,d,t,w)\) denotes a directed edge from node \(s\) to node \(d\) arriving at timestamp \(t\) with weight \(w\)._  
It is important to note that an edge \(e_{i}\) may appear multiple times at different timestamps. Consequently, the final weight of \(e_{i}\) is calculated using an _aggregation function_. There are various types of aggregation functions, including \(min(\cdot)\), \(max(\cdot)\), \(average(\cdot)\), \(sum(\cdot)\), etc. The \(sum(\cdot)\) function is the most widely accepted [1; 2], so we also use it as the aggregation function in the remainder of this paper. Due to the fact that edges arrive one by one in a graph stream \(S=\{e_{1},e_{2},\ldots,e_{n}\}\), the graph stream may form a dynamic graph which changes as edges arrive (both edge weight and graph architecture may change as edges arrive). **Definition 2** (Session). : _A session \(C=\{e_{i},e_{i+1},\ldots,e_{j}\}(1\leq i<j\leq n)\) is defined as a continuous subsequent graph stream \(S=\{e_{1},e_{2},\ldots,e_{n}\}\)._  
**Definition 3** (Heavy edge). : _In a graph stream \(S\), an edge that ranks in the top \(k\) percentile out of all the unique edges in a graph stream is considered to be a heavy edge._  
**Definition 4** (Light edge). : _Each edge in a graph stream \(S\) except the heavy edges is regarded as a light edge._  
**Definition 5** (Graph sketch [1]). : _Supposing that a graph \(G=(V,E)\) is formed by a given graph stream \(S\), graph sketch \(\mathcal{K}\) is defined as a graph \(\mathcal{K}=(V_{\mathcal{K}},E_{\mathcal{K}})\) whose size is smaller than \(G\), i.e., \(|V_{\mathcal{K}}|\leq|V|\) and \(|E_{\mathcal{K}}|\leq|E|\), where a hash function \(H(\cdot)\) is associated with map each node in \(V\) to a node in \(V_{\mathcal{K}}\). Correspondingly, an edge \((s,d)\) in \(E\) will be mapped to the edge \((H(s),H(d))\) in \(E_{\mathcal{K}}\)._  
In order to minimize the query error caused by hash collisions, it is common to simultaneously utilize a number of graph sketches \(\{\mathcal{K}_{1},\mathcal{K}_{2},\ldots,\mathcal{K}_{m}\}\) that use different hash functions \(\{H_{1}(\cdot),H_{2}(\cdot),\ldots,H_{m}(\cdot)\}\) to summarize a graph stream. **Definition 6** (Graph compression ratio [1]). : _Compression ratio \(r\) in graph summarization means that a graph sketch uses \(|E|\times r\) space to store a graph \(G=(V,E)\). For example, if a graph stream contains 500,000 edges, compression ratio \(1/50\) indicates indicates that the graph sketch takes 500,000 \(\times\) 1/50 = 10,000 space units, which is a \(\sqrt{10,000}\times\sqrt{10,000}\) (i.e., \(100\times 100\)) matrix. In practice, adjacency matrix is usually adopted to implement a graph sketch. We call \(\alpha=\sqrt{|E|\times r}\) the width of graph sketch._  
In Figure 3, an example illustrates how a set of graph sketches can be used to summarize a graph stream and answer queries. Considering two graph sketches with different hash functions for summarizing a graph stream \(S\), all the values in the two adjacency matrices are initialized to 0 at the beginning. In response to the arrival of an edge, both graph sketches conduct the following _edge update_ operation. **Edge update:** Each graph sketch \(\mathcal{K}_{i}\) calculates the hash values \((H_{l}(s),H_{l}(d))\) for each edge \(e=(s,d,t,w)\) in graph stream \(S\). Afterwards, it locates the corresponding position \(M_{i}[H_{i}(s)][H_{l}(d)]\) in the adjacency matrix and adds the value there by \(w\). Graph sketches are capable of answering edge queries and node queries in linear time after processing all the edge updates. The method of answering queries are described as follows. **Edge query:** The purpose of edge query is to return the estimated weight of an given edge \(e=(s,d)\).