  Graph compression is a data analysis technique that consists in the
replacement of parts of a graph by more general structural patterns in order to
reduce its description length. It notably provides interesting exploration
tools for the study of real, large-scale, and complex graphs which cannot be
grasped at first glance. This article proposes a framework for the compression
of temporal graphs, that is for the compression of graphs that evolve with
time. This framework first builds on a simple and limited scheme, exploiting
structural equivalence for the lossless compression of static graphs, then
generalises it to the lossy compression of link streams, a recent formalism for
the study of temporal graphs. Such generalisation relies on the natural
extension of (bidimensional) relational data by the addition of a third
temporal dimension. Moreover, we introduce an information-theoretic measure to
quantify and to control the information that is lost during compression, as
well as an algebraic characterisation of the space of possible compression
patterns to enhance the expressiveness of the initial compression scheme. These
contributions lead to the definition of a combinatorial optimisation problem,
that is the Lossy Multistream Compression Problem, for which we provide an
exact algorithm.
