0 1cm [gray]0.75 1.5 Preprint

# Dynamic Embeddings for Interaction Prediction

Zekarias T. Kefato<EMAIL_ADDRESS>KTH Royal Institute of
TechnologyStockholmSweden ,  Sarunas Girdzijauskas<EMAIL_ADDRESS>KTH Royal
Institute of TechnologyStockholmSweden ,  Nasrullah Sheikh
<EMAIL_ADDRESS>IBM Research – AlmadenSan JoseUSA and  Alberto
Montresor<EMAIL_ADDRESS>University of TrentoTrentoItaly

(2021)

###### Abstract.

In recommender systems (RSs), predicting the next item that a user interacts
with is critical for user retention. While the last decade has seen an
explosion of RSs aimed at identifying relevant items that match user
preferences, there is still a range of aspects that could be considered to
further improve their performance. For example, often RSs are centered around
the user, who is modeled using her recent sequence of activities. Recent
studies, however, have shown the effectiveness of modeling the _mutual_
interactions between users and items using separate user and item embeddings.

Building on the success of these studies, we propose a novel method called
DeePRed that addresses some of their limitations. In particular, we avoid
recursive and costly interactions between consecutive short-term embeddings by
using long-term (stationary) embeddings as a proxy. This enable us to train
DeePRed using simple mini-batches without the overhead of specialized mini-
batches proposed in previous studies. Moreover, DeePRed’s effectiveness comes
from the aforementioned design and a multi-way attention mechanism that
inspects user-item compatibility. Experiments show that DeePRed outperforms
the best state-of-the-art approach by at least 14% on next item prediction
task, while gaining more than an order of magnitude speedup over the best
performing baselines. Although this study is mainly concerned with temporal
interaction networks, we also show the power and flexibility of DeePRed by
adapting it to the case of static interaction networks, substituting the
short- and long-term aspects with local and global ones. The source code is
available here: https://github.com/zekarias-tilahun/deepred

dynamic embeddings, mutual RNN, recommender systems, interaction prediction,
multi-way attention

††copyright: acmcopyright††journalyear: 2021††doi:
10.1145/1122445.1122456††conference: Preprint; ††booktitle: ;††price:
15.00††isbn: 978-1-4503-XXXX-X/18/06

##  1\. Introduction

Vital to the success of a number of real-world recommender systems (RS) is the
ability to predict future interactions between entities based on their
previous interaction history. In many recommender systems, effective user-item
interaction prediction enable end-users to sift through an overwhelming number
of choices. In addition, in biology, pharmacology and related fields,
interaction prediction between biological and chemical compounds has been
explored to better understand unknown bio-chemical interactions (Buza and
Peška, 2017; You et al., 2019; Zitnik et al., 2018).

In this paper, we are primarily interested in temporal interaction networks
between two sets of entities– _users_ and _items_. The terms cover a variety
of notions, _e.g._ users could be customers in an e-commerce system, or
accounts on Reddit, YouTube or Spotify; items could be products, posts, media
produced or consumed by users.

Given a set of observed interactions between users and items, predicting
possible future interactions is an increasingly important and challenging
task. The goal of this paper is to introduce a new method to predict the next
items that users interact with, based on their previous history of
interaction. We model our problem through bipartite temporal interaction
networks, as they can naturally and effectively represent user-item
interactions over time.

#### Existing studies

In the context of RS, several approaches have been proposed to predict future
items a user is likely to interact with, providing encouraging results (Wu et
al., 2017, 2019; Hidasi et al., 2015; Xu et al., 2019; Wang et al., 2020; Tan
et al., 2016; Kumar et al., 2019; Covington et al., 2016; Dai et al., 2016a).
Often times, however, the focus is on modeling users, while the user-item
interaction dynamics that provide a richer signal is overlooked (Wang et al.,
2019). In several cases, RNNs and other models suitable for sequences were
used to train a predictive model over the item sequence corpus.

Recently, studies have shown how to mutually model both user and items based
on bipartite interaction networks and demonstrate significant improvement over
existing methods (Kumar et al., 2019; Dai et al., 2016a). Unlike previous
approaches, they have employed mutually recursive RNNs that are more capable
to model the user-item interaction dynamics. While they use two types of
embeddings, long-term and short-term, the former is just a fixed one-hot
vector and the latter is the real core of their models, that it is used to
capture recent user preferences and item properties. Moreover, these
approaches work by recursively computing the short-term embedding at time $t$
based on the embedding at time $t-1$ , which leads to sequential training that
proved to be a bottleneck as the network scales up. Even if recent work has
introduced a mini-batch training algorithm, the overhead is not completely
alleviated yet (Kumar et al., 2019).

#### This study

We propose a novel algorithm called DeePRed (Dynamic Embeddings for
Interaction Prediction). DeePRed provides a simple yet powerful way of
modeling short-term interaction behaviours that removes the aforementioned
recursive dependency for efficient training. This is achieved by decoupling
the _learnable_ user or item embeddings into long-term and short-term
embeddings, in order to capture both stationary and transitory interaction
patterns. Furthermore, DeePRed computes separate embeddings from the point of
view of both: users and items. Henceforth, although our discussion mostly
covers users, the same principles can be applied to items unless explicitly
stated otherwise.

The key idea behind the effectiveness of DeePRed is that, each time a user
interacts with an item, it is modeled using a sequence of $k$ recent items she
interacted with, which reflects a context of interaction. For example, Fig. 1
shows the $k$ recent interaction history of a user $u$ and an item $i$. We see
that the two most recent interactions at $t_{l}$ and $t_{l-1}$ are within the
context of SciFi, for both $u$ and $i$. That is, the last two items that $u$
has interacted with are relevant to the theme of SciFi. Thus, the long-term
(contextually stationary) embedding of the items (Spider man and Alien movies)
at $t_{l}$ and $t_{l-1}$ are used to encode such context.

Similar to previous work (Kumar et al., 2019; Dai et al., 2016a), we use two
mutual RNNs that capture the interaction and temporal patterns within a
history sequence (the $k$ most recent interaction events), and generate high-
level features. However, unlike previous work, the two RNNs share the same
model parameters and are not recursively dependent.

Figure 1. An illustration of the sequence of $k$ recent interaction events
starting from the last event $t_{l}$ before a given time $t$ for a user $u$
(${\mathbb{L}}_{u}(t^{<},k)$) and an item $i$ (${\mathbb{L}}_{i}(t^{<},k)$).

Finally, the power of DeePRed comes from a multi-way attention mechanism that
we employ to capture the user-item interaction signal, to check whether the
short-term history ($k$ most recent interactions) of a user and an item are
compatible using attention weights. The weights are then used as feature
selectors over the high-level features and predict the short-term embeddings.
In DeePRed, each interaction produces a new instance of short-term embedding
for both the user and item. This gives DeePRed the power to reason based on
consistent behaviours as opposed to rare events, and it is in contrast to
(Kumar et al., 2019) that updates the existing ones. Besides its qualitative
power, predicting short-term embeddings as opposed to interaction
probabilities is another choice in our design that boosts DeePRed’s
efficiency.

The last but not the least aspect of DeePRed is that it can be seamlessly
extended to tackle static interaction networks. This is achieved by replacing
long and short-term aspects with global and local ones, based on a sample of
interactions as opposed to the latest (recent) ones.

#### Our contribution

Our contributions are the following:

  * •

Novelty: We propose a novel algorithm that captures user (item) preferences
over time by modeling users (items) using their recent interaction history. By
leveraging the decoupling of the learnable embeddings, we employ _non-
recursive_ mutual RNNs to capture interaction and temporal patterns within the
histories. Furthermore, an attention mechanism is used to inspect user-item
compatibility allowing to significantly improve the predictive performance of
our approach.

  * •

Empirical results: With respect to the state of the art, our results show at
least a 14% gain on mean reciprocal rank, measured on three real-world and
pubicly available datasets.

  * •

Efficiency: As a result of eliminating the recursive self-dependency between
short-term embeddings at different time steps, DeePRed achieves more than one
order of magnitude speedup over the best performing SOTA methods.

  * •

Easy extension to static networks: Though the focus of this study is on
temporal interaction networks, we have shown that DeePRed is seamlessly
extendable to static interaction networks using three real-world datasets.

##  2\. Modeling Preliminaries

The focus of this study is to model temporal interaction networks; yet, our
proposal could be adapted to static networks with little effort. We therefore
show first the general model, and then we show how to specialize it for the
static case.

We take an ordered set ${\mathbb{L}}$ containing a log of interactions between
a set of users ${\mathbb{U}}$ and a set of items ${\mathbb{I}}$, where
${L=|{\mathbb{L}}|}$, ${U=|{\mathbb{U}}|}$, and ${I=|{\mathbb{I}}|}$. An event
$e=(u,i,t)\in{\mathbb{L}}$ records an interaction between a user $u$ and an
item $i$ at time $t$. Events associated with users and items are intrinsically
ordered by time. Let ${\mathbb{L}}_{u}$ be the set of all interaction events
of user $u$, such that ${{\mathbb{L}}_{u}=\\{e_{1},e_{2},\ldots,e_{l}\\}}$ and
events are intrinsically ordered, that is if two events
${e_{j}=(u,i_{j},t_{j})}$ and ${e_{k}=(u,i_{k},t_{k})}$ are such that $j\leq
k$, then $t_{j}\leq t_{k}$.

In predicting future interactions between users and items, generally, both
long-term and short-term interaction behaviours are commonly used (Zhu et al.,
2017; Beutel et al., 2018; Dai et al., 2016b). However, short-term behaviours
are mostly favored to have a strong impact on follow-up interactions. We adopt
a similar assumption and model user and item preferences from both long-term
and short-term perspectives. The long-term preferences are captured through
the complete interaction histories of users/items. For a user $u$ and an item
$i$, ${\mathbb{L}}_{u}$ and ${\mathbb{L}}_{i}$ denote their complete
interaction history, respectively.

Although user preferences are normally considered to change over time (Wu et
al., 2017), we assume that users usually have a dominant (stationary)
preference, which remains unchanged. However, as their preferences change over
time depending on recent actions, users have a tendency to do related actions.
For instance, in movie RS, a particular genre might be preferred by a user at
any given time. More importantly, however, one is likely to show interest in
movies of different genres based on mood, events in her life (e.g. marriage,
childbirth, trauma) and seasons (e.g. Christmas, Summer) (Wu et al., 2017).
Thus, the most recent watching behaviors have a stronger impact than the old
preferences over the next movie that a user is likely to watch.

To capture recent preferences, in line with (Zhang et al., 2019; Beutel et
al., 2018), we use the $k$ most recent interaction events. Unlike some studies
(Hidasi et al., 2015; Kang and McAuley, 2018; Wu et al., 2019; Covington et
al., 2016), however, we assume that the $k$ most recent interaction events
from both the user and the item influence the next user-item interaction.
Later, we shall discuss the details of the benefit of this design choice.
Thus, the $k$ most recent interactions of each user ${u\in{\mathbb{U}}}$ and
item ${i\in{\mathbb{I}}}$, respectively, before a given time $t$ are
identified by:

$\displaystyle{\mathbb{L}}_{u}(t^{<},k)=\\{i_{j},\Delta_{j}:(u,i_{j},t_{j})\in{\mathbb{L}}_{u},t_{j}<t,j=l-k,\ldots,l\\}$
$\displaystyle{\mathbb{L}}_{i}(t^{<},k)=\\{u_{j},\Delta_{j}:(u_{j},i,t_{j})\in{\mathbb{L}}_{i},t_{j}<t,j=l-k,\ldots,l\\}$

where $\Delta_{j}=t-t_{j}$ captures the hotness (recency) of the $j^{th}$
event.

For static networks, we simply strip out time from ${\mathbb{L}}$; any subsets
thereof become unordered. In this case,
${{\mathbb{L}}_{u}(k)\subseteq{\mathbb{L}}_{u}}$ and
${{\mathbb{L}}_{i}(k)\subseteq{\mathbb{L}}_{i}}$ simply denote a sampled set
of $k$ events from observed events ${\mathbb{L}}_{u}$ and ${\mathbb{L}}_{i}$,
respectively.

#### Research question

The main goal of this study is: given an ordered set of observed events
${\mathbb{L}}_{\mathcal{O}}$, can we design a novel algorithm that effectively
predicts future interactions in temporal interaction networks? Can we also
ensure efficiency? In addition, can we design it flexible enough to make it
applicable to static interaction networks?

##  3\. DeePRed

The proposed algorithm, DeePRed, captures both stationary and transitory
preferences of users and items in interaction networks, by maintaining two
dynamic embeddings, one long-term and one short-term, in a latent context-
space ${\mathcal{S}}$. The main hypothesis in DeePRed is that an underlying
hidden context-space ${\mathcal{S}}$ is considered to have been generated as a
result of interactions between users and items. This space is assumed to be
thematically divided into different regions that are associated to a
particular theme or context. For an intuitive understanding of ${\mathcal{S}}$
in DeePRed, let us consider an illustration shown in Fig. 2. To simplify our
discussion, suppose ${\mathcal{S}}$ is a 2-dimensional euclidean space, which
is further divided into three different thematic regions, $C_{1},C_{2},C_{3}$.
The notion of a theme/context is related to user interests (preferences) and
item properties.

The two dynamic embeddings are updated at every user-item interaction, both
for users and items. Since DeePRed applies the same procedure for both, the
following discussion is given from a user’s perspective. Suppose user $u$ has
interacted with an item relevant to context $C_{2}$ at time $t_{1}$. To
reflect such behavior, we start by initializing long-term and short-term
embeddings, which are located within the same context $C_{2}$.

As time progresses, when the user interacts with different items, new
instances of the short-term embeddings are generated by keeping the previous
ones. The new instances are shown in the figure along with a timestamp
associated to the interaction, which caused the current embedding. The
motivation for keeping the embeddings comes from a need to maintain a smooth
short-term embedding that reflects the “normal” behaviour and the property of
a user and an item, respectively. Unless there is a “significant” amount of
interactions that cause a drift in a user’s interest, for example from $C_{2}$
to $C_{1}$, “unexpected” interactions should not have a strong influence on
future behaviors (Koren, 2009). Rarely, a user might interact with items from
distant contexts (e.g. $C_{3}$); for such a temporary case, a new instance can
be projected without affecting other short-term embeddings. This allows
DeePRed to reason based on embeddings that are closer to a query than
exceptional cases. Furthermore, DeePRed gives the flexibility to use embedding
histories as needed. In addition, depending on the setting one can choose to
discard old embeddings or store them in aggregated form.

The long-term embeddings, on the other hand, are updated and shifted to a new
point, discarding the old ones. The dotted line Fig. 2 shows the trajectory of
the long-term embedding of user $u$, starting from the inactive to active. In
a nutshell, these embeddings can be seen as aggregates of the short-term ones
over time.

In platforms like YouTube, LastFM, Spotify, the flexibility proposed by
DeePRed can be utilized to recommend multi-faceted sets of items, for example
one based on short-term embeddings and another based on long-term ones. This
is in contrast to several studies that use a single embedding for
recommendation.

#### Modeling long-term interactions

The overall preferences of users and the properties of items are captured by
their long-term interactions. To capture patterns in such interactions, we use
identity-based embeddings of users and items that live in the same context
space ${\mathcal{S}}$. That is, we use an embedding matrix
${\bm{E}}\in{\mathbb{R}}^{d\times U+I}$, which will be trained as interactions
are observed; ${\bm{e}}_{u}$ and ${\bm{e}}_{i}$ denote the long-term embedding
of user $u$ and item $i$. To emphasize that ${\bm{e}}_{u}$ and ${\bm{e}}_{i}$
are conditioned on ${\mathbb{L}}_{u}$ and ${\mathbb{L}}_{i}$, we use the
notation ${\bm{e}}_{u}|{\mathbb{L}}_{u}$ and ${\bm{e}}_{i}|{\mathbb{L}}_{i}$,
respectively.

#### Modeling short-term interactions

Here the focus is in modeling recent interaction patterns of users and items
that govern their follow-up actions. To capture such patterns, we use short-
term embeddings ${{\bm{u}}(t)|{\mathbb{L}}_{u}(t^{<},k)}$ and
${{\bm{i}}(t)|{\mathbb{L}}_{i}(t^{<},k)}$ for users and items, respectively,
conditioned on their recent interactions. In previous studies, short-term
embeddings of users and items were recursively dependent on their respective
previous short-term embeddings (Kumar et al., 2019; Dai et al., 2016b). The
recursive nature of these algorithms inherently makes them expensive, as they
would need to introduce a specialized algorithm for processing batches of
interactions to avoid sequential processing. For example, Kumar et al. had to
introduce an algorithm called t-batch, that process batches by respecting the
temporal order (Kumar et al., 2019). Our design choice avoids such overhead by
relying on the interaction histories rather than the previous short-term
embeddings, which allows for “simple” batching.

Figure 2. An illustration of the evolution of the short-term and long-term
embeddings of user $u$ in a context space, which is further divided into
smaller sub-spaces reflecting a context or theme ($C_{1},C_{2},C_{3}$). The
dotted arrow indicates the trajectory of the long-term embedding (indicated in
black circle). The short-term embeddings of the user are annotated with
timestamps, which is associated with the interaction that generated them.

###  3.1. The proposed architecture

The complete architecture of DeePRed is depicted in Fig. 3. The input of
DeePRed is given by the observed interaction events and a hyper-parameter $k$
of the model.

Figure 3. The architecture of DeePRed

#### Encoder

We process the user and item histories separately, using user and item
encoders that share weights. Again, this is in contrast to previous studies
that use separate RNN modules that are dependent on previous short-term
embeddings. In DeePRed, both the user and item encoder have the same
structure; for this reason, most of our discussion is related to the user
encoder, while the item encoder is similar.

The first component of a user (item) encoder computes a signature embedding of
the short-term history using the long-term embedding of the items (users) and
the deltas as follows:

(1)
${\bm{S}}_{u}(t)=f({\mathbb{L}}_{u}(t^{<},k))=[[{\bm{e}}_{i_{j}};\Delta_{j}]:(i_{j},\Delta_{j})\in{\mathbb{L}}_{u}(t^{<},k)]$
(2)
${\bm{S}}_{i}(t)=f({\mathbb{L}}_{i}(t^{<},k))=[[{\bm{e}}_{u_{j}};\Delta_{j}]:(u_{j},\Delta_{j})\in{\mathbb{L}}_{i}(t^{<},k)]$

The simple, yet expressive and powerful trick used here is that to compute the
signature ${\bm{S}}_{u}(t)$ at time $t$, Eq. 1 relies on the long-term
embeddings of the $k$ most recent items that the user $u$ interacted with.
Equivalently, in Eq. 2, the $k$ most recent users that interacted with the
item $i$ are used to compute ${\bm{S}}_{i}(t)$. The key hypothesis is that the
long-term or stationary embeddings of _multiple items_ is a strong signal for
capturing a user’s recent interest, as each stationary embedding
${\bm{e}}_{i_{j}}\in{\bm{S}}_{u}(t)$ captures a sticking property or context
(e.g. SciFi) of item $i_{j}$. In addition, note that the signature at time $t$
contains information only from the _past_ , as we want to predict the present.

Furthermore, it has been shown that the delay between interactions plays a
significant role in predicting future interactions. Thus, each long-term
embedding is combined $[\cdot;\cdot]$ with $\Delta_{j}$ in the signature to
increase the impact of fresh activities and decrease the importance of the
stale ones. Note that, some studies use a decay function of $\Delta_{j}$
instead, e.g. ${g(\Delta_{j})=1/\log(e+\Delta_{j})}$ (Zhang et al., 2019; Zhu
et al., 2017; Beutel et al., 2018). In our experiments we found no difference
between these approaches, and hence we simply use $\Delta_{j}$.

Second, to model recurring interaction and delay patterns in a history, we
employ shared and mutual RNN modules over the signatures, ${\bm{S}}_{u}(t)$
and ${\bm{S}}_{i}(t)$. Empirically, Gated Recurrent units (GRU) tend to give
better performance, thus we use GRU instead of the basic RNN. Therefore, the
standard GRU model for capturing recurrence in a signature ${\bm{S}}(t)$ (user
or item) slightly modified to integrate $\Delta_{j}$ is given as

(3) $\displaystyle{\bm{z}}_{j}$
$\displaystyle=\sigma({\bm{W}}_{1z}{\bm{e}}_{j}+{\bm{b}}_{1z}+{\bm{W}}_{2z}\Delta_{j}+{\bm{b}}_{2z}+{\bm{W}}_{3z}{\bm{h}}_{j-1}+{\bm{b}}_{3z})$
(4) $\displaystyle{\bm{r}}_{j}$
$\displaystyle=\sigma({\bm{W}}_{1r}{\bm{e}}_{j}+{\bm{b}}_{1r}+{\bm{W}}_{2r}\Delta_{j}+{\bm{b}}_{2r}+{\bm{W}}_{3r}{\bm{h}}_{j-1}+{\bm{b}}_{3r})$
(5) $\displaystyle{\bm{n}}_{j}$
$\displaystyle=\tanh({\bm{W}}_{1n}{\bm{e}}_{j}+{\bm{b}}_{1n}+{\bm{W}}_{2n}\Delta_{j}+{\bm{b}}_{2n}+{\bm{z}}_{j}*({\bm{W}}_{3n}{\bm{h}}_{j-1}+{\bm{b}}_{3n}))$
(6) $\displaystyle{\bm{h}}_{j}$
$\displaystyle=(1-{\bm{r}}_{j})*{\bm{n}}_{j}+{\bm{r}}_{j}*{\bm{h}}_{j-1}$

where $\sigma$ is the sigmoid function and ${\bm{W}}_{pq}$, ${\bm{b}}_{pq}$,
${p\in\\{1,2,3\\}}$ and ${q\in\\{z,r,n\\}}$ are the parameters of the model
shared by the encoders; ${\bm{e}}_{j}$ corresponds to either
${\bm{e}}_{i_{j}}$ or ${\bm{e}}_{u_{j}}$ depending on the specified signature.
At each step $j$, a new hidden state ${\bm{h}}_{j}$ is computed using the
$j^{\textrm{th}}$ step inputs of ${\bm{S}}(t)$, _i.e._ the long-term embedding
${\bm{e}}_{j}$ and $\Delta_{j}$, and the previous hidden state
${\bm{h}}_{j-1}.$

Finally, we concatenate the hidden states of the GRU as

(7) ${\bm{F}}(t)=[{\bm{h}}_{1},\ldots,{\bm{h}}_{k}]$

in order to obtain a high-level feature matrix of the signature at time $t$
that captures recurring interaction and delay patterns. Again, depending on
the encoder, ${\bm{F}}(t)$ is either ${\bm{F}}_{u}(t)$ or ${\bm{F}}_{i}(t)$.

#### Alignment

Recall that both the user’s and item’s long-term embeddings live in the same
space, and the high-level features ${\bm{F}}_{u}(t)$ and ${\bm{F}}_{i}(t)$ are
derived based on such embeddings. Thus, as shown in Eq. 8, the alignment
component is used to inspect the compatibility between these features, to see
how well the recent events of $u$ and $i$ agree contextually.

(8) ${\bm{A}}(t)=\tanh({\bm{F}}_{u}(t)^{T}{\bm{F}}_{i}(t))$

We can interpret each row $j$ of ${\bm{A}}(t)\in{\mathbb{R}}^{k\times k}$ as a
measure of context agreement between the $j^{\textrm{th}}$ item in the given
user’s $(u)$ short-term history with all the users in the given item’s $(i)$
short-term history at time $t$. In Eq. 8, similar to (dos Santos et al., 2016;
Kefato and Girdzijauskas, 2020b), one can add more degree of freedom by
introducing a trainable parameter $\Theta\in{\mathbb{R}}^{d\times d}$
depending on the problem setting as in the following equation:

(9) ${\bm{A}}(t)=\tanh({\bm{F}}_{u}(t)^{T}\Theta{\bm{F}}_{i}(t))$

However, we have empirically observed that for the problem at hand, fixing
$\Theta$ to the identity matrix ${\bm{I}}$ gives a better result. When Eq. 9
is applied, DeePRed tends to overfit faster even with a strong regularization;
as a result, we opted for Eq. 8 instead. Hence, the only free parameters of
DeePRed are the long-term embedding ${\bm{E}}$ and the GRU parameters.

#### Attention + Projection

Finally, we want to pay attention to the strong context agreements in
${\bm{A}}(t)$, signaled by high scores, in order to obtain embeddings that
reflect short-term behaviours. In other words, we want to investigate the
compatibility between the recent interest of a user and the property of an
item to understand where the agreement lies. To this end, we compute attention
weights for each item in the user’s recent history (and vice-versa for each
user in the item’s recent history) using a column-wise (${\bm{X}}_{\bullet:}$)
and row-wise (${\bm{X}}_{:\bullet}$) max-pooling as shown in Eq. 10 and 11,
respectively.

(10) $\tilde{{\bm{u}}}(t)=\max{{\bm{A}}(t)_{\bullet:}}$ (11)
$\tilde{{\bm{i}}}(t)=\max{{\bm{A}}(t)_{:\bullet}}$

The $j^{\textrm{th}}$ component $\tilde{{\bm{u}}}_{j}(t)$ of the vector
${\tilde{{\bm{u}}}(t)\in{\mathbb{R}}^{k}}$ corresponds to the attention weight
of the $j^{\textrm{th}}$ event,
$(i_{j},\Delta_{j})\in{\mathbb{L}}_{u}(t^{<},k)$. It indicates:

  * $\square$

the strongest alignment (contextual agreement) of the $j^{\textrm{th}}$ item
$i_{j}$ from all the users in the short-term history
${\mathbb{L}}_{i}(t^{<},k)$ of the item $i$

  * $\square$

the hotness of the event

and it is the result of the column-wise pooling on the $j^{\textrm{th}}$ row,
$\max({\bm{A}}(t)_{j:})$. These two interpretations of the attention weights
are based on the assumption that future activities are governed by recent
actions and interest (Zhang et al., 2019; Nguyen et al., 2018; Zhu et al.,
2017). Inversely, stale events should have less impact on future interactions.

Equivalently, the $j^{\textrm{th}}$ component $\tilde{{\bm{i}}}_{j}(t)$ of
${\tilde{{\bm{i}}}(t)\in{\mathbb{R}}^{k}}$ represents the attention weights of
the $j^{\textrm{th}}$ event, $(u_{j},\Delta_{j})\in{\mathbb{L}}_{i}(t^{<},k)$
and it is the result of the row-wise pooling on the $j^{\textrm{th}}$ column,
$\max({\bm{A}}(t)_{:j})$. The interpretation remains the same.

In this way, each item in the user history and each user in the item history
are now scored in relation to their contextual agreement, from which we obtain
the compatibility between the interacting user and item. Alternatively, we
have used mean-pooling in Eq. 10 and 11 and empirically observed no
difference.

At this point, we _project_ a new point representing the short-term interest
and properties using the normalized attention weights. Eq. 12 and 13 compute
the user and item projection using the weighted sum of the features
${\bm{F}}_{u}(t)$ and ${\bm{F}}_{i}(t)$, respectively.

(12)
${\bm{u}}(t)={\bm{F}}_{u}(t)\cdot\texttt{softmax}(\tilde{{\bm{u}}}(t)^{T})$
(13)
${\bm{i}}(t)={\bm{F}}_{i}(t)\cdot\texttt{softmax}(\tilde{{\bm{i}}}(t)^{T})$

Both equations can be seen as feature selectors based on contextual agreement
and freshness. That is, they select those features that have a strong
contextual agreement and are relatively new as indicated by the magnitude of
the attention weights. The $\texttt{softmax}(\cdot)$ function gives us a
distribution of weights for events in the short-term history of $u$ and $i$.
That is, fresh and contextually agreeing events will get weights close to 1,
otherwise close to 0. We argue that the model can learn in a way that weights
are distributed in the aforementioned manner. As desired, consequently,
weighted features with weights close to 1 will govern the projections. We
consider ${\bm{u}}(t)$ and ${\bm{i}}(t)$ as predictions of the short-term
embeddings of the user and item at time $t$, respectively.

###  3.2. Training DeePRed

Similarly to previous work (Kumar et al., 2019), DeePRed predicts the user and
item embeddings, albeit in a different manner. Thus, we employ a similar loss
function using mean squared error. Our goal is to jointly train the long-term
and short-term embeddings in order to bring the projection of frequently
interacting items as close as possible. To this end, we minimize the $L_{2}$
distance as

(14)
${\mathcal{L}}=\min\frac{1}{N}\sum_{(u,i,t)\in{\mathbb{L}}_{train}}||{\bm{u}}(t)-{\bm{i}}(t)||_{2}^{2}+{\mathcal{L}}_{reg}$

where $N$ is the batch size for batch training and ${\mathbb{L}}_{train}$ is
the observed event log in the training set. The second term on the RHS of Eq.
14, a regularization loss, is introduced to avoid the trivial solution of
collapsing into a subspace. It is motivated by the Laplacian eigenmaps method,
which adds the constraint ${\bm{u}}(t)^{T}{\bm{i}}(t)=1$ to avoid the
collapse. Therefore, we specify ${\mathcal{L}}_{reg}$ as

(15) ${\mathcal{L}}_{reg}=\gamma*||{\bm{v}}^{T}{\bm{v}}-{\bm{I}}||_{F}^{2}$

where ${\bm{v}}=[{\bm{u}}(t);{\bm{i}}(t)]\in{\mathbb{R}}^{d\times 2}$ and
$\gamma$ is a regularization coefficient. ${\mathcal{L}}_{reg}$ encourages
points to be similar to themselves but not others. Given that we predict
embeddings following (Belkin and Niyogi, 2003; Kumar et al., 2019) as opposed
to scores as in (Dai et al., 2016b), we do not need for a contrastive loss in
Eq. 14.

Since our algorithm is designed in such a way that the short-term embeddings
at time $t$ are not dependent on the ones at time $t-1$, batching is
straightforward and DeePRed incurs in no overhead from batch processing unlike
the work of Kumar et al. (Kumar et al., 2019). Together with design choices
explained above, this makes DeePRed efficient, as demonstrated in Section 4.

###  3.3. DeePRed for Static Networks

DeePRed requires only minor changes to be applicable to static interaction
networks, as explained below.

The first obvious change is the lack of time, and consequently the lack of
order; we consider ${\mathbb{L}}$ to be an unordered set. Thus, the notion of
“long-term” and “short-term” interactions is meaningless. Instead, the
equivalent idea in static networks is “global” for “long-term” and “context-
aware” for “short-term”. Global interactions are modeled as
$({\bm{e}}_{u}|{\mathbb{L}}_{u}$ or ${\bm{e}}_{i}|{\mathbb{L}}_{i})$ using
almost all the observed events in no specific order. We refer to the
corresponding embeddings as _global embeddings_. Similarly, context-aware
interactions are modeled using _context-aware embeddings_
${\bm{u}}|{\mathbb{L}}_{u}(k)$ or ${\bm{i}}|{\mathbb{L}}_{i}(k)$ conditioned
on $k$ randomly sampled events. The context-aware embeddings are in line with
recent studies that argue against the adequacy of using a single embedding per
node (Epasto and Perozzi, 2019; Liu et al., 2019; Yang et al., 2020; Kefato
and Girdzijauskas, 2020a; Tu et al., 2017). Each node, instead, is represented
by multiple embeddings reflecting the multi-dimensional aspect of a node’s
interest or property.

Thus, the input is specified by each interaction $(u,i)\in{\mathbb{L}}$ and
$k$. The user and item encoders take ${\mathbb{L}}_{u}(k)$ and
${\mathbb{L}}_{i}(k)$; encoding amounts to a simple embedding lookup and
concatenation operation, to generate ${\bm{F}}_{u}$ and ${\bm{F}}_{i}$
ignoring the GRU model. The followup steps are a straightforward application
of the _alignment_ first, followed by _attention + projection_ to obtain the
context-aware embeddings ${\bm{u}}$ and ${\bm{i}}$.

##  4\. Empirical Evaluation

We evaluate the performance of the proposed algorithm using three real-world
temporal interaction networks and we compare DeePRed against seven state-of-
the-art baselines.

Method | Reddit | Wikipedia | LastFM |  | Minimum % of improvement
---
of DeePRed over method
MRR | Recall@10 | MRR | Recall@10 | MRR | Recall@10 | MRR | Recall@10
lstm | 0.355 | 0.551 | 0.329 | 0.455 | 0.062 | 0.119 | 133.23 % | 51.17 %
TimeLstm | 0.387 | 0.573 | 0.247 | 0.342 | 0.068 | 0.137 | 113.95 % | 45.37 %
rrn | 0.603 | 0.747 | 0.522 | 0.617 | 0.089 | 0.182 | 37.13 % | 11.51 %
LatentCross | 0.421 | 0.588 | 0.424 | 0.481 | 0.148 | 0.227 | 96.67 % | 41.67 %
ctdne | 0.165 | 0.257 | 0.035 | 0.056 | 0.01 | 0.01 | 401.81 % | 224.12 %
DeepCoEvolve | 0.171 | 0.275 | 0.515 | 0.563 | 0.019 | 0.039 | 71.84 % | 57.90 %
Jodie | 0.726 | 0.852 | 0.746 | 0.822 | 0.195 | 0.307 | 14.04 % | -2.23 %
DeePRed | 0.828 | 0.833 | 0.885 | 0.889 | 0.393 | 0.416 | - | -
% gain over Jodie | 14.04 % | -2.23 % | 18.63 % | 8.15 % | 101.53 % | 35.50 % | - | -
Table 1. The comparison of the empirical results between DeePRed and the
baseline methods for the three temporal datasets. Bold and blue highlight
indicate best and second best performing algorithms, respectively

###  4.1. Datasets

The three publicly available datasets we selected are the following:

  * •

Reddit (Kumar et al., 2019) contains post interactions by users on subreddits
(items), over a period of one month. The most active users (10,000) and items
(1,000) are collected, with 672,447 interactions in total. Actions are
repeated 79% of the time.

  * •

Wikipedia (Kumar et al., 2019) contains edit interactions by editors (users)
on Wikipedia pages (items) over a period of one month. 8,227 editors with at
least 5 edits and the 1,000 most edited pages are included, for a total of
157,474 interactions. Actions are repeated 61% of the time.

  * •

LastFM (Kumar et al., 2019) contains listening activities by users on songs
(items), over a period of one month, restricted to 1,000 users who listened to
the 1,000 most-listened songs, with 1,293,103 interactions in total. Actions
are repeated 8.6% of the time.

###  4.2. Baselines

We compare DeePRed with seven state-of-the-art algorithms commonly used in
recommender systems, grouped as follows:

  * •

Sequence models are different flavors of RNNs trained based on item-sequence
data: lstm, TimeLstm (Zhu et al., 2017), rrn (Wu et al., 2017), LatentCross
(Beutel et al., 2018)

  * •

Bipartite models are baselines based on bipartite interaction graph and employ
mutually recursive RNNs: DeepCoEvolve (Dai et al., 2016a), Jodie (Kumar et
al., 2019).

  * •

Graph base model: finally, we have ctdne based on continuous time graph
embedding using temporal random walks.

###  4.3. Next Item Prediction Experiment

Based on observations of recent interactions with items, the goal is to
predict the next item a user is likely to interact with. This is what lies at
the backbone of a number of RS.

#### Setting

We use the same partitions used by Kumar et al. (Kumar et al., 2019), _i.e._
data is partitioned by respecting the temporal ordering of events as training
(80%), validation (10%), and test (10%). During training, we use the
validation set to tune the hyperparameters of our model using Bayesian
optimization.

During testing, given a ground-truth interaction $(u,i,t)$, DeePRed predicts a
ranked list of the top-$k$ items that $u$ will interact with at time $t$,
based on previous interactions ${\mathbb{L}}_{u}(t^{<},k)$ and
${\mathbb{L}}_{i}(t^{<},k)$. Since DeePRed predicts short-term embeddings, as
opposed to interaction probabilities, we can use an efficient nearest-neighbor
search to predict the top-$k$ items. We use mean reciprocal rank (MRR) and
Recall@10 to measure the quality of the ranked list.

#### Results

Results are reported in Table 1. Since all the settings are exactly the same,
the figures for all the baselines are directly taken from Kumar et al. (Kumar
et al., 2019).

DeePRed outperforms all the baselines by a significant margin in all but one
case. Almost all the baselines have a huge gap between MRR and Recall@10,
unlike the small gap of DeePRed. This shows that DeePRed ranks the ground
truth higher, while others simply detect it in lower positions in the top-10
predicted items. For example, for the only case where Jodie beats DeePRed by a
small margin, the Recall@1 is 0.648 for Jodie and 0.813 for DeePRed.

#### Effect of features

One might ask, and rightly so, why not include a richer set of features in
DeePRed, as in previous works (Beutel et al., 2018; Kumar et al., 2019; Dai et
al., 2016a). First, some of these features (software client, page) are not
easily accessible (Beutel et al., 2018). Other features, such as the textual
content, could be easily integrated into our model without affecting the
architecture; anyway, we found no difference for the three datasets. To verify
this, we have further investigated what happens when you remove textual
features from the strongest baseline, Jodie. As shown in Table 2, JodieNF
(Jodie with no features) performs as well as Jodie, if not better, for the two
datasets with textual interaction features.

Method | Reddit | Wikipedia
---|---|---
MRR | Recall@10 | MRR | Recall@10
Jodie | 0.726 | 0.852 | 0.746 | 0.822
JodieNF | 0.726 | 0.852 | 0.759 | 0.824
Table 2. Jodie vs JodieNF

###  4.4. Runtime Experiment

Figure 4. The computational time (in minutes) required to complete an epoch
using the Reddit dataset.

To empirically compare DeePRed’s efficiency, we measured the time needed to
run the models. In Fig. 4, we report the comparison between the methods for
completing an epoch using the Reddit dataset. We see that DeePRed is much
faster than all the baselines. Since we are using the figures from (Kumar et
al., 2019), Fig. 4 might not be a fair comparison as the machines are
different. Hence, we rerun Jodie on our machine and it took 15 minutes to
complete the same epoch, showing that the speedup by DeePRed is even better,
more than an order of magnitude.

###  4.5. Hyperparameter sensitivity experiment

In this section, we analyze the effect of different hyperparameters of the
methods on next item prediction. We simply compare DeePRed with Jodie, since
it is much better than all the other baselines.

#### Impact of proportion of training size

Despite their gap, as shown in Fig. 5, for both methods the observation of 60%
of the events is sufficient for effective next item prediction on Reddit and
Wikipedia. On the contrary, DeePRed executed on LastFM keeps improving as
repeated actions are sparse and patterns might emerge from observing more
examples.

#### Impact of Embedding Size

Fig. 6 shows the impact of the embedding size; for DeePRed, 128 is an optimal
value, while for Jodie this parameter has no influence, almost.

#### Effect of $k$

Parameter $k$, the number of short-term events in ${\mathbb{L}}_{u}(t^{<},k)$
and ${\mathbb{L}}_{i}(t^{<},k)$, affects DeePRed only. Our findings are
reported in Fig. 7; we observe that $k$ has different effects across datasets.
In LastFM, increasing the number of events produces an improvement; in Reddit,
there is no effect; in Wikipedia, a declining effect can be observed. Recall
that, actions are seldom repeated globally in LastFM, implying that repeated
actions are locally sparse; for this reason, interaction patterns are detected
by increasing the volume of retrospective observations.

Figure 5. Effect of training proportion Figure 6. Effect of embedding size
Figure 7. Effect of the short-term history size

###  4.6. Static Networks’ Experiment

We discuss now our experiments carried out on three static networks. Although
DeePRed performs well, our goal here is to show its potential and flexibility,
rather than report its superiority.

#### Datasets

We use the following static interaction networks:

  * •

MATADOR (Manually Annotated Targets and Drugs Online Resource) (S et al.,
2008) is a drug-target interaction network, with 801 drugs (users) 2,901
targets (items), and 15,843 interactions.

  * •

SIDER (Side Effect Resource version 4.1) (M et al., 2015) is a drug (user) and
side-effects (item) association dataset. There are 639 users, 10,184 items and
174,977 interactions (associations).

  * •

STEAM (ste, [n.d.]) is a popular PC gaming hub dataset, containing games
(items) users have purchased. There are 12,393 users, 5,155 games, and 129,511
purchasing actions.

#### Baselines

We use four baselines grouped as follows:

  * •

Context-aware: Splitter (Epasto and Perozzi, 2019) is a SOTA context-aware
baseline; similarly to DeePRed, it learns multiple embeddings of nodes for
static networks.

  * •

Context-free Deepwalk (Perozzi et al., 2014), Node2vec (Grover and Leskovec,
2016) and line (Tang et al., 2015) are popular baselines used for static
network embedding

Figure 8. The Average Precision result for interaction prediction on static
networks

The interaction prediction is executed as a link prediction task, where we
create a random partition of the graph as training (60%), validation (10%),
and test (30%) sets. In addition, we randomly sample non-existing (negative)
interactions proportional to the test set (30%). An algorithm is trained on
the training set and tuned on the validation set. The average precision (AP),
which summarizes the precision-recall curve is then computed based on a
method’s capacity to rank the test (true) over negative (false) interactions.
The results are reported in Fig 8, where we see that DeePRed is comparable
with a context-aware and much better than context-free baselines.

##  5\. Related Work

Factorization methods have significantly influenced the study of recommender
systems (RS), more prominently since the Netflix prize competition. However,
as deep neural networks (DNNs) gained momentum across several domains, several
studies have shown the effectiveness of DNNs in RS as well (Covington et al.,
2016; Jing and Smola, 2017; Wang et al., 2019; Wu et al., 2017). Early efforts
used a vanilla DNN architecture by integrating crafted and learned features
into the models (Covington et al., 2016).

As recurring patterns in user-item interactions are considered to be critical
in recommending or predicting future activities, recurrent neural networks
(RNNs) and its variants have been widely used in interaction prediction or RS.

###  5.1. RNNs for Recommender Systems

RNNs are inherently suited for modeling patterns in sequential data, such as
language and time-series. Due to their effectiveness, they have seen
applicability in different areas, such as NLP, speech recognition, computer
vision, and health–just to name a few.

Initial efforts in RS have employed RNNs by simply using a sequence of user
actions in order to capture repeated user activity patterns, and model their
preference or behavior (Wu et al., 2017; Tan et al., 2016; Hidasi et al.,
2015). This approach has further been used to predict interesting items for
users based on their preference, for example on platforms like YouTube,
Spotify, LastFM. However, standard RNNs and its variants (LSTM, GRU) can only
capture recurrence and do not encode delay or interval between activities,
which is an intrinsic nature of user behaviours. This is because activities
that are close to an event in time are more likely to trigger such event than
the ones that are far apart.

###  5.2. Time-based RNNs

Motivated by the aforementioned need, extensions to RNNs (LSTM, GRU) have been
introduced to account for time. In addition to the existing gating mechanisms
in RNNs, these studies have introduced different time-gating mechanisms to
favor new events and discount the impact of old ones (Zhu et al., 2017; Zhang
et al., 2019). Novelty or oldness refer to the delta in time, not to the
position of events in a sequence.

###  5.3. Mutual RNNs

Closely related to our study, recently mutual RNNs for next item prediction
have been proposed (Kumar et al., 2019; Dai et al., 2016a). A simple yet
powerful aspect of these approaches is the bipartite temporal interaction
network model, and the mutual RNN architecture that paved a way to examine
user-item interaction dynamics. However, besides the essential differences in
modeling short-term embeddings of users and items, DeePRed is also different
in using shared and non-recursive mutual RNNs.

###  5.4. Other methods

Besides RNNs, other methods such as graph neural networks (GNN) and
transformers have also been employed in RS (Vaswani et al., 2017). The former
was introduced for neural collaborative-filtering and session-based RS (Wang
et al., 2020; Wu et al., 2019; Xu et al., 2019; Wang et al., 2019). Due to the
ever increasing impact of transformers for modeling sequential data, several
studies proposed this model for predicting next basket items (Kang and
McAuley, 2018; Sun et al., 2019; Xu et al., 2019). Training transformers has
proved to be much more efficient than RNNs, as they are highly parallelizable.
However, the core component of transformers– _self-attention_ –has the
tendency to distribute attention weights and discounting impact from local
dependencies (Xu et al., 2019).

##  6\. Conclusion and Future Work

In this study we present a novel algorithm called DeePRed for next item
prediction in temporal interaction networks. Building up on recent
achievements, DeePRed captures the mutual interaction dynamics in the
interactions between users and items. We propose a simple yet powerful
mechanism to model both user and item short-term preferences based on the
their recent interaction history. The history serves as proxy for the context
of interaction in recent events. We leverage the mechanism to avoid recursive
dependency between consecutive short-term embeddings of a user or an item over
time. Our design enables DeePRed to be effective in predicting next item
interaction without compromising efficiency.

Our empirical finding on three real-world datasets demonstrate the
effectiveness of DeePRed over seven SOTA baselines by at least 14%. In
addition, DeePRed is at least an order of magnitude faster than the best
performing baselines.

We have also shown that the design of DeePRed is flexible enough to
accommodate static networks. As a demonstration, we show how well it performs
for interaction prediction over bio-chemical and gaming interaction networks.

Though maintaining multiple embeddings in DeePRed is what lies behind its
effectiveness, it comes at the cost of memory. As GPU memory is expensive,
this calls for an improved design for DeePRed, that will be addressed in
future work.

##  Appendix A DeePRed Configuration

Table A1 shows the final configurations of DeePRed used to report the results
in Section 4. The experiments are executed on an NVIDIA QUADRO RTX 5000 GPU
with NVLink, 3072 CUDA cores, and 16 GB GDDR6 memory.

Table A1. The configuration of DeePRed’s hyperparameters

## References

  * (1)
  * ste ([n.d.]) [n.d.].  https://www.kaggle.com/tamber/steam-video-games.
  * Belkin and Niyogi (2003) M. Belkin and P. Niyogi. 2003.  Laplacian Eigenmaps for Dimensionality Reduction and Data Representation.  _Neural Computation_ 15, 6 (2003), 1373–1396.
  * Beutel et al. (2018) Alex Beutel, Paul Covington, Sagar Jain, Can Xu, Jia Li, Vince Gatto, and Ed H. Chi. 2018.  Latent Cross: Making Use of Context in Recurrent Recommender Systems. In _Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining_ (Marina Del Rey, CA, USA) _(WSDM ’18)_. Association for Computing Machinery, New York, NY, USA, 46–54.  https://doi.org/10.1145/3159652.3159727
  * Buza and Peška (2017) Krisztian Buza and Ladislav Peška. 2017.  Drug–target interaction prediction with Bipartite Local Models and hubness-aware regression.  _Neurocomputing_ 260 (2017), 284 – 293.  https://doi.org/10.1016/j.neucom.2017.04.055
  * Covington et al. (2016) Paul Covington, Jay Adams, and Emre Sargin. 2016\.  Deep Neural Networks for YouTube Recommendations. In _Proceedings of the 10th ACM Conference on Recommender Systems_ (Boston, Massachusetts, USA) _(RecSys ’16)_. Association for Computing Machinery, New York, NY, USA, 191–198.  https://doi.org/10.1145/2959100.2959190
  * Dai et al. (2016a) Hanjun Dai, Yichen Wang, Rakshit Trivedi, and Le Song. 2016a.  Deep Coevolutionary Network: Embedding User and Item Features for Recommendation.  arXiv:1609.03675 [cs.LG]
  * Dai et al. (2016b) Hanjun Dai, Yichen Wang, Rakshit Trivedi, and Le Song. 2016b.  Recurrent Coevolutionary Feature Embedding Processes for Recommendation.  _CoRR_ abs/1609.03675 (2016).  arXiv:1609.03675 http://arxiv.org/abs/1609.03675
  * dos Santos et al. (2016) Cicero dos Santos, Ming Tan, Bing Xiang, and Bowen Zhou. 2016\.  Attentive Pooling Networks.  arXiv:1602.03609 [cs.CL]
  * Epasto and Perozzi (2019) Alessandro Epasto and Bryan Perozzi. 2019.  Is a Single Embedding Enough? Learning Node Representations that Capture Multiple Social Contexts.  _The World Wide Web Conference on - WWW ’19_ (2019).  https://doi.org/10.1145/3308558.3313660
  * Grover and Leskovec (2016) Aditya Grover and Jure Leskovec. 2016.  node2vec: Scalable Feature Learning for Networks.  _CoRR_ abs/1607.00653 (2016).  arXiv:1607.00653 http://arxiv.org/abs/1607.00653
  * Hidasi et al. (2015) Balázs Hidasi, Alexandros Karatzoglou, Linas Baltrunas, and Domonkos Tikk. 2015.  Session-based Recommendations with Recurrent Neural Networks.  arXiv:1511.06939 [cs.LG]
  * Jing and Smola (2017) How Jing and Alexander J. Smola. 2017.  Neural Survival Recommender. In _Proceedings of the Tenth ACM International Conference on Web Search and Data Mining_ (Cambridge, United Kingdom) _(WSDM ’17)_. Association for Computing Machinery, New York, NY, USA, 515–524.  https://doi.org/10.1145/3018661.3018719
  * Kang and McAuley (2018) Wang-Cheng Kang and Julian McAuley. 2018.  Self-Attentive Sequential Recommendation.  arXiv:1808.09781 [cs.IR]
  * Kefato and Girdzijauskas (2020a) Zekarias T. Kefato and Sarunas Girdzijauskas. 2020a.  Gossip and Attend: Context-Sensitive Graph Representation Learning. In _14-th International AAAI Conference on Web and Social Media_ _(ICWSM’20)_.  arXiv:2004.00413 [cs.LG] https://arxiv.org/abs/2004.00413
  * Kefato and Girdzijauskas (2020b) Zekarias T. Kefato and Sarunas Girdzijauskas. 2020b.  Graph Neighborhood Attentive Pooling.  arXiv:2001.10394 [cs.LG]
  * Koren (2009) Yehuda Koren. 2009\.  Collaborative Filtering with Temporal Dynamics. In _Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ (Paris, France) _(KDD ’09)_. Association for Computing Machinery, New York, NY, USA, 447–456.  https://doi.org/10.1145/1557019.1557072
  * Kumar et al. (2019) Srijan Kumar, Xikun Zhang, and Jure Leskovec. 2019\.  Predicting Dynamic Embedding Trajectory in Temporal Interaction Networks. In _Proceedings of the 25th ACM SIGKDD international conference on Knowledge discovery and data mining_.
  * Liu et al. (2019) Ninghao Liu, Qiaoyu Tan, Yuening Li, Hongxia Yang, Jingren Zhou, and Xia Hu. 2019\.  Is a Single Vector Enough?  _Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ (Jul 2019).  https://doi.org/10.1145/3292500.3330967
  * M et al. (2015) Kuhn M, Letunic I, Jensen LJ, and Bork P. 2015\.  The SIDER database of drugs and side effects.. In _Nucleic Acids Res_.  https://doi.org/10.1093/nar/gkv1075
  * Nguyen et al. (2018) Giang Hoang Nguyen, John Boaz Lee, Ryan A. Rossi, Nesreen K. Ahmed, Eunyee Koh, and Sungchul Kim. 2018.  Continuous-Time Dynamic Network Embeddings. In _Companion Proceedings of the The Web Conference 2018_ (Lyon, France) _(WWW ’18)_. International World Wide Web Conferences Steering Committee, Republic and Canton of Geneva, CHE, 969–976.  https://doi.org/10.1145/3184558.3191526
  * Perozzi et al. (2014) Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. 2014\.  DeepWalk: Online Learning of Social Representations.  _CoRR_ abs/1403.6652 (2014).  arXiv:1403.6652 http://arxiv.org/abs/1403.6652
  * S et al. (2008) Günther S, Kuhn M, Dunkel M, Campillos M, Senger C, Petsalaki E, Ahmed J, Urdiales EG, Gewiess A, Jensen LJ, Schneider R, Skoblo R, Russell RB, Bourne PE, Bork P, and Preissner R. 2008\.  SuperTarget and Matador: resources for exploring drug-target relationships.. In _Nucleic Acids Res_.
  * Sun et al. (2019) Fei Sun, Jun Liu, Jian Wu, Changhua Pei, Xiao Lin, Wenwu Ou, and Peng Jiang. 2019.  BERT4Rec: Sequential Recommendation with Bidirectional Encoder Representations from Transformer. In _Proceedings of the 28th ACM International Conference on Information and Knowledge Management_ (Beijing, China). Association for Computing Machinery, New York, NY, USA.  https://doi.org/10.1145/3357384.3357895
  * Tan et al. (2016) Yong Kiam Tan, Xinxing Xu, and Yong Liu. 2016.  Improved Recurrent Neural Networks for Session-Based Recommendations. In _Proceedings of the 1st Workshop on Deep Learning for Recommender Systems_. ACM, 17–22.  https://doi.org/10.1145/2988450.2988452
  * Tang et al. (2015) Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. 2015\.  LINE: Large-scale Information Network Embedding.  _CoRR_ abs/1503.03578 (2015).  arXiv:1503.03578 http://arxiv.org/abs/1503.03578
  * Tu et al. (2017) Cunchao Tu, Han Liu, Zhiyuan Liu, and Maosong Sun. 2017\.  CANE: Context-Aware Network Embedding for Relation Modeling. In _Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_. Association for Computational Linguistics, Vancouver, Canada, 1722–1731.  https://doi.org/10.18653/v1/P17-1158
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, undefinedukasz Kaiser, and Illia Polosukhin. 2017.  Attention is All You Need. In _Proceedings of the 31st International Conference on Neural Information Processing Systems_ (Long Beach, California, USA) _(NIPS’17)_. Curran Associates Inc., Red Hook, NY, USA, 6000–6010.
  * Wang et al. (2019) Xiang Wang, Xiangnan He, Meng Wang, Fuli Feng, and Tat-Seng Chua. 2019.  Neural Graph Collaborative Filtering. In _Proceedings of the 42nd International ACM SIGIR Conference on Research and Development in Information Retrieval_ (Paris, France) _(SIGIR’19)_. Association for Computing Machinery, New York, NY, USA, 165–174.  https://doi.org/10.1145/3331184.3331267
  * Wang et al. (2020) Ziyang Wang, Wei Wei, Gao Cong, Xiao-Li Li, Xian-Ling Mao, and Minghui Qiu. 2020\.  Global Context Enhanced Graph Neural Networks for Session-Based Recommendation. In _Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval_ (Virtual Event, China) _(SIGIR ’20)_. Association for Computing Machinery, New York, NY, USA, 169–178.  https://doi.org/10.1145/3397271.3401142
  * Wu et al. (2017) Chao-Yuan Wu, Amr Ahmed, Alex Beutel, Alexander J. Smola, and How Jing. 2017.  Recurrent Recommender Networks. In _Proceedings of the Tenth ACM International Conference on Web Search and Data Mining_ (Cambridge, United Kingdom) _(WSDM ’17)_. Association for Computing Machinery, New York, NY, USA, 495–503.  https://doi.org/10.1145/3018661.3018689
  * Wu et al. (2019) Shu Wu, Yuyuan Tang, Yanqiao Zhu, Liang Wang, Xing Xie, and Tieniu Tan. 2019\.  Session-Based Recommendation with Graph Neural Networks.  _Proceedings of the AAAI Conference on Artificial Intelligence_ 33 (Jul 2019), 346–353.  https://doi.org/10.1609/aaai.v33i01.3301346
  * Xu et al. (2019) Chengfeng Xu, Pengpeng Zhao, Yanchi Liu, Victor S. Sheng, Jiajie Xu, Fuzhen Zhuang, Junhua Fang, and Xiaofang Zhou. 2019\.  Graph Contextualized Self-Attention Network for Session-based Recommendation. In _Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI-19_. International Joint Conferences on Artificial Intelligence Organization, 3940–3946.  https://doi.org/10.24963/ijcai.2019/547
  * Yang et al. (2020) Carl Yang, Aditya Pal, Andrew Zhai, Nikil Pancha, Jiawei Han, Charles Rosenberg, and Jure Leskovec. 2020.  MultiSage: Empowering GCN with Contextualized Multi-Embeddings on Web-Scale Multipartite Networks. In _Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ _(KDD ’20)_. ACM, 2434–2443.  https://doi.org/10.1145/3394486.3403293
  * You et al. (2019) Jiaying You, Robert D. McLeod, and Pingzhao Hu. 2019\.  Predicting drug-target interaction network using deep learning model.  _Computational Biology and Chemistry_ (2019).  http://www.sciencedirect.com/science/article/pii/S1476927119301902
  * Zhang et al. (2019) Yuan Zhang, Xi Yang, Julie Ivy, and Min Chi. 2019\.  ATTAIN: Attention-based Time-Aware LSTM Networks for Disease Progression Modeling. In _Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI-19_. International Joint Conferences on Artificial Intelligence Organization, 4369–4375.  https://doi.org/10.24963/ijcai.2019/607
  * Zhu et al. (2017) Yu Zhu, Hao Li, Yikang Liao, Beidou Wang, Ziyu Guan, Haifeng Liu, and Deng Cai. 2017.  What to Do next: Modeling User Behaviors by Time-LSTM. In _Proceedings of the 26th International Joint Conference on Artificial Intelligence_ (Melbourne, Australia) _(IJCAI’17)_. AAAI Press, 3602–3608.
  * Zitnik et al. (2018) Marinka Zitnik, Monica Agrawal, and Jure Leskovec. 2018\.  Modeling polypharmacy side effects with graph convolutional networks.  _Bioinformatics_ (2018).  https://doi.org/10.1093/bioinformatics/bty294


# Generalized Step-Chirp Sequences With Flexible Bandwidth

Cheng Du, Yi Jiang  Department of Communication Science and Engineering
Fudan University
Shanghai, China
Email<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Sequences with low aperiodic autocorrelation sidelobes have been extensively
researched in literatures. With sufficiently low integrated sidelobe level
(ISL), their power spectrums are asymptotically flat over the whole frequency
domain. However, for the beam sweeping in the massive multi-input multi-output
(MIMO) broadcast channels, the flat spectrum should be constrained in a
passband with tunable bandwidth to achieve the flexible tradeoffs between the
beamforming gain and the beam sweeping time. Motivated by this application, we
construct a family of sequences termed the generalized step-chirp (GSC)
sequence with a closed-form expression, where some parameters can be tuned to
adjust the bandwidth flexibly. In addition to the application in beam
sweeping, some GSC sequences are closely connected with Mow’s unified
construction of sequences with perfect periodic autocorrelations, and may have
a coarser phase resolution than the Mow sequence while their ISLs are
comparable.

##  I Introduction

Sequences with low aperiodic autocorrelation sidelobes are desirable in
communications and radar engineering, e.g., some of the chirp-like sequences
developed in [1, 2, 3, 4, 5]. With a low integrated sidelobe level (ISL),
these sequences have quite flat spectrums [6], which can be utilized to
achieve omnidirectional precoding in broadcast channels [7].

In 5G NR broadcast channels, the discrete Fourier transform (DFT) codebook is
adopted for broadcasting common messages [8, Section 6.1.6.3] in the initial
stage of communication. With the energy concentrated in the pointing
direction, the maximum beamforming gain can be achieve by the DFT codebook.
But for future wireless communication systems with massive number of antennas,
the resultant beam would be too narrow, thus requiring many times of beam
sweeping to cover the whole angular domain. In contrast, the chirp-like
sequence-based omnidirectional beamforming spreads the energy in the whole
angular domain, and thus avoids beam sweeping and improves the time
efficiency. The omnidirectional beamforming, however, has no beamforming gain,
and therefore may have insufficient range coverage for the millimeter-wave or
terahertz-wave communication systems where a high beamforming gain is required
for compensating the severe path loss.

To circumvent such a dilemma, it is desirable to achieve flexible tradeoffs
between the beamforming gain and the beam sweeping time, as pursued by the
3GPP [9]. From the aspect of spectrum, we aim at designing sequences whose
power variation in the passband and power leakage in the stopband should be as
small as possible, and the bandwidth of the passband should be flexibly
tunable. Besides, their entries should have equal amplitudes for maximizing
the energy efficiency of power amplifiers (PAs), and their phase resolutions
should be coarse for the implementation using a low-cost phase shifter network
(PSN).

Literatures on this topic include some numerical optimizations [10, 11, 12]
and some schemes with closed-form solutions [9, 13, 14, 15, 16]. Compared with
the numerical optimizations, the schemes with closed-form solutions are easier
for hardware implementation, but the bandwidth is less flexible except for the
scheme in [15]. The sequence inferred from [15], referred to as the
generalized chirp (GC) sequence in this paper, has flexible bandwidth the same
as the numerical counterparts, and its spectrum in the passband is
asymptotically flat [15]. Nevertheless, for the GC sequence, the phase
resolution of the PSN is too fine to be cost-effective when the number of
antennas is large, as shown in our simulations.

In recent years, polyphase sequences with low correlations and spectrally-null
constraints were constructed in [17, 18, 19, 20], whose $N$-point spectrums
(with $N$ being the sequence length) are ideally flat in the passbands and are
ideally null in the stopbands. Nevertheless, the $N$-point spectrum is
insufficient for beamforming because the user equipments (UEs) are distributed
in a continuous angular range, rather than the $N$ discrete directions.
Besides, the passbands are interleaved with the stopbands [20] and the
bandwidths are less flexible. Hence, they are still not suitable for beam
sweeping.

To achieve flexible tradeoffs between the beamforming gain and the beam
sweeping time, in this paper we construct a family of polyphase sequences with
flexible bandwidth, termed as the generalized step-chirp (GSC) sequence. The
GSC sequence enjoys a coarser phase resolution than the GC sequence. Besides,
when the passband stretches over the whole frequency domain, the GSC sequence
degenerates into a low-ISL sequence closely connected with the Mow sequence
[5] with perfect periodic autocorrelation, and may require a coarser phase
resolution than the Mow sequence.

Notations: $\lfloor\cdot\rfloor$ stands for taking the floor value.
${\mathbb{Z}}^{+}$ represents the set of positive integers,
${\mathbb{Z}}_{n}=\\{0,1,\cdots,n-1\\}$. $\omega_{N}=e^{j\frac{2\pi}{N}}$.
$\lVert\cdot\rVert$ is the Frobenius norm. For $x,y,s,t\in{\mathbb{R}}$,
$x\equiv y\mod s$ stands for that $x-y$ is an integer multiple of $s$;
$x=y\mod[s,t)$ means that $x-y$ is an integer multiple of $\left\lvert
s-t\right\rvert$ and $y\in[s,t)$; $x=y\mod s$ is equivalent to $x=y\mod[0,s)$.

##  II Preliminaries

In this section, we review two kinds of passive beamformings for the common
message broadcasting: the conventional beam sweeping based on the DFT codebook
[8, Section 6.1.6.3] in Section II-A and the omnidirectional beamforming based
on the chirp-like sequence [5] in Section II-B.

###  II-A DFT Codebook-based Beam Sweeping

Consider a uniform linear array (ULA) of $N$ isotropic antennas with half
wavelength spacing. Given a beamforming vector ${\bf
a}=[a_{0},a_{1},\cdots,a_{N-1}]$ with $\left\lvert
a_{n}\right\rvert=\frac{1}{\sqrt{N}},n\in{\mathbb{Z}}_{N}$, the radiated power
at azimuth angle $\theta$ and elevation angle $\varphi$ is

$y(u)=\left\lvert\sum_{n=0}^{N-1}a_{n}e^{-j\pi nu}\right\rvert^{2}$ (1)

where $u=\cos\varphi\cos\theta$. Note that $-1\leq u\leq 1$, hence $y(u)$ is
essentially the power spectrum of the sequence ${\bf a}$.

A DFT codeword is ${\bf d}(u_{0})=[d_{0},d_{1},\cdots,d_{N-1}]$ with
$d_{n}=\frac{1}{\sqrt{N}}e^{j\pi nu_{0}},n\in{\mathbb{Z}}_{N}$, where $u_{0}$
is the beam direction in the $u$-domain. Let $\Delta u\triangleq u-u_{0}$,
then the radiated power is

$y(u)=\frac{1}{N}\left\lvert\sum_{n=0}^{N-1}e^{-j\pi n\Delta
u}\right\rvert^{2}=\begin{cases}\left\lvert\frac{\sin\left(\frac{\pi
N}{2}\Delta u\right)}{\sqrt{N}\sin\left(\frac{\pi}{2}\Delta
u\right)}\right\rvert^{2},&\Delta u\neq 0\\\ N,&\Delta u=0\end{cases}.$ (2)

By (2), the maximum beamforming gain (the ratio of the maximum received power
to the average received power) $N$ can be achieved if $u=u_{0}$, and for a
sufficiently large $N$,

$\lim_{N\to\infty}\frac{y\left(u_{0}\pm\frac{1}{N}\right)}{y(u_{0})}=\left\lvert\lim_{N\to\infty}\frac{1}{N\sin\left(\frac{\pi}{2N}\right)}\right\rvert^{2}=\frac{4}{\pi^{2}}\approx
0.4,$ (3)

i.e., $u_{0}\pm\frac{1}{N}$ is closed to the half-power points of the beam.
Hence the DFT codeword ${\bf d}(u_{0})$is designed to cover
$[u_{0}-\frac{1}{N},u_{0}+\frac{1}{N}]$. Then a DFT codebook $\\{{\bf
d}(u_{0})\ |\ u_{0}\in\mathcal{T}\\}$ with
$\mathcal{T}=\\{\frac{2i+1}{N}-1|i\in{\mathbb{Z}}_{N}\\}$ is adopted to sweep
the beam over the whole space for broadcasting common message, as illustrated
by Fig. 1 (a). The beam sweeping would consume too many time slots if $N$ is
large.

###  II-B Chirp-like Sequence-based Omnidirectional Beamforming

In contrast to the beam sweeping that requires many time slots, the
omnidirectional beamforming aims at broadcasting messages using only one time
slot, which can be achieved by designing a sequence with a flat power
spectrum.

###### Definition 1

For a length-$N$ complex sequence ${\bf a}$ with $\lVert{\bf a}\rVert=1$, its
aperiodic autocorrelation is defined as

$R_{a}(\tau)\triangleq\sum_{n=0}^{N-1}a_{n}\overline{a}_{n-\tau},\quad
1-N\leq\tau\leq N-1,$ (4)

where $a_{n}=0$ if $n<0$ or $n\geq N$, and the overbar represents the complex
conjugation.

The power spectrum of ${\bf a}$ is

$y(u)=\sum_{\tau=1-N}^{N-1}R_{a}(\tau)e^{-j\pi u\tau},$ (5)

and the variance of the power spectrum is

$\displaystyle\frac{1}{2}\int_{-1}^{1}\left(y(u)-1\right)^{2}\,du$ (6)
$\displaystyle=$ $\displaystyle\frac{1}{2}\sum_{\tau_{1}\neq
0}\sum_{\tau_{2}\neq 0}R_{a}(\tau_{1})R_{a}^{*}(\tau_{2})\int_{-1}^{1}e^{-j\pi
u(\tau_{1}-\tau_{2})}\,du$ $\displaystyle=$ $\displaystyle\sum_{\tau\neq
0}\left\lvert R_{a}(\tau)\right\rvert^{2}\triangleq ISL_{a}$

where $ISL_{a}$ is the integrated sidelobe level (ISL) of $R_{a}(\tau)$. Hence
for omnidirectional beamforming, the sequence ’s ISL should be small, e.g.,
some of the chirp-like sequences [1, 2, 3, 4, 5]. As a unified construction of
sequences with perfect periodic autocorrelation, the Mow sequence family [5]
where some sequences have low ISL, is given below for ease of reference.

###### Definition 2

[5] The Mow sequence is a kind of sequences of length $N=sm^{2}$ with $s$
being the square-free part of $N$, whose entries are
$\frac{1}{\sqrt{N}}\omega_{N}^{m\xi_{n}},n\in{\mathbb{Z}}_{N}$ with

$\xi_{km+l}=mc(s)\alpha(l)k^{2}+\beta(l)k+f_{l}(0),\
l\in{\mathbb{Z}}_{m},k\in{\mathbb{Z}}_{sm}$ (7)

where

$c(s)=\begin{cases}\frac{1}{2},&{\rm for}\ s\ {\rm even}\\\ 1,&{\rm for}\ s\
{\rm odd}\end{cases}\ ,$ (8)

$\alpha(l)\in\\{1,2,\cdots,s-1\\}$ is any function with
$\gcd(\alpha(l),s)=1,\forall l\in{\mathbb{Z}}_{m}$, and
$\beta(l)\in{\mathbb{Z}}_{sm}$ is any function such that $\beta(l)\
\text{mod}\ m$ is a permutation of ${\mathbb{Z}}_{m}$, and $f_{l}(0),\forall
l\in{\mathbb{Z}}_{m}$ are any rational numbers.

Figure 1: The power spectrums of two kinds of beamformings. (a): the DFT
codebook-based beam sweeping; (b) the chirp-like sequence-based
omnidirectional beamforming.

The beam sweeping based on the DFT codebook and the omnidirectional
beamforming based on the Mow sequence are compared in Fig. 1. For the DFT
codebook, $N=10$; for the Mow sequence, $N=50$, $s=2$, $m=5$,
$c(s)=\frac{1}{2}$, $\alpha(l)=1$, $\beta(l)=l-25$, $f_{l}(0)=-9.5l$. The DFT
codebook in Fig. 1 (a) achieves the maximum beamforming gain but requires $10$
times of beam sweeping, while the Mow sequence in Fig. 1 (b) can broadcast
messages in one time slot but has no beamforming gain.

##  III Generalized Step-chirp Sequence

To achieve flexible tradeoffs between the beamforming gain and the beam
sweeping time, in Section III-A, we construct a family of polyphase sequences
with tunable bandwidth, termed as the generalized step-chirp (GSC) sequence;
in Section III-B, we discuss the relationships between the GSC sequence, the
DFT codebook, the generalized chirp (GC) sequence inferred from [15] and the
Mow sequence [5].

###  III-A Construction of Generalized Step-chirp Sequence

Consider a step-chirp signal as follows:

$c(t)=e^{j2\pi\int_{0}^{t}f(\tau)d\tau},\quad 0\leq t\leq T,$ (9)

where $f(t)$ is a step approximation of linear frequency modulation (LFM):

$f(t)=a(\lfloor t\rfloor+b),\ 0\leq t\leq T$ (10)

for $\forall a>0,\forall b\in{\mathbb{R}}$. An LFM $f^{\prime}(t)=t$ and its
step approximation $f(t)$ with $a=1,b=\frac{1}{2}$, and $T=10$ are illustrated
by Fig. 2. The bandwidth of the step-chirp signal is $aT$ approximately.
Besides, we require the Nyquist sampling number $aT^{2}\geq 1$.

Figure 2: Step approximation of LFM, $a=1,b=\frac{1}{2}$, and $T=10$.

Now sample $c(t)$ in (9) at rate $m\triangleq aT/\gamma$ with $0<\gamma\leq
1$, where $m$ is assumed to be an integer via setting $a$ properly. We then
obtain $N$ samples

$c\left(t\right)|_{t=\frac{n}{m}}=e^{j\phi_{n}},\quad n\in{\mathbb{Z}}_{N}$
(11)

with

$N=mT=aT^{2}/\gamma=m^{2}\gamma/a.$ (12)

Because $aT^{2}\geq 1$, we have $\gamma=\frac{aT^{2}}{N}\geq\frac{1}{N}$.

Factor $n\in{\mathbb{Z}}_{N}$ into

$n=km+l,\ k\triangleq\left\lfloor n/m\right\rfloor,\ l\in{\mathbb{Z}}_{m}.$
(13)

Direct calculations show that

$\phi_{n}=2\pi\frac{ak\left(k-1+2b\right)}{2}+2\pi\frac{a\left(k+b\right)l}{m}.$
(14)

Note from (12) that $a=\frac{m^{2}\gamma}{N}$; thus,

$\phi_{n}=\frac{2\pi}{N}m\gamma\left(\frac{k(k-1)}{2}m+kl+bn\right).$ (15)

Besides, the Fourier transform of $c(t)$ can be derived to be a weighted
summation of $T$ sinc functions:

$C(f)=\sum_{i=0}^{T-1}e^{j\pi[ai^{2}+2(ab-f)i+ab-f]}{\rm sinc}[f-a(i+b)].$
(16)

At $f_{0}\triangleq a(b-\frac{1}{2})$, the value of the left-most sinc
function ($i=0$) is $\text{sinc}(-\frac{a}{2})$; at $f_{1}\triangleq
a(b-\frac{1}{2}+T)$, the value of the right-most sinc function ($i=T-1$) is
$\text{sinc}(\frac{a}{2})$. Hence the interval
$(-\infty,f_{0})\cup(f_{1},+\infty)$ can be regarded as the stopband since
most of the sinc functions have attenuated to a low level. Because the
bandwidth of the step-chirp signal is $aT$ approximately, the interval
$[f_{0},f_{1}]$ can be regarded as the passband of $C(f)$. Note that the
analog bandwidth $aT$ is scaled to be the digital bandwidth $2\pi\gamma$ by
over-sampling, hence the passband of the sample sequence is
$\left[\omega_{0},\omega_{0}+2\pi\gamma\right]$ where

$\omega_{0}=\frac{2\pi\gamma}{aT}f_{0}=\frac{2\pi}{N}m\gamma\left(b-\frac{1}{2}\right).$
(17)

The above arguments established the following theorem.

###### Theorem 1

The GSC sequence is a family of polyphase sequences with entries
$\frac{1}{\sqrt{N}}\omega_{N}^{m\zeta_{n}},n\in{\mathbb{Z}}_{N}$, where

$\displaystyle\zeta_{n}=$
$\displaystyle\gamma\left(\frac{k(k-1)}{2}m+kl+bn\right),$ (18) $\displaystyle
k=\left\lfloor n/m\right\rfloor,\ l=n-km,$

with parameter set $\\{N,\gamma,m,b\ |\
N\in{\mathbb{Z}}^{+},m|N,\frac{1}{N}\leq\gamma\leq 1,b\in{\mathbb{R}}\\}$. The
passband of the power spectrum of the GSC sequence is

$\left[\omega_{0},\omega_{0}+2\pi\gamma\right]$ (19)

where $\omega_{0}=\frac{2\pi}{N}m\gamma\left(b-\frac{1}{2}\right)$. For beam
sweeping, the beam is pointed at $u_{0}$ to cover
$[u_{0}-\gamma,u_{0}+\gamma)$, where

$u_{0}=\frac{2}{N}m\gamma\left(b-\frac{1}{2}\right)+\gamma\ \text{mod}\
[-1,1).$ (20)

The bandwidth of the GSC sequence can be flexibly adjusted by tuning the
parameter $\gamma$, thus achieving the flexible tradeoffs between the
beamforming gain and the beam sweeping time, as shown in Simulations.

###  III-B Relationships Between the GSC sequence and Other Sequences

The relationships between the GSC sequence, the DFT codebook, the GC sequence
and the Mow sequence family are illustrated by Fig. 3, as explained below.

Figure 3: The relationships between the Mow sequence, the GC sequence, the DFT
codebook and the GSC sequence.

####  III-B1 GSC Sequence and DFT Codebook

In Theorem 1, let $m=N$ and $\gamma=\frac{1}{N}$. Then we have $k=0$ and $n=l$
for $\forall\ n\in{\mathbb{Z}}_{N}$. This degenerated GSC sequence has entries

$\frac{1}{\sqrt{N}}e^{j\frac{2\pi}{N}m\zeta_{n}}=\frac{1}{\sqrt{N}}e^{j\frac{2\pi}{N}bn},\
n\in{\mathbb{Z}}_{N},$ (21)

and the passband is

$\left[\frac{2\pi}{N}\left(b-\frac{1}{2}\right),\
\frac{2\pi}{N}\left(b+\frac{1}{2}\right)\right].$ (22)

According to Section II-A, this is exactly a DFT codeword pointing at
$u_{0}=\frac{2b}{N}\ \text{mod}\ [-1,1)$. Hence the GSC sequence encompasses
the DFT codebook and thus may be backward-compatible with the current
industrial standard.

####  III-B2 GSC Sequence and GC Sequence

When $m=1$, we have from (18) that
$\frac{1}{\sqrt{N}}\omega_{N}^{m\zeta_{n}}=\frac{1}{\sqrt{N}}\omega_{N}^{\gamma\frac{n(n+2b-1)}{2}}$,
which is the GC sequence inferred from over-sampling a chirp signal [15].
Therefore, the GSC sequence is also a generalization of the GC sequence. The
phase resolution of a sequence with phases in $\\{\frac{2\pi
p}{P}|p\in{\mathbb{Z}}_{P}\\}$ is $\frac{2\pi}{P}$. Note that the parameter
$m$ can be tuned for coarser phase resolution, e.g., suppose
$b\in{\mathbb{Z}}$ and $\gamma$ is a rational number of form $\frac{p}{q}$
with $p,q$ coprime, then the phase resolutions are

$R_{gsc}=\frac{2\pi}{Nq/\text{gcd}(Nq,mp)},\
R_{gc}=\frac{2\pi}{Nq/\text{gcd}(Nq,p)},$ (23)

from which we have $R_{gc}\leq R_{gsc}\leq mR_{gc}$, e.g., if $p=1$, then
$R_{gsc}=mR_{gc}$.

####  III-B3 GSC Sequence and Mow Sequence

Set $\gamma=1$ (i.e., the Nyquist sampling), and we obtain another kind of
degenerated GSC sequence with entries
$\frac{1}{\sqrt{N}}\omega_{N}^{m\zeta_{n}},n\in{\mathbb{Z}}_{N}$, where

$\displaystyle\zeta_{n}=$ $\displaystyle\ \frac{k(k-1)}{2}m+kl+bn,$ (24)
$\displaystyle k=\left\lfloor n/m\right\rfloor,\ l=n-km,$

with parameter set
$\\{N,m,b\,|\,N\in{\mathbb{Z}}^{+},m|N,b\in{\mathbb{R}}\\}$, which is related
to the Mow sequence as shown below.

###### Proposition 1

With the following two constraints on the parameter $m$ and $b$ in (24),
respectively, the degenerated GSC sequence in (24) is a special case of the
Mow sequence in (7):

  1. 1.

$m$ is the square part of $N$, i.e., $N=sm^{2}$.

  2. 2.

$2b$ is odd if $s$ is even or $b$ is an integer if $s$ is odd.

###### Proof:

First note that with the first constraint, the sequence length in (24) is
$sm^{2}$, which is the same as the Mow sequence.

Second, if $s$ is even and $2b$ is odd, then (24) is a special case of (7)
with $c(s)=\frac{1}{2}$, $\alpha(l)=1$, $\beta(l)=\frac{2b-1}{2}m+l$,
$f_{l}(0)=bl$ and $\frac{2b-1}{2}$ is an integer such that $\beta(l)\equiv l\
\text{mod}\ m$ is a permutation of ${\mathbb{Z}}_{m}$.

If $s$ is odd and $b$ is an integer, then denote $s=2d-1$ for some
$d\in{\mathbb{Z}}^{+}$. Since $k(k+2b-1)$ is an even number, it holds that

$\displaystyle dk(k+2b-1)$ $\displaystyle=\frac{k(k+2b-1)}{2}(s+1)$ (25)
$\displaystyle\equiv\frac{k(k+2b-1)}{2}\ \text{mod}\ s.$

Rewrite (24) as

$\zeta_{km+l}=\frac{k(k+2b-1)}{2}m+kl+bl.$ (26)

It follows from (26) and (25) that

$\zeta_{km+l}\equiv dk(k+2b-1)m+kl+bl\ \text{mod}\ sm,$ (27)

which is a special case of (7) with $c(s)=1$, $\alpha(l)=d$ [one may verify
that $\gcd(d,2d-1)=1$], $\beta(l)=(2b-1)dm+l$, $f_{l}(0)=bl$. ∎

Indeed, one may relax the constraints in Proposition 1 to improve the phase
resolution of the degenerated GSC sequence in (24). The phase resolution of
the Mow sequence in (7) with $f_{l}(0)$ being an integer is

$R_{mow}=\begin{cases}\frac{\pi}{N/m},&\ s\ {\rm is}\ {\rm even},m\ {\rm is}\
{\rm odd}\\\ \frac{2\pi}{N/m},&\ {\rm otherwise}\end{cases},$ (28)

and the phase resolution of the GSC sequence with
$\gamma=1,b\in{\mathbb{Z}}^{+}$ is $R_{gsc}=\frac{2\pi}{N/m}$. If $m$ is
larger than the square part of $N$, then the phase resolution of the GSC
sequence would be coarser than the Mow sequence as shown in Simulations.

##  IV Simulations

This section presents simulation examples to verify the capability of the GSC
sequence in making flexible tradeoffs between the beamforming gain and the
beam sweeping time, and its advantages over the GC sequence and the Mow
sequence in terms of the phase resolution and the spectrum.

###  IV-A Tradeoffs Between the Beamforming Gain and the Beam Sweeping Time

To show the flexibility of the GSC sequence for beam sweeping, we simulate and
show in Fig. 4 the beampatterns of the GSC sequences of length $N=120$ with
$(\gamma,m)\in\\{(\frac{1}{2},15),(\frac{1}{5},24),(\frac{1}{7},30),(\frac{1}{13},40)\\}$.
The parameter $b$ is chosen so that the beam direction $u_{0}$ in (20) runs
through $\\{(2i-1)\gamma-1|i=1,2,\cdots,\frac{1}{\gamma}\\}$ for the
contiguous coverage of $[-1,1)$. Fig. 4 (a) illustrates $2$ times of beam
sweeping with 2x beamforming gain while Fig. 4 (d) represents $13$ times of
beam sweeping with 13x beamforming gain. In summary, by adjusting $\gamma$ and
$b$ to control the bandwidth and the beam direction, flexible tradeoffs
between the beamforming gain and the beam sweeping time can be achieved for
efficient beam sweeping. We want to emphasize that the y-axis is in the linear
scale. Thus, the power fluctuation in the passband is less than $3$dB.

Figure 4: Flexible tradeoffs between the beamforming gain and the beam
sweeping time. (a): $\gamma=\frac{1}{2}$; (b): $\gamma=\frac{1}{5}$; (c):
$\gamma=\frac{1}{7}$; (d): $\gamma=\frac{1}{13}$.

###  IV-B Phase Resolution and Spectrum

For a GSC sequence ${\bf g}=[g_{0},g_{1},\cdots,g_{N-1}]$, the normalized root
mean square error (NRMSE) of passband is defined as

$\sqrt{\frac{1}{\left\lvert{\cal
I}_{p}\right\rvert}\sum_{i\in{\mathcal{I}}_{p}}\left(\gamma\left\lvert\sum_{n=0}^{N-1}g_{n}e^{-j\frac{2\pi}{N^{\prime}}in}\right\rvert^{2}-1\right)^{2}}$
(29)

where $N^{\prime}$ is the DFT length and
${\mathcal{I}}_{p}\subset{\mathbb{Z}}_{N^{\prime}}$ is the set of passband
indices. Here we set $N^{\prime}=4N$. And the stopband leakage ratio is
defined as

$\frac{1}{N^{\prime}}\sum_{i\in{\mathcal{I}}_{s}}\left\lvert\sum_{n=0}^{N-1}g_{n}e^{-j\frac{2\pi}{N^{\prime}}in}\right\rvert^{2}$
(30)

where ${\mathcal{I}}_{s}={\mathbb{Z}}_{N^{\prime}}\setminus{\mathcal{I}}_{p}$
is the set of the stopband indices.

Compared with the GC sequence and the Mow sequence, the GSC sequence with a
proper parameter $m$ may have a coarser phase resolution and a comparable
spectrum or even flatter.

####  IV-B1 GSC Sequence versus GC sequence

Fig. 5 shows the impact of the parameter $m$ on the spectrum and the phase
resolution of a GSC sequence, where $N=50$, $\gamma=\frac{1}{2}$, $b=1$.
Compared with the GC sequence, i.e., $m=1$, the GSC sequence with $m=10$ has
smaller passband NRMSE and stopband leakage ratio as shown in Fig. 5 (a), and
the phase resolution of the proposed GSC sequence is $10$ times coarser as
shown in Fig. 5 (b) and Fig. 5 (c).

Figure 5: The improvement of phase resolution and spectrum of the GSC sequence
against the GC sequence. (a): the passband NRMSE and the stopband leakage
ratio of a length-$50$ GSC sequence for different $m$; (b): the phases of the
GC sequence corresponding to $m=1$ in (a); (c): the phases of the GSC sequence
corresponding to $m=10$ in (a).

####  IV-B2 GSC sequence versus Mow sequence

Fig. 6 shows the ISL of a GSC sequence of length $N=462$ for different
parameters $m$, with $\gamma=1$ and $b=\frac{1}{2}$. Note that the square part
of $N=462$ is $m=1$, thus the point with $m=1$ in Fig. 6 corresponds to a Mow
sequence, which can be verified by simulation to have exactly the minimum ISL
among all the $55440$ Mow sequences of length $462$ with a phase resolution
$\frac{\pi}{462}$ [5, Theorem 5]. Remarkably, the ISL for $m=1$ is $0.0297$
and the ISL for $m=21$ is $0.0307$, which means a reduction of phase
resolution by a factor of $21$ but with a negligible increase of ISL, i.e., a
comparably flat spectrum.

Figure 6: The ISL of a length-$462$ GSC sequence for different $m$.

##  V Conclusions

In this paper, we construct the generalized step-chirp (GSC) sequence, which
can achieve flexible tradeoffs between the beamforming gain and the beam
sweeping time for the common message broadcasting in massive MIMO systems. The
GSC sequence has a coarser phase resolution than the generalized chirp (GC)
sequence, which facilitates its implementation with a low-cost phase shifter
network (PSN). Besides, the GSC sequence may have coarser phase resolution
than the Mow sequence with a negligible increase of the integrated sidelobe
level (ISL).

## References

  * [1] R. Frank, “Polyphase codes with good nonperiodic correlation properties,” _IEEE Transactions on Information Theory_ , vol. 9, no. 1, pp. 43–45, 1963.
  * [2] D. Chu, “Polyphase codes with good periodic correlation properties (corresp.),” _IEEE Transactions on information theory_ , vol. 18, no. 4, pp. 531–532, 1972.
  * [3] A. Milewski, “Periodic sequences with optimal properties for channel estimation and fast start-up equalization,” _IBM Journal of Research and Development_ , vol. 27, no. 5, pp. 426–431, 1983.
  * [4] B. M. Popovic, “Generalized chirp-like polyphase sequences with optimum correlation properties,” _IEEE Transactions on Information Theory_ , vol. 38, no. 4, pp. 1406–1409, 1992.
  * [5] W. H. Mow, “A new unified construction of perfect root-of-unity sequences,” in _Proceedings of ISSSTA’95 International Symposium on Spread Spectrum Techniques and Applications_ , vol. 3. IEEE, 1996, pp. 955–959.
  * [6] K.-U. Schmidt, “On a problem due to Littlewood concerning polynomials with unimodular coefficients,” _Journal of Fourier Analysis and Applications_ , vol. 19, no. 3, pp. 457–466, 2013.
  * [7] X. Meng, X. Xia, and X. Gao, “Omnidirectional space-time block coding for common information broadcasting in massive mimo systems,” _IEEE Transactions on Wireless Communications_ , vol. 17, no. 3, pp. 1407–1417, March 2018.
  * [8] 3GPP, “Study on new radio access technology physical layer aspects,” 3GPP, Technical Specification (TS) TS38.802 V14.2.0, Sept. 2017.
  * [9] Intel, “Codebook with beam broadening,” 3GPP, Tech. Rep. R1-1611929, Nov. 2016.
  * [10] W. Rowe, P. Stoica, and J. Li, “Spectrally constrained waveform design [sp tips&tricks],” _IEEE Signal Processing Magazine_ , vol. 31, no. 3, pp. 157–162, 2014.
  * [11] V. Sergeev, A. Davydov, G. Morozov, O. Orhan, and W. Lee, “Enhanced precoding design with adaptive beam width for 5G new radio systems,” in _2017 IEEE 86th Vehicular Technology Conference (VTC-Fall)_. IEEE, 2017, pp. 1–5.
  * [12] W. Ma, L. Zhu, and R. Zhang, “Passive beamforming for 3-D coverage in IRS-assisted communications,” _IEEE Wireless Communications Letters_ , vol. 11, no. 8, pp. 1763–1767, 2022.
  * [13] Z. Xiao, T. He, P. Xia, and X.-G. Xia, “Hierarchical codebook design for beamforming training in millimeter-wave communication,” _IEEE Transactions on Wireless Communications_ , vol. 15, no. 5, pp. 3380–3392, 2016.
  * [14] Z. Xiao, H. Dong, L. Bai, P. Xia, and X.-G. Xia, “Enhanced channel estimation and codebook design for millimeter-wave communication,” _IEEE Transactions on Vehicular Technology_ , vol. 67, no. 10, pp. 9393–9405, 2018.
  * [15] C. Fonteneau, M. Crussière, and B. Jahan, “A systematic beam broadening method for large phased arrays,” in _2021 Joint European Conference on Networks and Communications & 6G Summit (EuCNC/6G Summit)_. IEEE, 2021, pp. 7–12.
  * [16] C. Du, F. Li, and Y. Jiang, “Hierarchical beamforming for broadcast channels,” _IEEE Communications Letters_ , 2023.
  * [17] S. Hu, Z. Liu, Y. L. Guan, W. Xiong, G. Bi, and S. Li, “Sequence design for cognitive cdma communications under arbitrary spectrum hole constraint,” _IEEE Journal on Selected Areas in Communications_ , vol. 32, no. 11, pp. 1974–1986, 2014.
  * [18] Z. Liu, Y. L. Guan, U. Parampalli, and S. Hu, “Spectrally-constrained sequences: Bounds and constructions,” _IEEE Transactions on Information Theory_ , vol. 64, no. 4, pp. 2571–2582, 2018.
  * [19] L. Tian, C. Xu, and Y. Li, “A family of single-channel spectrally-null-constrained sequences with low correlation,” _IEEE Signal Processing Letters_ , vol. 27, pp. 1645–1649, 2020.
  * [20] Z. Ye, Z. Zhou, Z. Liu, X. Tang, and P. Fan, “New spectrally constrained sequence sets with optimal periodic cross-correlation,” _IEEE Transactions on Information Theory_ , vol. 69, no. 1, pp. 610–625, 2022.


# On the Finiteness Problem for classes of modular lattices

Christian Herrmann  Technische Universität Darmstadt FB4
Schloßgartenstr. 7
64289 Darmstadt
Germany<EMAIL_ADDRESS>Dedicated to the memory of Rudolf
Wille

###### Abstract.

The Finiteness Problem is shown to be unsolvable for any sufficiently large
class of modular lattices.

###### Key words and phrases:

Finiteness problem, modular lattice

###### 1991 Mathematics Subject Classification:

06C05, 03D35

Given a class $\mathcal{A}$ of algebraic structures, the _Finiteness Problem_
is to decide for any given finite presentation, that is a list of generator
symbols and relations, whether or not there is a finite bound on the size of
members of the class which ’admit the presentation’, that is a system of
generators satisfying the given relations; if $\mathcal{A}$ is a quasi-
variety, this means finiteness of the free $\mathcal{A}$-algebra given by the
presentation. Due to Slavik [6], the finiteness problem is algorithmically
solvable for the class of all lattices, due to Wille [7] for any class of
modular lattices, containing the subspace lattice of an infinite projective
plane, if one allows only order relations between the generators. The present
note relies on the unsolvability of the Triviality Problem for modular
lattices [4] which in turn relies on the result of Adyan [1, 2] and Rabin [5]
for groups. For a vector space $V$ let $\operatorname{L}(V)$ denote the
lattice of subspaces.

######  Theorem 1.

Let $\mathcal{A}$ a class of modular lattices such that
$\operatorname{L}(V)\in\mathcal{A}$ for some $V$ of infinite dimension. Then
the Finiteness Problem for $\mathcal{A}$ is algorithmically unsolvable.

The following restates the relevant part of Lemma 10 in [4].

######  Lemma 2.

There is a recursive set $\Sigma$ of conjunctions
$\varphi(\bar{x},x_{\bot},x_{\top})$ of lattice equations such that
$\forall\bar{x}\forall x_{\bot}\forall
x_{\top}.\;\varphi(\bar{x},x_{\bot},x_{\top})\Rightarrow\bigwedge_{i}x_{\bot}\leq
x_{i}\leq x_{\top}$ is valid in all modular lattices and such that the
following hold where $\varphi^{\exists}$ denotes the sentence
$\exists\bar{x}\exists x_{\bot}\exists
x_{\top}.\;\varphi(\bar{x},x_{\bot},x_{\top})\wedge x_{\bot}\neq x_{\top}$.

  1. (i)

If, for $\varphi\in\Sigma$, $\varphi^{\exists}$ is valid in some modular
lattice, then it is so within $\operatorname{L}(V)$ for any $V$ of infinite
dimension. Moreover, one can choose $x_{\bot}=0$ and $x_{\top}=V$.

  2. (ii)

The set of all $\varphi\in\Sigma$ with $\varphi^{\exists}$ valid in some
modular lattice is not recursive.

Consider the conjunction $\pi(\bar{y},y_{\bot},y_{\top})$ of the following
lattice equations

$y_{i}\cdot y_{j}=y_{\bot}\;(1\leq i<j\leq 4),\quad
y_{i}+y_{j}=y_{\top}\;(1\leq i<j\leq 4,\,j\neq 2)$

We use $x,y,\ldots$ both as variables and generator symbols and also to denote
their values under a particular assignment. In [3],
$\operatorname{FM}(J_{4}^{1})$ was defined as the modular lattice freely
generated under the presentation $\pi(\bar{y},y_{\bot},y_{\top})$
(equivalently, by the partial lattice $J^{4}_{1}$ arising from the $6$-element
height $2$ lattice $M_{4}$ with atoms $y_{1},y_{2},y_{3},y_{4}$ keeping all
joins and meets except the join of $\\{y_{1},y_{2}\\}$). The following was
shown (to prove (i) consider $V$ the direct sum of infinitely many subspaces
of dimension $\aleph_{0}$).

######  Lemma 3.

Up to isomorphism, $M_{4}$ and singleton are the only proper homomorphic
images of $\operatorname{FM}(J_{4}^{1})$. Moreover,
$\operatorname{FM}(J_{4}^{1})$ has the following properties:

  1. (i)

$\operatorname{FM}(J_{4}^{1})$ embeds into $\operatorname{L}(V)$ for any $V$
of infinite dimension. Moreover, the embedding can be chosen such that any
prime quotient has infinite index.

  2. (ii)

$\operatorname{FM}(J_{4}^{1})$ has infinite height.

  3. (iii)

$\operatorname{FM}(J_{4}^{1})$ has prime quotient $y_{\top}/(y_{1}+y_{2})$,
generating the unique proper congruence relation $\theta$.

  4. (iv)

$\operatorname{FM}(J_{4}^{1})/\theta$ is isomorphic to $M_{4}$.

###### Proof.

of Theorem 1. Given $\varphi\in\Sigma$ from Lemma 2, consider the presentation
$\varphi^{\\#}$ with generators
$\bar{x},x_{\bot},x_{\top},\bar{y},y_{\bot},y_{\top}$ and the relations from
$\varphi$, $\pi$, and in addition $x_{\top}=y_{\top}$ and
$x_{\bot}=y_{1}+y_{2}$. Considering a modular lattice $L$ with generators and
relations according to $\varphi^{\\#}$, the following are equivalent in view
of Lemma 3.

  1. (i)

$x_{\bot}=x_{\top}$.

  2. (ii)

$L$ is singleton or $M_{4}$.

  3. (iii)

$L$ is finite.

  4. (iv)

$L$ is of finite height.

Clearly, if $x_{\bot}=x_{\top}$ in every modular lattice admitting
presentation $\varphi$ then the same applies to the presentation
$\varphi^{\\#}$. On the other hand, assume that $\varphi^{\exists}$ is valid
in some modular lattice. Given any vector space $V$, embed
$\operatorname{FM}(J_{4}^{1})$ into $\operatorname{L}(V)$ as in (i) of Lemma 3
and denote $U=y_{1}+y_{2}$. By (i) of Lemma 2 one can evaluate $\bar{x}$ in
$\operatorname{L}(V/U)$ such that $\varphi(\bar{x},x_{\bot},x_{\top})$ holds
where $x_{\bot}=U$ and $x_{\top}=V$. This results into generators of a
sublattice $L$ of $\operatorname{L}(V)$ satisfying the relations of
$\varphi^{\\#}$ and such that $x_{\bot}\neq x_{\top}$. Thus, to decide whether
$x_{\bot}=x_{\top}$ for all modular lattices admitting presentation $\varphi$
reduces to deciding whether (i)–(iv) apply to all $L\in\mathcal{A}$ admitting
presentation $\varphi^{\\#}$. Undecidability of the latter problems follows
now from (ii) of Lemma 2. ∎

######  Corollary 4.

For no quasi-variety $\mathcal{A}$ as in Theorem 1 there is an algorithm to
decide, given a finite presentation, whether or not the lattice freely
generated in $\mathcal{A}$ under that presentation is of finite height.

## References

  * [1] Adyan, .I.: Algorithmic unsolvability of problems of recognition of certain properties of groups. Dokl. Akad. Nauk SSSR (N.S.) 103, 533–535 (1955) (Russian)
  * [2] Adyan, S.I.: Unsolvability of some algorithmic problems in the theory of groups. Trudy Moskov. Mat. Obsc. 6, 231–298 (1957) (Russian)
  * [3] Day, A., Herrmann, C., Wille, R.: On modular lattices with four generators. Algebra Universalis 2, 317–323 (1972)
  * [4] Herrmann, C., Tsukamoto, Y., Ziegler, M.: On the consistency problem for modular lattices and related structures. Int. J. Algebra Comput. 26, 1573–1595 (2016)
  * [5] Rabin, M.O.: Recursive unsolvability of group theoretic problems. Ann. of Math. 67, 172–194 (1958)
  * [6] Slavik, V.: Finiteness of finitely presented lattices. In: Lattice theory and its applications (Darmstadt, 1991). Res. Exp. Math., vol. 23, pp. 219–227. Heldermann, Lemgo (1995)
  * [7] Wille, R.: Über modulare Verbände, die von einer endlichen halbgeordneten Menge frei erzeugt werden. Math. Z. (1973) 131, 241–249 (German)