Learning-Based Dichotomy Graph Sketch for Summarizing Graph Streams with High Accuracy

Graph stream data is widely applied to describe the relationships in networks such as social networks, computer networks and hyperlink networks. Due to the large volume and high dynamicity of graph streams, several graph sketches were proposed to summarize them for fast queries. However, the existing graph sketches suffer from low performance on graph query tasks due to hash collisions between heavy and light edges. In this paper, we propose a novel learning-based Dichotomy Graph Sketch (DGS) mechanism, which adopts two separate graph sketches, a heavy sketch and a light sketch, to store heavy edges and light edges respectively. DGS periodically obtains heavy edges and light edges in a session of a graph stream, and use them as training samples to train a deep neural network (DNN) based binary classifier. The DNN-based classifier is then utilized to decide whether the upcoming edges are heavy or not, and store them in different graph sketches accordingly. With the learnable classifier and the dichotomy graph sketches, the proposed mechanism can resolve the hashing collision problem and significantly improve the accuracy for graph query tasks. We conducted extensive experiments on three real-world graph stream datasets, which show that DGS outperforms the state-of-the-art graph sketches in a variety of graph query tasks.