Approximations for the von Neumann and Rényi entropies of graphs with circulant type Laplacians

1.   Introduction

The notion of entropy is due to Rudolf Clausius (1850), and is linked with Carnot's famous theorem on the efficiency of thermal machines. This concept has many applications in different research areas, such as statistical mechanics, computation science, information theory, etc. The concept of graph entropy was introduced in information theory and is of special interest for understanding graph structure (see ^{[1,2,3,4,5,6,7,8]} and references therein).

Let $G$ be an undirected graph with $n$ vertices and at least one edge. The degree $d_i$ of a vertex $i$ is the number of edges incident on $i$. Let $L(G)$ be the Laplacian matrix of $G$, that is, $L(G) = D(G)-A(G),$ where $D(G)$ is the diagonal matrix whose $(i, i)$-th entry is $d_i$ and $A(G)$ is the (0, 1) adjacency matrix of $G$ ^[9], i.e., $a_{ij}$ is 1 if $i, \; j$ are adjacent, and 0 otherwise. Since $L(G)$ is symmetric, its eigenvalues are real and as each row (and column) sum is $0$, $L(G)$ is singular. Normalizing this matrix by its trace, we get the density matrix of $G$,

which is Hermitian with unit trace. By Gershgorin Theorem, all eigenvalues of $\rho_L(G)$ are nonnegative ^[10], so $G$ can be seen as a quantum state. The eigenvalues of $\rho_L(G)$ constitute the spectrum of the graph $G$. In view of the above, it seems natural to investigate the information content of the graph as a quantum state ^[11].

For $A$ and $B$ positive semidefinite matrices such that ${{{\rm{Tr}}}} A = 1$, we consider the following matrix functions

The functions $S(A),$ $S(A, B),$ $H_\alpha(A)$ and $H_\alpha(A, B)$ are, respectively, the von Neumann entropy of $A$, the von Neumann relative entropy of $A, B$, the $\alpha$-Rényi entropy of $A$ and the $\alpha$-Rényi relative entropy of $A, B$.

According to the fundamental inequality of statistical thermodynamics ^[12]

For ${{{\rm{Tr}}}} B = 1$, we have $S(A, B)\geq0$, and $H_\alpha(A, B)\geq0,$ with equality if $A = B$. So, $S(A, B)$ and $H_\alpha(A, B)$ may be conveniently used to measure the distance between the density matrices $A$ and $B$. Obviously, $\lim_{\alpha\rightarrow1}H_\alpha(A) = S(A)$ and $\lim_{\alpha\rightarrow1}H_\alpha(A, B) = S(A, B)$.

Let $G$ be a graph with at least one edge and let $\rho _{1}, \ldots, \rho_{n}$ be the eigenvalues of $\rho_L (G).$ We use the natural logarithm in the definitions of entropy and we make the convention that $0\log 0 = 0$. The von Neumann entropy of the graph $G$, denoted $S_L(G)$, is the von Neumann entropy of $\rho_L(G)$. From (1.1),

because $\rho_L(G)$ is unitarily diagonalizable and the logarithm is unitarily invariant. In terms of the eigenvalues $\lambda_1, \ldots, \lambda_n$ of the Laplacian $L(G)$, the von Neumann entropy of $G$ is expressed as

The $\alpha$-Rényi entropy of the graph $G$ ^[13], denoted $H_\alpha(G),$ is the $\alpha$-Rényi entropy of $\rho_L(G)$. For $\alpha\in(0, 1)\cup(1, \infty)$ fixed, from (1.3) we have

In terms of the eigenvalues $\lambda_1, \ldots, \lambda_n$ of the Laplacian $L(G)$, the $\alpha$-Rényi entropy of $G$ is expressed as

For a fixed graph $G$, the $\alpha$-Rényi entropy $H_\alpha(G)$ is a monotonically decreasing function of $\alpha$ ^[2]:

The complete graph $K_n$ is the one with the highest possible entropy. Indeed, if the density matrix $\rho$ is singular, its highest possible entropy is $\log(n-1)$ and that is the entropy of the graph $K_n.$ In terms of the eigenvalues $\lambda_k$ and $\lambda'_k$, respectively of the Laplacian $L(G)$ and of the Laplacian $L(K_n)$, the relative entropy of $G$ and $K_n$ is given by

where $\lambda_j$ and $\lambda'_{j}$ are similarly, increasingly or decreasingly, ordered. Under these assumptions, the $\alpha$-relative Rényi entropy of $G$ and $K_n$ is

In recent years, many approaches to increase the understanding of graphical models have been developed, using entropic quantities associated to the graphs constructs (vertices, edges, etc), see e.g., Simmons et al. ^[6,7] and references therein. The von Neumann entropy of graphs plays a major role in this program, namely by considering the von Neumann Theil index and its generalization by the Rényi entropy. In this note, using the Euler-Maclaurin formula we approximate the von Neumann and Rényi entropies of graphs of high dimensions whose Laplacians are $g$-circulant matrices, that is, circulant matrices where each row is a right cyclic shift in $g$-places to the preceding row. In the six cases we have studied, we observe that the relative entropy of $G$ and $K_n$ does not depend on $n$, for $n$ sufficiently large. We have approximated the distance of the graph $G$ to the graph $K_n$ because $K_n$ is the graph with $n$ vertices with the highest entropy. From our investigations, the following problems arise.

Problem 1. Does the above mentioned observation hold for a general graph with a $g$-circulant Laplacian?

Problem 2. According to our experiments, we conclude that, for a fixed number of vertices, when the average number ofincident edges on each vertex increases, the von Neumann and the $\alpha$-Rényi entropies increase. Does this behaviour hold in general? When the number of vertices $n$ is fixed, the average number of incident edges on each vertex is $2m/n,$ where $m$ is the number of edges, and the Problem may be rephrased in terms of the edges.

Problem 3. Does the question formulated in Problem 1 have a positive answer for a graph $G$ whose Laplacian is the quasi $g$-Toeplitz matrix (see Case 6 below), obtained by cutting appropriate edges in a graph $G$ with a $g$-circulant Laplacian? By a $g$-Toeplitz matrix we mean a matrix obtained from a $g$-circulant one by replacing its entries in the upper right and lower left corners by zeros.

2.   Graph entropy for graphs with g-circulant Laplacians

Throughout the article the following form of the Euler-Maclaurin (E-M) formula will be used. For a proof, see, e.g., ^{[14,15,16,17]}.

Lemma 1. Let $n$ be a positive integer and let $f$ be a continuous real functionin $[0, 1]$ of class $C^3(0, 1)$, i.e. with continuous derivaties until order $3$. Then

with

$B_3(x) = x^3-3x^2/2+x/2$ the third Bernoulli polynomialand $\{x\}$ the fractional part of $x$.

Case 1

The Laplacian matrix of the cycle (or circuit) $C_n$ is the $n\times n$ circulant matrix

whose eigenvalues are

Therefore, the eigenvalues of $\rho_L(C_n)$ are $\rho_k = \lambda_k/(2n).$

Consider $f(x): = (2-2\cos(2\pi x))\log(2-2\cos(2\pi x)).$ By the Euler-Maclaurin formula and having in mind (1.6), we find

because the command Integrate of Mathematica yields

We compute an upper bound for $|R_n|/n$. For $f(x) = (2-2\cos(2\pi x))\log(2-2\cos(2\pi x))$ in (2.2) and using the command NIntegrate of Mathematica, we find

so that

From (1.9), we obtain the relative entropy of $C_n$ and $K_n$,

As $S(K_n) = \log(n-1),$ we have

We study the asymptotic behavior of the 1/2-Rényi entropy of $C_n$ for large $n$. We use (1.8), and we introduce the function of the real variable $k/n$, $f(k/n): = \lambda_k = 2-2\cos(2\pi k/n),$ with $n$ a positive integer. In the spirit of the Euler-Maclaurin formula, we replace the sum

by the integral

which has been evaluated using the command Integrate of Mathematica. Obviously, $\sum_{k = 1}^n\lambda_k = 2n.$ So, we have for the 1/2-Rényi entropy,

We compute an upper bound for $|R_n|/n$. Using the command NIntegrate of Mathematica we find

so that by (2.2)

For the 1/2-Rényi relative entropy of $C_n$ and $K_n$, using (1.10), we obtain

The asymptotic behavior of the 2-Rényi entropy of $C_n$ for large $n$ follows in a similar way, using the Euler-Maclaurin formula. Indeed, we replace the sum

by the integral

and by (1.8), we get

Case 2

Next we consider the graph with $n$ vertices of the type represented in Figure 1. Its Laplacian, in the general case of $n$ vertices, is the circulant matrix

whose eigenvalues are

with $k = 1, \ldots, n$. The eigenvalues of the density matrix are $\rho_i = \lambda_i/(4n).$ Using the command NIntegrate of Mathematica, we find

Using the Euler-Maclaurin formula, the von Neumann entropy of $A_n$ is computed as

An upper bound to $|R_n|/n$ is now estimated. Using the Command NIntegrate of Mathematica we find

so that

Notice that, for $f(x) = (4-2\cos(2\pi x)-2\cos(4\pi x))\log(4-2\cos(2\pi x)-2\cos(4\pi x))$, we have

In an analogous way, we also find

Since $S(K_n) = \log(n-1)$ and as the command NIntegrate of Mathematica yields

we have

In order to approximate the $1/2$-Renyi entropy an analogous procedure holds. By (1.8) and as the command NIntegrate of Mathematica yields

we obtain

An upper bound to $|R_n|/n$ is estimated noticing that for $f(x) = (4-2\cos(2\pi x)-2\cos(4\pi x))^{1/2},$ we have

Thus

From (1.10), we get

Case 3

The Laplacian of the graph with $n$ vertices of the type represented in Figure 2 is

Its eigenvalues are

and the eigenvalues of the density matrix are $\rho_i = \lambda_i/(6n)$.

Using the Euler-Maclaurin formula, the von Neumann entropy is computed as

As by the command NIntegrate of Mathematica, we obtain

we get

For the relative entropy, by (1.9), we obtain,

Using the Euler-MacLaurin formula, for $\rho(k) = \rho_k = \lambda_k/\sum_{j = 1}^n\lambda_j$ and $f(n/k) = \lambda_k,$ we have

Having in mind that

we get

Case 4

The Laplacian of the graph with $n$ vertices of the type represented in Figure 3 is the 2-circulant matrix

In order to determine the eigenvalues and eigenvectors of $D_n$ we consider a vector of the form $w = (x{{{\rm{e}}}}^{i\theta_k}, y{{{\rm{e}}}}^{i\theta_k}, \ldots, x{{{\rm{e}}}}^{im\theta_k}, y{{{\rm{e}}}}^{im\theta_k})^{\mathrm{T}}$, $\theta_k = 2\pi k/m,$ $k = 1, \ldots, m$, and the secular equation

which yields

where

The matrix $\cal S$ is called the symbol associated to $D_n$, and its eigenvalues are

Defining

we obtain, using the command NIntegrate of Mathematica,

and so

For

we find, using the command NIntegrate of Mathematica,

and, using (1.8), we get

and

Case 5

The Laplacian of the graph with $n$ vertices of the type represented in Figure 4, is the 3-circulant matrix

The symbol associated to $F_n$ is

and its spectrum is

With the command NIntegrate of Mathematica, we find

By (1.6), we get

Using the command NIntegrate of Mathematica, we find

Thus, by (1.8)

Case 6

Up to now we have considered graphs with $g$-circulant Laplacians. Next, we evaluate the entropy of the graph of the type of the one in Figure 5, which is obtained by deleting in Figure 1 appropriate edges. Its Laplacian is the matrix

Let

where

and let $A'_n(\eta) = A_n+\eta\Delta_n.$ In the end we take $\eta = 1.$ Regarding $\Delta_n$ as a perturbation of $A_n$, the eigenvalues of $A'_n$ are easily obtained using perturbation theory. The eigenvalues of $A_n$ are given by (2.3) and the respective eigenvectors are

We have, for the eigenvalues $\lambda_k(\eta)$ of $A'_n(\eta)$,

See e.g., ^[18]. Then,

Theorem 2.1. Under the above notations, we have

Proof. To approximate the entropy of $A_n'$ we need the sum

where we have neglected terms of higher order than the first, in the correction. We are therefore led, by the Euler-Maclaurin formula, to consider the integral

For $n$ large, we may replace this integral by

which is easily evaluated using Mathematica. If $n$ is sufficiently large, the magnitude of the perturbation will be small enough in comparison with the magnitude of $A_n$ and first order perturbation theory is valid. An approximation for $S(A'_n)$ will now be obtained:

Hence, 1) follows. The remaining assertions are similarly shown.

3.   Discussion

The obtained results for the first five cases previously considered, are summarized in Table 1. They lead to the conclusion that the relative entropy of the different graphs with respect to the complete graph $K_n$ does not depend on $n$ for sufficiently high $n$, and that the distance between the graphs $G$ and $K_n$ slightly decreases when the average number of incident edges on each vertex of $G$ increases. We compute $H_{2}(G)$, the 2-Rényi entropy of $G$, by Eq (2) in ^[2], and then get the values of $\log_{2}n-H_{2}(G)$. Compared with $H_{2}(G, K_n)$, the 2-relative Rényi entropy of $G$ and $K_n$, our estimation method is better.

We have verified that $S(G, K_n)$ does not depend on $n$ if $n$ is large, and we have determined the $\lim_{n\rightarrow \infty} S(G, K_n)$, for several cyclic graphs $G$. We have seen that, asymptotically, $S(G, K_n)$ behaves like $S(K_n)- S(G)$. The following question naturally arises. Does $S(C_n, K_{1, n-1})$, where $K_{1, n-1}$ is the star graph, behave asymptotically like $S(K_{1, n-1}) -S(C_n)$? Let us compute $S(C_n, K_{1, n-1})$ using (1.6). The eigenvalues of $L(C_n)$ are $\lambda_k = 2-2\cos2\pi k/n,$ $k = 1, \ldots, n,$ so, the highest eigenvalue of $L(C_n)$ is 2. The eigenvalues $\lambda'_k$ of $L(K_{1, n-1})$ are 0, 1, with multiplicity $n-2$ and $n$. We find

and so

On the other hand

and so

while

The answer to the above question is negative.

Acknowledgments

The first author was partially supported by Fundação para a Ciência e Tecnologia, Portugal, under the Project UID/FIS/04564/2019, and by the Centre for Mathematics of the University of Coimbra, under the Project UID/MAT/00324/2013, funded by the Portuguese Government through FCT/MEC and co-funded by the European Regional Development Fund through the Partnership Agreement PT2020. The third author was supported by joint research project of Laurent Mathematics Center of Sichuan Normal University and National-Local Joint Engineering Laboratory of System Credibility Automatic Verification (No. ZD20220106).

Conflict of interest

The authors declare there is no conflicts of interest.