# Modeling Sequences as Star Graphs to Address Over-smoothing in Self-
attentive Sequential Recommendation

Bo Peng  The Ohio State UniversityColumbusOHUS<EMAIL_ADDRESS>,
Ziqi Chen  The Ohio State UniversityColumbusOHUS<EMAIL_ADDRESS>,  Srinivasan Parthasarathy  The Ohio State UniversityColumbusOHUS
<EMAIL_ADDRESS>and  Xia Ning  The Ohio State UniversityColumbusOHUS
<EMAIL_ADDRESS>
(2024; 20 February 2007; 12 March 2009; 5 June 2009)

###### Abstract.

Self-attention (SA) mechanisms have been widely used in developing sequential
recommendation (SR) methods, and demonstrated state-of-the-art performance.
However, in this paper, we show that self-attentive SR methods substantially
suffer from the over-smoothing issue that item embeddings within a sequence
become increasingly similar across attention blocks. As widely demonstrated in
the literature, this issue could lead to a loss of information in individual
items, and significantly degrade models’ scalability and performance. To
address the over-smoothing issue, in this paper, we view items within a
sequence constituting a star graph and develop a method, denoted as
$\mathop{\mathtt{MSSG}}\limits$, for SR. Different from existing self-
attentive methods, $\mathop{\mathtt{MSSG}}\limits$ introduces an additional
internal node to specifically capture the global information within the
sequence, and does not require information propagation among items. This
design fundamentally addresses the over-smoothing issue and enables
$\mathop{\mathtt{MSSG}}\limits$ a linear time complexity with respect to the
sequence length. We compare $\mathop{\mathtt{MSSG}}\limits$ with ten state-of-
the-art baseline methods on six public benchmark datasets. Our experimental
results demonstrate that $\mathop{\mathtt{MSSG}}\limits$ significantly
outperforms the baseline methods, with an improvement of as much as 10.10%.
Our analysis shows the superior scalability of $\mathop{\mathtt{MSSG}}\limits$
over the state-of-the-art self-attentive methods. Our complexity analysis and
run-time performance comparison together show that
$\mathop{\mathtt{MSSG}}\limits$ is both theoretically and practically more
efficient than self-attentive methods. Our analysis of the attention weights
learned in SA-based methods indicates that on sparse recommendation data,
modeling dependencies in all item pairs using the SA mechanism yields limited
information gain, and thus, might not benefit the recommendation performance
111 We will release the source code and processed datasets upon the acceptance
of this paper. .

Sequential Recommendation, Over-smoothing, Self-attention

††copyright: acmcopyright††journalyear: 2024††doi:
XXXXXXX.XXXXXXX††conference: Make sure to enter the correct conference title
from your rights confirmation emai; June 03–05, 2018; Woodstock, NY††price:
15.00††isbn: 978-1-4503-XXXX-X/18/06††ccs: Information systems Recommender
systems

##  1\. Introduction

(a) Sequential Graph

(b) Fully Connected Graph

(c) Star Graph

Figure 1.  Illustration of a sequence represented by different graphs, in
which $v_{s_{t}}$ is the $t$-th item in the sequence and $c$ is the internal
node in the star graph.

SR aims to identify and recommend the next item of users’ interest based on
their historical interactions. It has been widely employed in applications
such as online retail (He and McAuley, 2016) and video streaming (Belletti et
al., 2019), and has been drawing increasing attention from the research
community. With the prosperity of deep learning, deep neural networks,
especially recurrent neural networks (RNNs) (Hidasi and Karatzoglou, 2018)
have emerged as the prominent architecture of SR methods. From a graph
perspective, RNNs represent each interaction sequence using a sequential graph
as shown in Figure 1(a), and recurrently integrate information from items
within the sequence. This design, however, may not effectively capture the
long-range dependencies within sequences as it is challenging to propagate
information across long distances (Vaswani et al., 2017).

To better capture the long-range dependencies, SA mechanisms (Vaswani et al.,
2017) have recently been utilized for SR (Kang and McAuley, 2018; Zhou et al.,
2022), and demonstrated state-of-the-art performance (Kang and McAuley, 2018).
Given a sequence, SA mechanisms learn attention weights for all pairs of items
within sequences, and aggregates items using these attention weights. From a
graph perspective, this is essentially equivalent to viewing items within a
sequence as nodes in a fully connected graph 222For simplicity, we drop the
self-loops in the graph. (Dwivedi and Bresson, 2020) as illustrated in Figure
1(b), where $v_{s_{t}}$ is the $t$-th item in the sequence, and the edge
weights are determined by the attention weights. The fully connected graph
allows each item node to propagate information to all others in a single step,
thereby enabling SA-based methods to effectively capture long-range
dependencies within a sequence.

Though promising, modeling sequences as fully connected graphs leads to two
main issues. First, as will be demonstrated in our analysis (Section 6.3), SA-
based SR methods substantially suffer from the over-smoothing issue (Chen et
al., 2020) that the embeddings of items within a sequence could become more
and more similar across attention blocks. Learning similar embeddings for all
items within a sequence leads to the loss of information on individual items,
and thus, could substantially degrade the model performance (Chen et al.,
2020; Shi et al., 2022; Huang et al., 2020; Xu et al., 2018). In addition, as
shown in Shi et al. (Shi et al., 2022), the over-smoothing issue also
deteriorates the learning of deep models, thereby degrading the model
scalability. Second, SA-based SR methods generally suffer from quadratic time
complexities, which limit their utilities in large-scale recommendation
applications.

Addressing the above issues while still effectively capturing the long-range
dependencies within sequences represents a critical research challenge in
developing SR methods. To tackle this challenge, in this paper, we develop
$\mathop{\mathtt{MSSG}}\limits$, a method that models user interaction
sequences using star graphs for SR. Specifically,
$\mathop{\mathtt{MSSG}}\limits$ stacks multiple blocks to recursively capture
users’ intent from their interaction sequence (Kang and McAuley, 2018).
$\mathop{\mathtt{MSSG}}\limits$ has an attention layer and a feed-forward
layer in each block. In the attention layer, as illustrated in Figure 1(c),
$\mathop{\mathtt{MSSG}}\limits$ models each sequence as a star graph, where
edge weights are determined by the attention weights, and introduces an
additional internal node $c$ to integrate information from all item nodes
$v_{s_{t}}$, thereby capturing the user’s intent. In the feed-forward layer,
$\mathop{\mathtt{MSSG}}\limits$ updates the embedding of the internal node via
non-linear networks to more accurately estimate the user’s intent. Previous
work (Chen et al., 2020) shows that requiring information propagation among
all item nodes could be the essential reason for the over-smoothing issue.
Thus, $\mathop{\mathtt{MSSG}}\limits$ does not propagate information among
items. Instead, it utilizes an internal node for information aggregation. This
design allows $\mathop{\mathtt{MSSG}}\limits$ to fundamentally address the
over-smoothing issue (Section 6.3). Beyond addressing the over-smoothing
issue, by modeling sequences as star graphs, $\mathop{\mathtt{MSSG}}\limits$
also achieves a linear time complexity with respect to the sequence length as
will be proven in Section 4.5. In addition, similarly to that in SA
mechanisms, $\mathop{\mathtt{MSSG}}\limits$ could effectively capture long-
range dependencies within sequences as each item node could propagate
information to the internal node within one step.

We extensively compare $\mathop{\mathtt{MSSG}}\limits$ with ten state-of-the-
art baseline methods on six benchmark datasets. Our experimental results
demonstrate that $\mathop{\mathtt{MSSG}}\limits$ could remarkably outperform
the state-of-the-art baseline methods on the six datasets, with an improvement
of up to 10.10% at Recall@$10$ (Section 5.3.2). Our experimental results also
show that $\mathop{\mathtt{MSSG}}\limits$ consistently outperforms the state-
of-the-art SA-based SR method on users with different activity levels (Section
6.2). In addition, our analysis reveals that existing SA-based SR methods
suffer from the over-smoothing issue (Section 6.3), which limits their
scalability in learning deep models (Section 6.4). Our complexity analysis
(Section 4.5) and run-time performance comparison (Section 6.5) together show
that $\mathop{\mathtt{MSSG}}\limits$ is both theoretically and practically
more efficient than the state-of-the-art SA-based SR methods. Our analysis
also suggests that on sparse recommendation data, leveraging SA mechanisms to
capture item dependencies could yield limited information gain.

We summarize our major contributions as follows: 1) To the best of our
knowledge, this is the first work demonstrating the over-smoothing issue in
SA-based SR methods; 2) We develop $\mathop{\mathtt{MSSG}}\limits$ for SR in
which we model sequences using star graphs to address the over-smoothing issue
and enable linear time complexity; 3) $\mathop{\mathtt{MSSG}}\limits$
outperforms ten state-of-the-art baseline methods on six benchmark datasets;
4) Our analysis suggests that $\mathop{\mathtt{MSSG}}\limits$ could achieve
both superior scalability and superior run-time performance compared to SA-
based SR methods; 5) Our analysis also indicates that modeling item
dependencies using the SA mechanism on sparse recommendation data could yield
limited information gain, and thus, might not improve the recommendation
performance.

##  2\. Related Work

###  2.1. Sequential Recommendation

Numerous SR methods have been developed, particularly using Markov Chains
(MCs) and neural networks. Specifically, Rendle et al. (Rendle et al., 2010)
developed $\mathop{\mathtt{FPMC}}\limits$, a method in which MCs are utilized
to model the transitions among items. In recent years, neural networks such as
RNNs and convolutional neural networks (CNNs) have been widely adapted for SR.
For instance, Li et al. (Li et al., 2017) developed
$\mathop{\mathtt{NARM}}\limits$, which incorporates attention mechanisms into
RNNs to better capture users’ long-term preferences. Tang et al. (Tang and
Wang, 2018) developed a CNNs-based model $\mathop{\mathtt{Caser}}\limits$ that
employs vertical and horizontal convolutional filters to capture the synergies
among items for better recommendation. Besides RNNs and CNNs-based methods,
SA-based methods are also widely developed for SR. Kang et al. (Kang and
McAuley, 2018) developed a SA-based method $\mathop{\mathtt{SASRec}}\limits$,
which stacks multiple SA blocks to recursively learn users’ preferences. Sun
et al. (Sun et al., 2019) integrated the cloze objective and SA mechanisms,
and developed a bidirectional sequence modeling method, denoted as
$\mathop{\mathtt{Bert4Rec}}\limits$, for comprehensive user intent modeling.
Zhou et al. (Zhou et al., 2022) developed $\mathop{\mathtt{FMLP}}\limits$ for
SR, in which they replaced the attention map within each SA block with a
predefined transformation matrix for more efficient item aggregation. He et
al. (He et al., 2021) constrained SA blocks to attend to local items, thereby
enhancing the modeling of users’ short-term preferences. Recently, simple
shallow methods have been introduced for SR, and shown promising performance.
For example, Ma et al. (Ma et al., 2019) developed
$\mathop{\mathtt{HGN}}\limits$, which uses a single gating layer to adaptively
aggregate items and capture users’ preferences. Peng et al. (Peng et al.,
2021) developed $\mathop{\mathtt{HAM}}\limits$ in which a single pooling layer
is employed to learn the associations among items.

We notice that $\mathop{\mathtt{SGNN\text{-}HN}}\limits$ developed in Pan et
al. (Pan et al., 2020) also leverages star graphs for SR. However,
$\mathop{\mathtt{MSSG}}\limits$ differs significantly from
$\mathop{\mathtt{SGNN\text{-}HN}}\limits$. Specifically,
$\mathop{\mathtt{MSSG}}\limits$ is developed to address the over-smoothing
issue in SA-based SR methods. To this end, $\mathop{\mathtt{MSSG}}\limits$
utilizes the internal node to aggregate information from individual items, and
does not allow information propagation among items. In contrast,
$\mathop{\mathtt{SGNN\text{-}HN}}\limits$ aims to improve graph neural
networks (GNNs) in capturing long-range dependencies in sequences, and
leverages the internal node as an anchor node to better propagate information
among items. $\mathop{\mathtt{MSSG}}\limits$ and
$\mathop{\mathtt{SGNN\text{-}HN}}\limits$ are developed to address different
issues, and have substantially different architectures. Thus,
$\mathop{\mathtt{MSSG}}\limits$ is not an extension of
$\mathop{\mathtt{SGNN\text{-}HN}}\limits$.

###  2.2. Over-smoothing

The over-smoothing issue was firstly identified in GNNs (Hamilton et al.,
2017) by Li et al. (Li et al., 2018). They observed that as GNNs propagate and
mix information between neighboring nodes across layers, all nodes could
eventually have identical embeddings. As a result, GNNs lose the information
on individual nodes, which could substantially deteriorate the model
expressiveness (Chen et al., 2020). Recently, Shi et al. (Shi et al., 2022)
has proven that theoretically, SA-based methods could also suffer from over-
smoothing and result in sub-optimal performance. Numerous approaches have been
introduced to mitigate this issue. For example, Chen et al. (Chen et al.,
2020) optimized the graph topology based on the model prediction to mitigate
over-smoothing in GNNs. Shi et al. (Shi et al., 2022) developed hierarchical
fusion strategies ($\mathop{\mathtt{ConcatFusion}}\limits$ and
$\mathop{\mathtt{MaxFusion}}\limits$) to alleviate over-smoothing by fusing
embeddings from both shallow layers and deep layers as final output.

##  3\. Definition and notations

In this paper, we tackle the SR problem that given the historical interactions
of users, we recommend the next item of users’ interest. In this paper,
$\mathbb{U}=\\{u_{1},u_{2},\dots\\}$ is the set of all the users, where
$u_{i}$ represents the $i$-th user, and $|\mathbb{U}|$ is the total number of
users. Similarly, we represent the set of all the items as
$\mathbb{V}=\\{v_{1},v_{2},\dots\\}$. $|\mathbb{V}|$ is the total number of
items. The historical interactions of $u_{i}$ is represented as a sequence
$S_{i}=\\{v_{s_{1}}(i),v_{s_{2}}(i),\dots\\}$, where $v_{s_{t}}(i)$ is the
$t$-th interacted item in $S_{i}$ and $|S_{i}|$ is the length of the sequence.
Given $S_{i}$, the next item that $u_{i}$ will interact with is referred to as
the ground-truth next item, denoted as $v_{g}(i)$. The goal of
$\mathop{\mathtt{MSSG}}\limits$ is to correctly recommend $v_{g}(i)$ for
$u_{i}$. When no ambiguity arises, we will eliminate $i$ in $S_{i}$,
$v_{s_{t}}(i)$ and $v_{g}(i)$. We use uppercase letters to denote matrices,
lower-case bold letters to denote row vectors and lower-case non-bold letters
to represent scalars. Table A1 (Appendix A) shows the key notations used in
this paper.

Over-smoothing in SA-based methods: the embeddings of items within a sequence
become increasingly similar across attention blocks, thereby deteriorating the
model scalability and performance.

##  4\. Method

Figure 2.  The overall architecture of $\mathop{\mathtt{MSSG}}\limits$.
$\mathop{\mathtt{MSSG}}\limits$ models sequences using star graphs and
utilizes the internal node $c$ to integrate information from all item nodes.

Figure 2 presents the overall architecture of $\mathop{\mathtt{MSSG}}\limits$.
$\mathop{\mathtt{MSSG}}\limits$ treats sequences as star graphs to address the
over-smoothing issue. $\mathop{\mathtt{MSSG}}\limits$ also explicitly captures
users’ long-term preferences to enable comprehensive user intent modeling. We
present the detail of $\mathop{\mathtt{MSSG}}\limits$ in the following
sections.

###  4.1. Sequence Representation

Following $\mathop{\mathtt{SASRec}}\limits$, we focus on the most recent $n$
items in users’ interaction histories to generate recommendations.
Specifically, we transform each interaction sequence $S$ to a fixed-length
sequence $B$ = $\\{v_{b_{1}},v_{b_{2}}\dots\\}$, which contains the last $n$
items in $S$ (i.e., $v_{b_{t}}$=$v_{s_{|S_{i}|-n+t}}$). If $|S|$ is shorter
than $n$, we pad empty items, denoted as $v_{0}$, at the beginning of $B$. In
$\mathop{\mathtt{MSSG}}\limits$, following the literature (Kang and McAuley,
2018; Vaswani et al., 2017), we represent items and positions in each sequence
using learnable embeddings. We learn an item embedding matrix
$V\in\mathbb{R}^{|\mathbb{V}|\times d}$ in which the $j$-th row
$\mathbf{v}_{j}$ is the embedding of item $v_{j}$, and $d$ is the dimension of
embeddings. We use a constant zero vector as the embedding of padding items.
Similarly, we learn a position embedding matrix $P\in\mathbb{R}^{n\times d}$,
and $\mathbf{p}_{t}$ is the embedding of the $t$-th position. Given $V$ and
$P$, we represent the sequence $B$ using a matrix $E$:

(1)
$E=[\mathbf{e}_{1};\mathbf{e}_{2};\cdots;\mathbf{e}_{n}]=[\mathbf{v}_{b_{1}}+\mathbf{p}_{1};\mathbf{v}_{b_{2}}+\mathbf{p}_{2};\cdots;\mathbf{v}_{b_{n}}+\mathbf{p}_{n}],$

where $\mathbf{v}_{b_{t}}$ is the embedding of $v_{b_{t}}$.

###  4.2. Modeling Sequences as Star Graphs

$\mathop{\mathtt{MSSG}}\limits$ employs a multi-block architecture to
recursively model users’ intent. Distinct from existing SA-based SR methods
(Kang and McAuley, 2018; Fan et al., 2022), in each block,
$\mathop{\mathtt{MSSG}}\limits$ treats each item within $B$ as a node in a
star graph, and introduces an additional internal node to estimate the user’s
intent by aggregating information from all item nodes using multi-head
attention (Vaswani et al., 2017). Across blocks,
$\mathop{\mathtt{MSSG}}\limits$ updates only the embedding of the internal
node to enhance the estimation of the user’s intent, while maintaining fixed
embeddings on item nodes to preserve their individual information. In
$\mathop{\mathtt{MSSG}}\limits$, we have $n_{b}$ blocks, and each block
contains an attention layer and a feed-forward layer. In what follows, we
present the attention layer and the feed-forward layer in each block in
detail.

####  4.2.1. Attention layer

$\mathop{\mathtt{MSSG}}\limits$ employs multi-head attention to adaptively
aggregate information from item nodes to the central internal node in each
block as follows:

(2) $\displaystyle\begin{aligned}
\boldsymbol{\alpha}^{m}_{k}&=\text{softmax}\left(\frac{\left(\mathbf{c}^{m-1}Q^{m}_{k}\right)\left(EZ^{m}_{k}\right)^{\top}}{\sqrt{d}}\right),\quad\mathbf{head}^{m}_{k}=\boldsymbol{\alpha}^{m}_{k}(EA^{m}_{k}),\\\
\mathbf{g}^{m}&=[\mathbf{head}^{m}_{1},\mathbf{head}^{m}_{2},\dots,\mathbf{head}^{m}_{n_{h}}]O^{m},\\\
\end{aligned}$

where $\mathbf{c}^{m-1}$ is the embedding of the internal node from the
$(m\text{-}1)$-th block, and $\mathbf{g}^{m}$ is the output of the attention
layer in the $m$-th block. Each attention layer has $n_{h}$ attention heads
and $\mathbf{head}^{m}_{k}$ is the output from the $k$-th attention head.
$\boldsymbol{\alpha}^{m}_{k}$ is the attention weights learned in the $k$-th
attention head. $Q^{m}_{k},Z^{m}_{k}\text{and
}A^{m}_{k}\in\mathbb{R}^{d\times\frac{d}{n_{h}}}$ are learnable parameters in
the $k$-th attention head. $O^{m}\in\mathbb{R}^{d\times d}$ is a learnable
parameter to integrate the attention heads.

Unlike SA-based methods, which require every item to aggregate information
from all others to capture global information within the sequence,
$\mathop{\mathtt{MSSG}}\limits$ introduces an additional internal node to
specifically capture the global information and estimate the user’s intent.
This approach results in a linear time complexity as will be shown in Section
4.5, while could still effectively capture long-range dependencies within the
sequence.

####  4.2.2. Feed-forward layer

After each attention layer, we include a feed-forward layer to endow
$\mathop{\mathtt{MSSG}}\limits$ with non-linearity, and enable more expressive
models (Vaswani et al., 2017). Particularly, given $\mathbf{g}^{m}$, we stack
two fully-connected networks (FCNs) as the feed-forward layer:

(3)
$\mathbf{c}^{m}=(f(\mathbf{g}^{m}W^{m}_{1}+\mathbf{b}^{m}_{1}))W^{m}_{2}+\mathbf{b}^{m}_{2},$

where $f(\cdot)$ is an activation function such as ReLU (Nair and Hinton,
2010) and GELU (Hendrycks and Gimpel, 2016), $W^{m}_{1}$,
$W^{m}_{2}\in\mathbb{R}^{d\times d}$ and $\mathbf{b}^{m}_{1}$,
$\mathbf{b}^{m}_{2}$ are learnable parameters. It is worth noting that
different from SA-based methods, $\mathop{\mathtt{MSSG}}\limits$ updates only
the embedding of the internal node across blocks, while fixing the item node
embeddings. As a result, $\mathop{\mathtt{MSSG}}\limits$ could preserve the
information on individual items and will not be affected by the over-smoothing
issue, even when learning deep models (Section 6.3). Following
$\mathop{\mathtt{SASRec}}\limits$ (Kang and McAuley, 2018), we connect each
layer with its previous layer using residual connections (He et al., 2016) to
mitigate the degradation issue (Roy et al., 2018) during training. Recent
studies (Peng et al., 2021; Liu et al., 2018) show that the most recent
interacted item could be a strong indicator of the next item of users’
interest. Thus, for each sequence, $\mathop{\mathtt{MSSG}}\limits$ employs
$\mathbf{e}_{n}$, the embedding of the last item in $E$ (Equation 1), as the
initial embedding of the internal node in the first block (i.e.,
$\mathbf{c}^{0}$=$\mathbf{e}_{n}$).

###  4.3. Comprehensive User Intent Modeling

As demonstrated in the literature (Peng et al., 2021; Ma et al., 2019), both
users’ short-term preferences and long-term preferences play important roles
in generating accurate recommendations. By considering $\mathbf{e}_{n}$, the
embedding of the most recent interacted item, as the initial embedding of the
internal node, the internal node embedding should be able to effectively
capture the user’s short-term preferences across blocks. However, it may not
also fully capture the user’s long-term preferences as the long-term
preferences of the user could be different from her short-term preferences.
Thus, to enable comprehensive user intent modeling,
$\mathop{\mathtt{MSSG}}\limits$ learns user embeddings to specifically capture
users’ long-term preferences. In particular, $\mathop{\mathtt{MSSG}}\limits$
learns an embedding matrix $U\in\mathbb{R}^{|\mathbb{U}|\times d}$ to
represent the long-term preferences of all the users. The $i$-th row
$\mathbf{u}_{i}$ in $U$ represents the long-term preferences of user $u_{i}$.

###  4.4. Recommendation Scores and Network Training

To generate recommendation scores for user $u_{i}$,
$\mathop{\mathtt{MSSG}}\limits$ integrates the embedding of the internal node
from the last block (i.e., $\mathbf{c}_{i}^{n_{b}}$) and the learned user
embedding $\mathbf{u}_{i}$, as follows:

(4)
$\hat{r}_{ij}=(\mathbf{c}^{n_{b}}_{i}+\mathbf{u}_{i})\mathbf{v}_{j}^{\top},$

where $\hat{r}_{ij}$ is the recommendation score of user $u_{i}$ on item
$v_{j}$, and $n_{b}$ is the total number of blocks in
$\mathop{\mathtt{MSSG}}\limits$. For each user, we recommend items with the
top-$k$ highest recommendation scores. Following
$\mathop{\mathtt{SASRec}}\limits$, we employ the binary cross-entropy loss to
minimize the negative log-likelihood of correctly recommending the ground
truth next item as follows:

(5)
$\min\limits_{\boldsymbol{\Theta}}-\sum\nolimits_{S_{i}\in\mathbb{T},v_{j}\not\in
S_{i}}\left[\log(\sigma(\hat{r}_{ig}))+\log(1-\sigma(\hat{r}_{ij}))\right],$

where $\mathbb{T}$ is the set of all the training sequences;
$\boldsymbol{\Theta}$ is the set of learnable parameters (e.g., $V$ and $P$);
and $\hat{r}_{ig}$ is the recommendation score of user $u_{i}$ on her ground-
truth next item $v_{g}(i)$. For each training sequence, we randomly sample one
negative item $v_{j}$ for optimization. All the learnable parameters are
randomly initialized, and are optimized in an end-to-end manner.

###  4.5. Complexity Analysis

Previous work (Tay et al., 2020; wang2020linformer;
katharopoulos2020transformers) shows that the time complexity of each SA block
is $\mathcal{O}(n^{2}d+nd^{2})$, where $n$ is the length of the transformed
sequence (Equation 1) and $d$ is the dimension of embeddings. The quadratic
time complexity limits the utility of SA-based methods in latency-sensitive
recommendation applications. In contrast, $\mathop{\mathtt{MSSG}}\limits$
models sequences as star graphs and could achieve a time complexity of
$\mathcal{O}(nd^{2})$, which is linear with respect to the sequence length
$n$. This allows $\mathop{\mathtt{MSSG}}\limits$ to be theoretically more
efficient than SA-based methods. Particularly, each SA block requires
$6nd^{2}+2n^{2}d+2nd$ operations to compute, whereas each block in
$\mathop{\mathtt{MSSG}}\limits$ requires only $2nd^{2}+4d^{2}+2nd+2d$
operations. The difference amounts to $4d^{2}(n-1)+2d(n^{2}-1)$, which is
quadratic with respect to both $d$ and $n$. As will be shown in Section 6.5,
the better time complexity could translate into superior run-time performance
of $\mathop{\mathtt{MSSG}}\limits$ over SA-based methods on modern GPUs.

##  5\. Materials

###  5.1. Baseline Methods

We compare $\mathop{\mathtt{MSSG}}\limits$ with ten state-of-the-art baseline
methods. Specifically, we compare $\mathop{\mathtt{MSSG}}\limits$ with the MC-
based method $\mathop{\mathtt{FPMC}}\limits$ (Rendle et al., 2010) and the
CNNs-based method $\mathop{\mathtt{Caser}}\limits$ (Tang and Wang, 2018). We
also compare $\mathop{\mathtt{MSSG}}\limits$ with the RNNs-based method
$\mathop{\mathtt{NARM}}\limits$ (Li et al., 2017) and two shallow methods
$\mathop{\mathtt{HAM}}\limits$ (Peng et al., 2021) and
$\mathop{\mathtt{HGN}}\limits$ (Ma et al., 2019). We compare
$\mathop{\mathtt{MSSG}}\limits$ with three state-of-the-art SA-based methods
$\mathop{\mathtt{SASRec}}\limits$ (Kang and McAuley, 2018),
$\mathop{\mathtt{Bert4Rec}}\limits$ (Sun et al., 2019) and
$\mathop{\mathtt{FMLP}}\limits$ (Zhou et al., 2022). We further compare
$\mathop{\mathtt{MSSG}}\limits$ with $\mathop{\mathtt{SASRec}}\limits$
equipped with two hierarchical fusion strategies: 1)
$\mathop{\mathtt{SASRec}}\limits$ with $\mathop{\mathtt{ConcatFusion}}\limits$
($\mathop{\mathtt{SASRec\text{-}Cat}}\limits$); and 2)
$\mathop{\mathtt{SASRec}}\limits$ with $\mathop{\mathtt{MaxFusion}}\limits$
($\mathop{\mathtt{SASRec\text{-}Max}}\limits$). These two fusion strategies
are developed in Shi et al. (Shi et al., 2022) to alleviate over-smoothing.
Note that, we do not consider baseline methods that the implementation is not
publicly available (e.g., $\mathop{\mathtt{SGNN\text{-}HN}}\limits$) to enable
a fair comparison. $\mathop{\mathtt{HGN}}\limits$ and
$\mathop{\mathtt{SASRec}}\limits$ have been compared with a comprehensive set
of other methods including $\mathop{\mathtt{GRU4REC}}\limits$ (Hidasi and
Karatzoglou, 2018) and $\mathop{\mathtt{NextItRec}}\limits$ (Yuan et al.,
2019), and have outperformed those methods. Therefore, we compare
$\mathop{\mathtt{MSSG}}\limits$ with $\mathop{\mathtt{HGN}}\limits$ and
$\mathop{\mathtt{SASRec}}\limits$ instead of the methods that they outperform.

To ensure a fair comparison, we exhaustively tune the hyper-parameters of all
the baseline methods. Thus, the performance of baseline methods reported in
our experiments is generally better than that reported in the literature (Ma
et al., 2019; Rajput et al., 2023). For example, on the
$\mathop{\texttt{Beauty}}\limits$ dataset (Section 5.2), the Recall@10
(Section 5.3.2) of $\mathop{\mathtt{SASRec}}\limits$ reported in our
experiments is 20.3% higher than that reported in a recent work (Rajput et
al., 2023). We report the implementation detail of
$\mathop{\mathtt{MSSG}}\limits$ and baseline methods, and the search range for
each hyper-parameter in Appendix B.

###  5.2. Datasets

We evaluate $\mathop{\mathtt{MSSG}}\limits$ and baseline methods on six public
benchmark datasets: 1) Amazon-Beauty ($\mathop{\texttt{Beauty}}\limits$) and
Amazon-Toys ($\mathop{\texttt{Toys}}\limits$) are from Amazon reviews (Ni et
al., 2019); 2) Goodreads-Children ($\mathop{\texttt{Children}}\limits$) and
Goodreads-Comics ($\mathop{\texttt{Comics}}\limits$) are from the Goodreads
website (goodreads1; goodreads2); and 3) MovieLens-1M
($\mathop{\texttt{ML-1M}}\limits$) and MovieLens-20M
($\mathop{\texttt{ML-20M}}\limits$) are from the MovieLens website (Harper and
Konstan, 2015), We discuss the dataset pre-processing and statistics in
Appendix C.

###  5.3. Experimental Protocol

####  5.3.1. Training, validation and testing sets

Following $\mathop{\mathtt{SASRec}}\limits$, on all the datasets, given the
historical interactions $S$ of each user, we use the last item (i.e.,
$v_{s_{|S|}}$) in the history for testing, the second last item (i.e.,
$v_{s_{|S|-1}}$) for validation, and all the previous items for training. We
tune hyper-parameters on the validation sets for all the methods using grid
search, and use the best-performing hyper-parameters in terms of Recall@$10$
(Section 5.3.2) for testing.

####  5.3.2. Evaluation metrics

Following the literature (Kang and McAuley, 2018; Peng et al., 2021; Ma et
al., 2019; Tang and Wang, 2018), we use Recall@$k$ and NDCG@$k$ to evaluate
$\mathop{\mathtt{MSSG}}\limits$ and the baseline methods. We refer the
audience of interest to Peng et al. (Peng et al., 2021) for the detailed
definitions of both Recall@$k$ and NDCG@$k$.

##  6\. Experimental Results

###  6.1. Overall Performance

Table 1. Overall Performance

Dataset | Metric | $\mathop{\mathtt{FPMC}}\limits$ | $\mathop{\mathtt{Caser}}\limits$ | $\mathop{\mathtt{NARM}}\limits$ | $\mathop{\mathtt{HGN}}\limits$ | $\mathop{\mathtt{HAM}}\limits$ | $\mathop{\mathtt{SASRec}}\limits$ | $\mathop{\mathtt{SASRec\text{-}Cat}}\limits$ | $\mathop{\mathtt{SASRec\text{-}Max}}\limits$ | $\mathop{\mathtt{Bert4Rec}}\limits$ | $\mathop{\mathtt{FMLP}}\limits$ | $\mathop{\mathtt{MSSG\text{-}u}}\limits$ | $\mathop{\mathtt{MSSG}}\limits$ | imprv (%)
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
$\mathop{\texttt{Beauty}}\limits$ | Recall@10 | 0.0750 | 0.0647 | 0.0554 | 0.0782 | 0.0865 | 0.0728 | 0.0704 | 0.0741 | 0.0549 | 0.0622 | 0.0874 | 0.0923 |  6.71∗
Recall@20 | 0.1086 | 0.0869 | 0.0835 | 0.1121 | 0.1221 | 0.1083 | 0.1024 | 0.1106 | 0.0776 | 0.0952 | 0.1249 | 0.1286 |  5.32∗
NDCG@10 | 0.0430 | 0.0371 | 0.0291 | 0.0434 | 0.0493 | 0.0398 | 0.0390 | 0.0397 | 0.0298 | 0.0330 | 0.0486 | 0.0516 |  4.67∗
NDCG@20 | 0.0514 | 0.0427 | 0.0362 | 0.0520 | 0.0582 | 0.0487 | 0.0470 | 0.0489 | 0.0355 | 0.0413 | 0.0581 | 0.0607 |  4.30∗
$\mathop{\texttt{Toys}}\limits$ | Recall@10 | 0.0869 | 0.0675 | 0.0557 | 0.0926 | 0.1010 | 0.0909 | 0.0843 | 0.0903 | 0.0539 | 0.0787 | 0.1031 | 0.1055 |  4.46∗
Recall@20 | 0.1173 | 0.0895 | 0.0816 | 0.1240 | 0.1303 | 0.1278 | 0.1123 | 0.1240 | 0.0756 | 0.1072 | 0.1392 | 0.1434 |  10.10∗
NDCG@10 | 0.0517 | 0.0396 | 0.0308 | 0.0540 | 0.0620 | 0.0521 | 0.0496 | 0.0515 | 0.0290 | 0.0444 | 0.0604 | 0.0625 |  0.81∗
NDCG@20 | 0.0594 | 0.0452 | 0.0373 | 0.0619 | 0.0694 | 0.0614 | 0.0566 | 0.0600 | 0.0344 | 0.0516 | 0.0696 | 0.0720 |  3.75∗
$\mathop{\texttt{Children}}\limits$ | Recall@10 | 0.1298 | 0.1303 | 0.1126 | 0.1536 | 0.1729 | 0.1752 | 0.1471 | 0.1706 | 0.1435 | 0.1675 | 0.1709 | 0.1924 |  9.82∗
Recall@20 | 0.1843 | 0.1832 | 0.1735 | 0.2118 | 0.2366 | 0.2337 | 0.2064 | 0.2320 | 0.1930 | 0.2249 | 0.2334 | 0.2589 |  9.43∗
NDCG@10 | 0.0763 | 0.0764 | 0.0585 | 0.0917 | 0.1038 | 0.1086 | 0.0861 | 0.1037 | 0.0884 | 0.1040 | 0.1038 | 0.1176 |  8.29∗
NDCG@20 | 0.0900 | 0.0897 | 0.0738 | 0.1063 | 0.1199 | 0.1234 | 0.1010 | 0.1191 | 0.1009 | 0.1184 | 0.1195 | 0.1343 |  8.83∗
$\mathop{\texttt{Comics}}\limits$ | Recall@10 | 0.2517 | 0.2320 | 0.1304 | 0.2857 | 0.3055 | 0.3196 | 0.2975 | 0.3144 | 0.2363 | 0.3163 | 0.3193 | 0.3317 |  3.79∗
Recall@20 | 0.2986 | 0.2791 | 0.1896 | 0.3322 | 0.3513 | 0.3650 | 0.3456 | 0.3649 | 0.2846 | 0.3631 | 0.3680 | 0.3833 |  5.01∗
NDCG@10 | 0.1875 | 0.1642 | 0.0720 | 0.2061 | 0.2319 | 0.2430 | 0.2219 | 0.2327 | 0.1478 | 0.2377 | 0.2435 | 0.2485 |  2.26∗
NDCG@20 | 0.1993 | 0.1760 | 0.0869 | 0.2178 | 0.2435 | 0.2545 | 0.2340 | 0.2454 | 0.1600 | 0.2496 | 0.2558 | 0.2615 |  2.75∗
$\mathop{\texttt{ML-1M}}\limits$ | Recall@10 | 0.1614 | 0.2874 | 0.2349 | 0.2428 | 0.2745 | 0.2623 | 0.2397 | 0.2598 | 0.1611 | 0.2409 | 0.2866 | 0.3000 |  4.38∗
Recall@20 | 0.2298 | 0.3955 | 0.3422 | 0.3439 | 0.3707 | 0.3709 | 0.3455 | 0.3737 | 0.2291 | 0.3571 | 0.3993 | 0.4132 |  4.48∗
NDCG@10 | 0.0841 | 0.1619 | 0.1252 | 0.1374 | 0.1576 | 0.1463 | 0.1296 | 0.1349 | 0.0832 | 0.1261 | 0.1582 | 0.1684 |  4.01∗
NDCG@20 | 0.1013 | 0.1892 | 0.1524 | 0.1629 | 0.1818 | 0.1681 | 0.1561 | 0.1636 | 0.1003 | 0.1553 | 0.1867 | 0.1970 |  4.12∗
$\mathop{\texttt{ML-20M}}\limits$ | Recall@10 | 0.0992 | 0.1739 | OOM | 0.1588 | 0.1673 | 0.1922 | 0.1859 | 0.1915 | 0.1106 | 0.1707 | 0.1957 | 0.1786 |  1.82∗
Recall@20 | 0.1622 | 0.2649 | OOM | 0.2390 | 0.2493 | 0.2919 | 0.2844 | 0.2909 | 0.1866 | 0.2672 | 0.2959 | 0.2753 |  1.37∗
NDCG@10 | 0.0478 | 0.0907 | OOM | 0.0845 | 0.0895 | 0.1004 | 0.0967 | 0.1002 | 0.0515 | 0.0862 | 0.1015 | 0.0924 |  1.10∗
NDCG@20 | 0.0636 | 0.1136 | OOM | 0.1047 | 0.1102 | 0.1255 | 0.1214 | 0.1251 | 0.0706 | 0.1105 | 0.1267 | 0.1167 |  0.96∗

  * •

For each dataset, the best performance in
$\mathop{\mathtt{MSSG\text{-}u}}\limits$ and $\mathop{\mathtt{MSSG}}\limits$
is in bold, and the best performance among the baseline methods is underlined.
The column “imprv” presents the percentage improvement of
$\mathop{\mathtt{MSSG}}\limits$ or $\mathop{\mathtt{MSSG\text{-}u}}\limits$
over the best-performing baseline methods. The ∗ indicates that the
improvement is statistically significant at 95% confidence level.

Table 1 presents the overall performance of $\mathop{\mathtt{MSSG}}\limits$,
its variant $\mathop{\mathtt{MSSG\text{-}u}}\limits$ and the state-of-the-art
baseline methods at Recall@$k$ and NDCG@$k$ on six benchmark datasets. In
$\mathop{\mathtt{MSSG\text{-}u}}\limits$, we remove user embeddings (i.e.,
$\mathbf{u}_{i}$) when calculating recommendation scores (Equation 4). We
introduce $\mathop{\mathtt{MSSG\text{-}u}}\limits$ to evaluate the
effectiveness of the learnable user embeddings in
$\mathop{\mathtt{MSSG}}\limits$. For $\mathop{\mathtt{NARM}}\limits$, on
$\mathop{\texttt{ML-20M}}\limits$, with the implementation provided by the
authors, we get the out-of-memory (OOM) issue on NVIDIA Volta V100 GPUs with
16 GB memory.

As shown in Table 1, overall, $\mathop{\mathtt{MSSG}}\limits$ is the best-
performing method on the six datasets. In terms of Recall@$10$ and
Recall@$20$, $\mathop{\mathtt{MSSG}}\limits$ significantly outperforms all the
baseline methods on five out of the six datasets except
$\mathop{\texttt{ML-20M}}\limits$. We observe a similar trend at both
NDCG@$10$ and NDCG@$20$. We notice that on $\mathop{\texttt{ML-20M}}\limits$,
$\mathop{\mathtt{MSSG}}\limits$ considerably underperforms
$\mathop{\mathtt{SASRec}}\limits$. However, without user embeddings,
$\mathop{\mathtt{MSSG\text{-}u}}\limits$ could still significantly outperform
$\mathop{\mathtt{SASRec}}\limits$ on $\mathop{\texttt{ML-20M}}\limits$. These
results demonstrate the strong performance of $\mathop{\mathtt{MSSG}}\limits$
and its variant $\mathop{\mathtt{MSSG\text{-}u}}\limits$ on different
recommendation scenarios.

####  6.1.1. Comparing $\mathop{\mathtt{MSSG}}\limits$ to
$\mathop{\mathtt{FPMC}}\limits$ and $\mathop{\mathtt{Caser}}\limits$

As presented in Table 1, $\mathop{\mathtt{MSSG}}\limits$ outperforms the MC-
based method $\mathop{\mathtt{FPMC}}\limits$ and CNNs-based method
$\mathop{\mathtt{Caser}}\limits$ by a significant margin on all the six
benchmark datasets. $\mathop{\mathtt{FPMC}}\limits$ views the transitions
among items as an MC and leverages only the most recent interacted items to
predict the next item of users’ interest. Consequently,
$\mathop{\mathtt{FPMC}}\limits$ may not be able to fully utilize the
information in early interacted items, and result in sub-optimal performance.
$\mathop{\mathtt{Caser}}\limits$ employs CNNs to integrate items within
sequences. Though CNNs have been shown effective in capturing local
structures, they may struggle to capture global information within sequences
(Yamashita et al., 2018). In contrast, by modeling sequences as star graphs,
$\mathop{\mathtt{MSSG}}\limits$ could effectively aggregate information from
all items to capture the global information, and thus, enable superior
recommendation performance over $\mathop{\mathtt{FPMC}}\limits$ and
$\mathop{\mathtt{Caser}}\limits$.

####  6.1.2. Comparison between $\mathop{\mathtt{MSSG}}\limits$ and
$\mathop{\mathtt{NARM}}\limits$

Table 1 shows that compared to the RNNs-based method
$\mathop{\mathtt{NARM}}\limits$, $\mathop{\mathtt{MSSG}}\limits$ demonstrates
superior performance on all the six datasets at all the evaluation metrics.
$\mathop{\mathtt{NARM}}\limits$ primarily uses RNNs to recurrently learn
users’ preferences. As demonstrated in the literature (Vaswani et al., 2017),
due to the recurrent nature, RNNs may struggle to model long-range
dependencies within sequences, which could limit their ability to capture
global information. In $\mathop{\mathtt{MSSG}}\limits$, as illustrated in
Figure 1(c), the central internal node could aggregate information from every
item node within one step. Thus, compared to $\mathop{\mathtt{NARM}}\limits$,
$\mathop{\mathtt{MSSG}}\limits$ could better capture long-range dependencies
within sequences, and achieve substantial performance improvement on all the
datasets.

####  6.1.3. Comparison between $\mathop{\mathtt{MSSG}}\limits$ and
$\mathop{\mathtt{HAM}}\limits$

Table 1 also presents that $\mathop{\mathtt{MSSG}}\limits$ significantly
outperforms the best-performing shallow method $\mathop{\mathtt{HAM}}\limits$
on all the six datasets. Compared to $\mathop{\mathtt{HAM}}\limits$,
$\mathop{\mathtt{MSSG}}\limits$ achieves a remarkable average improvement of
7.8% and 6.0% at Recall@$10$ and NDCG@$10$, respectively, across the six
datasets. $\mathop{\mathtt{HAM}}\limits$ employs the simple mean pooling to
aggregate items and estimate users’ intent. Though efficient, this simple
approach may not be sufficiently expressive to accurately estimate users’
intent from their diverse interactions. Different from
$\mathop{\mathtt{HAM}}\limits$, $\mathop{\mathtt{MSSG}}\limits$ stacks
multiple non-linear blocks to enable expressive models, which leads to a more
accurate user intent modeling as compared to $\mathop{\mathtt{HAM}}\limits$.

####  6.1.4. Comparison between $\mathop{\mathtt{MSSG}}\limits$ and
$\mathop{\mathtt{SASRec}}\limits$

Table 1 presents that both $\mathop{\mathtt{MSSG}}\limits$ and
$\mathop{\mathtt{MSSG\text{-}u}}\limits$ substantially outperform the best-
performing SA-based method $\mathop{\mathtt{SASRec}}\limits$. Similarly to
$\mathop{\mathtt{MSSG}}\limits$, $\mathop{\mathtt{SASRec}}\limits$ stacks
multiple SA blocks to recursively capture users’ intent, and has been
demonstrated state-of-the-art performance (Peng et al., 2021; Kang and
McAuley, 2018) in SR. However, as shown in Table 1,
$\mathop{\mathtt{MSSG}}\limits$ consistently outperforms
$\mathop{\mathtt{SASRec}}\limits$ on five out of six datasets (i.e.,
$\mathop{\texttt{Beauty}}\limits$, $\mathop{\texttt{Toys}}\limits$,
$\mathop{\texttt{Children}}\limits$, $\mathop{\texttt{Comics}}\limits$ and
$\mathop{\texttt{ML-1M}}\limits$). Particularly, compared to
$\mathop{\mathtt{SASRec}}\limits$, in terms of Recall@$10$,
$\mathop{\mathtt{MSSG}}\limits$ achieves a significant average improvement of
14.2% over the five datasets. In terms of NDCG@$10$,
$\mathop{\mathtt{MSSG}}\limits$ also outperforms
$\mathop{\mathtt{SASRec}}\limits$ with a significant average improvement of
15.1% over the five datasets. Similarly,
$\mathop{\mathtt{MSSG\text{-}u}}\limits$ also remarkably outperforms
$\mathop{\mathtt{SASRec}}\limits$ across the six datasets with an average
improvement of 7.0% and 7.2% at Recall@$10$ and NDCG@$10$, respectively. From
a graph perspective, $\mathop{\mathtt{SASRec}}\limits$ models sequences as
fully connected graphs, which allow each item to aggregate information from
other items within the sequence. Though promising, this design results in
quadratic time complexities and leads to the over-smoothing issue (Section
6.3). As shown in the literature (Cai and Wang, 2020; Yang et al., 2020), this
issue could substantially limit the model scalability and degrade the
recommendation performance. In contrast, by modeling sequences as star graphs,
$\mathop{\mathtt{MSSG}}\limits$ could fundamentally address the over-smoothing
issue while still being able to capture the long-range dependencies within
sequences. Consequently, as presented in Table 1,
$\mathop{\mathtt{MSSG}}\limits$ could enable significant improvement over
$\mathop{\mathtt{SASRec}}\limits$ on different recommendation scenarios.

####  6.1.5. Comparison between $\mathop{\mathtt{MSSG}}\limits$ and
$\mathop{\mathtt{SASRec\text{-}Max}}\limits$

Table 1 also shows that overall, both $\mathop{\mathtt{MSSG}}\limits$ and
$\mathop{\mathtt{MSSG\text{-}u}}\limits$ achieve superior performance over
$\mathop{\mathtt{SASRec\text{-}Max}}\limits$ on the six datasets. For example,
at Recall@10, $\mathop{\mathtt{MSSG}}\limits$ and
$\mathop{\mathtt{MSSG\text{-}u}}\limits$ achieves an average improvement of
11.4% and 7.7%, respectively, over the six datasets compared to
$\mathop{\mathtt{SASRec\text{-}Max}}\limits$.
$\mathop{\mathtt{SASRec\text{-}Max}}\limits$ mitigates over-smoothing by
fusing embeddings from both shallow layers and deep layers using max pooling.
In contrast, $\mathop{\mathtt{MSSG}}\limits$ fundamentally addresses over-
smoothing by modeling sequences using star graphs, thereby avoiding
information propagation among items. The substantial improvement of
$\mathop{\mathtt{MSSG}}\limits$ over
$\mathop{\mathtt{SASRec\text{-}Max}}\limits$ shows that our approach is more
effective than hierarchical fusion (Shi et al., 2022) in both addressing over-
smoothing, and improving recommendation performance.

####  6.1.6.  Performance Summary across Datasets

Table 2. Performance Improvement of $\mathop{\mathtt{MSSG\text{-}u}}\limits$
and $\mathop{\mathtt{MSSG}}\limits$ (%)

Method | Metric |  $\mathop{\mathtt{Caser}}\limits$ |  $\mathop{\mathtt{HAM}}\limits$ | $\mathop{\mathtt{SASRec}}\limits$
---|---|---|---|---
$\mathop{\mathtt{MSSG\text{-}u}}\limits$ |  Recall@$10$ |  28.2∗ |  4.6∗ |  7.0∗
Recall@$20$ |  28.5∗ |  6.5∗ |  5.7∗
NDCG@$10$ |  29.6∗ |  2.5∗ |  7.2∗
NDCG@$20$ |  29.8∗ |  3.8∗ |  7.0∗
$\mathop{\mathtt{MSSG}}\limits$ |  Recall@$10$ |  32.8∗ |  7.8∗ |  10.6∗
Recall@$20$ |  32.5∗ |  9.3∗ |  8.7∗
NDCG@$10$ |  34.7∗ |  6.0∗ |  11.2∗
NDCG@$20$ |  34.4∗ |  7.0∗ |  10.6∗

  * •

In this table, the column $\mathop{\mathtt{Caser}}\limits$,
$\mathop{\mathtt{HAM}}\limits$ and $\mathop{\mathtt{SASRec}}\limits$
represents the percentage improvement of
$\mathop{\mathtt{MSSG\text{-}u}}\limits$ and $\mathop{\mathtt{MSSG}}\limits$
over the corresponding method. The ∗ indicates that the improvement is
statistically significant at 85% confidence level.

Table 2 shows the average improvement of
$\mathop{\mathtt{MSSG\text{-}u}}\limits$ and $\mathop{\mathtt{MSSG}}\limits$
over the baseline methods $\mathop{\mathtt{Caser}}\limits$,
$\mathop{\mathtt{HAM}}\limits$ and $\mathop{\mathtt{SASRec}}\limits$ across
the six datasets. We focus on these baseline methods since they achieve the
best performance in terms of at least one evaluation metric on the datasets.
As shown in Table 2, both $\mathop{\mathtt{MSSG\text{-}u}}\limits$ and
$\mathop{\mathtt{MSSG}}\limits$ significantly outperform the baseline methods
across the six datasets. For example, $\mathop{\mathtt{MSSG\text{-}u}}\limits$
and $\mathop{\mathtt{MSSG}}\limits$ achieves a significant average improvement
of 7.0% and 10.6%, respectively, over $\mathop{\mathtt{SASRec}}\limits$ at
Recall@$10$ across the six datasets.

###  6.2. Comparison on Users with Different Activity Levels

We also compare the performance of $\mathop{\mathtt{MSSG}}\limits$ and
$\mathop{\mathtt{MSSG\text{-}u}}\limits$ with the best-performing SA-based SR
method $\mathop{\mathtt{SASRec}}\limits$ on users with different activity
levels. Specifically, we quantify users’ activity levels using the number of
interactions in their history, and bin users into different buckets based on
their activity levels. In this analysis, we use ten buckets in total: five
buckets correspond to the top-10%, $\cdots$, top 40-50% most active users; the
other five buckets are for the bottom 40-50%, $\cdots$, bottom-10% most active
users. Figure 3 presents the performance of $\mathop{\mathtt{MSSG}}\limits$,
$\mathop{\mathtt{MSSG\text{-}u}}\limits$ and $\mathop{\mathtt{SASRec}}\limits$
on $\mathop{\texttt{Beauty}}\limits$, $\mathop{\texttt{Toys}}\limits$ and
$\mathop{\texttt{Children}}\limits$. We present the results on
$\mathop{\texttt{Comics}}\limits$, $\mathop{\texttt{ML-1M}}\limits$ and
$\mathop{\texttt{ML-20M}}\limits$ in Appendix D.1 (Figure A1). The results on
$\mathop{\texttt{Comics}}\limits$, $\mathop{\texttt{ML-1M}}\limits$ and
$\mathop{\texttt{ML-20M}}\limits$ have a similar trend with that shown in
Figure 3.

$\mathop{\mathtt{MSSG}}\limits$ $\mathop{\mathtt{MSSG\text{-}u}}\limits$
$\mathop{\mathtt{SASRec}}\limits$

(a) $\mathop{\texttt{Beauty}}\limits$

(b) $\mathop{\texttt{Toys}}\limits$

(c) $\mathop{\texttt{Children}}\limits$

Figure 3. Performance on users of different activity levels

As shown in Figure 3, $\mathop{\mathtt{MSSG}}\limits$ outperforms
$\mathop{\mathtt{SASRec}}\limits$ by a remarkable margin on both active and
less active users across the three datasets. Similarly,
$\mathop{\mathtt{MSSG\text{-}u}}\limits$ substantially outperforms
$\mathop{\mathtt{SASRec}}\limits$ on users of different activity levels on
$\mathop{\texttt{Beauty}}\limits$ and $\mathop{\texttt{Toys}}\limits$, and
achieves highly competitive performance with $\mathop{\mathtt{SASRec}}\limits$
on $\mathop{\texttt{Children}}\limits$. These results signify that by modeling
sequences using star graphs, $\mathop{\mathtt{MSSG}}\limits$ and
$\mathop{\mathtt{MSSG\text{-}u}}\limits$ could more accurately estimate the
intent of users with different activity levels compared to
$\mathop{\mathtt{SASRec}}\limits$. Note that users’ activity level is not the
only factor in determining the difficulty of estimating their intent. As a
result, we do not expect a strictly increasing or decreasing performance curve
as activity levels change.

###  6.3. Analysis on Over-smoothing

We analyze if the state-of-the-art SA-based SR method
$\mathop{\mathtt{SASRec}}\limits$ suffers from the over-smoothing issue.
Specifically, for each dataset, we train a $\mathop{\mathtt{SASRec}}\limits$
model consisting of six SA blocks. Apart from the number of blocks, we use the
best-performing hyper-parameters of $\mathop{\mathtt{SASRec}}\limits$ on each
dataset to train the model. Subsequently, we calculate the average similarity
between the embeddings of items within a sequence for each SA block. We denote
the average similarity calculated from the output of the $m$-th SA block as
$a^{m}$. We discuss the details on the calculation of $a^{m}$ in Appendix D.2.

We use $a^{m}$ to assess whether the $\mathop{\mathtt{SASRec}}\limits$ model
suffers from the over-smoothing issue. In particular, the increase of $a^{m}$
over $m$ implies that generally, the embeddings of items within a user’s
interaction sequence become more and more similar across blocks. This serves
as strong evidence to demonstrate that the $\mathop{\mathtt{SASRec}}\limits$
model suffers from the over-smoothing issue. We also evaluate if
$\mathop{\mathtt{MSSG}}\limits$ suffers from over-smoothing by calculating
$a^{m}$ from the $\mathop{\mathtt{MSSG}}\limits$ model trained using the same
hyper-parameters as in $\mathop{\mathtt{SASRec}}\limits$. We present $a^{m}$
calculated from $\mathop{\mathtt{MSSG}}\limits$ and
$\mathop{\mathtt{SASRec}}\limits$ in Figure 4. Note that, we observe a similar
trend to that in Figure 4 when using a smaller number of blocks. Due to the
space limit, we present results for using six blocks only.

$\mathop{\mathtt{MSSG}}\limits$ $\mathop{\mathtt{SASRec}}\limits$

(a) $\mathop{\texttt{Beauty}}\limits$

(b) $\mathop{\texttt{Toys}}\limits$

(c) $\mathop{\texttt{Children}}\limits$

(d) $\mathop{\texttt{Comics}}\limits$

(e) $\mathop{\texttt{ML-1M}}\limits$

(f) $\mathop{\texttt{ML-20M}}\limits$

Figure 4. The average similarity $a^{m}$ in different blocks of
$\mathop{\mathtt{MSSG}}\limits$ and $\mathop{\mathtt{SASRec}}\limits$

As illustrated in Figure 4, in $\mathop{\mathtt{SASRec}}\limits$, $a^{m}$
increases across blocks on all the six datasets. For example, on
$\mathop{\texttt{Beauty}}\limits$, the average similarity rises from 0.56
(i.e., $a^{1}$) in the first block to 0.78 (i.e., $a^{6}$) in the last block.
These results demonstrate that $\mathop{\mathtt{SASRec}}\limits$ substantially
suffers from the over-smoothing issue. In contrast, as shown in Figure 4,
$a^{m}$ from $\mathop{\mathtt{MSSG}}\limits$ remains constant across blocks,
indicating that $\mathop{\mathtt{MSSG}}\limits$ is not affected by over-
smoothing. The key distinction between $\mathop{\mathtt{MSSG}}\limits$ and
$\mathop{\mathtt{SASRec}}\limits$ lies in their sequence modeling approaches.
While $\mathop{\mathtt{SASRec}}\limits$ utilizes fully connected graphs to
model sequences, $\mathop{\mathtt{MSSG}}\limits$ instead models sequences
using star graphs. As a result, $\mathop{\mathtt{MSSG}}\limits$ does not
require information propagation among item nodes, and allows each item to
maintain its individual information across blocks. Consequently,
$\mathop{\mathtt{MSSG}}\limits$ could fundamentally address the over-smoothing
issue. As shown in the literature (Xu et al., 2018; Shi et al., 2022), the
over-smoothing issue could substantially deteriorate the model scalability,
and thus, degrade the model performance in the task of interest. Therefore, by
addressing this issue, $\mathop{\mathtt{MSSG}}\limits$ could achieve superior
performance over $\mathop{\mathtt{SASRec}}\limits$ on benchmark datasets as
shown in Table 1.

###  6.4. Analysis on Scalability

The huge success of Transformer (Vaswani et al., 2017) highlights the
importance of a method’s scalability in determining its utility for real-world
applications. In this analysis, we evaluate the scalability of
$\mathop{\mathtt{MSSG}}\limits$ and $\mathop{\mathtt{SASRec}}\limits$ with
respect to the number of blocks and the embedding dimensions. Particularly, we
assess the ability of $\mathop{\mathtt{MSSG}}\limits$ and
$\mathop{\mathtt{SASRec}}\limits$ in learning deep (i.e., with a large number
of blocks) and wide (i.e., with a large embedding dimension) models on
benchmark datasets. To enable a fair comparison, in this analysis, we apply
the best-performing hyper-parameters of $\mathop{\mathtt{SASRec}}\limits$ on
each dataset for $\mathop{\mathtt{SASRec}}\limits$ and
$\mathop{\mathtt{MSSG}}\limits$.

Figure 5 presents the performance of $\mathop{\mathtt{SASRec}}\limits$ and
$\mathop{\mathtt{MSSG}}\limits$ at Recall@$10$ over different numbers of
blocks on the six benchmark datasets. We limit the maximum number of blocks
($n_{b}$) to six, as we got the out-of-memory issue with
$\mathop{\mathtt{SASRec}}\limits$ when $n_{b}>6$.

$\mathop{\mathtt{MSSG}}\limits$ $\mathop{\mathtt{SASRec}}\limits$

(a) $\mathop{\texttt{Beauty}}\limits$

(b) $\mathop{\texttt{Toys}}\limits$

(c) $\mathop{\texttt{Children}}\limits$

(d) $\mathop{\texttt{Comics}}\limits$

(e) $\mathop{\texttt{ML-1M}}\limits$

(f) $\mathop{\texttt{ML-20M}}\limits$

Figure 5. Performance over different numbers of blocks

Figure 5 demonstrates that $\mathop{\mathtt{MSSG}}\limits$ outperforms
$\mathop{\mathtt{SASRec}}\limits$ at the scalability with respect to $n_{b}$.
In particular, $\mathop{\mathtt{MSSG}}\limits$ maintains reasonable
performance as $n_{b}$ increases on all datasets, while
$\mathop{\mathtt{SASRec}}\limits$ fails on four out of the six datasets
($\mathop{\texttt{Children}}\limits$, $\mathop{\texttt{Comics}}\limits$,
$\mathop{\texttt{ML-1M}}\limits$, and $\mathop{\texttt{ML-20M}}\limits$) when
$n_{b}$=$6$. As discussed in Section 6.3, the state-of-the-art SA-based SR
method $\mathop{\mathtt{SASRec}}\limits$ substantially suffers from the over-
smoothing issue. Consequently, $\mathop{\mathtt{SASRec}}\limits$ struggles to
learn deep models, as the item embeddings become increasingly similar across
SA blocks (Xu et al., 2018; Zhao and Akoglu, 2019; Shi et al., 2022). In
contrast, as shown in Section 6.3, $\mathop{\mathtt{MSSG}}\limits$ is not
affected by over-smoothing, and thus, could enable superior scalability with
respect to $n_{b}$ compared to $\mathop{\mathtt{SASRec}}\limits$. It is worth
noting that, on $\mathop{\texttt{ML-1M}}\limits$ and
$\mathop{\texttt{ML-20M}}\limits$, the best performing
$\mathop{\mathtt{MSSG\text{-}u}}\limits$ and $\mathop{\mathtt{MSSG}}\limits$
models have at least 4 blocks (Appendix B), which reveals that the better
scalability of $\mathop{\mathtt{MSSG}}\limits$ at $n_{b}$ could translate into
superior recommendation performance on real datasets.

Due to the space limit, we present the scalability comparison between
$\mathop{\mathtt{MSSG}}\limits$ and $\mathop{\mathtt{SASRec}}\limits$ in terms
of embedding dimensions (i.e., $d$) in Appendix D.3. As shown in Appendix D.3
(Figure A2), $\mathop{\mathtt{MSSG}}\limits$ also substantially outperforms
$\mathop{\mathtt{SASRec}}\limits$ at the scalability over $d$. We refer the
audience to Appendix D.3 for a more detailed discussion.

###  6.5. Comparison on Run-time Performance

We conduct an analysis to evaluate the run-time performance of
$\mathop{\mathtt{MSSG}}\limits$ and $\mathop{\mathtt{SASRec}}\limits$ during
testing. To enable a fair comparison, similarly to that in Section 6.4, we
apply the best-performing hyper-parameters on
$\mathop{\mathtt{SASRec}}\limits$ for $\mathop{\mathtt{MSSG}}\limits$ and
$\mathop{\mathtt{SASRec}}\limits$, and compare their run-time performance
during testing when using different numbers of blocks. In addition, we perform
the evaluation for both $\mathop{\mathtt{MSSG}}\limits$ and
$\mathop{\mathtt{SASRec}}\limits$ using NVIDIA Volta V100 GPUs, and report the
average computation time per user over five runs in Figure 6. Moreover, we use
the same evaluation script for both $\mathop{\mathtt{MSSG}}\limits$ and
$\mathop{\mathtt{SASRec}}\limits$ to avoid any run-time performance
differences that might arise from differences in the implementation. We focus
on the run-time performance during testing due to the fact that it could
signify the models’ latency in real-time recommendation, which could
significantly affect the user experience and thus revenue.

$\mathop{\mathtt{MSSG}}\limits$ $\mathop{\mathtt{SASRec}}\limits$

(a) $\mathop{\texttt{Beauty}}\limits$

(b) $\mathop{\texttt{Toys}}\limits$

(c) $\mathop{\texttt{Children}}\limits$

(d) $\mathop{\texttt{Comics}}\limits$

(e) $\mathop{\texttt{ML-1M}}\limits$

(f) $\mathop{\texttt{ML-20M}}\limits$

Figure 6. Run-time performance over the number of blocks

As shown in Figure 6, on all the datasets, $\mathop{\mathtt{MSSG}}\limits$
achieves stronger run-time performance compared to
$\mathop{\mathtt{SASRec}}\limits$ over different numbers of blocks, and the
improvement increases as the number of blocks increases. Particularly, when
using the best-performing $n_{b}$ of $\mathop{\mathtt{SASRec}}\limits$ on each
dataset (e.g., $n_{b}=2$ on $\mathop{\texttt{Beauty}}\limits$ as in Appendix
B), $\mathop{\mathtt{MSSG}}\limits$ achieves an average speedup of 16.6%
compared to $\mathop{\mathtt{SASRec}}\limits$ over the six datasets. Note
that, as shown in Figure 5, with the same hyper-parameters,
$\mathop{\mathtt{MSSG}}\limits$ also outperforms
$\mathop{\mathtt{SASRec}}\limits$ in terms of the recommendation performance
on all the datasets except $\mathop{\texttt{ML-20M}}\limits$. These results
demonstrate that compared to $\mathop{\mathtt{SASRec}}\limits$,
$\mathop{\mathtt{MSSG}}\limits$ could generate more accurate recommendations
in lower latency, thus significantly improving the user experience. Note that
on GPUs, all the computations are performed in parallel. However, when
calculating the time complexity (Section 4.5), we assume the computations are
serial. Therefore, in terms of the run-time performance on GPUs, the
improvement of $\mathop{\mathtt{MSSG}}\limits$ over
$\mathop{\mathtt{SASRec}}\limits$ may not be as significant as that suggested
by the time complexity. However, in many applications, the recommendation
model could be deployed on edge devices with limited computing resources. In
these applications, as suggested by the time complexity comparison (Section
4.5), $\mathop{\mathtt{MSSG}}\limits$ could achieve a more substantial speedup
over $\mathop{\mathtt{SASRec}}\limits$.

###  6.6. Analysis on Attention Weights in $\mathop{\mathtt{SASRec}}\limits$

Figure 7. The average entropy of attention weight distribution in
$\mathop{\mathtt{SASRec}}\limits$ and uniform distribution

We conduct an analysis to investigate the information gain derived from the
attention weights learned in $\mathop{\mathtt{SASRec}}\limits$. Particularly,
we measure the information gain by comparing the average entropy from the
attention weight distributions and that from uniform distributions (i.e.,
weigh items equally). We present more details on the calculation of the
average entropy in Appendix D.4. A higher difference between the average
entropies indicates a larger information gain derived from the learned
attention weights. Figure 7 shows the average entropy from attention weight
distributions and uniform distributions on $\mathop{\texttt{Beauty}}\limits$,
$\mathop{\texttt{Toys}}\limits$ and $\mathop{\texttt{Children}}\limits$.
Following $\mathop{\mathtt{SASRec}}\limits$, we focus on the attention weights
learned in the first SA block in this analysis.

As shown in Figure 7, on all the three datasets, the difference between the
average entropy from attention weight distributions and uniform distributions
is highly marginal, indicating that $\mathop{\mathtt{SASRec}}\limits$ achieves
limited information gain from the learned attention weights. An important
difference between $\mathop{\mathtt{MSSG}}\limits$ and
$\mathop{\mathtt{SASRec}}\limits$ is that $\mathop{\mathtt{SASRec}}\limits$
captures the dependencies in each pair of items by learning attention weights,
while $\mathop{\mathtt{MSSG}}\limits$ does not explicitly model these
dependencies. As shown in Figure 7, on the notoriously sparse recommendation
data (Peng et al., 2021), limited information gain could be achieved by
capturing the dependency in each item pair. As a result, as shown in Table 1
and Table 2, without explicitly modeling dependencies in item pairs,
$\mathop{\mathtt{MSSG}}\limits$ and $\mathop{\mathtt{MSSG\text{-}u}}\limits$
could still achieve significant improvement over
$\mathop{\mathtt{SASRec}}\limits$ on benchmark datasets.

##  7\. Conclusion

In this paper, we identify the over-smoothing issue in SA-based SR methods. To
address this issue, we model sequences using star graphs and develop
$\mathop{\mathtt{MSSG}}\limits$ for SR. Different from SA-based methods in
which each item could aggregate information from all others,
$\mathop{\mathtt{MSSG}}\limits$ introduces an internal node for information
aggregation and does not propagate information among item nodes. Consequently,
$\mathop{\mathtt{MSSG}}\limits$ could fundamentally address the over-smoothing
issue and achieve a linear time complexity with respect to the sequence
length. We extensively evaluate $\mathop{\mathtt{MSSG}}\limits$ against ten
state-of-the-art baseline methods on six benchmark datasets. Our experimental
results show that overall, $\mathop{\mathtt{MSSG}}\limits$ outperforms
baseline methods on all the datasets except for
$\mathop{\texttt{ML-20M}}\limits$, with an improvement of up to 10.10%. On
$\mathop{\texttt{ML-20M}}\limits$, a variant of
$\mathop{\mathtt{MSSG}}\limits$ could still significantly outperform all the
baseline methods. Our analysis shows that $\mathop{\mathtt{MSSG}}\limits$
achieves superior scalability with respect to both the number of blocks and
the embedding dimensions compared to the state-of-the-art SA-based SR method
$\mathop{\mathtt{SASRec}}\limits$. This improved scalability could lead to
enhanced recommendation performance in benchmark datasets. In addition, our
complexity analysis and run-time performance comparison together demonstrate
that $\mathop{\mathtt{MSSG}}\limits$ is both theoretically and practically
more efficient than $\mathop{\mathtt{SASRec}}\limits$. Thus,
$\mathop{\mathtt{MSSG}}\limits$ could be particularly desirable in
applications with limited computing resources. Our analysis also suggests that
$\mathop{\mathtt{SASRec}}\limits$ achieves limited information gain by
explicitly modeling dependencies between items using the SA mechanism.
Therefore, without modeling the dependencies, $\mathop{\mathtt{MSSG}}\limits$
could still outperform $\mathop{\mathtt{SASRec}}\limits$ in benchmark
datasets.

## References

  * (1)
  * Belletti et al. (2019) Francois Belletti, Minmin Chen, and Ed H Chi. 2019.  Quantifying long range dependence in language and user behavior to improve rnns. In _Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_. 1317–1327.
  * Cai and Wang (2020) Chen Cai and Yusu Wang. 2020.  A note on over-smoothing for graph neural networks.  _arXiv_ (2020).
  * Chen et al. (2020) Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, and Xu Sun. 2020.  Measuring and relieving the over-smoothing problem for graph neural networks from the topological view. In _Proceedings of the AAAI conference on artificial intelligence_ , Vol. 34. 3438–3445.
  * Dwivedi and Bresson (2020) Vijay Prakash Dwivedi and Xavier Bresson. 2020.  A generalization of transformer networks to graphs.  _arXiv_ (2020).
  * Fan et al. (2022) Ziwei Fan, Zhiwei Liu, Yu Wang, Alice Wang, Zahra Nazari, Lei Zheng, Hao Peng, and Philip S Yu. 2022\.  Sequential Recommendation via Stochastic Self-Attention.  _arXiv_ (2022).
  * Hamilton et al. (2017) Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017\.  Inductive representation learning on large graphs.  _Advances in neural information processing systems_ 30 (2017).
  * Harper and Konstan (2015) F. Maxwell Harper and Joseph A. Konstan. 2015.  The MovieLens Datasets: History and Context.  _ACM Trans. Interact. Intell. Syst._ 5, 4, Article 19 (dec 2015), 19 pages.  https://doi.org/10.1145/2827872
  * He et al. (2016) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. 2016\.  Deep residual learning for image recognition. In _Proceedings of the IEEE conference on computer vision and pattern recognition_. 770–778.
  * He and McAuley (2016) Ruining He and Julian McAuley. 2016.  Ups and downs: Modeling the visual evolution of fashion trends with one-class collaborative filtering. In _proceedings of the 25th international conference on world wide web_. 507–517.
  * He et al. (2021) Zhankui He, Handong Zhao, Zhe Lin, Zhaowen Wang, Ajinkya Kale, and Julian McAuley. 2021\.  Locker: Locally constrained self-attentive sequential recommendation. In _Proceedings of the 30th ACM International Conference on Information & Knowledge Management_. 3088–3092.
  * Hendrycks and Gimpel (2016) Dan Hendrycks and Kevin Gimpel. 2016.  Gaussian error linear units (gelus).  _arXiv_ (2016).
  * Hidasi and Karatzoglou (2018) Balázs Hidasi and Alexandros Karatzoglou. 2018.  Recurrent neural networks with top-k gains for session-based recommendations. In _Proceedings of the 27th ACM international conference on information and knowledge management_. 843–852.
  * Huang et al. (2020) Wenbing Huang, Yu Rong, Tingyang Xu, Fuchun Sun, and Junzhou Huang. 2020.  Tackling over-smoothing for general graph convolutional networks.  _arXiv_ (2020).
  * Kang and McAuley (2018) Wang-Cheng Kang and Julian McAuley. 2018.  Self-attentive sequential recommendation. In _International Conference on Data Mining_. 197–206.
  * Li et al. (2017) Jing Li, Pengjie Ren, Zhumin Chen, Zhaochun Ren, Tao Lian, and Jun Ma. 2017\.  Neural attentive session-based recommendation. In _Proceedings of the Conference on Information and Knowledge Management_. 1419–1428.
  * Li et al. (2018) Qimai Li, Zhichao Han, and Xiao-Ming Wu. 2018.  Deeper insights into graph convolutional networks for semi-supervised learning. In _Proceedings of the AAAI conference on artificial intelligence_ , Vol. 32.
  * Liu et al. (2018) Qiao Liu, Yifu Zeng, Refuoe Mokhosi, and Haibin Zhang. 2018\.  STAMP: Short-Term Attention/Memory Priority Model for Session-Based Recommendation. In _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_ (London, United Kingdom) _(KDD ’18)_. Association for Computing Machinery, New York, NY, USA, 1831–1839.  https://doi.org/10.1145/3219819.3219950
  * Ma et al. (2019) Chen Ma, Peng Kang, and Xue Liu. 2019.  Hierarchical gating networks for sequential recommendation. In _Proceedings of the ACM SIGKDD international conference on knowledge discovery & data mining_. 825–833.
  * Nair and Hinton (2010) Vinod Nair and Geoffrey E Hinton. 2010.  Rectified linear units improve restricted boltzmann machines. In _Icml_.
  * Ni et al. (2019) Jianmo Ni, Jiacheng Li, and Julian McAuley. 2019.  Justifying Recommendations using Distantly-Labeled Reviews and Fine-Grained Aspects. In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_. Association for Computational Linguistics, Hong Kong, China, 188–197.  https://doi.org/10.18653/v1/D19-1018
  * Pan et al. (2020) Zhiqiang Pan, Fei Cai, Wanyu Chen, Honghui Chen, and Maarten De Rijke. 2020.  Star graph neural networks for session-based recommendation. In _Proceedings of the 29th ACM international conference on information & knowledge management_. 1195–1204.
  * Peng et al. (2021) Bo Peng, Zhiyun Ren, Srinivasan Parthasarathy, and Xia Ning. 2021.  HAM: hybrid associations models for sequential recommendation.  _IEEE Transactions on Knowledge and Data Engineering_ (2021).
  * Rajput et al. (2023) Shashank Rajput, Nikhil Mehta, Anima Singh, Raghunandan H Keshavan, Trung Vu, Lukasz Heldt, Lichan Hong, Yi Tay, Vinh Q Tran, Jonah Samost, et al. 2023\.  Recommender Systems with Generative Retrieval.  _arXiv preprint arXiv:2305.05065_ (2023).
  * Rendle et al. (2012) Steffen Rendle, Christoph Freudenthaler, Zeno Gantner, and Lars Schmidt-Thieme. 2012.  BPR: Bayesian personalized ranking from implicit feedback.  _arXiv_ (2012).
  * Rendle et al. (2010) Steffen Rendle, Christoph Freudenthaler, and Lars Schmidt-Thieme. 2010\.  Factorizing personalized markov chains for next-basket recommendation. In _Proceedings of the international conference on World wide web_. 811–820.
  * Roy et al. (2018) Prasun Roy, Subhankar Ghosh, Saumik Bhattacharya, and Umapada Pal. 2018.  Effects of degradations on deep neural network architectures.  _arXiv_ (2018).
  * Shi et al. (2022) Han Shi, Jiahui Gao, Hang Xu, Xiaodan Liang, Zhenguo Li, Lingpeng Kong, Stephen Lee, and James T Kwok. 2022\.  Revisiting Over-smoothing in BERT from the Perspective of Graph.  _arXiv_ (2022).
  * 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_. 1441–1450.
  * Tang and Wang (2018) Jiaxi Tang and Ke Wang. 2018.  Personalized top-n sequential recommendation via convolutional sequence embedding. In _Proceedings of the international conference on web search and data mining_. 565–573.
  * Tay et al. (2020) Yi Tay, Mostafa Dehghani, Dara Bahri, and Donald Metzler. 2020\.  Efficient transformers: A survey.  _arXiv_ (2020).
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  _Advances in neural information processing systems_ 30 (2017).
  * Xu et al. (2018) Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. 2018.  Representation learning on graphs with jumping knowledge networks. In _International Conference on Machine Learning_. 5453–5462.
  * Yamashita et al. (2018) Rikiya Yamashita, Mizuho Nishio, Richard Kinh Gian Do, and Kaori Togashi. 2018.  Convolutional neural networks: an overview and application in radiology.  _Insights into imaging_ 9 (2018), 611–629.
  * Yang et al. (2020) Chaoqi Yang, Ruijie Wang, Shuochao Yao, Shengzhong Liu, and Tarek Abdelzaher. 2020.  Revisiting over-smoothing in deep GCNs.  _arXiv_ (2020).
  * Yuan et al. (2019) Fajie Yuan, Alexandros Karatzoglou, Ioannis Arapakis, Joemon M Jose, and Xiangnan He. 2019.  A Simple Convolutional Generative Network for Next Item Recommendation. In _Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining_. ACM.
  * Zhao and Akoglu (2019) Lingxiao Zhao and Leman Akoglu. 2019.  Pairnorm: Tackling oversmoothing in gnns.  _arXiv_ (2019).
  * Zhou et al. (2022) Kun Zhou, Hui Yu, Wayne Xin Zhao, and Ji-Rong Wen. 2022\.  Filter-enhanced MLP is all you need for sequential recommendation. In _Proceedings of the ACM Web Conference 2022_. 2388–2399.

##  Appendix A Notations

Table A1. Key Notations notations |  meanings
---|---
$\mathbb{U}$ |  the set of users
$\mathbb{V}$ |  the set of items
$S_{i}$ |  the historical interaction sequence of user $u_{i}$
$v_{s_{t}}(i)$ |  the $t$-th item in $S_{i}$
$B_{i}$ |  the fixed-length sequence converted from $S_{i}$
$v_{b_{t}}(i)$ |  the $t$-th item in $B_{i}$
$v_{g}(i)$ |  the ground-truth next item that user $u_{i}$ will interact with

Table A1 summarizes the key notations used in this paper.

##  Appendix B Reproducibility

Table A2. Best-performing Hyper-parameters in $\mathop{\mathtt{MSSG}}\limits$,
$\mathop{\mathtt{MSSG\text{-}u}}\limits$ and Baseline Methods

Dataset | $\mathop{\mathtt{FPMC}}\limits$ |  | $\mathop{\mathtt{Caser}}\limits$ |  | $\mathop{\mathtt{NARM}}\limits$ |  | $\mathop{\mathtt{HGN}}\limits$ |  | $\mathop{\mathtt{HAM}}\limits$ |  | $\mathop{\mathtt{SASRec}}\limits$
---|---|---|---|---|---|---|---|---|---|---|---
$d$ |  | $d$ | $n_{s}$ | $n_{p}$ | $n_{v}$ | $n_{f}$ |  | $d$ | $l_{r}$ |  | $d$ | $n_{s}$ | $n_{p}$ | $\lambda$ |  | $d$ | $n_{s}$ | $n_{p}$ | $\lambda$ | $n_{l}$ | $n_{o}$ |  | $d$ | $n$ | $n_{h}$ | $n_{b}$
$\mathop{\texttt{Beauty}}\limits$ | 512 |  | 512 | 4 | 1 | 2 | 8 |  | 512 | 1e-3 |  | 512 | 3 | 2 | 1e-3 |  | 512 | 3 | 2 | 1e-3 | 1 | 1 |  | 128 | 75 | 4 | 2
$\mathop{\texttt{Toys}}\limits$ | 512 |  | 512 | 4 | 1 | 1 | 4 |  | 512 | 1e-3 |  | 512 | 3 | 1 | 1e-4 |  | 512 | 3 | 1 | 1e-3 | 1 | 1 |  | 128 | 50 | 2 | 3
$\mathop{\texttt{Children}}\limits$ | 128 |  | 512 | 4 | 1 | 2 | 4 |  | 256 | 1e-4 |  | 256 | 3 | 1 | 0 |  | 256 | 4 | 2 | 1e-4 | 1 | 2 |  | 256 | 175 | 2 | 1
$\mathop{\texttt{Comics}}\limits$ | 256 |  | 512 | 4 | 1 | 1 | 4 |  | 256 | 1e-3 |  | 512 | 3 | 1 | 0 |  | 512 | 3 | 1 | 0 | 1 | 3 |  | 256 | 200 | 1 | 1
$\mathop{\texttt{ML-1M}}\limits$ | 256 |  | 128 | 6 | 1 | 4 | 16 |  | 512 | 1e-4 |  | 128 | 4 | 1 | 1e-3 |  | 512 | 5 | 1 | 1e-3 | 2 | 1 |  | 256 | 150 | 4 | 3
$\mathop{\texttt{ML-20M}}\limits$ | 128 |  | 256 | 6 | 1 | 2 | 8 |  | OOM | OOM |  | 128 | 4 | 2 | 1e-3 |  | 256 | 5 | 2 | 1e-3 | 3 | 3 |  | 256 | 150 | 2 | 3

Dataset | $\mathop{\mathtt{SASRec\text{-}Cat}}\limits$ |  | $\mathop{\mathtt{SASRec\text{-}Max}}\limits$ |  | $\mathop{\mathtt{Bert4Rec}}\limits$ |  | $\mathop{\mathtt{FMLP}}\limits$ |  | $\mathop{\mathtt{MSSG\text{-}u}}\limits$ |  | $\mathop{\mathtt{MSSG}}\limits$
---|---|---|---|---|---|---|---|---|---|---|---
$d$ | $n$ | $n_{h}$ | $n_{b}$ |  | $d$ | $n$ | $n_{h}$ | $n_{b}$ |  | $d$ | $n_{h}$ | $n_{b}$ |  | $d$ | $n$ | $n_{h}$ | $n_{b}$ |  | $d$ | $n$ | $n_{h}$ | $n_{b}$ |  | $d$ | $n$ | $n_{h}$ | $n_{b}$
$\mathop{\texttt{Beauty}}\limits$ | 256 | 50 | 4 | 3 |  | 128 | 50 | 2 | 3 |  | 512 | 4 | 1 |  | 128 | 200 | 1 | 3 |  | 256 | 75 | 4 | 2 |  | 256 | 75 | 16 | 3
$\mathop{\texttt{Toys}}\limits$ | 256 | 75 | 8 | 5 |  | 128 | 100 | 16 | 3 |  | 512 | 4 | 1 |  | 128 | 50 | 1 | 3 |  | 256 | 50 | 4 | 4 |  | 256 | 50 | 8 | 4
$\mathop{\texttt{Children}}\limits$ | 256 | 100 | 2 | 2 |  | 256 | 200 | 2 | 2 |  | 256 | 4 | 2 |  | 256 | 150 | 1 | 1 |  | 256 | 200 | 1 | 2 |  | 512 | 100 | 1 | 1
$\mathop{\texttt{Comics}}\limits$ | 256 | 200 | 1 | 2 |  | 256 | 100 | 1 | 3 |  | 128 | 4 | 1 |  | 512 | 200 | 1 | 1 |  | 512 | 200 | 1 | 1 |  | 512 | 200 | 1 | 1
$\mathop{\texttt{ML-1M}}\limits$ | 256 | 75 | 4 | 3 |  | 512 | 200 | 2 | 4 |  | 256 | 4 | 3 |  | 512 | 175 | 1 | 1 |  | 512 | 200 | 2 | 5 |  | 512 | 200 | 4 | 4
$\mathop{\texttt{ML-20M}}\limits$ | 256 | 200 | 2 | 4 |  | 512 | 150 | 2 | 2 |  | 128 | 4 | 3 |  | 512 | 150 | 1 | 2 |  | 512 | 150 | 8 | 5 |  | 256 | 100 | 4 | 4

  * •

In the table. “OOM” represents the out-of-memory issue.

We implement $\mathop{\mathtt{MSSG}}\limits$ and
$\mathop{\mathtt{MSSG\text{-}u}}\limits$ in Python 3.9.13 with PyTorch 1.10.2.
We use Adam optimizer with learning rate 1e-3 for
$\mathop{\mathtt{MSSG}}\limits$ and $\mathop{\mathtt{MSSG\text{-}u}}\limits$
on all the datasets. For all the baseline methods except
$\mathop{\mathtt{FPMC}}\limits$ and $\mathop{\mathtt{Bert4Rec}}\limits$, we
use the implementation provided by the authors in GitHub. For
$\mathop{\mathtt{FPMC}}\limits$ and $\mathop{\mathtt{Bert4Rec}}\limits$, we
use the implementation in RecBole 333https://recbole.io/, a widely used
library to benchmark recommendation methods. For
$\mathop{\mathtt{SASRec}}\limits$, $\mathop{\mathtt{FMLP}}\limits$,
$\mathop{\mathtt{MSSG\text{-}u}}\limits$ and $\mathop{\mathtt{MSSG}}\limits$,
we search the embedding dimension $d$ in $\\{64,128,256,512\\}$, the length of
the fixed-length sequences $n$ in $\\{50,75,100,125,150,175,200\\}$, the
number of heads $n_{h}$ in $\\{1,2,4,8,16\\}$, and the number of blocks
$n_{b}$ in $\\{1,2,3,4,5\\}$. For $\mathop{\mathtt{Bert4Rec}}\limits$, we
search $d$ in $\\{64,128,256,512\\}$, $n_{h}$ in $\\{1,2,4,8,16\\}$ and
$n_{b}$ in $\\{1,2,3,4,5\\}$. For $\mathop{\mathtt{SASRec\text{-}Cat}}\limits$
and $\mathop{\mathtt{SASRec\text{-}Max}}\limits$, the search range of $d$, $n$
and $n_{h}$ is the same with that in $\mathop{\mathtt{SASRec}}\limits$. We
search $n_{b}$ in $\mathop{\mathtt{SASRec\text{-}Cat}}\limits$ and
$\mathop{\mathtt{SASRec\text{-}Max}}\limits$ in $\\{2,3,4,5\\}$ as
$\mathop{\mathtt{SASRec\text{-}Cat}}\limits$ and
$\mathop{\mathtt{SASRec\text{-}Max}}\limits$ are equivalent to
$\mathop{\mathtt{SASRec}}\limits$ when $n_{b}$=$1$. We use GELU (Hendrycks and
Gimpel, 2016) as the activation function in the feed-forward layer for
$\mathop{\mathtt{SASRec}}\limits$,
$\mathop{\mathtt{SASRec\text{-}Cat}}\limits$,
$\mathop{\mathtt{SASRec\text{-}Max}}\limits$
$\mathop{\mathtt{MSSG\text{-}u}}\limits$ and $\mathop{\mathtt{MSSG}}\limits$.
We use the PyTorch implementation in GitHub
444https://github.com/pmixer/SASRec.pytorch for
$\mathop{\mathtt{SASRec}}\limits$. For $\mathop{\mathtt{FPMC}}\limits$, we
search $d$ in $\\{64,128,256,512\\}$. For $\mathop{\mathtt{Caser}}\limits$ we
search $d$ in $\\{64,128,256,512\\}$, the length of the subsequences $n_{s}$
in $\\{4,5,6\\}$, the number of negative items during training $n_{p}$ in
$\\{1,2\\}$, the number of vertical filters in CNNs $n_{v}$ in $\\{1,2,4\\}$,
and the number of horizontal filters in CNNs $n_{f}$ in $\\{4,8,16\\}$. For
$\mathop{\mathtt{NARM}}\limits$ we search $d$ in $\\{64,128,256,512\\}$ and
the learning rate $l_{r}$ in {1e-2, 1e-3, 1e-4}. For
$\mathop{\mathtt{HGN}}\limits$ we search $d$ in $\\{64,128,256,512\\}$,
$n_{s}$ in $\\{3,4,5\\}$, $n_{p}$ in $\\{1,2\\}$, and the regularization
factor $\lambda$ in {0, 1e-3, 1e-4}. For $\mathop{\mathtt{HAM}}\limits$ we
search $d$ in $\\{64,128,256,512\\}$, $n_{s}$ in $\\{3,4,5\\}$, $n_{p}$ in
$\\{1,2\\}$, $\lambda$ in {0, 1e-3, 1e-4}, the number of items in low order
$n_{l}$ in $\\{1,2,3\\}$, and the order of item synergies $n_{o}$ in
$\\{1,2,3\\}$. Following the instruction in RecBole, we use the Bayesian
personalized ranking loss (Rendle et al., 2012) and cross-entropy loss for
$\mathop{\mathtt{FPMC}}\limits$ and $\mathop{\mathtt{Bert4Rec}}\limits$,
respectively. We report the best-performing hyper-parameters of
$\mathop{\mathtt{MSSG}}\limits$, $\mathop{\mathtt{MSSG\text{-}u}}\limits$ and
baseline methods in Table A2.

##  Appendix C Dataset Pre-processing and Statistics

Table A3. Dataset Statistics

dataset | #users | #items | #intrns | #intrns/u | #u/i
---|---|---|---|---|---
$\mathop{\texttt{Beauty}}\limits$ | 22,363 | 12,101 | 198,502 | 8.9 | 16.4
$\mathop{\texttt{Toys}}\limits$ | 19,412 | 11,924 | 167,597 | 8.6 | 14.1
$\mathop{\texttt{Children}}\limits$ | 48,296 | 32,871 | 2,784,423 | 57.6 | 84.7
$\mathop{\texttt{Comics}}\limits$ | 34,445 | 33,121 | 2,411,314 | 70.0 | 72.8
$\mathop{\texttt{ML-1M}}\limits$ | 6,040 | 3,952 | 1,000,209 | 165.6 | 253.1
$\mathop{\texttt{ML-20M}}\limits$ | 129,780 | 13,663 | 9,926,480 | 76.5 | 726.5

  * •

In this table, “#users”, “#items” and “#intrns” represents the number of
users, items and user-item interactions, respectively. The column “#intrns/u”
has the average number of interactions of each user. The column “#u/i” has the
average number of interactions on each item.

Following $\mathop{\mathtt{SASRec}}\limits$, for
$\mathop{\texttt{Beauty}}\limits$, $\mathop{\texttt{Toys}}\limits$ and
$\mathop{\texttt{ML-1M}}\limits$, we only keep the users and items with at
least 5 ratings. For $\mathop{\texttt{Children}}\limits$,
$\mathop{\texttt{Comics}}\limits$ and $\mathop{\texttt{ML-20M}}\limits$, which
are not used in $\mathop{\mathtt{SASRec}}\limits$, following
$\mathop{\mathtt{HAM}}\limits$, we keep users with at least 10 ratings, and
items with at least 5 ratings. Following the literature (Kang and McAuley,
2018; Peng et al., 2021), we consider the ratings as users’ implicit feedback,
and convert ratings into binary values. Particularly, for ratings with a range
from 1 to 5, we convert ratings 4 and 5 to binary value 1, or 0 otherwise.
Table A3 presents the statistics of the processed datasets.

##  Appendix D More Experimental Results and Details

###  D.1. Comparison on Users with Different Activity Levels (Cont.)

$\mathop{\mathtt{MSSG}}\limits$ $\mathop{\mathtt{MSSG\text{-}u}}\limits$
$\mathop{\mathtt{SASRec}}\limits$

(a) $\mathop{\texttt{Comics}}\limits$

(b) $\mathop{\texttt{ML-1M}}\limits$

(c) $\mathop{\texttt{ML-20M}}\limits$

Figure A1. Performance on users of different activity levels

Figure A1 shows the performance of $\mathop{\mathtt{MSSG}}\limits$,
$\mathop{\mathtt{MSSG\text{-}u}}\limits$ and $\mathop{\mathtt{SASRec}}\limits$
in users of different activity levels on the
$\mathop{\texttt{Comics}}\limits$, $\mathop{\texttt{ML-1M}}\limits$ and
$\mathop{\texttt{ML-20M}}\limits$ datasets. As shown in Figure A1, the
performance on $\mathop{\texttt{Comics}}\limits$,
$\mathop{\texttt{ML-1M}}\limits$ and $\mathop{\texttt{ML-20M}}\limits$ has a
similar trend with that on $\mathop{\texttt{Beauty}}\limits$,
$\mathop{\texttt{Toys}}\limits$ and $\mathop{\texttt{Children}}\limits$
(Figure 3 in Section 6.2). Particularly, $\mathop{\mathtt{MSSG}}\limits$
substantially outperforms $\mathop{\mathtt{SASRec}}\limits$ on
$\mathop{\texttt{Comics}}\limits$ and $\mathop{\texttt{ML-1M}}\limits$ in both
active and less active users. Similarly, in most activity levels,
$\mathop{\mathtt{MSSG\text{-}u}}\limits$ considerably outperforms
$\mathop{\mathtt{SASRec}}\limits$ on $\mathop{\texttt{ML-1M}}\limits$ and
$\mathop{\texttt{ML-20M}}\limits$. On $\mathop{\texttt{Comics}}\limits$,
$\mathop{\mathtt{MSSG\text{-}u}}\limits$ also achieves highly comparable
performance with $\mathop{\mathtt{SASRec}}\limits$.

###  D.2. Calculating Average Similarities Between Item embeddings

Given the transformed sequence of user $u_{i}$:
$B_{i}$=$\\{v_{b_{1}}(i),v_{b_{2}}(i),\dots\\}$ (Section 4.1), we calculate
the average similarity of the embeddings of items within a sequence for each
SA block as follows:

(6)
$a_{i}^{m}=\frac{1}{|B_{i}|^{2}}\sum_{j=1}^{|B_{i}|}\sum_{k=1}^{|B_{i}|}\cos(\mathbf{e}_{j}^{m},\mathbf{e}_{k}^{m}),$

where $|B_{i}|$ is the length of $B_{i}$; $\mathbf{e}_{j}^{m}$ is the
embedding of the $j$-th item in $B_{i}$ after the $m$-th SA block;
$\cos(\cdot)$ is the cosine similarity; $a_{i}^{m}$ is the average similarity
between the embeddings of items in $B_{i}$ after the $m$-th SA block. Note
that as illustrated in Figure 1(b), $\mathop{\mathtt{SASRec}}\limits$ updates
the embedding of each item within the sequence in each SA block. Thus, we
expect different embeddings for the same item in different blocks. We
eliminate $i$ in $\mathbf{e}_{j}^{m}(i)$ in Equation 6 for simplicity.

Given $a_{i}^{m}$, we average it over all the users in the dataset:

(7) $a^{m}=\frac{1}{|\mathbb{U}|}\sum_{u_{i}\in\mathbb{U}}a_{i}^{m},$

where $a^{m}$ is the average similarity over all the users and $\mathbb{U}$ is
the set of all the users.

###  D.3. Scalability over Embedding Dimensions

Figure A2 presents the performance of $\mathop{\mathtt{SASRec}}\limits$ and
$\mathop{\mathtt{MSSG}}\limits$ at Recall@$10$ over different embedding
dimensions on the six datasets. We observe that when the embedding dimension
$d$=$2048$, both $\mathop{\mathtt{SASRec}}\limits$ and
$\mathop{\mathtt{MSSG}}\limits$ were unable to complete training within 24
hours. Thus, we limit the maximum embedding dimension to $1024$ in this
analysis.

$\mathop{\mathtt{MSSG}}\limits$ $\mathop{\mathtt{SASRec}}\limits$

(a) $\mathop{\texttt{Beauty}}\limits$

(b) $\mathop{\texttt{Toys}}\limits$

(c) $\mathop{\texttt{Children}}\limits$

(d) $\mathop{\texttt{Comics}}\limits$

(e) $\mathop{\texttt{ML-1M}}\limits$

(f) $\mathop{\texttt{ML-20M}}\limits$

Figure A2. Performance over different embedding dimensions

As shown in Figure A2, $\mathop{\mathtt{MSSG}}\limits$ is also more scalable
than $\mathop{\mathtt{SASRec}}\limits$ with respect to $d$. On all the
datasets, $\mathop{\mathtt{MSSG}}\limits$ could perform reasonably well when
$d$=$1024$. However, $\mathop{\mathtt{SASRec}}\limits$ fails on three out of
the six datasets ($\mathop{\texttt{Toys}}\limits$,
$\mathop{\texttt{ML-1M}}\limits$ and $\mathop{\texttt{ML-20M}}\limits$) when
$d$=$1024$. These results demonstrate the superior scalability of
$\mathop{\mathtt{MSSG}}\limits$ over $\mathop{\mathtt{SASRec}}\limits$ with
respect to $d$. We also notice that as illustrated in Figure A2, the
recommendation performance of $\mathop{\mathtt{MSSG}}\limits$ improves as $d$
increases on both $\mathop{\texttt{Children}}\limits$ and
$\mathop{\texttt{Comics}}\limits$. These results suggest that better
scalability in $d$ also leads to improved recommendation performance in real-
world datasets.

###  D.4. Calculating Entropy from Attention Weight Distributions

Given the attention map $A$ from the first SA block in
$\mathop{\mathtt{SASRec}}\limits$, we calculate the average entropy of the
attention weight distributions over all the items as follows:

(8)
$\frac{-1}{\sum\limits_{u_{i}\in\mathbb{U}}\sum\limits_{j=1}^{n}\mathbbm{1}(v_{b_{j}}(i)\neq
v_{0})}\sum\limits_{u_{i}\in\mathbb{U}}\sum\limits_{j=1}^{n}\mathbbm{1}(v_{b_{j}}(i)\neq
v_{0})\sum\limits_{k=1}^{j}(A_{ijk}\log(A_{ijk})),$

where $\mathbbm{1}(x)$ is an indicator function (i.e., $\mathbbm{1}(x)=1$ if
$x$ is true, otherwise 0); $n$ is the length of the transformed sequence
(Section 4.1); $v_{b_{j}}(i)\neq v_{0}$ excludes the padding items; and
$-\sum\limits_{k=1}^{j}(A_{ijk}\log(A_{ijk}))$ is the entropy calculated from
the attention weights of $v_{b_{j}}(i)$.