  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.
