# Summarizing Labeled Multi-Graphs

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jun 2022.

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

- [On the Detection of Reviewer-Author Collusion Rings From Paper Bidding](https://mlsanity.com/paper/2402.07860/) (2024)
- [ADAMM: Anomaly Detection of Attributed Multi-graphs with Metadata: A Unified Neural Network Approach](https://mlsanity.com/paper/2311.07355/) (2023)

## Abstract (arXiv)

Real-world graphs can be difficult to interpret and visualize beyond a certain size. To address this issue, graph summarization aims to simplify and shrink a graph, while maintaining its high-level structure and characteristics. Most summarization methods are designed for homogeneous, undirected, simple graphs; however, many real-world graphs are ornate; with characteristics including node labels, directed edges, edge multiplicities, and self-loops. In this paper we propose LM-Gsum, a versatile yet rigorous graph summarization model that (to the best of our knowledge, for the first time) can handle graphs with all the aforementioned characteristics (and any combination thereof). Moreover, our proposed model captures basic sub-structures that are prevalent in real-world graphs, such as cliques, stars, etc. LM-Gsum compactly quantifies the information content of a complex graph using a novel encoding scheme, where it seeks to minimize the total number of bits required to encode (i) the summary graph, as well as (ii) the corrections required for reconstructing the input graph losslessly. To accelerate the summary construction, it creates super-nodes efficiently by merging nodes in groups. Experiments demonstrate that LM-Gsum facilitates the visualization of real-world complex graphs, revealing interpretable structures and high- level relationships. Furthermore, LM-Gsum achieves better trade-off between compression rate and running time, relative to existing methods (only) on comparable settings.