# Geometric measure of quantum discord and the geometry of a class of two-
qubit states

Wei Song  wsong1@mail.ustc.edu.cn(Corresponding~Author) School of Electronic
and Information Engineering, Hefei Normal University, Hefei 230061, China
Long-Bao Yu  School of Electronic and Information Engineering, Hefei Normal
University, Hefei 230061, China  Ping Dong  School of Electronic and
Information Engineering, Hefei Normal University, Hefei 230061, China  Da-
Chuang Li  School of Electronic and Information Engineering, Hefei Normal
University, Hefei 230061, China  Hefei National Laboratory for Physical
Sciences at the Microscale and Department of Modern Physics, University of
Science and Technology of China, Hefei 230026, China  Ming Yang  School of
Physics and Material Science, Anhui University, Hefei 230039, China  Zhuo-
Liang Cao  School of Electronic and Information Engineering, Hefei Normal
University, Hefei 230061, China

###### Abstract

We investigate the geometric picture of the level surfaces of quantum
entanglement and geometric measure of quantum discord(GMQD) of a class of
X-states, respectively. This pictorial approach provides us a direct
understanding of the structure of entanglement and GMQD. The dynamic evolution
of GMQD under two typical kinds of quantum decoherence channels is also
investigated. It is shown that there exists a class of initial states for
which the GMQD is not destroyed by decoherence in a finite time interval.
Furthermore, we establish a factorization law between the initial and final
GMQD, which allows us to infer the evolution of entanglement under the
influences of the environment.

###### pacs:

03.67.Mn, 03.65.Ud, 03.65.Yz

##  I Introduction

Entanglement is regarded as an ingredient resource for performing almost all
quantum information processing tasksNeilsen:2000 . The situation started to
change until a computational model was presented named deterministic quantum
computation with one qubit(DQC1)Datta:2008 . Quantum discord was considered to
be the figure of merit for this model of quantum computation. Ever since,
quantum discord has attracted much attentionOllivier:2001 ; Henderson:2001 ;
Luo:2008 ; Modi:2010 ; Dakic:2010 ; Chen:2011 ; Shi:2011a ; Shi:2011b ;
Cornelio:2011 ; Ferraro:2010 ; Streltsov:2011 ; Piani:2011 ; Al-Qasimi:2011 ;
Bennett:2011 ; Galve:2011 ; Luo:2010 ; Hassan:2010 ; Yu:2011 ; Bylicka:2010 ;
Huang:2011 ; Fanchini:2011 ; Zhang:2011a ; Zhang:2011b ; Shabani:2009 ;
Bradler:2010 . Quantum discord is a measure of nonclassical correlations
between two subsystems of a quantum system. It quantifies how much a system
can be disturbed when people observe it to gather information. Such quantum
correlations may be present in separable states and have a non vanishing value
for almost all quantum statesFerraro:2010 . On the other hand, the quantum
discord can be used to indicate the quantum phase transitions better than
entanglement in certain physical systems at a finite temperature
Dillenschneider:2008 ; Werlang:2010 . In particular, two operational
interpretations of quantum discord have been proposed, one in thermodynamics
Zurek:2003  and the other from the information theoretic perspective through
the state merging protocol Cavalcanti:2011 ; Madhok:2011 . These results
establish the status of quantum discord as another important resource for
quantum informational processing tasks besides entanglement.

Originally, the first definition of quantum discord was given by Ollivier and
Zurek Ollivier:2001 and, independently, by Henderson and Vedral Henderson:2001
. The quantum discord of a composite system AB is defined by
$D_{A}\equiv\mathop{\min}\limits_{\left\\{{E_{i}^{A}}\right\\}}\sum\limits_{i}{p_{i}}S\left({\rho_{B|i}}\right)+S\left({\rho_{A}}\right)-S\left({\rho_{AB}}\right)$,
where $S\left({\rho_{AB}}\right)=Tr\left({\rho_{AB}\log_{2}\rho_{AB}}\right)$
is the von Neumann entropy and the minimum is taken over all positive operator
valued measures(POVMs) $\left\\{{E_{i}^{A}}\right\\}$ on the subsystem $A$
with $p_{i}=Tr\left({E_{i}^{A}\rho_{AB}}\right)$ being the probability of the
i-th outcome and
$\rho_{B|i}={{Tr_{A}\left({E_{i}^{A}\rho_{AB}}\right)}\mathord{\left/{\vphantom{{Tr_{A}\left({E_{i}^{A}\rho_{AB}}\right)}{p_{i}}}}\right.\kern-1.2pt}{p_{i}}}$
being the conditional state of subsystem $B$. In a more restrict sense, the
minimum is often taken over the von Neumann measurements. However, it is
notoriously difficult to compute because of the minimization taken over all
possible POVM, or von Neumann measurements. At present, there are only a few
analytical results including the Bell-diagonal states Luo:2008 , rank-2 states
Shi:2011b ; Cen:2011 and Gaussian states Giorda:2010 ; Adesso:2010 . In
addition, a simple algorithm to evaluate the quantum discord for two-qubit
X-states is proposed by Ali _et al._ Ali:2010  with minimization taken over
only a few cases. Unfortunately, their algorithm is valid only for a family of
X-statesChen:2011 ; Lu:2011a . Recently Shi _et al._ Shi:2011c  present an
efficient method to solve this problem. For the general two-qubit states, the
evaluation of quantum discord remains a nontrivial task and only some lower
and upper bounds are available Yu:2011c . In order to avoid the difficulties
in minimization procedures a geometric view of quantum discord was introduced.
Generally, there are two versions of geometric measure of quantum
discord(GMQD). In the first version the concept of relative entropy is used as
a distance measure of correlations Modi:2010 . The second version is defined
by the Hilbert-Schmidt norm measure Dakic:2010 . The relative-entropy-based
discords have the drawback that their analytical expressions are known only
for certain limited classes of states. Below we only consider the second
version of GMQD. Especially, Dakic _et al_ Dakic:2012  show that the GMQD is
related to the fidelity of remote state preparation which provides an
operational meaning to GMQD. Formerly, this geometric measure of quantum
discord is defined by
$D_{A}^{g}=\mathop{\min}\limits_{\chi\in\Omega_{0}}\left\|{\rho-\chi}\right\|^{2}$,
where $\Omega_{0}$ denotes the set of zero-discord states and
$\left\|{X-Y}\right\|^{2}=Tr\left({X-Y}\right)^{2}$ is the square norm in the
Hilbert-Schmidt space. The subscript $A$ denotes that the measurement is taken
on the system $A$. An arbitrary two-qubit state can be written in Bloch
representation:

$\displaystyle\rho=\frac{1}{4}\left[{I\otimes
I+\sum\limits_{i}^{3}{\left({x_{i}\sigma_{i}\otimes
I+y_{i}I\otimes\sigma_{i}}\right)+\sum\limits_{i,j=1}^{3}{R_{ij}\sigma_{i}\otimes\sigma_{j}}}}\right]$
(1)

where $x_{i}=Tr\rho\left({\sigma_{i}\otimes
I}\right),y_{i}=Tr\rho\left({I\otimes\sigma_{i}}\right)$ are components of the
local Bloch vectors, $\sigma_{i},i\in\left\\{{1,2,3}\right\\}$ are the three
Pauli matrices, and $R_{ij}=Tr\rho\left({\sigma_{i}\otimes\sigma_{j}}\right)$
are components of the correlation tensor. For the two-qubit case, the zero-
discord state is of the form
$\chi=p_{1}\left|{\psi_{1}}\right\rangle\left\langle{\psi_{1}}\right|\otimes\rho_{1}+p_{2}\left|{\psi_{2}}\right\rangle\left\langle{\psi_{2}}\right|\otimes\rho_{2}$,
where
$\left\\{{\left|{\psi_{1}}\right\rangle,\left|{\psi_{2}}\right\rangle}\right\\}$
is a single-qubit orthonormal basis. Then an analytic expression of the GMQD
is given by Dakic:2010 :

$\displaystyle
D_{A}^{g}\left(\rho\right)=\frac{1}{4}\left({\left\|x\right\|^{2}+\left\|R\right\|^{2}-k_{\max}}\right)$
(2)

where $x=\left({x_{1},x_{2},x_{3}}\right)^{T}$ and $k_{\max}$ is the largest
eigenvalue of matrix $K=xx^{T}+RR^{T}$.

Figure 1: (Color online). The geometry of the set of valid states with
different $r$ and $s$, repectively.
(a)$r$=$s$=0.3,(b)$r$=$s$=0.5,(c)$r$=0.4,$s$=0.1

In this paper we shall investigate the level surfaces of entanglement and GMQD
for a class of two-qubit states using the geometric picture presented in
Lang:2010 . It is well known that the set of Bell-diagonal states for two
qubits can be depicted as a tetrahedron in three dimensions in Bloch
representation Horodecki:2009 . Analogous to entanglement, Lang and Caves have
depicted the level surfaces of quantum discord for Bell-diagonal states. More
recently, Girolami and Adesso Girolami:2011  and independently Batle _et al._
Batle:2011  provided numerical evidence, from which one can infer that discord
and GMQD may be different. It is thus worth investigating the GMQD from the
geometric picture. In this sense, our research provides a direct understanding
of the structure of GMQD. We consider a class of X-states that the Bloch
vectors are $z$ directional, which include Bell-diagonal states as a special
case. We show that the level surface of GMQD is very different from the
quantum discord. On the other hand, the dynamics of quantum discord has
attracted much attention due to the inevitable interaction with environment.
The dynamic behavior of GMQD is also investigated under two typical kinds of
decoherence channels. We find a class of states for which the GMQD is not
destroyed by decoherence in a finite time interval. Interestingly, we also
obtain a factorization law for GMQD which allows us to infer the evolution of
entanglement under the influences of the environment, _e.g._ the phase damping
channel(PDC), and the depolarizing channel(DPC).

The paper is organized as follows. In Sec.II, we present the geometric picture
of the level surfaces of quantum entanglement and GMQD of a class of X-states
with $z$ directional Bloch vectors, respectively. It is shown that the surface
of constant GMQD varies with the local Bloch vectors. In Sec.III, we
investigate the dynamic evolution of GMQD under quantum decoherence channels,
and obtain analytic results for two typical kinds of quantum decoherence
channels. A summary is given in Sec.IV.

##  II geometrical picture of entanglement and GMQD

For analytical simplicity, we consider the following two-qubit X states:

$\displaystyle\rho=\frac{1}{4}\left[{I\otimes I+\textbf{r}\cdot\sigma\otimes
I+I\otimes\textbf{s}\cdot\sigma+\sum\limits_{i=1}^{3}{c_{i}\sigma_{i}\otimes\sigma_{i}}}\right]$
(3)

where we choose the Bloch vectors as $z$ directional with
$\textbf{r}=\left({0,0,r}\right)$,$\textbf{s}=\left({0,0,s}\right)$. The GMQD
can be calculated explicitly for this state, thus allowing us to get analytic
results. If $\textbf{r}=\textbf{s}=0$, $\rho$ is reduced to the two-qubit
Bell-diagonal states. Horodecki have shown that Bell-diagonal states belongs
to a tetrahedron with vertices $(1,-1,1),(-1,1,1),(1,1,-1)$,and $(-1,-1,-1)$
in the Bloch representation. From the positivity of the eigenvalues of $\rho$
in Eq.(3), we have

$\displaystyle
0\leqslant\frac{{\text{1}}}{{\text{4}}}\left({1-\sqrt{r^{2}-2rs+s^{2}+c_{1}^{2}+2c_{1}c_{2}+c_{2}^{2}}-c_{3}}\right)\leqslant
1,$ $\displaystyle
0\leqslant\frac{{\text{1}}}{{\text{4}}}\left({1+\sqrt{r^{2}-2rs+s^{2}+c_{1}^{2}+2c_{1}c_{2}+c_{2}^{2}}-c_{3}}\right)\leqslant
1,$ $\displaystyle
0\leqslant\frac{{\text{1}}}{{\text{4}}}\left({1-\sqrt{r^{2}+2rs+s^{2}+c_{1}^{2}-2c_{1}c_{2}+c_{2}^{2}}+c_{3}}\right)\leqslant
1,$ $\displaystyle
0\leqslant\frac{{\text{1}}}{{\text{4}}}\left({1+\sqrt{r^{2}+2rs+s^{2}+c_{1}^{2}-2c_{1}c_{2}+c_{2}^{2}}+c_{3}}\right)\leqslant
1$

For fixed parameters $r$ and $s$, the above inequalities become a three-
parameter set, whose geometry can be depicted in the three dimensional
correlation state space. In Fig.1 we plot the physical region with different
$r$ and $s$, respectively. Fig.1 shows that physical regions of the state
$\rho$ shrink with larger $r$ and $s$. We plot in Fig.2 the level surfaces of
constant concurrence with fixed $r$ and $s$ for three cases. Here, we choose
concurrence to measure entanglement which is defined as
$C=\max\left\\{{0,\lambda_{1}-\lambda_{2}-\lambda_{3}-\lambda_{4}}\right\\}$,
where the $\lambda_{i}$ are, in decreasing order, the square roots of the
eigenvalues of the matrix
$\rho\sigma_{y}\otimes\sigma_{y}\rho^{*}\sigma_{y}\otimes\sigma_{y}$ where
$\rho^{*}$ is the complex conjugate of $\rho$. As shown in Fig.2, the level
surfaces of constant concurrence for the state $\rho$ defined in Eq.(3)
consist of four discrete pieces, and the areas decrease when the concurrence
increases.An extremal case is the four vertices $(1,-1,1),(-1,1,1),(1,1,-1)$,
and $(-1,-1,-1)$ of the tetrahedron corresponding to the four Bell states with
maximal concurrence. Finally, we investigate the GMQD from the geometric
picture. For the state $\rho$, the GMQD can be calculated in the method
presented in Ref. Lu:2010c  By introducing a matric $\mathcal{R}$ defined by

$\mathcal{R}=\left({{\begin{array}[]{*{20}c}1&{y^{T}\hfill}\\\ x&R\hfill\\\
\end{array}}}\right)$ (5)

and $3\times 4$ matric $\mathcal{{R^{\prime}}}$ through deleting the first row
of $\mathcal{R}$, then the GMQD is given by

$\displaystyle
D_{A}^{g}\left(\rho\right)=\frac{1}{4}\left[{\left({\sum\limits_{k}{\lambda_{{}_{k}}^{2}}}\right)-\mathop{\max}\limits_{k}\lambda_{{}_{k}}^{2}}\right]$
(6)

where ${\lambda_{k}}$ is the singular values of $\mathcal{R^{\prime}}$. For
the two-qubit state $\rho$ in Eq.(3), we obtain

$\displaystyle
D_{A}^{g}\left(\rho\right)=\frac{1}{4}\left({c_{1}^{2}+c_{2}^{2}+c_{3}^{2}+r^{2}-{\text{Max}}\left({c_{1}^{2},c_{2}^{2},c_{3}^{2}+r^{2}}\right)}\right)$
(7)

The geometric picture is depicted in terms of the constant GMQD in Fig.3. From
these plots one can see that the shape of the constant GMQD is quite different
from quantum discord. It also shows different shapes for different local Bloch
vectors. The constant surfaces are cut off by the physical region of state
$\rho$. For small discord the surface is continuous, and it becomes discrete
pieces for larger discord. At the four vertices
$(1,-1,1),(-1,1,1),(1,1,-1)$,and $(-1,-1,-1)$ of the tetrahedron the GMQD
reaches its maximal value. Furthermore, one can see that GMQD is neither
concave nor convex as shown in Fig.3.

Figure 2: (Color online). Surfaces of constant concurrence. (a)$r$=$s$
=0.3,$C(\rho)$=0.03,(b)$r$=$s$=0.5,$C(\rho)$=0.35,(c)$r$=0.4,$s$=0.1,$C(\rho)$=0.03
Figure 3: (Color online). Surfaces of constant GMQD. (a)$r$=$s$
=0.3,$D(\rho)$=0.03,(b)$r$=$s$=0.5,$D(\rho)$=0.35,(c)$r$=0.4,$s$=0.1,$D(\rho)$=0.08

##  III Dynamics of GMQD under local decoherence channels

In this section we consider the state affected by the action of two
independent channels and calculate the GMQD analytically. The dynamics of
quantum discord has been investigated in both Markovian and non-Markovian
environments and has been demonstrated experimentally Werlang:2009b ;
Maziero:2009 ; Wang:2010 ; Mazzola:2010 ; Li:2011 ; Fanchini:2010 ;
Auccaise:2011 ; Xu:2010a ; Xu:2010b . It has been shown that the behaviors of
quantum discord and GMQD may be different. It is thus desirable to consider
the evolution of GMQD under different decoherence channels. Here, we consider
two typical kinds of decoherence channels: the phase damping channel(PDC), and
the depolarizing channel(DPC). To calculate the dynamics of GMQD, we turn to
the Heisenberg picture to describe the quantum channels. In order to obtain
the analytic expressions of GMQD of the state subject to local decoherence
channels, we need to calculate the expection matrix $\mathcal{R}$. In the
Heisenberg picture Lu:2010c ; Wang:2010d , the expectation matrix
$\mathcal{R}$ is given by

$\displaystyle\mathcal{R}_{ij}=\left({M_{A}\mathcal{R}_{0}M_{B}^{T}}\right)_{ij}$
(8)

where $\mathcal{R}_{0}=Tr\left({\sigma_{i}\otimes\sigma_{j}\rho_{0}}\right)$,
$i\in\left\\{{0,1,2,3}\right\\}$, $\rho_{\text{0}}$ is the initial state, and
$M_{A\left(B\right)}$ is the transmission matrix of each local channel. For
simplicity, we choose the local channels to be identical. In this case, the
transmission matrices can be written as

$M_{PDC}=\left({{\begin{array}[]{*{20}c}1&0&0&0\hfill\\\ 0&1-p&0&0\hfill\\\
0&0&1-p&0\hfill\\\ 0&0&0&1\hfill\\\ \end{array}}}\right),$ (9)

$M_{DPC}=\left({{\begin{array}[]{*{20}c}1&0&0&0\hfill\\\ 0&1-p&0&0\hfill\\\
0&0&1-p&0\hfill\\\ 0&0&0&1-p\hfill\\\ \end{array}}}\right),$ (10)

For state (3),
$\mathcal{R}_{0}=\left\\{{\left\\{{1,0,0,s}\right\\},\left\\{{0,c_{1},0,0}\right\\},\left\\{{0,0,c_{2},0}\right\\}}\right.$
$\left.{\left\\{{r,0,0,c_{3}}\right\\}}\right\\}$. According to the above
formula, we have

$\displaystyle
D_{PDC}^{g}=\frac{1}{4}\left[{\left({1-p}\right)^{4}c_{1}^{2}+\left({1-p}\right)^{4}c_{2}^{2}+r^{2}+c_{3}^{2}}\right.$
$\displaystyle\left.{-\max\left\\{{\left({1-p}\right)^{4}c_{1}^{2},\left({1-p}\right)^{4}c_{2}^{2},r^{2}+c_{3}^{2}}\right\\}}\right]$
(11)

$\displaystyle
D_{DPC}^{g}=\frac{1}{4}\left[{\left({1-p}\right)}\right.^{4}c_{1}^{2}+\left({1-p}\right)^{4}c_{2}^{2}$
$\displaystyle+\left({1-p}\right)^{2}r^{2}+\left({1-p}\right)^{4}c_{3}^{2}$
$\displaystyle-\max\left\\{{\left({1-p}\right)^{4}}\right.c_{1}^{2},\left({1-p}\right)^{4}c_{2}^{2}$
$\displaystyle\left.{\left.{\left({1-p}\right)^{2}r^{2}+\left({1-p}\right)^{4}c_{3}^{2}}\right\\}}\right]$
(12)

For some Bell-diagonal states, it has been shown that quantum discord is not
destroyed by decoherence for some finite time interval Mazzola:2010 . A
natural question arises: Whether such a phenomena exists for GMQD? We consider
the state in Eq.(3) undergoes two identical PDCs. In this case,
$p=1-\exp(-\gamma t)$, where $\gamma$ is the phase damping rate. For
$c_{1}=0,c_{2}^{2}>r^{2}+c_{3}^{2}$, suppose ${p_{1}}$ satisfies the equation
$\left({1-p_{1}}\right)^{4}c_{2}^{2}=r^{2}+c_{3}^{2}$. If ${p<p_{1}}$, from
Eq.(11) we have $D_{PDC}^{g}=\frac{1}{4}\left({r^{2}+c_{3}^{2}}\right)$ which
is independent of time. Therefore, we conclude that for a finite time interval
the GMQD does not decay despite the presence of local phase damping noises. It
is directly seen that such a phenomena also exists for the case
$c_{2}=0,c_{1}^{2}>r^{2}+c_{3}^{2}$. These results show that GMQD remains
intact under the action of some special kinds of quantum channels. It should
be noted that similar phenomenon have also been noticed by Karpat _et al_
Karpat:2011  for the qubit-qutrit systems. In the geometric picture, this
behavior corresponds to the state evolving along a straight line in the
constant GMQD tube until it enconters another constant GMQD tube.

Hitherto, we have only considered the time evolution of GMQD under PDC or DPC
described by Eq.(11) and Eq.(12). Next, we want to derive a more general
result on GMQD relating the initial and final state of GMQD. Inspired by the
famous factorization law for entanglement decay derived by Konrad _et al._
Konrad:2008 , we find an analogous factorization law between the initial and
final GMQD of the class of two-qubit states defined in Eq.(3) subject to two
different local decoherence channels. We state our result as the following
theorem.

Theorem. Consider the class of X-states defined in Eq.(3), with each qubit
being subject to the local decoherence channels, _i.e._ the phase damping
channel(PDC) or the depolarizing channel(DPC). The time evolution of GMQD
satisfies

$\displaystyle
D^{g}\left[{\left({\$_{1}\otimes\$_{2}}\right)\rho(t)}\right]\geqslant
2D^{g}\left[{\left({\$_{1}\otimes\$_{2}}\right)\left|{\beta_{i}}\right\rangle\left\langle{\beta_{i}}\right|}\right]D^{g}\left[{\rho}(0)\right].$
(13)

where the local decoherence channels are represented by ${\$_{1}}$ and
${\$_{2}}$, $\rho_{0}$ is the initial state and
${\left|{\beta_{i}}\right\rangle},i\in\left\\{{1,2,3,4}\right\\}$ denotes one
of the four Bell states.

Proof. First we consider the state $\rho(0)$ is effected by the action of two
identical local PDCs, the time evolution of GMQD is given by Eq.(11). For
convenience we divide the proof into three cases.

Case 1. $r^{2}+c_{3}^{2}\geqslant\left\\{{c_{1}^{2},c_{2}^{2}}\right\\}$. In
this case, it is easy to show that the inequality becomes equality.

Case 2. $c_{1}^{2}\geqslant c_{2}^{2}\geqslant r^{2}+c_{3}^{2}$. First, using
Eq.(7) we have
$D^{g}\left({\rho(0)}\right)=\frac{1}{4}\left({c_{2}^{2}+r^{2}+c_{3}^{2}}\right)$.
Suppose ${p_{0}}$ satisfies the equation
$\left({1-p_{0}}\right)^{4}c_{1}^{2}=r^{2}+c_{3}^{2}$. If $p\leqslant p_{0}$,
the GMQD of the state $\rho$ is given by

$\displaystyle D_{{}^{PDC}}^{g}\left(\rho(0)\right)$ $\displaystyle=$
$\displaystyle\frac{1}{4}\left[{\left({1-p}\right)^{4}c_{2}^{2}+r^{2}+c_{3}^{2}}\right]$
$\displaystyle\geqslant$
$\displaystyle\frac{1}{4}\left[{\left({1-p}\right)^{4}c_{2}^{2}+\left({1-p}\right)^{4}\left({r^{2}+c_{3}^{2}}\right)}\right]$
$\displaystyle=$
$\displaystyle\left({1-p}\right)^{4}D^{g}\left({\rho(0)}\right)$
$\displaystyle=$ $\displaystyle
2D^{g}\left[{\left({\$_{PDC}\otimes\$_{PDC}}\right)\left|{\beta_{i}}\right\rangle\left\langle{\beta_{i}}\right|}\right]D^{g}\left({\rho(0)}\right)$

If $p>p_{0}$, then

$\displaystyle D_{{}^{PDC}}^{g}\left(\rho(t)\right)$ $\displaystyle=$
$\displaystyle\frac{1}{4}\left[{\left({1-p}\right)^{4}c_{1}^{2}+\left({1-p}\right)^{4}c_{2}^{2}}\right]$
$\displaystyle\geqslant$
$\displaystyle\frac{1}{4}\left[{\left({1-p}\right)^{4}c_{2}^{2}+\left({1-p}\right)^{4}\left({r^{2}+c_{3}^{2}}\right)}\right]$
$\displaystyle=$
$\displaystyle\left({1-p}\right)^{4}D^{g}\left({\rho(0)}\right)$
$\displaystyle=$ $\displaystyle
2D^{g}\left[{\left({\$_{PDC}\otimes\$_{PDC}}\right)\left|{\beta_{i}}\right\rangle\left\langle{\beta_{i}}\right|}\right]D^{g}\left({\rho(0)}\right)$

Case 3. $c_{1}^{2}\geqslant r^{2}+c_{3}^{2}\geqslant c_{2}^{2}$. For
$p\leqslant p_{0}$ or $p>p_{0}$, the proof is similar to case 2.

By simply exchanging $c_{1}$ and $c_{2}$ we can verify the above relations for
the cases $c_{2}^{2}\geqslant c_{1}^{2}\geqslant r^{2}+c_{3}^{2}$ and
$c_{2}^{2}\geqslant r^{2}+c_{3}^{2}\geqslant c_{1}^{2}$. For the case of two
identical local DPCs, one can prove the above results in the same way as for
PDCs. In the following, we consider the first qubit is subject to the PDC and
the second qubit is subject to the DPC. The expectation matrix $\mathcal{R}$
can be calculated according to the formula
$\mathcal{R}=M_{A}\mathcal{R}_{0}M_{B}^{T}$, where $M_{A\left(B\right)}$ is
the transformation matrix of PDC(DPC). Thus, the GMQD is given by

$\displaystyle
D^{g}\left({\rho\left(t\right)}\right)=\frac{1}{4}\left[{\left({1-p}\right)}\right.^{4}c_{1}^{2}+\left({1-p}\right)^{4}c_{2}^{2}+r^{2}+\left({1-p}\right)^{2}c_{3}^{2}$
$\displaystyle\left.{{-\text{
max}}\left\\{{\left({1-p}\right)^{4}c_{1}^{2},\left({1-p}\right)^{4}c_{2}^{2},r^{2}+\left({1-p}\right)^{2}c_{3}^{2}}\right\\}}\right]$

where we have assumed that the parameter $p$ is the same in the two
decoherence channels. Then it suffices to consider three separate cases.

Case 1. $r^{2}+c_{3}^{2}\geqslant\left\\{{c_{1}^{2},c_{2}^{2}}\right\\}$. Then

$\displaystyle
D^{g}\left({\rho\left(t\right)}\right)=\frac{1}{4}\left[{\left({1-p}\right)^{4}c_{1}^{2}+\left({1-p}\right)^{4}c_{2}^{2}}\right]$
$\displaystyle=2D^{g}\left[({\$_{PDC}\otimes\$_{DPC})\left({\left|{\beta_{i}}\right\rangle\left\langle{\beta_{i}}\right|}\right)}\right]D^{g}\left({\rho\left(0\right)}\right)$
(17)

Case 2. ${c_{1}^{2}\geqslant c_{2}^{2}\geqslant r^{2}+c_{3}^{2}}$. Suppose
$p^{\prime}_{0}$ satisfies
$\left({1-p^{\prime}_{0}}\right)^{4}c_{1}^{2}=r^{2}+\left({1-p^{\prime}_{0}}\right)^{2}c_{3}^{2}$.
If $p\leqslant p^{\prime}_{0}$, we have

$\displaystyle
D^{g}\left({\rho\left(t\right)}\right)=\frac{1}{4}\left[{\left({1-p}\right)^{4}c_{2}^{2}+r^{2}+\left({1-p}\right)^{2}c_{3}^{2}}\right]$
$\displaystyle\geqslant\frac{1}{4}\left[{\left({1-p}\right)^{4}c_{2}^{2}+\left({1-p}\right)^{4}r^{2}+\left({1-p}\right)^{4}c_{3}^{2}}\right]$
$\displaystyle=2D^{g}\left[({\$_{PDC}\otimes\$_{DPC})\left({\left|{\beta_{i}}\right\rangle\left\langle{\beta_{i}}\right|}\right)}\right]D^{g}\left({\rho\left(0\right)}\right)$
(18)

If $p>p^{\prime}_{0}$, we obtain

$\displaystyle
D^{g}\left({\rho\left(t\right)}\right)=\frac{1}{4}\left[{\left({1-p}\right)^{4}c_{1}^{2}+\left({1-p}\right)^{4}c_{2}^{2}}\right]$
$\displaystyle\geqslant\frac{1}{4}\left({1-p}\right)^{4}\left[{c_{2}^{2}+r^{2}+c_{3}^{2}}\right]$
$\displaystyle=2D^{g}\left[({\$_{PDC}\otimes\$_{DPC})\left({\left|{\beta_{i}}\right\rangle\left\langle{\beta_{i}}\right|}\right)}\right]D^{g}\left({\rho\left(0\right)}\right)$
(19)

Case 3. ${c_{1}^{2}\geqslant r^{2}+c_{3}^{2}\geqslant c_{2}^{2}}$. In this
case, the proof is similar to case 2.

One can also directly verify that the above relation holds for the other
cases.$\hfill\blacksquare$

The theorem above provides us a method to compute the lower bound of the time
evolution of a class of X-states under two typical kinds of decoherence
channels, without resorting to the time evolution of the underlying quantum
state itself. This inequality also holds for the one-sided PDC or DPC, which
is summarized as the following Corollary:

Corollary 1. For the class of X-states defined in Eq.(3), with one qubit being
subject to PDC or DPC, we have

$\displaystyle D^{g}\left({\rho\left(t\right)}\right)\geqslant
2D^{g}\left[({\$_{i}\otimes
I)\left({\left|{\beta_{i}}\right\rangle\left\langle{\beta_{i}}\right|}\right)}\right]D^{g}\left({\rho\left(0\right)}\right)$
(20)

Moreover, for $r=s=0$, _i.e._ Bell diagonal states, using Eq.(12), one can
directly calculate the above inequality becomes equality which we summarize as
follows:

Corollary 2. For arbitrary Bell-diagonal states subject to two DPCs, the
evolution of GMQD is given by

$\displaystyle
D_{DPC}^{g}\left(\rho(t)\right)=2D^{g}\left[{\left({\$_{DPC}\otimes\$_{DPC}}\right)\left|{\beta_{i}}\right\rangle\left\langle{\beta_{i}}\right|}\right]D^{g}\left(\rho(0)\right)$

where the two DPCs may be different. By far we have considered the time
evolution of GMQD in the presence of two typical kinds of local decoherence
noise. Another important decoherence noise is the amplitude damping
channel(ADC). Evidence can show that the above relation also holds for two
identical ADCs, i.e.

$\displaystyle D^{g}\left({\rho\left(t\right)}\right)\geqslant
2D^{g}\left[({\$_{ADC}\otimes\$_{ADC})\left({\left|{\beta_{i}}\right\rangle\left\langle{\beta_{i}}\right|}\right)}\right]D^{g}\left({\rho\left(0\right)}\right)$

In Fig.4, we plot the evolution of GMQD under two identical ADCs and its lower
bound in Eq.(22) when (a)$c_{1}=0.1,c_{2}=0.1,c_{3}=0.2,r=s=0.3$;
(b)$c_{1}=0.2,c_{2}=0.05,c_{3}=0.3,r=0.4,s=0.1$.

Figure 4: (Color online).Plots of the dynamics of GMQD under two identical
ADCs(blue line) and its lower bound defined in Eq.(22)(red
line).(a)$c_{1}=0.1,c_{2}=0.1,c_{3}=0.2,r=s=0.3$;
(b)$c_{1}=0.2,c_{2}=0.05,c_{3}=0.3,r=0.4,s=0.1$.

##  IV DISCUSSIONS AND CONCLUSIONS

In this work, we investigated the level surfaces of GMQD for a class of two-
qubit X-states from the geometric picture. First, we plot the physical region
for a class of two-qubit X-states with fixed local Bloch vectors. It is shown
that physical regions of the state have different geometry with the Bell-
diagonal states and shrink with larger Bloch vectors. Second, the geometric
picture is depicted in terms of the constant concurrence and GMQD,
respectively. We find that the shape of the surfaces has close relationship
with the value of GMQD and local Bloch vectors. Finally, we also investigate
the dynamics of GMQD under two typical kinds of decoherence channels and
obtain analytic results of the evolution of GMQD. It is shown that there
exists a class of initial states for which the GMQD is not destroyed by
decoherence in a finite time interval. Moreover, a direct factorization
relationship between the initial and final GMQD subject to two typical kinds
of decoherence channels is derived. This factorization law allows us to infer
the evolution of entanglement under the influences of the environment without
resorting to the time evolution of the initial quantum state itself. An open
question is whether this law holds under general local decoherence channels.
Our results imply that further study on the dynamics of GMQD is required.

##  V ACKNOWLEDGMENTS

We are grateful to the referee for valuable suggestions. This work was
supported by the National Natural Science Foundation of China under Grant
No.10905024,No.11005029,No.11104057,No.11204061, the Key Project of Chinese
Ministry of Education under Grant No.211080, and the Key Program of the
Education Department of Anhui Province under Grant No.KJ2011A243,
No.KJ2012A244, No.KJ2012A245, the Anhui Provincial Natural Science Foundation
under Grant No.11040606M16, No.10040606Q51, the Doctoral Startup Foundation of
Hefei Normal University under Grant No.2011rcjj03.

Note added. After completing this manuscript, we became aware of an
interesting related works by Yao Yao _et al_Yao:2011  recently.

## References

  * (1) Neilsen M A, Chuang I L. Quantum Computation and Quantum Information. New York: Cambridge University Press, 2000. 35-45
  * (2) Datta A, Shaji A, Caves C M. Quantum Discord and the Power of One Qubit, Phys. Rev. Lett, 2008, 100: 050502
  * (3) Ollivier H, Zurek W H. Quantum Discord: A Measure of the Quantumness of Correlations, Phys. Rev. Lett, 2001, 88: 017901
  * (4) Henderson L, Vedral V. Classical, quantum and total correlations, J. Phys. A, 2001, 34: 6899
  * (5) Luo S. Using measurement-induced disturbance to characterize correlations as classical or quantum, Phys. Rev. A, 2008, 77: 022301
  * (6) Modi K, Paterek T, Son W, Vedral V, Williamson M. Unified View of Quantum and Classical Correlations, Phys. Rev. Lett, 2010, 104: 080501
  * (7) Dakic B, Vedral V, Brukner C. Necessary and Sufficient Condition for Nonzero Quantum Discord, Phys. Rev. Lett, 2010, 105: 190502
  * (8) Dakic B, Lipp Y O, Ma X, Ringbauer M, Kropatschek S, Barz S, Paterek T, Vedral V, Zeilinger A, Brukner C, Walther P. Quantum Discord as Optimal Resource for Quantum Communication, http://arxiv.org/abs/1203.1629
  * (9) Chen Q, Zhang C, Yu S, Yi X X, Oh C H. Quantum discord of two-qubit X states, Phys. Rev. A, 2011, 84: 042313
  * (10) Shi M, Jiang F, Sun C, Du J. Geometric picture of quantum discord for two-qubit quantum states, New J. Phys, 2011 13: 073016
  * (11) Shi M, Yang W, Jiang F, Du J. Quantum discord of two-qubit rank-2 states, J. Phys. A: Math. Theor, 2011, 44: 415304
  * (12) Cornelio M F, Oliveira M C, Fanchini F F. Entanglement Irreversibility from Quantum Discord and Quantum Deficit, Phys. Rev. Lett, 2011, 107: 020502
  * (13) Ferraro A, Aolita L, Cavalcanti D, Cucchietti F M, Acin A. Almost all quantum states have nonclassical correlations, Phys. Rev. A, 2010, 81: 052318
  * (14) Streltsov A, Kampermann H, Bruss D. Linking Quantum Discord to Entanglement in a Measurement, Phys. Rev. Lett, 2011, 106: 160401
  * (15) Piani M, Gharibian S, Adesso G, Calsamiglia J, Horodecki P, Winter A. All Nonclassical Correlations Can Be Activated into Distillable Entanglement, Phys. Rev. Lett, 2011, 106: 220403
  * (16) Qasimi A A, James D F V. Comparison of the attempts of quantum discord and quantum entanglement to capture quantum correlations, Phys. Rev. A, 2011, 83: 032101
  * (17) Bennett C H, Grudka A, Horodecki M, Horodecki P, Horodecki R. Postulates for measures of genuine multipartite correlations, Phys. Rev. A, 2011, 83: 012312
  * (18) Galve F, Giorgi G L, Zambrini R. Maximally discordant mixed states of two qubits, Phys. Rev. A, 2011, 83: 012102
  * (19) Luo S, Fu S. Geometric measure of quantum discord, Phys. Rev. A, 2010, 82: 034302
  * (20) Hassan A S M, Lari B, Joag P S. Tight lower bound to the geometric measure of quantum discord, Phys. Rev. A, 2012, 85: 024302
  * (21) Yu S, Zhang C, Chen Q, Oh C H. Witnessing the quantum discord of all the unknown states, http://arxiv.org/abs/1102.4710
  * (22) Bylicka B, Chruscinski D. Witnessing quantum discord in $2\times N$ systems, Phys. Rev. A, 2010, 81: 062102
  * (23) Huang J H, Wang L, Zhu S Y. A new criterion for zero quantum discord, New J. Phys, 2011, 13: 063045
  * (24) Fanchini F F, Cornelio M F, Oliveira M C, Caldeira A O. Conservation law for distributed entanglement of formation and quantum discord, Phys. Rev. A, 2011, 84: 012313
  * (25) Zhang C, Yu S, Chen Q, Oh C H. Observable estimation of entanglement of formation and quantum discord for bipartite mixed quantum states, Phys. Rev. A, 2011, 84: 052112
  * (26) Zhang C, Yu S, Chen Q, Oh C H. Detecting the quantum discord of an unknown state by a single observable Phys. Rev. A, 2011, 84: 032122
  * (27) Shabani A, Lidar D A. Vanishing Quantum Discord is Necessary and Sufficient for Completely Positive Maps, Phys. Rev. Lett, 2009, 102: 100402
  * (28) Bradler K, Wilde M M, Vinjanampathy S, Uskov D B. Identifying the quantum correlations in light-harvesting complexes, Phys. Rev. A, 2010, 82: 062310
  * (29) Dillenschneider R. Quantum discord and quantum phase transition in spin chains, Phys. Rev. B, 2008, 78: 224413
  * (30) Werlang T, Trippe C, Ribeiro G A P, Rigolin G. Quantum Correlations in Spin Chains at Finite Temperatures and Quantum Phase Transitions, Phys. Rev. Lett, 2010, 105: 095702
  * (31) Zurek W H. Quantum discord and MaxwellĄŻs demons, Phys. Rev. A, 2003, 67: 012320
  * (32) Cavalcanti D, Aolita L, Boixo S, Modi K, Piani M, Winter A. Operational interpretations of quantum discord, Phys. Rev. A, 2011, 83: 032324
  * (33) Madhok V, Datta A. Interpreting quantum discord through quantum state merging, Phys. Rev. A, 2011, 83: 032323
  * (34) Cen L X, Li X Q, Shao J, Yan Y. Quantifying quantum discord and entanglement of formation via unified purifications, Phys. Rev. A, 2011, 83: 054101
  * (35) Giorda P, Paris M G A. Gaussian Quantum Discord, Phys. Rev. Lett, 2010, 105: 020503
  * (36) Adesso G, Datta A. Quantum versus Classical Correlations in Gaussian States, Phys. Rev. Lett, 2010, 105: 030501
  * (37) Ali M, Rau A R P, Alber G. Quantum discord for two-qubit X states, Phys. Rev. A, 2010, 81: 042105
  * (38) Lu X M, Ma J, Xi Z, Wang X. Optimal measurements to access classical correlations of two-qubit states, Phys. Rev. A, 2011, 83: 012327
  * (39) Shi M, Sun C, Jiang F, Yan X, Du J. On the optimal measurement for quantum discord of two-qubit states, http://arxiv.org/abs/1110.6681
  * (40) Yu S, Zhang C, Chen Q, Oh C H. Tight bounds for the quantum discord, http://arxiv.org/abs/1102.1301
  * (41) Lang M D, Caves C M. Quantum Discord and the Geometry of Bell-Diagonal States , Phys. Rev. Lett, 2010, 105: 150501
  * (42) Horodecki R, Horodecki P, Horodecki M, Horodecki K. Quantum entanglement, Rev. Mod. Phys, 2009, 81: 865-942
  * (43) Girolami D, Adesso G. Quantum discord for general two-qubit states: Analytical progress, Phys. Rev. A, 2011, 83: 052108
  * (44) Batle J, Plastino A, Plastino A R, and Casas M. Properties of a geometric measure for quantum discord, http://arxiv.org/abs/1103.0704
  * (45) Lu X M, Xi Z J, Sun Z, Wang X. Geometric measure of quantum discord under decoherence, Quantum Inf. Comp, 2010, 10: 994-1003
  * (46) Werlang T, Souza S, Fanchini F F, Villas Boas C J. Robustness of quantum discord to sudden death, Phys. Rev. A, 2009, 80: 024103
  * (47) Maziero J, Celeri L C, Serra R M, Vedral V. Classical and quantum correlations under decoherence Phys. Rev. A, 2009, 80: 044102
  * (48) Wang B, Xu Z Y, Chen Z Q, Feng M. Non-Markovian effect on the quantum discord, Phys. Rev. A, 2010, 81: 014101
  * (49) Mazzola L, Piilo J, Maniscalco S. Sudden Transition between Classical and Quantum Decoherence, Phys. Rev. Lett, 2010, 104: 200401
  * (50) Li B, Wang Z X, Fei S M. Quantum discord and geometry for a class of two-qubit states, Phys. Rev. A, 2011, 83: 022321
  * (51) Fanchini F F , Werlang T, Brasil C A, Arruda L G E, Caldeira A O. Non-Markovian dynamics of quantum discord, Phys. Rev. A, 2010, 81: 052107
  * (52) Auccaise R, Celeri L C, Soares-Pinto D O, deAzevedo E R, Maziero J, Souza A M, Bonagamba T J, Sarthour R S , Oliveira I S, Serra R M. Environment-induced sudden transition in quantum discord dynamics , Phys. Rev. Lett, 2011, 107: 140403
  * (53) Xu J S, Xu X Y, Li C F, Zhang C J, Zou X B, Guo G C. Experimental investigation of classical and quantum correlations under decoherence. Nat. Commun, 2010, 1: 7
  * (54) Xu J S, Li C F, Zhang C J, Xu X Y, Zhang Y S, Guo G C. Experimental investigation of the non-Markovian dynamics of classical and quantum correlations, Phys. Rev. A, 2010, 82: 042328
  * (55) Wang X, Miranowicz A, Liu Y X, Sun C P, Nori F. Sudden vanishing of spin squeezing under decoherence, Phys. Rev. A, 2010, 81: 022106
  * (56) Konrad T, Melo F D, Tiersch M, Kasztelan C, Aragao A, Buchleitner A. Evolution equation for quantum entanglement, Nature Physics, 2008, 4: 99-102
  * (57) Karpat G, Gedik Z. Correlation Dynamics of Qubit-Qutrit Systems in a Classical Dephasing Environment, Physics Letters A, 2011, 375: 4166-4171
  * (58) Yao Y, Li H W, Yin Z Q, Han Z F. Geometric interpretation of the geometric discord, Physics Letters A, 2012, 376: 358-364


# Ensembling Graph Predictions for AMR Parsing

Hoang Thanh Lam1, Gabriele Picco1, Yufang Hou1, Young-Suk Lee2,
Lam M. Nguyen2, Dzung T. Phan2, Vanessa López1, Ramon Fernandez Astudillo2
1 IBM Research, Dublin, Ireland
2 IBM Research, Thomas J. Watson Research Center, Yorktown Heights, USA
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

In many machine learning tasks, models are trained to predict structure data
such as graphs. For example, in natural language processing, it is very common
to parse texts into dependency trees or abstract meaning representation (AMR)
graphs. On the other hand, ensemble methods combine predictions from multiple
models to create a new one that is more robust and accurate than individual
predictions. In the literature, there are many ensembling techniques proposed
for classification or regression problems, however, ensemble graph prediction
has not been studied thoroughly. In this work, we formalize this problem as
mining the largest graph that is the most supported by a collection of graph
predictions. As the problem is NP-Hard, we propose an efficient heuristic
algorithm to approximate the optimal solution. To validate our approach, we
carried out experiments in AMR parsing problems. The experimental results
demonstrate that the proposed approach can combine the strength of state-of-
the-art AMR parsers to create new predictions that are more accurate than any
individual models in five standard benchmark datasets.

##  1 Introduction

Ensemble learning is a popular machine learning practice, in which predictions
from multiple models are blended to create a new one that is usually more
robust and accurate. Indeed, ensemble methods like XGBOOST are the winning
solution in many machine learning and data science competitions (Chen and
Guestrin, 2016). A key reason behind the successes of the ensemble methods is
that they can combine the strength of different models to reduce the variance
and bias in the final prediction (Domingos, 2000; Valentini and Dietterich,
2004). Research in ensemble methods mostly focuses on regression or
classification problems (Dong et al., 2020). Recently, in many machine
learning tasks prediction outputs are provided in a form of graphs. For
instance, in Abstract Meaning Representation (AMR) parsing (Banarescu et al.,
2013), the input is a fragment of text and the output is a rooted, labeled,
directed, acyclic graph (DAG). It abstracts away from syntactic
representations, in the sense that sentences with similar meaning should have
the same AMR. Figure 1 shows an AMR graph for the sentence _You told me to
wash the dog_ where nodes are concepts and edges are relations.

AMR parsing is an important problem in natural language processing (NLP)
research and it has a broad application in downstream tasks such as question
answering (Kapanipathi et al., 2020) and common sense reasoning (Lim et al.,
2020). Recent approaches for AMR parsing leverage the advances from pretrained
language models (Bevilacqua et al., 2021) and numerous deep neural network
architectures (Cai and Lam, 2020a; Zhou et al., 2021).

Unlike methods for ensembling numerical or categorical values for regression
or classification problems where the mean value or majority votes are used
respectively, the problem of graph ensemble is more complicated. For instance,
Figure 2 show three graphs $g_{1},g_{2},g_{3}$ with different structures,
having varied number of edges and vertices with different labels. In this
work, we formulate the ensemble graph prediction as a graph mining problem
where we look for the largest common structure among the graph predictions. In
general, finding the largest common subgraph is a well-known computationally
intractable problem in graph theory. However, for AMR parsing problems where
the AMR graphs have labels and a simple tree-alike structure, we propose an
efficient heuristic algorithm (_Graphene_) to approximate the solution of the
given problem well.

Figure 1:  An example AMR graph for the sentence _You told me to wash the
dog_.

To validate our approach, we collect the predictions from four state-of-the-
art AMR parsers and create new predictions using the proposed graph ensemble
algorithm. The chosen AMR parsers are the recent state-of-the-art AMR parsers
including a seq2seq-based method using BART (Bevilacqua et al., 2021), a
transition-based approach proposed in (Zhou et al., 2021) and a graph-based
approach proposed in (Cai and Lam, 2020a). In addition to those models, we
also trained a new seq2seq model based on T5 (Raffel et al., 2020) to leverage
the strength of this pretrained language model.

The experimental results show that in five standard benchmark datasets, our
proposed ensemble approach outperforms the previous state-of-the-art models
and achieves new state-of-the-art results in all datasets. For example, our
approach achieves new state-of-the-art results with 1.7, 1.5, and 1.3 points
better than prior arts in the BIO (under out-of-distribution evaluation), AMR
2.0, and AMR 3.0 datasets respectively. This result demonstrates the strength
of our ensemble method in leveraging the model diversity to achieve better
performance. An interesting property of our solution is that it is model-
agnostic, therefore it can be used to make an ensemble of existing model
predictions without the requirement to have an access to model training.
Source code is open-sourced111https://github.com/IBM/graph_ensemble_learning.

Our paper is organized as follows: Section 2 discusses a formal problem
definition and a study on the computational intractability of the formulated
problem. The graph ensemble algorithm is described in Section 3. Experimental
results are reported in Section 4 while Section 5 discusses related works. The
conclusion and future work are discussed in Section 6.

##  2 Problem formulation

Denote $g=(E,V)$ as a graph with the set of edges $E$ and the set of vertices
$V$. Each vertex $v\in V$ and edge $e\in E$ is associated with a label denoted
as $l(v)$ and $l(e)$ respectively, where $l(.)$ is a labelling function. Given
two graphs $g_{1}=(E_{1},V_{1})$ and $g_{2}=(E_{2},V_{2})$, a _vertex
matching_ $\phi$ is a bijective function that maps a vertex $v\in V_{1}$ to a
vertex $\phi(v)\in V_{2}$.

######  Example 1.

In Figure 2, between $g_{1}$ and $g_{2}$ there are many possible vertex
matches, where $\phi(g_{1},g_{2})=[1\rightarrow 3,2\rightarrow 2,3\rightarrow
1]$ is one of them (which can be read as the first vertex of $g_{1}$ is mapped
to the third vertex of $g_{2}$ and so forth). Notice that not all vertices
$v\in V_{1}$ has a match in $V_{2}$ and vice versa. Indeed, in this example,
the fourth vertex in $g_{2}$ does not have a matched vertex in $g_{1}$.

Figure 2:  A graph ensemble example. Each node and edge of $g$ occurs in at
least two out of three graphs $g_{1},g_{2},g_{3}$. Therefore, $g$ is
$\theta$-supported where $\theta=2$ by the given set of graphs. Graph $g$ is
also the graph with the largest sum of supports among all $\theta$-supported
graphs. The tables show the node and edge support (votes) are updated in each
step of the Graphene algorithm when $g_{1}$ is a pivot graph.

Given two graphs $g_{1}$, $g_{2}$ and a vertex match $\phi(g_{1},g_{2})$,
support of a vertex $v$ with respect to the matching $\phi$, denoted as
$s_{\phi}(v)$, is equal to 1 if $l(v)=l(\phi(v))$ and 0 otherwise. Given an
edge $e=(v_{1},v_{2})$ the support of $e$ with respect to the vertex match
$\phi$, denoted as $s_{\phi}(e)$, is equal to 1 if
$l(e)=l((\phi(v_{1}),\phi(v_{2})))$ and 0 otherwise.

######  Example 2.

In Figure 2, for the vertex match $\phi(g_{1},g_{2})=[1\rightarrow
3,2\rightarrow 2,3\rightarrow 1]$, the first vertex in $g_{1}$ and the third
vertex in $g_{2}$ shares the same label $A$, therefore the support of the
given vertex is equal to 1. On the other hand, the third vertex in $g_{1}$ and
the first vertex in $g_{2}$ does not have the same label so their support is
equal to 0.

Between two graphs, there are many possible vertex matches, the _best vertex
match_ is defined as the one that has the maximal total vertex support and
edge support. In our discussion, when we mention a vertex match we always
refer to the best vertex match.

Denote
$G=\\{g_{1}=(E_{1},V_{1}),g_{2}=(E_{2},V_{2}),\cdots,g_{m}=(E_{m},V_{m})\\}$
as a set of $m$ graphs. Given any graph $g=(E,V)$, for every $g_{i}$ denote
$\phi_{i}(g,g_{i})$ as the best vertex match between $g$ and $g_{i}$. The
total support of a vertex $v\in V$ or an edge $e\in E$ is defined as follows:

  * •

$\operatorname{support}(e)=\sum_{i=1}^{m}s_{\phi_{i}}(e)$

  * •

$\operatorname{support}(v)=\sum_{i=1}^{m}s_{\phi_{i}}(v)$

Given a support threshold $\theta$, a graph $g$ is called $\theta$-supported
by $G$ if for any node $v\in V$ or any edge $e\in E$,
$\operatorname{support}(v)\geq\theta$ and
$\operatorname{support}(e)\geq\theta$.

######  Example 3.

In Figure 2, graph $g$ is $\theta$-supported by $G=\\{g_{1},g_{2},g_{3}\\}$
where $\theta=2$.

Intuitively, an ensemble graph $g$ should have as many common edges and
vertices with all the graph predictions as possible. Therefore, we define the
graph ensemble problem as follows:

######  Problem 1 (Graph ensemble).

Given a support threshold $\theta$ and a collection of graphs $G$, find the
graph $g$ that is $\theta$-supported by $G$ and has the largest sum of vertex
and edge supports.

######  Theorem 1.

Finding the optimal $\theta$-supported graph with the largest total of support
is NP-Hard.

###### Proof.

We prove the NP-Hardness by reduction to the _Maximum Common Edge Subgraph_
(MCES) problem, which is known to be an NP-Complete problem (Bahiense et al.,
2012). Given two graphs $g_{1}$ and $g_{2}$, the MCES problem finds a graph
$g$ that is a common subgraph of $g_{1}$ and $g_{2}$ and the number of edges
in $g$ is the largest. Consider the following instance of the Graph Ensemble
problem with $\theta=2$, and $G=\\{g_{1},g_{2}\\}$ created from the graphs in
the MCES problem. Assume that all vertices and all edges of $g_{1}$ and
$g_{2}$ have the same label $A$.

Since $\theta=2$, a $\theta$-supported graph is also a common subgraph between
$g_{1}$ and $g_{2}$ and vice versa. Denote $g_{s}$ and $g_{e}$ as the common
subgraph between $g_{1}$ and $g_{2}$ with the largest support and the largest
common edge, respectively. We can show that $g_{s}$ has as many edges as
$g_{e}$. In fact, since $g_{s}$ is the largest supported common subgraph there
is no vertex $v\in g_{e}$ such that $v\not\in g_{s}$ because otherwise we can
add $v$ to $g_{s}$ to create a larger supported graph. For any edge
$e=(v_{1},v_{2})\in g_{e}$, since both vertices $v_{1}$ and $v_{2}$ also
appear in $g_{s}$, the edge $e=(v_{1},v_{2})$ must also be part of $g_{s}$
otherwise we can add this edge to $g_{s}$ to create a subgraph with a larger
support. Therefore, $g_{s}$ has as many edges as $g_{e}$, which is also a
solution to the MCES problem. ∎

##  3 Graph ensemble algorithm

In this section, we discuss a heuristic algorithm based on the strategy
_“Please correct me if I am wrong!"_ to solve Problem 1. The main idea is to
improve a pivot graph based on other graphs. Specifically, starting with a
pivot graph $g_{i}$ ($i=1,2,\cdots,m$), we collect the votes from the other
graphs for every existing vertex and existing/non-existing edges to correct
$g_{i}$. We call the proposed algorithm _Graphene_ which stands for Graph
Ensemble algorithm. The key steps of the algorithm are provided in the pseudo-
code in Algorithm 1.

Input: a set of graphs $G=\\{g_{1},g_{2},\cdots,g_{m}\\}$ and the support
threshold $\theta$

Output: an ensemble graph $g^{e}$

Algorithm: Graphene($G,\theta$)

for  _$i\leftarrow 1$ to $m$_ do

$g_{\text{pivot}}\leftarrow g_{i}$

$V\leftarrow$ Initialise($g_{\text{pivot}}$)

for  _$j\leftarrow 1$ to $m$_ do

if  _$j\neq i$_ then

$V\leftarrow V$ $\cup$ getVote($\phi(g_{\text{pivot}},g_{j}$))

end for

$g^{e}_{i}\leftarrow Filter(V,\theta)$

end for

$g^{e}\leftarrow$ the graph with the largest support among
$g^{e}_{1},\cdots,g^{e}_{m}$

Return $g^{e}$

Algorithm 1 Graph ensemble with the Graphene algorithm.

For example, in Figure 2, the algorithm starts with the first graph $g_{1}$
and considers it as a pivot graph $g_{\text{pivot}}$. In the first step, it
creates a table to keep voting statistics $V$ initialized with the vote counts
for every existing vertex and edge in $g_{\text{pivot}}$. To draw additional
votes from the other graphs, it performs the following subsequent steps:

  * •

Call the function $\phi(g_{1},g_{i})$ $(i=2,3,\cdots,m)$ to get the best
bijective mapping $\phi$ between the vertices of two graphs $g_{1}$ and
$g_{i}$ (with a little bit abuse of notation we drop the index $i$ from
$\phi_{i}$ when $g_{i}$ and $g_{\text{pivot}}$ are given in the context). For
instance, the best vertex match between $g_{1}$ and $g_{2}$ is
$\phi=1\rightarrow 3,2\rightarrow 2,3\rightarrow 1$ because that vertex match
has the largest number of common labeled edges and vertices.

  * •

Enumerate the matching vertices and edges to update the voting statistics
accordingly. For instance, since the vertex 3 in $g_{1}$ with label $B$ is
mapped to the vertex 1 in $g_{2}$ with label $C$, a new candidate label $C$ is
added to the table for the given vertex. For the same reason, we add a new
candidate label $Z$ for the edge $(1,2)$. For all the other edges and vertices
where the labels are matched the votes are updated accordingly.

Once the complete voting statistics $V$ is available, the algorithm filters
the candidate labels of edges and vertices using the provided support
threshold $\theta$ by calling the function $Filter(V,\theta)$ to obtain an
ensemble graph $g^{e}_{i}$. For special cases, when disconnected graphs are
not considered as a valid output, we keep all edges of the pivot graph even
its support is below the threshold. On the other hand, for the graph
prediction problem, where a graph is only considered a valid graph if it does
not have multiple edges between two vertices and multiple labels for any
vertex, we remove all candidate labels for vertices and edges except the one
with the highest number of votes.

Assume that the resulting ensemble graph that is created by using $g_{i}$ as
the pivot graph is denoted as $g^{e}_{i}$. The final ensemble graph $g^{e}$ is
chosen among the set of graphs $g^{e}_{1},g^{e}_{2},\cdots,g^{e}_{m}$ as the
one with the largest total support. Recall that $\phi(g_{\text{pivot}},g_{i})$
finds the best vertex match between two graphs. In general, the given task is
computationally intractable. However, for labeled graphs like AMR a heuristic
was proposed (Cai and Knight, 2013) to approximate the best match by a hill-
climbing algorithm. It first starts with the candidate with labels that are
mostly matched. The initial match is modified iteratively to optimize the
total number of matches with a predefined number of iterations (default value
set to 5). This algorithm is very efficient and effective, it was used to
calculate the Smatch score in (Cai and Knight, 2013) so we reuse the same
implementation to approximate $\phi(g_{\text{pivot}},g_{i})$ (report on
average running time can be found in the supplementary materials).

##  4 Experiments

We compare our _Graphene_ algorithm against four previous state-of-the-art
models on different benchmark datasets. Below we describe our experimental
settings.

###  4.1 Experimental settings

####  4.1.1 Model settings

##### SPRING

The SPRING model, presented in (Bevilacqua et al., 2021), tackles Text-to-AMR
and AMR-to-Text as a symmetric transduction task. The authors show that with a
pretrained encoder-decoder model, it is possible to obtain state-of-the-art
performances in both tasks using a simple seq2seq framework by predicting
linearized graphs. In our experiments, we used the pretrained models provided
in (Bevilacqua et al., 2021)222Available for download at
https://github.com/SapienzaNLP/spring. In addition, we trained 3 more models
using different random seeds following the same setup described in (Bevilacqua
et al., 2021). Blink (Li et al., 2020) was used to add wiki tags to the
predicted AMR graphs as a post-processing step.

##### T5

The T5 model, presented in (Raffel et al., 2020), introduces a unified
framework that models a wide range of NLP tasks as a text-to-text problem. We
follow the same idea proposed in (Xu et al., 2020) to train a model to
transfer a text to a linearized AMR graph based on T5-Large. The data is
preprocessed by linearization and removing wiki tags using the script provided
in (amr, ). In addition to the main task, we added a new task that takes as
input a sentence and predicts the concatenation of word senses and arguments
provided in the English Web Treebank dataset (goo, ). The model is trained
with 30 epochs. We use ADAM optimization with a learning rate of 1e-4 and a
mini-batch size of 4. Blink (Li et al., 2020) was used to add wiki tags to the
predicted AMR graphs during post-processing.

##### APT

(Zhou et al., 2021) proposed a transition-based AMR parser333Available under
https://github.com/IBM/ transition-amr-parser. based on Transformer (Vaswani
et al., 2017). It combines hard-attentions over sentences with a target side
action pointer mechanism to decouple source tokens from node representations.
For model training in our experiments, we use the setup described in (Zhou et
al., 2021) and added 70K model-annotated silver data sentences to the training
data, which was created from the 85K sentence set in (Lee et al., 2020) with
self-learning described in the paper.

##### Cai&Lam

The model proposed in (Cai and Lam, 2020b) treats AMR parsing as a series of
dual decisions (i.e., _which parts of the sequence to abstract_ , and _where
in the graph to construct_) on the input sequence and constructs the AMR graph
incrementally. Following (Cai and Lam, 2020b), we use Stanford
CoreNLP444Available at https://github.com/stanfordnlp/stanza/ for
tokenization, lemmatization, part-of-speech tagging, and named entity
recognition. We apply the pretrained model provided by the authors555The model
“AMR2.0+BERT+GR” can be downloaded from https://github.com/jcyk/AMR-gs to all
testing datasets and follow the same pre-processing and post-processing steps
for graph re-categorization.

##### Graphene (our algorithm)

The only hyperparameter of the Graphene algorithm is the threshold $\theta$. A
popular practice for ensemble methods via voting strategy (Dong et al., 2020)
is to consider the labels that get at least 50% of the total number of votes,
therefore we set the threshold $\theta$ such that $\frac{\theta}{m}\geq 0.5$
(where $m$ is the number of models in the ensemble). In all experiments, we
used a Tesla GPU V100 for model training and used 8 CPUs for making an
ensemble.

####  4.1.2 Evaluation

We use the script666https://github.com/mdtux89/amr-evaluation provided in
(Damonte et al., 2017) to calculate the Smatch score (Cai and Knight, 2013),
the most relevant metric for measuring the similarity between the predictions
and the gold AMR graphs. The overall Smatch score can be broken down into
different dimensions, including the followings sub-metrics:

  * •

Unlabeled (Unl.): Smatch score after removing all edge labels

  * •

No WSD (NWSD): Smatch score while ignoring Propbank senses

  * •

NE: F-score on the named entity recognition (:name roles)

  * •

Wikification (Wiki.): F-score on the wikification (:wiki roles)

  * •

Negations (Neg.): F-score on the negation detection (:polarity roles)

  * •

Concepts (Con.): F-score on the concept identification task

  * •

Reentrancy (Reen.): Smatch computed on reentrant edges only

  * •

SRL: Smatch computed on :ARG-i roles only

####  4.1.3 Datasets

Similarly to (Bevilacqua et al., 2021), we use five standard benchmark
datasets (dat, ) to evaluate our approach. Table 1 shows the statistics of the
datasets. AMR 2.0 and AMR 3.0 are divided into train, development and testing
sets and we use them for _in-distribution_ evaluation in Section 4.2.
Furthermore, the models trained on AMR 2.0 training data are used to evaluate
_out-of-distribution_ prediction on the BIO, the LP and the New3 dataset (See
Section 4.3).

Table 1: Benchmark datasets. All instances of BIO, LP, and New3 are used to test models in out-of-distribution evaluation. For AMR 2.0 and 3.0, the models are trained on the training dataset, validated on the development dataset. We report results on testing sets in the in-distribution evaluation. Datasets | AMR 2.0 | AMR 3.0 | BIO | Little Prince (LP) | New3
---|---|---|---|---|---
Training | 36,521 | 55,635 | n/a | n/a | n/a
Dev | 1,368 | 1,722 | n/a | n/a | n/a
Test | 1,371 | 1,898 | 6,952 | 1,562 | 527

###  4.2 In-distribution evaluation

In the same spirit of (Bevilacqua et al., 2021), we evaluate the approaches
when training and test data belong to the same domain. Table 2 shows the
results of the models on the test split of the AMR 2.0 and AMR 3.0 datasets.
The metrics reported for SPRING correspond to the model with the highest
Smatch score among the 4 models(the checkpoint plus the 3 models with
different random seeds).

Table 2:  Results on the test splits of the AMR 2.0 and AMR 3.0 dataset.  Models | Smatch | Unl. | NWSD | Con. | NE | Neg. | Wiki. | Reen. | SRL
---|---|---|---|---|---|---|---|---|---
AMR 2.0 |  |  |  |  |  |  |  |  |
SPRING | 84.22 | 87.38 | 84.72 | 89.98 | 90.77 | 72.65 | 82.76 | 74.30 | 82.89
APT | 82.70 | 86.18 | 83.23 | 89.48 | 90.20 | 67.27 | 78.87 | 73.19 | 82.01
T5 | 82.98 | 86.17 | 83.43 | 89.85 | 90.65 | 73.43 | 77.99 | 72.44 | 82.02
Cai&Lam | 80.15 | 83.60 | 80.66 | 87.39 | 82.25 | 78.09 | 85.36 | 66.46 | 77.35
_Graphene 4S_ | 84.78 | 87.96 | 85.29 | 90.64 | 92.19 | 75.22 | 83.88 | 71.42 | 83.46
_Graphene All_ | 85.85 | 88.68 | 86.35 | 91.23 | 92.30 | 77.01 | 84.63 | 74.49 | 84.41
AMR 3.0 |  |  |  |  |  |  |  |  |
SPRING | 83.25 | 86.40 | 83.71 | 89.38 | 87.80 | 72.94 | 81.22 | 73.33 | 81.97
APT | 80.57 | 83.96 | 81.07 | 88.38 | 86.82 | 68.69 | 76.88 | 70.78 | 80.17
T5 | 82.17 | 85.22 | 82.66 | 89.03 | 86.99 | 72.59 | 73.78 | 72.18 | 81.18
_Graphene 4S_ | 83.77 | 86.89 | 84.23 | 90.09 | 88.27 | 74.60 | 81.92 | 70.22 | 82.46
_Graphene All_ | 84.41 | 87.35 | 84.83 | 90.51 | 88.64 | 74.76 | 82.25 | 71.93 | 83.15

For the ensemble approach, we report the result when Graphene is an ensemble
of four SPRING checkpoints, denoted as _Graphene 4S_. The ensemble of all the
models including four SPRING checkpoints, APT, T5, and Cai&Lam is denoted as
_Graphene All_. For the AMR 3.0 dataset, the Cai&Lam model is not available so
the reported result corresponds to an ensemble of all six models.

We can see that Graphene successfully leverages the strength of all the models
and provides better prediction both in terms of the overall Smatch score and
sub-metrics. In both datasets, we achieve the state-of-the-art results with
performance gain of 1.6 and 1.2 Smatch points in AMR 2.0 and AMR 3.0
respectively. Table 2 shows that by combining predictions from four
checkpoints of the SPRING model, Graphene 4S provides better results than any
individual models. The result is improved further when increasing the number
of ensemble models, indeed _Graphene All_ improves _Graphene 4S_ further and
outperforms the individual models in terms of the overall Smatch score.

###  4.3 Out-of-distribution evaluation

In contrast to in-distribution evaluation, we use the models trained with AMR
2.0 data to collect AMR predictions for the testing datasets in the domains
that differ from the AMR 2.0 dataset. The purpose of the experiment is to
evaluate the ensemble approach under out-of-distribution settings.

Table 3 shows the results of our experiments. Similar to the in-distribution
experiments, the _Graphene 4S_ algorithm achieves better results than other
individual models, while the _Graphene All_ approach improves the given
results further. We achieve the new state-of-the-art results in these
benchmark datasets (under out-of-distribution settings). This result has an
important practical implication because in practice it is very common not to
have labeled AMR data for domain-specific texts. After all, the labeling task
is very time-demanding. Using the proposed ensemble methods we can achieve
better results with domain-specific data not included in the training sets.

Table 3:  Results of out-of-distribution evaluation on the BIO, New3, and Little Prince dataset. Models | Smatch | Unl. | NWSD | Con. | NE | Neg. | Wiki. | Reen. | SRL
---|---|---|---|---|---|---|---|---|---
BIO |  |  |  |  |  |  |  |  |
SPRING | 60.52 | 65.33 | 61.42 | 67.76 | 33.92 | 65.68 | 3.80 | 51.19 | 62.86
APT | 51.23 | 56.27 | 51.81 | 58.22 | 15.68 | 52.91 | 3.62 | 43.53 | 54.24
T5 | 58.89 | 63.86 | 59.69 | 66.63 | 30.42 | 65.11 | 2.46 | 48.56 | 61.47
Cai&Lam | 42.22 | 49.78 | 42.85 | 47.10 | 5.19 | 51.42 | 7.32 | 39.23 | 51.00
_Graphene 4S_ | 61.51 | 66.22 | 62.28 | 68.48 | 33.02 | 68.24 | 4.46 | 50.40 | 63.70
_Graphene All_ | 62.29 | 66.89 | 63.07 | 68.64 | 32.62 | 69.48 | 4.54 | 52.06 | 64.21
New3 |  |  |  |  |  |  |  |  |
SPRING | 74.66 | 78.99 | 75.21 | 82.38 | 67.52 | 67.48 | 67.20 | 66.47 | 75.65
APT | 71.06 | 75.92 | 71.58 | 80.34 | 65.65 | 67.08 | 57.14 | 63.02 | 73.40
T5 | 73.04 | 77.30 | 73.68 | 82.65 | 68.24 | 64.20 | 56.42 | 64.65 | 75.03
Cai&Lam | 60.81 | 66.00 | 61.29 | 72.79 | 45.60 | 59.57 | 46.39 | 57.70 | 68.87
_Graphene 4S_ | 74.84 | 79.23 | 75.30 | 82.56 | 69.98 | 69.51 | 68.34 | 63.53 | 76.31
_Graphene All_ | 75.60 | 79.64 | 76.14 | 83.08 | 68.40 | 69.62 | 67.98 | 67.16 | 76.88
Little Prince |  |  |  |  |  |  |  |  |
SPRING | 77.85 | 82.31 | 78.85 | 84.68 | 60.53 | 70.72 | 60.53 | 68.28 | 77.78
APT | 75.21 | 80.07 | 76.12 | 85.29 | 65.15 | 67.92 | 69.70 | 63.28 | 75.31
T5 | 77.66 | 81.99 | 78.53 | 85.12 | 58.06 | 72.33 | 59.35 | 67.03 | 78.30
Cai&Lam | 71.03 | 75.91 | 72.07 | 80.18 | 22.73 | 57.51 | 31.50 | 59.29 | 72.02
_Graphene 4S_ | 77.91 | 82.40 | 78.86 | 84.91 | 61.54 | 73.58 | 60.65 | 64.77 | 78.12
_Graphene All_ | 78.54 | 82.81 | 79.44 | 85.52 | 64.05 | 75.11 | 63.45 | 67.83 | 78.72
Figure 3:  The gold AMR and the ensemble AMR graph of SPRING, T5, APT and
Cai&Lam using the Graphene algorithm for the sentence _“They want money, not
the face"_.

###  4.4 How the ensemble algorithm works

We explore a few examples to demonstrate the reason why the ensemble method
works. Figure 3 shows a sentence with a gold AMR in Penman format and a list
of AMRs corresponding to the prediction of SPRING (Bevilacqua et al., 2021),
T5 (Raffel et al., 2020), APT (Zhou et al., 2021), Cai and Lam (Cai and Lam,
2020b) parser and the ensemble graph given by Graphene.

In this particular example, with the sentence _“They want money, not the
face"_ , the AMR prediction from SPRING is inaccurate. Graphene corrects the
prediction thanks to the votes given from the other models. In particular, the
label $and$ of the root node $z_{0}$ of SPRING prediction was corrected to
$contrast-01$ because T5, APT and Cai&Lam parsers all vote for $contrast-01$.
On the other hand, the labels $:op1$ and $:op2$ of the edges $(z_{0},z_{1})$
and $(z_{0},z_{4})$ were modified to have the correct labels $:ARG1$ and
$:ARG2$ accordingly thanks to the votes from the other models. We can also see
that even though the Cai&Lam method misses polarity prediction, since the
other models predict polarity correctly, the ensemble prediction does not
inherit this mistake. Putting everything together, the prediction from
Graphene perfectly matches with the gold AMR graph in this example.

Table 4:  The average total support and Smatch score of the prediction from SPRING, Graphene with SPRING as a pivot and Graphene considering every prediction as a pivot respectively. The support is highly correlated with Smatch score. | AMR 2.0 | AMR 3.0 | BIO | LP | New3
---|---|---|---|---|---
| Sup. | Smat. | Sup. | Smat. | Sup. | Smat. | Sup. | Smat. | Sup. | Smat.
SPRING | 170.15 | 84.08 | 136.90 | 83.14 | 166.86 | 60.52 | 69.33 | 77.85 | 118.27 | 74.66
SPR. pivot | 172.70 | 84.70 | 139.42 | 83.73 | 169.97 | 61.56 | 70.97 | 78.22 | 120.85 | 74.83
Graphene | 175.73 | 85.85 | 142.07 | 84.43 | 179.38 | 62.29 | 72.64 | 78.54 | 123.62 | 75.60

The Graphene algorithm searches for the graph that has the largest support
from all individual graphs. One question that arises from this is whether the
support is correlated with the accuracy of AMR parsing. Table 4 shows the
support and the Smatch score of three models in the standard benchmark
datasets. The first model is SPRING, while the second one denoted as _Graphene
SPRING pivot_ starts with a SPRING prediction as a pivot and corrects the
prediction using votes from other models. The last model corresponds to the
Graphene algorithm that polls the votes while considering every prediction as
a pivot for correction and selecting the best one. Since Graphene looks for
the best pivot to have better-supported ensemble graphs, the total supports of
the Graphene predictions are larger than the Graphene SPRING pivot
predictions. From the table, we can also see that the total support is highly
correlated to the Smatch score. Namely, Graphene has higher support in all the
benchmark datasets and a higher Smatch score than Graphene SPRING pivot. This
experiment suggests that by optimizing the total support we can obtain the
ensemble graphs with higher Smatch score.

##  5 Related work

##### Ensemble learning.

Ensemble learning is a popular machine learning approach that combines
predictions from different learners to make a more robust and more accurate
prediction. Many ensembling approaches have been proposed, such as bagging
(Breiman, 1996) or boosting (Schapire and Freund, 2013), the winning solutions
in many machine learning competitions (Chen and Guestrin, 2016). These methods
are proposed mainly for regression or classification problems. Recently,
structure output prediction emerges as an important problem thanks to the
advances in deep learning research. To apply popular ensembling techniques
such as bagging or boosting, it is important to study the ensemble method for
combining structure predictions.

##### Ensemble structure prediction.

Previous studies have explored various ensemble learning approaches for
dependency and constituent parsing: (Sagae and Lavie, 2006) proposes a
reparsing framework that takes the output from different parsers and maximizes
the number of votes for a well-formed dependency or constituent structure;
(Kuncoro et al., 2016) uses minimum Bayes risk inference to build a consensus
dependency parser from an ensemble of independently trained greedy LSTM
transition-based parsers with different random initializations. Note that a
syntactic tree is a special graph structure in which nodes for a sentence from
different parsers are roughly the same. In contrast, we propose an approach to
ensemble graph predictions in which both graph nodes and edges can be
different among base predictions.

##### Ensemble methods for AMR parsing.

Parsing text to AMR is an important research problem. State-of-the-art
approaches in AMR parsing are divided into three categories. Sequence to
sequence models (Bevilacqua et al., 2021; Konstas et al., 2017; Van Noord and
Bos, 2017; Xu et al., 2020) consider the AMR parsing as a machine translation
problem that translates texts to AMR graphs. The transition-based methods
(Zhou et al., 2021) predicts a sequence of actions given the input text, and
then the action sequence is turned into an AMR graph using an oracle decoder.
Lastly, graph-based methods (Cai and Lam, 2020b) directly construct the AMR
graphs from textual data. All these methods are complementary to each other
and thus ensemble methods can leverage the strength of these methods to create
a better prediction, as demonstrated in this paper. Ensemble of AMR
predictions from a single type of model is studied in (Zhou et al., 2021)
where the authors demonstrated that by combining predictions from three
different model’s checkpoints they gain performance improvement in the final
prediction. However, ensemble in sequential decoding requires that all
predictions are from the same type of models. It is not applicable for cases
when the predictions are from different types of models such as seq2seq,
transition-based or graph-based models. In contrast to that approach, our
algorithm is model-agnostic, i.e. it can combine predictions from different
models. In our experiments, we have demonstrated the benefit of combining
predictions from different models, with additional gains in performance
compared to the ensemble of predictions from a single model’s checkpoints.

##  6 Conclusions and future work

In this paper, we formulate the graph ensemble problem, study its
computational intractability, and provide an algorithm for constructing graph
ensemble predictions. We validate our approach with AMR parsing problems. The
experimental results show that the proposed approach outperforms the previous
state-of-the-art AMR parsers and achieves new state-of-the-art results in five
different benchmark datasets. We demonstrate that the proposed ensemble
algorithm not only works well for in-distribution but also for out-of-
distribution evaluations. This result has a significant practical impact,
especially when applying the proposed method to domain-specific texts where
training data is not available. Moreover, our approach is model-agnostic,
which means that it can be used to combine predictions from different models
without the requirement of having an access to model training. In general, our
approach provides the basis for graph ensemble, studying classical ensemble
techniques such as bagging, boosting, or stacking for graph ensemble is a
promising future research direction that is worth considering to improve the
results further.

## References

  * [1] AMRLIB data preprocessing https://github.com/bjascob/amrlib/tree/master/scripts.
  * [2] AMR benchmark datasets. https://amr.isi.edu/download.html.
  * [3] English Web Treebank dataset: https://catalog.ldc.upenn.edu/ldc2012t13.  URL https://catalog.ldc.upenn.edu/LDC2012T13.
  * Bahiense et al. [2012] Laura Bahiense, Gordana Manić, Breno Piva, and Cid C De Souza.  The maximum common edge subgraph problem: A polyhedral investigation.  _Discrete Applied Mathematics_ , 160(18):2523–2541, 2012.
  * Banarescu et al. [2013] Laura Banarescu, Claire Bonial, Shu Cai, Madalina Georgescu, Kira Griffitt, Ulf Hermjakob, Kevin Knight, Philipp Koehn, Martha Palmer, and Nathan Schneider.  Abstract meaning representation for sembanking.  In _Proceedings of the 7th Linguistic Annotation Workshop and Interoperability with Discourse_ , pages 178–186, 2013.
  * Bevilacqua et al. [2021] Michele Bevilacqua, Rexhina Blloshmi, and Roberto Navigli.  One SPRING to rule them both: Symmetric AMR semantic parsing and generation without a complex pipeline.  In _Proceedings of AAAI_ , 2021.
  * Breiman [1996] Leo Breiman.  Bagging predictors.  _Machine learning_ , 24(2):123–140, 1996.
  * Cai and Lam [2020a] Deng Cai and Wai Lam.  AMR parsing via graph-sequence iterative inference.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 1290–1301, Online, July 2020a. Association for Computational Linguistics.  doi:10.18653/v1/2020.acl-main.119.  URL https://www.aclweb.org/anthology/2020.acl-main.119.
  * Cai and Lam [2020b] Deng Cai and Wai Lam.  AMR parsing via graph-sequence iterative inference.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 1290–1301, Online, July 2020b. Association for Computational Linguistics.  doi:10.18653/v1/2020.acl-main.119.  URL https://www.aclweb.org/anthology/2020.acl-main.119.
  * Cai and Knight [2013] Shu Cai and Kevin Knight.  Smatch: an evaluation metric for semantic feature structures.  In _Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_ , pages 748–752, Sofia, Bulgaria, August 2013. Association for Computational Linguistics.  URL https://www.aclweb.org/anthology/P13-2131.
  * Chen and Guestrin [2016] Tianqi Chen and Carlos Guestrin.  XGBoost: A scalable tree boosting system.  In _Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , 2016.
  * Damonte et al. [2017] Marco Damonte, Shay B. Cohen, and Giorgio Satta.  An incremental parser for Abstract Meaning Representation.  In _Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics: Volume 1, Long Papers_ , pages 536–546, Valencia, Spain, April 2017. Association for Computational Linguistics.  URL https://www.aclweb.org/anthology/E17-1051.
  * Domingos [2000] Pedro Domingos.  A unified bias-variance decomposition.  In _Proceedings of 17th International Conference on Machine Learning_ , pages 231–238, 2000.
  * Dong et al. [2020] Xibin Dong, Zhiwen Yu, Wenming Cao, Yifan Shi, and Qianli Ma.  A survey on ensemble learning.  _Frontiers of Computer Science_ , 14(2):241–258, 2020.
  * Kapanipathi et al. [2020] Pavan Kapanipathi, Ibrahim Abdelaziz, Srinivas Ravishankar, Salim Roukos, Alexander Gray, Ramon Astudillo, Maria Chang, Cristina Cornelio, Saswati Dana, Achille Fokoue, et al.  Question answering over knowledge bases by leveraging semantic parsing and neuro-symbolic reasoning.  _arXiv preprint arXiv:2012.01707_ , 2020.
  * Konstas et al. [2017] Ioannis Konstas, Srinivasan Iyer, Mark Yatskar, Yejin Choi, and Luke Zettlemoyer.  Neural AMR: Sequence-to-sequence models for parsing and generation.  _ACL_ , 2017.
  * Kuncoro et al. [2016] Adhiguna Kuncoro, Miguel Ballesteros, Lingpeng Kong, Chris Dyer, and Noah A. Smith.  Distilling an ensemble of greedy dependency parsers into one MST parser.  In _Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing_ , pages 1744–1753, Austin, Texas, November 2016. Association for Computational Linguistics.  doi:10.18653/v1/D16-1180.  URL https://www.aclweb.org/anthology/D16-1180.
  * Lee et al. [2020] Young-Suk Lee, Ramon Fernandez Astudillo, Tahira Naseem, Revanth Gangi Reddy, Radu Florian, and Salim Roukos.  Pushing the limits of AMR parsing with self-learning.  In _Findings of EMNLP 2020_ , pages 3208–3214, 2020.
  * Li et al. [2020] Belinda Z. Li, Sewon Min, Srinivasan Iyer, Yashar Mehdad, and Wen-tau Yih.  Efficient one-pass end-to-end entity linking for questions.  In _EMNLP_ , 2020.
  * Lim et al. [2020] Jungwoo Lim, Dongsuk Oh, Yoonna Jang, Kisu Yang, and Heuiseok Lim.  I know what you asked: Graph path learning using AMR for commonsense reasoning.  In _Proceedings of the 28th International Conference on Computational Linguistics_ , pages 2459–2471, Barcelona, Spain (Online), December 2020. International Committee on Computational Linguistics.  doi:10.18653/v1/2020.coling-main.222.  URL https://www.aclweb.org/anthology/2020.coling-main.222.
  * Raffel et al. [2020] Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu.  Exploring the limits of transfer learning with a unified text-to-text transformer.  _Journal of Machine Learning Research_ , 21(140):1–67, 2020.  URL http://jmlr.org/papers/v21/20-074.html.
  * Sagae and Lavie [2006] Kenji Sagae and Alon Lavie.  Parser combination by reparsing.  In _Proceedings of the Human Language Technology Conference of the NAACL, Companion Volume: Short Papers_ , pages 129–132, New York City, USA, June 2006. Association for Computational Linguistics.  URL https://www.aclweb.org/anthology/N06-2033.
  * Schapire and Freund [2013] Robert E Schapire and Yoav Freund.  Boosting: Foundations and algorithms.  _Kybernetes_ , 2013.
  * Valentini and Dietterich [2004] Giorgio Valentini and Thomas G Dietterich.  Bias-variance analysis of support vector machines for the development of svm-based ensemble methods.  _Journal of Machine Learning Research_ , 5(Jul):725–775, 2004.
  * Van Noord and Bos [2017] Rik Van Noord and Johan Bos.  Neural semantic parsing by character-based translation: Experiments with abstract meaning representations.  _arXiv preprint arXiv:1705.09980_ , 2017.
  * Vaswani et al. [2017] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  _Advances in Neural Information Processing Systems_ , pages 5998–6008, 2017.
  * Xu et al. [2020] Dongqin Xu, Junhui Li, Muhua Zhu, Min Zhang, and Guodong Zhou.  Improving AMR parsing with sequence-to-sequence pre-training.  _EMNLP_ , 2020.
  * Zhou et al. [2021] Jiawei Zhou, Tahira Naseem, Ramon Fernandez Astudillo, and Radu Florian.  AMR parsing with action-pointer transformer.  In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (NAACL 2021)_ , pages 5585–5598, 2021.

Ensemble Graph Prediction
Supplementary Material

##  Appendix A Running time

Figure 4 shows the average running time of the Graphene algorithm. The
horizontal axis corresponds to the average graph size (the number of triples)
while the vertical axis shows the average running time (in seconds). We can
see that the running time depends on the average size of the AMR graphs. Since
AMR graph size is proportional to the input sentence length, the largest
average graph has around 50 triples. Graphene requires less than 2 seconds on
an 8-core CPU machine to make an ensemble from 7 models.

Figure 4:  Average running time of the Graphene algorithm versus the average
graph size in the LP, New3, AMR 3.0, AMR 2.0, and BIO datasets respectively.

##  Appendix B On the support threshold

The popular VotingClassifier algorithm implemented in scikit-learn
777https://scikit-
learn.org/stable/modules/generated/sklearn.ensemble.VotingClassifier.html
follows the majority vote rule where the label with the most votes is selected
as the final prediction. Therefore, we apply the same rule in our experimental
settings where setting theta = 0.5 is equivalent to the majority vote rule in
classification problems.

If there is an independent validation set, this hyper-parameter can be tuned
to choose the right theta value for that dataset. For example, in the AMR 2.0
dataset, the results of ensembling 4 Spring models, APT model, and T5 models
on the validation set (the dev split) when theta is varied are reported in
Table 5.

Table 5:  The results of ensembling 4 Spring models, APT model, and T5 models on the validation set (the dev split) when $\theta$ is varied. On this dev set, $\theta=0.5$ is a proper choice for AMR 2.0. | $\theta=0.1$ | $\theta=0.3$ | $\theta=0.5$ | $\theta=0.7$ | $\theta=0.9$
---|---|---|---|---|---
Smatch | 81.64 | 85.01 | 85.49 | 85.12 | 83.68
Precision | 76.13 | 83.62 | 85.86 | 86.53 | 86.54
Recall | 88.00 | 86.55 | 85.13 | 83.75 | 81.01

Based on this result on an independent dev set, theta=0.5 is the right choice
for AMR 2.0. Note that setting theta is a trade-off between precision and
recall.

##  Appendix C Comparison with median baselines

Beside the Graphene 4S baseline, we provide the results in Table 6 of the
following baseline approaches:

  * •

Uniform sampling: for each set of predictions we sample the graph uniformly at
random, this approach is equivalent to the “median” representative from a set.

  * •

Ideal median: assumes that the gold AMRs are available for the test set (hence
named as "ideal"). We computed the Smatch of each prediction with the gold AMR
and use the AMR with the median Smatch score as the final prediction.

Table 6:  Comparison with median baselines  | AMR 2.0 | AMR 3.0 | BIO | new3 | LP
---|---|---|---|---|---
uniform Sampling | 82.58 | 82.98 | 56.00 | 71.18 | 76.17
Ideal median | 83.80 | 83.66 | 57.72 | 73.06 | 77.14
Graphene | 85.85 | 84.41 | 62.29 | 75.60 | 78.54

##  Appendix D Pivot selection

Figure 5:  Pie charts shows the percentage of the number of times each model
was selected as the best pivot in the Graphene algorithm. Notice that when
tight happens, the ensemble created when first algorithm is considered as the
pivot is selected as the final ensemble graph.

Figure 5 shows the pie-charts with the percentage summarizing the number of
times that the prediction created when each algorithm is chosen as a pivot
graph is selected as the final prediction. Notice that the order of the
algorithms matters because when tight happens, the ensemble is chosen from the
first algorithm in the list.

The results show that all algorithms contribute to the final predictions. In
the Bio dataset where the test data is from a specific domain that differs
from the training data domain, Graphene benefits from the model diversity when
it leverages predictions from all models effectively.

##  Appendix E Robustness on down-sampled training data

Table 7:  When the training data is down-sampled, the gain of using Graphene is enlarged. | Sample rate 0.6 | Sample rate 0.8
---|---|---
Methods/Data | AMR 2.0 | BIO | New3 | LP | AMR 2.0 | BIO | New3 | LP
SPRING 603 | 82.40 | 58.22 | 73.81 | 76.75 | 83.28 | 58.85 | 74.13 | 76.96
SPRING 703 | 82.74 | 57.93 | 73.49 | 76.60 | 83.43 | 59.50 | 74.71 | 77.40
SPRING 803 | 82.85 | 58.72 | 73.42 | 76.68 | 83.39 | 58.97 | 73.57 | 77.39
SPRING 903 | 82.81 | 58.80 | 74.09 | 76.96 | 83.12 | 57.52 | 73.50 | 76.70
T5 | 82.08 | 56.46 | 72.84 | 76.31 | 82.59 | 58.69 | 73.42 | 77.70
Graphene | 84.20 | 61.66 | 75.01 | 77.79 | 84.70 | 62.23 | 75.98 | 78.09

We down-sampled the AMR 2.0 training data with sample rates 0.6 and 0.8. Then
4 Spring models with different random seeds and the T5 model were trained on
these two sample sets. The Smatch score on AMR 2 test sets and on the out-of-
distribution sets (LP, New3, Bio) are reported in Table 7.

Compared to the best individual models, Graphene is more robust and 1.35,
2.86, 0.92, and 0.83 points better when the sample rate is equal to 0.6. While
compared to the best individual models, Graphene is more robust and 1.27,
2.73, 1.27 and 0.39 points better better when the sample rate is equal to 0.8.
This result demonstrates that the proposed method is robust with respect to
smaller training data.

##  Appendix F Ties broken arbitrarily

When many ensemble graphs have the same support, Graphene chooses the ensemble
graph created when the first model in the list is chosen as the pivot. Table 8
shows the results when each model is put first in the list. If we have a
validation set like the case with AMR 2.0 or AMR 3.0, we can tune the right
input order to achieve the best performance on the validation set.

In case there is no validation set available, to mitigate the impact of random
input order, we can break the ties arbitrarily, the results of ties broken
arbitrarily are reported in Table 9.

Table 8:  Results of Graphene when each model is put first in the list.  Grapphene Models | S | S703 | S803 | S903 | T5 | APT | Cai&Lam
---|---|---|---|---|---|---|---
AMR 2.0 | 85.66 | 85.77 | 85.81 | 85.87 | 85.65 | 85.67 | 85.11
AMR 3.0 | 84.44 | 84.42 | 84.34 | 84.44 | 84.35 | 84.18 | NA
Bio | 62.38 | 62.41 | 62.39 | 62.44 | 62.38 | 62.41 | 62.34
LP | 78.65 | 78.63 | 78.75 | 78.70 | 78.65 | 78.23 | 77.75
New3 | 75.65 | 75.69 | 75.88 | 75.82 | 75.78 | 75.48 | 74.92
Table 9:  Results of Graphene when ties are broken arbitrarily.  Grapphene Models | AMR 2.0 | AMR 3.0 | Bio | LP | New3
---|---|---|---|---|---
Graphene 4SATC | 85.52 | 84.27 | 62.39 | 78.50 | 75.66

##  Appendix G Support and Smatch

We have shown in Table 4 that the average total support is highly correlated
with the Smatch score. We performed statistical significant tests to support
the given hypothesis. Below is the correlation between the "Normalised total
support" (the total support normalised to the size of the graph) and the
Smatch score, together with the p-value for each dataset:

  * •

AMR 2.0: Pearson correlation =0.60 , p-value = 2.7e-117

  * •

AMR 3.0: Pearson correlation =0.49 , p-value = 2.6e-137

  * •

BIO: Pearson correlation =0.55 , p-value = 0.0

  * •

LP: Pearson correlation =0.56, p-value =3.4e-130

  * •

New3: Pearson correlation = 0.73, p-value=5.1e-191

The overall correlation between the "Normalised total support" and the Smatch
score, together with the p-value for all datasets is: Pearson correlation
=0.67 , p-value=0.0