# Dichotomy Graph Sketch: Summarizing Graph Streams with High Accuracy Based on Deep Learning +
###### Abstract
Typical graph sketches use a random hash function to map each edge to a bucket of a matrix, and then record the edge weight within the bucket, as illustrated in Figure 1. As a result of the random nature of the hash function, hash collisions may occur when querying an edge or a node with the graph sketch. There will be a significant performance degradation on query tasks if a heavy edge (an edge with a large weight) collides with a light edge (an edge with a small weight). In the example presented in Figure 1, the graph stream contains one heavy edge (edge \(e_{2}\)) with a weight of 100 and three light edges (edges \(e_{1}\), \(e_{3}\) and \(e_{4}\)). It is possible for a graph sketch to map a heavy edge \(e_{1}\) and a light edge \(e_{2}\) to the same bucket of the matrix due to a hash collision. In graph sketch, the bucket stores the sum of the edge weights (see Section 3 for details); therefore, the value recorded in this bucket is \(1+100=101\). As a result, if we query the weight of edge \(e_{1}\), the graph sketch will return the value 101, and the relative error (see Section 5.2.1 for details) of this query is \((101-1)/1=100\), which is extraordinary high for a light edge. We further test the performance of TCM [1], a state-of-the-art graph sketch, on two real-world datasets, _subelj_jung_ ([[http://konect.cc/networks/subelj_jung-j/](http://konect.cc/networks/subelj_jung-j/)]([http://konect.cc/networks/subelj_jung-j/](http://konect.cc/networks/subelj_jung-j/)), access date: 10 December 2023) and _subelj_jdk_ ([[http://konect.cc/networks/subelj_jdk/](http://konect.cc/networks/subelj_jdk/)]([http://konect.cc/networks/subelj_jdk/](http://konect.cc/networks/subelj_jdk/)), access date: 10 December 2023), and the results are shown in Figure 2. It is demonstrated that TCM performs poorly on edge query tasks, and the average relative error when querying light edges is extremely high. The average relative error dramatically increases with the increase in compression ratio (i.e., reducing the size of the graph sketch). Thus, a hash collision between a heavy edge and a light edge will result in an unacceptably high query error for the light edge, which is a major limitation of conventional graph sketches. To address the above issue, it is desirable to design a new graph sketch mechanism to resolve the high query error caused by hash collisions. (This paper is a significant extension of the conference paper published in [7]. In this paper, significant modifications have been made to improve the practicability of the research problem, enhance the solution framework and algorithm with rationale, and provide additional experimental results with detailed analysis.) In this paper, we propose a novel Dichotomy Graph Sketch (DGS) approach, which is able to differentiate heavy edges and light edges during the edge recording process and, respectively, store them in two separate matrices to avoid hash collisions. DGS first determines the type of edge by using the _edge classifier_ when a new edge arrives. If the edge is classified as a heavy edge, it will be stored in the _heavy sketch_; otherwise, it will be stored in the _light sketch_. In order to train the edge classifier, we utilize a _sample generator_ which is comprised of a temporal graph sketch and two min-heaps. At the end of each session, we obtain the heavy edges from the sample generator (see Section 4 for details) in order to train the edge classifier. In this way, the hash collision in Figure 1 can be avoided and the query performance can be improved. The main results and contributions of this paper are summarized as follows:  
* As a novel method for summarizing graph streams, we propose Dichotomy Graph Sketch (DGS). It is capable of distinguishing heavy edges from light edges during edge updating. * We adopt deep learning techniques in our graph sketch design. In particular, we design a novel neural network architecture to detect heavy edges during the edge updating process, which allows us to store heavy edges and light edges in two separate matrices.