text:
\section{Introduction}
In many data science applications, data appears in the form of large-scale graphs. For example, in social networks, vertices represent users and an edge between vertices represents friendship; in the World Wide Web, vertices are websites and edges indicate the hyperlinks from one site to the other; in biological systems, vertices can be proteins and edges illustrate protein-to-protein interaction. Such graphs may contain billions of vertices. In addition, edges tend to be correlated with each other since, for example, two people sharing many common friends are likely to be friends as well. How to efficiently compress such large-scale structural information to reduce the I/O and communication costs in storing and transmitting such data is a persisting  challenge in the era of big data.

The literature on graph compression is vast. Existing compression schemes follow various different methodologies. Several methods exploited combinatorial properties such as cliques and cuts in the graph~\cite{Rossi--Zhou2018,Lim--Kang--Faloutsos2014}. Many works targeted at domain-specific graphs such as web graphs~\cite{Boldi--Vigna2004}, biology networks~\cite{Conway--Thomas--Bromage--Andrew2011,Hayashida--Akutsu2010}, and social network graphs~\cite{Chierichetti--Kumar--Lattanzi--Mitzenmacher--Panconesi--Raghavan2009}. Various representations of graphs were proposed, such as the text-based method, where the neighbor list of each vertex is treated as a ``word''~\cite{Navarro2007,Sadakane2003}, and the $k^2$-tree method, where the adjacency matrix is recursively partitioned into $k^2$ equal-size submatrices~\cite{Brisaboa--Ladra--Navarro2009}.  \emph{Succinct} graph representations that enable certain types of fast computation, such as adjacency query or vertex degree query, were also widely studied~\cite{Farzan--Munro2013}. While most compression schemes are for labeled graphs, there are also works considering lossless compression of unlabeled graphs~\cite{Turan1984,Naor1990,Choi--Szpankowski2012}, graphs with marks on its edges and vertices~\cite{Delgosha--Anatharam2017,Delgosha--Anatharam2019, Delgosha--Anatharam2020},
or (correlated) data on the graph~\cite{Abbe16,Asadi--Abbe--Verdu2017}. We refer the readers to~\cite{Besta--Hoefler2018} for an exhaustive survey on lossless graph compression and space-efficient graph representations.

In this paper, we take an information theoretic approach to study lossless compression of a graph. We assume the graph is generated by some random graph model and investigate lossless compression schemes that achieve the theoretical limit, i.e., the entropy of the graph, asymptotically as the number of vertices goes to infinity. When the underlying distribution/statistics of the random graph model is known, optimal lossless compression can be achieved by methods like Huffman coding. However, in most real-world applications, the exact distribution is usually hard to obtain and the data we are given is a single realization of this distribution. This motivates us to consider the framework of \emph{universal compression}, in which we assume the underlying distribution belongs to a known family of distributions and require that the encoder and the decoder should not be a function of the underlying distribution. The goal of universal compression is to design a single compression scheme that universally achieves the optimal theoretical limit, for every distribution in the family, without knowing which distribution generates the data. For this paper, we focus on the family of \emph{stochastic block models}, which are widely used random graph models that capture the clustering effect in social networks. Our goal is to develop a universal graph compression scheme for a family of stochastic block models with as wide range of parameters as possible.

How to design computationally efficient universal compression scheme is a fundamental question in information theory. In the past several decades, a large number of universal compressors were proposed for one-dimensional sequences with fixed alphabet size, whose entropy is linear in the number of variables. Prominent results include the Laplace  and Krichevsky--Trofimov (KT) compressors for i.i.d.\! processes~\cite{Xie--Barron00a, Xie--Barron00b}, Lempel--Ziv compressor~\cite{Lempel--Ziv77,Lempel--Ziv78} and Burrows--Wheeler transform\cite{effros2002universal} for stationary ergodic processes, and context tree weighting~\cite{willems1995context} for finite memory processes. Many of these have been adopted in standard data compression applications such as \texttt{compress}, gzip, GIF, TIFF, and bzip2. Despite these exciting developments, existing universal compression techniques fall short of establishing optimality results for graph data due to the following challenges. Firstly, graph data generated from a stochastic block model has non-stationary two-dimensional correlation, so existing techniques do not immediately apply here. Secondly, in many practical applications, where the graph is sparse, the entropy of the graph may be sublinear in the number of entries in the adjacency matrix.

For the first challenge, a natural question arising is: can we convert the two-dimensional adjacency matrix of the graph into a one-dimensional sequence in some order and apply a universal compressor for the sequence? For some simple graph model such as Erd\H os--R\'enyi  graph, where each edge is generated i.i.d.\! with probability $p$, this would indeed work. For more complex graph models including stochastic block models, it is unclear whether there is an ordering of the entries that results in a stationary process. We will show in Section~\ref{sec:C1discussion} several orders including row-by-row, column-by-column, and diagonal-by-diagonal fail to produce a stationary process. We alleviate this challenge by designing a decomposition of the adjacency matrix into blocks. We then show in Theorem~\ref{prop:blkIndep} that with a carefully chosen parameter, the block decomposition converts two-dimensional correlated entries into a sequence of \emph{almost} i.i.d.\! blocks with slowly growing alphabet size. To address the second challenge, we adjust the standard definition of universality, which normalizes the compression length by the number of variables. The new definition of universality accommodates data with unknown leading order in its entropy expression.

Lossless compression for stochastic block models was first studied by Abbe~\cite{Abbe16} (albeit not under the universal compression framework). The focus there is two-fold: 1) compute the entropy of the stochastic block model; 2) explore the relation between community detection and compression. Several interesting questions were presented: Knowing the community assignments will help compression since edges can be grouped into i.i.d.\! subsets. But is community detection necessary for compression? In the regime when community detection is not possible, how do we compress the graph? We answer these questions in this paper by presenting a universal compressor that does not require knowledge of the edge probabilities, the community assignments, or the number of communities. Our compressor remains universal even in the regime when community detection is information theoretically impossible. As a consequence, universal compression is a fundamentally easier task than community detection for stochastic block models.

Recently, universal compression of graphs with marked edges and vertices is studied by Delgosha and Anantharam~\cite{Delgosha--Anatharam2019tit,Delgosha--Anatharam2020}. They focus on the \emph{sparse} graph regime, where the number of edges is in the same order as the number of vertices $n$. They employ the framework of local weak convergence, which provides a technique to view a sequence of graphs as a sequence of distributions on neighbourhood structures. Built on this framework, they propose an algorithm that compresses graphs by describing the local neighbourhood structures. Moreover, they introduce a universality/optimality criterion through a notion of entropy for graph sequences under the local weak convergence framework, known as the \emph{BC entropy}~\cite{Bordenave_2014}. This universality criterion is stronger than the one used in this paper. It requires the asymptotic length of the compressor to match the constants in both first and second order terms in Shannon entropy, whereas the universality criterion we use only requires to match the first order term. As a consequence of the stronger criterion, the compressor in~\cite{Delgosha--Anatharam2019tit} is universal over a smaller random graph family. In comparison, we expand the range of edge numbers from $\Theta(n)$ in the sparse regime to $\Theta(n^\alpha)$ for every $0< \alpha \le 2$ and propose a single universal compressor for the whole family under the weaker universality criterion. In Section~\ref{sec:BCentropy}, we evaluate the proposed compressor  under the criterion in~\cite{Delgosha--Anatharam2019tit} for the family of \emph{symmetric} SBMs. The proposed compressor achieves a similar performance in terms of BC entropy in the sparse regime.

The rest of the paper is organized as follows. In Section~\ref{sec:setup}, we define universality over a family of graph distributions and the stochastic block models. We present our main result in Section~\ref{sec:main}, which is a graph compressor that is universal for a family containing most non-trivial stochastic block models. We describe  the proposed graph compressor in Section~\ref{sec:univGraphComp}.  We illustrate key steps in establishing universality in Section~\ref{sec:theorem} and elaborate the proof of each step in Section~\ref{sec:proposition}. In Section~\ref{sec:BCentropy}, we provide the second order analysis of the expected length of our compressor and compare it to the one in~\cite{Delgosha--Anatharam2019tit} In Section~\ref{sec:C1discussion}, we explain why existing universal compressors developed for stationary processes may not be immediately applicable for some one-dimensional ordering of entries in the adjacency matrix. In Section~\ref{sec:experiments}, we implement our compressor in four benchmark graph datasets and compare its empirical performance to four competing algorithms.

{\bf Notation.}
For an integer $n$, let $[n] = \{1,2,\ldots,n\}$. Let $\log(\cdot) = \log_2(\cdot)$. We follow the standard order notation: $f(n) = O(g(n))$ if $\lim_{n \to \infty} \frac{|f(n)|}{g(n)} < \infty$; $f(n) = \Omega(g(n))$ if $\lim_{n \to \infty}\frac{f(n)}{g(n)} >0$; $f(n) = \Theta(g(n))$ if $f(n) = O(g(n))$ and $f(n) = \Omega(g(n))$; $f(n) = o(g(n))$ if $\lim_{n \to \infty}\frac{f(n)}{g(n)} = 0$; $f(n) = \omega(g(n))$ if $\lim_{n \to \infty}\frac{|f(n)|}{|g(n)|} = \infty$; and $f(n) \sim g(n)$ if $\lim_{n \to \infty}\frac{f(n)}{g(n)} = 1$.

\subsection{Problem Setup}\label{sec:setup}
For simplicity, we focus on simple (undirected, unweighted, no self-loop) graphs with labeled vertices in this paper. But our compression scheme and the corresponding analysis can be extended to more general graphs. Let $\mathcal{A}_n$ be the set of all labeled simple graphs on $n$ vertices. Let $\{0,1\}^i$ be the set of binary sequences of length $i$, and set $\{0,1\}^* = \cup_{i=0}^\infty\{0,1\}^i$. A lossless graph compressor $C\mathchoice{\colon}{\colon}{:\mspace{1mu}}{:} \mathcal{A}_n \to \{0,1\}^*$ is a one-to-one function that maps a graph to a binary sequence. Let $\ell(C(A_n))$ denote the length of the output sequence. When $A_n$ is generated from a distribution, it is known that the entropy $H(A_n)$  is a fundamental lower bound on the expected length of any lossless compressor~\cite[Theorem 8.3]{Polyanskiy--Wu14}
\begin{align}\label{eq:losslessLB}
    H(A_n)-\log(e(H(A_n)+1)) \le {\mathsf E}[\ell(C(A_n))],
\end{align}
and therefore
\[
 \liminf_{n \to \infty}\frac{{\mathsf E}[\ell(C(A_n))]}{H(A_n)} \ge 1.
\]
Thus, a graph compressor is said to be \emph{universal} for the family of distributions $\mathscr{P}$ if for all distribution ${\mathsf P} \in \mathscr{P}$ and $A_n \sim {\mathsf P}$, we have
\begin{equation}
 \limsup_{n \to \infty}\frac{{\mathsf E}[\ell(C(A_n))]}{H(A_n)} = 1.
\end{equation}

A stochastic block model $\mathrm{SBM}(n,L,{\bf p},{\bf W})$ defines a probability distribution over $\mathcal{A}_n$. Here $n$ is the number of vertices, $L$ is the number of communities. Each vertex $i \in [n]$ is associated with a community assignment $X_i \in [L]$. The length-$L$ column vector ${\bf p}=(p_1,p_2,\ldots,p_L)^T$ is a probability distribution over $[L]$, where $p_i$ indicates the probability that any vertex is assigned community $i$. ${\bf W}$ is an $L\times L$ symmetric matrix, where $W_{ij}$ represents the probability of having an edge between a vertex with community assignment $i$ and a vertex with community assignment $j$. We say $A_n \sim \mathrm{SBM}(n,L,{\bf p},{\bf W})$ if the community assignments $X_1,X_2,\ldots,X_n$ are generated i.i.d.\! according to ${\bf p}$ and for every pair $1 \le  i<j \le n$, an edge is generated between vertex $i$ and vertex $j$ with probability $W_{X_i,X_j}$. In other words, in the adjacency matrix $A_n$ of the graph, $A_{ij} \sim \mathrm{Bern}(W_{X_i,X_j})$ for $i <j$; the diagonal entries $A_{ii} = 0$ for all $i \in [n]$; and $A_{ij} = A_{ji}$ for $i > j$. We assume all the entries in ${\bf W}$ are in the same regime $f(n)$ and write ${\bf W} = f(n){\bf Q}$, where ${\bf Q}$ is an $L\times L$ symmetric matrix with constant entries $Q_{ij} = \Theta(1)$ for all $i,j \in [L]$. We assume all entries in ${\bf p}$ are $\Theta(1)$. We will consider two families of stochastic block models: For $0 < \epsilon < 1$,
\begin{align}
 \mathscr{P}_1(\epsilon)&\mathchoice{\colon}{\colon}{:\mspace{1mu}}{:} \mathrm{SBM} \text{ with } L = \Theta(1), f(n) = O(1), f(n)= \Omega\left(\tfrac{1}{n^{2-\epsilon}}\right),\label{eq:P1family}\\
 \mathscr{P}_2(\epsilon)&\mathchoice{\colon}{\colon}{:\mspace{1mu}}{:} \mathrm{SBM} \text{ with } L = \Theta(1), f(n) = o(1), f(n)= \Omega\left(\tfrac{1}{n^{2-\epsilon}}\right).\label{eq:P2family}
\end{align}
Note that the edge probability $\frac{1}{n^2}$ is the threshold for a random graph to contain an edge with high probability~\cite{Frieze--Karonski2015}. Thus, the family $\mathscr{P}_1(\epsilon)$ covers most non-trivial SBM graphs. Clearly, $\mathscr{P}_2(\epsilon)$ is a strict subset of $\mathscr{P}_1(\epsilon)$, as it does not contain the constant regime $f(n) = 1$.

\subsection{Main Results}\label{sec:main}
The main contribution of this paper is providing two compressors universal over the classes  $\mathscr{P}_1(\epsilon)$ and  $\mathscr{P}_2(\epsilon)$ respectively for $0 < \epsilon < 1$. Note that a compressor universal over the class $ \mathscr{P}_1(\epsilon)$ is also universal over the class  $\mathscr{P}_2(\epsilon)$, but our compressor designed specifically for the class  $\mathscr{P}_2(\epsilon)$ has a lower computational complexity. We will formally state the results in the next two theorems.
\begin{thm}[Universality over $\mathscr{P}_1$]\label{thm:strongUniv}
For every $0 < \epsilon < 1$, the graph compressor $C_k$ defined in Section~\ref{sec:univGraphComp} is universal over the family $\mathscr{P}_1(\epsilon)$ provided that
 \[
 0 < \delta < \epsilon, \quad k \le \sqrt{\delta \log n}, \quad \text{ and } \quad k = \omega(1).
 \]
\end{thm}

\begin{thm}[Universality over $\mathscr{P}_2$]\label{thm:weakUniv}
For every $0 < \epsilon < 1$, the graph compressor $C_1$ defined in Section~\ref{sec:univGraphComp} is universal over the family $\mathscr{P}_2(\epsilon)$.
\end{thm}

For now, one can think of $k$ as a parameter that defines a compression scheme $C_k$—the exact definition will become clear in the next section when we precisely define the compressors.

\section{Algorithm: Universal Graph Compressor}\label{sec:univGraphComp}
In this section, we describe our universal graph compression scheme.
For each $k$ that divides $n$, the graph compressor $C_k\mathchoice{\colon}{\colon}{:\mspace{1mu}}{:} \mathcal{A}_n \to \{0,1\}^*$ is defined as follows.
\begin{itemize}
 \item {\bf Block decomposition.}
Let $n' = \frac{n}{k}$. For $1 \le i,j \le n'$, let ${\bf B}_{ij}$ be the submatrix of $A_n$ formed by the rows $(i-1)k + 1, (i-1)k + 2, \ldots, ik$ and the columns $(j-1)k + 1, (j-1)k + 2, \ldots, jk$. For example, we have
\begin{equation}\label{eq:B12}
{\bf B}_{12} = \begin{bmatrix}
A_{1, k +1} & A_{1, k + 2} & \cdots & A_{1, 2k}\\
A_{2, k +1} & A_{2, k + 2} & \cdots & A_{2, 2k}\\
\vdots & \vdots & \ddots & \vdots\\
A_{k, k +1} & A_{k, k +2} & \cdots & A_{k, 2k}
\end{bmatrix}.
\end{equation}
We then write $A_n$ in the block-matrix form as
\begin{equation}\label{eq:blockMatrix}
A_n =
\begin{bmatrix}
{\bf B}_{11} & {\bf B}_{12} & \cdots & {\bf B}_{1,n'}\\
{\bf B}_{21} & {\bf B}_{22} & \cdots & {\bf B}_{2,n'}\\
\vdots & \vdots & \ddots & \vdots\\
{\bf B}_{n',1} & {\bf B}_{n',2} & \cdots & {\bf B}_{n',n'}
\end{bmatrix}.
\end{equation}
Denote
\begin{align}\label{eq:ButDefn}
{\bf B}_{\mathrm{ut}} \coloneqq {\bf B}_{12},{\bf B}_{13},{\bf B}_{23},{\bf B}_{14},{\bf B}_{24},{\bf B}_{34},\ldots,{\bf B}_{1,n'},\cdots,{\bf B}_{n'-1,n'}
\end{align}
as the sequence of off-diagonal blocks in the upper triangle and
\begin{align}\label{eq:BdiagDefn}
{\bf B}_{\mathrm{d}} \coloneqq {\bf B}_{11},{\bf B}_{22},\ldots, {\bf B}_{n',n'}
\end{align}
as the sequence of diagonal blocks.

\item {\bf Binary to $m$-ary conversion.} Let $m := 2^{k^2}$. Each $k \times k$ block with binary entries in the two block sequences ${\bf B}_{\mathrm{ut}}$ and ${\bf B}_{\mathrm{d}}$ is converted into a symbol in $[m]$.

\item {\bf KT probability assignment.} Apply KT sequential probability assignment for the two $m$-ary sequences ${\bf B}_\mathrm{ut}$ and ${\bf B}_\mathrm{d}$ respectively. Given an $m$-ary sequence $x_1,x_2,\ldots,x_N$, \emph{KT sequential probability assignment} defines $N$ conditional probability distributions over $[m]$ as follows. For $j = 0,1,2,\ldots,N-1$, assign conditional probability
\begin{equation}\label{eq:KTProbAssgnSeq}
 q_{\mathrm{KT}}(i|x^j) \coloneqq q_{\mathrm{KT}}(X_{j+1} = i| X^j = x^j) = \frac{N_i(x^j) + 1/2 }{j + m/2} \quad \text{ for each } i \in [m],
\end{equation}
where $X^j \coloneqq (X_1,\ldots,X_j), x^j \coloneqq (x_1,x_2,\ldots,x_j)$, and $N_i(x^j) \coloneqq \sum_{k=1}^j \mathbbm{1}\{x_k = i\}$ counts the number of symbol $i$ in $x^j$.

\item {\bf Adaptive arithmetic coding.} With the KT sequential probability assignments, compress the two sequences ${\bf B}_\mathrm{ut}$ and ${\bf B}_\mathrm{d}$ separately using adaptive arithmetic coding~\cite{Marpe--Schwarz--Wiegand2003} (see description in Algorithm~\ref{alg:arithmetic}).  In case $k = 1$, the diagonal sequence ${\bf B}_\mathrm{d}$ becomes an all-zero sequence since we assume the graph is simple. So we will only compress the off-diagonal sequence ${\bf B}_\mathrm{ut}$.

\begin{algorithm}
\SetKwInOut{Input}{Input}\SetKwInOut{Output}{Output}
\Input{Data sequence $x^N$, alphabet size $m$}
\BlankLine
Initialize $\texttt{lower}=0, \texttt{upper}=1, \texttt{logprob}=0, N_1 = N_2 = \cdots = N_m = 0$\;
\For{$j = 0,1,\ldots,N-1$}{
$\texttt{range} \leftarrow \texttt{upper}-\texttt{lower}$\;
\For{$i = 1,2,\ldots,x_{j+1}$}{
Compute $q_\mathrm{KT}(i|x^j) = \frac{N_i+1/2}{j+m/2}$\;
}
$\texttt{upper} \leftarrow \texttt{lower} + \texttt{range}\cdot\sum_{i=1}^{x_{j+1}}q_{\mathrm{KT}}(i|x^j)$\;
$\texttt{lower} \leftarrow \texttt{upper} - \texttt{range}\cdot q_{\mathrm{KT}}(x_{j+1}|x^j)$\;
$N_{x_{j+1}} \leftarrow N_{x_{j+1}} + 1$\;
$\texttt{logprob} \leftarrow \texttt{logprob} + \log(q_{\mathrm{KT}}(x_{j+1}|x^j))$\;
}
\BlankLine
\Output{the binary representation of $\frac{1}{2}(\texttt{lower}+\texttt{upper})$ with $\lceil-\texttt{logprob}\rceil + 1$ bits}
 \caption{$m$-ary adaptive arithmetic encoding with KT probability assignment}\label{alg:arithmetic}
\end{algorithm}
\end{itemize}

Given the compressed graph sequence $y^L$, the number of vertices $n$ and the block size $k$, the graph decompressor $D_k\mathchoice{\colon}{\colon}{:\mspace{1mu}}{:} \{0,1\}^* \to \mathcal{A}_n$ is defined as follows.
\begin{itemize}
\item {\bf Adaptive arithmetic decoding.} With the KT sequential probability assignments defined in~\eqref{eq:KTProbAssgnSeq}, decompress the two code sequences for ${\bf B}_\mathrm{ut}$ and ${\bf B}_\mathrm{d}$ separately using adaptive arithmetic decoding (see Algorithm~\ref{alg:arithmeticDec}). The length of data sequence ${\bf B}_\mathrm{ut}$ and ${\bf B}_\mathrm{d}$ are $\frac{n}{k}(\frac{n}{k}-1)/2$ and $\frac{n}{k}$ respectively.
\begin{algorithm}
\SetKwInOut{Input}{Input}\SetKwInOut{Output}{Output}
\Input{Binary sequence $y^L$, alphabet size $m=2^{k^2}$, length of data sequence $N$}
\BlankLine
Add `$0.$' before sequence $y^L$ and convert it into a decimal real number $Y$. Initialize $\texttt{lower}=0, \texttt{upper}=1, N_1 = N_2 = \cdots = N_m = 0$\;
\For{$j = 0,1,\ldots,N-1$}{
$\texttt{range} \leftarrow \texttt{upper}-\texttt{lower}$\;
\For{$i = 1,2,\ldots,m$}{
Compute $q_\mathrm{KT}(i|x^j) = \frac{N_i+1/2}{j+m/2}$\;
}
Find minimum $z\in[m]$ such that $\texttt{lower}+\texttt{range}\cdot \sum_{i=1}^{z} q_\mathrm{KT}(i|x^j)>Y $\;
$\texttt{upper} \leftarrow \texttt{lower} + \texttt{range}\cdot\sum_{i=1}^{z}q_{\mathrm{KT}}(i|x^j)$\;
$\texttt{lower} \leftarrow \texttt{upper} - \texttt{range}\cdot q_{\mathrm{KT}}(z|x^j)$\;
$N_{z} \leftarrow N_{z} + 1$\;
$x_{j+1} \leftarrow z$\;

}
\BlankLine
\Output{the $m$-ary data sequence $x_1,x_2,\cdots,x_N$}
 \caption{$m$-ary adaptive arithmetic decoding with KT probability assignment}\label{alg:arithmeticDec}
\end{algorithm}
 \item {\bf $m$-ary to binary conversion.} Each $m$-ary symbol in the sequence is converted to a $k^2$-bit binary number and further converted into a $k\times k$ block with binary entries.
 \item {\bf Adjacency matrix recovery.} With the blocks in ${\bf B}_\mathrm{ut}$ and ${\bf B}_\mathrm{d}$, recover the adjacency matrix of $A_n$ in the order described in~\eqref{eq:blockMatrix},~\eqref{eq:ButDefn}, and~\eqref{eq:BdiagDefn}.

\end{itemize}

One can check that $C_k$ is well-defined. The block decomposition and the binary to $m$-ary conversion are clearly one-to-one. It is also known that for any valid probability assignment, arithmetic coding produces a prefix code, which as also one-to-one.

The computational complexity of the proposed algorithm is $O(2^{k^2}n^2)$. For the choice of $k$ that achieves universality over $\mathscr{P}_1(\epsilon)$ family in Theorem~\ref{thm:strongUniv}, $O(2^{k^2}n^2) = O(n^{2+\delta})$ for $\delta < \epsilon$. For the choice of $k$ that achieves universality over $\mathscr{P}_2(\epsilon)$ family in Theorem~\ref{thm:weakUniv}, $O(2^{k^2}n^2) = O(n^2)$.

The orders in ${\bf B}_\mathrm{ut}$ and ${\bf B}_\mathrm{d}$ do not matter in terms of establishing universality. The current orders in~\eqref{eq:ButDefn} and~\eqref{eq:BdiagDefn} together with arithmetic coding enable a \emph{horizon free} implementation. That is, the encoder does not need to know the \emph{horizon} $n$ to start processing the data and can output partial coded bits \emph{on the fly} before receiving all the data. This leads to short encoding and decoding delay. For some real-world applications, for example, when the number of users increases in a large social network, this compressor has the advantage of not requiring to re-process existing data and re-compress the whole graph from scratch.

\begin{rem}[{\bf Laplace probability assignment}]\label{rmk:Laplace}
 As an alternative to the KT sequential probability assignment, one can also use the Laplace sequential probability assignment. Given an $m$-ary sequence $x_1,x_2,\ldots,x_N$, \emph{Laplace sequential probability assignment} defines $N$ conditional probability distributions over $[m]$ as follows. For $j = 0,1,2,\ldots,N-1$, we assign conditional probability
\begin{equation}\label{eq:LaplaceProbAssgnSeq}
 q_{\mathrm{L}}(X_{j+1} = i| X^j = x^j) = \frac{N_i(x^j) + 1 }{j + m} \quad \text{ for each } i \in [m].
\end{equation}
Both methods can be shown to be universal, while Laplace probability assignment has a much cleaner derivation. However, KT probability assignment produces a better empirical performance. For this reason, we keep both in the paper.
\end{rem}

\section{Main Ideas in Establishing Universality}\label{sec:theorem}
In this section, we establish the universality of the graph compressor in Section~\ref{sec:univGraphComp}.
\paragraph{Graph Entropy}
We first calculate the entropy of the (random) graph $A_n$, which, recall, is the fundamental lower bound on the expected compression length for any compression scheme. Since to establish optimality we need to show that $ \limsup_{n \to \infty}\frac{{\mathsf E}[\ell(C(A_n))]}{H(A_n)} \le 1$, we will only be concerned with the first order term in $H(A_n)$.
\begin{lem}[Graph entropy]\label{prop:graphEntropy}
 Let $A_n \sim \text{SBM}(n,L,{\bf p},f(n){\bf Q})$ with $f(n) = O(1), f(n) = \Omega\left(\frac{1}{n^2}\right)$, and $L = \Theta(1)$. For $0 \le p \le 1$, let $h(p) \triangleq -p\log(p) - (1-p) \log(1-p)$ denote the binary entropy function. For a matrix $W$ with entries in $[0,1]$, let $h(W)$ be a matrix of the same dimension whose $(i,j)$ entry is $h(W_{ij})$. Then
 {\allowdisplaybreaks
 \begin{align}
  \label{eq:graphEntropy}
  H(A_n) &= {n \choose 2} H(A_{12}|X_1,X_2) (1+o(1))\\
  &= {n \choose 2}{\bf p}^T h\bigl(f(n){\bf Q}\bigr) {\bf p} + o\left(n^2h\bigl(f(n)\bigr)\right).\label{eq:graphEntropy2}
 \end{align}}%
In particular, when $f(n) = \Omega\left(\frac{1}{n^2}\right)$ and $f(n) = o(1)$, expression~\eqref{eq:graphEntropy2} can be further simplified as
\begin{equation}
 \label{eq:graphEntropyo(1)}
  H(A_n) =  {n \choose 2} f(n)\log\left(\frac{1}{f(n)}\right)({\bf p}^T{\bf Q}{\bf p} + o(1)).
\end{equation}
\end{lem}
\begin{rem}
 In the regime $f(n) = \Omega\left(\frac{1}{n}\right)$ and $f(n) = O(1)$, the above result has been established in~\cite{Abbe16}. We extend the analysis to the regime $f(n) = o\left(\frac{1}{n}\right)$ and $f(n) = \Omega(\frac{1}{n^2})$.
\end{rem}

\begin{rem}
 Lemma~\ref{prop:graphEntropy} can be used to calculate the entropy of the graph for certain important regimes of $f(n)$, in which the SBM displays characteristic behavior. For $f(n) = 1$, we have $H(A_n) = {n \choose 2}h\left({\bf p}^T {\bf Q} {\bf p}\right)(1 + o(1))$; for $f(n) = \frac{\log n}{n}$ (the regime where the phase transition for exact recovery of the community assignments occurs~\cite{Abbe--Bandeira--Hall15, Abbe--Sandon15}), we have $H(A_n) = \frac{ n \log ^2 n}{2}({\bf p}^T {\bf Q} {\bf p}  + o(1))$; when $f(n) = \frac{1}{n}$ (the regime where the phase transition  for detection between SBM and the Erd\H os--R\'enyi  model occurs~\cite{Mossel--Neeman--Sly15}), we have $H(A_n) = \frac{n \log n}{2}({\bf p}^T {\bf Q} {\bf p}  + o(1))$; when $f(n) = \frac{1}{n^2}$ (the regime where the phase transition for the existence of an edge occurs), we have $H(A_n) = \log n({\bf p}^T {\bf Q} {\bf p}  + o(1))$.
\end{rem}

\paragraph{Asymptotic i.i.d. via Block Decomposition}
To compress the matrix $A_n$, we wish to decompose it into a large number of components that have little correlation between them. This leads to the idea of block decomposition described previously. Since the sequence of blocks are used to compress $A_n$, the next theorem claims these blocks are identically distributed and asymptotically independent in a precise sense described as follows.
\begin{thm}[Block decomposition]\label{prop:blkIndep}Let $A_n \sim \text{SBM}(n,L,{\bf p},f(n){\bf Q})$ with
$f(n) = \Omega\left(\frac{1}{n^{2-\epsilon}}\right)$ for some $0 <\epsilon < 1$, $f(n) = O(1)$, and $L = \Theta(1)$. Let $k$ be an integer that divides $n$ and $n' = n/k$. Consider the $k\times k$ block decomposition in~\eqref{eq:blockMatrix}. We have all the off-diagonal blocks share the same joint distribution; all the diagonal blocks share the same joint distribution. In other words, for any $1 \le i_1,i_2,j_1,j_2 \le n'$ with $i_1 \neq j_1, i_2 \neq j_2$ and $1 \le l_1,l_2 \le n'$, we have
\begin{align*}
    {\bf B}_{i_1,j_1} &\stackrel{d}{=} {\bf B}_{i_2,j_2}, \\
    {\bf B}_{l_1,l_1} &\stackrel{d}{=} {\bf B}_{l_2,l_2}.
\end{align*}
In addition, if $k = \omega(1)$ and $k = o(n)$, we have
\begin{equation}\label{eq:AsympIndepBlks}
    \lim_{n\to \infty}\frac{H({\bf B}_{\mathrm{ut}})}{{n' \choose 2}H({\bf B}_{12})} = 1.
\end{equation}
\end{thm}

\paragraph{Length Analysis for Correlated Sequences}
Thanks to this property of the block decomposition, we hope to compress these blocks as if they are independent using a Laplace probability assignment (which, recall, is universal for the class of all $m$-ary iid processes). However, since these blocks are still correlated (albeit weakly), we will need a result on the performance of Laplace probability assignment on correlated sequences with identical marginals, which we give next.

\begin{thm}[Laplace probability assignment for correlated sequence]\label{prop:NonIIDcomp}
Consider arbitrarily correlated $Z_1, Z_2,$ $\ldots, Z_N$, where the marginal distribution of each $Z_i$ is identically distributed over an alphabet of size $m \geq 2$. Let $\ell_{\mathrm{L}}(z^N) = \log \frac{1}{q_{\mathrm{L}}(z^N)}$ where $q_{\mathrm{L}}(\cdot)$ is the marginal distribution induced by Laplace probability assignment in~\eqref{eq:LaplaceProbAssgnSeq}
\begin{align}\label{eq:LaplaceProbAssgn}
    q_{\mathrm{L}}(z^N) \coloneqq \frac{N_1!N_2!\cdots N_m!}{N!}\cdot \frac{1}{{N+m-1 \choose m-1}}.
\end{align}
We then have
\begin{equation}
{\mathsf E}[\ell_{\mathrm{L}}(Z^N)] \le m\log(2eN) + N H(Z_1). \label{eq:LenLaplaceGen}
\end{equation}
\end{thm}

We provide a similar result for the KT probability assignment.
\begin{thm}[KT probability assignment for correlated sequence]\label{prop:KTlength}
 Consider arbitrarily correlated $Z_1, Z_2, \ldots,$ $Z_N$, where the marginal distribution of each $Z_i$ is identically distributed over an alphabet of size $m \geq 2$. Let $\ell_{\mathrm{KT}} (z^N)=\log \frac{1}{q_{\mathrm{KT}}(z^N)}$ where $q_\mathrm{KT}(\cdot)$ is the marginal distribution induced by KT probability assignment in~\eqref{eq:KTProbAssgnSeq}
\begin{align}\label{eq:KTProbAssgn}
    q_{\mathrm{KT}}(z^N) = \frac{(2N_1 -1)!!(2N_2 -1)!!\cdots (2N_m -1)!!}{m(m+2)\cdots (m+2N-2)}
\end{align}
with $(-1)!! \triangleq 1$.  We then have
  \begin{equation}
{\mathsf E}[\ell_{\mathrm{KT}}(Z^N)]\le \tfrac{m}{2}\log\left(e\bigl(1+\tfrac{2N}{m}\bigr)\right)+\tfrac 12\log(\pi N)+NH(Z_1).\label{eq:LenKT}
\end{equation}
\end{thm}

We are now ready to prove Theorem~\ref{thm:strongUniv}.
\iffalse
 We use the bound in~\eqref{eq:LenKT} to establish the upper bound on the length of the code. Choose $m = 2^{k^2}$. For the off-diagonal blocks, set $N_1 = {n'\choose 2}$; for the diagonal blocks, set $N_2 = n'$. We have
 {\allowdisplaybreaks
 \begin{align*}
  \frac{{\mathsf E}(\ell(C_k(A_n)))}{H(A_n)} &\le \frac{N_1H({\bf B}_{12}) + \tfrac m2 \log\left(\tfrac{2N_1}{m}\right) + N_2H({\bf B}_{11}) + \tfrac m2 \log\left(\tfrac{2N_2}{m}\right) + O(\log N_1)}{H(A_n)}\\
   &= \frac{{n'\choose 2}H({\bf B}_{12}) + \tfrac 12 2^{k^2} \log\left(\frac{n^2}{k^22^{k^2}}\right) + n'H({\bf B}_{11}) + \tfrac 12 2^{k^2} \log\left(\frac{2n}{k2^{k^2}}\right) + O(\log n)}{H(A_n)}\\
   &\stackrel{(a)}{\le} \frac{{n'\choose 2}H({\bf B}_{12})}{H({\bf B}_{\mathrm{ut}})} + \frac{n'H({\bf B}_{11})}{H(A_n|X^n)} + \frac{ 2^{k^2} (\tfrac 32\log n - k^2) + O(\log n)}{H(A_n)|_{f(n) = n^{-2+\epsilon}}}\\
   &\stackrel{(b)}{=} 1+o(1) + \frac{\tfrac{nk}{2}H(A_{12}|X_1,X_2) + o(nkh(f(n)))}{\tfrac{n^2}{2}H(A_{12}|X_1,X_2)} + \frac{ 2^{k^2} (\tfrac 32\log n - k^2) + O(\log n)}{\tfrac12 n^2 {\bf p}^T{\bf Q}{\bf p} h(f(n))|_{f(n)=n^{-2+\epsilon}}}\\
   &\stackrel{(c)}{\le} 1+o(1) + \tfrac{k}{n} + o(\tfrac{k}{n})+ \frac{\tfrac 32 n^{\delta} \log n + O(\log n)}{\tfrac {2-\epsilon}{2}{\bf p}^T{\bf Q}{\bf p} n^{\epsilon}\log n}\\
   &\stackrel{(d)}{=} 1+o(1).
 \end{align*}}%
Here, $(a)$ follows since $H(A_n) \ge H({\bf B}_{\mathrm{ut}})$ for the first term, $H(A_n) \ge H(A_n|X^n)$ for the second term, and for the third term, $H(A_n)$ decreases when the graph gets sparser and thus lower bounded by the entropy when $f(n) = n^{-2+\epsilon}$. $(b)$ follows from Theorem~\ref{prop:blkIndep} and the entropy calculation from Lemma~\ref{prop:graphEntropy}. $(c)$ follows since $k \le \sqrt{\delta\log n}$ and $(d)$ follows since $0 < \delta < \epsilon$.
\end{proof}

\fi

\begin{proof}[{\bf Proof of Theorem~\ref{thm:strongUniv}}]
We will prove the universality of $C_k$ for both KT probability assignment and Laplace probability assignment. Note that the upper bound on the expected length of KT in~\eqref{eq:LenKT} is upper bounded by the upper bound on the length of Laplace in~\eqref{eq:LenLaplaceGen}. So it suffices to show Laplace probability assignment is universal.

 We use the bound in Theorem~\ref{prop:NonIIDcomp} to establish the upper bound on the length of the code. Recall that here we compress the diagonal blocks ${\bf B}_{\mathrm{d}}$ ($m = 2^{k_n^2}$-sized alphabet, $N = n'$ blocks) and the off-diagonal blocks ${\bf B}_{\mathrm{ut}}$  ($m = 2^{k_n^2}$-sized alphabet, $N = {n' \choose 2}$ blocks) separately. We have,
 {\allowdisplaybreaks
 \begin{align*}
  \frac{{\mathsf E}(\ell(C_k(A_n)))}{H(A_n)} &= \frac{{\mathsf E}(\ell_{\mathrm{L}}({\bf B}_{\mathrm{ut}})) + {\mathsf E}(\ell_{\mathrm{L}}({\bf B}_{\mathrm{d}}))}{H(A_n)}\\
   &\le \frac{{n' \choose 2}H({\bf B}_{12}) + 2^{k_n^2}\log\left(2e{n' \choose 2}\right) + n'H({\bf B}_{11}) + 2^{k_n^2}\log(2en')}{H(A_n)} \\
   &\stackrel{(a)}{\le}  \frac{{n' \choose 2}H({\bf B}_{12}) + 2^{k_n^2}\log\left(en^2\right) + n H({\bf B}_{11}) + 2^{k_n^2}\log(2en)}{H(A_n)} \\
   &\stackrel{(b)}{\le} \frac{{n' \choose 2}H({\bf B}_{12}) + 2^{k_n^2}\log\left(2e^2n^3\right) + nk_n^2 H(A_{12})}{H(A_n)} \\
   &= \frac{{n' \choose 2}H({\bf B}_{12})}{H(A_n)} + \frac{2^{k_n^2}\log\left(2e^2n^3\right)}{H(A_n)} + \frac{nk_n^2 H(A_{12})}{H(A_n)},
 \end{align*}}%
 where in (a) we bound ${n' \choose 2} \le n^2$ and $n' \le n$, and in (b) we note that $H({\bf B}_{11}) \le k_n^2 H(A_{12})$ since there are $k_n^2 - k_n$ elements of the matrix (all apart from the diagonal elements) are distributed identically as $A_{12}$. We will now  analyze each of these three terms separately. Firstly, using Theorem~\ref{prop:blkIndep} yields that $\frac{{n' \choose 2} H({\bf B}_{12})}{H(A_n)} \to 1$. Next, since $f(n) = \Omega\left(\frac{1}{n^{2-\epsilon}}\right)$, we have $H(A_n) = \Omega(n^{\epsilon} \log n)$ and subsequently substituting $k_n \le \sqrt{\delta \log n}$, we have
 \[
 \frac{2^{k_n^2} \log (2en^3)}{H(A_n)} =  O\left(\frac{n^{\delta} \log n}{n^{\epsilon} \log n}\right)  = O\left(n^{\delta - \epsilon}\right) = o(1)
 \]
 since $\delta <  \epsilon$. Moreover, we have
 \[
 \frac{n k_n^2 H(A_{12})}{H(A_n)} \le \frac{n k_n^2 H(A_{12})}{H(A_n|X^n)} = \frac{n k_n^2 H(A_{12})}{{n \choose 2}H(A_{12}|X_1,X_2)} = O\left(\frac{k_n^2}{n}\right) = o(1),
 \]
 where the penultimate equality used the fact that $H(A_{12}) \sim H(A_{12}|X_1,X_2)$ (since $h(f(n){\bf p}^T {\bf Q} {\bf p}) \sim {\bf p}^T h(f(n){\bf Q}) {\bf p}$). We have then established that
 \begin{align*}
  \frac{{\mathsf E}(\ell(C_k(A_n)))}{H(A_n)} &\le \frac{{n' \choose 2}H({\bf B}_{12})}{H(A_n)} + \frac{2^{k_n^2}\log\left(2en^3\right)}{H(A_n)} + \frac{nk_n^2 H(A_{12})}{H(A_n)} \\
  &= 1 + o(1),
 \end{align*}
 which finishes the proof.
\end{proof}
The proof of Theorem~\ref{thm:weakUniv} follows similar arguments as in Theorem~\ref{thm:strongUniv} and is deferred to Section~\ref{sec:theorem2}.

\section{Proof of Universality}\label{sec:proposition}
\subsection{Graph Entropy}
\begin{proof}[Proof of Lemma~\ref{prop:graphEntropy}]
 Note that
 {\allowdisplaybreaks
\begin{align}
    H(A_n) &= H(A_n|X^n) + I(X^n;A_n)\nonumber \\
    &= {n \choose 2}H(A_{12}|X_1,X_2) + I(X^n;A_n) \label{eq:condindepAij}\\
    &= {n \choose 2}{\bf p}^T h\bigl(f(n){\bf Q}\bigr){\bf p}  + I(X^n;A_n), \label{eq:upperboundEntropyRateCommLabels}

\end{align}}%
where~\eqref{eq:upperboundEntropyRateCommLabels} follows since all the ${n \choose 2}$ edges are identically distributed and also independent given $X^n$ and consequently
\[
H(A_n|X^n) = {n \choose 2}H(A_{12}|X_1,X_2) = {n \choose 2} \sum_{i,j} H(A_{12}|X_1 = i,X_2 = j)p_i p_j = {n \choose 2} {\bf p}^T h\left(f(n){\bf Q}\right){\bf p}.
\]
When $f(n) = \Theta(1)$, we see that since
\[
0 \le I(X^n;A_n) \le H(X^n) = n H(X_1) \le n \log L,
\]
we have that $H(A_n) = {n \choose 2}{\bf p}^T h\bigl(f(n){\bf Q}\bigr){\bf p} + o\left(n^2 h(f(n))\right)$.

Next, consider the case when $f(n) = o(1)$ and $f(n) = \Omega\left(\frac{1}{n^2}\right)$. By properties of the entropy, we have
\begin{align}\label{eq:EntropyBdSadwich}
  H(A_n|X^n) \le  H(A_n) \le {n \choose 2} H(A_{12}).
\end{align}
Note that
\[
{\mathsf P}(A_{12} = 1) = \sum_{i,j}{\mathsf P}(A_{12} = 1|X_1 =i, X_2 = j)p_ip_j = {\bf p}^T f(n){\bf Q} {\bf p},
\]
which yields that $H\left(A_{12}\right) = h\left(f(n){\bf p}^T {\bf Q} {\bf p}\right)$. Substituting this in~\eqref{eq:EntropyBdSadwich} gives
\begin{align}\label{eq:EntropyTightBds}
  {n \choose 2} {\bf p}^T h(f(n){\bf Q}) {\bf p} \le  H(A_n) \le {n \choose 2} h\left(f(n){\bf p}^T{\bf Q}{\bf p}\right).
\end{align}
Note now for any $g(n) = o(1)$, we have
{\allowdisplaybreaks
\begin{align*}
    h(g(n)) &= -g(n) \log g(n) - (1-g(n)) \log (1-g(n)) \\
    &= -g(n) \log g(n) \left(1 + \frac{(1-g(n)) \log (1 - g(n))}{g(n)\log g(n)}\right).
\end{align*}}%
By noting that $\frac{\log (1 - g(n))}{g(n)} \rightarrow -1$ and $\frac{1}{\log (g(n))} \rightarrow 0$ as $g(n) \rightarrow 0$ we see that
\[
h(g(n)) = g(n)\log\frac{1}{g(n)}(1 + o(1)).
\]
Using this, we note that
${\bf p}^T h(f(n){\bf Q}) {\bf p} = {\bf p}^T {\bf Q} {\bf p} f(n) \log \frac{1}{f(n)}(1+o(1))$ and $h(f(n){\bf p}^T {\bf Q} {\bf p}) = {\bf p}^T {\bf Q} {\bf p} f(n) \log \frac{1}{f(n)}(1+o(1))$. Finally, substituting this into~\eqref{eq:EntropyTightBds} yields
\[
H(A_n) = {n \choose 2} {\bf p}^T {\bf Q} {\bf p} f(n) \log \frac{1}{f(n)}(1+o(1))
\]
as required.
\end{proof}
\subsection{Asymptotic i.i.d.\! via Block Decomposition}
We first invoke a known property of stochastic block models (see, for example,~\cite{Lauritzen--Rinaldo--Sadeghi2017}). We include the proof here for completeness.
\begin{lem}[Exchangeability of SBM]\label{lem:exchangeability}
 Let $A_n \sim \mathrm{SBM}(n,L,{\bf p},{\bf W})$. For a permutation $\pi: [n] \to [n]$, let $\pi(A_n)$ be an $n \times n$ matrix whose $(i,j)$ entry is given by $A_{\pi(i),\pi(j)}$. Then, for any permutation $\pi: [n] \to [n]$, the joint distribution of $A_n$ is the same as the joint distribution of $\pi(A_n)$, i.e.,
 \begin{equation}
  A_n \stackrel{d}{=} \pi(A_n).
 \end{equation}

\end{lem}
\begin{proof}Let $a_n$ be a realization of the random matrix $A_n$ and $\pi(X^n)$ be the permuted vector $(X_{\pi(1)}, \ldots, X_{\pi(n)})$. For any symmetric binary matrix $a_n$ with zero diagonal entries, we have
{\allowdisplaybreaks
\begin{align*}
 {\mathsf P}(A_n = a_n) &= \sum_{x^n \in [L]^n} {\mathsf P}(A_n = a_n,X^n = x^n)\\
 &= \sum_{x^n \in [L]^n} {\mathsf P}(A_n = a_n | X^n = x^n) \prod_{i=1}^n {\mathsf P}(X_i = x_i)\\
 &\stackrel{(a)}{=} \sum_{x^n \in [L]^n} \prod_{\substack{i,j\\ 1 \le i < j \le n}} {\mathsf P}(A_{ij} = a_{ij}|X_i = x_i, X_j = x_j) \prod_{i=1}^n {\mathsf P}(X_{\pi(i)} = x_i)\\
 &\stackrel{(b)}{=} \sum_{x^n \in [L]^n}\prod_{\substack{i,j\\ 1 \le i < j \le n}} (W_{x_i,x_j})^{a_{ij}}(1-W_{x_i,x_j})^{1-a_{ij}}\prod_{i=1}^n {\mathsf P}(X_{\pi(i)} = x_i)\\
 &\stackrel{(c)}{=} \sum_{x^n \in [L]^n} \prod_{\substack{i,j\\ 1 \le i < j \le n}} {\mathsf P}(A_{\pi(i),\pi(j)} = a_{ij}|X_{\pi(i)} = x_i, X_{\pi(j)} = x_j) \prod_{i=1}^n {\mathsf P}(X_{\pi(i)} = x_i) \\
 &{=} \sum_{x^n \in [L]^n} {\mathsf P}(\pi(A_n) = a_n, \pi(X^n) = x^n)\\
 &= {\mathsf P}(\pi(A_n) = a_n),
\end{align*}}%
where $(a)$ follows since $X^n$ are i.i.d. and thus ${\mathsf P}(X_i = x_i) = {\mathsf P}(X_{\pi(i)} = x_i)$ and $(b)$ follows since $A_{ij} \sim \mathrm{Bern}(W_{X_i,X_j})$, and thus
\begin{align}
 {\mathsf P}(A_{ij} = a_{ij}|X_i = x_i, X_j = x_j) &= \begin{cases}
                                             W_{x_i,x_j} & \text{ if } a_{ij} = 1\\
                                             1-W_{x_i,x_j} & \text{ if } a_{ij} = 0
                                            \end{cases}\label{eq:condProb1}\\
           &= (W_{x_i,x_j})^{a_{ij}}(1-W_{x_i,x_j})^{1-a_{ij}}. \label{eq:condProb2}
\end{align}
The step in $(c)$ follows since $A_{\pi(i),\pi(j)} \sim \mathrm{Bern}(W_{X_{\pi(i)},X_{\pi(j)}})$ and the conditional probability has the same expression as in~\eqref{eq:condProb2}.
\end{proof}

Now we are ready to establish Theorem~\ref{prop:blkIndep}.
\begin{proof}[Proof of Theorem~\ref{prop:blkIndep}]
For any $i_1 \neq j_1$ and $i_2 \neq j_2$, consider a permutation $\pi_1: [n] \to [n]$ that has
\[
   \pi_1(x) =\Big\{ \begin{array}{lr}
       x + (i_2-i_1)k_n & \text{for } (i_1-1)k_n + 1 \leq x \leq i_1k_n\\
       x + (j_2-j_1)k_n & \text{for } (j_1-1)k_n + 1 \leq x \leq j_1k_n
        \end{array}
  \]
  and the remaining $n-2k_n$ arguments are mapped to the $n-2k_n$ values in $[n]\setminus \{(i_2-1)k_n + 1 ,\ldots, i_2k_n, (j_2-1)k_n ,\ldots ,j_2k_n\}$ in any order. Lemma~\ref{lem:exchangeability} implies that ${\bf B}_{i_1,j_1}$, which is the submatrix formed by the rows
  $(i_1-1)k_n + 1, \ldots, i_1k_n$ and the columns $(j_1-1)k_n + 1,\ldots, j_1k_n$ has the same distribution  as the submatrix formed by the rows $\pi_1((i_1-1)k_n + 1),\ldots, \pi_1( i_1k_n)$ and the columns $\pi_1((j_1-1)k_n + 1),\ldots, \pi_1(j_1k_n)$. From the definition of $\pi_1$, we see that the latter submatrix is ${\bf B}_{i_2,j_2}$ and we establish that ${\bf B}_{i_1,j_1} \stackrel{d}{=} {\bf B}_{i_2,j_2}$. Similarly, defining a permutation $\pi_2: [n] \to [n]$ which has
  \[
   \pi_2(x) = \begin{array}{lr}
       x + (l_2-l_1)k_n & \text{for } (l_1-1)k_n + 1 \leq x \leq l_1k_n
        \end{array}
  \]
  and invoking Lemma~\ref{lem:exchangeability} establishes $ {\bf B}_{l_1,l_1} \stackrel{d}{=} {\bf B}_{l_2,l_2}$.

 Now, clearly $H({\bf B}_{\mathrm{ut}}) \le {n' \choose 2}H({\bf B}_{12})$, and therefore we have
\begin{equation}\label{eq:limsupBut}
    \limsup_{n \to \infty} \frac{H({\bf B}_{\mathrm{ut}})}{{n' \choose 2}H({\bf B}_{12})} \le 1.
\end{equation}
Moreover we have $H(A_n) = H({\bf B}_{\mathrm{ut}}, {\bf B}_{\mathrm{d}}) \le H({\bf B}_{\mathrm{ut}}) + H({\bf B}_{\mathrm{d}}) \le H({\bf B}_{\mathrm{ut}}) + n'H({\bf B}_{\mathrm{11}}) \le  H({\bf B}_{\mathrm{ut}}) + n'k_n^2 h(A_{12})$ where the last inequality follows by noting that except for the diagonal elements of ${\bf B}_{\mathrm{d}}$ (which are zero and thus have zero entropy), all other elements have the same distribution as $A_{12}$. We therefore obtain $H({\bf B}_{\mathrm{ut}}) \ge H(A_n) - n'k_n^2h(A_{12}) = H(A_n) - nk_n h(A_{12}) \ge H(A_n|X_1^n) - nk_n h(A_{12}) = {n \choose 2}{\bf p}^T h(f(n){\bf Q}){\bf p} - nk_n h(f(n){\bf p}^T {\bf Q}{\bf p})$. Consequently,
\begin{align}\label{eq:lbBut}
   \frac{H({\bf B}_{\mathrm{ut}})}{{n' \choose 2}H({\bf B}_{12})} \ge \frac{{n \choose 2} \left({\bf p}^T h(f(n){\bf Q}) {\bf p} - \frac{2 k_n h(f(n){\bf p}^T {\bf Q}{\bf p}) }{n-1}\right)}{{n' \choose 2}H({\bf B}_{12})}.
\end{align}
We will now analyze the right hand side of~\eqref{eq:lbBut} in two parameter ranges.
{\allowdisplaybreaks
\begin{itemize}
    \item \underline{$f(n) = 1$ :} We have
\begin{align}
    H({\bf B}_{12}) &\stackrel{(a)}{\le} H({\bf B}_{12}|X_1^{2k_n}) + H(X_1^{2k_n}) \nonumber \\
    &\le H({\bf B}_{12}|X_1^{2k_n}) + 2k_n H({\bf p}) \nonumber\\
    &\stackrel{(b)}{=} k_n^2 H(A_{1,k_n}|X_1,X_{k_n}) + 2k_n H({\bf p}) \nonumber\\
    &\le k_n^2\left({\bf p}^T h({\bf Q}){\bf p} + 2 \frac{\log L}{k_n}\right), \label{eq:BlockEntropyUB}
\end{align}
where (a) follows from the chain rule and (b) follows since all elements of the matrix ${\bf B}_{12}$ are independent given $X_1,\cdots,X_{2k_n}$.
    Plugging this into the right hand side of~\eqref{eq:lbBut} we obtain
    \begin{align}
        \frac{H({\bf B}_{\mathrm{ut}})}{{n' \choose 2}H({\bf B}_{12})}
         \ge\frac{{n \choose 2}\left({\bf p}^T h({\bf Q}){\bf p} - \frac{2k_n h({\bf p}^T {\bf Q}{\bf p})}{n-1}\right)}{{n' \choose 2}k_n^2\left({\bf p}^T h({\bf Q}){\bf p} + 2 \frac{\log L}{k_n}\right)}. \label{eq:liminfBut}
    \end{align}
    Since $k_n = o(n), k_n = \omega(1)$ and ${n' \choose 2}k_n^2 \sim {n \choose 2}$, we have from~\eqref{eq:liminfBut}
    \begin{align}\label{eq:liminfone}
          \liminf_{n \to \infty} \frac{H({\bf B}_{\mathrm{ut}})}{{n' \choose 2}H({\bf B}_{12})} \ge 1,
    \end{align}
    which together with~\eqref{eq:limsupBut} yields the required result.

    \item \underline{$f(n) = \Omega\left(\frac{1}{n^2}\right), f(n) = o(1):$} Since ${\bf B}_{12}$ is a matrix of $k_n^2$ identically distributed Bernoulli random variables, we have
    \begin{align}\label{eq:vanishingPblkEntropy}
    H({\bf B}_{12}) \le k_n^2 h(A_{1,k_n}) = k_n^2 h\left(f(n){\bf p}^T {\bf Q} {\bf p} \right).
    \end{align}
    Plugging this into the RHS of~\eqref{eq:lbBut} then yields
    \begin{align}
        &\frac{H({\bf B}_{\mathrm{ut}})}{{n' \choose 2}H({\bf B}_{12})} \ge \frac{{n \choose 2}\left({\bf p}^T h(f(n){\bf Q}){\bf p} - \frac{2k_n h(f(n){\bf p}^T {\bf Q}{\bf p})}{n-1}\right)}{{n' \choose 2}k_n^2 h\left(f(n){\bf p}^T {\bf Q}{\bf p}\right)}. \label{eq:bbutVanishP}
    \end{align}
    We first observe that in this parameter range, since $f(n) = o(1)$, we have by Lemma~\ref{prop:graphEntropy}
    \begin{align}\label{eq:entropyGapVanishes}
     {\bf p}^T h(f(n){\bf Q}){\bf p}   \sim  h\left(f(n){\bf p}^T {\bf Q}{\bf p}\right).
    \end{align}
     Finally using that $k_n = o(n)$ and ${n' \choose 2}k_n^2 \sim {n \choose 2}$ establishes
     \begin{align}\label{eq:liminfoneVanishing}
          \liminf_{n \to \infty} \frac{H({\bf B}_{\mathrm{ut}})}{{n' \choose 2}H({\bf B}_{12})} \ge 1,
    \end{align}
    which together with~\eqref{eq:limsupBut} yields the required result.
\end{itemize}}%
\end{proof}

\subsection{Length of the Laplace Probability Assignment}
\begin{proof}[Proof of Theorem~\ref{prop:NonIIDcomp}]
Let us first elaborate the relation between probability assignment and compression length.
In Algorithm~\ref{alg:arithmetic}, the terms $\log(q(x_{j+1}|x^j))$ are added up, which lead to the marginal probability implied by the sequential probability assignment
\begin{equation}\label{eq:marginal}
 \sum_{j=0}^{N-1}\log(q(x_{j+1}|x^j)) = \log \left(\prod_{j=0}^{N-1} q(x_{j+1}|x^j)\right) = \log(q(x^N)).
\end{equation}
The compression output length of Algorithm~\ref{alg:arithmetic} is $\left\lceil\log\frac{1}{q(x^N)}\right\rceil + 1$.

Now we analyze the compression length of Laplace compressor for the sequence $Z_1,Z_2,\ldots,Z_N$.
Define $\theta_i \coloneqq {\mathsf P}(Z_1 = i), N_i \coloneqq \sum_{k=1}^N \mathbbm{1} \{Z_k = i\}, i \in [m]$.
We have
{\allowdisplaybreaks
\begin{align}
      \ell_{\mathrm{L}}(z^n) &=\log \frac{1}{q_{\mathrm{L}}(z^N)} \nonumber \\
      &= \log \frac{\theta_1^{N_1}\theta_2^{N_2}\cdots\theta_m^{N_m}}{q_{\mathrm{L}}(z^N)} + \log \frac{1}{\theta_1^{N_1}\theta_2^{N_2}\cdots\theta_m^{N_m}} \nonumber \\
      &= \log {N+m-1 \choose m-1} \nonumber + \log \left(\frac{N!}{N_1!N_2!\cdots N_m!}\theta_1^{N_1}\theta_2^{N_2}\cdots\theta_m^{N_m}\right) +  \log \frac{1}{\theta_1^{N_1}\theta_2^{N_2}\cdots\theta_m^{N_m}} \nonumber \\
      &\stackrel{(a)}{\le} \log {N+m-1 \choose m-1}  + \log \frac{1}{\theta_1^{N_1}\theta_2^{N_2}\cdots\theta_m^{N_m}} \nonumber  \\
      &\stackrel{(b)}{\le} (m-1)\log\left(e\left(\frac{N}{m-1}+1\right)\right) + \log \frac{1}{\theta_1^{N_1}\theta_2^{N_2}\cdots\theta_m^{N_m}} \nonumber \\
      &\le m \log (2eN) + \sum_{i=1}^m N_i \log\frac{1}{\theta_i}, \label{eq:LenLaplaceRV}
\end{align}}%
where (a) follows since $\frac{N!}{N_1!N_2!\cdots N_m!}\theta_1^{N_1}\theta_2^{N_2}\cdots\theta_m^{N_m}$ is a multinomial probability which is always upper bounded by 1, and (b) follows since ${n \choose k} \le \left(\frac{en}{k}\right)^k$. Taking expectation on both sides of~\eqref{eq:LenLaplaceRV}, we obtain
{\allowdisplaybreaks
\begin{align}
    {\mathsf E}[  \ell_{\mathrm{L}}(Z^N) ] &\le  m \log (2e N) + \sum_{i=1}^m {\mathsf E}[N_i] \log\frac{1}{\theta_i} \nonumber \\
    &\stackrel{(a)}{=}  m \log (2eN) + \sum_{i=1}^m N \theta_i \log\frac{1}{\theta_i} \nonumber \\
    &=  m \log (2eN) + N H(Z_1), \nonumber
\end{align}}%
where (a) follows since ${\mathsf E}[N_i] = \sum_{k=1}^N {\mathsf E}[\mathbbm{1}\{Z_k = i\}] = N {\mathsf P}(Z_1 = i)$ since the $Z_i$ are identically distributed.
\end{proof}

\subsection{Length of the KT probability assignment}
\begin{lem}\label{lem:KTlength}
 For any integer $m>0$, $N_1, N_2, \cdots N_m \in \mathbb{N}$ and probability distribution $(\theta_1, \cdots \theta_m)$, $$\frac{\binom{N}{N_1,N_2\cdots N_m}\theta_1^{N_1}\cdots\theta_m^{N_m}}{\binom{2N}{2N_1,2N_2\cdots 2N_m}\theta_1^{2N_1}\cdots\theta_m^{2N_m}}\ge 1,$$ where $N=\sum_{i=1}^m N_i$.
\end{lem}
\begin{rem}
 Equivalently, consider an urn containing known number of balls with m different colours. The lemma claims that the probability of getting $N_1$ balls of colour 1, $N_2$ of balls of colour 2, $\cdots$ $N_m$ balls of colour m out of $N$ draws with replacement is always greater than the probability of getting $2N_1$ balls of colour 1, $2N_2$ of balls of colour 2, $\cdots$ $2N_m$ balls of colour m out of $2N$ draws with replacement.
\end{rem}
\begin{proof
Let $p_1=N_1/N, p_2=N_2/N,\cdots,p_m=N_m/N.$ Notice that $\sum_{i=1}^m p_i=1$, so $(p_1,\cdots p_m)$ can be viewed as a probability distribution. And the entropy of this distribution is $H(p_1, \cdots p_m)=\sum_{i=1}^m -p_i\log{p_i}.$ Firstly we consider the case when $N_1,N_2\cdots N_m$ are all positive and none of them equal to N.
By Stirling's approximation for factorial $\sqrt{2\pi n}(\frac{n}{e})^n e^{1/(12n+1)}\le n!\le \sqrt{2\pi n}(\frac{n}{e})^n e^{1/12n}$, we can bound
{\allowdisplaybreaks
\begin{align*}
\binom{N}{N_1,N_2\cdots N_m}&\ge \frac{\sqrt{2\pi N}N^N \exp\left(\frac{1}{12N+1}-\frac{1}{12N_1}-\frac{1}{12N_2}-\cdots -\frac{1}{12N_m}\right)}{(2\pi)^{m/2}(N_1N_2\cdots N_m)^{1/2}N_1^{N_1}N_2^{N_2}\cdots N_m^{N_m}}\\
&=\frac{\exp\left(\frac{1}{12N+1}-\frac{1}{12N_1}-\frac{1}{12N_2}-\cdots -\frac{1}{12N_m}\right)}{(2\pi)^{\frac{m-1}{2}}(p_1p_2\cdots p_m)^{1/2}N^{\frac{m-1}{2}}2^{-NH(p_1,p_2,\cdots,p_m)}}.
\end{align*}}%
Similarly, we have
{\allowdisplaybreaks
$$\binom{2N}{2N_1,2N_2\cdots 2N_m}\le \frac{\exp\left(\frac{1}{24N}-\frac{1}{24N_1+1}-\frac{1}{24N_2+1}-\cdots -\frac{1}{24N_m+1}\right)}{(2\pi)^{\frac{m-1}{2}}2^{\frac{m-1}{2}}(p_1p_2\cdots p_m)^{1/2}N^{\frac{m-1}{2}}2^{-2NH(p_1\cdots p_m)}}\cdot$$}%
Consider the function
\begin{align*}
f(N_1,N_2,\cdots,N_m)=\tfrac{1}{12N+1}-\tfrac{1}{24N}+(\tfrac{1}{24N_1+1}-\tfrac{1}{12N_1})+(\tfrac{1}{24N_2+1}-\tfrac{1}{12N_2})+\cdots +(\tfrac{1}{24N_m+1}-\tfrac{1}{12N_m})
\end{align*}
and the function
$$g(n)=\frac{1}{24n+1}-\frac{1}{12n},$$
where $n$ is a positive integer.
Function $g(n)$ is minimized with $n=1$ and $\min g(n)=1/25-1/12$ and we can bound function $f(N_1,N_2,\cdots,N_m)\ge \frac{1}{12N+1}-\frac{1}{24N}+(1/25-1/12)m$.
Finally we are ready to prove the lemma.
\begin{align*}
\frac{\binom{N}{N_1,N_2\cdots N_m}\theta_1^{N_1}\cdots\theta_m^{N_m}}{\binom{2N}{2N_1,2N_2\cdots 2N_m}\theta_1^{2N_1}\cdots\theta_m^{2N_m}} &\ge \frac{2^{\frac{m-1}{2}}\exp(f(N_1,N_2,\cdots,N_m))}{2^{NH(p_1\cdots p_m)}\theta_1^{N_1}\cdots\theta_m^{N_m}}\\
&\ge \frac{2^{\frac{m-1}{2}}\exp\left(\frac{1}{12N+1}-\frac{1}{24N}+(1/25-1/12)m\right)}{2^{-ND_{\mathrm{KL}}(p||\theta)}} \\
&=2^{\frac{m-1}{2}}2^{ND_{\mathrm{KL}}(p||\theta)}2^{\log{e}(\frac{1}{12N+1}-\frac{1}{24N}+(1/25-1/12)m)}.
\end{align*}
Notice that $\frac{1}{12N+1}-\frac{1}{24N}$ goes to zero when $N\to \infty$, $\frac{m-1}{2}>(1/25-1/12)m$ and $D_{\mathrm{KL}}(P||\theta)\ge 0$. Therefore in this case,
$$\frac{\binom{N}{N_1,N_2\cdots N_m}\theta_1^{N_1}\cdots\theta_m^{N_m}}{\binom{2N}{2N_1,2N_2\cdots 2N_m}\theta_1^{2N_1}\cdots\theta_m^{2N_m}} \ge 1.$$
When one of $\{N_i\}_{i=1}^N$ equals to $N$, without loss of generality, we assume that $N_1=N$. We have
{\allowdisplaybreaks
$$\frac{\binom{N}{N_1,N_2\cdots N_m}\theta_1^{N_1}\cdots\theta_m^{N_m}}{\binom{2N}{2N_1,2N_2\cdots 2N_m}\theta_1^{2N_1}\cdots\theta_m^{2N_m}}=\frac{1}{\theta_1^{N_1}\cdots\theta_m^{N_m}}>1.$$}%
When there are $k$ numbers out of $N_1, N_2, \cdots, N_m$ that equal to zero, we can simply remove these values and consider the case with alphabet size $m-k$. And this will yield the same result.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{prop:KTlength}]
\iffalse
Similar to the analysis of Laplace, we first write the marginal probability induced by KT probability assignment
\begin{align}\label{eq:KTProbAssgn}
    q_{\mathrm{KT}}(x^N) = \frac{(2N_1 -1)!!(2N_2 -1)!!\cdots (2N_m -1)!!}{m(m+2)\cdots (m+2N-2)},
\end{align}
where $(-1)!! \triangleq 1$.
\fi
In this proof, we define a generalized form of factorial function. Let $x$ be a positive integer, $(x+\frac{1}{2})!=\frac{1}{2} \frac{3}{2} \cdots (x+\frac{1}{2})$. Since $(2N_1-1)!!=\frac{(2N_1)!}{2^{N_1}(N_1)!}$, we have
{\allowdisplaybreaks
\begin{align*}
m(m+2)\cdots (m+2N-2)=2^N \left(\frac{m}{2}\right) \left(\frac{m+2}{2}\right)\cdots \left(\frac{m+2N-2}{2}\right)=2^N\frac{\left(\frac{m}{2}+N-1\right)!}{\left(\frac{m}{2}-1\right)!}.
\end{align*}}%
Therefore we can rewrite the KT probability assignment in~\eqref{eq:KTProbAssgn} as
{\allowdisplaybreaks
\begin{align*}
q_\mathrm{KT}(z^N)&=\frac{(\frac{m}{2}-1)!}{2^N(\frac{m}{2}+N-1)!}\frac{\binom{2N}{N}}{\binom{2N}{N}}\prod_{i=1}^m \frac{(2N_i)!}{N_i ! \vspace{.2em}2^{N_i}}\\
&=\frac{(\frac{m}{2}-1)!}{2^N(\frac{m}{2}+N-1)!} \binom{2N}{N}N! \frac{N!}{(2N)!}\prod_{i=1}^m \frac{(2N_i)!}{N_i !2^{N_i}} \\
&\stackrel{(a)}{\ge}\frac{\left(\frac{m}{2}-1\right)!\binom{2N}{N}}{4^N (N+\frac{m}{2}-\frac{1}{2})^{\frac{m-1}{2}}}\frac{N!}{(2N)!}\prod_{i=1}^m \frac{(2N_i)!}{N_i !}\\
&\stackrel{(b)}{=}\frac{\theta_1^{N_1}\cdots\theta_m^{N_m}(\frac{m}{2}-1)!\binom{2N}{N}}{4^N (N+\frac{m}{2}-\frac{1}{2})^{\frac{m-1}{2}}}\frac{\binom{N}{N_1,N_2\cdots N_m}\theta_1^{N_1}\cdots\theta_m^{N_m}}{\binom{2N}{2N_1,2N_2\cdots 2N_m}\theta_1^{2N_1}\cdots\theta_m^{2N_m}},
\end{align*}}%
where (a) follows that when m is even, $\frac{N!}{(\frac{m}{2}+N-1)!}=\frac{1}{(N+1)\cdots (\frac{m}{2}+N-1)}\ge \frac{1}{(N+\frac{m}{2}-\frac{1}{2})^{\frac{m-1}{2}}}$ and when m is odd, $\frac{N!}{(\frac{m}{2}+N-1)!}\ge\frac{N!}{(\frac{m}{2}+N-\frac{1}{2})!}=\frac{1}{(N+1)\cdots (\frac{m}{2}+N-\frac{1}{2})}\ge\frac{1}{(N+\frac{m}{2}-\frac{1}{2})^{\frac{m-1}{2}}}$, (b) follows that $\binom{N}{N_1,N_2\cdots N_m}=\frac{N!}{\prod_{i=1}^m N_i !}$ and $\theta_i\triangleq\mathbb{P}(Z_1=i)$. By lemma~\ref{lem:KTlength}, we have $q_\mathrm{KT}(z^N)\ge\frac{\theta_1^{N_1}\cdots\theta_m^{N_m}(\frac{m}{2}-1)!\binom{2N}{N}}{4^N (N+\frac{m}{2}-\frac{1}{2})^{\frac{m-1}{2}}}$. Thus,
{\allowdisplaybreaks
\begin{align*}
\ell_\mathrm{KT} (z^N)&=\log \frac{1}{q_\mathrm{KT}(z^N)}\\
&\le \log{\frac{1}{\theta_1^{N_1}\cdots\theta_m^{N_m}}}+\log{\frac{4^N (N+\frac{m}{2}-\frac{1}{2})^{\frac{m-1}{2}}}{(\frac{m}{2}-1)!\binom{2N}{N}}}\\
&=\log{\frac{1}{\theta_1^{N_1}\cdots\theta_m^{N_m}}}+\frac{m-1}{2}\log{\left(N+\frac{m-1}{2}\right)}+\log{\frac{4^N}{\binom{2N}{N}}}-\log{\left(\frac{m}{2}-1\right)!}\\
&\stackrel{(a)}{\le}\log{\frac{1}{\theta_1^{N_1}\cdots\theta_m^{N_m}}}+\frac{m-1}{2}\log{\left(N+\frac{m-1}{2}\right)}+\log{\frac{4^N}{\binom{2N}{N}}}-\left(\frac{m}{2}-1\right)\log{(\frac{\frac{m}{2}-1}{e})}\\
&\stackrel{(b)}{\sim}\log{\frac{1}{\theta_1^{N_1}\cdots\theta_m^{N_m}}}+\frac{m-1}{2}\log{\left(N+\frac{m-1}{2}\right)}+\log{\sqrt{\pi N}}-\left(\frac{m}{2}-1\right)\log{\left(\frac{\frac{m}{2}-1}{e}\right)}\\
&\sim \frac{m}{2}\log{\frac{e(\frac{m}{2}+N)}{m/2}}+\log{\sqrt{\pi N}}+\log{\frac{1}{\theta_1^{N_1}\cdots\theta_m^{N_m}}}\\
&=\frac{m}{2}\log\left(e\bigl(1+\tfrac{2N}{m}\bigr)\right)+\frac 12\log(\pi N)+\sum_{i=1}^m N_i \log{\frac{1}{\theta_i}},
\end{align*}}%
where $(a)$ follows Stirling's approximation $k!\ge \sqrt{2\pi k}(\frac{k}{e})^{k}e^{\frac{1}{12k+1}}$ and (b) follows Stirling's approximation for binomial coefficient, i.e., $\binom{2N}{N}\sim \frac{4^N}{\sqrt{\pi N}}$. Therefore, we have
\begin{align*}
{\mathsf E}[\ell_\mathrm{KT}(Z^N)]\le \frac{1}{2}m\log\left(e\bigl(1+\tfrac{2N}{m}\bigr)\right)+\frac 12\log(\pi N)+NH(Z_1).\\[-3em]
\end{align*}
\end{proof}

\subsection{Proof of Theorem~\ref{thm:weakUniv}}\label{sec:theorem2}
\begin{proof}Once again, we establish universality for both KT and Laplace probability assignment. Following a similar argument as in the proof of Theorem~\ref{thm:strongUniv}, it suffices to show the universality of Laplace. Since we are compressing $N = {n \choose 2}$ identically distributed bits using a Laplace probability assignment, Theorem~\ref{prop:NonIIDcomp} yields
 {\allowdisplaybreaks
\begin{align*}
    \frac{{\mathsf E}(\ell(C_1(A_n)))}{H(A_n)} &\le  \frac{\log(2eN) + N H\left(A_{12}\right)}{H(A_n)} \\
    &\le \frac{\log(2eN) + N H\left(A_{12}\right)}{H(A_n|X_1^n)} \\
    &= \left(\frac{\log(2eN) + N H\left(A_{12}\right)}{N H(A_{12})} \right) \frac{H(A_{12})}{H(A_{12}|X_1,X_2)} \\
    &= \left(1 + \frac{\log(2eN)}{Nh(f(n){\bf p}^T {\bf Q} {\bf p})}  \right)\frac{h(f(n){\bf p}^T {\bf Q} {\bf p})}{{\bf p}^T h(f(n){\bf Q}) {\bf p}}\\
    &\stackrel{(a)}{=} 1 + o(1).
\end{align*}}%
Here, (a) is justified by noting that $\frac{\log(2eN)}{Nh(f(n){\bf p}^T {\bf Q} {\bf p})} \le \frac{\log(2en^2)}{{n \choose 2}h(n^{-(2-\epsilon)}{\bf p}^T {\bf Q} {\bf p})} \frac{h(n^{-(2-\epsilon)}{\bf p}^T {\bf Q} {\bf p})}{h(f(n){\bf p}^T {\bf Q} {\bf p})}$, and then noting that  $\frac{\log(2en^2)}{{n \choose 2}h(n^{-(2-\epsilon)}{\bf p}^T {\bf Q} {\bf p})} = o(1)$ and $\frac{h(n^{-(2-\epsilon)}{\bf p}^T {\bf Q} {\bf p})}{h(f(n){\bf p}^T {\bf Q} {\bf p})} = O(1)$ when $f(n) = \Omega\left(\frac{1}{n^{2-\epsilon}}\right)$ and that $H(h(f(n){\bf p}^T {\bf Q} {\bf p}) \sim {\bf p}^T h(f(n){\bf Q}) {\bf p}$.
\end{proof}

\begin{rem}
When $f(n) = 1$, the compressor $C_1$ is strictly suboptimal. This is because the length achieved by $C_1$ is ${n \choose 2}h\left(f(n) {\bf p}^T {\bf Q} {\bf p} \right) (1 + o(1))$, whereas the first order term in the entropy is ${n \choose 2} {\bf p}^T  h\left(f(n){\bf Q}\right)  {\bf p}^T$. When $f(n)$ is $o(1)$, these two have the same first order term. However, when $f(n)$ is constant, ${\bf p}^T  h\left(f(n){\bf Q}\right)  {\bf p}^T$ is strictly smaller than $h\left(f(n) {\bf p}^T {\bf Q} {\bf p} \right) $ by concavity of entropy.
\end{rem}

\section{Second order analysis in the sparse regime}\label{sec:BCentropy}
So far, we have shown that our algorithm always matches the first order term in the Shannon entropy. Now, we proceed to analyze the second order term of the expected length of our proposed compressor. We focus on the family of \emph{symmetric} SBM with edge probability $f(n) = 1/n$ and evaluate the performance of our compressor using the framework of local weak convergence, as introduced in~\cite{Bordenave_2014}. This would allow us to compare the performance of our compressor to the compressor proposed in~\cite{Delgosha--Anatharam2017}. We first introduce some basic definitions on rooted graphs in Subsection~\ref{subsec:definitions}. Then, we define the local weak convergence of graphs and derive the local weak convergence limit of the symmetric stochastic block model in Subsection~\ref{subsec:LWC}. Finally, we review the definition of BC entropy in Subsection~\ref{subsec:BCentropy} and state the performance guarantee of our compression algorithm in Subsection~\ref{subsec:Achieve_BC}.

\subsection{Basic definitions on  rooted graphs}\label{subsec:definitions}
Let $G=(V,E)$ be a simple graph (undirected, unweighted, no self-loop), with $V$ a countable set of vertices and $E$ a countable set of edges. Let $u\stackrel{G}{\sim}v$ denote the connectivity of vertices $u$ and $v$ in $G$. $G$ is said to be \emph{locally finite} if, for all $v\in V$, the degree of $v$ in $G$ is finite. A rooted graph $(G,o)$ is a locally finite and connected graph $G=(V,E,o)$ with a distinguished vertex $o\in V$, called the root. Two rooted graphs $(G_1,o_1)=(V_1,E_1,o_1)$ and $(G_2,o_2)=(V_2,E_2,o_2)$ are \emph{isomorphic}, denoted as $(G_1,o_1)\simeq(G_2,o_2)$, if there exists a bijection $\pi:V_1\rightarrow V_2$ such that $\pi(o_1)=o_2$ and $u\stackrel{G_1}{\sim}v$ if and only if $ \pi(u)\stackrel{G_2}{\sim}\pi(v)$ for all $u,v \in V_1$. One can verify that this notion of isomorphism defines an equivalence relation on rooted graphs. Let $[G,o]$ denote the equivalence class corresponding to $(G,o)$. Let $\mathcal{G}^*$ denote the set of all locally finite and connected rooted graphs. For $(G,o)\in\mathcal{G}^*$ and $h\in \mathbb{N}$, we write $(G,o)_h$ for the truncated graph at depth $h$ of the graph $(G,o)$, in other words, the induced subgraph on the vertices such that their distance from the root is less than or equal to $h$. The equivalence classes $[G,o]_h$ follows the similar definition. Let $\mathcal{G}^*_h$ denote the set of all $[G,o]_h$. Now, we define the metric $d^*$ on $\mathcal{G}^*$. For any $[G_1,o_1]$ and $[G_2,o_2]$, let
$$\hat{h}:=\sup\{h\in \mathbb{Z}^+:(G_1,o_1)_h\simeq(G_2,o_2)_h \text{ for some } (G_1,o_1) \in [G_1,o_1], (G_2,o_2) \in [G_2,o_2]\}$$
and define the metric $d^*$ as $$d^*([G_1,o_1],[G_2,o_2]):=\frac{1}{1+\hat{h}}.$$ As shown in~\cite{Delgosha--Anatharam2017}, equipped with the metric defined above, $\mathcal{G}^*$ is a Polish space, i.e, a complete separable metric space. For this Polish space, let $\mathcal{P}(\mathcal{G}^*)$ denote the Borel probability measures on it. We say that a sequence of measures $\mu_n\in\mathcal{P(G^*)}$ \emph{converges weakly} to $\mu\in\mathcal{P}(\mathcal{G}^*)$, written as $\mu_n\rightsquigarrow\mu$, if for any bounded continuous function $f$ on $\mathcal{G}^*$, we have $\int fd\mu_n\rightarrow\int fd\mu$. It was shown in~\cite{billing} that $\mu_n\rightsquigarrow\mu$ if for any uniformly continuous and bounded functions $f$, we have $\int fd\mu_n\rightarrow\int fd\mu$. For $\mu\in \mathcal{P}(\mathcal{G}^*)$, $h\in\{0,1,2,\ldots\}$, and $[G,o]\in \mathcal{G}^*$, let $\mu_h$ denote the $h$-neighborhood marginal of $\mu$
$$\mu_h([G,o])=\sum_{[G',o]\in \mathcal{G}^*:[G',o]_h=[G,o]}\mu([G',o]).$$
For a locally finite graph $G=(V,E)$ and a vertex $v\in V$, let $G(v)$ denote the graph component in $G$ that is connected to $v$. By our previous definitions, $(G(v),v)$ denotes the rooted graph of the connected component of $v$ and the root is located at $v$ and $[G(v),v]$ denotes the equivalence class corresponding to $(G(v),v)$. Now, the \emph{rooted neighbourhood distribution} of $G$ is defined as the distribution of the rooted graph when the root is chosen uniformly at random over $V$
\begin{equation}
U(G):=\frac{1}{|V|}\sum_{v\in V}\delta_{[G(v),v]},\label{eqn:U(G)}
\end{equation}
where $\delta$ is the Dirac delta function.

\subsection{Local weak convergence} \label{subsec:LWC}
For our study of stochastic block model, which is a sequence of \emph{random} graphs $\{A_n\}_{n=1}^\infty$, $U(A_n)$ as defined in~\eqref{eqn:U(G)} becomes a random distribution. In the section, we establish the asymptotic behavior of the average neighbourhood distribution ${\mathsf E} U(A_n)$ averaged over the randomness of the graph $A_n$.

To state the limiting distribution, we define the \emph{Galton--Watson tree} probability distribution on rooted trees $\mathrm{GWT}(\mathrm{P}_\lambda)$ as follows. Let $\mathrm{P}_\lambda$ denote the Poisson distribution with mean $\lambda$. We take a vertex as the root and generate $Z^{(1)}\sim\mathrm{P}_\lambda$ as the number of children of the first generation. For the first generation, independent of $Z^{(1)}$, we generate $\xi^{(1)}_1,\ldots, \xi^{(1)}_{Z^{(1)}}$ i.i.d. according to $\mathrm{P}_\lambda$ as the number of children of each vertex in the first generation. Let $Z^{(2)}=\sum_{i=1}^{Z^{(1)}}\xi^{(1)}_i$ denote the total number of vertices in the first generation. In general, for the $j$th generation, $j = 1,2,\ldots$, generate the number of children for each vertex in the $j$th generation $\xi^{(j)}_1,\ldots,\xi^{(j)}_{Z^{(j)}}$ i.i.d. according to $\mathrm{P}_\lambda$, independent of all previous variables $\{ \xi^{(i-1)}_1, \ldots, \xi^{(i-1)}_{Z^{(i-1)}}, Z^{(i)}, \text{ for all } i \le j\}$. Let $Z^{(j+1)}= \sum_{k=1}^{Z^{(j)}}\xi^{(j)}_k$ denote the total number of vertices in the $j$th generation.
In this way, we iteratively defined a measure on rooted trees.
With the definitions above, we are ready to establish the local weak convergence of the symmetric stochastic block model.
\begin{lem}[Local weak convergence of sparse symmetric SBMs]\label{LWC_SBM}
Let $A_n$ denote a graph generated from a symmetric stochastic block model $\mathrm{SBM}(n,L,\mathbf{p},\frac{1}{n}\mathbf{Q})$ with $\mathbf{p}=\left(\frac{1}{L},\ldots,\frac{1}{L}\right)$, $\mathbf{Q}_{ii}=a,\forall i\in[n]$ and $\mathbf{Q}_{ij}=b,\forall i,j\in[n],i\neq j$. Let $U(A_n)$, defined as in~\eqref{eqn:U(G)}, be the random rooted neighbourhood distribution of $A_n$.
Then, the average neighbourhood distribution ${\mathsf E} U(A_n)$ converges weakly to a Poisson Galton--Walson tree
$${\mathsf E} U(A_n)\rightsquigarrow \mathrm{GWT}(\mathrm{P}_{\lambda}),$$
where $\lambda = \frac{a + (L-1)b}{L}$.
\end{lem}
\begin{rem}
When $a=b$, the symmetric stochastic block model recovers the well-known local weak convergence result on Erd\H{o}s--R\'{e}nyi model (see, e.g.,~\cite{}).
\end{rem}
\begin{proof}[{\bf Proof of Lemma~\ref{LWC_SBM}}]
We want to show that for any uniformly continuous and bounded function $f$,
$$\left|\int fd{\mathsf E} U(A_n)-\int f d\mathrm{GWT}(\mathrm{P}_{\lambda})\right|\rightarrow 0$$
as $n\rightarrow \infty$.
Since $f$ is a uniformly continuous function on $\mathcal{G}^*$, for every $\epsilon >0$ there exists $\delta >0$ such that, for any pair of rooted graphs $[G_1,o_1]$ and $[G_2,o_2]\in \mathcal{G^*}$ with $d^*([G_1,o_1],[G_2,o_2])<\delta$ we have $|f(G_1,o_1)-f(G_2,o_2)|< \epsilon$. Recall that $d^*([G_1,o_1],[G_2,o_2]):=\frac{1}{1+\hat{h}}$, where $\hat{h}$ denotes the maximum layers of matching between $[G_1,o_1]$ and $[G_2,o_2]$. Therefore, as long as $h>\frac{1}{\delta}-1$, we have $|f((G,o)_h)-f(G,o)|< \epsilon$. It follows that $|f([i,o])-f([g,o])|<\epsilon$, if $[i,o]_h=[g,o]$. Let $\mu\in\mathcal{P}(\mathcal{G}^*)$ and assume $h>\frac{1}{\delta}-1$. We have
{\allowdisplaybreaks
\begin{align}
    \left|\int fd\mu_h-\int fd\mu\right|&=\left|\sum_{[g,o]\in \mathcal{G}^*_h}f([g,o])\mu_h([g,o])-\sum_{[i,o]\in \mathcal{G}^*}f([i,o])\mu([i,o])\right|\\
    &\le \sum_{[g,o]\in\mathcal{G}^*_h}\left|f([g,o])\mu_h([g,o])-\sum_{[i,o]\in\mathcal{G}^*:[i,o]_h=[g,o]}f([i,o])\mu([i,o])\right|\\
    &=\sum_{[g,o]\in\mathcal{G}^*_h}\left|\sum_{[i,o]\in\mathcal{G}^*:[i,o]_h=[g,o]}(f([g,o])-f([i,o]))\mu([i,o])\right|\\
    &\le\sum_{[g,o]\in\mathcal{G}^*_h}\sum_{[i,o]\in\mathcal{G}^*:[i,o]_h=[g,o]}\left|f([g,o])-f([i,o])\right|\mu([i,o])\\
    &\le\sum_{[g,o]\in\mathcal{G}^*_h}\sum_{[i,o]\in\mathcal{G}^*:[i,o]_h=[g,o]}\epsilon\mu([i,o])=\epsilon,
\end{align}}%
where (3) follows since $\mu_h([g,o])=\sum_{[i,o]\in \mathcal{G}^*:[i,o]_h=[g,o]}\mu([i,o])$.
Therefore, we have $|\int fd{\mathsf E} U(A_n)_h-\int fd{\mathsf E} U(A_n)|<\epsilon$ and $|\int fd\mathrm{GWT}(\mathrm{P}_{\lambda})_h-\int fd\mathrm{GWT}(\mathrm{P}_{\lambda})|<\epsilon$. Let $B\subseteq\mathcal{G}^*$ be a measurable event in $\mathcal{G}^*$. By the exchangability of stochastic block model, we have ${\mathsf E} U(A_n)(B)=\frac{1}{n}\sum_{i=1}^n{\mathsf P}([A_n(i),i]\in B)={\mathsf P}([A_n(1),1]\in B)$, in other words, ${\mathsf E} U(A_n)$ is simply the neighbourhood distribution at vertex $1$. By the analogous argument as in proposition 2 of~\cite{Mossel--Neeman--Sly15}, for any $\epsilon>0$, there exists $n_0$ such that if $n\ge n_0$ and $\frac{\ln n}{10\ln (2(a+(L-1)b))}\ge R$, we have $d_{TV}(\mathrm{GWT}(\mathrm{P}_{\lambda})_R,{\mathsf E} U(A_n)_R)<\epsilon$, where $d_{TV}(\cdot,\cdot)$ denotes the total variation distance between two measures. Remember here the total variation distance is  $d_{TV}(\mu_1,\mu_2):=\sup_{g:\mathcal{G}^*\rightarrow [-1,1]}(\int gd\mu_1-\int gd\mu_2)$. Since $f$ is a bounded function, we have $|\int f d\mathrm{GWT}(\mathrm{P}_{\lambda})_R-\int fd{\mathsf E} U(A_n)_R|<\epsilon$, as long as n is large enough. Therefore, if we take $n$ large enough such that $\frac{\ln n}{10\ln (2(a+(L-1)b))}>\frac{1}{\delta}-1$ and $|\int f d\mathrm{GWT}(\mathrm{P}_{\lambda})_h-\int fd{\mathsf E} U(A_n)_h|<\epsilon$, we have
{\allowdisplaybreaks
\begin{align*}
    \left|\int f d{\mathsf E} U(A_n)-\int fd\mathrm{GWT}(\mathrm{P}_{\lambda})\right|&\le \left|\int fd{\mathsf E} U(A_n)_h-\int fd{\mathsf E} U(A_n)\right|\\
    &+\left|\int fd\mathrm{GWT}(\mathrm{P}_{\lambda})_h-\int fd\mathrm{GWT}(\mathrm{P}_{\lambda})\right|\\
    &+\left|\int f d\mathrm{GWT}(\mathrm{P}_{\lambda})_h-\int fd{\mathsf E} U(A_n)_h\right|\\
    &<3\epsilon,
\end{align*}}%
which completes the proof.
\end{proof}

\subsection{BC entropy}\label{subsec:BCentropy}
In this section, we review the notion of BC entropy introduced in~\cite{Bordenave_2014}, which is shown to be the fundamental limit of universal lossless compression for certain graph family~\cite{Delgosha--Anatharam2017}.

For a Polish space $\Omega$, let $\mathcal{P}(\Omega)$ denote the set of all Borel probability measures on $\Omega$. Let $A$ be a Borel set in $\Omega$, we define the \emph{$\epsilon$-extension of A}, denoted $A^\epsilon$, as the union of the open balls with radius $\epsilon$ centered around the points in $A$. For two probability measures $\mu$ and $\nu$ in $\mathcal{P}(\Omega)$, we define the \emph{L\'{e}vy--Prokhorov distance} $d_\mathrm{LP}(\mu,\nu):=\inf\{\epsilon>0:\mu(A)\le\nu(A^\epsilon)+\epsilon \text{ and } \nu(A)\le\mu(A^\epsilon)+\epsilon,\forall A\in\mathcal{B}(\Omega)\}$, where $\mathcal{B}(\Omega)$ denotes the Borel sigma algebra of $\Omega$.
Let $\rho\in \mathcal{P}(\mathcal{G}^*)$. Let $d$ be the expected number of neighbours of root under the law $\rho$ and let a sequence $m=m(n)$ such that $m/n\rightarrow d/2$, as $n\rightarrow\infty$. Define
${\mathcal{G}_{n,m}}$ to be the set of graphs with $n$ vertices and $m$ edges. For $\epsilon>0$, define
$${\mathcal{G}_{n,m}}(\rho,\epsilon)=\{G\in {\mathcal{G}_{n,m}}:U(G)\in B(\rho,\epsilon)\},$$
where $B(\rho,\epsilon)$ denotes the open ball with radius $\epsilon$ around $\rho$ with respect to Lévy–Prokhorov metric. Now, we define the \emph{$\epsilon$-upper BC entropy} of $\rho$ as
$${\overline{\Sigma}}(\rho,\epsilon)=\limsup\limits_{n\rightarrow\infty}\frac{\log |{\mathcal{G}_{n,m}}(\rho,\epsilon)|-m\log n}{n}$$
and define the \emph{upper BC entropy} of $\rho$ as
$${\overline{\Sigma}}(\rho)=\lim_{\epsilon\rightarrow 0}{\overline{\Sigma}}(\rho,\epsilon).$$
Similarly we define the \emph{$\epsilon$-lower BC entropy} ${\underline{\Sigma}}(\rho,\epsilon)$ and \emph{lower BC entropy} ${\underline{\Sigma}}(\rho)$ with $\limsup$ replaced by $\liminf$ in above definitions. If $\rho$ is such that ${\overline{\Sigma}}(\rho)={\underline{\Sigma}}(\rho)$, then this common limit is called the \emph{BC entropy} of $\rho$
$$\Sigma(\rho):={\overline{\Sigma}}(\rho)={\underline{\Sigma}}(\rho).$$

The following lemma states the BC entropy of the Galton--Waston tree distribution.
\begin{lem}[Corollary 1.4 of\cite{Bordenave_2014}]\label{SBM_BCentropy}
The BC entropy of the Galton--Watson tree distribution $\mathrm{GWT}(\mathrm{P}_\lambda)$ is given by
$$\Sigma\left(\mathrm{GWT}(\mathrm{P}_\lambda)\right)=\frac{\lambda}{2}\log \frac{e}{\lambda} \quad \mathrm{bits}.$$
\end{lem}

\iffalse
The above definitions on BC entropy are all based on \emph{deterministic} graphs. For a \emph{random} graph $G$, the neighbourhood distribution $U(G)$ is random and therefore the above definition needs to be adjusted.

In the following, we introduce a new notion of BC entropy for random graphs.

Let $G_n$ be a graph generated from stochastic block model $\mathrm{SBM}(n,L,\mathbf{p},\frac{1}{n}\mathbf{Q})$. Let $m=m(n)$ be a sequence such that $m/n\rightarrow \mathbf{p}^T\mathbf{Q}\mathbf{p}/2$. We define the \emph{$\epsilon$-upper BC entropy of stochastic block model}
$${\overline{\Sigma}}\left(\mathrm{SBM},\epsilon\right)=\limsup\limits_{n\rightarrow\infty}\frac{\log |{\mathcal{G}_{n,m}}({\mathsf E} U(G_n),\epsilon)|-m\log n}{n}$$
and the \emph{upper BC entropy of $\mathrm{SBM}(n,L,\mathbf{p},\frac{1}{n}\mathbf{Q})$}
$${\overline{\Sigma}}\left(\mathrm{SBM}\right)=\lim_{\epsilon\rightarrow 0}{\overline{\Sigma}}\left(\mathrm{SBM},\epsilon\right).$$
Similarly, we define the \emph{$\epsilon$-lower BC entropy of stochastic block model} ${\underline{\Sigma}}\left(\mathrm{SBM},\epsilon\right)$ and the \emph{lower BC entropy of stochastic block model} ${\underline{\Sigma}}\left(\mathrm{SBM}\right)$ with $\limsup$ replaced by $\liminf$ in above definitions. If stochastic block model $\mathrm{SBM}\left(n,L,\mathbf{p},\frac{1}{n}\mathbf{Q}\right)$ is such that ${\overline{\Sigma}}\left(\mathrm{SBM}\right)={\underline{\Sigma}}\left(\mathrm{SBM}\right)$, then we define the \emph{BC entropy of stochastic block model}
$$\Sigma\left(\mathrm{SBM}\right):={\underline{\Sigma}}\left(\mathrm{SBM}\right)={\overline{\Sigma}}\left(\mathrm{SBM}\right).$$
Now, we can get the BC entropy of a symmetric stochastic block model in the following Lemma.
\begin{lem}[BC entropy of sparse symmetric SBMs]\label{SBM_BCentropy}
The BC entropy of a symmetric stochastic block model $\mathrm{SBM}\left(n,L,\mathbf{p},\frac{1}{n}\mathbf{Q}\right)$ with $\mathbf{p}=\left(\frac{1}{L},\ldots,\frac{1}{L}\right)$, $\mathbf{Q}_{ii}=a,\forall i\in[n]$ and $\mathbf{Q}_{ij}=b,\forall i,j\in[n],i\neq j$ is given by
$$\Sigma\left(\mathrm{SBM}\right)=\frac{\lambda}{2}\log \frac{e}{\lambda} \quad \mathrm{bits},$$
where $\lambda = \mathbf{p}^T\mathbf{Q}\mathbf{p} = \frac{a+(L-1)b}{L}$.
\end{lem}
\begin{proof}[{\bf Proof of Lemma~\ref{SBM_BCentropy}}]
Let $A_n\sim \mathrm{SBM}\left(n,L,\mathbf{p},\frac{1}{n}\mathbf{Q}\right)$. From Lemma~\ref{LWC_SBM}, we have that ${\mathsf E} U(A_n)\rightsquigarrow \mathrm{GWT}(\mathrm{P}_{\lambda})$. As shown in~\cite{billing}, in  a Polish space, weak convergence of probability measures implies the convergence in L\'{e}vy--Prokhorov distance. Therefore, for any $\epsilon>0$, there exists $n_0$ such that for all $n \ge n_0$,
\begin{equation}
B({\mathsf E} U(A_n),2\epsilon)\supset B(\mathrm{GWT}(\mathrm{P}_\lambda),\epsilon)\supset B({\mathsf E} U(A_n),\epsilon/2).
\end{equation}
By the definition of ${\mathcal{G}_{n,m}}(\rho,\epsilon)$, we have
\begin{equation}
{\mathcal{G}_{n,m}}({\mathsf E} U(A_n),2\epsilon)\supseteq{\mathcal{G}_{n,m}}(\mathrm{GWT}(\mathrm{P}_\lambda),\epsilon)\supseteq{\mathcal{G}_{n,m}}({\mathsf E} U(A_n),\epsilon/2).
\end{equation}
It follows that
\begin{align*}
\frac{\log|{\mathcal{G}_{n,m}}({\mathsf E} U(A_n),2\epsilon)|-m\log n}{n}&\ge \frac{\log|{\mathcal{G}_{n,m}}(\mathrm{GWT}(\mathrm{P}_\lambda),\epsilon)|-m\log n}{n}\\
&\ge \frac{\log|{\mathcal{G}_{n,m}}({\mathsf E} U(A_n),\epsilon/2)|-m\log n}{n}
\end{align*}
for any $n\ge n_0$, where $m$ denotes a sequence $m=m(n)$ such that $m/n\rightarrow\lambda/2$. \textcolor{blue}{Why do we need this condition on $m$? Is (44) true for any $m$?}
Taking the $\limsup$ on $n$ for the inequality gives
$${\overline{\Sigma}}\left(\mathrm{SBM},2\epsilon\right)\ge {\overline{\Sigma}}(\mathrm{GWT}(\mathrm{P}_\lambda),\epsilon)\ge {\overline{\Sigma}}\left(\mathrm{SBM},\epsilon/2\right).$$
Taking the limit $\epsilon$ to zero yields ${\overline{\Sigma}}\left(\mathrm{SBM}\right)\ge {\overline{\Sigma}}(\mathrm{GWT}(\mathrm{P}_\lambda))\ge {\overline{\Sigma}}\left(\mathrm{SBM}\right)$, i.e, ${\overline{\Sigma}}\left(\mathrm{SBM}\right)= {\overline{\Sigma}}(\mathrm{GWT}(\mathrm{P}_\lambda))$. Similarly replace $\limsup$ with $\liminf$ in the above arguments gives ${\underline{\Sigma}}\left(\mathrm{SBM}\right)= {\underline{\Sigma}}(\mathrm{GWT}(\mathrm{P}_\lambda))$. Now, it is shown in Corollary 1.4 of\cite{Bordenave_2014} that the BC entropy of $\mathrm{GWT}(\mathrm{P}_\lambda)$ exists and $\Sigma(\mathrm{GWT}(\mathrm{P}_\lambda))=\frac{\lambda\log e}{2}-\frac{\lambda}{2}\log \lambda\medspace(\mathrm{bits})$. Therefore, the BC entropy of $\mathrm{SBM}\left(n,L,\mathbf{p},\frac{1}{n}\mathbf{Q}\right)$ exists and $$\Sigma\left(\mathrm{SBM}\right)=\frac{\lambda\log e}{2}-\frac{\lambda}{2}\log \lambda\medspace(\mathrm{bits}).$$
\end{proof}
\fi

\subsection{Achieving BC entropy in the sparse regime}\label{subsec:Achieve_BC}
With the Lemma above, we can give a performance guarantee of our algorithm corresponding to the BC entropy. It is a Theorem analog to Proposition 1 in\cite{Delgosha--Anatharam2017}.
\begin{thm}\label{thm:Achieve_BC}
Let $A_n\sim\mathrm{SBM}\left(n,L,\mathbf{p},\frac{1}{n}\mathbf{Q}\right)$ with $\mathbf{p}=\left(\frac{1}{L},\ldots,\frac{1}{L}\right)$, $\mathbf{Q}_{ii}=a,\forall i\in[n]$ and $\mathbf{Q}_{ij}=b,\forall i,j\in[n],i\neq j$. Let $\lambda = \mathbf{p}^T\mathbf{Q}\mathbf{p} = \frac{a+(L-1)b}{L}$ and $m= \binom{n}{2}\frac{\lambda}{n}$ be the expected number of edges in the model. Then, our compression algorithm achieves the BC entropy of the local weak limit of stochastic block models in the sense that
$$\limsup_{n \to \infty}\frac{{\mathsf E}[\ell(C_k(A_n))]-m\log n}{n}\le \Sigma\left(\mathrm{GWT}(\mathrm{P}_\lambda)\right).$$
\end{thm}
\begin{proof}
By our proof of theorem (need to fill in ref), we have
$${\mathsf E}[\ell(C_k(A_n))]\le \binom{n'}{2}H(\mathbf{B}_{12})+2^{k_n^2}\log(2en^3)+nk^2_nH(A_{12}).$$
Notice that
\begin{align*}
    \binom{n'}{2}H(\mathbf{B}_{12})&\le \binom{n'}{2}k_n^2H(A_{12})\\
    &=\binom{n'}{2}k_n^2h(\lambda/n)\\
    &\stackrel{(1)}{=}\binom{n'}{2}k_n^2\left(\frac{1}{n}\lambda\log \frac{ne}{\lambda}+o\left(\frac{1}{n}\right)\right)\\
    &\stackrel{(2)}{\sim} \binom{n}{2}\left(\frac{1}{n}\lambda\log n +\frac{1}{n}\lambda\log \frac{e}{\lambda}+o\left(\frac{1}{n}\right)\right)\\
    &=\binom{n}{2}\frac{1}{n}\lambda\log n+\frac{\lambda\log e-\lambda\log \lambda}{2}n+o(n)\\
    &\stackrel{(3)}{=}m\log n+n\Sigma\left(\mathrm{GWT}(\mathrm{P}_\lambda)\right)+o(n)
\end{align*}
where (1) follows since $h(p)=p\log \frac{e}{p}-\frac{\log e}{2}p^2+o(p^2)$, (2) follows since $n'k_n=n$ and (3) follows from Lemma~\ref{SBM_BCentropy}.
Then it suffices to that the remaining terms in the upper bound of ${\mathsf E}[\ell(C_k(A_n))]$ are all $o(n)$. Indeed we have
\begin{align*}
    2^{k_n^2}\log (2en^3)\le 2^{\delta\log n}\log (2en^3)=n^\delta \log (2en^3)=o(n)
\end{align*}
since $\delta<1$ and
\begin{align*}
    nk^2_nH(A_{12})&=nk^2_nh(\lambda/n)\\
    &=nk^2_n\left(\frac{1}{n}\lambda\log \frac{ne}{\lambda}+o\left(\frac{1}{n}\right)\right)\\
    &\le n\delta \log n \left(\frac{1}{n}\lambda\log \frac{ne}{\lambda}+o\left(\frac{1}{n}\right)\right)\\
    &=\delta\log n \left(\lambda\log \frac{ne}{\lambda}\right)+o\left(\log n\right)\\
    &=o(n).
\end{align*}
\end{proof}

\begin{rem}
For sparse symmetric SBMs, Theorem \ref{thm:Achieve_BC} shows that our compressor achieves the BC entropy of the Galton--Watson tree that is the local weak convergence limit of the underlying sequence of graphs. We note, however, that for the family of sparse symmetric SBMs, it is unclear if this BC entropy is the fundamental limit of lossless compression. This is because the family of sparse symmetric SBMs does not belong to the family of random graphs considered in~\cite{Delgosha--Anatharam2019tit}, where a converse statement can be established.
\end{rem}

\section{Stationarity in the stochastic block model}\label{sec:C1discussion}
In this section, we take a closer look at the correlation among entries in the adjacency matrix and explain why existing universal compressors developed for stationary processes may not be immediately applicable for certain orderings of the entries.

Compressing $A_n$ entails compressing
\[
A_{12},\ldots,A_{1,n},A_{23},\ldots,A_{n-1,n},
\]
i.e. the bits in the upper triangle of $A_n$. Clearly, these are not independent (because of the dependency through $X_1^n$) so one cannot use any of the compressors universal for the class of iid processes to compress $A_n$. So, one hopes that it is possible to list the ${n \choose 2}$ random variables $A_{12},\ldots,A_{1,n},A_{23},\ldots,A_{n-1,n}$ in an order that makes the resulting sequence stationary, so that the Lempel--Ziv compressor (which, recall, is universal for the class of stationary processes) may be used. However, we show now that some of the most natural orders of listing these ${n \choose 2}$ bits result in a sequence that is nonstationary.
\begin{enumerate}
    \item {\bf Horizontally:} Listing the bits in the upper triangle row-wise (i.e. first listing the bits in the first row, followed by the bits in the second and so on, ending with $A_{n-1,n}$) we get the following sequence
    \[
    A_{12},\ldots,A_{1,n},A_{23},\ldots,A_{2,n},\ldots,A_{n-1,n},
    \]
    which can be seen to be nonstationary. Consider the case when $n = 4, L = 2, Q_{11} = Q_{12} = 1,  Q_{12} = 0$. In this case the horizontal ordering is
    \[
    A_{12},A_{13},A_{14},A_{23},A_{24},A_{34}
    \]
    and this is seen to be nonstationary by observing $P(A_{12} = 1 ,A_{13} = 0,A_{14} = 1) > 0$ but $P(A_{23}=1 ,A_{24} = 0,A_{34} = 1) = 0$.

    \item {\bf Vertically:} Listing the bits in the upper triangle column-wise (i.e. first listing the bits in the first column, followed by the bits in the second and so on, ending with $A_{n-1,n}$) we get the following sequence
    \[
    A_{12}, A_{13},A_{23},\ldots,A_{1,n},\ldots,A_{n-1,n},
    \]
    which can be seen to be nonstationary. Consider the case when $n = 4, L = 2, Q_{11} = Q_{12} = 1,  Q_{12} = 0$. In this case the vertical ordering is
    \[
    A_{12},A_{13},A_{23},A_{14},A_{24},A_{34}
    \]
    and this is seen to be nonstationary by observing $P(A_{12} = 1 ,A_{13} = 0,A_{23} = 1) = 0$ but $P(A_{14}=1 ,A_{24} = 0,A_{34} = 1) > 0$.

    \item {\bf Diagonally:} Consider $\lfloor \frac{n}{2} \rfloor$ sequences defined as
\begin{align*}
    S_1 &:= A_{12}, A_{23},A_{34},\ldots,A_{n-1,n},A_{n,1} \\
    S_2 &:= A_{13}, A_{24}, A_{35},\ldots,A_{n-2,n}, A_{n-1,1},A_{n,2} \\
   & \vdots \\
    S_{\lfloor \frac{n}{2} \rfloor-1} &:= A_{1,1+\lfloor \frac{n}{2} \rfloor-1},A_{2,2+\lfloor \frac{n}{2} \rfloor-1},\cdots,A_{n,\lfloor \frac{n}{2} \rfloor-1}
\end{align*}
and

    \[
   S_{\lfloor \frac{n}{2} \rfloor} =\begin{cases}
   A_{1,1+n/2}, A_{2,2+n/2},\ldots,A_{n/2,n}, & \text{ when } n \text{ is even},\\
   A_{1,1+\lfloor \frac{n}{2} \rfloor},A_{2,2+\lfloor \frac{n}{2} \rfloor},\ldots,A_{n,n + \lfloor \frac{n}{2} \rfloor}, & \text{ when } n \text{ is odd}.
   \end{cases}
   \]
  Concatenating $S_1,\ldots,S_{\lfloor \frac{n}{2} \rfloor}$ yields a sequence of length ${n \choose 2}$. This corresponds to listing the bits diagonal-wise. However, even this does not yield a sequence that is stationary which can be illustrated by considering the case when $n = 4, L = 2, Q_{11} = Q_{12} = 1,  Q_{12} = 0$. In this case the diagonal ordering is
    \[
    A_{12},A_{23},A_{34},A_{41},A_{13},A_{24}
    \]
    and this is seen to be nonstationary by observing $P(A_{12} = 0 ,A_{23} = 1,A_{34} = 1) > 0$ but $P(A_{34}=0 ,A_{41} = 1,A_{13} = 1) = 0$.
\end{enumerate}

\section{Experiments}\label{sec:experiments}
We implement the proposed universal graph compressor (UGC) in four widely used benchmark graph datasets: protein-to-protein interaction network (PPI)~\cite{Grover--Leskovec2016}, LiveJournal friendship network (Blogcatalog)~\cite{Tang--Liu2009}, Flickr user network (Flickr)~\cite{Tang--Liu2009}, and YouTube user network (YouTube)~\cite{Nandanwar--Murty2016}. The block decomposition size $k$ is chosen to be $1,2,3,4$ and we present in Table~\ref{tab:UGC} the compression ratios (the ratio between output length and input length of the encoder) of UGC for different choices of $k$. We present in Table~\ref{tab:simulation} the compression ratios of four competing algorithms.

\begin{table}[htbp]
	\centering
	\begin{tabular}{||c |c | c | c | c ||}
		\hline
		& $k=1$  & $k=2$ & $k=3$ & $k=4$  \\
		\hline
		PPI & 0.0228 & $\mathbf{0.0226}$ & 0.0227 & 0.034 \\
		\hline
		Blogcatalog & 0.0275 & 0.0270 & $\mathbf{0.0267}$ & 0.0288\\
		\hline
		Flickr & 0.00960 & 0.00935 & 0.00915 & $\mathbf{0.00907}$ \\
		\hline
		YouTube & $4.51 \times 10^{-5}$ & $4.11 \times 10^{-5}$ & $\mathbf{3.98 \times 10^{-5}}$ & $4.00 \times 10^{-5}$\\
		\hline
	\end{tabular}
	\caption{Compression ratio of UGC under different $k$ values.}\label{tab:UGC}
\end{table}
\begin{table}[htbp]
	\centering
	\begin{tabular}{||c  | c | c | c | c||}
		\hline
		& CSR & Ligra+ & LZ & PNG  \\
		\hline
		PPI  & 0.166 & 0.0605 & {0.06} & 0.089  \\
		\hline
		Blogcatalog & 0.203 & {0.0682} & 0.080 & 0.096 \\
		\hline
		Flickr & 0.0584 & 0.0217 & 0.0307 & 0.0262 \\
		\hline
		YouTube & $3.23\times 10^{-4}$ & $9.90\times 10^{-5}$& $1.09\times 10^{-4}$ & $1.10\times 10^{-3}$ \\
		\hline
	\end{tabular}
	\caption{Compression ratios of competing algorithms.}\label{tab:simulation}
\end{table}
\begin{itemize}
	\item CSR: Compressed sparse row is a widely used sparse matrix representation format. In the experiment, we further optimize its default compressor exploiting the fact that the graph is simple and its adjacency matrix is symmetric with binary entries.
	\item Ligra+: This is another powerful sparse matrix representation format~\cite{Shun--Blelloch2013,Shun--Dhulipala--Blelloch2015}, which improves upon CSR using byte codes with run-length coding.
	\item LZ: This is an implementation of the algorithm proposed in~\cite{Lempel--Ziv86}, which first transforms the two-dimensional adjacency matrix into a one-dimensional sequence using the Peano--Hilbert space filling curve and then compresses the sequence using Lempel--Ziv 78 algorithm~\cite{Lempel--Ziv78}.
	\item PNG: The adjacency matrix of the graph is treated as a gray-scaled image and the PNG lossless image compressor is applied.
\end{itemize}
The compression ratios of the five algorithms implemented on four datasets are given as follows. The proposed UGC outperforms all competing algorithms in all datasets. The compression ratios from competing algorithms are 2.4 to 27 times that of the universal graph compressor.

Note, however, that CSR and Ligra+ are designed to enable fast computation, such as adjacency query or vertex degree query, in addition to compressing the matrix. Our proposed compressor does not possess such functionality and is designed solely for compression purpose.

\section*{Acknowledgment}
L. Wang would like to thank Emmanuel Abbe and Tsachy Weissman for stimulating discussions in the initial phase of the work. She is grateful to Young-Han Kim and Ofer Shayevitz for their interest and encouragement in this result. C. Wang would like to thank Richard Peng for his suggestion in writing.

\bibliographystyle{IEEEtran}

redpajama_set_name: RedPajamaArXiv


text:
Q: Echo variable from frontend in widget dashboard form I create a WordPress widget and want to echo $widget_id variable inside
   function form($instance);

to be visible inside WP dashboard. Variable exists https://codex.wordpress.org/Function_Reference/wp_add_dashboard_widget and is echoed in frontend using
 function widget( $args, $instance )

without issues. Is that possible? (when I try to echo variable I get notice that variable is undefined, and it is not displayed)

A:  function my_function( $widget, $return, $instance ){
   echo $widget->id;
 }
 add_action( 'in_widget_form', 'my_function', 1, 3 );

redpajama_set_name: RedPajamaStackExchange


I'm not sure what it was about the blurb that captured my attention, but I'm so glad it did. I have not read romantic suspense in a while and I realize now that I've missed it. Also, I had no issues reading this out-of-order. The author gives us enough within this story that it all makes sense.
In a nutshell, Angie Pallorino is an ex-detective who was let go after shooting and killing a suspect when she went a bit rogue on a case she had been working on. Additionally, that case brought forth certain truths about her own past that she was completely unaware of. She is attempting to rebuild her career in private investigations and is currently working with a company called Coastal Investigations, but only until she has enough hours under her belt. After that, she plans to strike out on her own.
Angie is in a relationship with Det. James Maddocks, who she had previously worked with while on the force. They are in love, but Angie is struggling with recent events, the loss of her job and rebuilding her career. In an attempt to spend quality time, they go away for a long weekend to camp and fish. On their last night while packing up to leave, they hear a man screaming for help. He was out along the banks of the Nahamish River harvesting wild mushrooms when he stumbles upon partially unearthed human remains. An autopsy reveals the body to be that of Jasmine Gulati, who was seen going over the falls in 1994, 24 years before.
What follows is an incredibly twisted story with multiple layers of deception, revealed slowly and in such a way that it kept me guessing until nearly the end. I love to guess the outcome when reading RS, but my first choice of the "killer" was off; and while I admit to figuring out part of the details about who killed Jasmine, there was so much more to it. So many secrets, not only about what happened to Jasmine and who killed her, but the lengths people will go to protect those they love. Add to that, a small town where everyone knows everyone and you've got the perfect recipe for a big cover up where more than just the killer is at fault. Beyond the murder, you have the story of the women who were with Jasmine on the fated fishing trip that took her life, as well as some crossover between other cold cases. White spins a fantastic mystery with awesome connectivity between all the pieces. I will definitely be reading the prior two books and look forward to more from this author.
Note: While there is an element of romance in this story I wanted to note that Angie and Maddocks while together at the beginning of the story, take a break right after their weekend trip when the body is found. Angie is struggling to commit, so Maddocks, frustrated, puts the relationship ball in her court. They are apart through the whole book until nearly the end when everything is wrapped up and they do appear together in the epilogue.
This was an interesting take on the theme of Beauty and the Beast. Isabelle "Belle" Reading finds herself homeless when her dad kicks her out of the house because he's not happy with her choice of friends and the business that she's started with them-The Naughty Princess Club. Belle is devastated. She has no money to get a place of her own, she can't ask her friends who have financial problems of their own, and all her hopes of saving her beloved library are going down the drain. She begins to sleep at the library while she tries to figure out what to do next.
Vincent "Beast" Adams comes through big time when he realizes Belle has been sleeping at the library. He offers her a place to stay while she figures things out. Vincent is the bouncer at a club in town and while Belle knows him, she confused by his offer. Since she has no other prospects, she accepts.
I'm not sure what it was about the blurb that made me want to read this story. I've stayed away from stories that use fairytales blatantly as a theme. In this one, our H/H are even named Belle and Beast. Perhaps I was intrigued by the fact that these young women who meet in book 1, find a fast friendship in their common struggles and decide to start a princess themed stripping business because why not??? Though the Disney franchise would probably have a cow!
I took a while to actually "get" this pairing. I'm not sure if it's because I had not read the previous book and the relationship dynamic had already been established for Belle and Vincent. As the story moves forward, though, I came to enjoy them as a couple. Belle comes off as a bit naive and Vincent's beasty-ness is really just based on his physical size. I guess it's a good name for a bouncer at a club. I warmed to Vincent so much more once we get into his back story and I could understand where his head is at. It certainly confirms the "don't judge a book by it's cover" where Vincent is concerned-because he was so much more and he and Belle are well suited.
Cute story with humorous moments with a feel-good-girlfriends theme.


text:
Your Say: What do Fakenham people think of Norwich Street 'carbuncle'?
Published: 7:00 AM December 4, 2021
We spoke to people in Fakenham to get their thoughts on 9 Norwich Street. - Credit: Aaron McMillan
It has been described as a carbuncle by Fakenham's mayor, but what do residents make of the dilapidated property on Norwich Street?
The building in Fakenham was issued with a notice of intention to carry out urgent works on October 19, meaning it had 28 days to either secure a plan in order to fulfil the requirements set out by North Norfolk District Council (NNDC) or launch an appeal with the Secretary of State.
Our reporter, Aaron McMillan, spoke to people in the market town to get their thoughts.
Pearl Cooper, 77, from Fakenham. - Credit: Aaron McMillan
Pearl Cooper, 77, from Fakenham, said: "It is absolutely diabolical. It makes you wonder why you pay council tax. It is absolutely horrendous."
Robert Robinson, 72, from Hempton. - Credit: Aaron McMillan
Robert Robinson, 72, from Hempton, said: "I would like to see it kept, but it needs major renovation. I think the shop front would be lovely. It could be turned into a lovely business if they could do something about the building."
Sue Oakley, 68, from Hempton. - Credit: Aaron McMillan
Sue Oakley, 68, from Hempton, said: "It is a mess and an eyesore. I would like to keep it, but it needs major refurbishment - it could be made fit again. I think it would be a nice building."
Liz Jones, 59, from Great Ryburgh. - Credit: Aaron McMillan
Liz Jones, 59, from Great Ryburgh, said: "It feels a shame that it looks like that. I'm not sure how it is still standing. It is such a shame it is left like this."
Anne Lejeune, 68, from Fakenham. - Credit: Aaron McMillan
Anne Lejeune, 68, from Fakenham, said: "I think something should be done about it. I am not sure how long it has been like this, but a few years I think - I cannot remember. It seems like it has always been like this now."
Jill Delaney, from Fakenham. - Credit: Aaron McMillan
1 School heads reveal feeling of 'positivity' at start of term
2 Two rescued from sinking fishing boat
3 The day Linda McCartney flew into Fakenham
4 Headteacher says 'good' Ofsted rating a testament to hard work
6 MAPPED: Where thousands of homes could be built in north Norfolk
8 Boris Johnson expected to announce easing of Covid-19 Plan B restrictions
9 'Over the moon' - Widower drums up £1,000 for caring hospice
10 Brass band's search for new members as older players put off by Covid
Jill Delaney, from Fakenham, said: "It is an eyesore, and has been like that for a little while. It just lets down the whole street."

redpajama_set_name: RedPajamaCommonCrawl


text:
Tishman Speyer attempting to revive Hudson Yards deal
TISHMAN SPEYER IS TRYING TO RESUSCITATE ITS DEAL with the Metropolitan Transportation Authority to develop Hudson Yards after the MTA declared an impasse in negotiations last week. Mayor Michael Bloomberg, who is in Europe this week, was meeting Friday in London with Tishman principal Jerry Speyer, who flew in from Milan. In New York today, Tishman representatives will meet with the MTA to search for common ground. The transportation agency said last week that it was willing to start talking with other bidders—presumably The Durst Organization and Vornado Realty Trust, which made a joint proposal, and The Related Companies—but has yet to reach out to them.
SEN. CHARLES SCHUMER IS EXPECTED TO PROPOSE IDEAS to keep the big West Side projects on track at a Crain's New York Business breakfast forum today at the Grand Hyatt, beginning at 8:30 a.m. Moynihan Station and the Jacob K. Javits Convention Center are likely to be on his agenda. For a full report on his speech, check www. crainsnewyork.com.
THE REALTY ADVISORY BOARD AND SEIU LOCAL 32BJ WILL resume contract negotiations Tuesday, two days before a deal covering 1,500 private security officers at buildings across the city is set to expire. The RAB deal is the first of several security contracts, covering 4,000 guards that is due to run out between now and August. The union rejected a late-April offer from RAB that did not provide cost-of-living increases.
MAJOR LEAGUE BASEBALL'S ALL-STAR GAME AT YANKEE Stadium is the hottest ticket for corporate events in 2008, according to a nationwide survey of more than 250 corporate travel managers released this month by TSE Sports & Entertainment. The game is beating out the 2008 Summer Olympics in Beijing and Super Bowl XLII in Glendale, Ariz.
THE 2007-08 TELEVISION SEASON STILL HAS A FEW weeks to go, but the cable networks are already claiming victory over the broadcast networks. According to Turner Research, part of Time Warner's cable networks division, the big four networks saw the number of 18- to 49-year-old viewers—the audience most desired by advertisers—fall by 10% to 15.4 million through May 4. Their share was 32%. Meanwhile, advertising-supported cable increased its prime-time share of the 18- to 49-year-old audience to 47%, from 43%. The analysis is based on Turner's reading of Nielsen Media Research numbers.
BURMESE GROUPS IN NEW YORK ARE ORGANIZING RALLIES and vigils to raise money for the victims of Cyclone Nargis in Myanmar. Late last week, the U.S. Campaign for Burma held a demonstration outside the United Nations in an attempt to push the Burmese junta to give aid workers access to the worst-hit areas. Earlier in the week, a group of Buddhist monks in Queens and the Myanmar Baptist Church started raising funds. Several other religious and activist groups, including the New York Burma Roundtable and the National Burma Action Committee, are also organizing relief efforts.
Developer reveals new look for Hudson Yards district office tower
Sponsored Content: 2019: a year of action