  Graph summarization is beneficial in a wide range of applications, such as
visualization, interactive and exploratory analysis, approximate query
processing, reducing the on-disk storage footprint, and graph processing in
modern hardware. However, the bulk of the literature on graph summarization
surprisingly overlooks the possibility of having edges of different types. In
this paper, we study the novel problem of producing summaries of multi-relation
networks, i.e., graphs where multiple edges of different types may exist
between any pair of nodes. Multi-relation graphs are an expressive model of
real-world activities, in which a relation can be a topic in social networks,
an interaction type in genetic networks, or a snapshot in temporal graphs. The
first approach that we consider for multi-relation graph summarization is a
two-step method based on summarizing each relation in isolation, and then
aggregating the resulting summaries in some clever way to produce a final
unique summary. In doing this, as a side contribution, we provide the first
polynomial-time approximation algorithm based on the k-Median clustering for
the classic problem of lossless single-relation graph summarization. Then, we
demonstrate the shortcomings of these two-step methods, and propose holistic
approaches, both approximate and heuristic algorithms, to compute a summary
directly for multi-relation graphs. In particular, we prove that the
approximation bound of k-Median clustering for the single relation solution can
be maintained in a multi-relation graph with proper aggregation operation over
adjacency matrices corresponding to its multiple relations. Experimental
results and case studies (on co-authorship networks and brain networks)
validate the effectiveness and efficiency of the proposed algorithms.
