# Graph Spring Network and Informative Anchor Selection for Session-based
Recommendation

Zizhuo Zhang, and Bang Wang  Z. Zhang and B. Wang are with the School of
Electronic, Information and Communications, Huazhong University of Science and
Technology (HUST), Wuhan, China 430074
E-mail: {zhangzizhuo<EMAIL_ADDRESS>Corresponding Author: Bang Wang.
This work is supported in part by National Natural Science Foundation of China
(Grant No: 62172167).Manuscript received ; revised XXX.

###### Abstract

Session-based recommendation (SBR) aims at predicting the next item for an
ongoing anonymous session. The major challenge of SBR is how to capture richer
relations in between items and learn ID-based item embeddings to capture such
relations. Recent studies propose to first construct an item graph from
sessions and employ a Graph Neural Network (GNN) to encode item embedding from
the graph. Although such graph-based approaches have achieved performance
improvements, their GNNs are not suitable for ID-based embedding learning for
the SBR task. In this paper, we argue that the objective of such ID-based
embedding learning is to capture a kind of neighborhood affinity in that the
embedding of a node is similar to that of its neighbors’ in the embedding
space. We propose a new graph neural network, called Graph Spring Network
(GSN), for learning ID-based item embedding on an item graph to optimize
neighborhood affinity in the embedding space. Furthermore, we argue that even
stacking multiple GNN layers may not be enough to encode potential relations
for two item nodes far-apart in a graph. In this paper, we propose a strategy
that first selects some informative item anchors and then encode items’
potential relations to such anchors. In summary, we propose a GSN-IAS model
(Graph Spring Network and Informative Anchor Selection) for the SBR task. We
first construct an item graph to describe items’ co-occurrences in all
sessions. We design the GSN for ID-based item embedding learning and propose
an item entropy measure to select informative anchors. We then design an
unsupervised learning mechanism to encode items’ relations to anchors. We next
employ a shared gated recurrent unit (GRU) network to learn two session
representations and make two next item predictions. Finally, we design an
adaptive decision fusion strategy to fuse two predictions to make the final
recommendation. Extensive experiments on three public datasets demonstrate the
superiority of our GSN-IAS model over the state-of-the-art models.

###### Index Terms:

Graph spring network, Informative anchor selection, Item entropy, Session-
based recommendation, Graph neural network

##  1 Introduction

Recommendation systems as an important information filtering device can
effectively reduce information overload and assist users easily finding their
mostly interested items. A common approach [1, 2, 3] to provide personalized
recommendation is through analyzing user profile and his behavior to match his
mostly interested items. However, user profile may not be available in many
practical situations, for example, a user browsing items without logging. The
task of session-based recommendation (SBR) is hence proposed for such
situations, which has attracted widespread attentions recently [4]. According
to [5, 6, 7], the SBR task can be defined as follows:

Let $V=\\{v_{i}|i=1,2,...,N\\}$ denote the set of all unique items, where $N$
is the total number of items. A session is a chronological sequence of clicked
items for an anonymous user, which can be represented as
$S=\\{v_{1},v_{2},...,v_{\tau}\\}$, where $v_{i}\in V$ in the session is the
$i$-th item clicked by the user and $\tau$ is the session length. The SBR task
is to predict the next item to be clicked for an ongoing session, i.e.
$v_{\tau+1}$ for session $S$. A SBR recommendation model predicts the
preference scores for all candidate items in $V$, i.e.
$\hat{\mathbf{y}}=\\{\hat{y}_{1},\hat{y}_{2},...,\hat{y}_{N}\\}$, and
constructs a top-$K$ recommendation list by selecting $K$ items with highest
preference scores.

The challenges of SBR lies in two aspects: (1) Sessions are anonymous and
items are recorded with only their identifiers (ID), which makes it impossible
to establish users’ profiles nor to analyze items’ features; (2) Sessions are
often short, which makes it difficult to capture transitional logics in
sessions, not even mention that items often have no attribution information.
Early approaches have mainly relied on some simple popularity rules [8] or
matrix factorization [9] for predicting the next item, which have not well
encoded items’ representations, nor utilizing items’ sequential relations in
sessions [7]. Recently, for their powerful capabilities of representation
learning, many neural networks have been designed and applied for the SBR
task.

Some neural network-based methods [5, 6, 10, 11, 12, 13] have achieved
significant improvements over traditional approaches. The core idea is to
design a neural network model for encoding items’ representations and learning
the ongoing session representation, such that the next item is selected with
its representation the most similar to that the session representation, e.g.,
using a cosine or dot product similarity function. Some of neural models [10,
11] have further considered the collaborative information between multiple
sessions to enhance the session representation learning. However, they lack
the exploration of potential relations in between items from multiple
sessions.

Some graph-based models propose to first construct an item graph for item
embedding learning and session representation learning [7, 14, 15, 16, 17, 18,
19, 20, 21]. As many items’ transitions are extracted from multiple sessions,
it is expected that more useful transitional information can be encoded in
items’ embeddings via, say for example, a graph neural network (GNN). We
approve the effectiveness of item graph construction, as it has two
advantages: One is to alleviate the issue of item sparsity in individual
sessions; The other is to transfer the problem of mining item inter-relations
as exploring structural characteristics of a graph. Some well-known GNNs,
including graph convolution network (GCN) [22], graph attention network (GAT)
[23], LightGCN [24], have been adopted for learning item embedding mainly from
the viewpoint of item co-occurrences in the graph by capturing node-centric
local structural characteristics. Although these GNNs can encode graph
structural characteristics, they may not be much suitable for item embedding
learning in the SBR task.

The items contained in anonymous sessions are only equipped with their
identifiers (ID). On the one hand, items’ embeddings are often randomly
initialized. On the other hand, the objective of such ID-based embedding
learning is to ensure a kind of neighborhood affinity by capturing items’ co-
occurrences as their topological relations on the item graph. We refer the
neighborhood affinity to indicate the condition that a node embedding is
closer to its neighbors’ than its non-neighbors’ in the embedding space. Some
GNNs, like the GCN and GAT, employ a kind of global transformation kernel to
update items’ initial embeddings. Although they can capture local structural
characteristics, such global transformation may not ensure the neighborhood
affinity in the original item embedding space, not to mention introducing
additional trainable parameters for embedding space transformation. The
LightGCN, though without a global transformation, the aggregation computation
simply updates a node embedding via averaging its neighbors’, yet not
including the node itself embedding in the update process.

In this paper, we propose a new graph spring network (GSN) for learning item
embedding on an item graph. The basic idea of GSN is to ensure the
neighborhood affinity in the embedding space by aggregating the neighbors’
information to a node through a series of current optimal aggregation weights
in an iterative way. Compared with the GCN and GAT, it does not employ some
global transformation kernel, so without involving additional trainable
parameters. Compared with the LightGCN, its aggregation weights computation
directly depends on item embeddings, rather than simple graph Laplacian
matrix.

We can stack multiple GSN layers to include high-order neighbors for learning
item embedding, however it still may not be enough to encode possible
relations for two item nodes far-apart in the item graph. Indeed, the item
graph only establishes edges of co-appeared items in sessions. It could be the
case that some items have not co-appeared in sessions, but they may share some
similar latent features, say for example categorical features. This resembles
the case of two nodes far-apart in the item graph but containing similar
latent features, which motivates us to further encode some global topological
signals for each item. In this paper, we propose to first select some
informative items (called anchors) and then encode potential relations to
these anchors.

In this paper, we proposed a GSN-IAS model (Graph Spring Network and
Informative Anchor Selection) for the SBR task. An item graph is first
constructed for describing items’ co-occurrences in all sessions. We design
the GSN for item embedding learning based on the item graph, and analyze its
convergence property. We propose a measure, called item entropy, to select
informative anchors only based on their statistics in sessions. We next design
an unsupervised learning mechanism to output items’ encodings, which is to
encode items’ potential relations to anchors. Based on item embedding and item
encoding, we employ a shared gated recurrent unit (GRU) network to learn two
session representations and output two next item predictions. Finally, we
design an adaptive decision fusion strategy to fuse the two predictions to
output final preference scores for recommendation list construction. Extensive
experiments on three public real-world datasets validate that our GSN-IAS
outperforms the state-of-the-art methods .

Our main contributions can be summarized as follows:

  * •

Propose a new graph neural network (GSN) for item embedding learning.

  * •

Provide a proof on the GSN convergence.

  * •

Define item entropy for informative anchor selection.

  * •

Propose an unsupervised method for anchor-based item encoding learning.

  * •

Propose a parameters shared GRU for two session representations and two next
item predictions.

  * •

Propose an adaptive decision fusion to fuse two predictions for final
recommendation.

The rest is organized as follows: Section 2 reviews the related work. Section
3 presents our GSN-IAS model. Experiment settings are provided in Section 4
and results are analyzed in Section 5. Section 6 concludes this paper.

Figure 1: The overall architecture of the proposed GSN-IAS model. (a) Item
graph construction; (b) Graph spring network for item embedding; (c)
Informative item selection for item encoding; (d) A shared GRU network for
session representation learning; (e) Adaptive fusion of two predictions.

##  2 Related Work

We review related work from three aspects: traditional methods, neural network
methods and graph-based methods.

###  2.1 Traditional Methods

Some general recommendation approaches [8, 9, 25] can be directly applied in
the SBR task. For example, the item-based method [8] recommends items by
computing items’ similarity based on the co-occurrence relations. However,
these methods neglect the sequential information in a session, i.e. the order
of items. Some other studies [26, 27, 28] employ Markov chain to model
sequential information of a session. For example, Rendle et al. [27] combine
matrix factorization and first-order Markov chain for next item prediction.
However, the independence assumption of Markov chain-based methods is so
strict, limiting its prediction accuracy [7]. Recently, some studies [29, 30]
realize the importance of items’ co-occurrence relations and temporal
properties in sessions, and they can achieve competitive performance by using
the k-nearest-neighbor approach and temporal decay functions.

###  2.2 Neural Network Methods

Recurrent neural networks (RNNs) are capable of sequential modeling, and many
RNN-based models have been designed for the SBR task [5, 10, 13, 31, 12, 32,
33, 34]. For example, Hidasi et al. [12] propose a GRU4Rec model by applying a
GRU layer to encoder sequential items. Li et al. [5] propose a NRAM model to
boost a GRU layer with attention to learn session representation by
discriminating GRU hidden states. Wang et al. [10] propose a CSRM model to
exploit collaborative information from multiple sessions. Ren et al. [13]
propose a RepeatNet model that incorporates a repeat-explore mechanism into a
GRU network to automatically learn the switch probabilities between repeat and
explore modes.

Besides using RNNs, some other neural networks have also be explored for the
SBR task [6, 11, 35, 36, 37, 38, 39, 40, 41]. For example, Liu et al. [6]
propose the STAMP model that employs an attention network to emphasize the
importance of the last click item when learning session representation. Kang
et al. [35] propose the SASRec algorithm by stacking self-attention layers to
capture latent relations in between consecutive items in a session. Yuan et
al. [36] propose a NextItNet model by using a dilated convolutional network to
capture dependencies in between items. Song et al. [37] propose the ISLF model
that employs a recurrent variational auto-encoder (VAE) to take interest shift
into account. Pan et al. [39] apply a modified self-attention network to
estimate items’ importance in a session. Luo et al. [11] integrate the
collaborative self-attention network to learn the session representation and
predict the intent of the current session by investigating neighborhood
sessions. Yuan et al. [40] propose a dual sparse attention network to find the
possible unrelated item in sessions.

The aforementioned neural models mainly consider item transition or co-
occurrence relations within a single session or several similar sessions,
which limits their performance because of their lack of item embedding
learning against the whole set of all available items and sessions.

###  2.3 Graph-based Methods

Recently, graph neural models have aslo been adopted in the SBR task [7, 14,
15, 16, 17, 18, 19, 20, 21, 42, 43, 44]. Wu et al. [7] propose a SR-GNN model
to construct a session graph and employ the GGNN model [45] for item
representation learning. Xu et al. [14] make a combination of GNN and multi-
layer self-attention network. Qiu et al. propose a FGNN model to convert a
session into a directed weighted graph and use a weighted attention graph
neural layer for item embedding learning. Zheng et al. [19] propose a DGTN
model in which a session together with its similar sessions are used to first
construct an item graph. Yu et al. [20] propose a TAGNN model with a target
attention mechanism to learn a target-aware session representation. Wang et
al. [18] propose a GCE-GNN model to learn two types of item embeddings from a
session graph and a global item graph. Zhang et al. [43] propose a random walk
approach to mine a kind of latent categorical information of items from an
item graph. Xia et al. [15] learn the inter- and intra-session information
from two types of hypergraphs. Li et al. [44] propose a disentangled GNN
method to cast item and session embeddings with disentangled representations
of multiple factors.

##  3 The Proposed GSN-IAS model

Fig. 1 presents the architecture of our GSN-IAS model, which consists of the
following parts: (1) item graph construction; (2) graph spring network for
item embedding; (3) informative anchor selection for item encoding; (4)
session representation learning; and (5) prediction and fusion.

###  3.1 Item Graph Construction

To deal with item sparsity in one session, we first construct an item graph to
capture potential items’ inter-relations from all sessions. In particular, we
construct an undirected weighted item graph
$\mathcal{G}=\\{\mathcal{V},\mathcal{E}\\}$ with $\mathcal{V}$ the set of
nodes (viz. items) and $\mathcal{E}$ the set of edges as follows: An edge
$e_{ij}=(v_{i},v_{j},w_{i,j})$ in $\mathcal{E}$ is established between an item
$v_{i}$ and another item $v_{j}$, if the $v_{j}$ is within a window of size
$k$ centered at $v_{i}$ in any session, and $w_{i,j}$ is its weight
corresponding the number of appearances of the relations $(v_{i},v_{j})$ in
all sessions. Fig. 1 illustrates an item graph constructed from three
sessions. Take item $v_{3}$ for example. For a window size $k=2$, the
neighbors of item $v_{3}$ include $\\{v_{1},v_{2},v_{4},v_{5},v_{6}\\}$.

Figure 2: An example to illustrate the GSN core operations. (a) A node $v_{i}$
with three neighbors $v_{1},v_{2},v_{3}$. (b) The iteration process of GSN.
(c) The lower part illustrates the input embeddings of the four nodes. After
aggregation weights computation, it next illustrates the weighted neighbors’
embeddings. The adjustments according to neighbors’ embeddings are illustrated
as dashed arrows; While the last one shows the updated embedding for node
$v_{i}$ according to its own embedding and the weighted sum of its neighbors’
embeddings. (d) Likens the GSN operation to a process in which multiple
springs find a balance point via springs’ push and pull.

Input: $\mathbf{h}_{i}\in\mathbb{R}^{d}$ (the embedding of node $v_{i}$), and
$\\{\mathbf{h}_{j}\in\mathbb{R}^{d}|v_{j}\in\mathcal{N}_{i}\\}$ (the
embeddings of $v_{i}$’s neighbors)

Output: $\mathbf{h}_{i}^{\prime}\in\mathbb{R}^{d}$ (updated embedding of
$v_{i}$)

1
$\mathbf{h}\leftarrow\mathtt{UN}(\mathbf{h})=\frac{\mathbf{h}}{\|\mathbf{h}\|}$,
for all $v_{i},v_{j}$

2 $\mathbf{c}_{i}^{(0)}$ $\leftarrow$ $\mathbf{h}_{i}$

3 for  _$t=1,2,...,T$_ do

4 $w=0$

5 for  _$v_{j}\in\mathcal{N}_{i}$_ do

6
$\alpha_{ij}\leftarrow\mathbf{h}_{j}^{\mathsf{T}}\cdot\mathbf{c}_{i}^{(t-1)}$
// Compute similarity

7 $w\leftarrow w+\exp(\alpha_{ij})$

8 end for

9 for  _$v_{j}\in\mathcal{N}_{i}$_ do

10 $\alpha_{ij}\leftarrow\frac{\exp(\alpha_{ij})}{w}$ // Normalize to
probability

11 end for

12
$\mathbf{c}_{i}\leftarrow\mathtt{UN}(\mathbf{h}_{i}+\sum_{v_{j}\in\mathcal{N}_{i}}\alpha_{ij}\mathbf{h}_{j})$
// Update

13 end for

Result: $\mathbf{h}_{i}^{\prime}\leftarrow\mathbf{c}_{i}$

Algorithm 1 The Graph Spring Network (core operation for one node $v_{i}$)

###  3.2 Graph Spring Network for Item Embedding

####  3.2.1 Graph Spring Network

We propose a graph spring network (GSN) to learn nodes’ embeddings from a
graph, which aims to find a balance point for each node in the embedding space
given its neighbors’ embeddings in an iterative way. We first introduce the
operation of unit normalization for regulating a node’s embedding as a unit
vector as follows:

$\mathtt{UN}(\mathbf{h})=\frac{\mathbf{h}}{\|\mathbf{h}\|},$ (1)

where $\mathbf{h}$ denotes an item embedding and $\|\mathbf{h}\|$ its vector
norm, 2-norm here.

For an item node $v_{i}$ in the item graph $\mathcal{G}$, let
$\mathcal{N}_{i}$ denote the set of its one-hop neighbors. Given its
neighbors’ embeddings $\\{\mathbf{h}_{j}|v_{j}\in\mathcal{N}_{i}\\}$, the core
operation of GSN in one iteration contains two main steps:

$\displaystyle\alpha_{ij}^{(t+1)}$
$\displaystyle=\frac{\exp(\mathbf{h}_{j}^{\mathsf{T}}\cdot\mathbf{c}_{i}^{(t)})}{\sum_{v_{j}\in\mathcal{N}_{i}}\exp(\mathbf{h}_{j}^{\mathsf{T}}\cdot\mathbf{c}_{i})},$
(2) $\displaystyle\mathbf{c}_{i}^{(t+1)}$
$\displaystyle=\mathtt{UN}(\mathbf{h}_{i}+\sum_{v_{j}\in\mathcal{N}_{i}}\alpha_{ij}^{(t+1)}\mathbf{h}_{j}),$
(3)

where $\mathbf{c}_{i}$ is an intermediate variable used for iteration and
$\mathbf{c}_{i}^{(0)}=\mathbf{h}_{i}$. Note that the unit normalization
obtains a unit vector without changing its direction. Algorithm 1 presents the
pseudo-codes for the core operations of one-layer GSN. Notice that for the
input embeddings of a node $v_{i}$ and its neighbors, one-layer GSN iterates
$T$ times to update the node $v_{i}$’s embedding.

Fig. 2 uses a toy example to illustrate the embedding update process for one
node. The weight $\alpha_{ij}$ measures the normalized similarity between node
$v_{i}$ and its neighbor $v_{j}$ in the embedding space. The weighted vector
$\alpha_{ij}\mathbf{h}_{j}$ can be regarded as some virtual force exerted by
$v_{j}$ to $v_{i}$, liken to a spring between two nodes for pushing close or
pull away two nodes; While all $\alpha_{ij}\mathbf{h}_{j}$s together with
$\mathbf{h}_{i}$ shall decide the new direction of the updated embedding for
$v_{i}$. An iterated process of such core operations would lead to that the
embedding $\mathbf{h}_{i}$ of node $v_{i}$ gradually converges to some balance
point in the embedding space, liken that the virtual forces by its neighbors
reach a balance and no longer change its position.

####  3.2.2 Convergence analysis

The design philosophy of our GSN is to enable the embeddings of neighboring
nodes can also reflect the local structural relations between a node and its
neighbors in the item graph. We investigate whether these local structural
relations have a balanced point, i.e. whether GSN converges after a sufficient
number of iterations. We next prove the convergence of GSN by combining GSN
and a von Mises-Fisher distribution [46]. That is, for a node $v_{i}$, the
iterative updating leads to the convergence of its normalized similarities
$\alpha_{ij}$ to its neighbors as well as its embedding $\mathbf{h}_{i}$.

The probability density function of the von Mises-Fisher distribution
(vMF)111https://en.wikipedia.org/wiki/Von_Mises-Fisher_distribution is given
by:

$f(\mathbf{x};\bm{\mu},\kappa)=C(\kappa)\exp(\kappa\bm{\mu}^{\mathsf{T}}\mathbf{x})\propto\exp(\kappa\bm{\mu}^{\mathsf{T}}\mathbf{x}),$
(4)

where $\bm{\mu}$ and $\kappa\geq 0$ are called the mean direction and the
concentration parameter, respectively, and $C(\kappa)$ is a constant. The
larger value of $\kappa$, the higher concentration of the distribution around
the mean direction $\bm{\mu}$.

Let $\mathbf{c}_{i}$ denote the parameter of vMF distribution. We initialize
nodes’ embeddings $\mathbf{h}_{i}$ and
$\\{\mathbf{h}_{j}|v_{j}\in\mathcal{N}_{i}\\}$ by:

$\displaystyle\mathbf{h}_{i}\sim{\rm vMF}(\mathbf{c}_{i},1),$ (5)
$\displaystyle\mathbf{h}_{j}\sim{\rm vMF}(\mathbf{c}_{i},\alpha_{ij}),$ (6)

where $\alpha_{ij}$ is the concentration of $\mathbf{h}_{j}$ around the
$\mathbf{c}_{i}$. With such initializations, the GSN operation for computing
$\mathbf{c}_{i}$ can be converted to estimate the parameter $\mathbf{c}_{i}$
based on the noisy observation
$\mathbf{h}=\\{\mathbf{h}_{i},\mathbf{h}_{j}|v_{i}\vee
v_{j}\in\mathcal{N}_{i}\\}$. The following theorem summarizes the property and
convergence of the GSN core operation:

###### Theorem 1

The computation process of GSN core operation is equivalent to an expectation-
maximization (EM) algorithm estimating parameter of the vMF distribution by
maximizing the likelihood probability $P(\mathbf{h}_{i}|\mathbf{c}_{i})$. The
convergence of GSN core operation is equivalent to the convergence of the EM
algorithm for estimating the parameter of vMF distribution.

###### Proof 1

See Appendix .1.

Theorem 1 indicates that the GSN iteration process can be transformed as using
the EM algorithm for parameter estimation. In Proof 1, we prove that Eq. (2)
is performing the E-step, and Eq. (3) is performing the M-step. Our GSN in
fact is iteratively performing the E-step and M-step to estimate the parameter
$\mathbf{c}_{i}$ based on the given observations
$\mathbf{h}=\\{\mathbf{h}_{i},\mathbf{h}_{j}|v_{i}\vee
v_{j}\in\mathcal{N}_{i}\\}$. According to the convergence of EM algorithm, the
GSN therefore converges. The convergence of GSN core operation also reflects
the difference between our GSN and some widely used GNNs, like LightGCN [24]
and GAT [23]. Given the neighbors’ embeddings of a node $v_{i}$, our GSN is to
iteratively find a locally optimal aggregation weights between $v_{i}$ and its
neighbors; While most GNNs compute the aggregation weights only once by an
attention function or by direct graph Laplacian matrix. More comparisons with
other GNNs are provided in Appendix .2.

####  3.2.3 Item Embedding

We can also stack multiple layers of GSN to include high-order neighbors for
learning a node embedding. Let $\mathbf{h}_{i}^{(l)}(l=1,...,L)$ denote the
$l$-th layer embedding of $v_{i}$ learned by GSN, and $\mathbf{H}^{(l)}$
denote the $l$-th layer embedding matrix of all nodes. For an item node
$v_{i}$, to enjoy some potential relations with its higher orders’ neighbors,
we compute its final item embedding $\mathbf{h}_{i}^{a}$ by

$\mathbf{h}_{i}^{a}=\mathbf{h}_{i}^{(0)}+\mathbf{h}_{i}^{(1)}+...+\mathbf{h}_{i}^{(L)}.$
(7)

We denote $\mathbf{H}^{a}\in\mathbb{R}^{N\times d}$ as the item embeddings
matrix, where the $i$-th row is the embedding of item $v_{i}$.

###  3.3 Informative Anchor Selection for Item Encoding

####  3.3.1 Informative Anchor Selection

We would like to select a few of representative items to describe potential
categorical features from thousands of items. To this end, we propose a
measure, called item entropy, to evaluate the informativeness of an item. The
item entropy $H(v_{i})$ of $v_{i}$ is defined by

$H(v_{i})=-\sum_{j=1}^{\lvert\mathcal{S}\rvert}P_{v_{i},s_{j}}\cdot\log(P_{v_{i},s_{j}})$
(8)

where $\lvert\mathcal{S}\rvert$ is the number of all available sessions. If an
item $v_{i}$ is clicked in a session $s_{j}$, then $P_{v_{i},s_{j}}$ is
computed by

$\begin{split}P_{v_{i},s_{j}}=\frac{\text{number of clicks in session
}s_{j}}{\text{total number of clicks}}\times\\\ \frac{\text{number of sessions
including item }v_{i}}{\text{total number of sessions}};\end{split}$ (9)

Otherwise, $P_{v_{i},s_{j}}=0$. According to the definition, an item appearing
in more sessions has higher item entropy, and a session including more clicks
has more influence on item entropy. A large item entropy indicates that an
item appears in a lot of sessions and these sessions include more clicks. In
this regard, we select $M$ items with the top-$M$ highest item entropy as
informative items, called anchors. Let $\mathcal{A}$ denote the set of all
selected anchors.

####  3.3.2 Item Encoding

We extract the corresponding rows from item embedding matrix $\mathbf{H}^{a}$
to construct an anchor embedding matrix $\mathbf{A}\in\mathbb{R}^{M\times d}$.
Then we leverage a linear transformation to transfer the anchor embeddings
from the item embedding space to another so-called anchor encoding space:

$\mathbf{C}=\mathbf{W}_{c}\mathbf{A}+\mathbf{b}_{c},$ (10)

where $\mathbf{C}\in\mathbb{R}^{M\times d}$ is the embedding matrix of
anchors, $\mathbf{W}_{c}$ and $\mathbf{b}_{c}$ are trainable linear
transformation parameters.

We propose an unsupervised strategy to learn a soft assignment as the item-
anchor distribution to describe their relations. Given an embedding
$\mathbf{h}_{i}^{a}$ of item $v_{i}$, we use an encoder network to produce the
logits of the probabilities, and then convert them to a distribution
$\mathbf{p}_{i}\in\mathbb{R}^{M}$ by a softmax layer as follows:

$\displaystyle\bm{\beta}_{i}$ $\displaystyle=f_{p}(\mathbf{h}_{i}^{a}),$ (11)
$\displaystyle p_{i,j}$
$\displaystyle=\frac{\exp(\beta_{i,j})}{\sum_{j^{\prime}=1}^{M}\exp(\beta_{i,j^{\prime}})},$
(12) $\displaystyle\mathbf{p}_{i}$
$\displaystyle=[p_{i,1},p_{i,2},...,p_{i,M}],$ (13)

where $f_{p}(\cdot)$ is the encoder network to map an item embedding
$\mathbf{h}_{i}^{a}\in\mathbf{R}^{d}$ to a logits
$\bm{\beta}_{i}\in\mathbb{R}^{M}$. Any $d\rightarrow M$ encoder network can be
used as $f_{p}$. In this paper, we employ a two-layer feed forward neural
network to complete this task:

$f_{p}(\mathbf{h})=\mathbf{W}_{p}^{(2)^{\top}}{\rm
LeakyReLU}(\mathbf{W}_{p}^{(1)^{\top}}\mathbf{h}+\mathbf{b}_{p}^{(1)})+\mathbf{b}_{p}^{(2)},$
(14)

where $\mathbf{W}_{p}^{(1)}\in\mathbb{R}^{d\times
d},\mathbf{b}_{p}^{(1)}\in\mathbb{R}^{d}$ and
$\mathbf{W}_{p}^{(2)}\in\mathbb{R}^{d\times
M},\mathbf{b}_{p}^{(2)}\in\mathbb{R}^{M}$ are trainable parameters. We use
$\mathbf{P}\in\mathbb{R}^{N\times M}$ to denote the item-anchor distribution
matrix.

We assign the representative information of each anchor to items based on the
item-anchor distribution to obtain item encoding as follows:

$\mathbf{H}^{b}=\mathbf{P}\mathbf{C},$ (15)

where $\mathbf{H}^{b}\in\mathbb{R}^{N\times d}$ is the item encoding matrix,
the $i$-th row $\mathbf{h}_{i}^{b}=\mathbf{p}_{i}\mathbf{C}$ in
$\mathbf{H}^{b}$ is the item encoding for $v_{i}$. Notice that this process is
an end-to-end learning schema, where the model learns how to assign the
distribution for anchors of an input item.

###  3.4 Session Representation Learning

For a session $S=\\{v_{1},v_{2},...,v_{\tau}\\}$, in order to capture its
sequential information, we employ a gated recurrent unit (GRU) network to
learn the session representation from two perspectives of the item embeddings
$S^{a}=\\{\mathbf{h}_{1}^{a},\mathbf{h}_{2}^{a},...,\mathbf{h}_{\tau}^{a}\\}$
and item encodings
$S^{b}=\\{\mathbf{h}_{1}^{b},\mathbf{h}_{2}^{b},...,\mathbf{h}_{\tau}^{b}\\}$:

$\displaystyle(\mathbf{s}_{1}^{a},\mathbf{s}_{2}^{a},...,\mathbf{s}_{\tau}^{a})$
$\displaystyle={\rm
GRU}(\mathbf{h}_{1}^{a},\mathbf{h}_{2}^{a},...,\mathbf{h}_{\tau}^{a}),$ (16)
$\displaystyle(\mathbf{s}_{1}^{b},\mathbf{s}_{2}^{b},...,\mathbf{s}_{\tau}^{b})$
$\displaystyle={\rm
GRU}(\mathbf{h}_{1}^{b},\mathbf{h}_{2}^{b},...,\mathbf{h}_{\tau}^{b}),$ (17)

where $\mathbf{s}_{\tau}$ is the hidden state of GRU at the timestamp $\tau$.
We select the last hidden state $\mathbf{s}_{\tau}^{a}$ and
$\mathbf{s}_{\tau}^{b}$ as two session representations. We note that it is one
GRU network shared for learning both session representations, which can help
the GRU to be jointly optimized for both item embeddings and item encodings.

###  3.5 Prediction and Fusion

We propose to use decision fusion to obtain the final score prediction. Note
that $\mathbf{s}_{\tau}^{a}$ and $\mathbf{s}_{\tau}^{b}$ encode a session $S$
from two different feature spaces: The objective of $\mathbf{H}^{a}$ is to
encode local structural characteristics; While that of $\mathbf{H}^{b}$ is to
encode global topological information. A feature fusion might confuse the two
design objectives; yet a decision fusion may be able to reconcile them.

We first independently compute two intermediate predictions
$\mathbf{\hat{y}}^{a}\in\mathbb{R}^{d}$ and
$\mathbf{\hat{y}}^{b}\in\mathbb{R}^{d}$ based on $\mathbf{s}_{\tau}^{a}$ and
$\mathbf{s}_{\tau}^{b}$ by

$\displaystyle\mathbf{\hat{y}}^{a}$ $\displaystyle={\rm
softmax}(\mathbf{H}^{a}\mathbf{s}_{\tau}^{a}),$ (18)
$\displaystyle\mathbf{\hat{y}}^{b}$ $\displaystyle={\rm
softmax}(\mathbf{H}^{b}\mathbf{s}_{\tau}^{b}).$ (19)

We further employ two trainable weights to implement an adaptive decision
fusion as follows:

$\mathbf{\hat{y}}=\sigma(\omega^{a})\cdot\mathbf{\hat{y}}^{a}+\sigma(\omega^{b})\cdot\mathbf{\hat{y}}^{b},$
(20)

where $\mathbf{\hat{y}}\in\mathbb{R}^{N}$ is the final score prediction for
recommendation, and $\sigma(\omega^{a}),\sigma(\omega^{b})$ are the adaptive
fusion weights, $\sigma(\cdot)$ is the $\mathtt{sigmoid}$ function. The
top-$K$ highest-scored items are selected to construct a recommendation list.

We leverage the cross entropy loss function to supervise the prediction
$\mathbf{\hat{y}}^{a},\mathbf{\hat{y}}^{b}$ and $\mathbf{\hat{y}}$ as follows:

$\displaystyle\mathcal{L}_{a}(\mathbf{\hat{y}}^{a},\mathbf{y})$
$\displaystyle=-\sum_{i=1}^{N}y_{i}\log(\hat{y}_{i}^{a}),$ (21)
$\displaystyle\mathcal{L}_{b}(\mathbf{\hat{y}}^{b},\mathbf{y})$
$\displaystyle=-\sum_{i=1}^{N}y_{i}\log(\hat{y}_{i}^{b}),$ (22)
$\displaystyle\mathcal{L}_{c}(\mathbf{\hat{y}},\mathbf{y})$
$\displaystyle=-\sum_{i=1}^{N}y_{i}\log(\hat{y}_{i}),$ (23)
$\displaystyle\mathcal{L}$
$\displaystyle=\mathcal{L}_{a}+\mathcal{L}_{b}+\mathcal{L}_{c},$ (24)

where $\mathbf{y}$ is the ground truth, a one-hot indicative vector: $y_{i}=1$
if $v_{i}=v_{\tau+1}$; Otherwise $y_{i}=0$. Similarly,
$\hat{y}_{i}^{a},\hat{y}_{i}^{b},\hat{y}_{i}$ are the $i$-th scores in
$\mathbf{\hat{y}}^{a},\mathbf{\hat{y}}^{b},\mathbf{\hat{y}}$, respectively. At
last, we optimize the loss function $\mathcal{L}$ to train our model.

TABLE I: Statistics of the three datasets. Datasets | Yoochoose 1/64 | RetailRocket | Diginetica
---|---|---|---
number of nodes $N$ | 17,376 | 36,968 | 43,097
number of edges $|E|$ | 227,205 | 542,655 | 782,655

##  4 Experiment Settings

###  4.1 Datasets

We conduct experiments on three real-world datasets:
Yoochoose222http://2015.recsyschallenge.com/challenge.html,
RetailRocket333https://www.kaggle.com/retailrocket/ecommerce-dataset and
Diginetica444http://cikm2016.cs.iupui.edu/cikm-cup, which are commonly used in
the SBR task [5, 6, 7, 10, 16, 34, 40]. The Yoochoose is from the Recsys
Challenge 2015, containing six months of clicks from an European e-commerce
website. The RetailRocket is a Kaggle contest dataset published by an
e-commerce company, containing browsing activities in six months. The
Diginetica comes from CIKM Cup 2016, and only its transactional data are used.

To make a fair comparison, our data preprocessing is the same as that of [5,
6, 7, 10, 40]. In particular, we filter out sessions of length one and items
appearing less than five times. Furthermore, after constructing the item
graph, we adopt the data augmentation approach in [7, 16]. Table II summarizes
the statistics of the three datasets.

TABLE II: Statistics of the three datasets. Datasets | Yoochoose 1/64 | RetailRocket | Diginetica
---|---|---|---
# train sessions | 369,859 | 433,648 | 719,470
# test sessions | 55,696 | 15,132 | 60,858
# items | 17,376 | 36,968 | 43,097
# average lengths | 6.16 | 5.43 | 5.12

###  4.2 Parameter Setting

Following previous work [5, 6, 7, 10], we set the vector dimension $d=100$ and
the mini-batch size to 100 for the three datasets. We adopt the Adam optimizer
with the initial learning rate 0.01, with a decay rate of 0.1 after every 3
epoches. We set the L2 penalty to $10^{-5}$ to avoid overfitting. We set $k=3$
for the item graph construction. We set the GSN iteration $T=4$. The hyper-
parameters of the number of anchors $M$ and the number of GSN layer $L$ will
be discussed in our later section 5.5 of hyper-parameter analysis.

TABLE III: Overall performance comparison.

| Methods | Yoochoose 1/64 | RetailRocket | Digineitca
---|---|---|---|---
| HR@20(%) | MRR@20(%) | HR@20(%) | MRR@20(%) | HR@20(%) | MRR@20(%)
Traditional Methods | POP | 11.15 | 2.99 | 1.61 | 0.38 | 0.74 | 0.22
S-POP | 39.62 | 18.99 | 39.53 | 27.17 | 21.60 | 13.51
FPMC | 45.62 | 15.01 | 32.37 | 13.82 | 26.53 | 6.95
SKNN | 63.77 | 25.22 | 54.28 | 24.46 | 48.06 | 16.95
STAN | 69.45 | 28.74 | 53.48 | 26.81 | 49.93 | 17.59
Neural Methods | NARM | 68.32 | 28.63 | 50.22 | 24.59 | 49.70 | 16.17
STAMP | 68.74 | 29.67 | 50.96 | 25.17 | 45.64 | 14.32
CSRM | 69.85 | 29.71 | - | - | 51.69 | 16.92
CoSAN | 70.04 | 29.85 | 52.47 | 24.40 | 48.34 | 15.22
Graph-based Methods | SR-GNN | 70.57 | 30.94 | 50.32 | 26.57 | 50.73 | 17.59
GC-SAN | 70.66 | 30.04 | 51.18 | 27.40 | 50.84 | 17.79
TAGNN | 71.02 | 31.12 | - | - | 51.31 | 18.03
FLCSP | 71.58 | 31.31 | 52.63 | 25.85 | 51.68 | 17.27
Disen-GNN | 71.46 | 31.36 | - | - | 53.79 | 18.99
GCE-GNN | 72.18 | 30.84 | - | - | 54.22 | 19.04
|  $S^{2}$-DHCN | 68.34 | 27.89 | 53.66 | 27.30 | 53.18 | 18.44
Proposed Methods | GSN-IAS | 72.34 | 31.45 | 57.13 | 29.97 | 55.65 | 19.24
Improv.(%) | 0.22 | 0.29 | 5.25 | 9.38 | 2.64 | 1.05

  * 1

We have run 3 times in each dataset, and report the mean performances metrics,
and the variances of different runs are consistently smaller than 0.01% in our
model.

###  4.3 Competitors

We compare GSN-IAS with the following competitors, which are divided into
three groups:

Traditional methods: these apply some simple recommendation rules, like item
popularity, matrix factorization, Markov chain or k-nearest-neighbors.

$\cdot$ POP and S-POP recommend the most popular items in the training dataset
and in the current session respectively.

$\cdot$ FPMC [27] combines matrix factorization and Markov chain for the next
item recommendation.

$\cdot$ SKNN [29] uses the k-nearest-neighbors (KNN) approach for session-
based recommendation.

$\cdot$ STAN [30] extends the SKNN method to incorporate sequential and
temporal information with a decay factor.

Neural Network Models: these focus on designing neural network to learn
session representation.

$\cdot$ NARM [5] incorporates a GRU layer with attention mechanism to learn
session sequential representation.

$\cdot$ STAMP [6] uses an attention mechanism to capture general interests of
a session and current interests of the last click.

$\cdot$ CSRM [10] considers the collaborative neighborhors of the latest $m$
sessions for predicting the sessision intent.

$\cdot$ CoSAN [11] learns the session representation and predicts the session
intent by investigating neighborhood sessions.

Graph-based Models: these incorporate complex transition relations, co-
occurrence relations into graph to capture richer information.

$\cdot$ SR-GNN [7] is the first work proposing to apply the graph neural
network to learn item embedding.

$\cdot$ GC-SAN [14] combines the graph neural network and multi-layers self-
attention network.

$\cdot$ TAGNN [20] uses a target attention mechanism to learn session
representation.

$\cdot$ FLCSP [43] makes a decision fusion of latent categorical prediction
and sequential prediction.

$\cdot$ Disen-GNN [44] proposes a disentangled graph neural network to capture
the session purpose with the consideration of factor-level attention on each
item.

$\cdot$ GCE-GNN [18] constructs session graph and global graph to learn two
levels of item embedding.

$\cdot$ $S^{2}$-DHCN [15] learns the inter- and intra-session information from
two types of hypergraphs.

##  5 Experiment Results

We adopt two metrics commonly used in the SBR task, i.e., HR@20 and MRR@20.
HR@20 (Hit Rate) focuses on whether the desired item appearing in the
recommended list, without considering the ranking of item in the recommended
list. MRR@20 (Mean Reciprocal Rank) is the average of reciprocal ranks of the
correct recommended items in the recommendation list.

###  5.1 Overall Comparison (RQ1)

Table III presents the overall performance comparison between our GSN-IAS and
the competitors, where the best results in every column are boldfaced and the
second results are underlined. It is observed that our GSN-IAS outperforms the
others on all three datasets in terms of the highest HR@20 and MRR@20 on three
datasets.

In traditional methods, the POP and S-POP based on simple recommendation rules
are not competitive, since they lack the ability to capture the item
sequential dependency in sessions. The FPMC using Markov chain to model the
sequential relations also performs poorly, since the strict independence
assumption of Markov chain is inconsistent with the real situation of the SBR
task. The SKNN and STAN achieve competitive performances compared with neural
methods and graph-based methods, and the SKNN even reaches the second best of
HR@20 on RetailRocket dataset. They both consider the influence of similar
sessions, and the STAN designs two time decay functions to describe the
recency of a past session and the chronological order of items in a session,
respectively. These imply that the collaborative information of similar
sessions and the sequential relations in a session are important for the SBR
task.

The neural methods, i.e. the NARM, STAMP, CSRM and CoSAN, generally achieve
significant performance improvements over traditional methods, which reflects
the powerful representation ability of neural networks. However, these methods
focus on learning a session representation, but have neglected to exploit some
potential relations in between items from different sessions. Notice that
compared with the NARM and STAMP, the CSRM and CoSAN take consideration of the
collaborative information of similar sessions to assist the representation
learning of current session, which makes them get better performance.

The graph-based methods, i.e. the SR-GNN, GC-SAN, TAGNN, FLCSP, Disen-GNN,
GCE-GNN and $S^{2}$-DHCN, achieve the state-of-the-art performance, which
indicates that modeling the potential relations in between items by a graph
structure is helpful for item and senssion representation learning. The first
five construct a directed graph to capture item transition relations; While
the GCE-GNN and $S^{2}$-DHCN consider item co-occurrences via constructing an
undirected graph and a hypergraph respectively. The GCE-GNN gets three second
best performances including HR@20 on Yoochoose 1/64 and HR@20, MRR@20 on
Diginetica, and $S^{2}$-DHCN also gets competitive performances on
RetailRocket and Diginetica. These suggest the importance of item co-
occurrence relations for item embedding learning.

Our approach GSN-IAS outperforms all the state-of-the-art algorithms on the
three datasets. Especially on the RetailRocket dataset, the improvements of
HR@20 and MRR@20 are 5.25% and 9.38% compared with the second best. This
suggests the effectiveness of using our GSN for item embedding learning and
informative anchor selection for item encoding. Note that except the GCE-GNN
on Diginetica, other competitors only achieve the second best performance of
either HR@20 or MRR@20; While our GSN-IAS achieves the best on both metrics.

TABLE IV: Ablation study results.

Dataset | Yoochoose 1/64 | RetailRocket | Digineitca
---|---|---|---
Method | HR@20 | MRR@20 | HR@20 | MRR@20 | HR@20 | MRR@20
GSN-Anchor | 70.77 | 29.61 | 53.18 | 27.16 | 53.64 | 18.23
GSN-Item | 72.16 | 31.33 | 56.87 | 29.70 | 55.50 | 19.20
GSN-IAS-AvgFuse | 72.27 | 31.35 | 56.67 | 29.66 | 55.42 | 19.13
GSN-IAS | 72.34 | 31.45 | 57.13 | 29.97 | 55.65 | 19.24
$(\sigma(\omega^{a}),\sigma(\omega^{b}))$ | (0.8834, 0.1125) | (0.8421, 0.1517) | (0.8062, 0.1850)

###  5.2 Ablation Study

We conduct ablation experiments to examine the effectiveness of each component
in our GSN-IAS. We develop the following three ablation algorithms:

  * •

GSN-Anchor: It only uses item encoding for session representation learning and
prediction.

  * •

GSN-Item: It only uses item embedding for session representation learning and
prediction.

  * •

GSN-IAS-AvgFuse: It uses both item embedding and item encoding for session
representation learning, but uses an average pooling for decision fusion.

Table IV presents the results of ablation study. We first observe that GSN-IAS
achieves the best performance than its ablation algorithms. Even the worst-
performing GSN-Anchor has achieved the same level of performance as the state-
of-the-art SR-GNN, GC-SAN, TAGNN, FLCSP methods, and GSN-Item also outperforms
all competitors. These reflect two points: One is that each component in GSN-
IAS makes its contribution to more accurate prediction, where GSN-Item plays
the protagonist and GSN-Anchor the auxiliary; The other is that our GSN is an
effective graph neural network to learn item embedding for the SBR task.

From Table IV, we also observe that GSN-IAS outperforms the GSN-IAS-AvgFuse,
which indicates the effectiveness of our adaptive fusion for learning fusion
weights. On this basis, the last line of Table IV specifically shows the
fusion weights learned for different datasets, where the fusion weights are
learned differently for different datasets. Furthermore, it is not unexpected
that $\sigma(\omega^{a})>\sigma(\omega^{b})$ on all datasets. This is in
consistent with our previous analysis that the item embedding learning is the
dominant factor, while the informative anchors information complements the
former for the SBR task.

TABLE V: Performance comparison for using GCN, GAT, LightGCN for item
embedding learning.

Dataset | Yoochoose 1/64 | RetailRocket | Digineitca
---|---|---|---
Method | HR@20 | MRR@20 | HR@20 | MRR@20 | HR@20 | MRR@20
GCN-IAS | 71.86 | 30.42 | 56.73 | 27.47 | 50.10 | 14.88
GAT-IAS | 72.16 | 30.81 | 57.05 | 29.51 | 55.06 | 18.61
LightGCN-IAS | 72.47 | 30.98 | 57.18 | 29.55 | 55.64 | 19.20
GSN-IAS | 72.34 | 31.45 | 57.13 | 29.97 | 55.65 | 19.24

Figure 3: Visualization by t-sne for item embedding and anchor-based item
embedding. We conduct a KMeans (K=5) clustering, and present the embeddings
clustered in one class with the same color.

###  5.3 Comparison with other graph neural networks

We conduct experiments using other well-knwon graph neural networks, including
GCN [22], GAT [23], LightGCN [24], to replace our GSN for item embedding
learning. We fix the hyper-parameter of the GNN layer $L=\\{2,2,5\\}$ and the
number of anchors $M=\\{100,500,1000\\}$ for Yoochoose 1/64, RetailRocket,
Dignetica, respectively. These comparison algorithms are denoted as GCN-IAS,
GAT-IAS and LightGCN-IAS.

Table V presents the experiment results of using different GNNs. It is
observed that GSN-IAS and LightGCN-IAS achieve comparable performance and are
better than the other two, which validates our motivation of designing GSN
without trainable parameters for ID-based item embedding learning in the SBR
task. In addition, the GAT-IAS achieves better performance than that of GCN-
IAS, which implies that learning aggregation weights based on node embedding
is better than computing on graph adjacent matrix. Although the performance of
our GSN is comparable to LightGCN, our GSN provides a new idea using a more
simple, convenient and effective way to learn node embedding on a graph
without using any additional parameters.

Figure 4: The performance of GSN-Anchor for using different numbers of
selected anchors.

###  5.4 Visualization of item embedding

Fig. 3 presents the visualization of item embedding and item encoding in our
GSN-IAS by the t-sne [47] algorithm. We observe that the results are
consistent across different datasets. The original embeddings (the 1st column)
are randomly initialized without much differentiations. Contrastively, after
GSN learning for item embedding and after informative anchor selection for
item encoding, the item embeddings (the 2nd column) and item encodings (the
4th column) reflect obvious clustering effect, that is, the similar items are
closer to each other in the latent embedding space. To present the results
more intuitively, we employ KMeans (K=5) algorithm to cluster the item
embeddings (the 3rd column) and the item encodings (the 5th column). We can
observe that the clustering effect is more obvious. Such clustering effect
implies that both item embeddings and encodings can provide good item
differentiations. Previous experiment results also reflect that such item
differentiations can help to achieve more accurate recommendation.

TABLE VI: Performance of using different numbers of GSN layers.

Dataset | Yoochoose 1/64 | RetailRocket | Digineitca
---|---|---|---
Method | HR@20 | MRR@20 | HR@20 | MRR@20 | HR@20 | MRR@20
GSN-IAS-1hop | 72.23 | 31.38 | 56.32 | 29.79 | 54.93 | 19.14
GSN-IAS-2hop | 72.34 | 31.45 | 57.13 | 29.97 | 55.21 | 19.22
GSN-IAS-3hop | 72.42 | 31.11 | 57.00 | 29.66 | 55.53 | 19.18
GSN-IAS-4hop | 72.52 | 31.07 | 57.34 | 29.63 | 55.57 | 19.13
GSN-IAS-5hop | 72.46 | 31.03 | 57.59 | 29.42 | 55.65 | 19.24

###  5.5 Hyperparameter Analysis

We finally examine the two hyperparameters in our GSN-IAS: One is the number
of anchors, i.e. $M$; and the other is the number of stacked GSN layers, i.e
$L$.

Fig. 4 presents the performance of GSN-Anchor for using different numbers of
anchors. We observe that the trend of curve of HR@20 or MRR@20 on all the
three datasets are consistent, that is, increasing first, then maintaining
relatively stable, even decreasing slightly on RetailRocket with the increase
of $M$. These results first indicate that too few anchors carry insufficient
information; With increasing the number of anchors, the information provided
by anchors tend to be saturated; While too many anchors may introduce some
noise or repeated information to weaken the item differentiations.

Table VI presents the performance of using different layers of GSN. above
contrast experiments. We first note that even the GSN-IAS-1hop still
outperforms the state-of-the-art methods. With the increase of $L$, the HR@20
increases, but the growth rate slows down and even decreases on Yoochoose
1/64. The MRR@20 increases first and then decreases on Yoochoose 1/64 and
RetailRocket. These results are easy to understand: Using a lager $L$, higher-
order information of each node in the item graph can be explored, but more
high-order neighbors may blur a node’s information. The choice of $L$ is also
related to the dataset size. The Yoochoose 1/64 is smaller than RetailRocket
and Diginetica; So using a small $L$ suffices for Yoochoose 1/64. The
RetailRocket and Diginetica contain about 2.1 times and 2.5 times more items
than Yoochoose 1/64, needing a larger $L$ to explore more higher-order
neighbors.

##  6 Conclusion

In this paper, we have proposed a novel GSN-IAS model for the SBR task. Our
model explores item co-occurrence to construct an item graph, on which we
propose a new GSN neural network to optimize neighborhood affinity in ID-based
item embedding learning. We have also deigned an informative anchor selection
strategy to select anchors and to encode potential relations of all nodes to
such anchors. Furthermore, we have employed a shared GRU to learn two session
representations for two predictions. We have also proposed an adaptive
decision fusion mechanism to fuse the two predictions to output the final
recommendation list. Experiments on three public datasets have validated the
superiority of our GSN-IAS model over the state-of-the-art algorithms.

In this paper, we have especially discussed the characteristics of ID-based
item embedding learning for the SBR task. We note that our GSN model may not
only be suitable for such ID embedding learning in the SBR task, but may also
be of further applications in other scenarios, like collaborative filtering.
Our future work will explore the GSN potentials in other tasks. Furthermore,
we suggest to further mine and encode some latent transition knowledge such as
diverse transitional modes in between different kinds of items as another
interesting future work.

## References

  * [1] X. Su and T. M. Khoshgoftaar, “A survey of collaborative filtering techniques,” _Advances in artificial intelligence_ , vol. 2009, 2009.
  * [2] Y. Shi, M. Larson, and A. Hanjalic, “Collaborative filtering beyond the user-item matrix: A survey of the state of the art and future challenges,” _ACM Computing Surveys (CSUR)_ , vol. 47, no. 1, pp. 1–45, 2014.
  * [3] S. Zhang, L. Yao, A. Sun, and Y. Tay, “Deep learning based recommender system: A survey and new perspectives,” _ACM Computing Surveys (CSUR)_ , vol. 52, no. 1, pp. 1–38, 2019.
  * [4] S. Wang, L. Cao, and Y. Wang, “A survey on session-based recommender systems,” _arXiv preprint arXiv:1902.04864_ , 2019.
  * [5] J. Li, P. Ren, Z. Chen, Z. Ren, T. Lian, and J. Ma, “Neural attentive session-based recommendation,” in _Proceedings of the 2017 ACM on Conference on Information and Knowledge Management_ , 2017, pp. 1419–1428.
  * [6] Q. Liu, Y. Zeng, R. Mokhosi, and H. Zhang, “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_, 2018, pp. 1831–1839.
  * [7] S. Wu, Y. Tang, Y. Zhu, L. Wang, X. Xie, and T. Tan, “Session-based recommendation with graph neural networks,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 33, 2019, pp. 346–353.
  * [8] B. Sarwar, G. Karypis, J. Konstan, and J. Riedl, “Item-based collaborative filtering recommendation algorithms,” in _Proceedings of the 10th international conference on World Wide Web_ , 2001, pp. 285–295.
  * [9] S. Rendle, C. Freudenthaler, Z. Gantner, and L. Schmidt-Thieme, “Bpr: Bayesian personalized ranking from implicit feedback,” in _Proceedings of the twenty-fifth conference on uncertainty in artificial intelligence_ , ser. UAI’09. AUAI Press, 2009, pp. 452–461.
  * [10] M. Wang, P. Ren, L. Mei, Z. Chen, J. Ma, and M. de Rijke, “A collaborative session-based recommendation approach with parallel memory modules,” in _Proceedings of the 42nd International ACM SIGIR Conference on Research and Development in Information Retrieval_ , 2019, pp. 345–354.
  * [11] A. Luo, P. Zhao, Y. Liu, F. Zhuang, D. Wang, J. Xu, J. Fang, and V. S. Sheng, “Collaborative self-attention network for session-based recommendation.” in _IJCAI_ , 2020, pp. 2591–2597.
  * [12] B. Hidasi, A. Karatzoglou, L. Baltrunas, and D. Tikk, “Session-based recommendations with recurrent neural networks,” in _Proceedings of the 4th International Conference on Learning Representations_ , ser. ICLR ’16, 2016\.
  * [13] P. Ren, Z. Chen, J. Li, Z. Ren, J. Ma, and M. de Rijke, “Repeatnet: A repeat aware neural recommendation machine for session-based recommendation,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 33, 2019, pp. 4806–4813.
  * [14] C. Xu, P. Zhao, Y. Liu, V. S. Sheng, J. Xu, F. Zhuang, J. Fang, and X. Zhou, “Graph contextualized self-attention network for session-based recommendation.” in _IJCAI_ , vol. 19, 2019, pp. 3940–3946.
  * [15] X. Xia, H. Yin, J. Yu, Q. Wang, L. Cui, and X. Zhang, “Self-supervised hypergraph convolutional networks for session-based recommendation,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 35, 2021, pp. 4503–4511.
  * [16] R. Qiu, J. Li, Z. Huang, and H. Yin, “Rethinking the item order in session-based recommendation with graph neural networks,” in _Proceedings of the 28th ACM International Conference on Information and Knowledge Management_ , 2019, pp. 579–588.
  * [17] T. Chen and R. C.-W. Wong, “Handling information loss of graph neural networks for session-based recommendation,” in _Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, 2020, pp. 1172–1180.
  * [18] Z. Wang, W. Wei, G. Cong, X.-L. Li, X.-L. Mao, and M. Qiu, “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_ , 2020, pp. 169–178.
  * [19] Y. Zheng, S. Liu, Z. Li, and S. Wu, “Dgtn: Dual-channel graph transition network for session-based recommendation,” in _ICDMW_ , 2020.
  * [20] F. Yu, Y. Zhu, Q. Liu, S. Wu, L. Wang, and T. Tan, “Tagnn: Target attentive graph neural networks for session-based recommendation,” in _Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval_ , 2020, pp. 1921–1924.
  * [21] Z. Pan, F. Cai, W. Chen, H. Chen, and M. de Rijke, “Star graph neural networks for session-based recommendation,” in _Proceedings of the 29th ACM International Conference on Information & Knowledge Management_, 2020, pp. 1195–1204.
  * [22] T. N. Kipf and M. Welling, “Semi-supervised classification with graph convolutional networks,” _arXiv preprint arXiv:1609.02907_ , 2016.
  * [23] P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Lio, and Y. Bengio, “Graph attention networks,” in _Proceedings of the 6th International Conference on Learning Representations_ , ser. ICLR ’18, 2018.
  * [24] X. He, K. Deng, X. Wang, Y. Li, Y. Zhang, and M. Wang, “Lightgcn: Simplifying and powering graph convolution network for recommendation,” in _Proceedings of the 43rd International ACM SIGIR conference on research and development in Information Retrieval_ , 2020, pp. 639–648.
  * [25] G. Linden, B. Smith, and J. York, “Amazon. com recommendations: Item-to-item collaborative filtering,” _IEEE Internet computing_ , vol. 7, no. 1, pp. 76–80, 2003.
  * [26] G. Shani, D. Heckerman, and R. I. Brafman, “An mdp-based recommender system,” _Journal of Machine Learning Research_ , vol. 6, no. Sep, pp. 1265–1295, 2005\.
  * [27] S. Rendle, C. Freudenthaler, and L. Schmidt-Thieme, “Factorizing personalized markov chains for next-basket recommendation,” in _Proceedings of the 19th international conference on World wide web_ , 2010, pp. 811–820.
  * [28] A. Zimdars, D. M. Chickering, and C. Meek, “Using temporal data for making recommendations,” in _Proceedings of the Seventeenth conference on Uncertainty in artificial intelligence_ , ser. UAI’01. Morgan Kaufmann Publishers Inc., 2001, pp. 580–588.
  * [29] D. Jannach and M. Ludewig, “When recurrent neural networks meet the neighborhood for session-based recommendation,” in _Proceedings of the Eleventh ACM Conference on Recommender Systems_ , 2017, pp. 306–310.
  * [30] D. Garg, P. Gupta, P. Malhotra, L. Vig, and G. Shroff, “Sequence and time aware neighborhood for session-based recommendations: Stan,” in _Proceedings of the 42nd International ACM SIGIR Conference on Research and Development in Information Retrieval_ , 2019, pp. 1069–1072.
  * [31] Y. K. Tan, X. Xu, and Y. Liu, “Improved recurrent neural networks for session-based recommendations,” in _Proceedings of the 1st Workshop on Deep Learning for Recommender Systems_ , 2016, pp. 17–22.
  * [32] M. Quadrana, A. Karatzoglou, B. Hidasi, and P. Cremonesi, “Personalizing session-based recommendations with hierarchical recurrent neural networks,” in _Proceedings of the Eleventh ACM Conference on Recommender Systems_ , 2017, pp. 130–137.
  * [33] Z. Pan, F. Cai, Y. Ling, and M. de Rijke, “An intent-guided collaborative machine for session-based recommendation,” in _Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval_ , 2020, pp. 1833–1836.
  * [34] Z. Zhang and B. Wang, “Learning sequential and general interests via a joint neural model for session-based recommendation,” _Neurocomputing_ , vol. 415, pp. 165–173, 2020.
  * [35] W.-C. Kang and J. McAuley, “Self-attentive sequential recommendation,” in _2018 IEEE International Conference on Data Mining (ICDM)_. IEEE, 2018, pp. 197–206.
  * [36] F. Yuan, A. Karatzoglou, I. Arapakis, J. M. Jose, and X. He, “A simple convolutional generative network for next item recommendation,” in _Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining_ , 2019, pp. 582–590.
  * [37] J. Song, H. Shen, Z. Ou, J. Zhang, T. Xiao, and S. Liang, “Islf: Interest shift and latent factors combination model for session-based recommendation.” in _IJCAI_ , 2019, pp. 5765–5771.
  * [38] F. Zhou, Z. Wen, K. Zhang, G. Trajcevski, and T. Zhong, “Variational session-based recommendation using normalizing flows,” in _The World Wide Web Conference_ , 2019, pp. 3476–3475.
  * [39] Z. Pan, F. Cai, Y. Ling, and M. de Rijke, “Rethinking item importance in session-based recommendation,” in _Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval_ , 2020, pp. 1837–1840.
  * [40] J. Yuan, Z. Song, M. Sun, X. Wang, and W. X. Zhao, “Dual sparse attention network for session-based recommendation,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 35, no. 5, 2021, pp. 4635–4643.
  * [41] J. Cho, S. Kang, D. Hyun, and H. Yu, “Unsupervised proxy selection for session-based recommender systems,” in _Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval_ , 2021, pp. 327–336.
  * [42] X. Xia, H. Yin, J. Yu, Y. Shao, and L. Cui, “Self-supervised graph co-training for session-based recommendation,” in _Proceedings of the 30th ACM International Conference on Information & Knowledge Management_, 2021, pp. 2180–2190.
  * [43] Z. Zhang and B. Wang, “Fusion of latent categorical prediction and sequential prediction for session-based recommendation,” _Information Sciences_ , vol. 569, pp. 125–137, 2021.
  * [44] A. Li, Z. Cheng, F. Liu, Z. Gao, W. Guan, and Y. Peng, “Disentangled graph neural networks for session-based recommendation,” _arXiv preprint arXiv:2201.03482_ , 2022.
  * [45] Y. Li, D. Tarlow, M. Brockschmidt, and R. Zemel, “Gated graph sequence neural networks,” _arXiv preprint arXiv:1511.05493_ , 2015.
  * [46] J. Ma, P. Cui, K. Kuang, X. Wang, and W. Zhu, “Disentangled graph convolutional networks,” in _International Conference on Machine Learning_. PMLR, 2019, pp. 4212–4221.
  * [47] L. Van der Maaten and G. Hinton, “Visualizing data using t-sne.” _Journal of machine learning research_ , vol. 9, no. 11, 2008.

###  .1 A Proof of Convergence of GSN

We investigate whether the core operation of GSN can converge after a
sufficient number of iterations. We take an arbitrary node as example and
conduct convergence analysis under the EM algorithm framework. We prove that
the GSN iteration process is equivalent to an expectation-maximization (EM)
algorithm estimating parameter of the vMF distribution by maximizing the
likelihood probability $P(\mathbf{h}_{i}|\mathbf{c}_{i})$.

We first briefly review the EM algorithm to clarify our objective. The EM
algorithm is an iterative method to find the maximum likelihood estimates of
parameters for a statistical model depending on unobserved latent variables.
The EM iteration alternates between performing an expectation step (E-step) to
compute the expectation function of the log-likelihood, and a maximization
step (M-step) to find such parameters maximizing the expected log-likelihood
computed on the E-step. We can also derive the expectation function for our
task.

We assume that the parameter after $t$ iterations is $\mathbf{c}_{i}^{(t)}$,
and EM algorithm optimizes the new parameter estimate $\mathbf{c}_{i}$ to
increase the log-likelihood denoted as
$L(\mathbf{c}_{i})=\log(P(\mathbf{h}|\mathbf{c}_{i}))$, that is,
$L(\mathbf{c}_{i})>L(\mathbf{c}_{i}^{(t)})$. Let us consider the difference
between them:

$\displaystyle
L(\mathbf{c}_{i})-L(\mathbf{c}_{i}^{(t)})=\log\left(\sum_{\bm{\alpha}}P(\mathbf{h},\bm{\alpha}|\mathbf{c}_{i})\right)-\log
P(\mathbf{h}|\mathbf{c}_{i}^{(t)})$ (25)
$\displaystyle=\log\left(\sum_{\bm{\alpha}}P(\bm{\alpha}|\mathbf{h},\mathbf{c}_{i}^{(t)})\frac{P(\mathbf{h}|\bm{\alpha},\mathbf{c}_{i})P(\bm{\alpha}|\mathbf{c}_{i})}{P(\bm{\alpha}|\mathbf{h},\mathbf{c}_{i}^{(t)})}\right)-\log
P(\mathbf{h}|\mathbf{c}_{i}^{(t)})$
$\displaystyle\geq\sum_{\bm{\alpha}}P(\bm{\alpha}|\mathbf{h},\mathbf{c}_{i}^{(t)})\log\frac{P(\mathbf{h}|\bm{\alpha},\mathbf{c}_{i})P(\bm{\alpha}|\mathbf{c}_{i})}{P(\bm{\alpha}|\mathbf{h},\mathbf{c}_{i}^{(t)})}-\log
P(\mathbf{h}|\mathbf{c}_{i}^{(t)})$
$\displaystyle=\sum_{\bm{\alpha}}P(\bm{\alpha}|\mathbf{h},\mathbf{c}_{i}^{(t)})\log\frac{P(\mathbf{h}|\bm{\alpha},\mathbf{c}_{i})P(\bm{\alpha}|\mathbf{c}_{i})}{P(\bm{\alpha}|\mathbf{h},\mathbf{c}_{i}^{(t)})P(\mathbf{h}|\mathbf{c}_{i}^{(t)})}$

where $\bm{\alpha}$ are the latent variables. We let:

$\begin{split}&B(\mathbf{c}_{i},\mathbf{c}_{i}^{(t)})\triangleq
L(\mathbf{c}_{i}^{(t)})+\\\
&\sum_{\bm{\alpha}}P(\bm{\alpha}|\mathbf{h},\mathbf{c}_{i}^{(t)})\log\frac{P(\mathbf{h}|\bm{\alpha},\mathbf{c}_{i})P(\bm{\alpha}|\mathbf{c}_{i})}{P(\bm{\alpha}|\mathbf{h},\mathbf{c}_{i}^{(t)})P(\mathbf{h}|\mathbf{c}_{i}^{(t)})}\end{split}.$
(26)

So we have

$L(\mathbf{c}_{i})\geq B(\mathbf{c}_{i},\mathbf{c}_{i}^{(t)}).$ (27)

Obviously, $B(\mathbf{c}_{i},\mathbf{c}_{i}^{(t)})$ is a lower boundary of
$L(\mathbf{c}_{i})$, where
$L(\mathbf{c}_{i}^{(t)})=B(\mathbf{c}_{i}^{(t)},\mathbf{c}_{i}^{(t)})$. In
order for $L(\mathbf{c}_{i})$ to increase as much as possible, we choose
$\mathbf{c}_{i}^{(t+1)}$ to maximize $B(\mathbf{c}_{i},\mathbf{c}_{i}^{(t)})$
as follows:

$\displaystyle\mathbf{c}_{i}^{(t+1)}=\mathop{\arg\max}\limits_{\mathbf{c}_{i}}B(\mathbf{c}_{i},\mathbf{c}_{i}^{(t)})$
(29) $\displaystyle=$
$\displaystyle\mathop{\arg\max}\limits_{\mathbf{c}_{i}}(L(\mathbf{c}_{i}^{(t)})$
$\displaystyle\quad\quad+\sum_{\bm{\alpha}}P(\bm{\alpha}|\mathbf{h},\mathbf{c}_{i}^{(t)})\log\frac{P(\mathbf{h}|\bm{\alpha},\mathbf{c}_{i})P(\bm{\alpha}|\mathbf{c}_{i})}{P(\bm{\alpha}|\mathbf{h},\mathbf{c}_{i}^{(t)})P(\mathbf{h}|\mathbf{c}_{i}^{(t)})})$
$\displaystyle=$
$\displaystyle\mathop{\arg\max}\limits_{\mathbf{c}_{i}}(\sum_{\bm{\alpha}}P(\bm{\alpha}|\mathbf{h},\mathbf{c}_{i}^{(t)})\log(P(\mathbf{h}|\bm{\alpha},\mathbf{c}_{i})P(\bm{\alpha}|\mathbf{c}_{i})))$
(30) $\displaystyle=$
$\displaystyle\mathop{\arg\max}\limits_{\mathbf{c}_{i}}(\sum_{\bm{\alpha}}P(\bm{\alpha}|\mathbf{h},\mathbf{c}_{i}^{(t)})\log
P(\mathbf{h},\bm{\alpha}|\mathbf{c}_{i}))$ (31) $\displaystyle=$
$\displaystyle\mathop{\arg\max}\limits_{\mathbf{c}_{i}}\mathbb{E}_{\bm{\alpha}}[\log
P(\mathbf{h},\bm{\alpha}|\mathbf{c}_{i})|\mathbf{h},\mathbf{c}_{i}^{(t)}]$
(32)

The $Q$-function is defined as follows.

###### Definition 1

$\bm{Q}$-function is the expectation of the log-likelihood function $\log
P(\mathbf{h},\bm{\alpha}|\mathbf{c}_{i})$ with respect to the conditional
probability $P(\bm{\alpha}|\mathbf{h},\mathbf{c}_{i}^{(t)})$ of the unobserved
latent variable $\bm{\alpha}$ given observed data $\mathbf{h}$ and the current
parameter $\mathbf{c}_{i}^{(t)}$, that is,

$Q(\mathbf{c}_{i},\mathbf{c}_{i}^{(t)})=\mathbb{E}_{\bm{\alpha}}[\log
P(\mathbf{h},\bm{\alpha}|\mathbf{c}_{i})|\mathbf{h},\mathbf{c}_{i}^{(t)}].$
(33)

We can intuitively find that choosing parameter $\mathbf{c}_{i}$ to maximize
$Q(\mathbf{c}_{i},\mathbf{c}_{i}^{(t)})$ is equivalent to maximize
$B(\mathbf{c}_{i},\mathbf{c}_{i}^{(t)})$, which can increase the likelihood
$L(\mathbf{c}_{i})$. The $Q$-function is the core of EM algorithm, and the
E-step and M-step are as follows:

  * •

E-step: Compute the $Q$-function for the given current parameter
$\mathbf{c}_{i}^{(t)}$.

  * •

M-step: Find the parameter $\mathbf{c}_{i}$ to maximize the $Q$-function.

We leverage the convergence of EM algorithm to discuss the convergence of our
GSN core operation. According to the probability density function of vMF
distribution, we have

$\displaystyle
P(\mathbf{h}_{i}|\mathbf{c}_{i})\propto\exp(\mathbf{h}_{i}^{\mathsf{T}}\mathbf{c}_{i})$
(34) $\displaystyle
P(\mathbf{h}_{j},\alpha_{ij}|\mathbf{h}_{j})\propto\exp(\alpha_{ij}\mathbf{h}_{j}^{\mathsf{T}}\mathbf{c}_{i})$
(35)

where $\alpha_{ij}$ is the concentration parameter seen as a latent variable.
We can write the log-likelihood in $Q$-function as follows:

$\displaystyle\log
P(\mathbf{h},\bm{\alpha}|\mathbf{c}_{i})=\log(P(\mathbf{h}_{i}|\mathbf{c}_{i})\prod_{v_{j}\in\mathcal{N}_{i}}P(\mathbf{h}_{j},\alpha_{ij}|\mathbf{c}_{i}))$
(36) $\displaystyle\propto$
$\displaystyle\log(\exp(\mathbf{h}_{i}^{\mathsf{T}}\mathbf{c}_{i})\prod_{v_{j}\in\mathcal{N}_{i}}\exp(\alpha_{ij}\mathbf{h}_{j}^{\mathsf{T}}\mathbf{c}_{i}))$
$\displaystyle=$
$\displaystyle\log(\exp(\mathbf{h}_{i}^{\mathsf{T}}\mathbf{c}_{i}+\sum_{v_{j}\in\mathcal{N}_{i}}\alpha_{ij}\mathbf{h}_{j}^{\mathsf{T}}\mathbf{c}_{i}))$
(37) $\displaystyle=$
$\displaystyle\mathbf{h}_{i}^{\mathsf{T}}\mathbf{c}_{i}+\sum_{v_{j}\in\mathcal{N}_{i}}\alpha_{ij}\mathbf{h}_{j}^{\mathsf{T}}\mathbf{c}_{i}$
(38)

The $Q$-function can be written as:

$\displaystyle Q(\mathbf{c}_{i},\mathbf{c}_{i}^{(t)})$ $\displaystyle=$
$\displaystyle\mathbb{E}_{\bm{\alpha}}[\log
P(\mathbf{h},\bm{\alpha}|\mathbf{c}_{i})|\mathbf{h},\mathbf{c}_{i}^{(t)}]$
(39) $\displaystyle=$
$\displaystyle\mathbb{E}_{\bm{\alpha}}[(\mathbf{h}_{i}^{\mathsf{T}}\mathbf{c}_{i}+\sum_{v_{j}\in\mathcal{N}_{i}}\alpha_{ij}\mathbf{h}_{j}^{\mathsf{T}}\mathbf{c}_{i})|\mathbf{h},\mathbf{c}_{i}^{(t)}]$
(40) $\displaystyle=$
$\displaystyle\mathbf{h}_{i}^{\mathsf{T}}\mathbf{c}_{i}+\sum_{v_{j}\in\mathcal{N}_{i}}\mathbb{E}(\alpha_{ij}|\mathbf{h},\mathbf{c}_{i}^{(t)})\mathbf{h}_{j}^{\mathsf{T}}\mathbf{c}_{i}$
(41)

We are going to compute
$\mathbb{E}(\alpha_{ij}|\mathbf{h},\mathbf{c}_{i}^{(t)})$, denoted as
$\hat{\alpha}_{ij}$, which is the expectation of latent variable $\alpha_{ij}$
given the current parameter $\mathbf{c}_{i}^{(t)}$ and observed data
$\mathbf{h}$. Note that $\alpha_{ij}$ describes the concentration of
$\mathbf{h}_{j}$ around the $\mathbf{c}_{i}$. We compute it based on the dot-
product similarity and normalize it as a probability by the softmax function
as follows:

$\displaystyle\hat{\alpha}_{ij}$ $\displaystyle=$
$\displaystyle\mathbb{E}(\alpha_{ij}|\mathbf{h},\mathbf{c}_{i}^{(t)})$ (42)
$\displaystyle=$
$\displaystyle\frac{\exp(\mathbf{h}_{j}^{\mathsf{T}}\mathbf{c}_{i}^{(t)})}{\sum_{v_{j}\in\mathcal{N}_{i}}\exp(\mathbf{h}_{j}^{\mathsf{T}}\mathbf{c}_{i}^{(t)})}$
(43)

Then the $Q$-function is rewritten as

$Q(\mathbf{c}_{i},\mathbf{c}_{i}^{(t)})=\mathbf{h}_{i}^{\mathsf{T}}\mathbf{c}_{i}+\sum_{v_{j}\in\mathcal{N}_{i}}\hat{\alpha}_{ij}\mathbf{h}_{j}^{\mathsf{T}}\mathbf{c}_{i}.$
(44)

After the expectation
$\mathbb{E}(\alpha_{ij}|\mathbf{h},\mathbf{c}_{i}^{(t)})$ has obtained, the
$Q$-function is computed directly. This proves that the Eq. (2) is performing
the E-step.

After the E-step, we have obtained the expectation
$\hat{\alpha}_{ij}=\mathbb{E}(\alpha_{ij}|\mathbf{h},\mathbf{c}_{i}^{(t)})$,
and we would like to find parameter $\mathbf{c}_{i}$ to maximize
$Q(\mathbf{c}_{i},\mathbf{c}_{i}^{(t)})$, that is,

$\mathbf{c}_{i}^{(t+1)}=\mathop{\arg\max}\limits_{\mathbf{c}_{i}}Q(\mathbf{c}_{i},\mathbf{c}_{i}^{(t)}).$
(45)

Note that we use an $\mathsf{UN}(\cdot)$ function to constraint
$\mathbf{c}_{i}$, i.e. $\|\mathbf{c}_{i}\|_{2}=1$. This is actually a
constrained extreme-value problem, which can be formulated as follows:

$\displaystyle\mathop{\max}\limits_{\mathbf{c}_{i}}Q(\mathbf{c}_{i},\mathbf{c}_{i}^{(t)})=\mathbf{h}_{i}^{\mathsf{T}}\mathbf{c}_{i}+\sum_{v_{j}\in\mathcal{N}_{i}}\hat{\alpha}_{ij}\mathbf{h}_{j}^{\mathsf{T}}\mathbf{c}_{i}$
(46) $\displaystyle s.t.\quad\|\mathbf{c}_{i}\|_{2}^{2}-1=0$ (47)

We use the Lagrange multipliers to solve this problem. The Lagrangian function
can be written as follows:

$L(\mathbf{c}_{i},\lambda,\eta)=\mathbf{h}_{i}^{\mathsf{T}}\mathbf{c}_{i}+\sum_{v_{j}\in\mathcal{N}_{i}}\hat{\alpha}_{ij}\mathbf{h}_{j}^{\mathsf{T}}\mathbf{c}_{i}+\lambda(\|\mathbf{c}_{i}\|_{2}^{2}-1),$
(48)

where $\lambda$ is the Lagrange multiplier. We take the derivative of the
Lagrangian function with respect to $\mathbf{c}_{i}$ and $\lambda$,
respectively, hence getting the extreme-value:

$\displaystyle\frac{\partial
L}{\partial\mathbf{c}_{i}}=\mathbf{h}_{i}+\sum_{v_{j}\in\mathcal{N}_{i}}\hat{\alpha}_{ij}\mathbf{h}_{j}+2\lambda\mathbf{c}_{i}=0$
(49a) $\displaystyle\frac{\partial
L}{\partial\lambda}=\|\mathbf{c}_{i}\|_{2}^{2}-1=0$ (49b)

A solution to these equations is as follows:

$\displaystyle{c}_{i}=-\frac{1}{2\lambda}(\mathbf{h}_{i}+\sum_{v_{j}\in\mathcal{N}_{i}}\hat{\alpha}_{ij}\mathbf{h}_{j})$
(50a) $\displaystyle\lambda\neq 0$ (50b)

The above solution shows that every $\mathbf{c}_{i}$ that satisfies the
$\lambda\neq 0$ is an extreme point at which the $Q$-function takes an extreme
value. We set $\lambda=-\frac{1}{2}\neq 0$, and $\mathbf{c}_{i}$ is computed
by

$\mathbf{c}_{i}=\mathbf{h}_{i}+\sum_{v_{j}\in\mathcal{N}_{i}}\hat{\alpha}_{ij}\mathbf{h}_{j}$
(51)

This can directly prove that Eq. (3) is performing the M-step.

Let $\alpha_{ij}^{(t)}$ and $\mathbf{c}_{i}^{(t)}$ denote the result of the
$t$-th E-step and M-step, respectively. According to Eq. (25), we have

$L(\mathbf{c}_{i}^{(t-1)})=\log(P(\mathbf{h}|\mathbf{c}_{i}^{(t-1)}))\leq\log(P(\mathbf{h}|\mathbf{c}_{i}^{(t)}))=L(\mathbf{c}_{i}^{(t)})$
(52)

The likelihood $L(\mathbf{c}_{i})$ increases monotonically, and its upper-
bound is zero. Therefore, the GSN convergence follows the convergence of the
EM algorithm.

###  .2 Comparison with other graph neural networks

We compare our GSN with two commonly used GNNs, i.e. LightGCN [24] and GAT
[23].

The core operation of LightGCN can be formulated by

$\displaystyle\mathbf{H}^{(l+1)}$
$\displaystyle=\mathbf{D}^{-\frac{1}{2}}\mathbf{A}\mathbf{D}^{-\frac{1}{2}}\mathbf{H}^{(l)}$
(53) $\displaystyle\mathbf{h}_{i}^{(l+1)}$
$\displaystyle=\sum_{v_{j}\in\mathcal{N}_{i}}\frac{1}{\sqrt{|\mathcal{N}_{i}|}\sqrt{|\mathcal{N}_{j}|}}\mathbf{h}_{j}^{(l)}$
(54)

where Eq. (53) is the matrix form and Eq. (54) is the vector form, and
$\mathbf{L}=\mathbf{D}^{-\frac{1}{2}}\mathbf{A}\mathbf{D}^{-\frac{1}{2}}$ is
the Laplacian matrix of the graph, $\mathcal{N}_{j}$ is the neighbor set of
its neighbor node $v_{j}$. We can observe the commonalities and differences
between GSN and LightGCN as follows:

  * •

Commonalities: Both GSN and LightGCN do not involve a global transformation
kernel, as well as no extra trainable parameters, which can ensure the
training process only within the initial node embedding space.

  * •

Differences: The aggregation weights of LightGCN depends on numbers of one-
order and two-order neighbors. The aggregation weights of GSN are computed as
the embedding space similarities between a node and its neighbors.

The core operation of GAT can be formulated by:

$\displaystyle\gamma_{ij}=\frac{\exp\left({\Phi}(\mathbf{a}^{(l)\mathsf{T}}[\mathbf{W}^{(l)}\mathbf{h}_{i}^{(l)}||\mathbf{W}^{(l)}\mathbf{h}_{j}^{(l)}])\right)}{\sum_{v_{j}\in\mathcal{N}_{i}}\exp\left({\Phi}(\mathbf{a}^{(l)\mathsf{T}}[\mathbf{W}^{(l)}\mathbf{h}_{i}^{(l)}||\mathbf{W}^{(l)}\mathbf{h}_{j}^{(l)}])\right)}$
(55)
$\displaystyle\mathbf{h}_{i}^{(l+1)}=\sigma(\sum_{v_{j}\in\mathcal{N}_{i}}\gamma_{ij}\mathbf{W}^{(l)}\mathbf{h}_{j}^{(l)})$
(56)

where $\Phi$ is an activation function, say for example the LeakyReLU
function, $\mathbf{W}^{(l)},\mathbf{a}^{(l)}$ are the trainable parameters of
the $l$-th GAT layer. We can observe the commonalities and differences between
GSN and GAT as follows:

  * •

Commonalities: Both GSN and GAT compute the aggregation weights based on nodes
embeddings.

  * •

Differences: The GAT designs an attention function with some trainable
parameters to compute the aggregation weights only once. Our GSN estimates the
aggregation weights iteratively without additional trainable parameters. The
iteration process aims at finding a local optimal aggregation weight for a
node based on its neighbors’ current embeddings.

We next conduct complexity analysis. We compare the space complexity and time
complexity of GSN with LightGCN. To facilitate subsequent analysis, we
summarize the graph statistics used in this paper in Table I.

Space Complexity Analysis:

For GSN, we only store the neighbors information of each node and the node
embedding matrix $\mathbf{H}\in\mathbb{R}^{N\times d}$. We leverage the
neighbor sampling for each node to sample only a subset of its neighbors based
on the edge weights. The space complexity of one layer GSN is $O(Nd+Nr)$,
where $r$ is the number of sampled neighbors for each node.

For LightGCN, besides the node embedding matrix, LightGCN needs to store the
Laplacian matrix
$\mathbf{L}=\mathbf{D}^{-\frac{1}{2}}\mathbf{A}\mathbf{D}^{-\frac{1}{2}}\in\mathbb{R}^{N\times
N}$ of the graph. We can use the sparse matrix storage method coordinate
format to store the Laplacian matrix, which only stores the non-zero elements.
The space complexity of LightGCN is $O(Nd+2|E|)$, where $|E|$ is the number of
edges in the graph.

In this paper, we set $r=12$ for the three datasets, so
$Nr=\\{208,512;443,616;517,164\\}$ are slightly less than $2|E|$, yet they are
with the same magnitude order. As such, the space complexity of GSN is on par
with the LightGCN.

Time Complexity Analysis:

For GSN, the core operations can be computed parallelly for all nodes. The
time complexity of one layer GSN is $O(TNrd)$, where $T$ is the number of
iterations, $N$ is the number of nodes in the graph, $d$ is the dimension of
the node embedding. In general, the number of nodes in a graph is large, but
$T,r$ are two small constants, that is, $N\gg r,N\gg T$. The time complexity
can be reduced to $O(Nd)$.

For LightGCN, it only computes the matrix multiplication between Laplacian
matrix and feature matrix. Obviously, its time complexity is $O(|E|d)$.
Therefore, the time complexity of GSN and LightGCN depends on the number of
nodes and the number of edges in a graph, respectively.

In this paper, from Table I, we can observe that the number of nodes is less
than the edges, but they are still on the same magnitude order. As such, the
time complexity of our GSN is on par with the LightGCN.