title: Type Size Code for Compressing Erdös-Rényi Graphs
authors: Nematollah Iri
text: 
  
  A Self-Reasoning Framework for Anomaly Detection Using Video-Level Labels
      Muhammad Zaigham Zaheer, Arif Mahmood, Hochul Shin and Seung-Ik Lee
  This work is supported by the ICT R&D program of MSIP/IITP. [2017-0-00306, Dvlp. of Multimodal Sensor-based Intll. Sys. for Outdoor Surveillance Robots]. We thank Jin-ha Lee & Marcella Astrid for their dedicated help.
  M. Zaigham Zaheer, Hochul Shin and Seung-Ik Lee are with the Electronics and Telecommunications Research Institute(ETRI) and the University of Science and Technology (UST), Daejeon, Korea. mzz@ust.ac.kr, {creatrix, the_silee}@etri.re.kr.
  Arif Mahmood is with the Information Technology University, Lahore, Pakistan. rfmahmood@gmail.com.
  
  
      Aug. 2020
  ====================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================
  
  
  
  
  
  We consider universal source coding of unlabeled graphs which are commonly referred to as graphical structures. We adopt an Erdös-Rényi model to generate the random graphical structures. We propose a variant of the previously introduced Type Size code, where type classes are characterized based on the number of edges of the graphical structures. The proposed scheme sorts the graphical structures based on the size of their type classes and assigns binary sequences to them in this order. The ϵ-coding rate of the Type Size code (up to the third-order term) for compressing graphical structures is derived.
  
  
  
  
  
  
  
  
  
  
  
  
  § INTRODUCTION
  
  Many problems in social networks, world wide web, recommendation systems, biology and etc., reduce to computations and processings over graphs. With the emergence of big data, such graphs may contain trillion edges. Moreover, next generation applications in the big data era, enforce more stringent I/O access and latency requirements. Therefore, new methods for compressing such massive graphs are essential for retrieval and processing over short time scales.
  
  We aim at compressing the underlying graph up to isomorphism, i.e. to compress the structure of the graph. Many works, such as those in the area of graph summarization <cit.>, consider the compressed version of the graphical structure to be a graph itself <cit.>. Other works, such as <cit.>, follow an information theoretic paradigm, where the graph structure is mapped into binary strings. We focus on lossless graph compression to faithfully recover the original graph structure from its encoded bits. Numerous lossless graph compression algorithms have been proposed in the literature. See <cit.>, for an exhaustive survey on the existing works, .
  
  Prefix-free assumption has been traditionally imposed to unambiguously decode the block of codewords. However, for many applications in storage and retrieval, there are out-of-band markers to navigate the boundaries of the data to be compressed, hence, one may relax the prefix-free assumption for compression. Such a compression is referred to as one-to-one coding <cit.>.
  
  We follow a universal one-to-one source coding setup, where the underlying probability distribution generating the data is arduous to estimate or unknown, yet presumed to belong to a known class of distributions. A universal one-to-one compression scheme has been first introduced in <cit.>— the Type Size (TS) code— to optimally compress the class of all stationary memoryless sources. TS code, universally orders sequences based on the size of their type classes, and subsequently map them to binary strings in a lexicographic order. The result in <cit.> shows a gain of logarithmic order in the input size by relaxing the prefix-free assumption.
  
  There is an underlying flexibility in defining type classes from a TS code perspective. In fact, the one-to-one compression problem is equivalent to characterizing the type classes that lead to optimal performance <cit.>. Characterizing the type classes based on the empirical probability mass function of the sequences is shown to be optimal for compression of the class of all i.i.d. <cit.> and Markov <cit.> sources over a finite alphabet, while the quantized type classes <cit.> are shown to be optimal for compression of the parametric exponential family of distributions.
  
  We adopt the TS approach for compressing unlabeled Erdös-Rényi graphs, which we refer to as graphical structures, with an unknown edge probability of p. We define two graphical structures to be in the same type class if and only if they have the same number of edges. Note that two graphical structures within a type class have the same probability regardless of the enforced Erdös-Rényi model. We order the graphical structures based on the size of the type class they belong to, from smallest to largest, and subsequently map them to binary strings lexicographically (See Figure <ref> for an example). We show that with probability at least (1-ϵ), the TS code requires at most
  
      n 2 H(p) + σ(p)√(n 2)Q^-1(ϵ) -logn! + 𝒪(1)
  
  bits, to compress a graphical structure with n nodes, where H(p) and σ^2(p) are the entropy and the varentropy of the underlying Erdös-Rényi model p, respectively. The first and third-order terms in (<ref>) do match with an earlier result in <cit.>. However, we depart from an average case analysis in <cit.> to a probabilistic analysis.
  
  The required memory to store the TS code ordering grows super-exponentially with the graph size [The size of a graph is the number of its nodes.]. Even though, this memory requirement may sound prohibitive, however, many applications may afford this storage requirement in order to achieve the rate optimality. A few examples include but are not limited to
  
  
    * Long distance communications such as satellite communications,
  
    * Transmission over VLF and ELF frequencies which offer a very low bandwidth. Optimal-rate compression comes into awareness in such scenarios, since one can transmit only a limited few (hundreds) bits in a minute.
  
  
  The rest of the paper is organized as follows. We introduce the lossless source coding of the graphical structures and related definitions in Section <ref>. In Section <ref>, we describe the Type Size code and provide tight bounds on the type class sizes. In Section <ref>, we present the main theorem of the paper which is proved in Section <ref>. We conclude in Section <ref>.
  
  
  
  
  
  § PRELIMINARIES
  
  
  We adopt an Erdös-Rényi graph generation mechanism <cit.>, i.e., there is a simple undirected edge between pairs of nodes, independently with probability p. The structure of the graph is derived by removing the vertex labels. Let 𝒮(n) (resp. 𝒢(n)) be the set of simple Erdös-Rényi graphical structures (resp. labeled graphs) on n vertices. For a structure S∈𝒮(n), we define it's size as the number of vertices and ȷ(S) captures the number of edges in S. When it is clear from the context we simplify ȷ(S) as ȷ. For notational convenience, denote m=n2. Let π = π_1,π_2,...,π_m be an arbitrary ordering of pairs of nodes in G. Construct a sequence X_i,  i=1,⋯, m as follows: X_i=1, if there is an edge between pair of nodes corresponding to π_i, and 0 otherwise. Let x_i, i=1,...,m denote a realization of X_i for an observed G. Since X_i's are i.i.d., let X (resp. p(X)) be a random variable (resp. probability distribution) representing the underlying model of X_i's, i.e. p(X=1) = p(X_i=1)=p, i=1⋯ m. Denote ℬ as the class of all Bernoulli distributions over {0,1}. Let 𝔼 and 𝕍, denote expectation and variance with respect to p(X), respectively.
  
  We consider a source coding scheme which maps graphical structures in 𝒮(n) to variable length binary strings via a coding function
  
      ϕ: 𝒮(n)→{0,1}^* = {∅, 0, 1, 00, 01,10,11,000, ···}.
  
  
  We do not impose the prefix-free condition on the coding scheme. Let l(ϕ(S)) be the length of the compressed binary string. For any S∈𝒮(n), the underlying Erdös-Rényi model induces a probability distribution ℙ_S on the structures within 𝒮. We evaluate the performance of coding schemes through the ϵ-coding rate for graphs of size n given by
  
  
      R_n(ϵ,ϕ, p)=1/n 2min{k: ℙ_S(ℓ(ϕ(S))≥ k )≤ϵ}.
  
  
  
  
  § TYPE SIZE CODE
  
  
  
  
   §.§ Type Size Code
  
  
  For the class of all memoryless sources over a finite alphabet, the fixed-to-variable TS code
  is introduced in <cit.>, which sorts sequences based on the size of their elementary type classes (from
  smallest to largest) and then encodes sequences to variable-length bit-strings in this order. We borrow the framework of the TS code, however, for the purpose of compressing graphical structures we define two graphical structures to be in the same type class if and only if they have the same number of edges, i.e. T_S = {S'∈𝒮(n): ȷ(S) = ȷ(S')}, where T_S denotes the type class of S. We then sort graphical structures based on their type class sizes and map them to binary strings according to this type class size ordering. See Figure <ref> for an example of the TS code for compressing graphical structures of size n=4.
  
  <cit.>
  For the TS code
  
      R_n(ϵ,ϕ,p)≤1/n 2⌈logM(ϵ)⌉
  
  where
  
      M(ϵ)=inf_γ:ℙ_S(1/n 2log|T_S|>γ)≤ϵ∑_S∈𝒮(n): 
      1/n 2log|T_S|≤γ|T_S|.
  
  
  
  
  
  
   §.§ Type Class Size
  
  
  Let N(n,ȷ) be the number of graphs with n unlabeled nodes and ȷ simple undirected edges. Let
  
      Λ(n,ȷ)=n2ȷ/n!
  
  and
  
      μ = 2ȷ/n - log n.
  
  The following theorem by Wright <cit.>, gives the number of graphical structures for a given number of nodes and edges.
  <cit.>
  For a constant C_0 independent of n,
  
      N(n,ȷ) = Λ(n,ȷ)(1+𝒪(e^-C_0μ)),
  
  if and only if μ→∞ as n→∞.
  
  Let ℰ be the event where the condition of Theorem <ref> is not satisfied, i.e. lim_n→∞μ < ∞. In the following lemma, we show that the necessary and sufficient condition of Theorem <ref> is satisfied with high probability. The proof is an straightforward application of Chernoff bound <cit.> and is provided in Appendix <ref>.
  
  
  
  There exist constants 0<δ_1, δ_2<1 which are independent of n, such that
  
      ℙ_S(ȷ(S)≤ (1-δ_1)n 2p) ≤ e^-n 2δ_2.
  
  
  
  Size of the type class of S, |T_S| is then given by
  
      log|T_S|   =logN(n,ȷ)
         =logn2ȷ-logn!+𝒪(1)
  
  where 𝒪(1) term is (with an abuse of notation) bounded between two positive constants independent of n.
  
  Let ȷ^c = m-ȷ. Define empirical entropy of the graphical structure S as
  
      H_empirical(S) = -ȷ/mlogȷ/m - ȷ^c/mlogȷ^c/m.
  
  
  The following lemma provides upper and lower bounds on the size of the graphical type class.
  
  
  With probability at least 1-e^-n 2δ_2, we have the following upper and lower bounds for the size of the type class of a graphical structure S∈𝒮(n):
  
      n2H_empirical(S)-log n! +C_L ≤log|T_S|≤n2H_empirical(S)-logn! + C_U
  
  where C_L, C_U are constants independent of n and δ_2 is the constant in Lemma <ref>.
  
  
  See Appendix <ref>.
  
  
  
  
  
  § MAIN RESULT
  
  
  Let H(p) = 𝔼(log1/p(X)) be the entropy of the underlying source generating the Erdös-Rényi graph, and σ^2(p)=𝕍(log1/p(X)) be the varentropy of it. The following theorem provides an achievability bound for the rate of the TS code in compressing graphical structures.
  
  
  For the TS code and any Bernoulli distribution p∈ℬ,
  
      R_n(ϵ,ϕ,p) ≤  H(p) + σ(p)/√(n 2)Q^-1(ϵ) -logn!/n 2 + 𝒪(1/n^2).
  
  
  
  
  
  § PROOF OF THEOREM
  
  
  When it is clear from the context, we omit the underlying distribution and denote H:=H(p) and σ:=σ(p). For a constant A>0 defined in the Berry-Esséen Lemma <ref> (See Appendix <ref>) which is independent of n, let
  
      γ = H + σ/√(m)Q^-1(ϵ-A/√(m)-e^-mδ_2) - log n!/m +C_U/m
  
  where δ_2, C_U are the constants in Lemmas <ref> and <ref>, respectively. Denote
  
      p_γ  := ℙ_S(log|T_S| > mγ).
  
  Let q_S(X) be a derived Bernoulli distribution from the structure S, such that q_S(0)=ȷ^c/m and q_S(1) = ȷ/m. It is clear that
  
      H_empirical(S) = 1/m∑_i=1^m-log q_S(x_i).
  
  Let
  
      S_m = 1/σ(p)√(m)∑_i=1^m(-logq_S(x_i)-H(p)).
  
  
  
  Recall ℰ from Subsection <ref>. We have
  
      p_γ   = ℙ_S(log|T_S|>mγ | ℰ^c) ℙ_G(ℰ^c) + ℙ_S(log|T_S|>mγ | ℰ) ℙ_G(ℰ) 
         ≤ℙ_S (H_empirical(S)  >  H(p) + σ(p)/√(m) Q^-1(ϵ-A/√(m)-e^-mδ_2)) + e^-mδ_2
         = ℙ(S_m >  Q^-1(ϵ-A/√(m)-e^-mδ_2)) + e^-mδ_2
         ≤ Q( Q^-1(ϵ-A/√(m)-e^-mδ_2)) +A/√(m) + e^-mδ_2
         = ϵ
  
  where (<ref>) follows from the law of total probability, (<ref>) follows from upper bounding ℙ(ℰ^c) and ℙ(log|T_G|>mγ | ℰ) by 1 in conjunction with Lemma <ref>, (<ref>) is from the definitions (<ref>) and (<ref>), and finally (<ref>) is from the Berry-Esseen theorem <cit.> (See Appendix <ref>). We now bound M(ϵ) using (<ref>) with this choice of γ. Let
  
      f(S) = H_empirical(S) - logn!/m + C_U/m.
  
  Similarly, with an abuse of overloaded notation [The two definitions of the function f(·) should be distinguished based upon their arguments.], for any Bernoulli distribution p∈ℬ, define
  
      f(p) = H(p) - logn!/m + C_U/m.
  
  
  The rest of the proof is similar to <cit.>, however, we continue the proof for completeness.
  
   <cit.>
  
  There exists a Lipschitz constant K_0 independent of n, such that for any two Bernoulli distributions p, p̃∈ℬ,
  
      |f(p)-f(p̃)|≤ K_0 p-p̃.
  
  
  
  
  Fixing Δ=1/m, we have
  
      M(ϵ)    ≤∑_S∈𝒮(n):
      1/mlog|T_S|≤γ|T_S|
         ≤∑_S∈𝒮(n):
       f(S) -C_d/m≤γ2^mf(S)
         = ∑_i=0^∞∑_S∈𝒮(n):
       f(S)∈𝒜_i 2^mf(S)
         ≤∑_i=0^∞|{S∈𝒮(n):f(S)∈𝒜_i}| ·  2^mγ+C_d - miΔ
  
  where C_d=C_U-C_L and 𝒜_i = (γ +C_d/m-(i+1)Δ, γ +C_d/m-iΔ]. For a Bernoulli distribution p∈ℬ, define its 2-norm ball of radius r as B_r(p) = {p'∈ℬ: p-p'≤ r}. By extension, for a graphical structure S∈𝒮(n), define its 2-norm ball of radius r as B_r(S) := B_r(q_S), where q_S is the derived empirical distribution of S as defined at the beginning of this section. Note that for any two different structures S_1, S_2 ∈𝒮(n), B_1/2m(S_1) and B_1/2m(S_2) are disjoint. Moreover, observe that Vol(B_1/2m(S)) = 1/m.
  We have
  
      |{S∈𝒮(n):f(S)∈𝒜_i}|   =∑_S∈𝒮(n):
      f(S)∈𝒜_iVol(B_1/2m(S))/1/m
         = m∑_S∈𝒮(n):
      f(S)∈𝒜_iVol(B_1/2m(S))
         = mVol(⋃_S∈𝒮(n):
      f(S)∈𝒜_iB_1/2m(S))
         ≤ mVol(⋃_p∈ℬ:
      f(p)∈𝒜_iB_1/2m(p))
  
  where (<ref> is from disjointness of the balls. Let ρ(λ)=Vol{p∈ℬ:f(p)≤λ}. The following lemma from <cit.>, shows the Lipschitzness of ρ(·).
  <cit.>
  
  There exists a Lipschitz constant K_1 such that for all a,b,
  
      |ρ(a)-ρ(b)|≤ K_1|a-b|.
  
  
  
  We continue from (<ref>). Let a = γ +C_d/m-(i+1)Δ. We have
  
      |{S∈𝒮(n):f(S)∈𝒜_i}|    ≤ m·Vol(⋃_ a<f(p)≤ a+ΔB_1/2m(p)) 
         ≤ mVol({p:f(p)∈(a- K_0/2m,a+Δ+ K_0/2m)}) 
         = m(ρ(a+Δ+K_0/2m)-ρ(a-K_0/2m)) 
         ≤ mK_1K_0·(Δ+K_0/m)
  
  where (<ref>) is from the observation that for any p̃∈ B_1/2m(p), |f(p̃)-f(p)|≤K_0/2m and (<ref>) is from Lemma <ref>. Applying (<ref>) to (<ref>), we obtain
  
      M(ϵ)    ≤∑_i=0^∞ mK_1K_0·(Δ+K_0/m)· 2^mγ +C_d-miΔ
         = mK_1K_0·(Δ+K_0/m)· 2^mγ+C_d·1/1-2^-mΔ.
  
  Since Δ=1/m, we have
  
      logM(ϵ)
      					   ≤log(K_1K_0(K_0+1)) +mγ  + C_d + 1 
         =mH(p)+σ√(m)Q^-1(ϵ-A/√(m)-e^-mδ_2) -logn!+ C_U +C_1 
         ≤ mH(p)+σ√(m)Q^-1(ϵ)-logn!+C
  
  for constants C_1,C independent of n.
  
  
  
  
  § CONCLUSION AND FUTURE WORK
  
  
  We proposed a variant of the Type Size code for compressing graphical structures. Erdös-Rényi model is adopted as the underlying mechanism for generating the random graphs. We provided an analysis to derive the fine asymptotics of the overflow rate of the proposed Type Size code for compressing such structures. However, Erdös-Rényi model fails to fully represent the real-world networks such as the world wide web. The alternative models include the power law and the preferential attachment models. We study the finite blocklength compression of graphical structures not generated by the Erdös-Rényi model as a future work. The multigraph version of the problem, which permits multiple edges between pairs of nodes and the lossy version of the problem are also interesting future directions of this research.
  IEEEtran
  
  
  
  
  
  
  § PROOF OF LEMMA <REF>
  
  
  Observe that the number of edges in the Erdös-Rényi graph can be derived as the sum of m i.i.d. random variables X_i, defined in Subsection <ref>, i.e. ȷ(S) = ∑_i=1^m X_i. For positive α,t>0, from Chernoff bound <cit.>, we have
  
      ℙ_S(ȷ(S)≤α) ≤min_t>0 e^tα∏_i𝔼(e^-tX_i).
  
  On the other hand
  
      𝔼(e^-tX_i)    = pe^-t + (1-p) 
         = 1+ p(e^-t-1) 
         ≤ e^p(e^-t-1)
  
  where (<ref>) follows from ln x≤ x-1, for any positive x>0. Hence
  
      ℙ_S(ȷ(S)≤α) ≤min_t>0 e^tα· e^mp(e^-t-1).
  
  Since (<ref>) holds for any α,t>0, therefore, we may take α=(1-δ_1)mp and t= -ln(1-δ_1)>0, for an arbitrary 0< δ_1 < 1. Subsequently, we obtain
  
      ℙ_S(ȷ(S)≤ (1-δ_1)mp)    ≤(1/1-δ_1)^(1-δ_1)mp e^-mpδ_1
         = e^-mδ_2
  
  where δ_2 = -δ_1 - (1-δ_1)ln(1-δ_1)>0 is a positive constant.
  
  
  
  § PROOF OF LEMMA <REF>
  
  
  Utilizing Theorem <ref>, we proceed by providing tight upper and lower bounds for Λ(n,ȷ) in (<ref>).
  Upper Bound:
  
  Recall ȷ^c=n 2-ȷ. Using the Stirling's formula <cit.>, we have
  
      logn2ȷ   =logn2 !/ȷ!(n 2 -ȷ)!
         ≤log√(2π)n 2 ^n 2+1/22^-n 2+1/12n 2/(√(2π)ȷ^ȷ+1/22^-ȷ+1/12(ȷ+1))(√(2π)ȷ^c^ȷ^c+1/2e^-ȷ^c+1/12(ȷ^c+1))
         = (n 2+1/2)logn 2-n 2+1/12n 2-(ȷ+1/2)logȷ + ȷ -1/12(ȷ+1) -(ȷ^c+1/2)logȷ^c + ȷ^c - 1/12 (ȷ^c+1) - log√(2π)
         ≤(n 2+1/2)logn 2-(ȷlogȷ+ȷ^clogȷ^c)-1/2(logȷ+logȷ^c)+1/12-log√(2π).
  
  Recall q_S∈ℬ, a derived Bernoulli distribution with q_S(X=0)=ȷ^c/n 2 and q_S(X=1)=ȷ/n 2, with an entropy H(q_S)=H_empirical(S). Note that
  
      -ȷlogȷ-ȷ^clogȷ^c   = -n 2ȷ/n 2logȷ/n 2-n 2ȷ^c/n 2logȷ^c/n 2 -ȷlogn 2-ȷ^clogn 2
         =n 2H_empirical(S)-n 2logn 2.
  
  Without loss of generality, we assume 0<ȷ,ȷ^c<n 2. This can be accommodated by adding two extra header bits to the compressed data stream, to indicate if the graph is empty, complete, or else. Hence, we have
  
      logȷ + logȷ^c≥logn 2-1.
  
  (<ref>) in conjunction with (<ref>, <ref>), gives the upper bound.
  
  Lower Bound: 
  
  Using the Stirling's formula <cit.>, we have
  
      logn2ȷ   =logn2 !/ȷ!(n 2 -ȷ)!
         ≥log√(2π)n 2 ^n 2+1/22^-n 2+1/12(n 2+1)/(√(2π)ȷ^ȷ+1/22^-ȷ+1/12ȷ)(√(2π)ȷ^c^ȷ^c+1/22^-ȷ^c+1/12ȷ^c)
         = (n 2+1/2)logn 2-n 2 + 1/12(n 2 + 1)-(ȷ+1/2)logȷ+ȷ-1/12ȷ-(ȷ^c+1/2)logȷ^c+ȷ^c-1/12ȷ^c -log√(2π)
         =(n 2+1/2)logn 2-(ȷlogȷ+ȷ^clogȷ^c)-1/2(logȷ+logȷ^c)-1/6-log√(2π).
  
  Moreover, note that
  
      logȷ + logȷ^c≤1/2logn 2.
  
  The rest of the proof is similar to the proof of the upper bound.
  
  
  
  § BERRY-ESSÉEN BOUND
  
  
  <cit.>
  Let {Z_i} be independent and identically distributed random variables with zero mean and unit variance, and let Z̃ be a standard normal. Then, for a constant A>0 independent of n, all n≥ 1 and all z we have
  
      |ℙ(1/√(n)∑_i=1^nZ_i≤ z) - ℙ(Z̃≤ z)|≤A/√(n)
  
  
  
  
  
  
  
  