# BacHMMachine: An Interpretable and Scalable Model for Algorithmic
Harmonization

Yunyao Zhu*<EMAIL_ADDRESS>
Stephen Hahn*<EMAIL_ADDRESS>
Simon Mak<EMAIL_ADDRESS>
Yue Jiang<EMAIL_ADDRESS>
Cynthia Rudin<EMAIL_ADDRESS>

###### Abstract

Algorithmic harmonization – the automated harmonization of a musical piece
given its melodic line – is a challenging problem that has garnered much
interest from both music theorists and computer scientists. Methods for
algorithmic chorale harmonization typically adopt a black-box, “data-driven”
approach: they do not explicitly integrate principles from music theory but
rely on a complex learning model trained with a large amount of chorale data.
We propose instead a new harmonization model, called BacHMMachine, which
employs a “theory-driven” framework guided by music composition principles,
along with a “data-driven” model for learning compositional features within
this framework. These music principles are elicited from the four-part Baroque
chorales of J.S. Bach, but are broadly applicable for a wide range of musical
genres. BacHMMachine uses a novel Hidden Markov Model based on key and chord
transitions, providing a probabilistic framework for learning key modulations
and chordal progressions from a given melodic line. This allows for the
generation of creative, yet musically coherent harmonizations. Furthermore,
integrating compositional principles allows for a much simpler model that
results in vast decreases in computational burden and greater interpretability
compared to state-of-the-art algorithmic harmonization methods, at no penalty
to quality of harmonization or musicality. We demonstrate the improvement of
BacHMMachine over existing harmonization methods via comprehensive experiments
and Turing tests for Baroque chorales, and furthermore demonstrate its
flexibility and applicability to other domain fields by applying our
methodology to rock music.

††footnotetext: *Equal contribution

Harmonization is the task of generating a musically appropriate harmony given
a melody as the input. While harmonization is typically viewed as a creative
endeavor, it also follows formal rules set by musical convention and style.
Take, for example, the harmonization of Baroque-style chorales in four voices
(soprano, alto, tenor, and bass), where the given melody is a pre-existing
soprano voice, and the harmony arises from the interaction of the four melodic
lines. For such chorales, Gradus ad Parnassum (citep (Fux, 1725)) is an early
treatise on species counterpoint, formalizing a set of musical principles for
composition in multiple voices. Subject to such principles, composers may
write coherent harmonizations in any number of ways, the choice of which often
reflecting a composer’s creative signature.

In recent years, algorithmic harmonization has garnered notable interest from
both music theorists and computer scientists. Much of the existing literature
adopts a “data-driven” approach: musical pieces are first converted to
training data, then used within state-of-the-art machine learning models for
harmonization. Such methods are typically “black-box,” ignoring underlying
compositional principles from music theory (e.g., the DeepBach model of (citet
Hadjeres et al. 2017) or the BachBot model of (citet Liang et al. 2017)). We
provide a more comprehensive review of existing harmonization models in
Section 2.

Existing methods have important limitations. Because such methods use complex
models for learning chorale features, they typically do not embed the guiding
principles that underlie composition. The expectation is that such models will
learn these rules from data, but this learning is not perfect, and results
often lack the musical coherence present in human-written harmonizations. This
is particularly salient for Baroque chorales due to their highly organized
harmonic structure, but is also pertinent for other musical genres.
Furthermore, by ignoring structure provided by compositional principles, such
harmonization models require a large amount of training data to learn this
structure, not to mention idiosyncratic characteristics of given composers.
For certain use cases, the training sample size needed for satisfactory model
training may not even be available, resulting in unsatisfactory performance.
Even when such data are available, training the harmonization model with large
datasets can be computationally expensive, error-prone, and difficult to
troubleshoot or tune.

In our work, we adopt a “theory-driven” learning model which emulates the
process an expert musician may use for harmonization (citep (Andrews and
Sclater, 1993)). For Baroque chorales, this harmonization process typically
involves (i) generating the tonal and harmonic progressions from the given
melodic line and (ii) using the progressions to generate voice-leading for the
remaining voices. To mimic Step (i), our proposed model learns the
relationship between the given melody and local tonalities (or keys) of the
chorale as well as the relationship between the melody and the underlying
harmonic progression. The tonal and harmonic progressions can then be
efficiently inferred via either Viterbi decoding (citep (Viterbi, 1967)) or
posterior decoding (citep (Russell and Norvig, 2002)). Once the “backbone” of
the chorale – its tonal and harmonic progressions – is generated, we mimic
Step (ii) by building a probabilistic model for harmonization under the
inferred progression subject to Baroque compositional guidelines.

Our model, which we call BacHMMachine, provides an efficient, theory-guided,
interpretable, flexible, and easy-to-tune approach to the chorale
harmonization problem. Human experiments suggest preference for BacHHMachine
compared to the best black-box harmonization methods. The proposed method also
yields great computational savings compared to the state-of-the-art –
$\sim$30x faster than Google’s Coconet (citep (Dinculescu et al., 2019)) in
generating chorales and $\sim$1,000x faster than the approach of (citet Allan
and Williams (2004)). Furthermore, Turing tests suggest a surprisingly good
ability to generate convincing chorales. Finally, as we can interpret the
model directly, we are able to gain insights into music composition that
cannot be obtained using existing methods.

Given that chorales come from the same origins as many other genres of Western
music, our harmonization model naturally extends to such genres as well. In
particular, we show in Section 4.4 that the proposed BacHMMachine approach
extends quite naturally to the harmonization of modern rock music. We also
note that, compared to many existing methods, because our transition matrices
are interpretable, humans can manually adjust them to their own taste. This
would not be possible with a complex black-box approach.

##  1 Musical Background

We first provide background on the underlying musical structure for
BacHMMachine using the four-part Baroque chorales of J.S. Bach, then show
later how similar music theories can be used for harmonizing melodies of
different musical genres. Figure 1 shows an excerpt of one such Bach chorale.
Here, the soprano (top) voice line in a chorale is the melody of the chorale,
often taken from pre-existing hymn tunes. This melody can be interpreted as
the “horizontal” aspect of a piece of music. On the other hand, harmony
involves the relationship between the notes of the chorale sung simultaneously
in different voices. In this sense, harmony is often viewed as the “vertical”
aspect of music. Music theorists (citep (see, e.g., Rameau, 1722)) typically
classify vertical harmony using Roman numeral notation (e.g., I, IV, V), with
different numerals describing unique structures. For instance, “I” represents
triadic harmony built on the tonic scale degree (the first note of the scale),
while “V7” represents a “seventh” chord built on the dominant scale degree
(the fifth note of the scale). An example is provided in Figure 1.

Figure 1: Annotated excerpt of J.S. Bach’s chorale harmonization, Jesu, deine
tiefen Wunden, BWV 194/6

Music of the Baroque era usually follows a harmonic framework known as the
“phrase model” (citep (Laitz, 2016; White and Quinn, 2018, see Figure 2)).
This framework dictates that harmonies should progress from those functioning
as tonic (I, VI, III) to those functioning as predominant (II, IV, VI) or
dominant (V, VII). Predominants lead to dominants, and dominants resolve back
to tonics. Within each functional category (tonic, predominant, or dominant),
harmonies tend to progress by root relations of a descending third or fifth.
Harmonic progressions that go against the phrase model are known as
retrogressive and rarely occur in Baroque music. Chorales that satisfy the
phrase model yield musically cohesive harmonic progressions; those that do not
may sound improperly resolved, and are musically displeasing.

Figure 2: Visualizing the phrase model harmonic framework (citep (Laitz,
2016)). Here, chords (denoted by numerals) may be major, minor, or diminished.

Another important aspect of chorale composition is the relationship between
local tonalities. Tonality refers to a musical passage’s centricity around a
single tone, where other tones in the musical environment are hierarchically
related to the central pitch. Temporary transitions from one tonality (or key)
to another, or modulations, are widely used to provide a more engaging and
complex harmonic structure. Like surface-level harmonic progressions, deeper
tonal shifts in music also usually follow the phrase model. The sequence of
tonal shifts in a chorale, or its key progression, is integral to a chorale’s
musical signature. Figure 1 shows the modulation from the tonic key of B-flat
major to F major, then back to B-flat major.

Additional rules should be followed for pleasing and convincing chorale
harmonizations. For instance, there are rules regarding chord inversions in
the bass voice, and principles prescribing which chord notes can be doubled or
omitted. To ensure a full sound, the soprano and alto voices and the alto and
tenor voices should stay within an octave of each other. Notes in an upper
voice should be relatively stable with sparing use of melodic leaps. Parallel
fifths and octaves are strongly discouraged as they erode voice independence
and are distracting to the listener. Non-chord tones (such as suspensions,
passing, and neighboring tones) may be added to smooth voice leading and add
rhythmic diversity (see Figure 1).

##  2 Existing Harmonization Methods

Existing methods can be broadly grouped into those relying on Markovian models
and those based on deep learning. (citet Yi and Goldsmith (2007)) use a
factored Markov decision processes planner to generate chordal progressions
based on input melody. However, their resulting harmonization (see Figure 3)
has serious flaws from a musical perspective. There are parallel octaves,
unusual note doublings, dissonant leaps in the bass, awkward voice spacing and
chord inversions (e.g., ending on $I^{6}_{4}$), and retrogressive harmonic
progressions, which result in musically displeasing harmonies.

(citet Kaliakatsos-Papakostas and Cambouropoulos (2014)) introduce a
hierarchical modeling approach using a hidden Markov model (HMM), with user-
specified fixed-chords as “anchors,” and generation of chords connecting them.
Using a second HMM, they produce the bass voice given the chordal progression
produced by the first model. Although introducing chord constraints is
musically interesting, the reliance on human experts to manually insert fixed
chords can make the harmonization process less flexible. Additionally, their
study also fails to incorporate non-chord tones and does not always adhere to
Baroque composition principles.

Figure 3: Violations of compositional principles for the chorale harmonization
in (citet Yi and Goldsmith (2007)).

(citet Allan and Williams (2004)) propose a more musically agnostic approach
that uses HMMs to generate chordal progressions. A first HMM is used to
generate chord notes and a second HMM adds non-chord notes decorating the
harmonization. One drawback is its overly large search space, requiring over
2,800 hidden states for chorale representation! One reason is that, for this
model, hidden states represent the unique sequence of intervals from the bass
note. As such, there are many musically redundant hidden states that represent
the same chord with different transpositions. In contrast, we adopt a more
musically-informed (and much smaller) state space which captures tonality and
chordal structure.

Some notable studies in chorale harmonization use deep learning methods.
HARMONET (citep (Hild et al., 1991)) is a hierarchical architecture containing
five neural nets determining chordal progression, chord inversions, the bass
note, and non-chord notes. Two recent approaches using neural networks are
DeepBach and BachBot. DeepBach (citep (Hadjeres et al., 2017)) is a graphical
model that generates four-part chorales using recurrent neural networks, while
BachBot (citep (Liang et al., 2017)) is an automatic composition system that
uses a deep long short-term memory model. Both approaches are supposedly
agnostic as they “rely on little musical knowledge.” Likely because of this,
generated harmonizations from such approaches often violate important
composition guidelines. Furthermore, these deep neural networks require a
large training set and are less interpretable and harder to tune than HMMs.

##  3 BacHMMachine

What distinguishes our approach from existing work is the emphasis on
emulating harmonization procedures of trained musicians that incorporate
genre-specific composition conventions. Our model includes three important
novel elements: key modulation, data representation of each chord by its Roman
numeral (including inversions), and strictly following chord inversion and
voice-crossing constraints.

Modulation: Existing methods generally focus only on chord transitions, with
chords assumed to belong to only one key throughout the entire piece. However,
chord transitions also depend on their location with respect to the whole
piece and presence of modulation, and thus existing methods do not capture
these musically important nuances, overlooking the prevalence and importance
of key modulation in Bach chorales and other musical genres. To produce an
authentic-sounding harmonization, it is crucial to take into account the key
transitions in addition to the chord transitions.

Chord-Equivalence Representation: Many existing methods treat any concurrent
vertical combination of notes as a unique chord. However, functionally
identical chords might occur in different forms (e.g., inversions,
transpositions). To reduce dimensionality of the emission and transition
matrices, we treat these different forms as one, as is typical in chorale
analysis. We consider only 31 unique chords in our training set and transpose
all chorales to C major or A minor, greatly reducing search space and training
time. We emphasize the underlying structure (chordal progression and key
modulation) rather than absolute pitches of notes.

Harmonization Constraints: For chorales, we impose basic harmonization
constraints when specifying each voice line. On a chord-level, we strictly
follow the chord inversion and voice crossing constraints, with combinations
of notes violating them not considered in the final harmonization. On a
chorale-level, once we generate possible harmonizations for the input melody,
we check them for potential violations of composition guidelines and assign a
penalty whenever a violation (e.g., voice crossing between chords, large
jumps, parallel fifths/octaves) occurs. We output the harmonization with the
lowest overall penalty. As mentioned earlier, many such harmonization
principles are not exclusive to only Bach chorales, but for a wide range of
musical genres (we will demonstrate this flexibility later for the
harmonization of a rock song).

###  3.1 Key-Chord Hidden Markov Model

The first step in our harmonization framework is to infer plausible key and
chordal progressions given an input melody. This is achieved by a novel Key-
Chord HMM model which integrates tonality and chordal structure to achieve
efficient, scalable and interpretable harmonization.

Let $\mathbf{M}=(m_{1},\cdots,m_{n})$ be the given melody line, with $m_{t}$
the melody note at time $t$ (i.e., on the $t^{\textrm{th}}$ beat). This can be
seen as a sequence of visible states for the HMM. Let
$\mathbf{K}=(k_{1},\cdots,k_{n})$ be the hidden key progression capturing the
modulation of the chorale, with $k_{t}\in\mathcal{K}$ the key at time $t$,
where $\mathcal{K}$ is the state space of 24 keys (12 major, 12 minor). Let
$\mathbf{C}=(c_{1},\cdots,c_{n})$ be its hidden chordal progression, with
$c_{t}\in\mathcal{C}$ the particular chord at time $t$, where $\mathcal{C}$ is
the state space of 31 chords. We aim to recover (or decode) the sequences of
keys and chords $\mathbf{K}$ and $\mathbf{C}$ from the melody $\mathbf{M}$.

We build the Key-Chord HMM in two stages, first for the key progression, then
for the chordal progression. For the key sequence $\mathbf{K}$, we impose the
following first-order Markovian model on transition probabilities:

$\displaystyle\begin{split}&\mathbb{P}(k_{t+1}|k_{1},...,k_{t})=\mathbb{P}(k_{t+1}|k_{t})=:T^{K}_{k_{t},k_{t+1}},\end{split}$
(1)

for $t=1,\cdots,n$. Here, $T^{K}_{k_{t},k_{t+1}}:=\mathbb{P}(k_{t+1}|k_{t})$
denotes the transition probability from key $k_{t}$ to $k_{t+1}$, which we
estimate using chorale data. This first-order Markovian assumption is standard
for HMMs, and can be justified by the earlier phrase model chordal structure.
Given key $k_{t}$, we assume that $m_{t}$, the melody note at time $t$,
depends only on $k_{t}$, i.e.:

$\displaystyle\begin{split}\mathbb{P}(m_{t}|k_{1},...,k_{t},m_{1},...,m_{t-1})=\mathbb{P}(m_{t}|k_{t})=:E_{k_{t},m_{t}}^{K},\end{split}$
(2)

for $t=1,\cdots,n$. Here, $E_{k_{t},m_{t}}^{K}$ denotes the emission
probability of melody note $m_{t}$ from key $k_{t}$. This is again a standard
HMM assumption, justifiable by the earlier discussion that the melody line can
be well-characterized by its underlying tonality and chord quality.

Next, for the chord sequence $\mathbf{C}$, we presume that the key sequence
has already been decoded from data (call this inferred sequence
$\mathbf{K}^{*}$, more on this in the next subsection). We again adopt a
first-order Markovian model for transition probabilities:

$\displaystyle\begin{split}&\mathbb{P}(c_{t+1}|c_{1},...,c_{t})=\mathbb{P}(c_{t+1}|c_{t})=:T^{C}_{c_{t},c_{t+1}},\end{split}$
(3)

for $t=1,\cdots,n$. Here, $T^{C}_{c_{t},c_{t+1}}:=\mathbb{P}(c_{t+1}|c_{t})$
denotes the transition probability from chord $c_{t}$ to $c_{t+1}$, which we
estimate from data. This can again be reasoned by the earlier phrase model.
Given the inferred key $k_{t}^{*}$ and chord $c_{t}$, we then assume that the
transposed melody note $\delta_{t}=m_{t}-k_{t}^{*}$ (i.e., modulo key change)
follows the model:

$\displaystyle\begin{split}\mathbb{P}(\delta_{t}|c_{1},...,c_{t},\delta_{1},...,\delta_{t-1})=\mathbb{P}(\delta_{t}|c_{t})=:E^{C}_{c_{t},\delta_{t}},\end{split}$
(4)

for $t=1,\cdots,n$. This leverages the observation that similar harmonic
structures are used over different tonalities. Figure 4 visualizes the Key-
Chord HMM model: the observed states are the input soprano melody line and the
hidden states are the underlying keys and chords.

Figure 4: Key-Chord HMM Visualization.

In practice, both the emission probabilities $E^{K}$ and $E^{C}$, as well as
key and chord transition probabilities $T^{K}$ and $T^{C}$, must be estimated
from chorale training data. We adopt the following hybrid estimation approach.
First, to ensure the harmonization does not violate progressions from the
phrase model, we set the probabilities of retrogressive chord transitions
(i.e., those violating the phrase model) to be near zero. The remaining
parameters are then estimated from the training data using maximum likelihood
estimation (citep (Casella and Berger, 2021)). This ensures our model not only
generates musically coherent chordal progressions in line with compositional
principles, but also permits us to learn a composer’s creative style under
such constraints. Our proposed model requires substantially fewer parameters
than existing HMM harmonization models (specifically (citep Allan and
Williams, 2004), which requires estimation of over $2,800^{2}$ transition
probabilities). As shown later, this yields a computationally efficient and
interpretable harmonization model, competitive with state-of-the-art models in
terms of harmonization quality.

####  3.1.1 Inferring Hidden Keys and Chords

We employ two approaches for inferring the underlying hidden key-chord
sequence from the Key-Chord HMM.

Viterbi Decoding: The Viterbi decoding algorithm (citep (Viterbi, 1967)) is a
popular dynamic programming method for inferring hidden states in HMMs and is
widely used in signal processing, natural language processing (citep
(Jurafsky, 2000)), and other fields. Here, a two-step implementation of the
Viterbi algorithm allows for efficient inference of the underlying key and
chord sequences.

Given melody line $\mathbf{M}$, the key inference problem can be formulated as

$\mathbf{K}^{*}\in\text{arg}\,\max\limits_{\mathbf{K}}\,\mathbb{P}(\mathbf{K}|\mathbf{M}).$
(5)

Here, $\mathbb{P}(\mathbf{K}|\mathbf{M})$ is the posterior probability of a
certain key sequence $\mathbf{K}$ given melody line $\mathbf{M}$ under the
Key-Chord HMM. This optimization, however, involves $|\mathcal{K}|^{n}$
variables, which can be high-dimensional. The Viterbi algorithm provides an
efficient way to solve this optimization problem via dynamic programming. In
our implementation, we used the Viterbi decoding function in the Python
package hmmlearn (citep (Lebedev et al., 2021)). Similarly, given melody line
$\mathbf{M}$ and and inferred key sequence $\mathbf{K}^{*}$, the chord
inference problem can be formulated as

$\mathbf{C}^{*}\in\text{arg}\,\max\limits_{\mathbf{C}}\,\mathbb{P}(\mathbf{C}|\mathbf{M}-\mathbf{K}^{*}).$
(6)

This can again be efficiently solved via the Viterbi algorithm, with the
observed states now taken to be the transposed melody
$\mathbf{M}-\mathbf{K}^{*}$. Algorithm 1 outlines this two-stage Viterbi
algorithm for inferring the underlying key-chord sequence
$(\mathbf{K}^{*},\mathbf{C}^{*})$.

Algorithm 1 Key-Chord Viterbi decoding

Viterbi decoding for keys:

  * •

Set $V_{0}^{\rm K}(0)\leftarrow 1,V_{k}^{\rm K}(0)\leftarrow 0$ for all
$k\in\mathcal{K}$.

  * •

For $t=0,\cdots,n-1$, update for all $k\in\mathcal{K}$

$\displaystyle V_{k}^{\rm K}(t+1)$
$\displaystyle\leftarrow\max\limits_{i\in\mathcal{K}}\left\\{V_{i}^{\rm
K}(t)E^{K}_{k,m_{t+1}}T^{K}_{i,k}\right\\}.$

  * •

Set $\mathbf{K}^{*}$ as the key sequence achieving
$\max_{i\in\mathcal{K}}V_{i}^{\rm K}(n).$

Viterbi decoding for chords:

  * •

Set $V_{0}^{\rm C}(0)\leftarrow 1,V_{c}^{\rm C}(0)\leftarrow 0$ for all
$c\in\mathcal{C}$.

  * •

For $t=0,\cdots,n-1$, update for all $c\in\mathcal{C}$

$\displaystyle V_{c}^{\rm C}(t+1)$
$\displaystyle\leftarrow\max\limits_{i\in\mathcal{C}}\left\\{V_{i}^{\rm
C}(t)E^{C}_{c,m_{t+1}-k_{t+1}^{*}}T^{C}_{i,c}\right\\}.$

  * •

Set $\mathbf{C}^{*}$ as the chord sequence achieving
$\max_{i\in\mathcal{C}}V_{i}^{\rm C}(n).$

Posterior Decoding: Posterior decoding provides an alternate approach for
hidden state inference. Instead of finding the key and chord sequences that
maximize the joint posterior probabilities $\mathbb{P}(\mathbf{K}|\mathbf{M})$
and $\mathbb{P}(\mathbf{C}|\mathbf{M})$, posterior encoding finds the key-
chord combination $(k_{t},c_{t})$ that maximizes the marginal posterior
probabilities $\mathbb{P}(k_{t}|\mathbf{M})$ and
$\mathbb{P}(c_{t}|\mathbf{M})$ at each time $t$. As with the earlier key-chord
Viterbi decoding, an analogous two-step procedure can be used for key-chord
posterior decoding, by performing the forward-backwards algorithm (an
efficient posterior decoding algorithm, see (citet Russell and Norvig 2002))
first for keys, then for chords. Both the Viterbi algorithm and posterior
encoding are widely used for HMM decoding, and we employ both in our
experiments.

###  3.2 Harmonization Model

In the second step, we use the inferred key-chord progression to generate the
harmonization. From music theory, each chord admits a limited number of note
arrangements over the available voices, and is subject to certain constraints
to ensure a musically coherent harmonization. We embed the following
constraints within our Baroque chorale model:

  1. 1.

No voice crossings: the harmonization must maintain the Soprano-Alto-Tenor-
Bass (SATB) order vertically.

  2. 2.

Voice lines should stay in their vocal range: alto notes should be between
F3-D5, tenor notes between B2-G4, and bass notes between E2-C4.

  3. 3.

Voice spacing: the soprano and alto voices should not be more than an octave
apart; the same should also hold for the alto and tenor voices.

  4. 4.

Chord structure: chords should obey their specific inversion and note doubling
guidelines; see (citet Andrews and Sclater (1993)) for a detailed discussion
of such rules.

Given the generated progression, we enumerate chord arrangements
$\mathbf{a}_{t}^{[1]},\mathbf{a}_{t}^{[2]},...$ that satisfy the above
vertical constraints at time $t$. A chord arrangement
$\mathbf{a}_{t}\in\mathbb{R}^{3}$ represents the alto, tenor, and bass notes.
Given a selected chord arrangement $\mathbf{a}_{t}$, we iterate through all
possible consecutive chord arrangement pairs
$(\mathbf{a}_{t},\mathbf{a}_{t+1}^{[1]}),(\mathbf{a}_{t},\mathbf{a}_{t+1}^{[2]}),...$
and select the $\mathbf{a}_{t+1}$ that minimizes the Euclidean distance
between the consecutive chord arrangements. With different chord arrangements
at the first beat, different harmonizations can be generated for a given
chorale. In the case of a tie, we check for horizontal constraints such as
voice crossings and parallel intervals. We allow occasional constraint
violations (with a penalty incurred when violations are found), and select the
harmonization with the lowest penalty.

###  3.3 Non-Chord Notes

We further diversify the rhythm of the generated chorale harmonization by
adding non-chord notes: ornamentation notes which do not belong to the given
chordal progression. While there are a variety of non-chord tones (see (citep
Andrews and Sclater, 1993)), we focus on the following types:

  1. 1.

Passing notes between neighboring notes a third apart.

  2. 2.

Auxiliary notes between two repeated chord notes.

  3. 3.

Appoggiaturas, or non-chord notes on strong beats.

These non-chord notes are added probabilistically and independently at each
beat, with probabilities estimated from training chorales or specified
manually.

###  3.4 Data

We use the Bach chorale corpus and chorale analyses provided in the Music21
toolkit (citep (Cuthbert and Ariza, 2021)), dividing chorales into those in
major vs. minor keys. When processing chorale data, we treat quarter notes as
the unit for one time step. Notes lasting more than one beat are split on a
per-beat basis, and notes lasting less than one beat are grouped into a list
of notes that together span one beat. At each time step, melody notes are
represented by their corresponding MIDI pitches, chords are represented using
Roman numeral notation, and keys are represented using letters. We note that
the data used to fit BacHMMachine is different from the data used in past
studies. Instead of using raw note data corresponding directly to pitches, we
use the annotated chorales (containing chordal and modulation information, see
Figure 1) which are proofread by music theorists (citep (Jones et al., 2021)).

For our rock data, we use the “Corpus Study of Rock Music” in (citet Temperley
and deClercq (2011)), which consists of analyses for the top 200 “Greatest
Songs of All Time,” as judged by Rolling Stone magazine. (citet Temperley and
deClercq (2011)) provide onset timings for every melodic note and Roman
numeral, as well as measure onsets. To keep the rock data consistent with the
Bach chorale data, we reduce the dataset to songs that are in major keys and
quadruple time (such as 4 4 or 12 8). Keys and scale degrees are represented
as integers from 0 to 11, describing absolute chromatic pitch
($C=0,C\sharp/D\flat=1,\dots,B=11$). For our study, Roman numerals were
simplified to triadic, root-position form in order to reduce model complexity.
We collect one representative Roman numeral, key, and melodic scale degree for
every measure. The numeral, key, and scale degree of the longest duration in
each measure serve as our HMM’s hidden and observed states respectively.

##  4 Experiments

In the following section we discuss our experiments regarding both the Bach-
style chorale and rock harmonizations. Our experiments show how our method for
chorale harmonization compares to others in terms of audience preference and
training/harmonization time. We also show how BacHMMachine may be simply
adjusted to work for other genres by generating harmonizations for rock
melodies. All audio generated by BacHMMachine for our experiments may be found
in the playlist linked below.

$\href https://soundcloud.com/stephen-hahn-533617325/sets/bachmmachine-
harmonizations/s-jropckP2g23?si=d79e6d1be7dc4ee3b53440ac13f62868&utm_source=clipboard&utm_medium=text&utm_campaign=social_sharing$

###  4.1 Bach Chorale Harmonization: Set-Up

To assess performance of BacHMMachine’s chorale harmonizations, we conducted
audience-preference experiments comparing our harmonizations to those
generated by the existing state-of-the-art algorithmic harmonization models.
The first experiment (_Exp. 1_) compares the proposed BacHMMachine with the
approach in (citet Allan and Williams (2004)), and the second experiment
(_Exp. 2_) compares BacHMMachine with Google’s Coconet model (citep (Huang et
al., 2017; Dinculescu et al., 2019)), which was featured on Google’s homepage
on Bach’s 334th birthday. We further conducted a preference experiment and
Turing test using Bach’s original harmonizations (_Exp. 3_). Finally, we
compared the BacHMMachine with either Viterbi or posterior decoding (_Exp.
4_), and with or without the use of non-chord notes (_Exp. 5_). Each
participant evaluated chorales generated from each of these five experiments,
and also one set of “sanity-check” questions which compare the original Bach
chorale to one deliberately composed to be unpleasant and dissonant.

For each experiment, we randomly selected an existing major key chorale and
used the soprano voice as the input melody. We displayed two video files, each
showing the harmonization generated by one of the methods. Video files
presented a scrolling score and highlighted notes as they were sung in SATB
voices. We blinded the label of each harmonization. To account for order
effects, the harmonization generated using BacHMMachine had a 50% chance of
being first or second. Respondents could pause and replay videos an unlimited
number of times. Following the videos, we asked respondents their preference
regarding the two harmonizations presented. Exp. 3 contained an additional
Turing test question asking which harmonization was composed by Bach.
Responses were evaluated on a five-point Likert scale that accounted for the
random ordering of each harmonization pair presented.

We launched all surveys on Amazon Mechanical Turk (MTurk), requesting
responses from MTurk crowd-workers with master qualifications and approval
rates of >95%. We rejected any responses that failed the “sanity-check” (i.e.,
not indicating preference for Bach’s original harmonization over our
deliberately dissonant composition). Our final analysis dataset consisted of
116 participants out of 160. Among our participants, 101 (87%) reported
enjoyment of classical music or status as music students or professionals;
only 15 (13%) reported seldom listening to classical music.

###  4.2 Preference and Computational Results

Table 1 shows the preference results for Exp. 1, Exp. 2, and Exp. 3. We see
that more respondents preferred BacHMMachine’s harmonizations to those
generated by both the Allan and Williams’ implementation (citep (Mammana et
al., 2019)) and Google’s Coconet application (citep (Dinculescu et al.,
2019)), suggesting that the quality of BachHMMachine’s harmonization is as
good as, if not better, than the existing harmonization approaches. We also
see that more respondents preferred Bach’s original harmonizations to ours,
which is not at all surprising. However, only 13.8% of respondents identified
Bach’s original harmonizations with certitude according to the results of the
Turing test (Table 2), with 36 (31%) respondents believing to some degree that
our harmonization was more likely to have been composed by Bach. This result
suggests that, while BacHMMachine might not have captured all of Bach’s
creative idiosyncrasies, it can produce musically convincing four-part chorale
harmonizations on par with (if not better than) those generated by more
complex methods. For methodological choices regarding BacHMMachine evaluated
in Exp. 4 and Exp. 5, Table 3 suggests that more respondents preferred our
harmonizations generated using posterior decoding and with non-chord notes.

Exp. 1: Comparison to Allan and Williams | $n$ | (%)
---|---|---
Definitely prefer BacHMMachine | 32 | (27.6%)
Somewhat prefer BacHMMachine | 33 | (28.4%)
No preference | 2 | (1.7%)
Somewhat prefer Allan and Williams | 25 | (21.6%)
Definitely prefer Allan and Williams | 24 | (20.7%)
Exp. 2: Comparison to Google’s Coconet |  |
Definitely prefer BacHMMachine | 26 | (22.4%)
Somewhat prefer BacHMMachine | 33 | (28.4%)
No preference | 11 | (9.5%)
Somewhat prefer Coconet | 30 | (25.9%)
Definitely prefer Coconet | 16 | (13.8%)
Exp. 3: Comparison to original Bach |  |
Definitely prefer BacHMMachine | 20 | (17.2%)
Somewhat prefer BacHMMachine | 23 | (19.8%)
No preference | 9 | (7.8%)
Somewhat prefer original Bach | 41 | (35.3%)
Definitely prefer original Bach | 23 | (19.8%)
Table 1: Comparison of harmonization approaches: “Which harmonization do you prefer?” | $n$ | (%)
---|---|---
Definitely BacHMMachine | 10 | (8.6%)
Somewhat BacHMMachine | 26 | (22.4%)
No preference | 22 | (19.0%)
Somewhat original Bach | 42 | (36.2%)
Definitely original Bach | 16 | (13.8%)
Table 2: Turing test: “Which was composed by Bach?” Exp. 4: Posterior decoding vs. Viterbi | $n$ | (%)
---|---|---
Definitely prefer Posterior decoding | 24 | (20.7%)
Somewhat prefer Posterior decoding | 33 | (28.4%)
No preference | 16 | (13.8%)
Somewhat prefer Viterbi | 26 | (22.4%)
Definitely prefer Viterbi | 17 | (14.7%)
Exp. 5: Inclusion of non-chord notes |  |
Definitely prefer no non-chord notes | 16 | (13.8%)
Somewhat prefer no non-chord notes | 32 | (27.6%)
No preference | 15 | (12.9%)
Somewhat prefer with non-chord notes | 30 | (25.9%)
Definitely prefer with non-chord notes | 23 | (19.8%)
Table 3: Comparison of BacHMMachine decoding approaches: “Which harmonization
do you prefer?”

Table 4 reports the computation time (in seconds) needed to train each of the
three algorithms on the same eight chorales, as performed on a personal
computer using a 1.8 GHz Dual-Core Intel Core i5 processor. The reported
results are the averages of 5 algorithm runs. We see that the training time
for the Allan and Williams’ algorithm is $\sim$1,000x that of the proposed
BacHMMachine. After both models are trained, the harmonization of a new
chorale can be performed very quickly (under a second). Unfortunately, we
cannot compare the model training time for Google’s Coconet, since the
application was already pre-trained. However, the computation time for
Coconet’s trained model to harmonize a new chorale is $\sim$30x longer than
that of BacHMMachine. This significant edge in computation time (either for
model training or harmonization) for BacHMMachine shows that the proposed
approach is indeed much more scalable than the state-of-the-art. This is again
due, in large part, to the integration of compositional principles within the
harmonization model, which allows for model reduction and efficient training.

Approach | Train time | Harmonization time
---|---|---
BacHMMachine | 6.27 | 0.60
Allan and Williams | 6175.05 | 0.56
Google’s Coconet | (unknown) | 18.56
Table 4: Comparison of training time on 8 chorales and harmonization time
(given the trained model) in seconds.

###  4.3 Model Interpretability

Figure 5: Annotated excerpt of the BacHMMachine harmonization of melody from
J.S. Bach’s chorale _Ach Gott und Herr_ , BWV 255.

Figure 5 shows an excerpt of a harmonized chorale using BacHMMachine, with
posterior decoding and including non-chord notes. A careful musical analysis
of this shows the generated harmonization satisfies much of the compositional
principles desired for Baroque chorale composition. We investigate this
further below.

Figure 6 visualizes the key transition probabilities learned by BacHMMachine.
There are several observations of interest. First, as expected, we see that
the estimated key probabilities strongly conform to the phrase model. Second,
we see that key transition probabilities demonstrate a high degree of key
stability, meaning that the generated chorales only change keys approximately
once per phrase. This frequency of key changes is similar to Bach chorale
harmonizations. Finally, we also observe that all keys have a strong
probability of modulating back to the tonic, with the next most common
destination being the dominant, which again is in line with musical
expectation (citep (Laitz, 2016)). This shows that, by integrating
compositional principles within the harmonization model, BacHMMachine can
learn interpretable stylistic features which are verifiable from music theory.

$\href https://soundcloud.com/stephen-hahn-533617325/bachmmachine-
harmonizations-bwv255-posterior-decoding/s-dmKUueTAJ3r?in=stephen-
hahn-533617325/sets/bachmmachine-
harmonizations/s-jropckP2g23&utm_source=clipboard&utm_medium=text&utm_campaign=social_sharing$

Figure 6: Estimated key transition probabilities (%) in the trained
BacHMMachine model.

(a) Estimated chord transition probabilities in the BacHMMachine model trained
on Bach chorale harmonizations.

(b) Estimated chord transition probabilities in the BacHMMachine model trained
on (citet Temperley and deClercq (2011))’s rock analyses within (citet Laitz
(2016))’s phrase model.

Figure 7: Estimated chord transition probabilities in the BacHMMachine model,
grouped by tonic (T), predominant (PD) and dominant (D) chords.

Figure 7(a) visualizes the chord transition probabilities learned by
BacHMMachine, organized by the tonic (T), predominant (PD) and dominant (D)
chord groups from the phrase model (see Figure 2). We see that, as expected,
the estimated chord probabilities from BacHMMachine closely follow the
harmonic structure dictated by the phrase model. In particular, the model
learned that tonics progress to tonics, predominants, or dominants with near
equal probability, that most predominants progress to dominants, and that most
dominants progress to tonics. This agrees with expected chord transitions from
the phrase model (citep (Laitz, 2016)), which demonstrates the
interpretability of the proposed model in corroborating stylistic features of
Baroque chorales.

###  4.4 Harmonization of Rock Melodies

The BacHMMachine model is not only capable of harmonizing Bach chorales, but
also a wide range of musical genres that follow similar harmonization
principles. To demonstrate this flexibility, we apply this model for
harmonizing rock songs.

Our procedure for harmonizing rock melodies is similar to that for Bach
chorales. First, we generate the underlying key progression and transpose the
melody according to key. Then we determine the harmonic progression of the
melody (one numeral for each user-defined measure). The harmonic and key
progressions determine the bass line, which plays the harmonic root on every
downbeat then arpeggiates the other chord tones until the measure is full.
Electric piano plays appropriate block chords or arpeggiates the harmony.
Finally, we add a simple drum pattern to fill out the texture. Each instrument
plays a common rock rhythm, which may be determined stochastically from a
rhythmic vocabulary, or manually selected by the user.

The audio file below contains the BacHMMachine harmonization of the melody
from Procol Harum’s A Whiter Shade of Pale. From a quick listen, we find that
the generated harmonization provides a convincing imitation of a typical rock
harmonic progression. The syntactical harmonic structure of rock music is
still a hot topic for debate in music theory, so there is no consensus on a
generalized rock “phrase model” (We observe how the rock transitions relates
to the Baroque phrase model in Figure 7). However, it is clear that the blues,
which often follows a straightforward harmonic formula, had a heavy influence
on the development of rock (as blues artist Muddy Waters said, “the blues had
a baby and named it rock and roll” (citep (Waters, 1977))). Specifically, the
blues is based on variations of a simple twelve-bar progression:

$||:\quad I\quad|\quad I\quad|\quad I\quad|\quad I\quad||\quad IV\quad|\quad
IV\quad|\quad I\quad|\quad I\quad||\quad V\quad|\quad IV\quad|\quad
I\quad|\quad I\quad:||$

The trained BacHMMachine model determined that the most probable outcome for
melody harmonization consists of simple progressions involving “I,” “IV,” and
“V” in a single key (see Figure 7(b)). Hence, the progressions learned by
BacHMMachine sound very similar to that from a blues progression, and can thus
successfully imitate rock harmony.

###  4.5 Interpretability Permits User Interactions

A benefit of BacHMMachine’s model interpretability is the fact that humans can
edit the transition probabilities if desired. In fact, the rock progressions
primarily involving “I,” “IV,” and “V” in a single key might be undesirable
for some users. The simple structure of BacHMMachine allows us to manipulate
the transition matrices to produce more interesting and personal results. Our
playlist includes a purely data-driven harmonization and another harmonization
after manually adjusting the transition probabilities to involve a greater
chord diversity.

$\href https://soundcloud.com/stephen-hahn-533617325/bachmmachine-
harmonization-a-whiter-shade-of-
pale/s-HltCil56dBU?si=a3e6de762a194e5da642b9ea7a342e82&utm_source=clipboard&utm_medium=text&utm_campaign=social_sharing$

$\href https://soundcloud.com/stephen-hahn-533617325/bachmmachine-
harmonization-a-whiter-shade-of-pale-v2/s-VPVTowY0CBE?in=stephen-
hahn-533617325/sets/bachmmachine-
harmonizations/s-jropckP2g23&si=3139f23ef59e44668fa2fc72e5905832&utm_source=clipboard&utm_medium=text&utm_campaign=social_sharing$

The custom matrix simply boosted the probability of encountering non-major
diatonic harmonies (ii, iii, vi, viio) as well as $\flat$VII, all of which
were largely avoided by the data-driven transition matrix. This kind of simple
adjustment to the transition matrix can be executed quickly and provides
tremendous potential for diverse melody harmonizations.

##  5 Conclusion

In this study, we described a probabilistic framework capable of generating
musically convincing harmonizations. The main strength of the model is that it
is musically informed, emulating the harmonization process of a human composer
by incorporating musical guidelines and constraints. Because of this, we are
able to reduce the number of violations of composition guidelines. By using
professional analyses instead of raw musical pitches as input data, our method
requires considerably fewer hidden states and takes a tiny fraction of the
training time of other HMM approaches. The use of HMMs themselves leads to the
generation process being more interpretable, with faster composition times
compared to recent deep learning approaches.

Because we directly use musical information, it is straightforward to extend
our model to take advantage of additional considerations. For instance, we may
explore supplemental data-encoding schemes that discretize chorales into
smaller time units, add an additional layer regarding key modulation or pivot
chords, or consider higher-order Markovian models. Regardless, it is clear
that by incorporating musical principles in our model, we are able to achieve
high-quality harmonization with much simpler and easily-interpretable models
at a tiny fraction of the computational cost. We encourage future researchers
to consider such domain-specific information when designing generative models
to hopefully achieve similar results.

## References

  * Allan and Williams [2004] Moray Allan and Christopher K. I. Williams.  Harmonising chorales by probabilistic inference.  In _Proceedings of Neural Information Processing Systems_ , 2004.
  * Andrews and Sclater [1993] William G. Andrews and Molly Sclater.  _Materials of Western Music: Part 1_.  Gordon V. Thompson Music, 1993.
  * Casella and Berger [2021] George Casella and Roger L Berger.  _Statistical Inference_.  Cengage Learning, 2021.
  * Cuthbert and Ariza [2021] Michael Scott Cuthbert and Christopher Ariza.  Music21: A toolkit for computer-aided musicology and symbolic music data, 2021.  URL https://github.com/cuthbertLab/music21.
  * Dinculescu et al. [2019] Monica Dinculescu, Cheng-Zhi Anna Huang, Tim Cooijmans, Adam Roberts, Aaron Courville, and Douglas Eck.  Coconet coucou, 2019.  URL http://coconet.glitch.me/.
  * Fux [1725] Johann Joseph Fux.  _Gradus ad Parnassum (Steps or Ascent to Mount Parnassus)_.  W. W. Norton & Company, 1725.
  * Hadjeres et al. [2017] Gaëtan Hadjeres, F. Pachet, and F. Nielsen.  DeepBach: a steerable model for Bach chorales generation.  In _Proceedings of the 34th International Conference on Machine Learning_ , 2017.
  * Hild et al. [1991] H. Hild, J. Feulner, and W. Menzel.  HARMONET: A neural net for harmonizing chorales in the style of J. S. Bach.  In _Proceedings of Neural Information Processing Systems_ , 1991.
  * Huang et al. [2017] Cheng-Zhi Anna Huang, Tim Cooijmans, Adam Roberts, Aaron Courville, and Douglas Eck.  Counterpoint by convolution.  In _International Society for Music Information Retrieval (ISMIR)_ , 2017.
  * Jones et al. [2021] Andrew Jones, Dmitri Tymoczko, and Hamish Robb.  Music21 corpus: Bach chorale analyses, 2021.  URL https://github.com/cuthbertLab/music21/tree/master/music21/corpus/bach/choraleAnalyses.
  * Jurafsky [2000] Dan Jurafsky.  _Speech & Language Processing_.  Pearson Education India, 2000.
  * Kaliakatsos-Papakostas and Cambouropoulos [2014] Maximos A. Kaliakatsos-Papakostas and E. Cambouropoulos.  Probabilistic harmonization with fixed intermediate chord constraints.  In _Proceeding of the Joint 11th Sound and Music Computing Conference (SMC) and 40th International Computer Music Conference (ICMC)_ , 2014\.
  * Laitz [2016] Steven Laitz.  _The Complete Musician: An Integrated Approach to Tonal Theory, Analysis, and Listening_.  Oxford University Press, 2016.
  * Lebedev et al. [2021] Sergei Lebedev, Anthony Lee, Gael Varoquaux, and Chris Farrow.  hmmlearn: Unsupervised learning and inference of Hidden Markov Models, 2021.  URL https://github.com/hmmlearn/hmmlearn.
  * Liang et al. [2017] Feynman T. Liang, Mark Gotham, Matthew Johnson, and J. Shotton.  Automatic stylistic composition of Bach chorales with deep LSTM.  In _International Society for Music Information Retrieval_ , 2017\.
  * Mammana et al. [2019] Lorenzo Mammana, Eric Nisoli, Allan Moray, and Christopher Williams.  Generation of Bach chorales harmonisation using Hidden Markov Models, 2019.  URL https://github.com/lorenzomammana/py-bach-harmonisation.
  * Rameau [1722] Jean-Philippe Rameau.  _Treatise on Harmony_.  Dover Publications, 1722.
  * Russell and Norvig [2002] Stuart Russell and Peter Norvig.  _Artificial Intelligence: A Modern Approach_.  Pearson, 2002.
  * Temperley and deClercq [2011] David Temperley and Trevor deClercq.  A corpus analysis of rock harmony.  _Popular Music_ , 30:47–70, 2011.  URL http://rockcorpus.midside.com/index.html.
  * Viterbi [1967] Andrew Viterbi.  Error bounds for convolutional codes and an asymptotically optimum decoding algorithm.  _IEEE Transactions on Information Theory_ , 13(2):260–269, 1967.
  * Waters [1977] Muddy Waters.  The blues had a baby and they named it rock and roll, pt. 2, 1977.
  * White and Quinn [2018] Christopher WM White and Ian Quinn.  Chord context and harmonic function in tonal music.  _Music Theory Spectrum_ , 40(2):314–335, 11 2018\.  ISSN 0195-6167.  doi: 10.1093/mts/mty021.  URL https://doi.org/10.1093/mts/mty021.
  * Yi and Goldsmith [2007] Liangrong Yi and J. Goldsmith.  Automatic generation of four-part harmony.  In _Proceedings of the Conference on Uncertainty in Artificial Intelligence_ , 2007.


# Modeling Relational Patterns for Logical Query Answering over Knowledge
Graphs

Yunjie He  Mojtaba Nayyeri  Bo Xiong
University of Stuttgart
{yunjie.he, mojtaba.nayyeri<EMAIL_ADDRESS>Evgeny Kharlamov
Bosch Center for Artificial Intelligence
<EMAIL_ADDRESS>&Steffen Staab
University of Stuttgart
<EMAIL_ADDRESS>
###### Abstract

Answering first-order logical (FOL) queries over knowledge graphs (KG) remains
a challenging task mainly due to KG incompleteness. Query embedding approaches
this problem by computing the low-dimensional vector representations of
entities, relations, and logical queries. KGs exhibit relational patterns such
as symmetry and composition and modeling the patterns can further enhance the
performance of query embedding models. However, the role of such patterns in
answering FOL queries by query embedding models has not been yet studied in
the literature. In this paper, we fill in this research gap and empower FOL
queries reasoning with pattern inference by introducing an inductive bias that
allows for learning relation patterns. To this end, we develop a novel query
embedding method, RoConE, that defines query regions as geometric cones and
algebraic query operators by rotations in complex space. RoConE combines the
advantages of Cone as a well-specified geometric representation for query
embedding, and also the rotation operator as a powerful algebraic operation
for pattern inference. Our experimental results on several benchmark datasets
confirm the advantage of relational patterns for enhancing logical query
answering task.

##  1 Introduction

Answering first-order logical (FOL) queries over knowledge graphs (KGs) has
been an important and challenging problem Ren and Leskovec (2020). Among
various approaches, logical query embedding (Hamilton et al., 2018; Ren et
al., 2020; Zhang et al., 2021; Ren and Leskovec, 2020) has received huge
attention due to its great efficiency and effectiveness. Logical query
embeddings take as input the KGs and a set of first-order logical queries that
include existential quantification ($\exists$), conjunction ($\land$),
disjunction ($\lor$), and negation ($\neg$). Figure 1 shows a concrete FOL
query example that corresponds to the natural language query “List the
capitals of non-European countries that have held either World Cup or
Olympics”.

Figure 1: An example of FOL query corresponds to "List the capitals of non-
European countries that have held either World Cup or Olympics".

The methods model logic operations by neural operators that act in the vector
space. In particular, they represent a set of entities as geometric shapes and
design neural-network-based logical operators to compute the embedding of the
logical queries. The similarity between the embedded logical query and a
candidate answer is calculated to measure plausibility.

Relations in KGs may form particular patterns, e.g., some relations are
symmetric (e.g., spouse) while others are anti-symmetric (e.g.,
parent$\\_$of); some relations are the inverse of other relations (e.g.,
son$\\_$of and father$\\_$of). Modeling relational patterns can potentially
improve the generalization capability and has been extensively studied in link
prediction tasks Sun et al. (2019); Nayyeri et al. (2021). This has been shown
particularly in Sun et al. (2019) where the RotatE model utilizes the rotation
operation in Complex space to model relational patterns and enhance link
prediction task. However, current logical query embedding models adopt deep
neural logical operators and are not able to model relational patterns, which
do matter for logical query answering. Figure 2 shows concrete examples of how
relation patterns can impact complex query reasoning in KGs.

Figure 2: (_top_) An example showing how relation patterns influence query
answering over incomplete KGs: the intermediate variable Judy’s father-in-law
in the query cannot be directly extracted from the given facts; (_bottom_) An
illustration of cone rotation. Based on the existing relations between Judy,
Justin, and Ryan, and the learned potential relation patterns from other parts
of the graph, the model is able to derive the following information by
relational rotation: (i) Justin is Judy’s spouse (symmetric rotation) (ii)
Justin is the child of Ryan (inversion rotation) (iii) Ryan is Judy’s father
in law (compositional rotation). With the predicted query embedding on $V$,
the model is able to derive where $V$ graduated from by another relational
rotation.

To model and infer various KG relational patterns in logical queries answering
process, we propose a novel method called RoConE that combines the advantages
of Cone as a well-specified geometric representation for query embedding Zhang
et al. (2021), and also the rotation operator Sun et al. (2019) as a powerful
algebraic operation for pattern inference. We define each relation as a
rotation from the source entity set to the answer/intermediate entity set and
perform neural logical operators upon the selected entity sets in the complex
vector space. We provide theoretical proof of its ability to model relational
patterns, as well as experimental results on how the relational patterns
influence logical queries answering over three established benchmark datasets.

##  2 Related Work

To answer more complex queries, a number of path-based (Xiong et al., 2017a;
Lin et al., 2018), neural (Hamilton et al., 2018; Ren et al., 2020; Kotnis et
al., 2021), and neural-symbolic (Arakelyan et al., 2021; Zhu et al., 2022)
methods have been developed. Among these methods, geometric and probabilistic
query embedding approaches (Hamilton et al., 2018; Ren et al., 2020; Zhang et
al., 2021; Ren and Leskovec, 2020) provide a way to tractably handle first-
order logic operators in queries and equip excellent computing efficiency.
This is done by representing entity sets as geometric objects or probability
distributions, such as boxes (Ren et al., 2020), cones (Zhang et al., 2021),
or Beta distribution (Ren and Leskovec, 2020), and performing neural logical
operations directly on them. In this way, the expensive search for
intermediate variables in multi-hop queries is avoided. All of the above query
embedding methods commonly apply multi-layer perceptron networks for selecting
answer entities of atomic queries by relation and performing logical
operations. Thus, their ability to capture relation patterns in KGs remains
unclear. Our proposed method RoConE fills in this gap and combines the
benefits of both worlds (KG embedding and complex query answering) together.

##  3 Preliminaries

##### Knowledge Graph

A KG $\mathcal{G}\subseteq\mathcal{E}\times\mathcal{R}\times\mathcal{E}$,
where $\mathcal{E}$ and $\mathcal{R}$ represent the set of entities and
relations respectively, can be defined as a set of subject-predicate-object
$\bigl{\langle}s,p,o\bigr{\rangle}$ triples. For each triple
$\bigl{\langle}e_{i},r,e_{j}\bigr{\rangle}$, $e_{i,j}\in\mathcal{E}$ and
$r\in\mathcal{R}$, it exists if and only if $e_{i}$ is linked to $e_{j}$ by
relation $r$.

##### First-Order Logical Queries involving constants

First-Order Logical Queries are broad and here we consider answering a subset,
i.e., multi-hop queries with constants and first-order logical operations
including conjunction ($\land$), disjunction ($\lor$), existential
quantification ($\exists$), and negation ($\neg$). The query consists of a set
of constants (anchor entities) $\mathcal{E}_{a}\subset\mathcal{E}$, a set of
existentially quantified bound variables $V_{1},...,V_{m}$ and a single target
answer variable $V_{?}$. The disjunctive normal form of this subset of FOL
queries is namely the disjunction of conjunctive formulas, and can be
expressed as

$q[V_{t}]=V_{t}.\exists V_{1},...,V_{m}:c_{1}\lor c_{2}\lor...\lor c_{n}$ (1)

where $c_{i}$, $i\in\\{1,...,n\\}$ corresponds to a conjunctive query with one
or more atomic queries $d$ i.e. $c_{i}=d_{i1}\land d_{i2}\land...\land
d_{im}$. For each atomic formula, $d_{ij}$ = $(e_{a},r,V)$ or
$\neg(e_{a},r,V)$ or $(V^{{}^{\prime}},r,V)$ or $\neg(V^{{}^{\prime}},r,V)$,
where $e_{a}\in\mathcal{E}_{a}$, $V\in\\{V_{t},V_{1},...,V_{k}\\}$,
$V^{{}^{\prime}}\in\\{V_{1},...,V_{k}\\}$, $r\in\mathcal{R}$. The goal of
logical query embedding is to find a set of answer entities
$\\{e_{t1},e_{t2},...\\}$ for $V_{t}$, such that
$q[V_{t}]=\operatorname{True}$.

##  4 Methodology

To accommodate the learning of relation patterns in query answering over KGs,
we propose a new model RoConE, which models entity sets as cones and relations
as anti-clockwise angular rotations on cones in the complex plane. Each cone
$\mathbf{q}$ is parameterized by $\mathbf{q}=(\mathbf{h}_{U},\mathbf{h}_{L})$,
where $|\mathbf{h}_{\\{U,L\\}}|=\textbf{1}$, and $\mathbf{h}_{U}$,
$\mathbf{h}_{L}\in\mathbb{C}^{d}$ represent the counter-clockwise upper and
lower boundaries of a cone, such that

$\begin{split}\mathbf{h}_{U}\equiv e^{i\boldsymbol{\theta}_{U}}\equiv
e^{i(\boldsymbol{\theta}_{ax}+\boldsymbol{\theta}_{ap}/2)},\\\
\mathbf{h}_{L}\equiv e^{i\boldsymbol{\theta}_{L}}\equiv
e^{i(\boldsymbol{\theta}_{ax}-\boldsymbol{\theta}_{ap}/2)},\end{split}$ (2)

where $\boldsymbol{\theta}_{ax}\in[-\pi,\pi)^{d}$ represents the angle between
the symmetry axis of the cone and $\boldsymbol{\theta}_{ap}\in[0,2\pi]^{d}$
represents the cone aperture, and $d$ is the embedding dimension. The query
and the set of entities are modeled as cones and each entity instance is
modeled as a vector such that $\mathbf{h}_{U}=\mathbf{h}_{L}$.

###  4.1 Logical Operators

As illustrated in Figure 1, each logical query can be represented as a
directed acyclic graph (DAG) tree, where the tree nodes correspond to
constants/anchor node entities or variables, and the edges correspond to atom
relations or logical operations in a query. Logical operations are performed
along the DAG tree from constants to the target answer variable. Figure 3
visualizes these operations on 2D complex space. The logical operators can be
defined as follows

##### Relational rotating projection

Given a set of entities $\mathcal{S}\subset\mathcal{E}$ and a relation
$r\in\mathcal{R}$, the projection operator selects the neighbouring entities
$\mathcal{S}^{{}^{\prime}}\subset\mathcal{E}$ by relation such that
$\mathcal{S}^{{}^{\prime}}=\\{e\in\mathcal{S},e^{{}^{\prime}}\in\mathcal{S}^{{}^{\prime}}:r(e,e^{{}^{\prime}})=True\\}$.
Existing query embedding methods (Zhang et al., 2021; Ren et al., 2020;
Hamilton et al., 2018; Ren and Leskovec, 2020) apply multi-layer perceptron
networks to accomplish this task. They do not accommodate the learning of
potential KG relational patterns which might help in reasoning logical
queries. Motivated by RotatE (Sun et al., 2019), we represent each relation
$\mathbf{r}$ as a counterclockwise relational rotation on query embeddings
about the origin of the complex plane such that
$\mathbf{r}=(\mathbf{r}_{U},\mathbf{r}_{L})$, where
$|\mathbf{r}_{\\{U,L\\}}|=\textbf{1}$, and
$\mathbf{r}_{U},\mathbf{r}_{L}\in\mathbb{C}^{d}$. Given the query embedding
$\mathbf{q}=(\mathbf{h}_{U},\mathbf{h}_{L})$ and a relation $\mathbf{r}$, the
selected query embedding
$\mathbf{q}^{{}^{\prime}}=(\mathbf{h}_{U}^{{}^{\prime}},\mathbf{h}_{L}^{{}^{\prime}})$
is

$\begin{split}\mathbf{h}_{U}^{{}^{\prime}}&=\mathbf{h}_{U}\circ\mathbf{r}_{U}\equiv
e^{i(\boldsymbol{\theta}_{ax}+\boldsymbol{\theta}_{ax,r}+(\boldsymbol{\theta}_{ap}+\boldsymbol{\theta}_{ap,r})/2)},\\\
\mathbf{h}_{L}^{{}^{\prime}}&=\mathbf{h}_{L}\circ\mathbf{r}_{L}\equiv
e^{i(\boldsymbol{\theta}_{ax}+\boldsymbol{\theta}_{ax,r}-(\boldsymbol{\theta}_{ap}+\boldsymbol{\theta}_{ap,r})/2)},\end{split}$
(3)

where $\circ$ is the Hadmard (element-wise) product, and
$\boldsymbol{\theta}_{ax,r}$, $\boldsymbol{\theta}_{ap,r}$ correspond to the
equivalent relational rotation on $\boldsymbol{\theta}_{ax}$,
$\boldsymbol{\theta}_{ap}$. Specifically, for each element of the cone
embeddings, we have $h_{U,i}^{{}^{\prime}}=h_{U,i}r_{U,i}$ and
$h_{L,i}^{{}^{\prime}}=h_{L,i}r_{L,i}$. Each element $r_{i}$ of the relational
rotation $\mathbf{r}_{\\{U,L\\}}$ corresponds to a counterclockwise rotation
on the matching element of upper or lower boundaries by $\theta_{r,i}$ radians
about the origin of the complex plane. By modeling the projection as
relational rotation on a cone in the complex space, RoConE is shown to model
and infer all three types of relation patterns introduced in Section 3. The
lemmas and their proofs are in Appendix and the rotations corresponding to
different relation patterns are visualized in Figure 4.

##### Intersection

For the input cone embeddings of entity sets
$\\{\mathbf{q}_{1},...,\mathbf{q}_{n}\\}$, the intersection operator selects
the intersection $\mathbf{q}^{{}^{\prime}}=\cap_{j=1}^{n}\mathbf{q}_{j}$ with
the SemanticAverage111 SemanticAverage and CardMin are explained in Appendix
B($\cdot$) and CardMin($\cdot$) (Zhang et al., 2021), which calculate the
semantic centers and apertures of cones respectively. Since we have each cone
$\mathbf{q}_{j}=(\mathbf{h}_{j,U},\mathbf{h}_{j,L})\equiv(e^{i(\boldsymbol{\theta}_{j,ax}+\boldsymbol{\theta}_{j,ap}/2)},e^{i(\boldsymbol{\theta}_{j,ax}-\boldsymbol{\theta}_{j,ap}/2)})$,
the intersection
$\mathbf{q}^{{}^{\prime}}=(\mathbf{h}_{U}^{{}^{\prime}},\mathbf{h}_{L}^{{}^{\prime}})$
can be defined as follows

$\begin{split}&\mathbf{h}_{U}^{{}^{\prime}}=e^{i(\boldsymbol{\theta}_{ax}^{{}^{\prime}}+\boldsymbol{\theta}_{ap}^{{}^{\prime}}/2)},\\\
&\mathbf{h}_{L}^{{}^{\prime}}=e^{i(\boldsymbol{\theta}_{ax}^{{}^{\prime}}-\boldsymbol{\theta}_{ap}^{{}^{\prime}}/2)},\end{split}$
(4)

where

$\begin{split}\boldsymbol{\theta}_{ax}^{{}^{\prime}}&=\textbf{SemanticAverage}(\\{(\boldsymbol{\theta}_{j,ax},\boldsymbol{\theta}_{j,ap})\\}_{j=1}^{n}),\\\
\boldsymbol{\theta}_{ap}^{{}^{\prime}}&=\textbf{CardMin}(\\{(\boldsymbol{\theta}_{j,ax},\boldsymbol{\theta}_{j,ap})\\}_{j=1}^{n}).\end{split}$
(5)

##### Disjunction

Given the input cone embeddings of entity sets
$\\{\mathbf{q}_{1},...,\mathbf{q}_{n}\\}$ where
$\mathbf{q}_{j}=(\mathbf{h}_{j,U},\mathbf{h}_{j,L})$, the disjunction operator
finds the union set
$\mathbf{q}^{{}^{\prime}}=\cup_{j=1}^{n}\mathbf{q}_{j}=\\{\mathbf{q}_{1},\dots,\mathbf{q}_{n}\\}$,
which is equivalent to

$(\\{(\text{h}_{1,U}^{1},\text{h}_{1,L}^{1}),\dots,(\text{h}_{n,U}^{1},\text{h}_{n,L}^{1})\\},\dots,\\{(\text{h}_{1,U}^{d},\text{h}_{1,L}^{d}),\dots,(\text{h}_{n,U}^{d},\text{h}_{n,L}^{d})\\})$

Following Ren et al. (2020), we also adopt DNF technique to translate FOL
queries into the disjunction of conjunctive queries and only perform the
disjunction operator in the last step in the computation graph.

##### Negation

Given a set of entities $\mathcal{S}\subset\mathcal{E}$, the negation operator
finds its complementary negation $\bar{S}=\mathcal{E}\setminus\mathcal{S}$.
Given the cone embedding of entity set $\mathcal{S}$,
$\mathbf{q}^{\mathcal{S}}=(\mathbf{h}_{U}^{\mathcal{S}},\mathbf{h}_{L}^{\mathcal{S}})$,
its corresponding complementary negation
$\bar{\mathbf{q}}=(\mathbf{h}_{L}^{\mathcal{S}},\mathbf{h}_{U}^{\mathcal{S}})$.

###  4.2 Optimization

Given a set of training samples, our goal is to minimize the distance between
the query cone embedding $\mathbf{q}=(\mathbf{h}_{U}^{q},\mathbf{h}_{L}^{q})$
and the answer entity vector $\mathbf{h}^{*}$ while maximizing the distance
between this query and negative samples. Thus, we define our training
objective, the negative sample loss as

$L=-log\sigma(\gamma-d(\mathbf{h}^{*},\mathbf{q}))-\frac{1}{k}\sum_{i=1}^{k}log\sigma(d(\mathbf{h}^{*}_{i},\mathbf{q})-\gamma)$

(6)

where $d(\cdot)$ is the combined distance specifically defined in Appendix C,
$\gamma$ is a margin, $\mathbf{h}^{*}$ is a positive entity and
$\mathbf{h}^{*}_{i}$ is the i-th negative entity, k is the number of negative
samples, and $\sigma(\cdot)$ represents the sigmoid function.

##  5 Experiments

Dataset | Model | 1p | 2p | 3p | 2i | 3i | pi | ip | 2u | up
---|---|---|---|---|---|---|---|---|---|---
| GQE | 35.2 | 7.4 | 5.5 | 23.6 | 35.7 | 16.7 | 10.9 | 8.4 | 5.8
| Query2Box | 41.3 | 9.9 | 7.2 | 31.1 | 45.4 | 21.9 | 13.3 | 11.9 | 8.1
FB15k-237 | BetaE | 39.0 | 10.9 | 10.0 | 28.8 | 42.5 | 22.4 | 12.6 | 12.4 | 9.7
| ConE | 41.8 | 12.8 | 11 | 32.6 | 47.3 | 25.5 | 14.0 | 14.5 | 10.8
| RoConE | 42.2 | 10.5 | 7.5 | 33.5 | 48.1 | 23.5 | 14.5 | 12.8 | 8.9
| GQE | 33.1 | 12.1 | 9.9 | 27.3 | 35.1 | 18.5 | 14.5 | 8.5 | 9.0
| Query2Box | 42.7 | 14.5 | 11.7 | 34.7 | 45.8 | 23.2 | 17.4 | 12.0 | 10.7
NELL995 | BetaE | 53.0 | 13.0 | 11.4 | 37.6 | 47.5 | 24.1 | 14.3 | 12.2 | 8.5
| ConE | 53.1 | 16.1 | 13.9 | 40.0 | 50.8 | 26.3 | 17.5 | 15.3 | 11.3
| RoConE | 54.5 | 17.7 | 14.4 | 41.9 | 53.0 | 26.1 | 20.7 | 16.5 | 12.8

Table 1:  MRR results (%) of RoConE, BETAE, Q2B, and GQE on answering EPFOL
($\exists,\land,\lor$) queries. The best statistic is highlighted in bold,
while the second best is highlighted in underline.

##### Experiment setup

We evaluate RoConE on two benchmark datasets NELL995 (Xiong et al., 2017b) and
FB15k-237 (Toutanova and Chen, 2015). RoConE is compared with various state-
of-the-art query embedding models. Mean reciprocal rank (MRR) is used as the
metric. More experimental details are in Appendix D.

##### Main results

Table 1 summarizes the performance of all methods on answering various query
types without negation. RoConE outperforms baseline methods on the majority of
query types while achieving competitive results on the others. We also
observed that RoConE shows better performances on NELL-995 than those on
FB15k-237. We conjecture that this is due to the discrepancy in the
distribution of relation patterns between these two datasets. As Table 2
shows, RoConE does not bring many improvements for answering query types
involving negation. There are two folds of possible reasons that might lead to
this result. Firstly, the traditional modeling of negation as complements may
be problematic, which can be reflected in the poor performance of all existing
QE models. This largely brings too much uncertainty into the query embedding
and leads to severe bias in prediction. Secondly, the influence of relation
patterns on negation queries is limited when we model negation as complements.

Dataset | Model | 2in | 3in | inp | pin | pni
---|---|---|---|---|---|---
FB15k-237 | BetaE | 5.1 | 7.9 | 7.4 | 3.6 | 3.4
ConE | 5.4 | 8.6 | 7.8 | 4.0 | 3.6
RoConE | 4.1 | 7.9 | 6.9 | 3.1 | 2.8
NELL995 | BetaE | 5.1 | 7.8 | 10 | 3.1 | 3.5
ConE | 5.7 | 8.1 | 10.8 | 3.5 | 3.9
RoConE | 5.2 | 7.7 | 9.4 | 3.2 | 3.7

Table 2:  MRR results (%) of RoConE, BETAE, and ConE on answering queries with
negation ($\neg$).

##### Ablation study

To investigate the influence of relation patterns on the query answering
model, we designed an ablation study for RoConE on NELL995. The results are
reported in Table 3. RoConE (Base) denotes the neural baseline model without
the relational rotating projection module. RoConE (S.E) and RoConE (Trunc)
correspond to two variants of RoConE with different rotation strategies. More
details are elaborated in Appendix D.4. The overperformance of RoConE and
RoConE (truncation) reconfirms the efficiency of relation patterns in logical
query reasoning tasks.

Model | 1p | 2p | 3p | 2i | 3i | pi | ip | 2u | up
---|---|---|---|---|---|---|---|---|---
RoConE (Base) | 53.1 | 16.1 | 13.9 | 40 | 50.8 | 26.3 | 17.5 | 15.3 | 11.3
RoConE (S.E.) | 51.3 | 16.6 | 13.8 | 38.4 | 48.4 | 18.9 | 19.5 | 14.7 | 12.1
RoConE (Trunc) | 53.7 | 17.8 | 14.2 | 41.9 | 53.0 | 27.5 | 20.4 | 16.6 | 12.7
RoConE | 54.5 | 17.7 | 14.4 | 41.9 | 53.0 | 26.1 | 20.7 | 16.5 | 12.8

Table 3:  Ablation study of RoConE on NELL995

##  6 Conclusion

In this paper, we theoretically and experimentally investigate the influence
of relation patterns on enhancing the logical query reasoning task. By
combining the relational rotating projection with the cone query embedding
model in complex space, we improve FOL queries reasoning with relation pattern
inference.

##  7 Limitations

RoConE incorporates the learning of potential KG relation patterns into the
existing query embedding model for solving logical queries. We provide initial
proof of the efficiency of relation patterns to complex reasoning via both
theoretical explanations and experiments. One limitation of RoConE is that the
relational rotating projection can not be generalized to other geometric query
embedding methods, except for cone embedding, due to the restriction of
natural geometry properties. For future work, we will propose more general and
effective strategies to enhance the learning of relation patterns in the
complex query reasoning task.

##  8 Ethics Statement

The authors declare that we have no conflicts of interest. This article does
not contain any studies involving business data and personal information.

## References

  * Arakelyan et al. (2021) Erik Arakelyan, Daniel Daza, Pasquale Minervini, and Michael Cochez. 2021.  Complex query answering with neural link predictors.  In _9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021_. OpenReview.net.
  * Hamilton et al. (2018) William L. Hamilton, Payal Bajaj, Marinka Zitnik, Dan Jurafsky, and Jure Leskovec. 2018.  Embedding logical queries on knowledge graphs.  In _Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada_ , pages 2030–2041.
  * Kotnis et al. (2021) Bhushan Kotnis, Carolin Lawrence, and Mathias Niepert. 2021.  Answering complex queries in knowledge graphs with bidirectional sequence encoders.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 35(6):4968–4977.
  * Lin et al. (2018) Xi Victoria Lin, Richard Socher, and Caiming Xiong. 2018.  Multi-hop knowledge graph reasoning with reward shaping.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pages 3243–3253, Brussels, Belgium. Association for Computational Linguistics.
  * Nayyeri et al. (2021) Mojtaba Nayyeri, Chengjin Xu, Yadollah Yaghoobzadeh, Sahar Vahdati, Mirza Mohtashim Alam, Hamed Shariat Yazdi, and Jens Lehmann. 2021.  Loss-aware pattern inference: A correction on the wrongly claimed limitations of embedding models.  In _Pacific-Asia Conference on Knowledge Discovery and Data Mining_ , pages 77–89. Springer.
  * Paszke et al. (2019) Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Z. Yang, Zach DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. 2019.  Pytorch: An imperative style, high-performance deep learning library.  _CoRR_ , abs/1912.01703.
  * Ren et al. (2020) Hongyu Ren, Weihua Hu, and Jure Leskovec. 2020.  Query2box: Reasoning over knowledge graphs in vector space using box embeddings.  In _8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020_. OpenReview.net.
  * Ren and Leskovec (2020) Hongyu Ren and Jure Leskovec. 2020.  Beta embeddings for multi-hop logical reasoning in knowledge graphs.  In _Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual_.
  * Sun et al. (2019) Zhiqing Sun, Zhi-Hong Deng, Jian-Yun Nie, and Jian Tang. 2019.  Rotate: Knowledge graph embedding by relational rotation in complex space.  _CoRR_ , abs/1902.10197.
  * Toutanova and Chen (2015) Kristina Toutanova and Danqi Chen. 2015.  Observed versus latent features for knowledge base and text inference.  In _Proceedings of the 3rd Workshop on Continuous Vector Space Models and their Compositionality_ , pages 57–66, Beijing, China. Association for Computational Linguistics.
  * Xiong et al. (2017a) Wenhan Xiong, Thien Hoang, and William Yang Wang. 2017a.  DeepPath: A reinforcement learning method for knowledge graph reasoning.  In _Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing_ , pages 564–573, Copenhagen, Denmark. Association for Computational Linguistics.
  * Xiong et al. (2017b) Wenhan Xiong, Thien Hoang, and William Yang Wang. 2017b.  DeepPath: A reinforcement learning method for knowledge graph reasoning.  In _Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing_ , pages 564–573, Copenhagen, Denmark. Association for Computational Linguistics.
  * Zaheer et al. (2017) Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Ruslan Salakhutdinov, and Alexander Smola. 2017.  Deep sets.
  * Zhang et al. (2021) Zhanqiu Zhang, Jie Wang, Jiajun Chen, Shuiwang Ji, and Feng Wu. 2021.  Cone: Cone embeddings for multi-hop reasoning over knowledge graphs.  In _Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual_ , pages 19172–19183.
  * Zhu et al. (2022) Zhaocheng Zhu, Mikhail Galkin, Zuobai Zhang, and Jian Tang. 2022.  Neural-symbolic models for logical queries on knowledge graphs.  In _International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA_ , volume 162 of _Proceedings of Machine Learning Research_ , pages 27454–27478. PMLR.

## Appendices

Figure 3: Visualization of logical operators (Zhang et al., 2021) Figure 4:
Relational rotations corresponding to different relation patterns on 2D
complex plane.

###  A Lemmas and Corresponding Proofs

######  Lemma 1.

RoConE can infer the symmetry and anti-symmetry patterns.

###### Proof.

Given cone query embeddings $X=(\mathbf{h}_{U}^{x},\mathbf{h}_{L}^{x})$,
$Y=(\mathbf{h}_{U}^{y},\mathbf{h}_{L}^{y})$ and relation
$r=(\mathbf{r}_{U},\mathbf{r}_{L})$, if $(X,r,Y)$ and $(Y,r,X)$ hold, we have:

$\begin{split}(\mathbf{h}_{U}^{x}\circ\mathbf{r}_{U},\mathbf{h}_{L}^{x}\circ\mathbf{r}_{L})&=(\mathbf{h}_{U}^{y},\mathbf{h}_{L}^{y}),\\\
(\mathbf{h}_{U}^{y}\circ\mathbf{r}_{U},\mathbf{h}_{L}^{y}\circ\mathbf{r}_{L})&=(\mathbf{h}_{U}^{x},\mathbf{h}_{L}^{x}),\end{split}$
(7)
$\rightarrow(\mathbf{h}_{U}^{y}\circ\mathbf{r}_{U}\circ\mathbf{r}_{U},\mathbf{h}_{L}^{y}\circ\mathbf{r}_{L}\circ\mathbf{r}_{L})=(\mathbf{h}_{U}^{y},\mathbf{h}_{L}^{y})$

thus, it is inferrable that $X$ is symmetric to $Y$ if and only if
$(\mathbf{r}_{U}\circ\mathbf{r}_{U}=\mathbf{1},\mathbf{r}_{L}\circ\mathbf{r}_{L}=\mathbf{1})$.
Similarly, if $(X,r,Y)$ and $\neg(Y,r,X)$ hold, we have:

$\begin{split}(\mathbf{h}_{U}^{x}\circ\mathbf{r}_{U},\mathbf{h}_{L}^{x}\circ\mathbf{r}_{L})&=(\mathbf{h}_{U}^{y},\mathbf{h}_{L}^{y}),\\\
(\mathbf{h}_{U}^{y}\circ\mathbf{r}_{U},\mathbf{h}_{L}^{y}\circ\mathbf{r}_{L})&\neq(\mathbf{h}_{U}^{x},\mathbf{h}_{L}^{x}),\end{split}$
(8)
$\rightarrow(\mathbf{h}_{U}^{x}\circ\mathbf{r}_{U}\circ\mathbf{r}_{U},\mathbf{h}_{L}^{x}\circ\mathbf{r}_{L}\circ\mathbf{r}_{L})\neq(\mathbf{h}_{U}^{x},\mathbf{h}_{L}^{x})$

thus, it is inferrable that $X$ is anti-symmetric to $Y$ if and only if
$(\mathbf{r}_{U}\circ\mathbf{r}_{U}\neq\mathbf{1},\mathbf{r}_{L}\circ\mathbf{r}_{L}\neq\mathbf{1})$.
∎

######  Lemma 2.

RoConE can infer the inversion pattern.

###### Proof.

Given cone query embeddings $X=(\mathbf{h}_{U}^{x},\mathbf{h}_{L}^{x})$,
$Y=(\mathbf{h}_{U}^{y},\mathbf{h}_{L}^{y})$ and relations
$r_{1}=(\mathbf{r}_{U,1},\mathbf{r}_{L,1})$,
$r_{2}=(\mathbf{r}_{U,2},\mathbf{r}_{L,2})$ if $(X,r_{1},Y)$ and $(Y,r_{2},X)$
hold, we have:

$\begin{split}(\mathbf{h}_{U}^{x}\circ\mathbf{r}_{U,1},\mathbf{h}_{L}^{x}\circ\mathbf{r}_{L,1})&=(\mathbf{h}_{U}^{y},\mathbf{h}_{L}^{y}),\\\
(\mathbf{h}_{U}^{y}\circ\mathbf{r}_{U,2},\mathbf{h}_{L}^{y}\circ\mathbf{r}_{L,2})&=(\mathbf{h}_{U}^{x},\mathbf{h}_{L}^{x}),\end{split}$
(9)
$\rightarrow(\mathbf{h}_{U}^{y}\circ\mathbf{r}_{U,2}\circ\mathbf{r}_{U,1},\mathbf{h}_{L}^{y}\circ\mathbf{r}_{L,2}\circ\mathbf{r}_{L,1})=(\mathbf{h}_{U}^{y},\mathbf{h}_{L}^{y})$

thus, it is inferrable that X is inversible to Y if and only if
$\mathbf{r}_{U,2}\circ\mathbf{r}_{U,1}=1$ and
$\mathbf{r}_{L,2}\circ\mathbf{r}_{L,1}=1$. ∎

######  Lemma 3.

RoConE can infer the composition pattern.

###### Proof.

Given cone query embeddings $X=(\mathbf{h}_{U}^{x},\mathbf{h}_{L}^{x})$,
$Y=(\mathbf{h}_{U}^{y},\mathbf{h}_{L}^{y})$,
$Z=(\mathbf{h}_{U}^{z},\mathbf{h}_{L}^{z})$ and relations
$r_{1}=(\mathbf{r}_{U,1},\mathbf{r}_{L,1})$,
$r_{2}=(\mathbf{r}_{U,2},\mathbf{r}_{L,2})$ if $(X,r_{1},Y)$ and $(Y,r_{2},Z)$
hold, we have:

$\begin{split}(\mathbf{h}_{U}^{x}\circ\mathbf{r}_{U,1},\mathbf{h}_{L}^{x}\circ\mathbf{r}_{L,1})&=(\mathbf{h}_{U}^{y},\mathbf{h}_{L}^{y}),\\\
(\mathbf{h}_{U}^{y}\circ\mathbf{r}_{U,2},\mathbf{h}_{L}^{y}\circ\mathbf{r}_{L,2})&=(\mathbf{h}_{U}^{z},\mathbf{h}_{L}^{z}),\\\
(\mathbf{h}_{U}^{x}\circ\mathbf{r}_{U,3},\mathbf{h}_{L}^{x}\circ\mathbf{r}_{L,3})&=(\mathbf{h}_{U}^{z},\mathbf{h}_{L}^{z}),\end{split}$
(10)

$\rightarrow$

$(\mathbf{h}_{U}^{x}\circ\mathbf{r}_{U,1}\circ\mathbf{r}_{U,2},\mathbf{h}_{L}^{x}\circ\mathbf{r}_{L,1}\circ\mathbf{r}_{L,2})=(\mathbf{h}_{U}^{x}\circ\mathbf{r}_{U,3},\mathbf{h}_{L}^{x}\circ\mathbf{r}_{L,3})$

thus, it is inferrable that relation $r_{3}$ is compositional of $r_{1}$ and
$r_{2}$ if and only if
$\mathbf{r}_{U,1}\circ\mathbf{r}_{U,2}=\mathbf{r}_{U,3}$. ∎

###  B Details of Intersection Operator

In this section, we explain the details of two important components of the
intersection operator, SemanticAverage($\cdot$) and CardMin($\cdot$)

##### SemanticAverage($\cdot$)

is expected to compute the semantic center
$\boldsymbol{\theta}_{ax}^{{}^{\prime}}$ of the input
$\\{(\boldsymbol{\theta}_{j,ax},\boldsymbol{\theta}_{j,ap})\\}_{j=1}^{n}$.
Specifically, the computation process is provided as:

$\begin{split}[\mathbf{x};\mathbf{y}]&=\sum_{i=1}^{n}[\mathbf{a}_{j}\circ\text{cos}(\boldsymbol{\theta}_{j,ax});\mathbf{a}_{j}\circ\text{sin}(\boldsymbol{\theta}_{j,ax})],\\\
\boldsymbol{\theta}_{ax}^{{}^{\prime}}&=\textbf{Arg}(\mathbf{x},\mathbf{y}),\end{split}$
(11)

where cos and sin represent element-wise cosine and sine functions.
Arg($\cdot$) computes the argument given $\mathbf{x}$ and $\mathbf{y}$.
$\mathbf{a}_{j}\in\mathbb{R}^{d}$ are attention weights such that

$[\mathbf{a}_{j}]_{k}=\frac{\text{exp}([\textbf{MLP}([\boldsymbol{\theta}_{j,ax}-\boldsymbol{\theta}_{j,ap/2};\boldsymbol{\theta}_{j,ax}+\boldsymbol{\theta}_{j,ap/2}])]_{k})}{\sum_{m=1}^{n}\text{exp}([\textbf{MLP}([\boldsymbol{\theta}_{m,ax}-\boldsymbol{\theta}_{m,ap/2};\boldsymbol{\theta}_{m,ax}+\boldsymbol{\theta}_{m,ap/2}])]_{k})},$

(12)

where MLP : $\mathbb{R}^{2d}\rightarrow\mathbb{R}^{d}$ is a multi-layer
perceptron network, [$\cdot$;$\cdot$] is the concatenation of two vectors.

##### CardMin($\cdot$)

predicts the aperture $\boldsymbol{\theta}_{ap}^{{}^{\prime}}$ of the
intersection set such that $[\boldsymbol{\theta}_{ap}^{{}^{\prime}}]_{i}$
should be no larger than any $\boldsymbol{\theta}_{j,ap}^{i}$, since the
intersection set is the subset of all input entity sets.

$[\theta_{ap}^{{}^{\prime}}]_{i}=\text{min}\\{\theta_{1,ap}^{i},\dots,\theta_{n,ap}^{i}\\}\cdot\sigma([\textbf{DeepSets}(\\{(\boldsymbol{\theta}_{j,ax},\boldsymbol{\theta}_{j,ap})\\}_{j=1}^{n})]_{i})$

(13)

where
DeepSets$(\\{(\boldsymbol{\theta}_{j,ax},\boldsymbol{\theta}_{j,ap})\\}_{j=1}^{n})$
(Zaheer et al., 2017) is given by

$\textbf{MLP}(\frac{1}{n}\sum_{j=1}^{n}\textbf{MLP}([\boldsymbol{\theta}_{j,ax}-\boldsymbol{\theta}_{j,ap/2};\boldsymbol{\theta}_{j,ax}+\boldsymbol{\theta}_{j,ap/2}])).$

###  C Distance Function

Inspired by Zhang et al. (2021); Ren et al. (2020), the distance between
$\mathbf{q}$ and $\mathbf{h}^{*}$ is defined as a combination of inside and
outside distances, $d_{com}(\mathbf{q},\mathbf{h}^{*})=d_{o}+\lambda d_{i}$:

$\begin{split}d_{o}(\mathbf{q},\mathbf{h}^{*})&=min\\{\|\mathbf{h}_{U}^{q}-\mathbf{h}^{*}\|_{1},\|\mathbf{h}_{L}^{q}-\mathbf{h}^{*}\|_{1}\\},\\\
d_{i}(\mathbf{q},\mathbf{h}^{*})&=min\\{\|\mathbf{h}_{ax}^{q}-\mathbf{h}^{*}\|_{1},\|\mathbf{h}_{U}^{q}-\mathbf{h}_{ax}^{q}\|_{1}\\},\end{split}$
(14)

where $\|\cdot\|_{1}$ is the $L_{1}$ norm, $\mathbf{h}_{ax}^{q}$ represents
the cone center, and $\lambda\in(0,1)$.
Note that $d_{com}$ can only be used for measuring the distance between a
single query embedding and an answer entity vector. Since we represent the
disjunctive queries in Disjunctive Normal Form as a set of query embeddings
$\\{\mathbf{q}_{1},\dots,\mathbf{q}_{n}\\}$, the distance between the answer
vector and such set of embeddings is the minimum distance between the vector
and each of these sets:

$d_{dis}(\mathbf{q},\mathbf{h}^{*})=min\\{d_{com}(\mathbf{q}_{1},\mathbf{h}^{*}),\dots,d_{com}(\mathbf{q}_{n},\mathbf{h}^{*})\\}$

(15)

Thus, the overall distance function can be defined as:

$d(\mathbf{q},\mathbf{h}^{*})=\begin{cases}d_{com}(\mathbf{q},\mathbf{h}^{*}),&\text{query
without disjunction}\\\ d_{dis}(\mathbf{q},\mathbf{h}^{*}),&\text{query with
disjunction}\end{cases}$

(16)

###  D More Details about Experiments

In this section, we elaborate more details about our experiments. The code is
anonymously available at https://anonymous.4open.science/r/RoConE-1C1E.

####  D.1 Dataset and Query structures

RoConE is compared with various state-of-the-art query embedding models,
including GQE (Hamilton et al., 2018), Query2Box (Ren et al., 2020), BetaE
(Ren and Leskovec, 2020), and ConE (Zhang et al., 2021). For a fair comparison
with existing query embedding models, we use the same query structures and
datasets NELL995 (Xiong et al., 2017a) and FB15k-237, and the open-sourced
framework created by Ren and Leskovec (2020) for logical query answering
tasks. Table 4 summarizes the descriptive statistics about the benchmark
datasets. Figure 5 illustrates all query structures used in our experiments.

Dataset | Training | Validation | Testing
---|---|---|---
| EPFOL | Negation | 1p | others | 1p | others
FB15k-237 | 149,689 | 14,968 | 20,101 | 5,000 | 22,812 | 5,000
NELL995 | 107,982 | 10,798 | 16,927 | 4,000 | 17,034 | 4,000
Table 4:  Statistics of benchmark datasets : FB15k-237 and NELL995. EPFOL
represents queries without negation, namely 1p/2p/3p/2i/3i. Figure 5: Fourteen
types of queries used in the experiments. "$p$" represents relational
projection, "$i$" represents intersection, "$u$" represents union and "n"
represents negation. The upper of queries is used in the training stage, while
all queries are evaluated in the validation and test stages.

####  D.2 Hyperparameters and Computational Resources

All of our experiments are implemented in Pytorch (Paszke et al., 2019)
framework and run on four Nvidia A100 GPU cards. For hyperparameters search,
we performed a grid search of learning rates in $\\{5\times
10^{-5},10^{-4},5\times 10^{-4}\\}$, the batch size in $\\{256,512,1024\\}$,
the negative sample sizes in $\\{128,64\\}$, the regularization coefficient
$\lambda$ in $\\{0.02,0.05,0.08,0.1\\}$ and the margin $\gamma$ in
$\\{20,30,40,50\\}$. The best hyperparameters are saved in Table 5.

Dataset | d | b | n | $\gamma$ | $\hskip 11.38109ptl$ | $\lambda$
---|---|---|---|---|---|---
FB15k-237 | 1600 | 128 | 512 | 30 | 5 $\times 10^{-5}$ | 0.1
NELL995 | 800 | 128 | 512 | 20 | $1\times 10^{-4}$ | 0.02

Table 5:  Hyperparameters found by grid search. d represents the embedding
dimension, b is the batch size, n is the negative sampling size, $\gamma$ is
the margin in loss, l represents the learning rate, $\lambda$ is the
regularization parameter in the distance function.

####  D.3 Evaluation Metrics

In this paper, we use Mean Reciprocal Rank (MRR) as the evaluation metric.
Given a sample of queries Q, Mean reciprocal rank represents the average of
the reciprocal ranks of results:

$MRR=\frac{1}{|Q|}\sum_{i=1}^{|Q|}\frac{1}{rank_{i}}$

####  D.4 Variants of relational projection strategies

To better incorporate the learning the relation patterns in query embedding
model, we proposed alternative two variants of the relational rotation
projection strategy:

  * •

RoConE (Trunc): after relational rotation, the two boundaries of query
embedding are truncated to ensure that aperture will not be greater than
$\pi$.

  * •

RoConE (S.E): replaces relational rotation on boundaries by a non-linear
sigmoid function which maps the boundaries to shrink or expand and only
maintains rotations on $\theta_{ax}$.

####  D.5 Error Bars of Main Results

We have run RoConE 10 times with different random seeds, and obtain mean
values and standard deviations of RoConE’s MRR results on EPFO and negation
queries. Table 6 shows that mean values and standard deviations of RoConE’s
MRR results on EPFOL queries. Table 7 shows mean values and standard
deviations of RoConE’s MRR results on negation queries.

Dataset | 1p | 2p | 3p | 2i | 3i | pi | ip | 2u | up
---|---|---|---|---|---|---|---|---|---
FB15k-237 | 42.2$\pm$ | 10.5$\pm$ | 7.5$\pm$ | 33.5$\pm$ | 48.1$\pm$ | 23.5$\pm$ | 14.5$\pm$ | 12.8$\pm$ | 8.9$\pm$
0.054 | 0.108 | 0.142 | 0.075 | 0.172 | 0.105 | 0.183 | 0.096 | 0.193
NELL995 | 54.5$\pm$ | 17.7$\pm$ | 14.4$\pm$ | 41.9$\pm$ | 53.0$\pm$ | 26.1$\pm$ | 20.7$\pm$ | 16.5$\pm$ | 12.8$\pm$
0.097 | 0.152 | 0.192 | 0.130 | 0.038 | 0.084 | 0.146 | 0.112 | 0.137

Table 6: RoConE’s MRR mean values and standard variances ($\%$) on answering
EPFO ($\exists$, $\land$, $\lor$) queries

Dataset | 2in | 3in | inp | pin | pni
---|---|---|---|---|---
FB15k-237 | 4.1$\pm$ | 7.9$\pm$ | 6.9$\pm$ | 3.1$\pm$ | 2.8$\pm$
0.089 | 0.092 | 0.161 | 0.083 | 0.077
NELL995 | 5.2$\pm$ | 7.7$\pm$ | 9.4$\pm$ | 3.2$\pm$ | 3.7$\pm$
0.012 | 0.079 | 0.154 | 0.012 | 0.097

Table 7: RoConE’s MRR mean values and standard variances ($\%$) on answering
negation queries