A Notion of Entropy for Sparse Marked Graphs and its Applications in Graphical Data Compression

Many modern data sources arising from social networks, biological data, etc. are best viewed as being represented by combinatorial structures such as graphs, rather than time series. The local weak limit theory for sparse graphs, also known as the objective method, provides a framework which enables one to make sense of a stationary stochastic process for sparse graphs. The theory of time series is the engine driving an enormous range of applications in areas such as control theory, communications, information theory and signal processing. It is to be expected that a theory of stationary stochastic processes for combinatorial structures, in particular graphs, would eventually have a similarly wide-ranging impact. Employing the above framework, we introduce a notion of entropy for probability distributions on rooted graphs. This is a generalization of the notion of entropy introduced by Bordenave and Caputo to graphs which carry marks on their vertices and edges. The above notion of entropy can be considered as a natural counterpart for the Shannon entropy rate in the world of graphical data. We illustrate this by introducing a universal compression scheme for marked graphical data. We also discuss a low complexity universal compression algorithm for marked graphical data. Furthermore, we will discuss an extension of this approach to a more general sparsity regime that also takes into account heavy-tailed sparse graphs in which the number of edges in the graph scales super linearly with the number of vertices. In order to do this, we employ the sparse graphon framework as well as an appropriate notion of entropy for this framework. Using this, we introduce a universal lossless compression method which is simultaneously applicable to both sparsity regimes, namely the local weak convergence regime and the sparse graphon regime.