28

# A Graph-Theoretical Framework to Analyse Zero Discord Quantum States

Anoopa Joshi
Indian Institute of Technology Jodhpur, Rajasthan, India
Parvinder Singh
Central University of Punjab, Bathinda, India
Atul Kumar
Indian Institute of Technology Jodhpur, Rajasthan, India  Email:
<EMAIL_ADDRESS>Email<EMAIL_ADDRESS>Email:
<EMAIL_ADDRESS>
###### Abstract

This article comprehensively explores matrices and their prerequisites for
achieving positive semi-definiteness. The study delves into a series of
theorems concerning pure quantum states in the context of weighted graphs. The
main objective of this study is to establish a graph-theoretic framework for
the study of quantum discord and to identify the necessary and sufficient
conditions for zero quantum discord states using unitary operators. This
research aims to advance the understanding of quantum discord and its
implications for quantum information theory with a graph-theoretic framework.

_Key words_ : Graph Laplacian, Density operator, Quantum gates, Quantum
discord

##  1 Introduction

In the bipartite and multipartite quantum systems, the phenomenon of
entanglement exhibits that a local measurement on one subsystem will have a
profound impact on the other subsystem due to the existence of nonlocal
correlation [24, 10, 15, 1, 2, 33, 34]. However, it is worth noting that
entanglement is not always a prerequisite for demonstrating nonlocal
characteristics in quantum systems [3, 4]. For example, a quantum computing
framework- deterministic quantum computation using single qubit- utilizing
highly mixed states was proposed in 1998 [20, 7]. Notably, this model was
successfully implemented experimentally in 2008 [21], and serves as an
excellent illustration that certain highly mixed states, even when separable,
exhibit intrinsic non-classical correlations which hold promising potential
for applications in quantum computing. Moreover, investigations have revealed
that quantum correlation exhibits greater resilience than entanglement in the
presence of noise, rendering quantum algorithms relying solely on nonlocal
correlations more robust compared to those relying on entanglement [32, 31,
30, 11].

Quantum discord is a measure of non-classical quantum correlation, and it has
been extensively studied for achieving efficient, secure, and optimal quantum
communication beyond the scope of entanglement. Quantifying quantum
correlation in a bipartite state is achieved by measuring quantum discord,
initially introduced by Ollivier and Zurek [26]. Obtaining an analytical
expression of quantum discord for arbitrary two-qubit states is challenging
due to the complex optimization over local measurements. Hence, determining
whether a quantum state has zero quantum discord is crucial in distinguishing
its quantum characteristics. For instance, it has been established that a
vanishing quantum discord between the principal system and its surroundings is
necessary and sufficient for characterizing the system’s dynamics through a
completely positive map [29, 22, 6, 23, 28]. Recently, researchers proposed a
necessary and sufficient condition for nonzero quantum discord using singular
value decomposition of a correlation matrix [6, 8, 27].

This study presents a simplified method for assessing zero quantum discord,
which involves partitioning the density matrix into block matrices and
evaluating the specific properties of these blocks. Mathematically, the
density operator $\rho_{G}$ is defined as [13, 5, 19, 17]:

$\rho_{G}=\frac{1}{Tr(L(G))}[L(G)]$

where $L(G)$ represents the Laplacian matrix of the weighted graph $G$.

Since the density operator $\rho_{G}$ serves as an alternate representation of
the state of a quantum system, it is pivotal in understanding the evolution of
quantum systems, which are inherently unitary operations. Consequently,
unitary operators, often called quantum gates, play a fundamental role in
quantum physics. These gates, including single-qubit gates like the Pauli
operators ($\sigma_{x}$, $\sigma_{y}$, $\sigma_{z}$), as well as multi-qubit
gates, are crucial for manipulating and transforming quantum states [25].
Notably, unitary operators enable the exploration of both separability and
quantum discord, which are measures of the correlation between two subsystems
of a quantum system. Ensuring the validity and reliability of quantum
computations requires necessary conditions for a positive semi-definite
matrix. These conditions encompass various mathematical criteria that must be
satisfied by the matrix elements [14].

Condition for positive semi-definite matrix: Let $A=[a_{pq}]_{n\times n}$ be a
positive semi-definite matrix then

  1. 1.

$|a_{ii}|\geq\sum_{i\neq j}|a_{ij}|$ [17].

  2. 2.

$det(\begin{bmatrix}a_{pp}&a_{pq}\\\ a_{qp}&a_{qq}\end{bmatrix})\geq 0$ for
$q>p$ [17].

Converse is true if
$\begin{bmatrix}\bar{x_{p}}&\bar{x_{q}}\end{bmatrix}\begin{bmatrix}a_{pp}&a_{pq}\\\
a_{qp}&a_{qq}\end{bmatrix}\begin{bmatrix}{x_{p}}\\\
{x_{q}}\end{bmatrix}=|b_{pq}||x_{p}+(-1)^{m_{pq}}x_{q}|^{2}+|c_{pq}||x_{p}+(-1)^{n_{pq}}ix_{q}|^{2}+[a_{pp}-|b_{pq}|-|c_{pq}|]|x_{p}|^{2}+[a_{qq}-|b_{pq}|-|c_{pq}|]|x_{q}|^{2}\geq
0$ for $q>p$, here $m_{pq}$ and $n_{pq}$ are either odd or even and $|b_{pq}|$
and $|c_{pq}|$ are positive,

and
$\begin{bmatrix}\bar{x_{p}}&\bar{x_{r}}\end{bmatrix}\begin{bmatrix}a_{pp}&a_{pr}\\\
a_{rp}&a_{rr}\end{bmatrix}\begin{bmatrix}{x_{p}}\\\
{x_{r}}\end{bmatrix}=|b_{pr}||x_{p}+(-1)^{m_{pr}}x_{r}|^{2}+|c_{pr}||x_{p}+(-1)^{n_{pr}}ix_{r}|^{2}+[a_{pp}-|b_{pr}|-|c_{pr}|]|x_{p}|^{2}++[a_{rr}-|b_{pr}|-|c_{pr}|]|x_{r}|^{2}\geq
0$ for $r>p$, here $m_{pr}$ and $n_{pr}$ are either odd or even and $|b_{pr}|$
and $|c_{pr}|$ are positive.

Then there exists
$\begin{bmatrix}\bar{x_{q}}&\bar{x_{r}}\end{bmatrix}\begin{bmatrix}a_{qq}&a_{qr}\\\
a_{rq}&a_{rr}\end{bmatrix}\begin{bmatrix}{x_{q}}\\\
{x_{r}}\end{bmatrix}=b_{1}|x_{q}+(-1)^{m_{qr}}x_{r}|^{2}+b_{2}|x_{q}+(-1)^{m_{pq}+n_{pr}}\bar{i}x_{r}|^{2}+b_{3}|x_{q}+(-1)^{n_{pq}+m_{pr}}\bar{i}x_{r}|^{2}+b_{4}|x_{q}+(-1)^{n_{pq}+n_{pr}}i\bar{i}x_{r}|^{2}+(+ve)$,
where $b_{1}$, $b_{2}$, $b_{3}$, and $b_{4}$ $\geq 0$ and $m_{qr}$ is either
odd or even and $m_{qr}=m_{pq}+m_{pr}$, such that
$\sum\begin{bmatrix}\bar{x_{p}}&\bar{x_{q}}\end{bmatrix}\begin{bmatrix}a_{pp}&a_{pq}\\\
a_{qp}&a_{qq}\end{bmatrix}\begin{bmatrix}{x_{p}}\\\
{x_{q}}\end{bmatrix}=a_{1}|x_{1}\pm x_{2}\pm\dots\pm x_{n}|^{2}+a_{2}|x_{1}\pm
ix_{2}\pm\dots\pm ix_{n}|^{2}+(+ve)$ which clearly shows that the matrix $A$
is a positive semi definite matrix.

Quantum Gates: Quantum gates display reversibility, ensuring that each input
has a unique corresponding output within the reversible circuit. In the realm
of quantum computing, a variety of gates exists, including single-qubit gates
(SQG) such as $I_{2}$, $\sigma_{x},\sigma_{y},\sigma_{z},$ and
$H=\frac{1}{\sqrt{2}}[\sigma_{x}+\sigma_{z}]$, as well as multiqubit gates
(MQG) such as Controlled-NOT (CX=$\begin{bmatrix}I_{2}&0\
0&\sigma_{x}\end{bmatrix}$), Controlled-Z (CZ=$\begin{bmatrix}I_{2}&0\
0&\sigma_{z}\end{bmatrix}$), and Swap gates. Combining these single and
multiqubit gates effectively enables global quantum computation [9, 12]. The
impact of their operations on qubits are briefly described below:

  1. 1.

Performing quantum gates on the graph: Consider a graph $G$ with vertices
$V(G)=\left\\{v_{1},v_{2},\dots,v_{n}\right\\}$ and edges
$E(G)=\left\\{e_{11},e_{12},\dots,e_{nn}\right\\}$. The vertices can be
represented as column vectors ($b_{i}$). Applying a quantum gate to a graph
$G$ signifies the action of applying the quantum gate to individual vertices
or edges.

  2. 2.

Performing quantum gate operations on a density operator: The expression
$\rho_{G}=\frac{1}{Tr(L)}\big{[}l_{ij}b_{i}\otimes{b_{j}}^{T}\big{]}_{2^{n}\times
2^{n}}$ represents the density operator, where $Tr(L)$ is the trace of matrix
$L$, $l_{ij}$ is an element of matrix $L$, and $b_{i}$ and $b_{j}$ are basis
vectors, then $\rho_{G}$ $\xrightarrow{\text{
QG}}{\rho}^{\prime}=\frac{1}{Tr(L)}\big{[}l_{ij}(QG\times
b_{i}\otimes{(QG\times b_{j})}^{T})\big{]}_{2^{n}\times 2^{n}}$

  3. 3.

Partial quantum gate on a graph $G$[18]:  Consider a graph $G$ with $2^{n}$
vertices. Let $V$ be the collection of vertices, defined as
$V=\\{b_{i}={c_{1}}^{i}\otimes{c_{2}}^{i}\otimes\dots\otimes{c_{n}}^{i}\text{
for all $i=1,2,\dots,2^{n}$}\\}$, where $c_{i}^{\prime}s$ are column vectors
in ${\mathbb{C}}^{2}$. Let us consider a unitary operator
$U=I_{2}\otimes{U_{2}\otimes\dots\otimes U_{n}}$, where $U_{2},\dots,U_{n}$
can be either $I_{2}$ or $\sigma_{x}$. In this case, a partial quantum gate on
the graph can be defined as $(\text{Partial}U)G=(Ub_{i},Ub_{j})\in E(G_{1})$
for all $(b_{i},b_{j})\in E(G)$, where, $U_{k}$ is determined by the following
conditions,

    1. (a)

$U_{k}=I_{2}$ if ${c_{k}}^{i}={c_{k}}^{j}$ .

    2. (b)

$U_{k}=\sigma_{x}$ if ${c_{k}}^{i}\neq{c_{k}}^{j}$.

  4. 4.

Partial quantum gate on a density operator [18]: Let
$\rho_{G}=\frac{1}{\text{Tr}(L(G))}\left[l_{ij}b_{i}\otimes{b_{j}}^{T}\right]_{2^{n}\times
2^{n}}$ represent the density operator of the graph $G$ with $2^{n=p+q}$
vertices. The vertex set $V$ is defined as
$V=\\{b_{i}={c_{1}}^{i}\otimes{c_{2}}^{i}\otimes\dots\otimes{c_{n}}^{i}\text{
for all $i=1,2,\dots,2^{n}$}\\}$, where ${c_{i}}$’s are column vectors in
${\mathbb{C}}^{2}$. Let us consider a unitary operator
$U=\underbrace{I_{2}\otimes\dots\otimes
I_{2}}_{q}\otimes{U_{q+1}\otimes\dots\otimes U_{q+p}}$ such that
$U_{q+1},\dots,U_{q+p}$ are either $I_{2}$ or $\sigma_{x}$ and $\rho_{G}$
represents as a block matrix of dimensions $2^{q}\times 2^{q}$. In this case,
a partial quantum gate on the density operator can be expressed as
$(\text{Partial}U)\rho_{G}=\frac{1}{Tr(L(G))}\big{[}l_{ij}Ub_{i}\otimes{(Ub_{j})}^{T}\big{]}_{2^{n}\times
2^{n}}$, where, $U_{k}$ is determined by the following conditions,

    1. (a)

$U_{k}=I_{2}$ if ${c_{k}}^{i}={c_{k}}^{j}$ .

    2. (b)

$U_{k}=\sigma_{x}$ if ${c_{k}}^{i}\neq{c_{k}}^{j}$.

In this article, we will adhere to the established definitions as:

  1. 1.

Consider $(G,a)$ as a graph linked to the $n$-qubit quantum state, consisting
of $2^{n}$ ($n=p+q$) vertices labeled as $(ij)$, where $i$ varies from 1 to
$2^{p}$, and $j$ varies from 1 to $2^{q}$.

  2. 2.

The expression $|x|$ represents the absolute value of x.

  3. 3.

For a matrix $A$, $\overline{A}$ represents as a conjugate of $A$.

The article is structured as follows: Section 2 introduces a series of
theorems about pure quantum states linked to weighted graphs. Section 3 delves
into the concept of discord and its intricate definition within the quantum
realm. It further analyzes quantum discord, unraveling its underlying
characteristics and implications from a graph-theoretic perspective. In
Section 4, we present a conclusive summary, highlighting the significance of
our research and its potential contributions to the evolving landscape of
quantum information science.

##  2 Conditions for a positive semi-definite matrix and the pure state
associated with a weighted graph

In this section, we establish a set of theorems that are presented for pure
states associated with weighted graphs.

######  Theorem 2.1.

Let $(G,a)$ be a connected weighted graph, which represents an $m$-qubit
state. A state $(G,a)$ is considered to be a pure state if the absolute value
of $l_{ij}$ is equal to $d_{ii}$ for all values of $i$ and $j$.

Proof: Consider $(G,a)$ as a connected weighted graph, which represents an
$m$-qubit state and
$\rho_{G}=\frac{1}{Tr(L(G))}L(G)=\frac{1}{Tr(L(G))}\begin{bmatrix}d_{11}&l_{12}&.&.&.&l_{12^{m}}\\\
l_{21}&d_{22}&.&.&.&l_{22^{m}}\\\ .&,&.&.&.&.\\\ .&,&.&.&.&.\\\ .&,&.&.&.&.\\\
l_{2^{m}1}&l_{2^{m}2}&.&.&.&d_{2^{m}2^{m}}\\\ \end{bmatrix}$ be the density
operator. If $\lvert l_{ij}\lvert=d_{ii}$ $\forall i,j$, then we clearly have
$Tr({\rho_{G}}^{2})=1$. Hence proved.

Example: The graphs $G_{1}$ and $G_{2}$ shown below also exemplify the theorem
mentioned earlier.

$|{00}\rangle$$|{01}\rangle$$|{10}\rangle$$|{11}\rangle$$\hskip
28.45274ptG_{1}\hskip 28.45274pt$$\hskip
28.45274pt\rho_{G_{1}}=\frac{1}{4}\begin{bmatrix}1&i&i&-1\\\ -i&1&1&i\\\
-i&1&1&i\\\ -1&-i&-i&1\end{bmatrix}\hskip 28.45274pt$ii-1-21i-2i-2-2

Here $d_{11}=d_{22}=d_{33}=d_{44}=1$, $l_{12}=l_{13}=l_{24}=l_{34}=i$,
$l_{14}=l_{41}=-1$, $l_{21}=l_{31}=l_{42}=l_{43}=-i$ and $l_{23}=l_{32}=1$.
Clearly, we have $d_{ii}=\lvert l_{ij}\lvert$.

$|{000}\rangle$$|{001}\rangle$$|{010}\rangle$$|{011}\rangle$$|{100}\rangle$$|{101}\rangle$$|{110}\rangle$$|{111}\rangle$$G_{2}$
-1-13-133

$\rho_{G_{2}}=\frac{1}{3}\begin{bmatrix}0&0&0&0&0&0&0&0\\\ 0&1&1&0&1&0&0&0\\\
0&1&1&0&1&0&0&0\\\ 0&0&0&0&0&0&0&0\\\ 0&1&1&0&1&0&0&0\\\ 0&0&0&0&0&0&0&0\\\
0&0&0&0&0&0&0&0\\\ 0&0&0&0&0&0&0&0\end{bmatrix}$

which further supports the above theorem.

######  Theorem 2.2.

Consider a weighted graph $(G,a)$ with $2^{m}$ vertices, where
$a\in{\mathbb{C}}$. This graph is associated with an $m$-qubit state that has
more than two components. If the graph consists of only one connected
component, labeled as $G_{1}$, and each vertex in $G_{1}$ is linked to every
other vertex via unique edges, satisfying the condition $\lvert
a{(v_{i},v_{j})}\lvert=a(v_{i},v_{i})+\sum_{v_{i}\neq v_{j}}\lvert
a{(v_{i},v_{j})}\lvert$ for all $v_{i}$, $v_{j}$ $\in G_{1}$, then, the
weighted graph $(G,a)$ corresponds to a pure quantum state.

Proof: Let $(G,a)$ $(a\in{\mathbb{C}})$ be a weighted graph with $2^{m}$
vertices, which represents an $m$-qubit quantum state. Let $G_{1}$ be the
connected component of $G$ that consists of $k$ vertices and absolute value of
edge weight ($a{(v_{i},v_{j})}$, for $v_{i}\neq v_{j}$) is $c$. Suppose
$\lvert a{(v_{i},v_{j})}\lvert=a(v_{i},v_{i})+\sum_{v_{i}\neq v_{j}}\lvert
a{(v_{i},v_{j})}\lvert$ for all $v_{i}$, $v_{j}$ $\in G_{1}$ which implies
that diagonal sum of density operator is $kc$, and the diagonal entries of
${\rho_{G}}^{2}$ is $kc^{2}$. Therefore $Tr({\rho_{G}}^{2})=1$. Therefore, it
has been demonstrated.

Example:  The graph $G$ depicted below serves as an illustration of theorem
2.2.

$v_{1}=|{00}\rangle$$v_{2}=|{01}\rangle$$v_{3}=|{10}\rangle$$v_{4}=|{11}\rangle$$G$
i

$\rho_{G}=\frac{1}{2}\begin{bmatrix}1&0&0&i\\\ 0&0&0&0\\\ 0&0&0&0\\\
-i&0&0&1\end{bmatrix}$

Here connected component say $G_{1}$ is with vertex set $V=\\{v_{1},v_{4}\\}$
and $a(v_{1},v_{1})=a(v_{4},v_{4})=0$, $a(v_{1},v_{4})=i$.

We can see that $\lvert a(v_{1},v_{4})\lvert=a(v_{1},v_{1})+\sum_{v_{i}\neq
v_{j}}\lvert a{(v_{i},v_{j})}\lvert$

######  Corollary 2.2.1.

Consider a connected weighted graph $(G,a)$ with $2^{m}$ vertices, associated
with an $m$-qubit state . The weight of each edge is represented by a real
number $a$. If the absolute of the weight of an edge from vertex $v_{i}$ to
$v_{j}$ (where $v_{i}\neq v_{j}$) is equal to the total of the weights of all
edges connected to vertex $v_{i}$, for all pairs of vertices $v_{i}$ and
$v_{j}$, then the weighted graph $(G,a)$ represents the pure state.

##  3 Quantum Discord of weighted Graphs

In this section, we discuss various conditions for zero or nonzero quantum
discord in the associated weighted graphs using block density operators.

######  Theorem 3.1.

Consider the density operator $\rho_{G}=[\rho_{ij}]_{4\times 4}$, which
represents a weighted graph $(G,a)$ on
${\mathbb{C}}^{2}\otimes{\mathbb{C}}^{2}$. Given that U is a unitary operator
expressed as $U=I_{2}\otimes U_{2}$. If
$(\overline{\text{Partial}U)\rho_{G}}=\rho_{G}$ and
$(\rho_{11}-\rho_{22})\rho_{14}=\rho_{12}(\rho_{13}-\rho_{24})$ then quantum
discord of the weighted graph, $D_{Q}(G,a)=0$.

Proof: Let $(G,a)$ be a weighted graph defined on
${\mathbb{C}}^{2}\otimes{\mathbb{C}}^{2}$ and $\rho_{G}=[\rho_{ij}]_{4\times
4}$ represents the density operator. Clearly,
$(\overline{\text{Partial}U)\rho_{G}}=\rho_{G}$ implies that blocks in the
density operator are Hermitian matrices. Moreover,
$(\rho_{11}-\rho_{22})\rho_{14}=\rho_{12}(\rho_{13}-\rho_{24})$ reveals
commutativity of the blocks as expressed by
$\rho_{11}\rho_{14}+\rho_{12}\rho_{24}=\rho_{12}\rho_{13}+\rho_{22}\rho_{14}$.
Hence the proof [16].

Example: Let
$\rho=\frac{1}{4}[I+\sum_{i=1}^{3}T_{ii}\sigma_{i}\otimes\sigma_{i}]$ be a
density operator.The quantum discord for the density matrix $\rho$ is equal to
zero if $T_{22}=T_{33}=0$ [6, 35].

$\rho=\frac{1}{4}[I+\sum_{i=1}^{3}T_{ii}\sigma_{i}\otimes\sigma_{i}]=\frac{1}{4}\begin{bmatrix}1+T_{33}&0&0&T_{11}-T_{22}\\\
0&1-T_{33}&T_{11}+T_{22}&0\\\ 0&T_{11}+T_{22}&1-T_{33}&0\\\
T_{11}-T_{22}&0&0&1+T_{33}\end{bmatrix}$
As per the Theorem 3.1 $(\overline{\text{Partial}U)\rho_{G}}=\rho_{G}$ if
$T_{11}-T_{22}=T_{11}+T_{22}$ which implies $T_{22}=0$. Also for
$\rho_{11}\rho_{14}+\rho_{12}\rho_{24}=\rho_{12}\rho_{13}+\rho_{22}\rho_{14}$,
one can show $(1+T_{33})(T_{11}-T_{22})=(1-T_{33})(T_{11}-T_{22})$. For
$T_{22}=0$, $T_{11}+T_{33}T_{11}=T_{11}-T_{33}T_{11}$ or $2T_{33}(T_{11})=0$
which implies that $T_{33}=0$.

######  Corollary 3.1.1.

Let $\rho_{G}$ represent the density operator of a weighted graph $(G,a)$ on
${\mathbb{C}}^{2}\otimes{\mathbb{C}}^{2}$. The quantum discord $D_{Q}(G,a)=0$
if $(\overline{I_{2}\otimes\sigma_{x}){\rho_{G}}}=\rho_{G}$ and
$(\sigma_{x}\otimes I_{2})\rho_{G}=\rho_{G}$.

Proof: Let $\rho_{G}$ represent the density operator of a weighted graph
$(G,a)$ on ${\mathbb{C}}^{2}\otimes{\mathbb{C}}^{2}$, given by
$\rho_{G}=\begin{bmatrix}A&B\\\ B^{*}&C\end{bmatrix}$. The conditions
$(\overline{I_{2}\otimes\sigma_{x}){\rho_{G}}}=\rho_{G}$ and
$(\sigma_{x}\otimes I_{2})\rho_{G}=\rho_{G}$ show that each block is in the
form $\begin{bmatrix}a&ib\\\ -ib&a\end{bmatrix}$ and
$\rho_{11}-\rho_{22}=\rho_{13}-\rho_{24}=0$. Using these results, one can
easily show that blocks are commuting with each other. [16].

######  Theorem 3.2.

Let $\rho_{G}$ represent the density operator corresponding to a weighted
graph $(G,a)$. Suppose the graph is associated with an $n$-qubit state
($n=p+q$) such that $\rho_{G}=[A^{xy}]_{2^{q}\times 2^{q}}$
$(A^{xy}=[a^{xy}_{ij}]_{2^{p}\times 2^{p}})$. The density operator $\rho_{G}$
can recursively represented as the block matrices such as
$A^{xy}=B^{xy}-C^{xy}+iD^{xy}-iE^{xy}$ where $B^{xy}$, $C^{xy}$, $D^{xy}$, and
$E^{xy}$ $\geq 0$. The quantum discord $D_{Q}(G,a)=0$ if $B^{lm}$, $B^{rs}$,
$C^{lm}$, $C^{rs}$,$D^{lm}$, $D^{rs}$, $E^{lm}$, and $E^{rs}$ all commute with
each other, for all $lm$ and $rs$ where $A^{rs}=B^{rs}-C^{rs}+iD^{rs}-iE^{rs}$
with $B^{rs}$, $C^{rs}$, $D^{rs}$, and $E^{rs}$ $\geq 0$, and
$A^{lm}=B^{lm}-C^{lm}+iD^{lm}-iE^{lm}$ where $B^{lm}$, $C^{lm}$, $D^{lm}$, and
$E^{lm}$ $\geq 0$.

Proof: Consider $\rho_{G}$ as the density operator corresponding to a weighted
graph $(G,a)$. Let us assume the graph is associated with an $n$-qubit state,
and $\rho_{G}$ can be represented as a block matrix
$\rho_{G}=[A^{xy}]{2^{q}\times 2^{q}}$, where
$A^{xy}=[a^{xy}_{ij}]_{2^{p}\times 2^{p}}$. Assume that
$A^{lm}=B^{lm}-C^{lm}+iD^{lm}-iE^{lm}$, where $B^{lm}$,$C^{lm}$,$D^{lm}$, and
$E^{lm}$ are positive semi-definite matrices and
$A^{rs}=B^{rs}-C^{rs}+iD^{rs}-iE^{rs}$ where $B^{rs}$, $C^{rs}$, $D^{rs}$, and
$E^{rs}$ are positive semi-definite matrices. If $B^{lm}$, $B^{rs}$, $C^{lm}$,
$C^{rs}$,$D^{lm}$, $D^{rs}$, $E^{lm}$, and $E^{rs}$ all commute with each
other, for all $lm$ and $rs$, then
$A^{lm}A^{rs}=(B^{lm}-C^{lm}+iD^{lm}-iE^{lm})(B^{rs}-C^{rs}+iD^{rs}-iE^{rs})=(B^{lm}-C^{lm}+iD^{lm}-iE^{lm})(B^{rs})-(B^{lm}-C^{lm}+iD^{lm}-iE^{lm})(C^{rs})+i(B^{lm}-C^{lm}+iD^{lm}-iE^{lm})(D^{rs})-i(B^{lm}-C^{lm}+iD^{lm}-iE^{lm})(E^{rs})=(B^{rs})(B^{lm}-C^{lm}+iD^{lm}-iE^{lm})-(C^{rs})(B^{lm}-C^{lm}+iD^{lm}-iE^{lm})+i(D^{rs})(B^{lm}-C^{lm}+iD^{lm}-iE^{lm})-i(E^{rs})(B^{lm}-C^{lm}+iD^{lm}-iE^{lm})=(B^{rs}-C^{rs}+iD^{rs}-iE^{rs})(B^{lm}-C^{lm}+iD^{lm}-iE^{lm})=A^{rs}A^{lm}$.
Hence Proved [16].

Example: The graph $G$ shown below illustrates the aforementioned theorem.

$|{00}\rangle$$|{01}\rangle$$|{10}\rangle$$|{11}\rangle$$\hskip
28.45274ptG\hskip
28.45274pt$2+i32+i$-2\sqrt{5}$2-i3$-2\sqrt{5}$2+i$-2\sqrt{5}$$-2\sqrt{5}$

We have $\rho_{G}=\frac{1}{12}\begin{bmatrix}3&2+i&3&2+i\\\ 2-i&3&2-i&3\\\
3&2+i&3&2+i\\\ 2-i&3&2-i&3\end{bmatrix}=\begin{bmatrix}A^{11}&A^{12}\\\
A^{21}&A^{22}\end{bmatrix}=\frac{1}{3}\Big{\\{}\frac{1}{2}\begin{bmatrix}1&1\\\
1&1\end{bmatrix}\otimes\frac{1}{2}\begin{bmatrix}1&i\\\
-i&1\end{bmatrix}\Big{\\}}+\frac{2}{3}\Big{\\{}\frac{1}{4}\begin{bmatrix}2&2\\\
2&2\end{bmatrix}\otimes\frac{1}{2}\begin{bmatrix}1&1\\\
1&1\end{bmatrix}\Big{\\}}$.
Here $(\rho_{11}-\rho_{22})\rho_{14}=\rho_{12}(\rho_{13}-\rho_{24})$,
$A^{11}=\frac{1}{12}\begin{bmatrix}3&2+i\\\ 2-i&3\end{bmatrix}$,
$A^{12}=\frac{1}{12}\begin{bmatrix}3&2+i\\\
2-i&3\end{bmatrix}=\frac{1}{12}\Bigg{\\{}\begin{bmatrix}2&2\\\
2&2\end{bmatrix}+\begin{bmatrix}1&i\\\ -i&1\end{bmatrix}\Bigg{\\}}$,
and $A^{lm}A^{rs}=A^{rs}A^{lm}$.

######  Theorem 3.3.

Consider $\rho_{G}$ as the density operator of a weighted graph $(G,a)$ that
is associated with an $n$-qubit state such that
$\rho_{G}=[A^{xy}]_{2^{q}\times 2^{q}}$ $(A^{xy}=[a^{xy}_{ij}]_{2^{p}\times
2^{p}})$ can be represented as a block matrix. Assume
$(\overline{PartialU){\rho_{G}}}=\rho_{G}$, where
$U=\underbrace{I_{2}\otimes\dots\otimes
I_{2}}_{q}\otimes\underbrace{U_{q+1}\dots\otimes U_{q+p}}_{p}$, and $U_{i}$
represents either $I_{2}$ or $\sigma_{x}$. The quantum discord $D_{Q}(G,a)=0$,
if $\overline{(PartialU^{\prime}){A^{rs}A^{lm}}}=A^{rs}A^{lm}$ for all $lm$
and $rs$, where $U^{\prime}=(U_{1}\otimes U_{2}\otimes\dots\otimes U_{p})$.

Proof: Consider $\rho_{G}$ as the density operator of a weighted graph $(G,a)$
which is associated with an $n$-qubit state. Assume that the density operator
$\rho_{G}$ can be expressed as a block matrix, denoted as
$[A^{xy}]_{2^{q}\times 2^{q}}$, where each block $A^{xy}$ is a $2^{p}\times
2^{p}$ matrix represented by $[a^{xy}_{ij}]_{2^{p}\times 2^{p}}$. Consider a
unitary operator $U$ defined as: $U=\underbrace{I_{2}\otimes\dots\otimes
I_{2}}_{q}\otimes\underbrace{U_{q+1}\dots\otimes U_{q+p}}_{p}$, where $U_{i}$
are either $I_{2}$ or $\sigma_{x}$. Furthermore, if
$(\overline{PartialU){\rho_{G}}}=\rho_{G}$, it implies that the blocks
$A^{xy}$ being Hermitian. Now if
$\overline{(PartialU^{\prime}){A^{rs}A^{lm}}}=A^{rs}A^{lm}$ for all $lm$ and
$rs$, where $U^{\prime}=(U_{1}\otimes U_{2}\otimes\dots\otimes U_{p})$ then
$A^{rs}A^{lm}$ is Hermitian. Consequently, it also implies that
$A^{rs}A^{lm}=A^{lm}A^{rs}$. Hence $D_{Q}(G,a)=0$ [16].

Example: The graphs shown below, denoted as $G_{1}$ and $G_{2}$, also
exemplify the theorem stated above.

$|{00}\rangle$$|{01}\rangle$$|{10}\rangle$$|{11}\rangle$$\hskip
28.45274ptG_{1}\hskip 28.45274pt$1-ii1

The density operator $\rho_{G}$ for the graph $G_{1}$ is,

$\rho_{G_{1}}=\frac{1}{8}\begin{bmatrix}2&0&1&-i\\\ 0&2&i&1\\\ 1&-i&2&0\\\
i&1&0&2\end{bmatrix}$

Here $A^{11}=\frac{1}{8}\begin{bmatrix}2&0\\\ 0&2\end{bmatrix}$ and
$A^{12}=\frac{1}{8}\begin{bmatrix}1&-i\\\ i&1\end{bmatrix}$.
Therefore, we can show that
$\overline{(PartialU^{\prime}){A^{11}A^{12}}}=A^{11}A^{12}=\frac{1}{32}\begin{bmatrix}1&-i\\\
i&1\end{bmatrix}=A^{12}A^{11}$.

Moreover, for the graph $G_{2}$

$|{000}\rangle$$|{001}\rangle$$|{010}\rangle$$|{011}\rangle$$|{100}\rangle$$|{101}\rangle$$|{110}\rangle$$|{111}\rangle$$\hskip
28.45274ptG_{2}\hskip 28.45274pt$

the density operator $\rho_{G_{2}}$ is,

$\rho_{G_{2}}=\frac{1}{24}\begin{bmatrix}3&0&0&0&-1&0&-1&-1\\\
0&3&0&0&0&-1&-1&-1\\\ 0&0&3&0&-1&-1&-1&0\\\ 0&0&0&3&-1&-1&0&-1\\\
-1&0&-1&-1&3&0&0&0\\\ 0&-1&-1&-1&0&3&0&0\\\ -1&-1&-1&0&0&0&3&0\\\
-1&-1&0&-1&0&0&0&3\end{bmatrix}$

where $A^{11}=\frac{1}{24}\begin{bmatrix}3&0&0&0\\\ 0&3&0&0\\\ 0&0&3&0\\\
0&0&0&3\end{bmatrix}$ and $A^{12}=\frac{1}{24}\begin{bmatrix}-1&0&-1&-1\\\
0&-1&-1&-1\\\ -1&-1&-1&0\\\ -1&-1&0&-1\end{bmatrix}$,
Similar to the case of $G_{1}$, we can show that
$\overline{(PartialU^{\prime}){A^{11}A^{12}}}=A^{11}A^{12}=\frac{1}{576}\begin{bmatrix}-3&0&-3&-3\\\
0&-3&-3&-3\\\ -3&-3&-3&0\\\ -3&-3&0&-3\end{bmatrix}=A^{12}A^{11}$.

######  Theorem 3.4.

Consider $\rho_{G}$ as the density operator of a weighted graph $(G,a)$
connected to an $n$-qubit state with $2^{n}$ vertices, where
$\rho_{G}=[A^{xy}]_{2^{n-1}\times 2^{n-1}}$ $(A^{xy}=[a^{xy}_{ij}]_{2\times
2})$. If $\rho_{G}=\overline{(\text{Partial}U)\rho_{G}}$ with $\lvert
a^{xy}_{ij}\lvert=\lvert a^{xy}_{ij+1}\lvert$ where
$U=\underbrace{I_{2}\otimes\dots\otimes I_{2}}_{n-1}\otimes U_{n}$ is a
unitary operator, then the graph corresponding to the quantum state will
exhibit a quantum discord value of zero.

Proof: Consider $\rho_{G}$ as the density operator of a weighted graph $(G,a)$
connected to an $n$-qubit state with $2^{n}$ vertices where
$\rho_{G}=[A^{xy}]_{2^{n-1}\times 2^{n-1}}$ $(A^{xy}=[a^{xy}_{ij}]_{2\times
2})$. Let us further introduce a unitary operators
$U=\underbrace{I_{2}\otimes\dots\otimes I_{2}}_{n-1}\otimes U_{n}$, where
${U_{n}}$ is either $I_{2}$ or $\sigma_{x}$. For
$\rho_{G}=\overline{(\text{Partial}U)\rho_{G}}$, we have all the
$2$-dimensional blocks $A^{xy}$ of $\rho_{G}$ as Hermitian matrices.
Furthermore, if $\lvert a^{xy}_{ij}\lvert=\lvert a^{xy}_{ij+1}\lvert$ then
block $A^{xy}$ either takes the form $A^{xy}=i^{m}\begin{bmatrix}a&ia\\\
-ia&a\end{bmatrix}$ or $A^{xy}=\begin{bmatrix}a&a\\\ a&a\end{bmatrix}$. Hence,
the proof [16].
Example: The graphs illustrated below, denoted as $G_{1}$ and $G_{2}$, also
exemplify the theorem discussed above.

$|{00}\rangle$$|{01}\rangle$$|{10}\rangle$$|{11}\rangle$$\hskip
28.45274ptG_{1}\hskip 28.45274pt$ii-1-21i-2i-2-2

The density operator linked to the graph $G_{1}$ can be expressed as

${\rho_{G_{1}}=\frac{1}{4}\begin{bmatrix}1&i&i&-1\\\ -i&1&1&i\\\ -i&1&1&i\\\
-1&-i&-i&1\end{bmatrix}}$

Thus, $A^{11}=\frac{1}{4}\begin{bmatrix}1&i\\\ -i&1\end{bmatrix}$,
$A^{12}=\frac{1}{4}i\begin{bmatrix}1&i\\\ -i&1\end{bmatrix}$ which shows
$A^{11}A^{12}=A^{12}A^{11}.$

$|{00}\rangle$$|{01}\rangle$$|{10}\rangle$$|{11}\rangle$$\hskip
28.45274ptG_{2}\hskip 28.45274pt$11-1-111

We can deduce the density operator associated with the graph $G_{2}$ as

${\rho_{G_{2}}=\frac{1}{4}\begin{bmatrix}1&-1&-1&1\\\ -1&1&1&-1\\\
-1&1&1&-1\\\ 1&-1&-1&1\end{bmatrix}}$

Evidently, $A^{11}=\frac{1}{4}\begin{bmatrix}1&-1\\\ -1&1\end{bmatrix}$,
$A^{12}=-\frac{1}{4}\begin{bmatrix}1&-1\\\ -1&1\end{bmatrix}$ indicating
$A^{11}A^{12}=A^{12}A^{11}$.

######  Theorem 3.5.

Consider $(G,a)$ as a weighted graph with $2^{n}$ vertices, which represents
an $n$-qubit quantum state. Let $E(G)$ be the set of edges in $(G,a)$, defined
as

$E(G)=\\{(v_{ij},v_{kl});\text{ such that edge lies between }v_{ij}\text{ and
}v_{kl}\\}.$

If there exists an edge $(v_{ij},v_{kl})$ in graph G such that both $j$ and
$l$ are either odd or even, then $D_{Q}(G,a)$, is equal to zero.

Proof: Consider $(G,a)$ as a weighted graph with $2^{n}$ vertices, which
represents an $n$-qubit quantum state. Let $E(G)$ be the edge set in $(G,a)$,
defined as $E(G)=\\{(v_{ij},v_{kl});\text{ such that edge lies between
}v_{ij}\text{ and }v_{kl}\\}.$

Interestingly, if $(v_{ij},v_{kl})$ belongs to $E(G)$ and both $j$ and $l$ are
either odd or even, then the density operator $(\rho_{G})$ can be expressed as
a diagonal matrix in every block.

Diagonal matrices have a significant property that they commute with each
other. Therefore, the blocks of the density operator $(\rho_{G})$, being
diagonal matrices, also commute. Hence, it is proved [16].

Example: The graph displayed below, represented by $G$, offers an illustration
of the theorem mentioned earlier

$v_{11}$$v_{12}$$v_{13}$$v_{14}$$v_{21}$$v_{22}$$v_{23}$$v_{24}$$\hskip
28.45274ptG\hskip 28.45274pt$

The associated density operator is
$\rho_{G}=\frac{1}{12}\begin{bmatrix}2&0&-1&0&-1&0&0&0\\\
0&3&0&-1&0&-1&0&-1\\\ -1&0&2&0&0&0&-1&0\\\ 0&-1&0&1&0&0&0&0\\\
-1&0&0&0&1&0&0&0\\\ 0&-1&0&0&0&1&0&0\\\ 0&0&-1&0&0&0&1&0\\\
0&-1&0&0&0&0&0&1\end{bmatrix}$ where each $2\times 2$ block are in the
diagonal form.

######  Theorem 3.6.

Consider a weighted graph $(G,a)$ with $2^{n}$ vertices, associated with an
$n$-qubit quantum state. Let $E(G)$ denote the set of edges in $(G,a)$,
defined as

$E(G)=\\{(v_{ij},v_{kl})\text{ such that edge lies between}v_{ij}\text{ and
}v_{kl}\\}.$

If there exists an edge $(v_{ij},v_{kl})$ in the graph $(G,a)$ for all $i=k$,
then the graph $(G,a)$ is correlated with a quantum state that has zero
discord.

Proof: Consider a weighted graph $(G,a)$ having $2^{n}$ vertices. This graph
depicts a quantum state consisting of $n$-qubits. The set of edges of the
graph $(G,a)$, represented as

$E(G)=\\{(v_{ij},v_{kl})\text{ such that edge lies between }v_{ij}\text{ and
}v_{kl}\\}.$

If $i=k$, then the density operator expressed as a diagonal block matrix which
linked to the graph $(G,a)$. Notably, these diagonal matrices in the density
operator are positive semi-definite. Hence Proved. [16].

Example: Below is a graph, labeled as $G$, which serves as an illustrative
example of the previously discussed theorem.

$v_{11}$$v_{12}$$v_{21}$$v_{22}$$v_{13}$$v_{14}$$v_{23}$$v_{24}$ G
1-11-1111-1-1111

The density operator of the graph is a diagonal block matrix such that

$\rho_{G}=\frac{1}{8}\begin{bmatrix}1&-1&-1&1&0&0&0&0\\\ -1&1&1&-1&0&0&0&0\\\
-1&1&1&-1&0&0&0&0\\\ 1&-1&-1&1&0&0&0&0\\\ 0&0&0&0&1&-1&-1&1\\\
0&0&0&0&-1&1&1&-1\\\ 0&0&0&0&-1&1&1&-1\\\ 0&0&0&0&1&-1&-1&1\end{bmatrix}$

The proof, therefore, follows from the theorem.

######  Theorem 3.7.

Consider $\rho_{G}=[A^{xy}]_{2\times 2}$ as the density operator of a weighted
graph $(G,a)$ with $2^{n}$ vertices, related to an $n$-qubit quantum state.
Here, $A^{xy}$ is a block matrix defined as
$A^{xy}=[A_{ij}^{xy}]_{2^{n-q-1}\times 2^{n-q-1}}$.

The quantum discord $D_{Q}(G,a)=0$ if
$\sum_{k}{A_{ik}}^{xy}{A_{kj}}^{rs}=\sum_{k}{{A_{ik}}^{rs}{A_{kj}}^{xy}}$ for
all $i,j$ and $\overline{Partial(U^{i})\rho_{G}}=\rho_{G}$, for
$U^{1}=\underbrace{I_{2}\otimes\dots\otimes I_{2}}_{p}\otimes
U_{p+1}\dots\otimes U_{p+q}$, and $U^{2}=I_{2}\otimes U_{2}\dots\otimes
U_{n}$, where, $U_{k}$ are either $I_{2}$ or $\sigma_{x}$.

Proof: Consider a weighted graph $(G,a)$ with $2^{n}$ vertices related to an
$n$-qubit quantum state. Let $\rho_{G}=[A^{xy}]{2\times 2}$ represent the
density operator of this graph, where $A^{xy}$ is a block matrix of size
$2^{n-q-1}$ and $A^{xy}$ is composed of elements denoted as $A{ij}^{xy}$. If
$\sum_{k}{A_{ik}}^{xy}{A_{kj}}^{rs}=\sum_{k}{{A_{ik}}^{rs}{A_{kj}}^{xy}}$ for
all $i,j$ and $\overline{Partial(U^{i})\rho_{G}}=\rho_{G}$, for
$U^{1}=\underbrace{I_{2}\otimes\dots\otimes I_{2}}_{p}\otimes
U_{p+1}\dots\otimes U_{p+q}$, and $U^{2}=I_{2}\otimes U_{2}\dots\otimes
U_{n}$, where, $U_{i}$ are either $I_{2}$ or $\sigma_{x}$, then $A^{xy}$ and
$A^{mn}$ commute, and each block of $A^{xy}$ also commutes. Hence, the discord
is zero [16].

######  Corollary 3.7.1.

Consider $\rho_{G}=[A^{xy}]_{4\times 4}$ as the density operator of a weighted
graph $(G,a)$ with $2^{n}$ vertices where $(G,a)$ represents an $n$-qubit
quantum state, and $A^{xy}$ be the block matrix of the density operator. The
quantum discord $D_{Q}(G,a)=0$ if
$(A^{11}-A^{22})A^{14}=A^{12}(A^{13}-A^{24})$.

######  Theorem 3.8.

Consider $\rho_{G}=[\rho_{ij}]_{2^{n}\times 2^{n}}$ as the density operator of
a weighted graph $(G,a)$ with $2^{n}$ vertices where $(G,a)$ represents an
$n$-qubit quantum state. The quantum discord is zero, if the density operator
can be expressed as
$\rho_{G}=\sum_{i}p_{i}{\rho_{i}}^{1}\otimes{\rho_{i}}^{2}$, with the
condition that ${\rho_{i}}^{1}$ and ${\rho_{i}}^{2}$ commute.

Proof: Consider $\rho_{G}=[\rho_{ij}]_{2^{n}\times 2^{n}}$ as the density
operator of a weighted graph $(G,a)$ with $2^{n}$ vertices where $(G,a)$
represents an $n$-qubit quantum state. Therefore, if the density operator is
written as $\rho_{G}=\sum_{i}p_{i}{\rho_{i}}^{1}\otimes{\rho_{i}}^{2}$ where
${\rho_{i}}^{1}$ and ${\rho_{i}}^{2}$ commute, then the quantum discord is
zero. (The normality and commutativity of blocks of the density operator imply
that the quantum discord is zero [16].)

######  Theorem 3.9.

Let $(G,a)$ represent a weighted graph with $2^{n}$ vertices, which represents
an $n$-qubit state. The state has zero quantum discord, if $a_{ij,kl}=b$
$\forall$ $(v_{ij},v_{kl})\in E(G)$ and $d_{ij,ij}=b(2^{n}-1)$ for all
$v_{ij}$.

Proof: Let $(G,a)$ be a weighted graph on $2^{n}$ vertices, which represents
an $n$-qubit state. For $a_{ij,kl}=b$ $\forall$ $(v_{ij},v_{kl})\in E(G)$ and
$d_{ij,ij}=b(2^{n}-1)$ for all $v_{ij}$, we have $a\in\mathbb{R}$ and
$d_{ij,ij}=\sum{a_{ij,kl}}$ which illustrates that the graph $(G,a)$ is a
complete graph. Therefore, the density operator can be formulated as
$\rho_{G}=\rho_{1}\otimes\rho_{2}$ and all blocks commute. Thus demonstrated.
[16].

Example:  Here, we discuss graphs associated with a quantum state that has
zero quantum discord, e.g., a complete graph, and a complete weighted graph
$K(n,a)$, $a>0$ associated with a three-qubit state.

$v_{11}$$v_{12}$$v_{13}$$v_{14}$$v_{21}$$v_{22}$$v_{23}$$v_{24}$$\hskip
28.45274pt\text{Complete Graph }(G_{1})\hskip
28.45274pt$1111111111111111111111111111

$v_{11}$$v_{12}$$v_{13}$$v_{14}$$v_{21}$$v_{22}$$v_{23}$$v_{24}$$\hskip
28.45274pt\text{Complete Graph with weight $a=3$ }(G_{2})\hskip
28.45274pt$3333333333333333333333333333

######  Theorem 3.10.

Consider $\rho_{G}$ as the density operator of a weighted graph $(G,a)$ with
$n=2^{m}$ vertices where $(G,a)$ represents an $n$-qubit quantum state. If the
reduced density operator ${\rho_{G}}^{A}$ is singular, then the quantum
discord of the quantum state is zero, i.e., $D_{Q}(G,a)=0$.

Proof:Consider $\rho_{G}=[\rho_{ij}]_{2^{m}\times 2^{m}}$ as a density
operator of a weighted graph $(G,a)$ with $n=2^{m}$ vertices where $(G,a)$
represents an $n$-qubit quantum state.

Since $det(\rho^{A}_{G})=0$, we have

$(\rho_{11}+\ldots+\rho_{\frac{n}{2}\frac{n}{2}})(\rho_{{\frac{n}{2}+1}{\frac{n}{2}+1}}+\ldots+\rho_{nn})={\lvert(\rho_{1{\frac{n}{2}+1}}+\rho_{2{\frac{n}{2}+2}}+\ldots+\rho_{\frac{n}{2}n})\lvert}^{2}.$

For $det(L^{A})=0$, it is established that the density operator can be
expressed as a product state [17], where each block commutes with one another.
Therefore, it has been demonstrated.

##  4 Conclusion

In this article, we presented a comprehensive analysis to study and
characterize the properties of weighted graphs. The focus of our study
revolved around the manifestation of zero discord as we presented significant
findings in this area. Using a systematic approach, we divided the density
matrix into distinct blocks, allowing for a thorough evaluation of zero
discord across various quantum states. The outcomes of our investigation will
have important implications for foundational aspects of quantum communication
and computing.

## References

  * [1] Stephen Barnett.  Quantum information, volume 16.  Oxford University Press, 2009.
  * [2] Charles H Bennett, Herbert J Bernstein, Sandu Popescu, and Benjamin Schumacher.  Concentrating partial entanglement by local operations.  Physical Review A, 53(4):2046, 1996.
  * [3] Charles H Bennett, David P DiVincenzo, Christopher A Fuchs, Tal Mor, Eric Rains, Peter W Shor, John A Smolin, and William K Wootters.  Quantum nonlocality without entanglement.  Physical Review A, 59(2):1070, 1999.
  * [4] Charles H Bennett, David P DiVincenzo, John A Smolin, and William K Wootters.  Mixed-state entanglement and quantum error correction.  Physical Review A, 54(5):3824, 1996.
  * [5] Samuel L Braunstein, Sibasish Ghosh, and Simone Severini.  The laplacian of a graph as a density matrix: a basic combinatorial approach to separability of mixed states.  Annals of Combinatorics, 10(3):291–317, 2006.
  * [6] Borivoje Dakić, Vlatko Vedral, and Časlav Brukner.  Necessary and sufficient condition for nonzero quantum discord.  Physical review letters, 105(19):190502, 2010.
  * [7] Animesh Datta, Anil Shaji, and Carlton M Caves.  Quantum discord and the power of one qubit.  Physical review letters, 100(5):050502, 2008.
  * [8] David Deutsch, Artur Ekert, Richard Jozsa, Chiara Macchiavello, Sandu Popescu, and Anna Sanpera.  Quantum privacy amplification and the security of quantum cryptography over noisy channels.  Physical review letters, 77(13):2818, 1996.
  * [9] David P DiVincenzo.  Two-bit gates are universal for quantum computation.  Physical Review A, 51(2):1015, 1995.
  * [10] Wolfgang Dür, Hans Aschauer, and H-J Briegel.  Multiparticle entanglement purification for graph states.  Physical review letters, 91(10):107903, 2003.
  * [11] FF Fanchini, T Werlang, CA Brasil, LGE Arruda, and AO Caldeira.  Non-markovian dynamics of quantum discord.  Physical Review A, 81(5):052107, 2010.
  * [12] Xiu Gu, Jorge Fernández-Pendás, Pontus Vikstål, Tahereh Abad, Christopher Warren, Andreas Bengtsson, Giovanna Tancredi, Vitaly Shumeiko, Jonas Bylander, Göran Johansson, et al.  Fast multiqubit gates through simultaneous two-qubit gates.  PRX Quantum, 2(4):040348, 2021.
  * [13] Ali Saif M Hassan and Pramod S Joag.  A combinatorial approach to multipartite quantum systems: basic formulation.  Journal of Physics A: Mathematical and Theoretical, 40(33):10251, 2007.
  * [14] Roger A Horn and Charles R Johnson.  Matrix analysis.  Cambridge university press, 2012.
  * [15] Michał Horodecki, Paweł Horodecki, and Ryszard Horodecki.  Separability of n-particle mixed states: necessary and sufficient conditions in terms of linear maps.  Physics Letters A, 283(1-2):1–7, 2001.
  * [16] Jie-Hui Huang, Lei Wang, and Shi-Yao Zhu.  A new criterion for zero quantum discord.  New Journal of Physics, 13(6):063045, 2011.
  * [17] Anoopa Joshi, Parvinder Singh, and Atul Kumar.  Entanglement and separability of graph laplacian quantum states.  Quantum Information Processing, 21(4):152, 2022.
  * [18] Anoopa Joshi, Parvinder Singh, and Atul Kumar.  Separability of graph laplacian quantum states: Utilizing unitary operators, neighbourhood sets and equivalence relation.  arXiv preprint arXiv:2401.02289, 2024.
  * [19] Anoopa Joshi, Ranveer Singh, and Atul Kumar.  Concurrence and three-tangle of the graph.  Quantum Information Processing, 17(12):327, 2018.
  * [20] Emanuel Knill and Raymond Laflamme.  Power of one bit of quantum information.  Physical Review Letters, 81(25):5672, 1998.
  * [21] Ben P Lanyon, Marco Barbieri, Marcelo P Almeida, and Andrew G White.  Experimental quantum computing without entanglement.  Physical review letters, 101(20):200501, 2008.
  * [22] Shunlong Luo.  Entanglement as minimal discord over state extensions.  Physical Review A, 94(3):032129, 2016.
  * [23] Kavan Modi, Aharon Brodutch, Hugo Cable, Tomasz Paterek, and Vlatko Vedral.  The classical-quantum boundary for correlations: Discord and related measures.  Reviews of Modern Physics, 84(4):1655, 2012.
  * [24] Michael A Nielsen and Isaac L Chuang.  Quantum computation and quantum information, 2000.
  * [25] Michael A Nielsen and Isaac L Chuang.  Quantum computation and quantum information.  Cambridge university press, 2010.
  * [26] Harold Ollivier and Wojciech H Zurek.  Quantum discord: a measure of the quantumness of correlations.  Physical review letters, 88(1):017901, 2001.
  * [27] Marco Piani, Paweł Horodecki, and Ryszard Horodecki.  No-local-broadcasting theorem for multipartite quantum correlations.  Physical review letters, 100(9):090502, 2008.
  * [28] CC Rulli and MS Sarandy.  Global quantum discord in multipartite systems.  Physical Review A, 84(4):042109, 2011.
  * [29] Alireza Shabani and Daniel A Lidar.  Vanishing quantum discord is necessary and sufficient for completely positive maps.  Physical review letters, 102(10):100402, 2009.
  * [30] Bo Wang, Zhen-Yu Xu, Ze-Qian Chen, and Mang Feng.  Non-markovian effect on the quantum discord.  Physical Review A, 81(1):014101, 2010.
  * [31] Bo-Ying Wang and Ming-Peng Gong.  Some eigenvalue inequalities for positive semidefinite matrix power products.  Linear Algebra and Its Applications, 184:249–260, 1993.
  * [32] T Werlang, S Souza, FF Fanchini, and CJ Villas Boas.  Robustness of quantum discord to sudden death.  Physical Review A, 80(2):024103, 2009.
  * [33] William K Wootters.  Entanglement of formation of an arbitrary state of two qubits.  Physical Review Letters, 80(10):2245, 1998.
  * [34] William K Wootters.  Entanglement of formation and concurrence.  Quantum Information & Computation, 1(1):27–44, 2001.
  * [35] Yao Yao, Hong-Wei Li, Zhen-Qiang Yin, and Zheng-Fu Han.  Geometric interpretation of the geometric discord.  Physics Letters A, 376(4):358–364, 2012.


# BASiS: Batch Aligned Spectral Embedding Space

Or Streicher Ido Cohen Guy Gilboa
Viterbi Faculty of Electrical and Computer Engineering
Technion - Israel Institute of Technology, Haifa, Israel
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Graph is a highly generic and diverse representation, suitable for almost any
data processing problem. Spectral graph theory has been shown to provide
powerful algorithms, backed by solid linear algebra theory. It thus can be
extremely instrumental to design deep network building blocks with spectral
graph characteristics. For instance, such a network allows the design of
optimal graphs for certain tasks or obtaining a canonical orthogonal low-
dimensional embedding of the data. Recent attempts to solve this problem were
based on minimizing Rayleigh-quotient type losses. We propose a different
approach of directly learning the graph’s eigensapce. A severe problem of the
direct approach, applied in batch-learning, is the inconsistent mapping of
features to eigenspace coordinates in different batches. We analyze the
degrees of freedom of learning this task using batches and propose a stable
alignment mechanism that can work both with batch changes and with graph-
metric changes. We show that our learnt spectral embedding is better in terms
of NMI, ACC, Grassman distnace, orthogonality and classification accuracy,
compared to SOTA. In addition, the learning is more stable.

##  1 Introduction

Representing information by using graphs and analyzing their spectral
properties has been shown to be an effective classical solution in a wide
range of problems including clustering [8, 21, 32], classification [13],
segmentation [26], dimensionality reduction [5, 10, 23] and more. In this
setting, data is represented by nodes of a graph, which are embedded into the
eigenspace of the graph-Laplacian, a canonical linear operator measuring local
smoothness.

Incorporating analytic data structures and methods within a deep learning
framework has many advantages. It yields better transparency and understanding
of the network, allows the use of classical ideas, which were thoroughly
investigated and can lead to the design of new architectures, grounded in
solid theory. Spectral graph algorithms, however, are hard to incorporate
directly in neural-networks since they require eigenvalue computations which
cannot be integrated in back-propagation training algorithms. Another major
drawback of spectral graph tools is their low scalability. It is not feasible
to hold a large graph containing millions of nodes and to compute its graph-
Laplacian eigenvectors. Moreover, updating the graph with additional nodes is
combersome and one usually resorts to graph-interpolation techniques, referred
to as Out Of Sample Extension (OOSE) methods.

An approach to solve the above problems using deep neural networks (DNNs),
firstly suggested in [24] and recently also in [9], is to train a network that
approximates the eigenspace by minimizing Rayleigh quotient type losses. The
core idea is that the Rayleigh quotient of a sum of $n$ vectors is minimized
by the $n$ eigenvectors with the corresponding $n$ smallest eigenvalues. As a
result, given the features of a data instance (node) as input, these networks
generate the respective coordinate in the spectral embedding space. This space
should be equivalent in some sense to the analytically calculated graph-
Laplacian eigenvector space. A common way to measure the equivalence of these
spaces is using the Grassman distance. Unfortunately, applying this indirect
approach does not guarantee convergence to the desired eigenspace and
therefore the captured might not be faithful.

An alternative approach, suggested in [18] for computing the diffusion map
embedding, is a direct supervised method. The idea is to compute the embedding
analytically, use it as ground-truth and train the network to map features to
eigenspace coordinates in a supervised manner. In order to compute the ground
truth embedding, the authors used the entire training set. This operation is
very demanding computationally in terms of both memory and time and is not
scalable when the training set is very large.

Figure 1: Toy examples. An Illustration of trained BASiS models over common
spectral-clustering toy examples. Each figure describes the embedding values
given by the network to each point in the space and the clustering results
over selected points. BASiS performs successful clustering and is able to
interpolate and extrapolate the training data smoothly.

Our proposed method is to learn directly the eigenspace in batches. We treat
each batch as sampling of the full graph and learn the eigenvector values in a
supervised manner. A major problem of this kind of scheme is the inconsistency
in the embedding coordinates. Thus, two instances in different batches with
the same features can be mapped to very different eigenspace coordinates. Our
solution is to use affine registration techniques to align the batches.
Further, we use this alignment strategy to also allow changes in the graph
affinity metric. Our proposed method retains the following main qualities: 1)
Scalability. Data is learnt in batches, allowing a training based on large and
complex input sets; 2) OOSE. Out of sample extension is immediate. 3) High
quality approximation of the eigenspace. Since our learning method is direct
and fully supervised, an excellent approximation of the graph eigenspace is
obtained. 4) Robustness to features change. We can train the model also when
features and affinities between nodes change; All the above properties yield a
spectral building block which can be highly instrumental in various deep
learning algorithms, containing an inherent orthogonal low dimensional
embedding of the data, based on linear algebraic theory.

##  2 Settings and Notations

Let $\\{x_{i}\\}_{i=1}^{n}$ be a set of data instances denoted as $X$ which is
a finite set in $\mathbb{R}^{d}$. These samples are assumed to lie on a lower
dimensional manifold $\mathcal{M}$.

These instances are represented as nodes on an undirected weighted graph
$G=(V,E,W)$, where $V$ and $E$ are sets of the vertices and edges,
respectively, and $W$ is the adjacency matrix. This matrix is symmetric and
defined by a distance measure between the nodes. For example, a common choice
is a Gaussian kernel and Euclidean distance,

$W_{ij}=\exp\left(-\frac{||x_{i}-x_{j}||_{2}^{2}}{2\sigma^{2}}\right),$ (1)

where $\sigma$ is a soft-threshold parameter.

The degree matrix $D$ is a diagonal matrix where $D_{ii}$ is the degree of the
$i$-th vertex, i.e., $D_{ii}=\sum_{j}{W_{ij}}$. The graph-Laplacian operator
is defined by,

$L\mathrel{\mathop{\mathchar 58\relax}}=D-W.$ (2)

The graph-Laplacian is a symmetric, positive semi-definite matrix, its
eigenvalues are real, and its eigenvectors form an orthogonal basis. The
eigenvalues of $L$ are sorted in ascending order
$\lambda_{1}\leq\lambda_{2}\leq...\leq\lambda_{n}$, where the corresponding
eigenvectors are denoted by $u_{1},u_{2}...,u_{n}$. The sample $x_{i}$ is
represented in the spectral embedding space as the $i$th row of the matrix
$U=\begin{bmatrix}u_{1}&\cdots&u_{K}\end{bmatrix}\in\mathbb{R}^{n\times K}$,
denoted as $\varphi_{i}$. Thus, more formally, the dimensionality reduction
process can be formulated as

$x_{i}\longmapsto\varphi_{i}=[u_{1}(i),u_{2}(i),...,u_{K}(i)]\in\mathbb{R}^{K},$
(3)

where $K\ll d$. This representation preserves well essential data information
[10, 15, 17, 22]

Alternatively, one can replace the Laplacian definition (2) with

$L_{N}\mathrel{\mathop{\mathchar
58\relax}}=D^{-\frac{1}{2}}LD^{-\frac{1}{2}}=I-D^{-\frac{1}{2}}WD^{-\frac{1}{2}}.$
(4)

This matrix may yield better performances for certain tasks and datasets [25,
26, 27].

##  3 Related Work

OOSE and scalability of graph-based learning methods are ongoing research
topics. Mathematical analyses and analytical solutions to these problems can
be found, for example, in [1, 4, 7, 12, 30]. However, neural networks learning
the latent space of the data usually yield an efficient, robust and reliable
solution for these problems. Moreover, neural network modules can be easily
integrated in larger networks, employing this embedding. For a recent use of
learnable graphs in semi-supervised learning and data visualization see [2].
The effectiveness of modeling PDE’s and certain eigenproblems in grid-free,
mesh-free manner was shown in [3, 29, 6]. We review below the main advances in
eigenspace embedding.

Diffusion Nets [18]. Diffusion Maps (DM) is a spectral embedding, resulting
from the eigendecomposition of

$P\mathrel{\mathop{\mathchar 58\relax}}=WD^{-1},$ (5)

known as the random-walk matrix [10]. More formally, similarly to Eq. 3,
diffusion maps is defined by

$x_{i}\longmapsto\varphi_{i}=[\gamma_{1}^{t}\Phi_{1}(i),\gamma_{2}^{t}\Phi_{2}(i),...,\gamma_{K}^{t}\Phi_{K}(i)]\in\mathbb{R}^{K},$
(6)

where $\\{\Phi_{j}\\}_{j=1}^{K}$ are the first non-trivial eigenvectors of
$P$, $\\{\gamma\\}_{i=j}^{K}$ are the corresponding eigenvalues and $t>0$ is
the diffusion time. Note, that $P$ and $L_{N}$ have the same eigenvectors, in
reverse order with respect to their eigenvalues.

Diffusion Net (DN) is an autoencoder trained to map between the data and the
DM. The loss function of the encoder is defined by,

$\mathcal{L}_{DN}^{e}(\theta^{e})=\frac{1}{2n}\sum_{i=1}^{n}\mathinner{\\!\left\lVert
f_{\theta^{e}}^{e}(x_{i})-\phi_{i}\right\rVert}^{2}+F(\theta^{e},X),$ (7)

where $\theta^{e}$ denotes the encoder’s parameters,
$f_{\theta^{e}}^{e}(x_{i})$ is the encoder output and
$F(\theta^{e},X)=\frac{\mu}{2}\sum_{l=1}^{L-1}{\mathinner{\\!\left\lVert\theta^{e}{{}_{l}}\right\rVert}_{F}^{2}}+\frac{\eta}{2m}\sum_{j=1}^{d}{||(P-\gamma_{j}I)(o^{e}_{j})^{T}||^{2}}$
is a regularization term such that $\theta^{e}{{}_{l}}$ are the weights of the
$l$-th layer, $o^{e}_{j}$ is the $j$-th column of the output matrix, $\mu$ and
$\eta$ are regularization parameters. Note, Diffusion Net requires to compute
the embedding of the training set in advance, meaning _it cannot be trained
with mini-batches_ and therefore has difficulty dealing with large datasets.

SpectralNet1 [24] (SpecNet1). This DNN learns the embedding corresponds to $L$
by minimizing the _ratio-cut_ loss of Ng _et al_. [21], without adding an
orthogonality constraint on the solution, with the loss

$\mathcal{L}_{SN1}(\theta)=\frac{1}{m^{2}}\sum_{i,j=1}^{m}{W_{i,j}||y_{i}-y_{j}||^{2}}=\frac{2}{m^{2}}\textrm{tr}(Y^{T}LY),$
(8)

where $y_{i}=f_{\theta}(x_{i})$ is the network output, $m$ is the batch size,
and tr is the trace operator. In order to calculate the eigenvectors of
$L_{N}$, one should normalize $y_{i},y_{j}$ with the corresponding node
degree. In SpectralNet1 orthogonality of the training is gained by defining
the last layer of the network as a linear layer set to orthogonalize the
output. The last layer’s weights are calculated during training with QR
decomposition over the DNN’s outputs. The authors point out that in order to
get good generalization and approximate orthogonal output at inference, large
batches are required.

SpectralNet2 [9] (SpecNet2). In this recent work the authors suggested to
solve the eigenpair problem of the matrix pencil $(W,D)$. The loss function is
defined by,

$\mathcal{L}_{SN2}(\theta)=\frac{1}{m^{2}}\textrm{tr}\left(-2Y^{T}WY+\frac{1}{m^{2}}Y^{T}DYY^{T}DY\right),$
(9)

where $Y$ is the network’s output. Given the output $Y$, an approximation to
the eigenvectors of $P$, Eq. 5, can be calculated as $\hat{U}=YO$ where
$O\in\mathbb{R}^{K\times K}$ satisfies

$\displaystyle Y^{T}WYO=Y^{T}DYO\Lambda,$ (10)

where $\Lambda$ is a refined approximation of the eigenvalue matrix of
$(W,D)$. Note that Eq. 10 requires a batch for its computation, which may be
problematic at inference. The authors show qualitatively a successful
approximation to the analytical embedding.

(a)

(b)

(c)

(d)

Figure 2: Illustration. The full dataset of three separated clusters, divided
into two subsets and anchors is shown in Fig. 2(a). Figs. 2(b)-2(c) show the
embedding spaces of subset $\\#1$ and subset $\\#2$, respectively. Fig. 2(d)
shows the embedding space of the entire data after aligning the embedding of
subset $\\#1$ to that of subset $\\#2$.

##  4 Our Method

###  4.1 Motivation

Our goal is to learn a model $f\mathrel{\mathop{\mathchar
58\relax}}\mathcal{M}\rightarrow\mathbb{R}^{K}$, where given a sample
$x\in\mathcal{M}$ approximates well the corresponding $\varphi$ of Eq. 3. As
is common with DNN learning, given a large training set, we would like to
train the model by splitting the dataset into batches. A batch can be viewed
as sampling the graph of the training set. A straightforward approach would be
to compute the eigenspace of each batch and to learn a mapping from $x$ to
$\varphi$, using a data loss similar to Diffusion Nets. The problem is that
different samples of the training set most often lead to different embeddings.
Specifically, the same instance $x_{i}$ can be mapped very differently in each
batch.

This can be demonstrated in a very simple toy example, shown in Fig. 2, which
illustrates the core problem and our proposed solution. Three distinct
clusters in Euclidean space are sampled in two trials (batches) and the
eigenspace embedding is computed analytically. Three samples appear in both
subsets, one for each cluster (red color). We refer to the common samples as
_anchors_. The plots of the instances in the embedding space for the two
subsets are shown in Figs. 2(b)-2(c). One can observe the embeddings are
different. Specifically, all anchors, which appear in both samplings, are
mapped differently in a substantial way. It is well known that eigenvector
embedding has a degree of freedom of rotation (as shown for example in [32]).
However, in the case of uneven sampling of clusters there may be also some
scale changes and slight translation (caused by the orthonormality
constraints). We thus approximate these degrees of freedom in the general case
as an affine rigid transformation according to the anchors. Aligning one
embedding space to the other one, using this transformation, yields a
consistent embedding, as can be seen in Fig. 2(d). Following the alignment
process, the embedding can be learnt well using batches.

In the toy example of the Three Moons, see Fig. 3, we show the mapping of $9$
anchor-points, as shown in Fig. 3(b). In Figs. 3(c)-3(d) the analytic
computation of the first two non-trivial eigenvectors are plotted for $20$
different batch samples of size $256$ (out of $9000$ nodes in the entire
dataset), all of which contain the $9$ points. In this simple example anchors
located on the same moon receive approximately the same value. However, in
different batches the embedding of the anchors is clearly inconsistent.
Surely, a network cannot be expected to generalize such a mapping. After
learning the transformation and performing alignment, the embedding values are
consistent. In Figs. 3(e)-3(f) the values are shown after our correction
procedure. This consistency allows to train DNN to learn the desired
embedding, by dividing the data into batches. The result of the trained DNN
model for the Three Moons dataset appears in Fig. 1 (second from left). These
toy examples lead us to the detailed description of our algorithm.

(a)

(b)

(c)

(d)

(e)

(f)

Figure 3: Three-Moons toy example. The full dataset is shown in Fig. 3(a) and
the chosen anchor-nodes in Fig. 3(b). Figs. 3(c)\- 3(d) show the values of the
two leading eigenvectors for the anchors, for 20 different graph-samples.
Figs. 3(e)\- 3(f) show those values after our proposed alignment.

###  4.2 BASiS Algorithm

We propose to calculate the embedding space with batches. To obtain
consistency in this representation, we calculate the first-order approximation
of the distortion obtained in the eigenvector values between different samples
of the data. The main steps of our algorithm are as follows: First we perform
two preliminary initialization steps.

Defining an anchor set. Draw $l$ samples from the data. This subset is denoted
as $V^{a}$ and will be added to any batch in the learning process.

Defining the reference embedding space. We would like to define the embedding
space of the anchor set as a reference space. However, to get more information
about the manifold $\mathcal{M}$, we add $m-l$ samples (randomly) and term it
as the reference set $V^{ref}$. After calculating the embedding
$V^{ref}\to\varphi^{ref}$ (as in Eq. 3), one can extract the coordinates of
the anchor samples,

$V^{a}\to\\{\varphi^{a,ref}_{i}\\}_{i=1}^{l}.$ (11)

Following this initialization, the main steps of the training are as follows:

Calculate the embedding space over a new batch. Draw $m-l$ new samples and add
them to the anchor set. Let us denote the union set as $V^{b}$. We calculate
$\\{\varphi_{i}\\}_{i=1}^{m}$, the embedding of $V^{b}$ and extract the
embedding $\\{\varphi^{a}_{i}\\}_{i=1}^{l}$ corresponding to the anchors.

Calculate the alignment transformation. Now, we calculate the alignment
transformation between $\\{\varphi^{a}_{i}\\}_{i=1}^{l}$ to
$\\{\varphi^{a,ref}_{i}\\}_{i=1}^{l}$. More formally, for
$\varphi^{a},\varphi^{a,ref}\in\mathbb{R}^{K}$ we find
$A\in\mathbb{R}^{K\times K}$ and $b\in\mathbb{R}^{K}$ which minimize

$\min_{A,b}\sum_{i=1}^{l}{\mathinner{\\!\left\lVert\varphi^{a,ref}_{i}-(A\varphi^{a}_{i}+b)\right\rVert}^{2}}.$
(12)

Alternatively, one can define $\hat{\varphi}^{a}=[\varphi^{a},1]$ and find the
transformation $T\in\mathbb{R}^{K\times(K+1)}$ such that

$\min_{T}\sum_{i=1}^{l}{\mathinner{\\!\left\lVert\varphi^{a,ref}_{i}-T\hat{\varphi}^{a}_{i}\right\rVert}^{2}}.$
(13)

In this case there are $K\times(K+1)$ degrees of freedom. Each anchor provides
$K$ constraints, that means at least $K+1$ anchors are needed in order to
solve this least squares problem. Since in many real-world problem there is
noise in the measurements, it is customary to solve such problems in an
overdertermined setting, using a higher number of anchors. In addition, given
a large number of anchors, the transformation can be calculated using best
matches - for example by using the RANdom SAmple Consensus (RANSAC) algorithm
[11].

Batch Alignment. Given the transformation $T$, we can align the embedding
$\\{\varphi_{i}\\}_{i=1}^{m}$ of all the instances of $V^{b}$. We define
$\hat{\varphi}=[\varphi,1]$ and update

$\varphi\leftarrow T\hat{\varphi}.$ (14)

Gradient Step. Now that we have a mechanism that allows to get consistent
embedding, we can train the DNN by dividing the data into batches and use a
simple MSE lose function

$\mathcal{L}_{BASiS}(\theta)=\frac{1}{m}\sum_{i=1}^{m}\mathinner{\\!\left\lVert
y_{i}-\varphi_{i}\right\rVert}^{2},$ (15)

where $y_{i}=f_{\theta}(x_{i})$ is the DNN’s output and $\varphi_{i}$ is the
embedding of $x_{i}$ after alignment.

The full training scheme is detailed in Algorithm 1.

Algorithm 1 BASiS Training Scheme

1:Inputs:

2: data features $\\{x_{i}\\}_{i=1}^{n}$, number of eigenvectors $K$, batch
size $m$, number of anchors $l$.

3:Outputs:

4: Spectral embedding model $f\mathrel{\mathop{\mathchar
58\relax}}\mathcal{M}\rightarrow\mathbb{R}^{K}$

5:Initialize:

6: Define anchor set $V^{a}$. Extract $\\{\varphi^{a,ref}_{i}\\}_{i=1}^{l}$,
the reference embedding of $V^{a}$ using Eq. 11

7:while $\mathcal{L}_{BASiS}(\theta)$ not converged do

8: Draw $m-l$ new samples.

9: Define node set $V^{b}$ as union of the anchors with the new sampled nodes.

10: Calculate the embedding $\\{\varphi_{i}\\}_{i=1}^{m}$ of $V^{b}$.

11: Calculate the optimal transformation $T$, Eq. 13.

12: Align $\\{\varphi_{i}\\}_{i=1}^{m}$ with $T$ , Eq. 14.

13: Do a gradient step of $\mathcal{L}_{BASiS}$, Eq. 15.

14:end while

###  4.3 BASiS for feature perturbation

In the process of network training, the features are often not fixed and
slightly change each iteration during training. In this case the adjacency
values change and hence naturally also the embedding space. We suggest an
algorithm to allow iterative changes in the feature space (inducing different
graph metric). This algorithm is also based on an alignment technique. Similar
to Algorithm 1, we define anchor nodes. Given the current features, we extract
$\\{\varphi^{a,prev}_{i}\\}_{i=1}^{l}$, the current spectral embedding of the
anchors. When the features are updated, we find the new embedding of the
anchors $\\{\varphi^{a,update}_{i}\\}_{i=1}^{l}$. In order to maintain
consistency in the learning process, we find a transformation $T_{G}$, as in
Eq. 13, that aligns the updated anchor embedding to the previous one. Then we
align the entire embedding space according to the calculated transformation.
Algorithm 2 summarizes the proposed method.

Algorithm 2 BASiS under iterative feature change

1:Inputs:

2: $\\{\varphi^{a,prev}_{i}\\}_{i=1}^{l}$ the anchors embedding over previous
features $\\{x_{i}\\}_{i=1}^{n}$, updated features
$\\{\hat{x}_{i}\\}_{i=1}^{n}$.

3:Outputs:

4: $\\{\varphi^{update}_{i}\\}_{i=1}^{n}$ the spectral embedding over the
updated features, aligned to $\\{\varphi^{a,prev}_{i}\\}_{i=1}^{l}$.

5:Calculate the embedding $\\{\varphi^{update}_{i}\\}_{i=1}^{n}$ over the
updated features.

6:Extract $\\{\varphi^{a,update}_{i}\\}_{i=1}^{l}$ the embedding correspond to
the anchors.

7:Calculate the transformation $T_{G}$ between
$\\{\varphi^{a,prev}_{i}\\}_{i=1}^{l}$ and
$\\{\varphi^{a,update}_{i}\\}_{i=1}^{l}$.

8:Align $\\{\varphi^{update}_{i}\\}_{i=1}^{n}$ with $T_{G}$.

Measures |  Networks |  MNIST |  Fashion-MNIST |  SVHN |  CIFAR-10
---|---|---|---|---|---
$d_{G}$↓ |  Diffusion-Net |  $0.204\pm 0.058$ |  $0.488\pm 0.238$ |  $1.909\pm 0.238$ |  $1.022\pm 0.250$
|  SpecNet1 |  $0.386\pm 0.074$ |  $0.375\pm 0.132$ |  $3.526\pm 0.529$ |  $2.256\pm 0.471$
|  SpecNet2 |  $1.388\pm 0.262$ |  $1.976\pm 0.210$ |  $1.903\pm 0.242$ |  $2.970\pm 0.682$
|  BASiS (Ours) |  $\bf{0.107\pm 0.038}$ |  $\bf{0.284\pm 0.073}$ |  $\bf{1.656\pm 0.170}$ |  $\bf{0.803\pm 0.085}$
$d_{\perp}$↓ |  Diffusion-Net |  $0.535\pm 0.365$ |  $0.823\pm 0.664$ |  $1.532\pm 0.354$ |  $2.957\pm 1.837$
|  SpecNet1 |  $6.296\pm 0.922$ |  $6.384\pm 0.899$ |  $4.507\pm 0.821$ |  $5.169\pm 0.775$
|  SpecNet2 |  $9.486\pm 0.001$ |  $8.561\pm 1.397$ |  $4.104\pm 0.269$ |  $4.922\pm 0.102$
|  BASiS (Ours) |  $\bf{0.247\pm 0.076}$ |  $\bf{0.590\pm 0.144}$ |  $\bf{0.488\pm 0.098}$ |  $\bf{0.407\pm 0.095}$
NMI↑ |  Diffusion-Net |  $0.944\pm 0.041$ |  $0.759\pm 0.085$ |  $0.645\pm 0.016$ |  $0.466\pm 0.034$
|  SpecNet1 |  $0.911\pm 0.008$ |  $0.761\pm 0.011$ |  $0.665\pm 0.018$ |  $0.443\pm 0.012$
|  SpecNet2 |  $0.925\pm 0.012$ |  $0.759\pm 0.010$ |  $0.701\pm 0.009$ |  $0.466\pm 0.013$
|  BASiS (Ours) |  $\bf{0.961\pm 0.001}$ |  $\bf{0.798\pm 0.001}$ |  $\bf{0.736\pm 0.001}$ |  $\bf{0.501\pm 0.001}$
ACC↑ |  Diffusion-Net |  $0.944\pm 0.030$ |  $0.781\pm 0.179$ |  $0.687\pm 0.303$ |  $0.620\pm 0.062$
|  SpecNet1 |  $0.963\pm 0.005$ |  $0.815\pm 0.029$ |  $0.811\pm 0.039$ |  $0.637\pm 0.029$
|  SpecNet2 |  $0.966\pm 0.007$ |  $0.801\pm 0.023$ |  $0.813\pm 0.015$ |  $0.606\pm 0.039$
|  BASiS (Ours) |  $\bf{0.986\pm 0.001}$ |  $\bf{0.865\pm 0.003}$ |  $\bf{0.880\pm 0.001}$ |  $\bf{0.688\pm 0.001}$
Accuracy(%)↑ |  Diffusion-Net |  $95.508\pm 1.449$ |  $86.207\pm 0.196$ |  $86.850\pm 1.386$ |  $67.316\pm 2.112$
|  SpecNet1 |  $92.278\pm 4.776$ |  $84.123\pm 1.229$ |  $85.154\pm 0.377$ |  $65.336\pm 0.626$
|  SpecNet2 |  $97.026\pm 0.546$ |  $85.953\pm 0.240$ |  $87.469\pm 0.130$ |  $67.093\pm 0.644$
|  BASiS (Ours) |  $\bf{98.522\pm 0.065}$ |  $\bf{87.202\pm 0.187}$ |  $\bf{88.021\pm 0.064}$ |  $\bf{68.887\pm 0.128}$
Table 1: Spectral embedding performance comparison. Average performance
obtained over 10 different installations of each of the four methods. In each
experiment we learn an embedding space in dimension of 10 for 1000 training
iterations using batches of size 512.

##  5 Experimental Results

In this section we examine the ability of BASiS to learn the graph-spectral
embedding over different datasets quantifying its success using several
performance measures. Our method is able to learn any desired eigen embedding
(since it is supervised by analytic calculations). To fairly compare our
method to the ones mentioned in Sec. 3 we calculate the eigenspace of $L_{N}$
(Eq. 4). For all methods the DNN’s architecture includes $5$ fully connected
(FC) layers with ReLU activation in between (see full details in the
supplementary).

###  5.1 Evaluation Metrics

We evaluate our results using several measures. We calculate the Grassmann
distance (projection metric) [14] between the network output and the
analytically calculated eigenvectors. The squared Grassmann distance between
two orthonormal matrices $Y_{1},Y_{2}\in\mathbb{R}^{n\times K}$ is defined as:

$d_{G}(Y_{1},Y_{2})=K-\sum_{i=1}^{K}{cos^{2}\theta_{i}},$ (16)

where $0\leq\theta_{1}\leq...\leq\theta_{K}\leq\frac{\pi}{2}$ are the
principal angles between the two subspaces $span(Y_{1})$ and $span(Y_{2})$.
The distance is in $[0,K]$ where lower values indicate greater proximity
between the subspaces.

A second measure is the degree of orthogonality of the DNN’s output $Y$. We
use the following orthogonality measure:

$d_{\perp}(Y)=||Y^{T}Y-I||_{F}^{2},$ (17)

where $I$ is an identity matrix and $||\cdot||_{F}$ is the Frobenius norm. For
$Y$ containing columns of orthonormal vectors we get $d_{\perp}(Y)=0$. In
general, we expect this measure to be close to zero in proper embeddings.

To evaluate the potential clustering performance we examined two common
metrics: Normalized mutual information (NMI) and unsupervised clustering
accuracy (ACC). The clustering result is achieved by preforming the K-Means
algorithm over the spectral embedding. Both indicators are in the range
$[0,1]$, where high values indicate a better correspondence between the
clustering result and the true labels. NMI is defined as,

$NMI(c,\hat{c})=\frac{I(c,\hat{c})}{max\\{H(c),H(\hat{c})\\}},$ (18)

where $I(c,\hat{c})$ is the mutual information between the true labels $c$ and
the clustering result $\hat{c}$ and $H(\cdot)$ denotes entropy. ACC is defined
as,

$ACC(c,\hat{c})=\frac{1}{n}\max_{\pi\in\Pi}{\sum_{i=1}^{n}{\mathbbm{1}\\{c_{i}=\pi(\hat{c}_{i})\\}}},$
(19)

where $\Pi$ is the set of possible permutations of the clustering results. To
choose the optimal permutation $\pi$ we followed [24] and used the Kuhn-
Munkres algorithm [19].

Finally, we examine how suitable the embedding is for classification. We
trained (with Cross-Entropy loss) a supervised linear regression model
containing a single fully connected layer without activation, and examined its
accuracy:

$Accuracy(c,\hat{c})=\frac{1}{n}{\sum_{i=1}^{n}{\mathbbm{1}\\{c_{i}=\hat{c}_{i}\\}}}.$
(20)

###  5.2 Spectral Clustering

In this section we examine the ability of our method to learn the spectral
embedding for clustering of different datasets. First, we examine the
performance for well-known spectral clustering toy examples, appearing in Fig.
1. In these examples the dataset includes $9000$ nodes and the model is
trained by calculating the first non-trivial eigenvectors (sampling $256$
nodes, using $1000$ iterations). In all the experiments NMI and ACC of 1.0
were obtained over the test set (i.e., perfect clustering results). In
addition, as demonstrate in Fig. 1, the learnt model is able to generalize the
clustering result and performs smooth interpolation and extrapolation of the
space mapping. We note that no explicit regularization loss is used in our
method, generalization and smoothness are obtained naturally through the
neural training process.

Next we compare the performance of BASiS to those of the models mentioned in
Sec. 3. We examine the results over 4 well-known image datasets: MNIST,
Fashion-MNIST [31], SVHN [20] and CIFAR-10 [16]. For each dataset we first
learn an initial low-dimensional representation, found to be successful for
graph-based learning, by a Siamese network, a convolutional neural network
(CNN) trained in a supervised manner using Contrastive loss

$\displaystyle\mathcal{L}_{Cont}(x_{i},x_{j},\theta)=\mathbbm{1}\\{y_{i}=y_{j}\\}\mathinner{\\!\left\lVert
f^{rep}_{\theta}(x_{i})-f^{rep}_{\theta}(x_{j})\right\rVert}_{2}^{2}$ (21)
$\displaystyle+\mathbbm{1}\\{y_{i}\neq
y_{j}\\}\max(0,\epsilon-\mathinner{\\!\left\lVert
f^{rep}_{\theta}(x_{i})-f^{rep}_{\theta}(x_{j})\right\rVert}_{2})^{2},$

where $f^{rep}_{\theta}(x_{i})$ is the Siamese network’s output for input
image $x_{i}$ labeld as $y_{i}$ , $\epsilon\in\mathbb{R}^{+}$. More details on
the architecture of the Siamese network are in the supplementary material. We
use this representations as inputs to the spectral embedding models. In all
the experiments the graph affinity matrix $W$ is defined by Eq. 1, using the
$50$ nearest neighbors of each node. We use $50$ neighbors in order that all
methods could perform well (see sensitivity analysis hereafter). The model is
trained to learn the first $K$ eigenvectors, where $K$ is equal to the number
of clusters. The batch size is set to $m=512$. For our method, we randomly
select $25$ anchor-nodes from each cluster and use RANSAC to find the best
transformation.

Comparison between the methods is summarized in Table 1. The numbers are
obtained by showing the average and empirical standard deviation of each
measure, as computed based on $10$ experiments.

Since the training process in Diffusion Net is not scalable, in each
initialization we randomly sampled a single batch from the training set and
trained the model with the analytically calculated spectral embedding. In
relation to SpecNet2, as indicated in Sec. 3, to obtain an approximation of
the spectral space, SpecNet2 requires a post-processing stage over the
network’s output. In order to maintain consistency and obtain reasonable
performance for all measures, the post-processing is performed over the entire
test set (this naturally limits the method and increases the level of
complexity at inference). More implementation details are in the
supplementary. Table 1 shows that our method is superior and more stable in
approximating the analytical embedding and in clustering.

We further examined the robustness of the methods to changes in the number of
neighbors for each node. This parameter defines the connectivity of the graph
in the affinity matrix. Fig. 4 shows the average and the empirical standard
deviation of the performance measures, for $50$ training procedures over the
MNIST dataset. It is shown that our method is highly robust and consistent. We
note the high sensitivity of Diffusion Net to this meta-parameter.

(a)

(b)

(c)

(d)

Figure 4: Robustness to the node neighborhood. The average and standard
deviation of $50$ different training experiments over the MNIST dataset, for
different number of neighbors per node.

(a)

(b)

(c)

(d)

Figure 5: Diffusion Maps encoding. Data set of 2000 snapshots of bunny on
rotating display [17]. Fig. 5(a) shows snapshot examples. Fig. 5(b) present
the analytically calculated DM embedding for the full dataset . The test set
analytical embedding is shown in Fig. 5(c) and the network output for the test
set in Fig. 5(d).

###  5.3 Diffusion Maps Encoding

We examine the ability of our model to learn the DM embedding (6). For this
purpose we use the dataset from [17] which includes $2000$ snapshots of toy
bunny located on a rotating surface. Six examples of such frames are shown in
Fig. 5(a). We define a graph using the $20$ nearest neighbors of each node,
and calculate the random-walk matrix $P$ (5). Raw pixels are used as features
(dimension $288,000$). Dimension reduction is performed with DM to
$\mathbb{R}^{2}$. In Fig. 5(b) the analytically calculated embedding obtained
based on the entire dataset is shown. Our model was trained to approximate
this embedding using $1500$ images. Test is performed over $500$ images. Fig.
5(c) shows the analytically calculated embedding over the test snapshots. Fig.
5(d) shows the embedding obtained by our trained model. Our method approximate
well the analytic calculation.

###  5.4 Iterative Change of Features

In this section we illustrate the performance of Algorithm 2 for aligning the
spectral embedding space under changing features. We define two DNN models.
The first one is for feature extraction, trained to minimize the Contrastive
loss (21). The second is trained for calculating the spectral embedding, using
Algorithm 1, based on the output of the features model. Both models are
trained simultaneously. The feature model is trained for $1500$ iterations,
where every tenth iteration we perform an update step for the spectral
embedding model. To maintain consistency under the feature change, we align
the spectral space using Algorithm 2 before performing an update step for the
spectral model. Fig. 6 shows the results of the training process over the
MNIST dataset where the learnt features are of dimension $16$ and the
eigenvectors are of dimension $9$. Fig. 7 shows a visualization (TSNE [28]) of
the test set embedding at the beginning and the end of the training process.
The two modules were able to converge and to reach good clustering results. In
addition, when the loss of the spectral module is sufficiently low (around
iteration 800, marked with a red line in Fig. 6) the clustering performance of
the spectral module is comparable to the analytic embedding, calculated with
the current features (the orange and the green plots tightly follow the blue
plot).

To illustrate the role of the transformation $T_{G}$, we show in Fig. 8 the
results of another experiment using a similar setting. For better
visualization, the training is only for three digits of MNIST: 4,7 and 9. The
embedding (and visualization) is two dimensional. It can be seen that $T_{G}$
imposes consistency of the resulting embedding under feature change, allowing
convergence and good approximation of the eigenvector space.

(a)

(b)

(c)

(d)

Figure 6: Training under feature change. Evolution of measures during training
(MNIST). 6(a)-6(b) losses of the features module and the spectral embedding
module, respectively. 6(c)-6(d) – clustering measures. Blue, analytic
calculation of the eigenvectors based on current features. Orange and green,
output of spectral embedding module (training and validation sets,
respectively).

(a)

(b)

Figure 7: Test set embedding. Visualization (TSNE) of the spectral embedding,
MNIST test set. Fig. 7(a) shows the spectral embedding at the beginning of
training, Fig. 7(b) at the end.

Figure 8: Features change demonstration Left column: the analytically
calculated spectral embedding of $V^{ref}$ obtained over the features module
output. Distortion is a consequence of feature change. Middle column: Spectral
embedding of $V^{ref}$ after alignment with $T_{G}$ . Right column: Network
spectral embedding of the test set. Each row represents the embeddings for the
10th, 100th, 500th and 1500th iteration, respectively.

##  6 Conclusion

In this paper we introduced BASiS, a new method for learning the eigenspace of
a graph, in a supervised manner, allowing the use of batch training. Our
proposed method has shown to be highly robust and accurate in approximating
the analytic spectral space, surpassing all other methods with respect to
Grassman distance, orthogonality, NMI, ACC and accuracy, over various
benchmarks. In addition, we proposed an adaptation of our procedure for
learning the eigenspace during iterative changes in the graph metric (as
common in neural training). Our method can be viewed as a useful building
block for integrating analytical spectral methods in deep learning algorithms.
This enables to effectively use extensive theory and practices available,
related to classical spectral embedding.

Acknowledgements. We acknowledge support by the Israel Science Foundation
(Grant No. 534/19), by the Ministry of Science and Technology (Grant No.
5074/22) and by the Ollendorff Minerva Center.

## References

  * [1] Carlos Alzate and Johan AK Suykens.  Multiway spectral clustering with out-of-sample extensions through weighted kernel pca.  IEEE transactions on pattern analysis and machine intelligence, 32(2):335–347, 2008.
  * [2] Angelica I Aviles-Rivero, Philip Sellars, Carola-Bibiane Schönlieb, and Nicolas Papadakis.  Graphxcovid: explainable deep graph diffusion pseudo-labelling for identifying covid-19 on chest x-rays.  Pattern Recognition, 122:108274, 2022.
  * [3] Leah Bar and Nir Sochen.  Strong solutions for pde-based tomography by unsupervised learning.  SIAM Journal on Imaging Sciences, 14(1):128–155, 2021.
  * [4] Mohamed-Ali Belabbas and Patrick J Wolfe.  On landmark selection and sampling in high-dimensional data analysis.  Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 367(1906):4295–4312, 2009.
  * [5] Mikhail Belkin and Partha Niyogi.  Laplacian eigenmaps for dimensionality reduction and data representation.  Neural computation, 15(6):1373–1396, 2003.
  * [6] Ido Ben-Shaul, Leah Bar, and Nir Sochen.  Solving the functional eigen-problem using neural networks.  arXiv preprint arXiv:2007.10205, 2020.
  * [7] Yoshua Bengio, Jean-françcois Paiement, Pascal Vincent, Olivier Delalleau, Nicolas Roux, and Marie Ouimet.  Out-of-sample extensions for lle, isomap, mds, eigenmaps, and spectral clustering.  Advances in neural information processing systems, 16, 2003.
  * [8] Xavier Bresson, Thomas Laurent, David Uminsky, and James H Von Brecht.  Multiclass total variation clustering.  arXiv preprint arXiv:1306.1185, 2013.
  * [9] Ziyu Chen, Yingzhou Li, and Xiuyuan Cheng.  Specnet2: Orthogonalization-free spectral embedding by neural networks.  arXiv preprint arXiv:2206.06644, 2022.
  * [10] Ronald R Coifman and Stéphane Lafon.  Diffusion maps.  Applied and computational harmonic analysis, 21(1):5–30, 2006.
  * [11] Martin A Fischler and Robert C Bolles.  Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography.  Communications of the ACM, 24(6):381–395, 1981.
  * [12] Charless Fowlkes, Serge Belongie, Fan Chung, and Jitendra Malik.  Spectral grouping using the nystrom method.  IEEE transactions on pattern analysis and machine intelligence, 26(2):214–225, 2004.
  * [13] Cristina Garcia-Cardona, Ekaterina Merkurjev, Andrea L Bertozzi, Arjuna Flenner, and Allon G Percus.  Multiclass data segmentation using diffuse interface methods on graphs.  IEEE transactions on pattern analysis and machine intelligence, 36(8):1600–1613, 2014.
  * [14] Jihun Hamm and Daniel D Lee.  Grassmann discriminant analysis: a unifying view on subspace-based learning.  In Proceedings of the 25th international conference on Machine learning, pages 376–383, 2008.
  * [15] Ori Katz, Ronen Talmon, Yu-Lun Lo, and Hau-Tieng Wu.  Alternating diffusion maps for multimodal data fusion.  Information Fusion, 45:346–360, 2019.
  * [16] Alex Krizhevsky, Geoffrey Hinton, et al.  Learning multiple layers of features from tiny images.  2009\.
  * [17] Roy R Lederman and Ronen Talmon.  Learning the geometry of common latent variables using alternating-diffusion.  Applied and Computational Harmonic Analysis, 44(3):509–536, 2018\.
  * [18] Gal Mishne, Uri Shaham, Alexander Cloninger, and Israel Cohen.  Diffusion nets.  Applied and Computational Harmonic Analysis, 47(2):259–285, 2019\.
  * [19] James Munkres.  Algorithms for the assignment and transportation problems.  Journal of the society for industrial and applied mathematics, 5(1):32–38, 1957.
  * [20] Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng.  Reading digits in natural images with unsupervised feature learning.  2011\.
  * [21] Andrew Ng, Michael Jordan, and Yair Weiss.  On spectral clustering: Analysis and an algorithm.  Advances in neural information processing systems, 14, 2001.
  * [22] Antonio Ortega, Pascal Frossard, Jelena Kovačević, José MF Moura, and Pierre Vandergheynst.  Graph signal processing: Overview, challenges, and applications.  Proceedings of the IEEE, 106(5):808–828, 2018.
  * [23] Sam T Roweis and Lawrence K Saul.  Nonlinear dimensionality reduction by locally linear embedding.  science, 290(5500):2323–2326, 2000.
  * [24] Uri Shaham, Kelly Stanton, Henry Li, Boaz Nadler, Ronen Basri, and Yuval Kluger.  Spectralnet: Spectral clustering using deep neural networks.  In Proceedings of the 6th International Conference on Learning Representations, 2018.
  * [25] Jianbo Shi and Jitendra Malik.  Motion segmentation and tracking using normalized cuts.  In Sixth international conference on computer vision (IEEE Cat. No. 98CH36271), pages 1154–1160. IEEE, 1998.
  * [26] Jianbo Shi and Jitendra Malik.  Normalized cuts and image segmentation.  IEEE Transactions on pattern analysis and machine intelligence, 22(8):888–905, 2000.
  * [27] Suman Tatiraju and Avi Mehta.  Image segmentation using k-means clustering, em and normalized cuts.  Department of EECS, 1:1–7, 2008.
  * [28] Laurens Van der Maaten and Geoffrey Hinton.  Visualizing data using t-sne.  Journal of machine learning research, 9(11), 2008.
  * [29] E Weinan, Jiequn Han, and Arnulf Jentzen.  Algorithms for solving high dimensional pdes: from nonlinear monte carlo to machine learning.  Nonlinearity, 35(1):278, 2021.
  * [30] Christopher Williams and Matthias Seeger.  Using the nyström method to speed up kernel machines.  Advances in neural information processing systems, 13, 2000.
  * [31] Han Xiao, Kashif Rasul, and Roland Vollgraf.  Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms.  arXiv preprint arXiv:1708.07747, 2017.
  * [32] Lihi Zelnik-Manor and Pietro Perona.  Self-tuning spectral clustering.  Advances in neural information processing systems, 17, 2004.