# Dichotomy Graph Sketch: Summarizing Graph Streams with High Accuracy Based on Deep Learning +
###### Abstract  
In many applications, data streams are indispensable to describe the relationships between nodes in networks, such as social networks, computer networks, and hyperlink networks. Fundamentally, a graph stream is a dynamic representation of a graph, which is usually composed of a sequence of edges, where each edge is represented by two endpoints and a weight. As a result of its large volume and highly dynamic nature, several graph sketches were proposed for the purposes of summarizing large-scale graph streams and enabling fast query processing. By using a compact data structure with hash functions, the graph sketches sequentially store the edges. Nevertheless, the existing graph sketches suffer from low performance on graph query tasks as a result of unpredictable collisions between heavy edges and light edges. To store heavy edges and light edges, this paper introduces a novel learning-based Dichotomy Graph Sketch (DGS) mechanism that uses two separate graph sketches, a _heavy sketch_ and a _light sketch_. During a graph stream session, DGS obtains heavy edges and light edges, and uses these edges as training samples for a deep neural network (DNN) based binary classifier. The DNN-based classifier is then used to determine whether the upcoming edges are heavy or not. We will store the edges that are classified as heavy edges in the heavy sketch, and those that are classified as light edges in the light sketch. By combining the learnable classifier and Dichotomy Graph Sketches, the proposed mechanism resolves the hashing collision problem in conventional graph sketches and significantly improves graph query accuracy. The DGS algorithm outperforms the state-of-the-art graph sketches in a variety of graph query tasks based on extensive experiments that were conducted on four real-world graph stream datasets. graph stream; graph stream summarization; sketch; graph sketch; deep learning +
Footnote †: 2023  
interactions form a dynamic graph. When new interactions occur, the social network graph will be dynamically updated. A graph stream, in formal terms, comprises a sequence of items, where each item represents an edge of the graph, usually represented by a tuple consisting of two endpoints and a weight. Due to the increasing size of graphs, it is necessary to build an accurate but small representation of the original graph so that analytics can be performed more efficiently. In order to accomplish this goal, researchers studied the _graph summarization_ problem in order to maintain the overall structure of the graph, while reducing its size. For example, [PERSON] et al. proposed a novel algorithm called SpecSumm [3] for graph summarization via node aggregation. Additionally, [PERSON] et al. have developed a utility-driven graph summarization method G-SCIS [4] that produces optimal compression with no loss of utility. They focused primarily on summarizing static graphs, which were incapable of handling dynamic graphs formed by graph streams. To this end, some researchers proposed _graph sketch_ as a way to summarize graph streams. For example, [PERSON] et al. proposed gSketch which utilized CM-sketch [5] to support edge query and aggregated subgraph query. In addition, [PERSON] et al. proposed a novel graph sketch called TCM [1]. Based on a hash function, TCM mapped each edge to a bucket in a matrix, and each bucket was assigned the edge weight. Since TCM kept topology information for the graph, it supported not only edge queries but also node queries. In a recent work, [PERSON] et al. proposed GSS [2], a method that combines an adjacency list buffer with a matrix to improve edge query accuracy. If a hash collision occurred in the matrix, then the adjacency list buffer stored the edge. Their follow-up study has been published in [6]. In this study, the matrix used in GSS was partitioned into multiple blocks, and the query was accelerated using bitmaps and FPGA (field-programmable gate array).