aainstitutetext: Korea Institute for Advanced Study,
85 Hoegiro, Dongdaemun-Gu, Seoul 02455, Koreabbinstitutetext: Academy of
Mathematics and Systems Science,
Beijing 100190, P. R. Chinaccinstitutetext: CAS Key Laboratory of Theoretical
Physics, Institute of Theoretical Physics,
Chinese Academy of Sciences, Beijing 100190, P. R. Chinaddinstitutetext:
School of Physical Sciences, University of Chinese Academy of Sciences,
No.19A Yuquan Road, Beijing 100049, P. R. Chinaeeinstitutetext: School of
Sciences, Xi’an Technological University, Xi’an 710021, P. R. China

# The Final Model Building for the Supersymmetric Pati-Salam Models from
Intersecting D6-Branes

Weikun He c,d,2 Tianjun Li a,3 Rui Sun***Corresponding author. e,4 Lina Wu
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

All the possible three-family ${\cal N}=1$ supersymmetric Pati-Salam models
constructed with intersecting D6-branes from Type IIA orientifolds on
$T^{6}/(\mathbb{Z}_{2}\times\mathbb{Z}_{2})$ are recently presented in arXiv:
2112.09632. Taking models with largest wrapping number $5$ and approximate
gauge coupling unification at GUT scale as examples, we show string scale
gauge coupling unification can be realized through two-loop renormalization
group equation running by introducing seven pairs of vector-like particles
from ${\cal N}=2$ sector. The number of these introduced vector-like particles
are fully determined by the brane intersection numbers while there are two
D6-brane parallel to each other along one two-torus. We expect this will solve
the gauge coupling unification problem in the generic intersecting brane
worlds by introducing vector-like particles that naturally included in the
${\cal N}=2$ sector.

##  1 Introduction

How to construct the realistic string models which are consistent with the low
energy phenomenology is a great challenge question. Among various string
models, the Pati-Salam model building in Type IIA theory on
$T^{6}/(\mathbb{Z}_{2}\times\mathbb{Z}_{2})$ orientifold with intersecting
D6-branes lpt ; magnetised ; MCJW ; Ibanez ; MKRR ; urangac ; afiru ; Uranga ;
imr ; bgkl ; bkl ; CSU2 ; Blumenhagen:2003jy ; CPS ; Cvetic:2004ui ;
Blumenhagen:2005mu ; Blumenhagen:2006ci ; CLW ; blumrecent ; Honecker ;
Cvetic:2004nk ; Chen:2005mj ; Chen:2007px ; Chen:2007zu  is very interesting,
although the absence of gauge coupling unification at the string scale might
be a generic problem. Recently, some concrete supersymmetric Pati-Salam models
have been constructed Li:2019nvi ; Li:2021 , and such D-brane models have been
investigated with more powerful reinforcement machine learning methods and
genetic algorithms as shown in Refs. Jim:brane ; Loges:2021hvn .

In Li:2021-2 , we propose a systematic method for such kind of model building
and for the first time construct all the three-family ${\cal N}=1$
supersymmetric Pati-Salam models from intersecting D6-branes where the gauge
symmetry can be broken down to the Standard Model (SM) gauge symmetry via the
D-brane splitting and supersymmetry (SUSY) preserving Higgs mechanism. We find
that there are $202752$ models in total, and show that there are only 33
independent models with different gauge coupling relations at string scale
after moduloing the equivalent relations. Thus, for the string landscape
study, we would like to emphasize that it is very important to consider the
equivalent relations. Howevere, one and only one model has traditional gauge
coupling unification at string scale. We also find that the largest absolute
value of wrapping number is $5$.

In Blumenhagen:2003jy , additional vector-like matter was introduced to push
GUT scale unification up to Planck scale for $SU(5)$ and $SO(10)$ GUT
theories. Instead of studying pushing up the unification scale, we will study
the methods to achieve string scale gauge unification from ${\cal N}=1$
supersymmetric Pati-Salam models without GUT scale unification. Taking models
with largest wrapping number $5$ and approximate gauge coupling unification as
an examples, we show that the additional exotic particles can be decoupled and
its gauge coupling relation can be realized at string scale via two-loop
renormalization group equation running by introducing seven pairs of vector-
like particles from ${\cal N}=2$ sector. Therefore, although most of these
Pati-Salam models do not directly have gauge coupling unification at string
scale, their gauge coupling unification may indeed be achieved at string scale
by introducing the vector-like particles from ${\cal N}=2$ sector. And then we
solve the gauge coupling unification problem in the generic D-brane models.
Moreover, one can explain the SM fermion masses and mixings via the three-
point and four point functions LMSW . Furthermore, it seems to us that this
brand new systematic method can be applied to the other intersecting D-brane
model building as well.

##  2 Review of Model Building

First, we briefly review the basics of constructing supersymmetric Pati-Salam
models on Type IIA $T^{6}/(\mathbb{Z}_{2}\times\mathbb{Z}_{2})$ orientifolds
with D6-branes intersecting at generic angles as discussed in CSU2 ; CPS .
Consider the six-torus $T^{6}$ factorized as three two-tori $T^{6}=T^{2}\times
T^{2}\times T^{2}$. Let $z_{i}$, $i=1,\;2,\;3$ be respectively the complex
coordinates for the $i$-th two-torus. For the orbifold group
$\mathbb{Z}_{2}\times\mathbb{Z}_{2}$, the generators $\theta$ and $\omega$ are
associated with the twist vectors $(1/2,-1/2,0)$ and $(0,1/2,-1/2)$
respectively. They act on the complex coordinates $z_{i}$ as

$\begin{split}\theta:&(z_{1},z_{2},z_{3})\mapsto(-z_{1},-z_{2},z_{3})\leavevmode\nobreak\
,\leavevmode\nobreak\ \\\
\omega:&(z_{1},z_{2},z_{3})\mapsto(z_{1},-z_{2},-z_{3})\leavevmode\nobreak\
.\leavevmode\nobreak\ \end{split}$ (1)

The orientifold projection is implemented by gauging the $\Omega R$ symmetry,
where $\Omega$ is world-sheet parity and $R$ acts on the complex coordinates
as

$R:(z_{1},z_{2},z_{3})\mapsto({\overline{z}}_{1},{\overline{z}}_{2},{\overline{z}}_{3})\leavevmode\nobreak\
.\leavevmode\nobreak\ \,$ (2)

In total, we have four kinds of orientifold 6-planes (O6-planes) for the
actions of $\Omega R$, $\Omega R\theta$, $\Omega R\omega$, and $\Omega
R\theta\omega$ respectively bkl ; Chen:2007zu ; CSU2 ; CPS . Moreover, three
stacks of $N_{a}$ D6-branes wrapping on the factorized three-cycles are
introduced to cancel the RR charges of these O6-planes.

There are two kinds of complex structures: rectangular and tilted, consistent
with the orientifold projection. The homology classes of these three cycles
wrapped by the D6-brane stack are of the form
$n_{a}^{i}[a_{i}]+m_{a}^{i}[b_{i}]$ for a rectangular torus and
$n_{a}^{i}[a^{\prime}_{i}]+m_{a}^{i}[b_{i}]$ for a tilted torus, where
$[a_{i}^{\prime}]=[a_{i}]+\frac{1}{2}[b_{i}]$. A generic one cycle can be
labeled by $(n_{a}^{i},l_{a}^{i})$ in terms of these wrapping numbers, with
$l_{a}^{i}\equiv m_{a}^{i}$ and $l_{a}^{i}\equiv
2\tilde{m}_{a}^{i}=2m_{a}^{i}+n_{a}^{i}$ for a rectangular and tilted two-
torus respectively. Note that $l_{a}^{i}-n_{a}^{i}$ is an even number for
tilted two-tori. We denote the wrapping number for stack $a$ of D6-branes
along the cycle to be $(n_{a}^{i},l_{a}^{i})$, and their $\Omega R$ images
${a^{\prime}}$ stack of $N_{a}$ D6-branes are with wrapping numbers
$(n_{a}^{i},-l_{a}^{i})$. The homology three-cycles for stack $a$ of D6-branes
and its orientifold image $a^{\prime}$ can be expressed as

$\displaystyle[\Pi_{a}]=\prod_{i=1}^{3}\left(n_{a}^{i}[a_{i}]+2^{-\beta_{i}}l_{a}^{i}[b_{i}]\right),$
(3)
$\displaystyle[\Pi_{a^{\prime}}]=\prod_{i=1}^{3}\left(n_{a}^{i}[a_{i}]-2^{-\beta_{i}}l_{a}^{i}[b_{i}]\right),$
(4)

where $\beta_{i}=0$ if the $i$-th two-torus is rectangular and $\beta_{i}=1$
otherwise. The homology three-cycles wrapped by the four O6-planes take the
forms of

$\begin{split}&\Omega R:[\Pi_{\Omega
R}]=2^{3}[a_{1}]\times[a_{2}]\times[a_{3}]\leavevmode\nobreak\
,\leavevmode\nobreak\ \,\\\ &\Omega R\omega:[\Pi_{\Omega
R\omega}]=-2^{3-\beta_{2}-\beta_{3}}[a_{1}]\times[b_{2}]\times[b_{3}]\leavevmode\nobreak\
,\leavevmode\nobreak\ \\\ &\Omega R\theta\omega:[\Pi_{\Omega
R\theta\omega}]=-2^{3-\beta_{1}-\beta_{3}}[b_{1}]\times[a_{2}]\times[b_{3}]\leavevmode\nobreak\
,\leavevmode\nobreak\ \\\ &\Omega R\theta:[\Pi_{\Omega
R}]=-2^{3-\beta_{1}-\beta_{2}}[b_{1}]\times[b_{2}]\times[a_{3}]\leavevmode\nobreak\
.\leavevmode\nobreak\ \end{split}$ (5)

The intersection numbers can be expressed in terms of the wrapping numbers as

$\displaystyle
I_{ab}=[\Pi_{a}][\Pi_{b}]=2^{-k}\prod_{i=1}^{3}(n_{a}^{i}l_{b}^{i}-n_{b}^{i}l_{a}^{i})\leavevmode\nobreak\
,\leavevmode\nobreak\ $ $\displaystyle
I_{ab^{\prime}}=[\Pi_{a}][\Pi_{b^{\prime}}]=-2^{-k}\prod_{i=1}^{3}(n_{a}^{i}l_{b}^{i}+n_{b}^{i}l_{a}^{i})\leavevmode\nobreak\
,\leavevmode\nobreak\ $ $\displaystyle
I_{aa^{\prime}}=[\Pi_{a}][\Pi_{a^{\prime}}]=-2^{3-k}\prod_{i=1}^{3}(n_{a}^{i}l_{a}^{i})\leavevmode\nobreak\
,\leavevmode\nobreak\ $ (6) $\displaystyle I_{aO6}=[\Pi_{a}][\Pi_{O6}]=$
$\displaystyle
2^{3-k}(-l_{a}^{1}l_{a}^{2}l_{a}^{3}+l_{a}^{1}n_{a}^{2}n_{a}^{3}+n_{a}^{1}l_{a}^{2}n_{a}^{3}+n_{a}^{1}n_{a}^{2}l_{a}^{3})$

where $k=\beta_{1}+\beta_{2}+\beta_{3}$ is the total number of tilted two-
tori, while $[\Pi_{O6}]=[\Pi_{\Omega R}]+[\Pi_{\Omega R\omega}]+[\Pi_{\Omega
R\theta\omega}]+[\Pi_{\Omega R\theta}]$ is the sum of the four O6-plane
homology three-cycles.

The massless particle spectrum obtained from intersecting D6-branes at general
angles can be expressed in terms of these intersection numbers as in Table 1.
Here, the representations refer to $U(N_{a}/2)$, e.g. when the intersecting
D6-branes are of number $N_{a}=8,N_{b}=4,N_{c}=4$, this gives $U(N_{x}/2)$
gauge groups for $x=a,b,c$. The gauge symmetry results from
$\mathbb{Z}_{2}\times\mathbb{Z}_{2}$ orbifold projection, as discussed in CSU2
. The chiral supermultiplets contain both scalars and fermions in this
supersymmetric constructions, while the positive intersection numbers refer to
the left-handed chiral supermultiplets. To have three families of the SM
fermions with quantum numbers are under $SU(4)_{C}\times SU(2)_{L}\times
SU(2)_{R}$ gauge symmetries, we require the intersection numbers to satisfy

$\begin{split}I_{ab}+I_{ab^{\prime}}\leavevmode\nobreak\ =\leavevmode\nobreak\
3\leavevmode\nobreak\ ,\leavevmode\nobreak\ \\\ I_{ac}\leavevmode\nobreak\
=\leavevmode\nobreak\ -3\leavevmode\nobreak\ ,\leavevmode\nobreak\
I_{ac^{\prime}}\leavevmode\nobreak\ =\leavevmode\nobreak\
0\leavevmode\nobreak\ ,\leavevmode\nobreak\ \,\end{split}$ (7)

or with $c$ and $c^{\prime}$ exchange. And then we can break the Pati-Salam
gauge symmetry down to the SM gauge symmetry via the D-brane splitting and
supersymmetry preserving Higgs mechanism Cvetic:2004ui .

Table 1: General massless particle spectrum for intersecting D6-branes at generic angles. Sector | Representation
---|---
$aa$ |  $U(N_{a}/2)$ vector multiplet
| 3 adjoint chiral multiplets
$ab+ba$ |  $I_{ab}$ $(\raisebox{-0.5pt}{\hbox{\rule{0.4pt}{6.5pt}\hskip-0.4pt\rule{6.5pt}{0.4pt}\hskip-6.5pt\rule[6.5pt]{6.5pt}{0.4pt}}\rule[6.5pt]{0.4pt}{0.4pt}\hskip-0.4pt\rule{0.4pt}{6.5pt}}_{a},\overline{\raisebox{-0.5pt}{\hbox{\rule{0.4pt}{6.5pt}\hskip-0.4pt\rule{6.5pt}{0.4pt}\hskip-6.5pt\rule[6.5pt]{6.5pt}{0.4pt}}\rule[6.5pt]{0.4pt}{0.4pt}\hskip-0.4pt\rule{0.4pt}{6.5pt}}}_{b})$ fermions
$ab^{\prime}+b^{\prime}a$ |  $I_{ab^{\prime}}$ $(\raisebox{-0.5pt}{\hbox{\rule{0.4pt}{6.5pt}\hskip-0.4pt\rule{6.5pt}{0.4pt}\hskip-6.5pt\rule[6.5pt]{6.5pt}{0.4pt}}\rule[6.5pt]{0.4pt}{0.4pt}\hskip-0.4pt\rule{0.4pt}{6.5pt}}_{a},\raisebox{-0.5pt}{\hbox{\rule{0.4pt}{6.5pt}\hskip-0.4pt\rule{6.5pt}{0.4pt}\hskip-6.5pt\rule[6.5pt]{6.5pt}{0.4pt}}\rule[6.5pt]{0.4pt}{0.4pt}\hskip-0.4pt\rule{0.4pt}{6.5pt}}_{b})$ fermions
$aa^{\prime}+a^{\prime}a$ |  $\frac{1}{2}(I_{aa^{\prime}}-\frac{1}{2}I_{a,O6})\;\;\raisebox{-0.5pt}{\hbox{\rule{0.4pt}{6.5pt}\hskip-0.4pt\rule{6.5pt}{0.4pt}\hskip-6.5pt\rule[6.5pt]{6.5pt}{0.4pt}}\rule[6.5pt]{0.4pt}{0.4pt}\hskip-0.4pt\rule{0.4pt}{6.5pt}}\hskip-0.4pt\raisebox{-0.5pt}{\hbox{\rule{0.4pt}{6.5pt}\hskip-0.4pt\rule{6.5pt}{0.4pt}\hskip-6.5pt\rule[6.5pt]{6.5pt}{0.4pt}}\rule[6.5pt]{0.4pt}{0.4pt}\hskip-0.4pt\rule{0.4pt}{6.5pt}}\;\;$ fermions
|
$\frac{1}{2}(I_{aa^{\prime}}+\frac{1}{2}I_{a,O6})\;\;\raisebox{-3.5pt}{\hbox{\rule{0.4pt}{6.5pt}\hskip-0.4pt\rule{6.5pt}{0.4pt}\hskip-6.5pt\rule[6.5pt]{6.5pt}{0.4pt}}\rule[6.5pt]{0.4pt}{0.4pt}\hskip-0.4pt\rule{0.4pt}{6.5pt}}\hskip-6.9pt\raisebox{3.0pt}{\hbox{\rule{0.4pt}{6.5pt}\hskip-0.4pt\rule{6.5pt}{0.4pt}\hskip-6.5pt\rule[6.5pt]{6.5pt}{0.4pt}}\rule[6.5pt]{0.4pt}{0.4pt}\hskip-0.4pt\rule{0.4pt}{6.5pt}}\;\;$
fermions

In addition to the three generation conditions Eq.(7), there are two other
main constraints on the four-dimensional $N=1$ supersymmetric model building,
namely, the RR tadpole cancellation conditions and the $N=1$ supersymmetry
preservation in four dimension Uranga ; imr ; CSU2 . In the brane
constructions, D6-branes and the orientifold O6-planes are the sources of RR
fields and restricted by the Gauss law in a compact space. Due to the
conservations of the RR field flux lines, the RR charges from D6-branes must
cancel with it from the O6-planes, which results in the RR tadpole
cancellations conditions

$\sum_{a}N_{a}[\Pi_{a}]+\sum_{a}N_{a}\left[\Pi_{a^{\prime}}\right]-4[\Pi_{O6}]=0,$
(8)

where the last term arises from the O6-planes are with $-4$ RR charges in
D6-brane charge unit. To simplify the discussion on tadpole cancellation
condition in the next section, we define

$\begin{array}[]{rrrr}A_{a}\equiv-n_{a}^{1}n_{a}^{2}n_{a}^{3},\,B_{a}\equiv
n_{a}^{1}l_{a}^{2}l_{a}^{3},\,C_{a}\equiv
l_{a}^{1}n_{a}^{2}l_{a}^{3},\,D_{a}\equiv l_{a}^{1}l_{a}^{2}n_{a}^{3},\\\
\tilde{A}_{a}\equiv-l_{a}^{1}l_{a}^{2}l_{a}^{3},\,\tilde{B}_{a}\equiv
l_{a}^{1}n_{a}^{2}n_{a}^{3},\,\tilde{C}_{a}\equiv
n_{a}^{1}l_{a}^{2}n_{a}^{3},\,\tilde{D}_{a}\equiv
n_{a}^{1}n_{a}^{2}l_{a}^{3}.\end{array}$ (9)

In order to cancel the RR tadpoles, we introduce D6-branes wrapping cycles
along the orientifold planes as the so-called “filler branes”. They
contributes to the RR tadpole cancellation conditions, and trivially satisfy
the four-dimensional $N=1$ supersymmetry conditions. They are chosen such that
the tadpole conditions satisfy

$\begin{split}&-2^{k}N^{(1)}+\sum_{a}N_{a}A_{a}=-2^{k}N^{(2)}+\sum_{a}N_{a}B_{a}=\\\
&-2^{k}N^{(3)}+\sum_{a}N_{a}C_{a}=-2^{k}N^{(4)}+\sum_{a}N_{a}D_{a}=-16,\end{split}$
(10)

where $2N^{(i)}$ is the number of filler branes wrapping along the $i$-th
O6-plane. Moreover, these filler branes represent the $USp$ group and carry
the wrapping numbers with one of the O6-planes as shown in Table 2.

Table 2: The wrapping numbers for four O6-planes. Orientifold action | O6-Plane | $(n^{1},l^{1})\times(n^{2},l^{2})\times(n^{3},l^{3})$
---|---|---
$\Omega R$ | 1 | $(2^{\beta_{1}},0)\times(2^{\beta_{2}},0)\times(2^{\beta_{3}},0)$
$\Omega R\omega$ | 2 | $(2^{\beta_{1}},0)\times(0,-2^{\beta_{2}})\times(0,2^{\beta_{3}})$
$\Omega R\theta\omega$ | 3 | $(0,-2^{\beta_{1}})\times(2^{\beta_{2}},0)\times(0,2^{\beta_{3}})$
$\Omega R\theta$ | 4 | $(0,-2^{\beta_{1}})\times(0,2^{\beta_{2}})\times(2^{\beta_{3}},0)$

Furthermore, the four-dimensional $N=1$ supersymmetry can be preserved with
the orientation projection iff the rotation angle of any D6-brane with respect
to the orientifold plane is an element of $SU(3)$, as shown in bdl . It
follows that $\theta_{1}+\theta_{2}+\theta_{3}=0$ mod $2\pi$, where
$\theta_{i}$ is the angle between the $D6$-brane and the orientifold-plane in
the $i$-th two-torus. The 4-dimensional N = 1 supersymmetry automatically
survive the $\mathbb{Z}_{2}\times\mathbb{Z}_{2}$ orbifold projection CPS , and
the SUSY conditions result in the equality and inequality conditions

$\begin{split}x_{A}\tilde{A}_{a}+x_{B}\tilde{B}_{a}+x_{C}\tilde{C}_{a}+x_{D}\tilde{D}_{a}=0,\\\
A_{a}/x_{A}+B_{a}/x_{B}+C_{a}/x_{C}+D_{a}/x_{D}<0,\end{split}$ (11)

where $x_{A}=\lambda$, $x_{B}=\lambda\leavevmode\nobreak\ 2^{\beta_{2}+\beta
3}/\chi_{2}\chi_{3}$, $x_{C}=\lambda 2^{\beta_{1}+\beta 3}/\chi_{1}\chi_{3},$
$x_{D}=\lambda 2^{\beta_{1}+\beta 2}/\chi_{1}\chi_{2}$, while
$\chi_{i}=R^{2}_{i}/R^{1}_{i}$ represent the complex structure moduli for the
$i$-th two-torus. The positive parameter $\lambda$ is introduced to put all
the variables $A,\,B,\,C,\,D$ at equal footing.

##  3 Search Method for Supersymmetric Pati-Salam Models

From a mathematical point of view, the search for wrapping numbers satisfying
all the conditions described in the last section is equivalent to solving a
Diophantine equation. In general, there does not exist any algorithm to solve
such equation, as implied by the negative solution of Hilbert’s tenth problem.
However, we devise an algorithm specially adapted to the form of our equations
for Supersymmetric Pati-Salam Models Li:2021-2 .

Now we describe the main strategy of our algorithm. First step: we enumerate
all the possible combinations of the signs of the twelve wrapping number
products $A_{a},B_{a},\dotsc,C_{c},D_{c}$. As observed previously in CPS ,
because of the SUSY condition, $(A_{a},B_{a},C_{a},D_{a})$ contains three
negative numbers and one positive number, or two negative numbers and two
zeroes, or with one negative and three zeros. The same applies to the stack
$b$ and the stack $c$.

Second step: for each possibility listed in the first step, we append the
twelve corresponding inequalities to the our system and try to solve the new
system. Inside the system, we look for the following kinds of equations or
subsystems

  1. 1.

Equation with only one non constant monome.

  2. 2.

A system of linear equations of full rank.

  3. 3.

A system of linear inequalities which has finitely many integer solutions.

When we find inside our system equations or subsystems of these kinds, we can
solve them with respect to the variables appearing in them. After the
resolution, the total number of unknown variables decreases. This might lead
to branching into subcases because the solution might not be unique. But there
are only finitely many subcases because we specifically looked for subsystems
admitting finite integer solution sets. Then, we repeat the procedure for each
subcase.

Third step: we repeat the procedure described in the second step until there
are no subsystem of the three kinds. At this stage, each subcase either gives
a solution or still has some unsolved varialbles (wrapping numbers). Now we
make use of inequalities of degree larger than 1, such as those given by
Eq.(11). By enumerating all the possible signs of the remaining variables, we
can determine whether Eq.(11) can be achieved.

Implementing this algorithm with the help of a computer program, we find that
in total there are $202752$ models. Because each equivalent class has 6144
models, we obtain that there are only 33 independent models with different
gauge coupling relations at string scale after moduloing the equivalent
relations. Thus, for the string landscape study, it is very important to
consider the equivalent relations.

##  4  Supersymmetric Pati-Salam Models

As presented with details in Li:2021-2 , the full list of supersymmetric Pati-
Salam models have $33$ different gauge coupling relations.

First, there is one and only one inequivalent model with gauge coupling
unification, i.e., the strong, weak and hypercharge gauge couplings
$g^{2}_{a},g^{2}_{b}$ and $\frac{5}{3}g^{2}_{Y}$ satisfy
$g^{2}_{a}=g^{2}_{b}=g^{2}_{c}=(\frac{5}{3}g^{2}_{Y})=4\sqrt{\frac{2}{3}}\pi
e^{\phi^{4}}$, where $\phi^{4}$ is the dilaton field. Also, there are four
confining $USp(2)$ gauge groups, and then we might stabilize the moduli and
break SUSY via gaugino condensation.

Second, let us present three representative models for the following
discussions of gauge coupling relations at string scale in the next Section:
Model 1 in Table 3 is a representative model with gauge coupling unification
at string scale; Model 2 in Table 4 and Model 3 in Table 5 are two kinds of
models with the largest possible wrapping number 5, which are related to each
other by exchanging $b-$ an $c-$stacks of D6-branes up to equivalent
relations. The gauge symmetry groups in Model 1 has four $USp(2)$ groups with
negative $\beta$ functions, so their moduli may be stabilized and
supersymmetry might be broken via gaugino condensations. However, Models 2 and
3 contain two $USp(2)$ groups, and only one $USp(2)$ group has negative
$\beta$ function.

In Model 1, similar to Chen:2007px , the additional exotic particles can be
decoupled. In Models 2 and 3, similar to Chen:2007px , we can decouple the
additional exotic particles except the four chiral multiplets under
$SU(4)_{C}$ anti-symmetric representation. And these four chiral multiplets
can be decoupled via instanton effects in principle Blumenhagen:2006xt ;
Haack:2006cy ; Florea:2006si , which we will discuss in Li:2021-3 .

Table 3: D6-brane configurations and intersection numbers of Model 1, and its gauge coupling relation is $g^{2}_{a}=g^{2}_{b}=g^{2}_{c}=(\frac{5}{3}g^{2}_{Y})=4\sqrt{\frac{2}{3}}\pi e^{\phi^{4}}$. Model 1 | $U(4)\times U(2)_{L}\times U(2)_{R}\times USp(2)^{4}$
---|---
stack | $N$ | $(n^{1},l^{1})\times(n^{2},l^{2})\times(n^{3},l^{3})$ | $n_{S}$ | $n_{A}$ | $b$ | $b^{\prime}$ | $c$ | $c^{\prime}$ | 1 | 2 | 3 | 4
$a$ | 8 | $(1,1)\times(1,0)\times(1,-1)$ | 0 | 0 | 3 | 0 | 0 | -3 | 0 | 1 | 0 | -1
$b$ | 4 | $(-1,0)\times(-1,3)\times(1,1)$ | 2 | -2 | - | - | 0 | 0 | 0 | 0 | -3 | 1
$c$ | 4 | $(0,1)\times(-1,3)\times(-1,1)$ | 2 | -2 | - | - | - | - | -3 | 1 | 0 | 0
1 | 2 | $(1,0)\times(1,0)\times(2,0)$ | $x_{A}=\frac{1}{3}x_{B}=x_{C}=\frac{1}{3}x_{D}$
2 | 2 | $(1,0)\times(0,-1)\times(0,2)$ | $\beta^{g}_{1}=\beta^{g}_{2}=\beta^{g}_{3}=\beta^{g}_{4}=-3$
3 | 2 | $(0,-1)\times(1,0)\times(0,2)$ |  $\chi_{1}=1$, $\chi_{2}=\frac{1}{3}$, $\chi_{3}=2$
4 | 2 | $(0,-1)\times(0,1)\times(2,0)$ |
Table 4: D6-brane configurations and intersection numbers of Model 2, and its gauge coupling relation is $g^{2}_{a}=\frac{7}{6}g^{2}_{b}=\frac{5}{6}g^{2}_{c}=\frac{25}{28}(\frac{5}{3}g^{2}_{Y})=\frac{8}{27}5^{3/4}\sqrt{7}\pi e^{\phi^{4}}$. Model 2 | $U(4)\times U(2)_{L}\times U(2)_{R}\times USp(2)^{2}$
---|---
stack | $N$ | $(n^{1},l^{1})\times(n^{2},l^{2})\times(n^{3},l^{3})$ | $n_{S}$ | $n_{A}$ | $b$ | $b^{\prime}$ | $c$ | $c^{\prime}$ | 1 | 4
$a$ | 8 | $(1,-1)\times(-1,1)\times(1,-1)$ | 0 | 4 | 0 | 3 | 0 | -3 | -1 | 1
$b$ | 4 | $(0,1)\times(-2,1)\times(-1,1)$ | -1 | 1 | - | - | 0 | -1 | -1 | 0
$c$ | 4 | $(-1,0)\times(5,2)\times(-1,1)$ | 3 | -3 | - | - | - | - | 0 | -5
1 | 2 | $(1,0)\times(1,0)\times(2,0)$ | $x_{A}=2x_{B}=\frac{14}{5}x_{C}=7x_{D}$
4 | 2 | $(0,-1)\times(0,1)\times(2,0)$ |  $\beta^{g}_{1}=-3$, $\beta^{g}_{4}=1$
|  |  |  $\chi_{1}=\frac{7}{\sqrt{5}}$, $\chi_{2}=\sqrt{5}$, $\chi_{3}=\frac{4}{\sqrt{5}}$
Table 5: D6-brane configurations and intersection numbers of Model 3, and its gauge coupling relation is $g^{2}_{a}=\frac{5}{6}g^{2}_{b}=\frac{7}{6}g^{2}_{c}=\frac{35}{32}(\frac{5}{3}g^{2}_{Y})=\frac{8}{27}5^{3/4}\sqrt{7}\pi e^{\phi^{4}}$. Model 3 | $U(4)\times U(2)_{L}\times U(2)_{R}\times USp(2)^{2}$
---|---
stack | $N$ | $(n^{1},l^{1})\times(n^{2},l^{2})\times(n^{3},l^{3})$ | $n_{S}$ | $n_{A}$ | $b$ | $b^{\prime}$ | $c$ | $c^{\prime}$ | 1 | 4
$a$ | 8 | $(-1,-1)\times(1,1)\times(1,1)$ | 0 | -4 | 0 | 3 | 0 | -3 | 1 | -1
$b$ | 4 | $(-5,2)\times(-1,0)\times(1,1)$ | -3 | 3 | - | - | 0 | 1 | 0 | 5
$c$ | 4 | $(-2,-1)\times(0,1)\times(1,1)$ | 1 | -1 | - | - | - | - | 1 | 0
1 | 2 | $(1,0)\times(1,0)\times(2,0)$ | $x_{A}=\frac{14}{5}x_{B}=2x_{C}=7x_{D}$
4 | 2 | $(0,-1)\times(0,1)\times(2,0)$ |  $\beta^{g}_{1}=-3$, $\beta^{g}_{4}=1$
|  |  |  $\chi_{1}=\sqrt{5}$, $\chi_{2}=\frac{7}{\sqrt{5}}$, $\chi_{3}=\frac{4}{\sqrt{5}}$

##  5 String-scale Gauge Coupling Unification

Once we obtain the full list of supersymmetric Pati-Salam models, we can
discuss the gauge coupling relations at the string scale. As shown in Table 3,
Model 1 has exact gauge coupling unification at GUT scale from brane
construction, while the other models do not.

Using the current precision electroweak data and setting $M_{\text{SUSY}}=3$
TeV, we study the gauge coupling relations at string scale (around $5\times
10^{17}$ GeV ) by solving two-loop renormalization group equations (RGEs)
Barger:2005qy ; Barger:2007qb , i.e., $M_{U}\simeq M_{\text{string}}$. The
generic gauge coupling relations at string scale for intersecting D6-brane
models can be written as
$g_{a}^{2}=k_{2}\,g_{b}^{2}=k_{Y}\,g_{Y}^{2}=g_{U}^{2}$, where $k_{Y}$ and
$k_{2}$ are constants for each model. For simplicity, we call these gauge
coupling relations as gauge coupling unification by redefining
$\alpha_{1}\equiv k_{Y}g_{Y}^{2}/4\pi$, $\alpha_{2}\equiv
k_{2}g_{b}^{2}/4\pi$, and $\alpha_{3}\equiv g_{a}^{2}/4\pi$. To define the
unification scale, we choose the evolution under the conditions
$\alpha_{U}^{-1}\equiv\alpha_{1}^{-1}=(\alpha_{2}^{-1}+\alpha_{3}^{-1})/2$ and
$\Delta=|\alpha_{1}^{-1}-\alpha_{2}^{-1}|/\alpha_{1}^{-1}$ as in Refs.
Chen:2017rpn ; Chen:2018ucf . In our study, the difference between
$\alpha_{\text{string}}^{-1}$ and $\alpha_{2}^{-1}$ or $\alpha_{3}^{-1}$ is
limited to be less than $1.0\%$.

For Model 1, the canonical hypercharge normalization $k_{Y}=5/3$ and
$k_{2}=1$. Utilizing two-loop RGEs method, we obtain that the gauge coupling
unification can be achieved at $1.39\times 10^{16}$ GeV which is just the
supersymmetric GUT scale value as shown in Fig.1. Note that this unification
scale is about one order magnitude smaller than string scale $5\times 10^{17}$
GeV.

Figure 1: Gauge coupling unification at $1.39\times 10^{16}$ GeV in Model 1

In Blumenhagen:2003jy , it was presented that additional vector-like matter
can push the unification at GUT scale up to Planck scale for $SU(5)$ and
$SO(10)$ GUT theories. Instead of studying pushing up the unification scale
with additional vector-like matter, we will study the feature while
introducing vector like particle to the models without GUT scale unification,
such as Model 2 and 3. To achieve canonical gauge coupling unification, we
first introduce the vector-like particles whose quantum numbers are the same
as those of the SM fermions and their Hermitian conjugate, see Barger:2007qb
and references therein. Their quantum numbers under $SU(3)_{C}\times
SU(2)_{L}\times U(1)_{Y}$ and their contributions to one-loop beta functions,
$\Delta b\equiv(\Delta b_{1},\Delta b_{2},\Delta b_{3})$ as complete
supermultiplets are

$\displaystyle XQ+{\overline{XQ}}={\mathbf{(3,2,{1\over
6})+({\bar{3}},2,-{1\over 6})}}\,,\quad\Delta b=({1\over 5},3,2)\,;$ (12)
$\displaystyle XU+{\overline{XU}}={\mathbf{({3},1,{2\over
3})+({\bar{3}},1,-{2\over 3})}}\,,\quad\Delta b=({8\over 5},0,1)\,;$ (13)
$\displaystyle XD+{\overline{XD}}={\mathbf{({3},1,-{1\over
3})+({\bar{3}},1,{1\over 3})}}\,,\quad\Delta b=({2\over 5},0,1)\,;$ (14)
$\displaystyle XL+{\overline{XL}}={\mathbf{(1,2,{1\over 2})+({1},2,-{1\over
2})}}\,,\quad\Delta b=({3\over 5},1,0)\,;$ (15) $\displaystyle
XE+{\overline{XE}}={\mathbf{({1},1,{1})+({1},1,-{1})}}\,,\quad\Delta
b=({6\over 5},0,0)\,;$ (16) $\displaystyle
XG={\mathbf{({8},1,0)}}\,,\quad\Delta b=(0,0,3)\,;$ (17) $\displaystyle
XW={\mathbf{({1},3,0)}}\,,\quad\Delta b=(0,2,0)\,;$ (18) $\displaystyle
XT+{\overline{XT}}={\mathbf{(1,3,1)+(1,3,-1)}}\,,\quad\Delta b=({{18}\over
5},4,0)\,;$ (19) $\displaystyle XS+{\overline{XS}}={\mathbf{(6,1,-{2\over
3})+({\bar{6}},1,{2\over 3})}}\,,\quad\Delta b=({16\over 5},0,5)\,;$ (20)
$\displaystyle XY+{\overline{XY}}={\mathbf{(3,2,-{5\over
6})+({\bar{3}},2,{5\over 6})}}\,,\quad\Delta b=(5,3,2)\,.\,$ (21)

For Models 2 as shown in Table 4, the gauge coupling relation at GUT scale is
$g^{2}_{a}=\frac{7}{6}\,g^{2}_{b}=\frac{5}{6}\,g^{2}_{c}=\frac{25}{28}\,(\frac{5}{3}g^{2}_{Y})=\frac{8}{27}\,5^{3/4}\sqrt{7}\pi
e^{\phi^{4}}$, without gauge coupling unification from brane construction. By
introducing additional pairs vector-like particles ($XD$, $\overline{XD}$) for
Model 2 with $k_{Y}=125/84,\leavevmode\nobreak\ k_{2}=7/6$ with $\Delta
b=({2\over 5},0,1)$, it would be possible to “bend” the values of
$\alpha_{1}^{-1},\alpha_{3}^{-1}$ to achieve gauge coupling as shown in Figure
2. Here the number of additional particles is important as it determines the
slope of bending and, as follows, the energy scale of the gauge unification.
We speculate the number given by brane intersection might lead to string scale
gauge coupling unification. Recall the quantum numbers of ($XD$,
$\overline{XD}$) under $SU(3)_{C}\times SU(2)_{L}\times U(1)_{Y}$ are
$XD=(3,1,-1/3)$, $\overline{XD}=(\bar{3},1,1/3)$. It is obvious that these
vector-like particles arise from $a$ and $c$ stack of brane intersection,
representing $SU(3)_{C}$ and $U(1)_{Y}$ respectively.

Read off the wrapping numbers $(n_{x}^{i},l_{x}^{i})$ for $a$ and $c$ stack of
the from Table 4, we note that $(n_{a}^{3},l_{a}^{3})$ and
$(n_{c}^{3},l_{c}^{3})$ has the same value yet with opposite sign. This
indicates the D6-branes wrapping on the third torus are parallel to each
other. Therefore there is no intersection on the third torus, but only on the
first and second torus. Following Eq. (2), we have intersection number
$I_{ac}=2^{-k}\prod_{i=1}^{2}(n_{a}^{i}\,l_{c}^{i}-n_{c}^{i}\,l_{a}^{i})=7$.
This indicates there are $7$ number of such vector-like particles naturally
arise from brane construction. By introducing $7$ pairs of vector-like
particle ($XD$, $\overline{XD}$) for Model 2 with
$k_{Y}=125/84,\leavevmode\nobreak\ k_{2}=7/6$, via two-loop RGEs method, we
indeed obtain string scale gauge coupling unification at around $7.22\times
10^{17}$ GeV presented in Figure 2.

Figure 2: Gauge coupling unification at $7.22\times 10^{17}$ GeV in Model 2

For Models 3 as shown in Table 5, the gauge coupling relation at GUT scale is
$g^{2}_{a}=\frac{5}{6}\,g^{2}_{b}=\frac{7}{6}\,g^{2}_{c}=\frac{35}{32}\,(\frac{5}{3}g^{2}_{Y})=\frac{8}{27}\,5^{3/4}\,\sqrt{7}\pi
e^{\phi^{4}}$, again without gauge coupling unification from brane
construction. Similar as for Model 2, we find vector-like particle ($XQ$,
$\overline{XQ}$) with quantum number $XQ=(3,2,1/6)$ and
$\overline{XQ}=(\bar{3},2,-1/6)$ are nature candidate to realize string scale
gauge coupling unification. These particles are realized from $a$ and $b$
stacks of brane intersection, with intersection number
$I_{ab}=2^{-k}\prod_{i=1}^{2}(n_{a}^{i}\,l_{b}^{i}-n_{b}^{i}\,l_{a}^{i})=7$.

Thus, by introducing $7$ pairs of vector-like particle ($XQ$, $\overline{XQ}$)
in Model 3 with $k_{Y}=175/96,\leavevmode\nobreak\ k_{2}=5/6$, we achieve
gauge coupling unification at around string scale $1.09\times 10^{17}$ GeV,
which we show in Figure 3.

Figure 3: Gauge coupling unification at $1.09\times 10^{17}$ GeV in Model 3

The masses of the extra vector-like particles for Model 2 and Model 3 are also
presented in Figure 2 and Figure 3, respectively. The right-side kinked points
on the plots indicate masses of the extra vector-like particles on the
$x$-axis.

One may ask the reason why only these type of vector-like particle are turned
on, but not the other type of vector-like particles. This is realized by
setting the minimal distance squared $Z^{2}_{(ac^{\prime})}$ (in $1/M_{s}$
units) between parallel D6-branes along the third torus is small, i.e., the
minimal length squared of the stretched string is small. Therefore, we have
the light scalars with squared-masses
$Z^{2}_{(ab^{\prime})}/(4\pi^{2}\alpha^{\prime})$ from the NS sector, and the
light fermions with the same masses from the R sector Uranga ; imr . These
scalars and fermions form the 4-dimensional $N=2$ hypermultiplets, so, _e.g._
for Model 2 we obtain the $I_{ac}$ (the intersection numbers for $a$ and $c$
stacks on the first two two-tori) vector-pairs of ($XD$, $\overline{XD}$)
under $SU(3)_{C}\times SU(2)_{L}\times U(1)_{Y}$ with quantum number
$XD=(3,1,-1/3)$, $\overline{XD}=(\bar{3},1,1/3)$. This setting applies to
Model 3 with ${\cal N}=2$ vector-like particles ($XQ$, $\overline{XQ}$) also.

##  6 Conclusions

In Li:2021-2 , we obtain all the three-family ${\cal N}=1$ supersymmetric
Pati-Salam models from intersecting D6-branes through systematic method. The
gauge symmetry can be broken down to the SM via the D6-brane splitting and
supersymmetry preserving Higgs mechanism. There are only 33 independent models
with different gauge coupling relations at string scale in total after modding
out the equivalent relations. In particular, one and only one model has
natural gauge coupling unification at GUT scale through brane construction.

In this paper, we study the gauge coupling unification at string scale for the
models without direct gauge unification at GUT scale from brane construction.
Taking models with approximate gauge coupling unification at GUT scale as
example, we showed that gauge coupling unification can be realized at string
scale by introducing pairs of vector-like particles from ${\cal N}=2$ sector.
In particular, to achieve the gauge unification as string scale, we propose
that the number of these introduced vector-like particles are fully determined
by the brane intersection numbers while there are two D6-brane parallel to
each other along one two-torus. Intriguingly, with two-loop RGEs method, we
explicitly showed for Model 2 and 3 that gauge coupling unified at string-
scale $10^{17}$ GeV by introducing $7$ pairs vector-like particles ($XD$,
$\overline{XD}$) and ($XQ$, $\overline{XQ}$) with their masses given
respectively.

We expect that by introducing pairs of vector-like particles from ${\cal N}=2$
sector for intersecting brane models, gauge coupling unification at string
scale can be achieved for generic D-brane models. In particular, the number of
vector-like particles are fully determined by brane intersection numbers.

###### Acknowledgements.

TL is supported by the National Key Research and Development Program of China
Grant No. 2020YFC2201504, as well as by the Projects No. 11875062 and No.
11947302 supported by the National Natural Science Foundation of China. WH is
supported by KIAS Individual Grant MG080401. RS is supported by KIAS
Individual Grant PG080701. LW is supported by Projects 2020JQ-804 from the
Natural Science Basic Research Plan in Shaanxi Province of China and 20JK0685
from Shaanxi Provincial Education Department.

## References

  * (1) J. Lykken, E. Poppitz and S. P. Trivedi, Nucl. Phys. B 543, 105 (1999).
  * (2) C. Angelantonj, I. Antoniadis, E. Dudas and A. Sagnotti, Phys. Lett. B 489 (2000) 223.
  * (3) M. Cvetič, M. Plümacher and J. Wang, JHEP 0004, 004 (2000); M. Cvetič, A. M. Uranga and J. Wang, Nucl. Phys. B 595, 63 (2001).
  * (4) G. Aldazabal, A. Font, L. E. Ibáñez and G. Violero, Nucl. Phys. B 536, 29 (1998); G. Aldazabal, L. E. Ibáñez, F. Quevedo and A. M. Uranga, JHEP 0008, 002 (2000).
  * (5) M. Klein and R. Rabadan, JHEP 0010, 049 (2000).
  * (6) J. F. G. Cascales and A. M. Uranga, hep-th/0311250.
  * (7) G. Aldazabal, S. Franco, L. E. Ibáñez, R. Rabadán and A. M. Uranga, JHEP 0102, 047 (2001).
  * (8) G. Aldazabal, S. Franco, L. E. Ibáñez, R. Rabadan and A. M. Uranga, J. Math. Phys. 42, 3103 (2001).
  * (9) L. E. Ibáñez, F. Marchesano and R. Rabadán, JHEP 0111, 002 (2001).
  * (10) R. Blumenhagen, L. Görlich, B. Körs and D. Lüst, JHEP 0010, 006 (2000).
  * (11) R. Blumenhagen, B. Körs and D. Lüst, JHEP 0102, 030 (2001).
  * (12) M. Cvetič, G. Shiu and A. M. Uranga, Nucl. Phys. B 615, 3 (2001).
  * (13) R. Blumenhagen, D. Lüst, S. Stieberger, JHEP 07, 036 (2003).
  * (14) M. Cvetič, I. Papadimitriou and G. Shiu, Nucl. Phys. B 659, 193 (2003) Erratum: [Nucl. Phys. B 696, 298 (2004)].
  * (15) M. Cvetič, T. Li and T. Liu, Nucl. Phys. B 698, 163 (2004).
  * (16) R. Blumenhagen, M. Cvetic, P. Langacker and G. Shiu, Ann. Rev. Nucl. Part. Sci. 55, 71 (2005).
  * (17) R. Blumenhagen, B. Kors, D. Lüst, S. Stieberger, Phys. Rept. 445, 1-193 (2007).
  * (18) M. Cvetič, P. Langacker and J. Wang, Phys. Rev. D 68, 046002 (2003).
  * (19) R. Blumenhagen, L. Gorlich and T. Ott, JHEP 0301, 021 (2003).
  * (20) G. Honecker, Nucl. Phys. B 666, 175 (2003).
  * (21) M. Cvetič, P. Langacker, T. Li and T. Liu, Nucl. Phys. B 709, 241 (2005).
  * (22) C. M. Chen, T. Li and D. V. Nanopoulos, Nucl. Phys. B 732, 224 (2006).
  * (23) C. M. Chen, T. Li, V. E. Mayes and D. V. Nanopoulos, Phys. Lett. B 665, 267 (2008).
  * (24) C. M. Chen, T. Li, V. E. Mayes and D. V. Nanopoulos, Phys. Rev. D 77, 125023 (2008).
  * (25) T. Li, A. Mansha and R. Sun, EPJC 81, 82 (2021).
  * (26) T. Li, A. Mansha, R. Sun, L. Wu, and W. He, Phys.Rev.D 104, 046018 (2021).
  * (27) J. Halverson, B. Nelson, and F. Ruehle, JHEP 06, 003 (2019).
  * (28) G. J. Loges, G. Shiu, Fortschritte der Physik 2022, 2200038, arXiv: 2112.08391[hep-th].
  * (29) M. Sabir, T. Li, A. Mansha, and X. C. Wang, in preparation.
  * (30) T. Li, R. Sun, and W. He, arXiv: 2112.09632 [hep-th].
  * (31) T. Li, R. Sun, and L. Wu, in preparation.
  * (32) M. Berkooz, M. R. Douglas and R. G. Leigh, Nucl. Phys. B 480, 265 (1996).
  * (33) R. Blumenhagen, M. Cvetic and T. Weigand, Nucl. Phys. B 771, 113 (2007).
  * (34) M. Haack, D. Krefl, D. Lust, A. Van Proeyen and M. Zagermann, JHEP 01, 078 (2007).
  * (35) B. Florea, S. Kachru, J. McGreevy and N. Saulina, JHEP 05, 024 (2007).
  * (36) V. Barger, J. Jiang, P. Langacker and T. Li, Nucl. Phys. B 726, 149 (2005).
  * (37) V. Barger, N. G. Deshpande, J. Jiang, P. Langacker and T. Li, Nucl. Phys. B 793, 307 (2008).
  * (38) H. Y. Chen, I. Gogoladze, S. Hu, T. Li and L. Wu, Eur. Phys. J. C 78, 26 (2018).
  * (39) H. Y. Chen, I. Gogoladze, S. Hu, T. Li and L. Wu, Int. J. Mod. Phys. A 35, 2050117 (2020).


# Tree Edit Distance Learning via Adaptive Symbol Embeddings

Benjamin Paaßen  Claudio Gallicchio  Alessio Micheli  Barbara Hammer

###### Abstract

Metric learning has the aim to improve classification accuracy by learning a
distance measure which brings data points from the same class closer together
and pushes data points from different classes further apart. Recent research
has demonstrated that metric learning approaches can also be applied to trees,
such as molecular structures, abstract syntax trees of computer programs, or
syntax trees of natural language, by learning the cost function of an edit
distance, i.e. the costs of replacing, deleting, or inserting nodes in a tree.
However, learning such costs directly may yield an edit distance which
violates metric axioms, is challenging to interpret, and may not generalize
well. In this contribution, we propose a novel metric learning approach for
trees which we call embedding edit distance learning (BEDL) and which learns
an edit distance indirectly by embedding the tree nodes as vectors, such that
the Euclidean distance between those vectors supports class discrimination. We
learn such embeddings by reducing the distance to prototypical trees from the
same class and increasing the distance to prototypical trees from different
classes. In our experiments, we show that BEDL improves upon the state-of-the-
art in metric learning for trees on six benchmark data sets, ranging from
computer science over biomedical data to a natural-language processing data
set containing over 300,000 nodes.

metric learning, trees, structured data, symbol embeddings, learning vector
quantization

##  1 Introduction

Many classification approaches in machine learning explicitly or implicitly
rely on some measure of _distance_ (Kulis, 2013; Bellet et al., 2014; Mokbel
et al., 2015). This is particularly apparent in case of the $k$-nearest
neighbor classifier which classifies data points by assigning the label of the
majority of the $k$ _nearest neighbors_ according to a given distance (Cover &
Hart, 1967); or in case of _learning vector quantization_ approaches which
classify data points by assigning the label of the closest prototype according
to a given distance (Kohonen, 1995). The success of such machine learning
approaches hinges on the distance being _discriminative_ , that is, data
points from the same class being generally closer compared to data points from
different classes. If the distance does not fulfill this criterion, one has to
_adapt_ or _learn_ the distance measure with respect to the data, which is the
topic of _metric learning_ (Kulis, 2013; Bellet et al., 2014).

Most prior research in metric learning has focused on learning a
generalization of the Euclidean distance according to some cost function
(Kulis, 2013; Bellet et al., 2014). However, the Euclidean distance is not
applicable to non-vectorial data, such as protein sequences, abstract syntax
trees of computer programs, or syntax trees of natural language. To process
these kinds of data, _edit distances_ are a popular option, in particular the
tree edit distance (Zhang & Shasha, 1989). In this contribution, we develop a
novel metric learning scheme for the tree edit distance which we call
embedding edit distance learning (BEDL).

While past research on metric learning for trees does exist (Bellet et al.,
2014), BEDL goes beyond the state-of-the-art in multiple aspects:

  * •

Based on the work of Bellet et al. (2012), we provide a generalized re-
formulation of the edit distance which lends itself to metric learning, and
can be applied to any kind of edit distance which uses replacement, deletion,
and insertion operations. Furthermore, we consider not only _one_ optimal edit
script for metric learning, but _all_ co-optimal edit scripts via a novel
forward-backward algorithm.

  * •

Our approach requires only a linear number of data tuples for metric learning,
as we represent classes by few _prototypes_ , which are selected via median
learning vector quantization (Nebel et al., 2015).

  * •

Most importantly, we do not directly learn the operation costs for the string
edit distance, but instead learn a vectorial embedding of the label alphabet
for our data structures, which yields Euclidean operation costs. This re-
formulation ensures that the resulting edit distance conforms to all metric
axioms. Further, we can interpret the resulting embedding vectors via
visualization, their pairwise distances and norms.

We begin by discussing related work, then we describe BEDL in more detail, and
finally we evaluate BEDL experimentally and discuss the results.

##  2 Related Work

Our work is related to multiple areas of machine learning, most notably
distances on structured data, metric learning, and vector embeddings.

In the past decades, multiple distance measures for structured data - i.e.
sequences, trees, and graphs - have been suggested. In particular, one could
define a distance based on existing string, tree, and graph kernels (Da San
Martino & Sperduti, 2010), such as Weisfeiler-Lehman Graph Kernels
(Shervashidze et al., 2011), topological distance-based tree kernels (Aiolli
et al., 2015), or deep graph kernels (Yanardag & Vishwanathan, 2015). Such
kernels achieve state-of-the-art results on structured data and can be adapted
to training data via multiple-kernel learning (Aiolli & Donini, 2015), or
kernels based on Hidden-Markov-Model states (Bacciu et al., 2018). Kernels,
however, have drawbacks in terms of interpretability, as a higher distance
value does not necessarily relate to any kind of intuitive difference between
the input trees. Further, kernel matrices are by definition limited to be
positive semi-definite, which may be an undue restriction for certain data
sets (Schleif & Tino, 2015).

If one strives for an interpretable measure of distance, _edit distances_ are
a popular choice, for example for the comparison of protein sequences in
bioinformatics (Smith & Waterman, 1981), or abstract syntax trees for
intelligent tutoring systems (Paaßen et al., 2018). Here, we focus on the tree
edit distance, which permits deletions, insertions, and replacements of single
nodes to transform an ordered tree $\bar{x}$ into another ordered tree
$\bar{y}$ (Zhang & Shasha, 1989). Such ordered trees are the most general data
structures which can still be treated efficiently via edit distances, as edit
distances on unordered trees and general graphs are provably NP-hard (Zhang et
al., 1992; Zeng et al., 2009). Furthermore, the tree edit distance includes
the edit distance on sequences as a special case, such that it can be seen as
a representative for edit distances as such.

Metric learning for the tree edit distance corresponds to adapting the costs
of edit operations in order to bring trees from the same class closer and push
trees from different classes further apart. Almost all of the existing
approaches, however, only bring trees from the same class closer together
(Bellet et al., 2014). For example, Boyer et al. (2007) have proposed to
replace the tree edit distance by the negative log probability of all tree
edit scripts which transform the left input tree $\bar{x}$ into the right
input tree $\bar{y}$. Accordingly, the costs of edit operations change to
probabilities of replacing, deleting, or inserting a certain label. These edit
probabilities are adapted to maximize the probability that trees from the same
class are edited into each other (Boyer et al., 2007). To replace generative
models by discriminative ones, Bellet et al. (2012, 2016), have proposed to
learn an edit distance $d$, such that the corresponding similarity
$2\cdot\exp[-d(\bar{x},\bar{y})]-1$ is “good” as defined by the goodness-
framework of (Balcan et al., 2008). Goodness according to this framework means
that a linear separator with low error between the classes exists in the space
of similarities (Balcan et al., 2008; Bellet et al., 2012). Bellet et al.
(2012) have experimentally shown that this approach outperforms generative
edit distance metric learning and have also established generalization
guarantees based on the goodness framework. Therefore, this _good edit
similarity learning_ (GESL) approach of Bellet et al. (2012) is our main
reference method.

Our novel approach is strongly inspired by GESL. However, our approach goes
beyond GESL in key aspects. First, we utilize a different cost function,
namely the generalized learning vector quantization (GLVQ) cost function,
which quantifies how much closer every data point is to the closest
prototypical example from the same class compared to the closest prototypical
example from another class (Sato & Yamada, 1995). Just as GESL, LVQ methods
are theoretically well-justified because it yields a maximum-margin classifier
(Schneider et al., 2009), and have been successfully applied for metric
learning on the string edit distance in the past (Mokbel et al., 2015; Paaßen
et al., 2016). However, in contrast to GESL, GLVQ also provides a principled
way to select prototypical examples for metric learning, and is flexible
enough to not only learn a cost matrix, but also a vectorial embedding of the
tree labels, such that the Euclidean distance on these embeddings provides a
discriminative cost function.

While embedding approaches are common in the literature, prior work has
focused mostly on embedding trees _as a whole_ , for example via graph kernel
approaches (Aiolli et al., 2015; Bacciu et al., 2018; Da San Martino &
Sperduti, 2010; Shervashidze et al., 2011; Yanardag & Vishwanathan, 2015),
recursive neural networks (Gallicchio & Micheli, 2013; Hammer et al., 2007;
Socher et al., 2013), or dimensionality reduction approaches (Gisbrecht et
al., 2015). In this contribution, we wish to obtain an embedding for the
single elements of a tree and maintain the tree structure. As of yet, such
approaches only exist for sequences, namely in the form of recurrent neural
network for natural language processing tasks (Cho et al., 2014; Sutskever et
al., 2014). In addition to word embeddings for trees, our approach also
provides a corresponding tree edit distance, which is optimized for
classification, and offers an intuitive view on the data, supporting
applications like intelligent tutoring systems (Paaßen et al., 2018).

##  3 Background

In this section, we revisit the basic problem of tree edit distance learning
by first introducing the tree edit distance of Zhang & Shasha (1989), as well
as the metric learning formalization suggested by Bellet et al. (2012).

###  3.1 Tree Edit Distance

We define a tree $\bar{x}$ over some set $\mathcal{X}$ as
$x(\bar{x}_{1},\ldots,\bar{x}_{R})$ where $x\in\mathcal{X}$ and
$\bar{x}_{1},\ldots,\bar{x}_{R}$ is a (potentially empty) list of trees over
$\mathcal{X}$. We denote the set of all possible trees over $\mathcal{X}$ as
$\mathcal{T}(\mathcal{X})$. Further, we call $x$ the _label_ of the tree. We
define the _size_ of a tree $x(\bar{x}_{1},\ldots,\bar{x}_{R})$ as
$|\bar{x}|:=1+\sum_{r=1}^{R}|\bar{x}_{r}|$. Finally, we call a list of trees
$\bar{x}_{1},\ldots,\bar{x}_{R}$ a _forest_. Note that every tree is also a
forest.

Next, we introduce _edits_ over trees. In general, a tree edit $\delta$ is a
function which transforms a forest into a forest (Paaßen et al., 2018). In
this particular case, we are only concerned with three kinds of edits, namely
deletions, which remove a certain label from a forest; insertions, which
insert a certain label into a forest; and replacements which remove a certain
label from a forest and put another label in its place. For example, deleting
x from a tree $\text{{x}}(\text{{y}},\text{{z}})$ results in the forest
$\text{{y}},\text{{z}}$. Inserting x into this forest as parent of y results
in the forest $\text{{x}}(\text{{y}}),\text{{z}}$. Finally, replacing z with q
in this forest results in the forest $\text{{x}}(\text{{y}}),\text{{q}}$.

We associate each edit with a _cost_ via a function
$c:(\mathcal{X}\cup\\{-\\})^{2}\to\mathbb{R}$. In particular, we define the
cost of a deletion of label $x$ as $c(x,-)$, the cost of an insertion of label
$y$ as $c(-,y)$, and the cost of a replacement of label $x$ with label $y$ as
$c(x,y)$. We define the cost of a _sequence_ of edits
$\delta_{1},\ldots,\delta_{T}$ as the sum over the costs of all edits.

Finally, we define the tree edit distance $d_{c}(\bar{x},\bar{y})$ between any
two trees $\bar{x}$ and $\bar{y}$ according to $c$ as the cost of the cheapest
sequence of edits that transforms $\bar{x}$ to $\bar{y}$. For example, if all
edits have a cost of $1$, the edit distance
$d_{c}(\text{{x}}(\text{{y}},\text{{z}}),\text{{q}}(\text{{z}}(\text{{q}})))$
between the trees $\text{{x}}(\text{{y}},\text{{z}})$ and
$\text{{q}}(\text{{z}}(\text{{q}}))$ is $3$ because the cheapest sequence of
edits is to replace x with q, delete y, and insert q.

Zhang & Shasha (1989) showed that the tree edit distance can be computed
efficiently using a dynamic programming algorithm if $c$ is a pseudo-metric,
meaning that $c$ is a non-negative and symmetric function, such that
$c(x,x)=0$ for any $x\in\mathcal{X}$, and such that the triangular inequality
is fulfilled.

######  Theorem 1.

Let $c$ be a pseudo-metric on $\mathcal{X}\cup\\{-\\}$. Then, the
corresponding tree edit distance $d_{c}(\bar{x},\bar{y})$ can be computed in
$\mathcal{O}(|\bar{x}|^{2}\cdot|\bar{y}|^{2})$ using a dynamic programming
scheme.

Conversely, if $c$ violates the triangular inequality, the dynamic programming
scheme overestimates the tree edit distance.

###### Proof.

Refer to Zhang & Shasha (1989) for a proof of the first claim, and refer to
the supplementary material (Paaßen, 2018b) for a proof of the second claim. ∎

Beyond enabling us to compute the tree edit distance efficiently, pseudo-
metric cost functions $c$ also ensure that the resulting tree edit distance
$d_{c}$ is a pseudo-metric itself.

######  Theorem 2.

Let $c$ be a pseudo-metric on $\mathcal{X}\cup\\{-\\}$. Then, the
corresponding tree edit distance $d_{c}$ is a pseudo-metric on the set of
possible trees over $\mathcal{X}$.

However, if $c$ violates any of the pseudo-metric properties (except for the
triangular inequality), we can construct examples such that $d_{c}$ violates
the same pseudo-metric properties.

###### Proof.

Refer to the supplementary material (Paaßen, 2018b). ∎

Both of these theorems make a pseudo-metric cost function $c$ desirable.
However, ensuring pseudo-metric properties on $c$ may be challenging in metric
learning, which is one of our key motivations for vectorial embeddings.

###  3.2 Tree Edit Distance Learning

Tree edit distance learning essentially means to adapt the cost function $c$,
such that the resulting tree edit distance $d_{c}$ is better suited for the
task at hand. Following Bellet et al. (2012, 2014), we frame tree edit
distance learning as minimizing some loss function over a set of _positive_
pairs of trees $P\subset\mathcal{T}(\mathcal{X})^{2}$ and _negative_ pairs of
trees $N\subset\mathcal{T}(\mathcal{X})^{2}$, that is, trees which should be
close and far away respectively. In particular, given a loss function $E$ we
wish to solve the optimization problem:

$\min_{c}E(d_{c},P,N)$ (1)

In our contribution, we build upon the _good edit similarity learning_ (GESL)
approach of Bellet et al. (2012), who propose the loss function

$\displaystyle E(d_{c},P,N)=$ $\displaystyle\beta\cdot\lVert
c\rVert^{2}+\sum_{(\bar{x},\bar{y})\in P}[d_{c}(\bar{x},\bar{y})-\eta]_{+}$
(2) $\displaystyle+$ $\displaystyle\sum_{(\bar{x},\bar{y})\in N}[\log(2)+\eta-
d_{c}(\bar{x},\bar{y})]_{+}$

where $[\mu]_{+}=\max\\{0,\mu\\}$ denotes the hinge loss, $\eta\in[0,\log(2)]$
is a slack variable permitting higher distances between positive pairs if
negative pairs are further apart, $\beta$ is a scalar regularization constant,
and $\lVert c\rVert^{2}$ denotes
$\sum_{x\in\mathcal{X}\cup\\{-\\}}\sum_{y\in\mathcal{X}\cup\\{-\\}}c(x,y)^{2}$.
As positive and negative pairs, Bellet et al. (2012) propose to use the $K$
closest neighbors in the same class and the $K$ furthest data points from a
different class respectively, where “closeness” refers to the tree edit
distance obtained via some initial, default cost function $c_{0}$ (Bellet et
al., 2012).

Note that minimizing the loss function 2 is infeasible because changing the
parameters $c$ may change other edit sequences to become the cheapest option
which in turn induces non-differentiable points in the loss function (Mokbel
et al., 2015). Therefore, Bellet et al. (2012) suggest to compute the cheapest
edit scripts according to a default cost function $c_{0}$ and keep them fixed
for the optimization. More precisely, let $\bm{P}_{c_{0}}(\bar{x},\bar{y})$ be
a matrix of size $|\bar{x}|+1\times|\bar{y}|+1$, such that
$\bm{P}_{c_{0}}(\bar{x},\bar{y})_{i,j}$ is $1$ if and only if the cheapest
edit script that transforms $\bar{x}$ to $\bar{y}$ according to the cost
function $c_{0}$ contains a replacement of node $x_{i}$ with node $y_{j}$,
where $x_{i}$ is the $i$th node in tree $\bar{x}$ according to pre-order and
$y_{j}$ is the $j$th node in tree $\bar{y}$ according to pre-order. Further,
if the cheapest edit script deletes $x_{i}$, we define
$\bm{P}_{c_{0}}(\bar{x},\bar{y})_{i,|\bar{y}|+1}=1$ and if the cheapest edit
script inserts $y_{j}$, we define
$\bm{P}_{c_{0}}(\bar{x},\bar{y})_{|\bar{x}|+1,j}=1$. We define all other
entries of $\bm{P}_{c_{0}}(\bar{x},\bar{y})$ as zero. We can compute the
matrix $\bm{P}_{c_{0}}(\bar{x},\bar{y})$ in
$\mathcal{O}(|\bar{x}|^{2}\cdot|\bar{y}|+|\bar{x}|\cdot|\bar{y}|^{2})$ via
backtracing (refer to the supplementary material (Paaßen, 2018a) for details).

Using this matrix, we can define the _pseudo edit distance_
$\tilde{d}_{c}(\bar{x},\bar{y})$, which we define as follows.

$\tilde{d}_{c}(\bar{x},\bar{y})=\sum_{i=1}^{|\bar{x}|+1}\sum_{j=1}^{|\bar{y}|+1}\bm{P}_{c_{0}}(\bar{x},\bar{y})_{i,j}\cdot
c(x_{i},y_{j})$ (3)

where we define $x_{|\bar{x}|+1}=y_{|\bar{y}|+1}:=-$. GESL now minimizes the
loss function 2 with respect to the pseudo-edit distance, which is a quadratic
optimization problem.

Bellet et al. (2012) show that GESL optimizes the “goodness” of the similarity
measure $k(\bar{x},\bar{y})=2\cdot\exp(-\tilde{d}_{c}(\bar{x},\bar{y}))-1$.
The concept of goodness has been introduced by Balcan et al. (2008) and
quantifies how well a given similarity measure lends itself for binary
classification. In particular, assume trees $\bar{x}_{1},\ldots,\bar{x}_{m}$
with class assignments $\ell(\bar{x}_{1}),\ldots,\ell(\bar{x}_{m})$. Then, we
wish to learn parameters $\vec{\alpha}\in\mathbb{R}^{m}$, such that we can
classify a new tree $\bar{x}$ via the predictive function
$f(\bar{x})=\mathrm{sign}(\sum_{i=1}^{m}\alpha_{i}\cdot
k(\bar{x},\bar{x}_{i}))$. We can learn the parameters $\vec{\alpha}$ by
solving the linear minimization problem:

$\min_{\vec{\alpha}}\sum_{i=1}^{m}\Big{[}1-\ell(\bar{x}_{i})\cdot\sum_{j=1}^{m}\alpha_{j}\cdot
k(\bar{x}_{i},\bar{x}_{j})\Big{]}_{+}+\lambda\cdot\lVert\vec{\alpha}\rVert_{1}$

where $\lambda$ is a hyper-parameter regulating the L1 regularization, and
hence the sparsity, of $\vec{\alpha}$.

Recall that GESL optimizes the pseudo edit distance
$\tilde{d}_{c}(\bar{x},\bar{y})$ instead of the edit distance
$d_{c}(\bar{x},\bar{y})$, and that the theory provided by Bellet et al. (2012)
does not guarantee the goodness of the actual edit distance
$d_{c}(\bar{x},\bar{y})$. Indeed, it may occur that the loss $E(d_{c},P,N)$
for the actual tree edit distance $d_{c}$ is considerably larger than the loss
$E(\tilde{d}_{c},P,N)$.

######  Theorem 3.

There exists combinations of an alphabet $\mathcal{X}$, positive pairs $P$,
negative pairs $N$, a default cost function $c_{0}$, and a regularization
constant $\beta$, such that the cost function $c_{1}$ learned by GESL is not a
pseudo-metric, and yields a loss $E(d_{c_{1}},P,N)>E(\tilde{d}_{c_{1}},P,N)$,
as well as $E(d_{c_{1}},P,N)>E(d_{c_{0}},P,N)$.

###### Proof.

Refer to the supplementary material (Paaßen, 2018b). ∎

Overall, we identify three key points in GESL we would like to address. First,
we would like to select positive and negative pairs in a principled fashion,
in contrast to the ad-hoc scheme of choosing the closest trees from the same
class and the furthest trees from another class. Second, we would like to
enhance the coupling between the pseudo tree edit distance $\tilde{d}_{c}$ to
the actual tree edit distance $d_{c}$. Third, we would like to ensure pseudo-
metric properties on $c$.

##  4 Method

In this section we introduce a novel method for tree edit distance learning.
We start by selecting positive and negative pairs for metric learning via
median learning vector quantization. Then, we introduce metric learning using
the generalized learning vector quantization cost function. Finally, we
propose a novel parameterization of the edit cost function $c$ via symbol
embeddings.

###  4.1 Median Learning Vector Quantization

To facilitate fast metric learning, we would like to limit ourselves to as few
positive and negative pairs as possible. We propose to select positive and
negative pairs via _prototypical_ data points which represent the classes
well. In particular, assume we have data points
$\bar{x}_{1},\ldots,\bar{x}_{m}$ with class assignments
$\ell(\bar{x}_{1}),\ldots,\ell(\bar{x}_{m})$. We propose to select a small
sample of prototypes
$\bar{w}_{1},\ldots,\bar{w}_{K}\subset\\{\bar{x}_{1},\ldots,\bar{x}_{m}\\}$
with $K\ll m$, and to construct positive pairs for all $\bar{x}_{i}$ as
$(\bar{x}_{i},\bar{w}_{i}^{+})$, where $\bar{w}_{i}^{+}$ is the closest
prototype to $\bar{x}_{i}$ according to $d_{c_{0}}$ from the same class; and
negative pairs as $(\bar{x}_{i},\bar{w}_{i}^{-})$, where $\bar{w}_{i}^{-}$ is
the closest prototype to $\bar{x}_{i}$ according to $d_{c_{0}}$ from a
different class.

In our approach, we select these prototypical data points such that they help
us to discriminate between the classes. More precisely, we aim for prototypes
$\bar{w}_{1},\ldots,\bar{w}_{K}$ which can classify as many data points
correctly as possible by assigning the class of the closest prototype. One way
to obtain such prototypes is to optimize the generalized learning vector
quantization (GLVQ) cost function (Sato & Yamada, 1995):

$E=\sum_{i=1}^{m}\Phi\Big{(}\frac{d^{+}_{i}-d^{-}_{i}}{d^{+}_{i}+d^{-}_{i}}\Big{)}$
(4)

where $d^{+}_{i}$ is the distance of $\bar{x}_{i}$ to $\bar{w}_{i}^{+}$,
$d^{-}_{i}$ is the distance of $\bar{x}_{i}$ to $\bar{w}_{i}^{-}$, and
$\Phi(\mu)=\log(4+\mu)$ (Nebel et al., 2015). Note that the fraction
$(d^{+}_{i}-d^{-}_{i})/(d^{+}_{i}+d^{-}_{i})$ is positive if and only if
$\bar{x}_{i}$ is misclassified, such that the cost function is related to the
classification error.

Note that optimizing the GLVQ cost function in this case requires a discrete
optimization scheme because the prototypes $\bar{w}_{k}$ are limited to be
training data points, which is called _median_ learning vector quantization
(Nebel et al., 2015). We follow the suggestion of Nebel et al. (2015) and
apply a generalized expectation maximization (EM) scheme to maximize
$\sum_{i=1}^{m}\log(g^{-}_{i}+g^{+}_{i})$, where
$g^{-}_{i}=2+d^{-}_{i}/(d^{+}_{i}+d^{-}_{i})$, and
$g^{+}_{i}=2-d^{+}_{i}/(d^{+}_{i}+d^{-}_{i})$. The expectation step of the EM
scheme consists of computing the quantities
$\gamma^{+}_{i}=g^{+}_{i}/(g^{+}_{i}+g^{-}_{i})$ as well as
$\gamma^{-}_{i}=g^{-}_{i}/(g^{+}_{i}+g^{-}_{i})$ for all $i$, and the
maximization step consists of finding a prototype $\bar{w}_{k}$ which can be
set to a different data point $\bar{x}_{i}$ such that the likelihood
$\mathcal{L}=\sum_{i=1}^{m}\gamma^{+}_{i}\cdot\log(g^{+}_{i}/\gamma^{+}_{i})+\gamma^{-}_{i}\cdot\log(g^{-}_{i}/\gamma^{-}_{i})$
is improved, assuming fixed $\gamma^{+}_{i}$ and $\gamma^{-}_{i}$. The EM
scheme stops if it is not possible to improve $\mathcal{L}$ for any prototype
anymore.

###  4.2 Metric Learning via Learning Vector Quantization

Recall that the GLVQ cost function in Equation 4 quantifies how well our
prototypes classify the training data. Following the recommendation of Mokbel
et al. (2015), we can not only use this cost function for learning the
prototypes, but also for learning the metric. In particular, we can minimize
the GLVQ loss with respect to the cost function $c$ using any unconstrained
gradient-based solver, such as the limited-memory Broyden-Fletcher-Goldfarb-
Shanno (L-BFGS) algorithm (Liu & Nocedal, 1989). For the gradient
$\nabla_{c}E$ we obtain:

$\sum_{i=1}^{m}\Phi^{\prime}\Big{(}\frac{d^{+}_{i}-d^{-}_{i}}{d^{+}_{i}+d^{-}_{i}}\Big{)}\cdot\frac{d^{-}_{i}\cdot\nabla_{c}d^{+}_{i}-d^{+}_{i}\cdot\nabla_{c}d^{-}_{i}}{(d^{+}_{i}+d^{-}_{i})^{2}}$
(5)

where $\Phi^{\prime}(\mu)=1/(4+\mu)$.

Following the GESL approach of Bellet et al. (2012), we optimize the pseudo
tree edit distance $\tilde{d}_{c}$ instead of the tree edit distance itself,
which yields the gradient
$\nabla_{c}\tilde{d}(\bar{x}_{i},\bar{w}_{k})=\bm{P}_{c_{0}}(\bar{x}_{i},\bar{w}_{k})$.
However, we improve upon GESL by not only considering one cheapest edit
script, but instead the average over all cheapest edit scripts. In particular,
we consider $\bm{P}_{c_{0}}(\bar{x}_{i},\bar{w}_{k})$ to be the average over
the matrices for all cheapest edit scripts.

Considering all co-optimal scripts permits us to exploit additional
information, with which we can prevent many degenerate cases in which
$\tilde{d}_{c}$ underestimates $d_{c}$. In particular, the counter example in
the proof of Theorem 3 does not hold in this case. Computing this average over
all cheapest edit scripts is possible efficiently via a novel forward-backward
algorithm which we developed for this contribution (refer to the supplementary
material; Paaßen (2018a)).

We further note that changes to the metric may also enable us to optimize the
prototype locations further. Therefore, we employ an alternating optimization
scheme where we first learn the prototype positions according to median GLVQ,
then adapt the metric, and repeat until either the prototype positions do not
change anymore or the solver is not able to improve the metric anymore.

Until now, we have addressed the selection of positive and negative pairs, as
well as a closer coupling between pseudo edit distance and edit distance.
However, we still have to ensure pseudo-metric properties on the learned cost
function. For this purpose, we introduce vectorial embeddings.

###  4.3 Tree Label Embeddings

Let $\mathcal{X}$ be a finite set with $U$ elements. Then, a vector embedding
of $\mathcal{X}$ is a matrix $\bm{A}\in\mathbb{R}^{V\times U}$ with $V\leq U$,
where each column is a vector $\vec{a}(x)$ for one $x\in\mathcal{X}$. Further,
we define $\vec{a}(-):=\vec{0}$, i.e. the origin of the $V$-dimensional
Euclidean space. We define the cost function corresponding to an embedding as
the Euclidean distance between the embedding vectors, that is:
$c_{\bm{A}}(x,y):=\lVert\vec{a}(x)-\vec{a}(y)\rVert$.

Because the cost function is the Euclidean distance, it is guaranteed to be a
pseudo-metric, irrespective of the choice of the embedding $\bm{A}$.
Furthermore, $c_{\bm{A}}$ is differentiable with respect to the embedding
vectors with the gradient
$\nabla_{\vec{a}(x)}c_{\bm{A}}(x,y)=(\vec{a}(x)-\vec{a}(y))/\lVert\vec{a}(x)-\vec{a}(y)\rVert$.
Using this gradient and Equation 3, we can also obtain a gradient of the
pseudo-edit distance $\tilde{d}_{c}(\bar{x},\bar{y})$ with respect to
$\vec{a}(x)$:

$\displaystyle\nabla_{\vec{a}(x)}\tilde{d}_{c_{\bm{A}}}(\bar{x},\bar{y})=$ (6)
$\displaystyle\sum_{i=1}^{|\bar{x}|}\delta(x,x_{i})\cdot\bigg{[}\sum_{j=1}^{|\bar{y}|+1}\bm{P}_{c_{0}}(\bar{x},\bar{y})_{i,j}\cdot\frac{\vec{a}(x)-\vec{a}(y_{j})}{\lVert\vec{a}(x)-\vec{a}(y_{j})\rVert}\bigg{]}$
$\displaystyle+$
$\displaystyle\sum_{j=1}^{|\bar{y}|}\delta(x,y_{j})\cdot\bigg{[}\sum_{i=1}^{|\bar{x}|+1}\bm{P}_{c_{0}}(\bar{x},\bar{y})_{i,j}\cdot\frac{\vec{a}(x)-\vec{a}(x_{i})}{\lVert\vec{a}(x)-\vec{a}(x_{i})\rVert}\bigg{]}$

where $\delta$ is the Kronecker-Delta, i.e.: $\delta(x,y)=1$ if $x=y$ and $0$
otherwise.

Finally, we can plug this result into Equation 5, which yields a gradient
$\nabla_{\vec{a}(x)}E$, such that we can learn the vectorial embedding of
$\mathcal{X}$ via gradient techniques. Note that prior theory on metric
learning on the GLVQ cost function suggests that the learned embedding will
degenerate to a very low rank-matrix such that the model may become overly
simplistic (Biehl et al., 2015). To prevent such a degeneration, we follow the
regularization recommendation of Schneider et al. (2010) and add the term
$\beta\cdot\log(\det({\bm{A}}^{T}\cdot\bm{A}))$ to the GLVQ loss 4, which adds
the gradient $\beta\cdot 2\cdot{{\bm{A}^{\dagger}}}^{T}$ where
$\bm{A}^{\dagger}$ is the Moore-Penrose-Pseudoinverse of $\bm{A}$.
Additionally, we follow the regularization approach of good edit similarity
learning (Bellet et al., 2012) and add the Frobenius-norm
$\beta\cdot\lVert\bm{A}\rVert^{2}_{F}$ to the loss, which adds the gradient
$\beta\cdot 2\cdot\bm{A}$.

As initialization of the vectorial embedding we use a $U$-dimensional simplex
with side length $1$, which leads to $c_{0}(x,y)=0$ if $x=y$ and $1$ otherwise
(refer to the supplementary material for a more detailed look into this
initialization (Paaßen, 2018b)).

Regarding computational complexity, we can analyze the gradient computation.
To compute a gradient, we first need to select the closest correct and closest
wrong prototype for every data point, which is possible in $\mathcal{O}(m\cdot
K)$. Then, we need to compute the gradient for each data point via Equation 6,
which is possible in $\mathcal{O}(m\cdot n^{2}\cdot V)$ where $n$ is the
largest tree size in the data set. Computing the regularization requires
$\mathcal{O}(V^{3})$ due to the Pseudoinverse, resulting in
$\mathcal{O}(m\cdot K+m\cdot n^{2}\cdot V+V^{3})$ overall. How often the
gradient needs to be computed depends on the optimizer, but can typically be
regarded as a constant. In our experiments, we limit the number of gradient
computations to $200$.

##  5 Experiments

In our experiment, we investigate whether our proposed metric learning scheme,
embedding edit distance learning (BEDL), is able to improve classification
accuracy beyond the default initialization, whether BEDL improves upon the
accuracy obtained by good edit similarity learning (Bellet et al., 2012), and
whether the resulting embedding yields insight regarding the classification
task in question. In particular, we evaluate on the following data sets,
including a variety of domains and data set sizes.

Strings: A two-class data set of $200$ strings of length 12, adapted from
Mokbel et al. (2015). Strings in class 1 consist of 6 a or b symbols, followed
by a c or d, followed by another 5 a or b symbols. Which of the two respective
symbols is selected is chosen uniformly at random. Strings in class 2 are
constructed in much the same way, except that they consist of 5 a or b
symbols, followed by a c or d, followed by another 6 a or b symbols. Note that
the classes can be neither discriminated via length nor via symbol frequency
features. The decisive discriminative feature is where a c or d is located in
the string.

MiniPalindrome and Sorting: Two data sets of Java programs, where classes
represent different strategies to solve a programming task. The MiniPalindrome
data set contains 48 programs implementing one of eight strategies to detect
whether an input string contains only palindromes (Paaßen, 2016a), and the
Sorting data set contains 64 programs implementing either a BubbleSort or an
InsertionSort strategy (Paaßen, 2016b). The programs are represented by their
abstract syntax tree where the label corresponds to one of 24 programming
concepts (e.g. class declaration, function declaration, method call, etc.).

Cystic and Leukemia: Two data sets from KEGG/Glycan data base (Hashimoto et
al., 2006) adapted from Gallicchio & Micheli (2013), where one class
corresponds to benign molecules and the other class corresponds to molecules
associated with cystic fibrosis or leukemia respectively. The molecules are
represented as trees, where the label corresponds to mono-saccharide
identifiers (one of 29 and one of 57 for Cystic and Leukemia, respectively),
and the roots are chosen according to biological meaning (Hashimoto et al.,
2006). The cystic data set contains 160, the Leukemia data set 442 molecules.

Sentiment: A large-scale two-class data set of 9613 sentences from movie
reviews, where one class (4650 trees) corresponds to negative and the other
class (4963 trees) to positive reviews. The sentences are represented by their
syntax trees, where inner nodes are unlabeled and leaves are labeled with one
of over $30,000$ words (Socher et al., 2013). Note that GESL is not
practically applicable for this data set, as the number of parameters to learn
scales quadratically with the number of words, i.e. $>30,000^{2}$. To make
BEDL applicable in whis case, we initialize the vectorial embedding with the
$300$-dimensional Common Crawl GloVe embedding (Pennington et al., 2014),
which we reduce via PCA, retaining $95\%$ of the data variance ($V=16.4\pm
2.3$ dimensions on average $\pm$ standard deviation). We adapt this initial
embedding via a linear transformation $\Omega\in\mathbb{R}^{V\times V}$ which
we learn vie BEDL. Further, we replace the cost function with the cosine
distance
$c_{\Omega}(\vec{x},\vec{y})=\frac{1}{2}-\frac{1}{2}\cdot({(\Omega\cdot\vec{x})}^{T}\cdot\Omega\cdot\vec{y})/(\lVert\Omega\cdot\vec{x}\rVert\cdot\lVert\Omega\cdot\vec{y}\rVert)$,
which is the recommended distance measure for the GloVe word embedding
(Pennington et al., 2014) (refer to the supplementary material for the
gradient; Paaßen (2018b)).

On each data set, we perform a crossvalidation111We used 20 folds for Strings
and Sentiment, 10 for Cystic and Leukemia, 8 for Sorting and 6 for
MiniPalindrome. For the programming data sets, the number of folds had to be
reduced to ensure that each fold still contained a meaningful number of data
points. For the Cystic and Leukemia data set, our ten folds were consistent
with the paper of Gallicchio & Micheli (2013). In all cases, folds were
generated such that the label distribution of the overall data set was
maintained. and compare the average test error across folds. In particular, we
compare the error when using the initial tree edit distance with the error
when using the pseudo-edit distance learned via good edit similarity learning
(GESL), and the tree edit distance learned via our proposed approach (BEDL).

In general, we would expect that a discriminative metric learned for one
classifier also facilitates classification using other classifiers. Therefore,
we report the classification error for four classifiers, namely the median
generalized learning vector quantization classifier (MGLVQ) for which our
method is optimized, the goodness classifier for which GESL is optimized
(Bellet et al., 2012), the K-nearest neighbor (KNN) classifier, and the
support vector machine (SVM) based on the radial basis function kernel. In
order to ensure a kernel matrix for SVM, we set negative eigenvalues to zero
(clip Eigenvalue correction). Note that this eigenvalue correction requires
cubic runtime in terms of the number of data points and is thus prohibitively
slow for large data set sizes. Therefore, for the Sentiment data set, we
trained the classifiers on a randomly selected sample of $300$ points from the
training data.

We optimized all hyper-parameters in a nested $5$-fold crossvalidation, namely
the number of prototypes $K$ for MGLVQ and LVQ metric learning in the range
$[1,15]$, the number of neighbors for KNN in the range $[1,15]$, the kernel
bandwidth for SVM in the range $[0.1,10]$, the sparsity parameter $\lambda$
for the goodness classifier in the range $[10^{-}5,10]$, and the
regularization strength $\beta$ for GESL and BEDL in the range $2\cdot K\cdot
m\cdot[10^{-6},10^{-2}]$. We chose the number of prototypes for BEDL, as well
as the number of neighbors for GESL as the optimal number of prototypes $K$
for MGLVQ.

As implementations, we used custom implementations of KNN, MGLVQ, the goodness
classifier, GESL, and BEDL, which are availabe at
https://doi.org/10.4119/unibi/2919994. For SVM, we utilized the LIBSVM
standard implementation (Chang & Lin, 2011). All experiments were performed on
a consumer-grade laptop with an Intel Core i7-7700 HQ CPU.

Table 1: The mean test classification error and runtimes for metric learning, averaged over the cross validation trials, as well as the standard deviation. The x-axis shows the metric learning schemes, the y-axis the different classifiers used for evaluation. The table is sub-divided for each data set. The lowest classification error for each data set is highlighted via bold print. classifier | initial | GESL | BEDL
---|---|---|---
|  | Strings |
KNN | $21.0\pm 10.2\%$ | $23.0\pm 10.8\%$ | $\bm{0.0\pm 0.0\%}$
MGLVQ | $36.0\pm 15.7\%$ | $34.0\pm 11.0\%$ | $\bm{0.0\pm 0.0\%}$
SVM | $9.0\pm 11.2\%$ | $10.0\pm 8.6\%$ | $\bm{0.0\pm 0.0\%}$
goodness | $11.5\pm 9.3\%$ | $0.5\pm 2.2\%$ | $\bm{0.0\pm 0.0\%}$
runtime [s] | $0\pm 0$ | $0.030\pm 0.002$ | $1.077\pm 0.098$
|  | MiniPalindrome |
KNN | $12.5\pm 11.2\%$ | $12.5\pm 7.9\%$ | $10.4\pm 9.4\%$
MGLVQ | $2.1\pm 5.1\%$ | $4.2\pm 6.5\%$ | $\bm{0.0\pm 0.0\%}$
SVM | $4.2\pm 6.5\%$ | $20.8\pm 15.1\%$ | $\bm{0.0\pm 0.0\%}$
goodness | $6.2\pm 6.8\%$ | $14.6\pm 5.1\%$ | $8.3\pm 10.2\%$
runtime [s] | $0\pm 0$ | $0.103\pm 0.014$ | $2.785\pm 0.631$
|  | Sorting |
KNN | $15.6\pm 8.8\%$ | $18.8\pm 16.4\%$ | $10.9\pm 8.0\%$
MGLVQ | $14.1\pm 10.4\%$ | $14.1\pm 8.0\%$ | $14.1\pm 8.0\%$
SVM | $10.9\pm 8.0\%$ | $\bm{9.4\pm 8.8\%}$ | $\bm{9.4\pm 8.8\%}$
goodness | $15.6\pm 11.1\%$ | $17.2\pm 14.8\%$ | $17.2\pm 9.3\%$
runtime [s] | $0\pm 0$ | $0.352\pm 0.102$ | $3.358\pm 0.748$
|  | Cystic |
KNN | $31.2\pm 6.6\%$ | $32.5\pm 10.1\%$ | $28.1\pm 8.5\%$
MGLVQ | $34.4\pm 6.8\%$ | $33.1\pm 9.8\%$ | $30.0\pm 10.1\%$
SVM | $28.1\pm 9.0\%$ | $33.1\pm 8.9\%$ | $29.4\pm 12.5\%$
goodness | $28.1\pm 8.5\%$ | $26.2\pm 14.4\%$ | $\bm{24.4\pm 13.3\%}$
runtime [s] | $0\pm 0$ | $0.353\pm 0.292$ | $0.864\pm 0.767$
|  | Leukemia |
KNN | $7.5\pm 2.6\%$ | $8.2\pm 4.6\%$ | $7.3\pm 4.3\%$
MGLVQ | $9.5\pm 4.0\%$ | $10.9\pm 4.7\%$ | $9.5\pm 3.0\%$
SVM | $7.0\pm 4.1\%$ | $8.8\pm 2.9\%$ | $6.8\pm 4.7\%$
goodness | $\bm{6.1\pm 4.3\%}$ | $10.0\pm 4.4\%$ | $6.3\pm 3.8\%$
runtime [s] | $0\pm 0$ | $2.208\pm 0.919$ | $6.550\pm 2.706$
|  | Sentiment |
kNN | $40.2\pm 2.8\%$ | $-$ | $38.2\pm 3.3\%$
MGLVQ | $44.0\pm 2.6\%$ | $-$ | $41.3\pm 5.7\%$
SVM | $34.3\pm 3.0\%$ | $-$ | $\bm{33.3\pm 3.6\%}$
goodness | $43.7\pm 1.9\%$ | $-$ | $42.5\pm 3.1\%$
runtime [s] | $0\pm 0$ | $-$ | $69.385\pm 58.064$

$0$$2$$4$$-0.1$$0$$0.1$$\text{{a}},\text{{b}},-$$\text{{c}},\text{{d}}$

$0$$5$$10$$-5$$0$$5$$-5$$0$$-$blockmodifierswhileparameterized type

Figure 1: A PCA of the learned embeddings for the Strings (top) and the
MiniPalindrome data set (bottom), covering $100\%$ and $83.54\%$ of the
variance respectively.

The results of our experiments are displayed in Table 1. In all data sets and
for all classifiers, BEDL yields lower classification error compared to GESL.
For the Strings data set we can also verify this result statistically with a
one-sided Wilcoxon signed rank test ($p<10^{-4}$). Furthermore, in all but the
Leukemia data set, BEDL yields the overall best classification results, and is
close to optimal for the Leukemia data set ($0.2\%$ difference). In all cases,
BEDL could improve the accuracy for KNN, in five out of six cases for SVM (the
exception being the Cystic data set), in four out of six cases for MGLVQ (in
Sorting and Leukemia it stayed equal), and in three out of six cases for the
goodness classifier. For the Strings and Sentiment data sets we can also
verify this result statistically with $p<0.05$ for all classifiers.

Note that the focus of our work is to improve classification accuracy via
metric learning, not to develop state-of-the-art classifiers as such. However,
we note that our results for the Sorting data set outperform the best reported
results by Paaßen et al. (2016) of $15\%$. For the Cystic data set we improve
the AUC from $76.93\pm 0.97\%$ mean and standard deviation across
crossvalidation trials to $79.2\pm 13.6\%$, and for the Leukemia data set from
$93.8\pm 3.3\%$ to $94.6\pm 4.5\%$. Both values are competitive with the
results obtained via recursive neural networks and a multitude of graph
kernels by Gallicchio & Micheli (2013). For the Sentiment data set, we obtain
a SVM classification error of $27.51\%$ on the validation set, which is
noticeably worse than the reported literature results of around $12.5\%$
(Socher et al., 2013). However, we note that we used considerably less data to
train our classifier (only $500$ points for the validation).

Interestingly, GESL tended to decrease classification accuracy compared to the
initial tree edit distance. Likely, GESL requires more neighbors for better
results (Bellet et al., 2012). However, scaling up to a high number of
neighbors lead to prohibitively high runtimes for our experiments such that we
do not report these results here. These high runtimes can be explained by the
fact that the number of slack variables in GESL increases with
$\mathcal{O}(m\cdot K)$ where $m$ is the number of data points and $K$ is the
number of neighbors. The scaling behavior is also visible in our experimental
results. For data sets with little data points and neighbors, such as Strings,
MiniPalindrome, and Sorting, GESL is $10$ to $30$ times faster compared to
BEDL. However, for Cystic and Leukemia, the runtime advantage shrinks to a
factor of $2$ to $3$.

In ablation studies, we studied the difference between GESL and BEDL in more
detail. We observed that considering the average over all co-optimal edit
scripts, and considering LVQ prototypes instead of ad-hoc nearest neighbors,
improved GESL on the MiniPalindrome data set, worsened it for the Strings data
set, and showed no remarkable difference for the Sorting, Cystic, and Leukemia
data set. We also compared BEDL without the embedding approach and with the
embedding approach. Interestingly, the pseudo-edit distance performed worse
when considering embeddings, while the actual edit distance performed better
when considering embeddings. In general, GESL variants performed better for
the pseudo-edit distance than for the actual edit distance, and LVQ variants
performed better for the actual edit distance compared to the pseudo edit
distance. We report the full results in the supplementary material (Paaßen,
2018b).

Beyond classification accuracy, our metric learning approach permits to
inspect the resulting embedding. Figure 1 displays a PCA of the embeddings
learned for the Strings and MiniPalindrome data set respectively. As we can
see, the embedding for the Strings data set captures the objective of the task
perfectly: Both a as well as b symbols are irrelevant for class discrimination
and are thus embedded at the origin, while c and d are embedded far from the
origin, but both at the same location. For MiniPalindrome, we also observe
that most syntactic concepts are embedded at zero, indicating that a
combination of the four remaining concepts is sufficient for class
discrimination; namely the block concept, which captures the nesting structure
of the program, the while concept, which is specific to one of the classes,
the modifiers concept, which can serve to count the number of variables and
methods in the program, and the parametrized type concept, which distinguishes
programs with advanced data structured from programs with primitive data
structures.

##  6 Conclusion

In this contribution we have proposed embedding edit distance learning (BEDL)
as a novel approach for edit distance learning on trees with three distinct
characteristics: First, our objective is the generalized learning vector
quantization cost function, which pulls data points closer to the closest
prototype for their own class and pushes them away from the closest prototype
for a different class; second, we consider not only a single optimal edit
script between trees but a summary of _all_ co-optimal edit scripts; finally,
we do not learn a cost function for the edits directly, but instead a
vectorial embedding of the label alphabet, which guarantees metric properties
and can be interpreted. In our experiments we have shown that BEDL improves
upon the state-of-the-art of good edit similarity learning for trees on a
diverse tree data sets including Java program syntax trees, tree-based
molecule representations from a biomedical task, and syntax trees in natural
language processing.

Limitations of our work include that an improvement of the loss function for
the pseudo edit distance does not strictly imply an improvement of the loss
for the actual edit distance, and that improvements in classification accuracy
are small for some classifiers and some data sets. Future research should
investigate the relation between pseudo edit distance and edit distance, as
well as the relation between the number of prototypes and metric learning
performance in more detail. It may also be worthwhile to study different cost
functions, in particular probabilistic ones, which may be compatible with
probabilistic models of the edit distance. Still, we regard our existing
contribution as a meaningful step towards edit distances on trees which are
both discriminative as well as interpretable and can thus enhance accuracy and
understanding on classification tasks of structured data.

## Acknowledgements

Funding by the DFG under grant number HA 2719/6-2 and the CITEC center of
excellence (EXC 277) is gratefully acknowledged. Thanks to David Nebel and our
anonymous reviewers for helpful comments and suggestions.

## References

  * Aiolli & Donini (2015) Aiolli, F. and Donini, M.  EasyMKL: A scalable multiple kernel learning algorithm.  _Neurocomputing_ , 169:215–224, 2015.  doi:10.1016/j.neucom.2014.11.078.
  * Aiolli et al. (2015) Aiolli, F., Martino, G. D. S., and Sperduti, A.  An efficient topological distance-based tree kernel.  _IEEE Transactions on Neural Networks and Learning Systems_ , 26(5):1115–1120, 2015.  doi:10.1109/TNNLS.2014.2329331.
  * Bacciu et al. (2018) Bacciu, D., Micheli, A., and Sperduti, A.  Generative kernels for tree-structured data.  _IEEE Transactions on Neural Networks and Learning Systems_ , 2018\.  doi:10.1109/TNNLS.2017.2785292.  in press.
  * Balcan et al. (2008) Balcan, M.-F., Blum, A., and Srebro, N.  A theory of learning with similarity functions.  _Machine Learning_ , 72(1):89–112, Aug 2008.  doi:10.1007/s10994-008-5059-5.
  * Bellet et al. (2012) Bellet, A., Habrard, A., and Sebban, M.  Good edit similarity learning by loss minimization.  _Machine Learning_ , 89(1):5–35, Oct 2012.  doi:10.1007/s10994-012-5293-8.
  * Bellet et al. (2014) Bellet, A., Habrard, A., and Sebban, M.  A survey on metric learning for feature vectors and structured data.  _arXiv e-prints_ , 2014.  URL http://arxiv.org/abs/1306.6709.
  * Bellet et al. (2016) Bellet, A., Bernabeu, J. F., Habrard, A., and Sebban, M.  Learning discriminative tree edit similarities for linear classification - application to melody recognition.  _Neurocomputing_ , 214:155 – 161, 2016.  doi:10.1016/j.neucom.2016.06.006.
  * Biehl et al. (2015) Biehl, M., Hammer, B., Schleif, F.-M., Schneider, P., and Villmann, T.  Stationarity of matrix relevance LVQ.  In _Proceedings of the 2015 International Joint Confgerence on Neural Networks (IJCNN 2015)_ , pp. 1–8, 2015.  doi:10.1109/IJCNN.2015.7280441.
  * Boyer et al. (2007) Boyer, L., Habrard, A., and Sebban, M.  Learning metrics between tree structured data: Application to image recognition.  In Kok, J. N., Koronacki, J., Mantaras, R. L. d., Matwin, S., Mladenič, D., and Skowron, A. (eds.), _Proceedings of the 18th European Conference on Machine Learning (ECML 2007)_ , pp. 54–66. Springer, 2007\.  doi:10.1007/978-3-540-74958-5_9.
  * Chang & Lin (2011) Chang, C.-C. and Lin, C.-J.  LIBSVM: A library for support vector machines.  _ACM Transactions on Intelligent Systems and Technology_ , 2(3):27:1–27:27, 2011.  doi:10.1145/1961189.1961199.  Software available at http://www.csie.ntu.edu.tw/~cjlin/libsvm.
  * Cho et al. (2014) Cho, K., van Merrienboer, B., Gülçehre, Ç., Bougares, F., Schwenk, H., and Bengio, Y.  Learning phrase representations using RNN encoder-decoder for statistical machine translation.  In Moschitti, A., Pang, B., and Daelemans, W. (eds.), _Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP 2014)_ , pp. 1724–1734, 2014.  URL https://www.aclweb.org/anthology/D14-1179.
  * Cover & Hart (1967) Cover, T. M. and Hart, P. E.  Nearest neighbor pattern classification.  _IEEE Transactions on Information Theory_ , 13(1):21–27, 1967.  doi:10.1109/TIT.1967.1053964.
  * Da San Martino & Sperduti (2010) Da San Martino, G. and Sperduti, A.  Mining structured data.  _Computational Intelligence Magazine_ , 5(1):42–49, Feb 2010.  doi:10.1109/MCI.2009.935308.
  * Gallicchio & Micheli (2013) Gallicchio, C. and Micheli, A.  Tree echo state networks.  _Neurocomputing_ , 101:319–337, 2013.  doi:10.1016/j.neucom.2012.08.017.
  * Gisbrecht et al. (2015) Gisbrecht, A., Schulz, A., and Hammer, B.  Parametric nonlinear dimensionality reduction using kernel t-SNE.  _Neurocomputing_ , 147:71–82, 2015.  doi:10.1016/j.neucom.2013.11.045.
  * Hammer et al. (2007) Hammer, B., Micheli, A., and Sperduti, A.  _Adaptive Contextual Processing of Structured Data by Recursive Neural Networks: A Survey of Computational Properties_ , pp. 67–94.  Springer Berlin Heidelberg, Berlin, Heidelberg, 2007.  doi:10.1007/978-3-540-73954-8_4.
  * Hashimoto et al. (2006) Hashimoto, K., Goto, S., Kawano, S., Aoki-Kinoshita, K. F., Ueda, N., Hamajima, M., Kawasaki, T., and Kanehisa, M.  KEGG as a glycome informatics resource.  _Glycobiology_ , 16(5):63R–70R, 2006.  doi:10.1093/glycob/cwj010.
  * Kohonen (1995) Kohonen, T.  _Learning Vector Quantization_ , pp. 175–189.  Springer Berlin Heidelberg, 1995.  doi:10.1007/978-3-642-97610-0_6.
  * Kulis (2013) Kulis, B.  Metric learning: A survey.  _Foundations and Trends in Machine Learning_ , 5(4):287–364, 2013.  doi:10.1561/2200000019.
  * Liu & Nocedal (1989) Liu, D. C. and Nocedal, J.  On the limited memory BFGS method for large scale optimization.  _Mathematical Programming_ , 45(1):503–528, 1989\.  doi:10.1007/BF01589116.
  * Mokbel et al. (2015) Mokbel, B., Paaßen, B., Schleif, F.-M., and Hammer, B.  Metric learning for sequences in relational LVQ.  _Neurocomputing_ , 169:306–322, 2015.  doi:10.1016/j.neucom.2014.11.082.
  * Nebel et al. (2015) Nebel, D., Hammer, B., Frohberg, K., and Villmann, T.  Median variants of learning vector quantization for learning of dissimilarity data.  _Neurocomputing_ , 169:295–305, 2015.  doi:10.1016/j.neucom.2014.12.096.
  * Paaßen et al. (2016) Paaßen, B., Mokbel, B., and Hammer, B.  Adaptive structure metrics for automated feedback provision in intelligent tutoring systems.  _Neurocomputing_ , 192:3–13, 2016.  doi:10.1016/j.neucom.2015.12.108.
  * Paaßen et al. (2018) Paaßen, B., Hammer, B., Price, T. W., Barnes, T., Gross, S., and Pinkwart, N.  The Continuous Hint Factory - providing hints in vast and sparsely populated edit distance spaces.  _Journal of Educational Datamining_ , 2018.  URL http://arxiv.org/abs/1708.06564.  accepted.
  * Paaßen (2016a) Paaßen, B.  MiniPalindrome, 2016a.  Bielefeld University, doi:10.4119/unibi/2900666.
  * Paaßen (2016b) Paaßen, B.  Java Sorting Programs, 2016b.  Bielefeld University, doi:10.4119/unibi/2900684.
  * Paaßen (2018a) Paaßen, B.  Revisiting the tree edit distance and its backtracing: A tutorial.  _ArXiv e-prints_ , 2018a.  URL https://arxiv.org/abs/1805.06869.
  * Paaßen (2018b) Paaßen, B.  Tree edit distance learning via adaptive symbol embeddings: Supplementary materials and results.  _ArXiv e-prints_ , 2018b.  URL https://arxiv.org/abs/1805.07123.
  * Pennington et al. (2014) Pennington, J., Socher, R., and Manning, C. D.  GloVe: Global vectors for word representation.  In Moschitti, A., Pang, B., and Daelemans, W. (eds.), _Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP 2014)_ , pp. 1532–1543, 2014.  URL http://www.aclweb.org/anthology/D14-1162.
  * Sato & Yamada (1995) Sato, A. and Yamada, K.  Generalized learning vector quantization.  In Tesauro, G., Touretzky, D., and Leen, T. (eds.), _Proceedings of the 7th conference on Advances in Neural Information Processing Systems (NIPS 1995)_ , pp. 423–429. MIT Press, 1995.  URL https://papers.nips.cc/paper/1113-generalized-learning-vector-quantization.
  * Schleif & Tino (2015) Schleif, F.-M. and Tino, P.  Indefinite proximity learning: A review.  _Neural Computation_ , 27(10):2039–2096, 2015\.  doi:10.1162/NECO_a_00770.
  * Schneider et al. (2009) Schneider, P., Biehl, M., and Hammer, B.  Adaptive relevance matrices in learning vector quantization.  _Neural Computation_ , 21(12):3532–3561, 2009\.  doi:10.1162/neco.2009.11-08-908.
  * Schneider et al. (2010) Schneider, P., Bunte, K., Stiekema, H., Hammer, B., Villmann, T., and Biehl, M.  Regularization in matrix relevance learning.  _IEEE Transactions on Neural Networks_ , 21(5):831–840, 2010.  doi:10.1109/TNN.2010.2042729.
  * Shervashidze et al. (2011) Shervashidze, N., Schweitzer, P., Leeuwen, E. J. v., Mehlhorn, K., and Borgwardt, K. M.  Weisfeiler-Lehman graph kernels.  _Journal of Machine Learning Research_ , 12(Sep):2539–2561, 2011.  URL http://www.jmlr.org/papers/v12/shervashidze11a.html.
  * Smith & Waterman (1981) Smith, T. F. and Waterman, M. S.  Identification of common molecular subsequences.  _Journal of Molecular Biology_ , 147(1):195–197, 1981.  doi:10.1016/0022-2836(81)90087-5.
  * Socher et al. (2013) Socher, R., Perelygin, A., Wu, J. Y., Chuang, J., Manning, C. D., Ng, A. Y., and Potts, C.  Recursive deep models for semantic compositionality over a sentiment treebank.  In Baldwin, T. and Korhonen, A. (eds.), _Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing (EMNLP 2013)_ , pp. 1631–1642, 2013.  URL http://www.aclweb.org/anthology/D/D13/D13-1170.pdf.
  * Sutskever et al. (2014) Sutskever, I., Vinyals, O., and Le, Q. V.  Sequence to sequence learning with neural networks.  In Ghahramani, Z., Welling, M., Cortes, C., Lawrence, N. D., and Weinberger, K. Q. (eds.), _Proceedings of the 27th Conference on Advances in Neural Information Processing Systems (NIPS 2014)_ , pp. 3104–3112. Curran Associates, Inc., 2014.  URL https://papers.nips.cc/paper/5346-sequence-to-sequence-learning-with-neural-networks.
  * Yanardag & Vishwanathan (2015) Yanardag, P. and Vishwanathan, S.  Deep graph kernels.  In _Proceedings of the 21th International Conference on Knowledge Discovery and Data Mining (KDD 2015)_ , pp. 1365–1374, New York, NY, USA, 2015. ACM.  doi:10.1145/2783258.2783417.
  * Zeng et al. (2009) Zeng, Z., Tung, A. K. H., Wang, J., Feng, J., and Zhou, L.  Comparing stars: On approximating graph edit distance.  _Proceedings of the VLDB Endowment_ , 2(1):25–36, 2009.  doi:10.14778/1687627.1687631.
  * Zhang & Shasha (1989) Zhang, K. and Shasha, D.  Simple fast algorithms for the editing distance between trees and related problems.  _SIAM Journal on Computing_ , 18(6):1245–1262, 1989.  doi:10.1137/0218082.
  * Zhang et al. (1992) Zhang, K., Statman, R., and Shasha, D.  On the editing distance between unordered labeled trees.  _Information Processing Letters_ , 42(3):133–139, 1992.  doi:10.1016/0020-0190(92)90136-J.