Summarizing Labeled Multi-graphs

March 17, 2023

Dimitris Berberidis, Carnegie Mellon University
Pierre Jinghong Liang, Carnegie Mellon University
Leman Akoglu, Carnegie Mellon University

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 TG-sum, 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. Experiments demonstrate that TG-sum facilitates the visualization of real-world complex graphs, revealing interpretable structures and high-level relationships. Furthermore, TG-sum achieves better trade-off between compression rate and running time, relative to existing methods (only) on comparable settings.