# Graph Summarization via Node Grouping: A Spectral Algorithm

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 51 references that are in the map.
- First posted on arXiv 8 Nov 2022.

## Builds on (most cited first, 11 of 11)

- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Multi-scale Attributed Node Embedding](https://mlsanity.com/paper/1909.13021/) (2019)
- [Network Embedding as Matrix Factorization: Unifying DeepWalk, LINE, PTE, and node2vec](https://mlsanity.com/paper/1710.02971/) (2017)
- [Characteristic Functions on Graphs: Birds of a Feather, from Statistical Descriptors to Parametric Models](https://mlsanity.com/paper/2005.07959/) (2020)
- [Exact Recovery in the Stochastic Block Model](https://mlsanity.com/paper/1405.3267/) (2014)
- [Partition and Code: learning how to compress graphs](https://mlsanity.com/paper/2107.01952/) (2021)
- [SSumM: Sparse Summarization of Massive Graphs](https://mlsanity.com/paper/2006.01060/) (2020)
- [Compressing Graphs and Indexes with Recursive Graph Bisection](https://mlsanity.com/paper/1602.08820/) (2016)
- [VoG: Summarizing and Understanding Large Graphs](https://mlsanity.com/paper/1406.3411/) (2014)
- [Incremental Lossless Graph Summarization](https://mlsanity.com/paper/2006.09935/) (2020)
- [Scalable Approximation Algorithm for Graph Summarization](https://mlsanity.com/paper/1806.03936/) (2018)

## Abstract (arXiv)

Graph summarization via node grouping is a popular method to build concise graph representations by grouping nodes from the original graph into supernodes and encoding edges into superedges such that the loss of adjacency information is minimized. Such summaries have immense applications in large-scale graph analytics due to their small size and high query processing efficiency. In this paper, we reformulate the loss minimization problem for summarization into an equivalent integer maximization problem. By initially allowing relaxed (fractional) solutions for integer maximization, we analytically expose the underlying connections to the spectral properties of the adjacency matrix. Consequently, we design an algorithm called SpecSumm that consists of two phases. In the first phase, motivated by spectral graph theory, we apply k-means clustering on the k largest (in magnitude) eigenvectors of the adjacency matrix to assign nodes to supernodes. In the second phase, we propose a greedy heuristic that updates the initial assignment to further improve summary quality. Finally, via extensive experiments on 11 datasets, we show that SpecSumm efficiently produces high-quality summaries compared to state-of-the-art summarization algorithms and scales to graphs with millions of nodes.