# SSumM: Sparse Summarization of Massive Graphs

arXiv: https://arxiv.org/abs/2006.01060 · HTML: https://mlsanity.com/paper/2006.01060/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Jun 2020.

## Built on by (most cited first, 9 of 9)

- [APEX2: Adaptive and Extreme Summarization for Personalized Knowledge Graphs](https://mlsanity.com/paper/2412.17336/) (2024)
- [Unsupervised Matching of Data and Text](https://mlsanity.com/paper/2112.08776/) (2021)
- [Large Language Models for Cryptocurrency Transaction Analysis: A Bitcoin Case Study](https://mlsanity.com/paper/2501.18158/) (2025)
- [Causal DAG Summarization (Full Version)](https://mlsanity.com/paper/2504.14937/) (2025)
- [NeuKron: Constant-Size Lossy Compression of Sparse Reorderable Matrices and Tensors](https://mlsanity.com/paper/2302.04570/) (2023)
- [SkillZip: Contract-Preserving Graph Compression for Scalable Agent Skill Libraries](https://mlsanity.com/paper/2608.05604/) (2026)
- [Graph Summarization via Node Grouping: A Spectral Algorithm](https://mlsanity.com/paper/2211.04169/) (2022)
- [Balancing Summarization and Change Detection in Graph Streams](https://mlsanity.com/paper/2311.18694/) (2023)
- [CGS: Configurable Graph Summarization with Bounded Neighborhood Loss and Query Support](https://mlsanity.com/paper/2607.10969/) (2026)

## Abstract (arXiv)

Given a graph G and the desired size k in bits, how can we summarize G within k bits, while minimizing the information loss? Large-scale graphs have become omnipresent, posing considerable computational challenges. Analyzing such large graphs can be fast and easy if they are compressed sufficiently to fit in main memory or even cache. Graph summarization, which yields a coarse-grained summary graph with merged nodes, stands out with several advantages among graph compression techniques. Thus, a number of algorithms have been developed for obtaining a concise summary graph with little information loss or equivalently small reconstruction error. However, the existing methods focus solely on reducing the number of nodes, and they often yield dense summary graphs, failing to achieve better compression rates. Moreover, due to their limited scalability, they can be applied only to moderate-size graphs. In this work, we propose SSumM, a scalable and effective graph-summarization algorithm that yields a sparse summary graph. SSumM not only merges nodes together but also sparsifies the summary graph, and the two strategies are carefully balanced based on the minimum description length principle. Compared with state-of-the-art competitors, SSumM is (a) Concise: yields up to 11.2X smaller summary graphs with similar reconstruction error, (b) Accurate: achieves up to 4.2X smaller reconstruction error with similarly concise outputs, and (c) Scalable: summarizes 26X larger graphs while exhibiting linear scalability. We validate these advantages through extensive experiments on 10 real-world graphs.