GS4: Graph stream summarization based on both the structure and semantics

Nowadays internet-based applications collect and distribute large datasets, which are mostly modeled by pertinent massive graphs. One solution to process such massive graphs is summarization. There are two kinds of graphs, stationary and stream. There are several algorithms to summarize stationary graphs; however, no comprehensive method has been devised to summarize stream graphs. This is because of the challenges of the graph stream, which are the high data volume and the continuous changes of data over time. To tackle such challenges, we propose a novel method based on the sliding window model that performs summarization using both the structure and vertex attributes of the input graph stream. We devise a new structure for a summary graph by considering the structural and semantical attributes that can better elucidate every heterogeneous summary graph. Moreover, our framework comprises innovative components for comparing hybrid summary graphs. To the best of our knowledge, this is the first method that summarizes a graph stream using both the structure and vertex attributes with varying contributions. Our approach also takes user directions and ontology into account. Aiming to study the efficiency and effectiveness of our proposed method, we conduct extensive experiments on two real-life datasets: American political web-logs and Amazon co-purchasing products. The experimental results confirm that compared to the existing approaches the proposed method generates graph summaries with better quality. The expected time of our proposed method in this paper (\(O(n^3)\)) has significantly enhanced the efficiency compared to the current best complexity which is \(O(n^5)\).