# VoG: Summarizing and Understanding Large Graphs

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Jun 2014.

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

- [Partition and Code: learning how to compress graphs](https://mlsanity.com/paper/2107.01952/) (2021)
- [Graph Similarity Description: How Are These Graphs Similar?](https://mlsanity.com/paper/2105.14364/) (2021)
- [Graph Summarization via Node Grouping: A Spectral Algorithm](https://mlsanity.com/paper/2211.04169/) (2022)
- [KG-MDL: Mining Graph Patterns in Knowledge Graphs with the MDL Principle](https://mlsanity.com/paper/2309.12908/) (2023)
- [CGS: Configurable Graph Summarization with Bounded Neighborhood Loss and Query Support](https://mlsanity.com/paper/2607.10969/) (2026)

## Abstract (arXiv)

How can we succinctly describe a million-node graph with a few simple sentences? How can we measure the "importance" of a set of discovered subgraphs in a large graph? These are exactly the problems we focus on. Our main ideas are to construct a "vocabulary" of subgraph-types that often occur in real graphs (e.g., stars, cliques, chains), and from a set of subgraphs, find the most succinct description of a graph in terms of this vocabulary. We measure success in a well-founded way by means of the Minimum Description Length (MDL) principle: a subgraph is included in the summary if it decreases the total description length of the graph. Our contributions are three-fold: (a) formulation: we provide a principled encoding scheme to choose vocabulary subgraphs; (b) algorithm: we develop method, an efficient method to minimize the description cost, and (c) applicability: we report experimental results on multi-million-edge real graphs, including Flickr and the Notre Dame web graph.