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.
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.
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