  Network theory has proven to be a powerful tool in describing and analyzing
systems by modelling the relations between their constituent objects. In recent
years great progress has been made by augmenting `traditional' network theory.
However, existing network representations still lack crucial features in order
to serve as a general data analysis tool. These include, most importantly, an
explicit association of information with possibly heterogeneous types of
objects and relations, and a conclusive representation of the properties of
groups of nodes as well as the interactions between such groups on different
scales. In this paper, we introduce a collection of definitions resulting in a
framework that, on the one hand, entails and unifies existing network
representations (e.g., network of networks, multilayer networks), and on the
other hand, generalizes and extends them by incorporating the above features.
To implement these features, we first specify the nodes and edges of a finite
graph as sets of properties. Second, the mathematical concept of partition
lattices is transferred to network theory in order to demonstrate how
partitioning the node and edge set of a graph into supernodes and superedges
allows to aggregate, compute and allocate information on and between arbitrary
groups of nodes. The derived partition lattice of a graph, which we denote by
deep graph, constitutes a concise, yet comprehensive representation that
enables the expression and analysis of heterogeneous properties, relations and
interactions on all scales of a complex system in a self-contained manner.
Furthermore, to be able to utilize existing network-based methods and models,
we derive different representations of multilayer networks from our framework
and demonstrate the advantages of our representation. We exemplify an
application of deep graphs using a real world dataset of precipitation
measurements.
