Incremental Lossless Graph Summarization

Jihoon Ko, Yunbum Kook, Kijung Shin

Abstract

As real-world graphs scale to billions of nodes and edges, efficient storage and analysis become critical. While lossless graph summarization offers a solution, existing batch-based algorithms are ill-suited for dynamic data streams where updates occur continuously. We present MoSSo, the first incremental algorithm for lossless graph summarization. MoSSo processes edge updates in near-constant time—up to seven orders of magnitude faster than state-of-the-art batch methods—by utilizing randomized sampling and coarse clustering to intelligently update supernode assignments.

Introduction

Graphs representing social networks, web links, and biological interactions are inherently dynamic. Lossless graph summarization reduces the footprint of these massive structures by grouping nodes into supernodes and edges into superedges, accompanied by a set of edge corrections to ensure perfect reconstruction. However, traditional summarization techniques are "batch" processes; even a single edge update necessitates re-running the entire algorithm, which is computationally prohibitive for high-velocity streams.

Overview of the lossless graph summarization problem and the symbols used in the MoSSo algorithm.

The MoSSo Framework

MoSSo (Move if Saved, Stay otherwise) addresses this limitation by incrementally updating the summary graph. Instead of global recomputation, MoSSo evaluates local moves for nodes affected by edge insertions or deletions. The efficiency of MoSSo stems from three core technical innovations:

  • Corrective Escape: To prevent the summary from converging to a poor local optimum, MoSSo periodically forces nodes into new supernodes. This stochastic "shaking" allows the algorithm to explore better configurations over time.
  • MCMC Sampling: High-degree nodes typically slow down summarization because evaluating their neighborhood is expensive. MoSSo employs Markov Chain Monte Carlo (MCMC) sampling to estimate the benefit of a move using only a small subset of neighbors, making update time independent of node degree.
  • Coarse Clustering: To identify the most beneficial supernode for a migrating node, MoSSo uses min-hashing-based coarse clustering. This quickly narrows down the search space to a few promising candidates.

Experimental Evaluation

MoSSo was evaluated against ten real-world datasets, including protein networks, email logs, and massive web graphs (e.g., Web-UK-02 with hundreds of millions of edges). The tests covered both insertion-only streams and fully dynamic streams involving edge deletions.

Performance and Scalability

The primary advantage of MoSSo is its unprecedented speed. It processes updates in less than 0.1 milliseconds on average, maintaining a near-constant update time regardless of the total graph size.

MoSSo achieves significantly lower execution times compared to batch algorithms like SAGS and SWeG.

Key findings include:

  • Speed: MoSSo is up to $10^7$ times faster than batch methods like SWeG and SAGS.
  • Scalability: The total runtime grows linearly with the number of changes, demonstrating excellent scalability for massive datasets.
  • Compression Efficiency: Despite its incremental nature, MoSSo maintains compression ratios competitive with state-of-the-art batch algorithms that process the entire graph at once.

Conclusion

MoSSo represents a significant leap in graph stream processing. By shifting from batch to incremental summarization, it enables real-time maintenance of compressed graph representations. Future research may extend these incremental principles to lossy summarization or more complex graph types, such as directed or weighted networks.

Summary updated

Abstract

Given a fully dynamic graph, represented as a stream of edge insertions and deletions, how can we obtain and incrementally update a lossless summary of its current snapshot? As large-scale graphs are prevalent, concisely representing them is inevitable for efficient storage and analysis. Lossless graph summarization is an effective graph-compression technique with many desirable properties. It aims to compactly represent the input graph as (a) a summary graph consisting of supernodes (i.e., sets of nodes) and superedges (i.e., edges between supernodes), which provide a rough description, and (b) edge corrections which fix errors induced by the rough description. While a number of batch algorithms, suited for static graphs, have been developed for rapid and compact graph summarization, they are highly inefficient in terms of time and space for dynamic graphs, which are common in practice. In this work, we propose MoSSo, the first incremental algorithm for lossless summarization of fully dynamic graphs. In response to each change in the input graph, MoSSo updates the output representation by repeatedly moving nodes among supernodes. MoSSo decides nodes to be moved and their destinations carefully but rapidly based on several novel ideas. Through extensive experiments on 10 real graphs, we show MoSSo is (a) Fast and 'any time': processing each change in near-constant time (less than 0.1 millisecond), up to 7 orders of magnitude faster than running state-of-the-art batch methods, (b) Scalable: summarizing graphs with hundreds of millions of edges, requiring sub-linear memory during the process, and (c) Effective: achieving comparable compression ratios even to state-of-the-art batch methods.
BibTeX
@misc{ko2020incremental,
  author = {Jihoon Ko and Yunbum Kook and Kijung Shin},
  title = {{Incremental Lossless Graph Summarization}},
  year = {2020},
  eprint = {2006.09935},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2006.09935},
}
Figure