\section{Introduction}

Recommender systems aim to provide users with the most relevant information or product
, with which they are likely to interact. Providing such information helps users quickly navigate and filter out irrelevant information from the plethora of data available online nowadays. As such, recommender systems have become indispensable components of online platforms, such as e-commerce, movie streaming and news websites, to drive user engagement and interactions.

Building recommender systems has been a very active research topic for years, resulting in a great number of methods proposed in the literature. Among them, collaborative filtering (CF) methods are arguably the most popular ones due to favorable performance compared to other methods~\cite{cfdos}. CF methods leverage collective user-item interactions and build models to predict the likelihood of unobserved interactions. For instance, models that follow the matrix-factorization (MF) approach --a very common CF approach-- learn users' and items' latent representation vectors (also referred to as \textit{latent embeddings or states}) by factorizing data matrices which contain historical interactions. Unknown user-item interaction scores are then calculated by taking the dot product of the corresponding representation vectors. These vectors, or embeddings, are often interpreted as encoding preferences of users and characteristics of items.

Despite being widely-adopted, traditional CF methods focus mainly on \textit{static settings}, where user preferences and other factors such as social trends around items, are \textit{assumed to be stationary}. In real application settings, however, such assumption seldom holds~\cite{rrn2019}. Recently, numerous works have focused on modeling the temporal dynamics in recommender systems~\cite{deng2018,Koren2010,song}. They are referred to as time-aware or
temporal collaborative filtering (TCF) methods~\cite{tcf,Liu2013,timereview}. TCF methods often employ recurrent neural networks (RNNs) to model the temporal trajectories of user embeddings~\cite{song,fusion}, or of both user and item embeddings ~\cite{rrn2019,deng2018,ntf}. They have achieved higher performance over non-temporal counterparts in predicting future ratings~\cite{rrn2019,Koren2010,Liu2013}.

A limitation of existing TCF methods is that they often rely
on linear MF models to individually learn users' and items' embeddings,  neglecting the fact that correlations amongst users and items are effective hints in modeling their latent representations. In contrast, recent studies on static
CF have shown the benefits of modeling user-item
interactions in forms of graphs and of using graph neural
networks (GNNs) to learn representations over linear models~\cite{Rianne2017,bnp}.
Motivated by this, we aim to leverage GNNs in the context of \textit{temporal} CF. To this end, we propose a method that (\textit{i}) employs a graph-based CF model, namely the Graph Convolutional Matrix Completion (GCMC) model~\cite{Rianne2017}, to effectively learn user and item embeddings and (\textit{ii}) models the temporal trajectories of these embeddings using RNNs. The RNNs, after training, can propagate the latent embeddings to a future time step. These latent states are then used to predict potential user-item interactions. An inherent challenge with this method in the temporal CF setting lies in the increased data sparsity. To overcome the challenge of efficiently learning the embeddings from highly sparse data, we propose to use the historical user-item interactions, accumulated over time. Our experimental results show systematic performance improvement obtained with this approach.

To summarize, our contributions in the paper are two-fold:
\begin{itemize}
    \item We propose a method, coined Time-aware Graph-based Matrix Completion (TG-MC), which leverages the state-of-the-art graph-based CF model with RNNs for collaborative filtering. To the best of our knowledge, we are the first to leverage the graph-based CF approach for TCF.
    \item We present comprehensive experiments on large-scale real-world data to assess the effectiveness of our method in comparison with the state of the art.
\end{itemize}

The remainder of the paper is organized as follows: Section II reviews the related work, Section III presents our method in detail. Section IV describes the experimental settings and results while Section V concludes the paper.

\section{Related Work}

Our work lies in the intersection between the temporal collaborative filtering (TCF) and the graph-based collaborative filtering literature. In this section, we review these two areas and show the differences between our method and existing ones in each corresponding area.

\subsection{Temporal Collaborative Filtering \label{sec:tars}}

Existing TCF methods focus on the temporal aspects of only users, of users and items, or of their interactions, e.g., rating scores.
In this section, existing studies are grouped based on how they model users' preferences and items' social perception. Throughout the paper, the opinion that a social environment has of a product will be referred as \textit{item (social) perception
.

A number of works consider items' social perception as stationary and model users' preferences as evolving over time~\cite{fusion}.
For instance, \cite{fusion} uses random walks to independently learn short- and long-term user preferences.

Nevertheless, most TCF methods in the literature assume that \textit{both} items' perception and users' preferences may evolve over time~\cite{rrn2019,deng2018,Koren2010}. They either (a) model users' and items' latent states by means of temporal MF~\cite{rrn2019,deng2018} or (b) infer rating scores by modeling users' and items' dynamics by means of baseline predictors~\cite{Koren2010}. While~\cite{Koren2010} and \cite{Liu2013} obtain time-stamped latent states by following a MF approach,~\cite{rrn2019} uses Long-Short Term Memory (LSTM) units~\cite{lstm} to learn time-varying functions, thus reconstructing the dynamics of the evolution rather than the latent states.

The previous studies propose methods that learn the evolution of users' preferences and items' perceptions using independent RNNs. Alternatively, other papers define baseline functions which only depend on previous rating scores and incorporate time-decay functions to penalize older ratings~\cite{twcf} or emphasize relevant periods like seasons or week-ends~\cite{rel2}.

Unlike the TCF techniques presented above, which employ baseline functions or MF methodologies, our method models the user-item interactions by means of graph-based techniques, that is, GNNs. Our target is to effectively learn the latent embeddings with these novel neural networks which allow for a more precise study of the interactions and an increase in computational complexity.

\subsection{Graph-based Collaborative Filtering \label{sec:link}}
Link prediction refers to the task of anticipating whether an edge should be created between two nodes. Recommender systems can be formulated as a link prediction problem by representing users, items and their interactions in a bipartite graph. One of the first papers that proposed this methodology was \cite{linkpred} who introduced novel linkage functions as measure for inferring the rating scores in the model. Since then, various methods have followed proposed by \cite{Rianne2017,bnp,convRS,Huang17,Wang2019}.

Although MF is arguably the most commonly employed approach for recommender systems, recent studies have also leveraged CNNs and GNNs with favorable outcomes.
Mainly thanks to the development of CNNs and GNNs in recent years, interpreting recommender systems as a link prediction problem has received a boost in attention, leading to performance improvements. Namely, the methods by~\cite{Rianne2017,bnp,Wang2019} outperform non-graph CF papers by incorporating GNNs, whereas \cite{convRS} addresses the problem similarly using CNNs. In effect, these papers leverage the graph structure of the data and employ neural networks in the extraction of the latent embeddings of users and items. Differently, \cite{Huang17} proposed to leverage signal processing  concepts such as as graph frequency and graph filters to address the problem.

The approaches reviewed in this subsection focus on the static CF problem and ignore the dynamics behind users' opinions and social trends. In this work, we attempt to combine graph-based and time-dependant techniques with the aim of learning user and item latent embeddings and their dynamics.

\section{The Proposed Method}
\begin{figure*}[h]
  \centering
  \includegraphics[scale=0.5]{archit2.pdf}
  \caption{The proposed time-aware graph-based matrix completion architecture for Recommender Systems (TG-MC). \textbf{(a)} The model receives as input a sparse tensor of ratings R$\in {\rm I\!R}^{N_U \times N_V \times T}$ in three dimensions (users, items and time). The empty elements of R represent unknown rating scores from a user to a specific item. \textbf{(b)} The encoder is formed by combining GNNs and fully-connected layers. Running the encoder step for each time window results in two length-T sequences of latent representations for users and items. \textbf{(c)} The predictive step encompasses an RNN-, LSTM- or GRU-based architecture. Given the two sequences of users and items embeddings, two RNN models, which we refer to as user- and item-RNNs, predict the subsequent embeddings. The two RNNs can share weights or can be completely independent. \textbf{(d)} By matrix multiplication, the decoder step obtains, at the subsequent time instance, the output matrix $\hat{R}_{T+1}$ which contains the predicted ratings scores.
}
  \label{fig:model}
\end{figure*}
In this work, we follow the TCF approach for recommender systems and consider the time information associated to the user-item interactions. Concretely, we group the observed interactions by the time they occur, resulting in a \textit{sequence of $T$ non-overlapping interaction matrices} $\{R_{1}, \ldots, R_{T} \}$. This is in contrast to the setting in static CF methods, where all the observed interactions are processed at once in a single data matrix. A time step $t$ in our setting is associated to a matrix $R_t$ which contains interactions occurring between $t-\delta/2$ and $t+\delta/2$ with $\delta$ the time window's length. $T$ is hence determined by the total time span of the data (between the first and the last observed interactions) and $\delta$.

To learn from the sequence of interaction matrices, we propose a method, coined Time-aware Graph-based Matrix Completion (TG-MC), which leverages a graph-based CF approach and temporal prediction techniques. The schema of our method is illustrated in Figure~\ref{fig:model}. During training, our method follows a two-stage pipeline. The first stage involves learning latent embeddings representing users and items using the GCMC model~\cite{Rianne2017}. This step is performed \textit{independently} for each interaction matrix $R_t$ with $t = 1\dots T$, resulting in two length-$T$-sequences of latent embeddings for the users and the items. At each time step, a bi-linear decoder is trained together with the GCMC model as in~\cite{Rianne2017}. In the second stage, we fit two RNNs on the sequences of user and item representations to model their temporal trajectories. During testing, these RNNs are used to propagate the user and item representation vectors to a future time instance, from which user-item interaction scores can be computed using the bi-linear decoder trained in the first stage. Next, we present the steps involved in our method in  detail.
\subsection{Learning Users and Items Latent Embeddings with a Graph-based Model}
\label{sec:user_item_factor_gnn}
\subsubsection{Modeling Users and Items}
Following~\cite{Rianne2017}, we represent the rating matrices in the form of graphs. Concretely, the interaction matrix $R_t$ is represented as a bipartite graph $\mathcal{G}_t$ where a node corresponds to either a user or an item, and an edge encodes a rating a user has given to an item. The aim of this step is to learn the latent representations associated to each user or item node. The latent embedding of the node $i$ at time $t$ is denoted with the vector $z_{i,t} \in {\rm I\!R}^{d \times 1}$, where $d$ is the dimension of the latent representation.

Independently of the node type (item or user), a latent node embedding $z_{i,t}$ is learned by the following two steps. First, a vector $h_{i,t}$ is computed by accumulating all incoming links of node $i$ (i.e. $j \rightarrow i$, $\forall j$ connected to $i$) in graph $\mathcal{G}_t$
\begin{equation}
    h_{i,t}=\sigma\left[ \text{accum}\left(\sum_{j\in N_{i,1}}  \mu_{j \rightarrow i,1,t} , ... , \sum_{j \in N_{i,R}}   \mu_{j \rightarrow i,R,t} \right) \right],
    \label{eq:acc}
\end{equation}
where $\sigma[\cdot]$ is the activation function and $N_{i,r}$ is the set of nodes with linked interactions to user (or item) $i$ with rating score $r \in \{1,\ldots, R\}$ and $\text{accum}(\cdot)$ is an accumulation function, e.g., concatenation or element-wise addition.
Each incoming link to node $i$ is a user-item interaction and contributes by
\begin{equation}
    \mu_{j \rightarrow i,r,t}=\frac{1}{c_{i,j,t}}W_{r,t} x_{j,t}.
    \label{eq:mpass}
\end{equation}
Here, $W_{r,t} \in {\rm I\!R}^{H \times N_U}$ are learnable weights. $N_U$ (or $N_V$) and $H$ are, respectively, the input size and the hidden dimension size, $x_{j,t}$ is the initial feature vector of item-node $j$ at time $t$, and $c_{i,j,t}$ is the normalization factor.

In the second step, the latent vector $z_{i,t}$ is computed by
\begin{equation}
    z_{i,t}=\sigma \left( W_t  h_{i,t}\right),
    \label{eq:latrep}
\end{equation}
where each weight matrix $W_t \in {\rm I\!R}^{d \times H}$ is learned from the available training data at time $t$. Depending on the node type (i.e., whether it represents a user or an item), we consider the learned representation $z_{i,t}$ as a user or an item vector, denoted as $u_{i,t}$ and $v_{j,t}$ respectively.

\begin{table*}[t]
\vspace{1cm}
\caption{Average test RMSE and MAE scores for all variations of our method on the Netflix and MovieLens 1M datasets.}
\centering
\begin{tabular}{cc|cc|cc}
\hline
  &                 & \multicolumn{2}{c}{\textbf{Non-Accumulative Representation}} & \multicolumn{2}{|c}{\textbf{Accumulative Representation}} \\
\cline{3-6}
\textbf{Dataset}               & \textbf{Method} & RMSE              & MAE              & RMSE             & MAE            \\
\hline
\hline
\multirow{3}{*}{Netflix} & TG-MC RNN  & $1.008\pm$ 0.085 & 0.921$\pm$0.040&  $1.001\pm0.033$&$0.822\pm0.022$   \\
  & TG-MC GRU       &   0.969 $\pm$ 0.034 &  0.876 $\pm$ 0.037 & $0.952\pm 0.023$  & \textbf{0.767$\pm$0.029}  \\
  & TG-MC LSTM      &     0.974 $\pm$ 0.028 & 0.918 $\pm$ 0.017 & \textbf{0.931$\pm $0.009} & 0.790$\pm $0.020   \\
\hline
\multirow{3}{*}{MovieLens 1M} & TG-MC RNN      &  1.032$\pm$ 0.030 & 0.830$\pm$0.027 & 0.876 $\pm$ 0.023 & 0.783 $\pm$ 0.027  \\
                               & TG-MC GRU     &  1.019$\pm$0.028  &  0.818$\pm$ 0.028 & 0.867 $\pm$  0.013 & 0.697 $\pm$ 0.023 \\
                               & TG-MC LSTM     & 1.015 $\pm$ 0.022 & 0.768$\pm$ 0.026  & \textbf{0.834 $\pm$ 0.011} & \textbf{0.664 $\pm$ 0.028}\\
\hline
\end{tabular}
\label{table:variations}
\end{table*}

\begin{table*}[t]
\caption{RMSE scores obtained by our method and reference methods on the Netflix and MovieLens 1M datasets.}
\centering
\begin{tabular}{c|cccc}
\hline
\textbf{Method }&\textbf{ Netflix}& \textbf{MovieLens 1M}\\
\hline
\hline
PMF \cite{pmf}& 0.957  & 0.883   \\
I-AutoRec \cite{autorec} & 0.979  & \textbf{0.833} \\
U-AutoRec \cite{autorec} & 0.985 &  0.877  \\
GCMC \cite{Rianne2017} & 1.264&  1.001   \\
TG-MC (ours) & \textbf{0.931} & 0.834\\
\hline
\end{tabular}
\label{table:indep}
\end{table*}

\subsubsection{Bi-linear Decoder}
Following the GCMC model~\cite{Rianne2017}, for each time window, we compute the user-item interaction scores from the learned user and item embeddings using a bi-linear decoder. In this work, as we consider ratings (e.g., one- to five-score rating) as the interaction type, the prediction of rating values can be treated as a classification problem. We calculate the probability of rating $R_{i,j,t}$ (user $i$ rate item $j$ at time $t$) to have value $r$ according to
\begin{equation}
P (R_{i,j,t}=r)= \frac{\exp (u_{i,t}^T Q_{r,t} v_{j,t})}{\sum_{s \in \mathcal{R}} \exp (u_{i,t}^T Q_{s,t} v_{j,t})} \text{,}
    \label{eq:prob}
\end{equation}
with $u_{i,t}$, $v_{j,t}$ the embeddings of user $i$ and item $j$ at time $t$ and $Q_{r,t} \in {\rm I\!R}^{d \times d}, \forall r=\{1,\ldots,R\}$ the learnable parameters of the bi-linear decoder at time $t$.

We jointly train the parameters of the bi-linear decoder ($Q_{r,t} \in {\rm I\!R}^{d \times d}, \forall r=\{1,\ldots,R\}$) and those of the graph-based user and item modelling ($W$), separately \textit{at each time window $t$}, by minimizing the negative log-likelihood objective function,
\begin{equation}
    \mathcal{L}_{graph} = - \sum_{i,j \in \Omega_{t}} \log P(R_{i,j,t} = r),
    \label{eq:loss1}
\end{equation}
with $\Omega_{t}$ the set of ratings available for training at time $t$, and $r$ is the ground-truth rating that user $i$ gives to item $j$.
\subsubsection{Handling Data Sparsity}
CF methods generally suffer from the data sparsity problem, i.e., the number of observed user-item interactions is scant compared to the total possible number of such interactions.
In our case, this problem aggravates because the number of observed ratings is distributed with respect to their time instanc
: if the range of observed interactions is uniformly distributed across time, the density of $R_t$ is on average $\rfrac{1}{T}$ that of $R$.

To mitigate this problem when building $R_t$, rather than only using the interactions observed within $t$, we also include the interactions accumulated from previous time steps $\{1,\dots,t-1\}$. Following this approach, the density of the rating matrix increases through time, i.e., $|\Omega_{t+1}| > |\Omega_t|, \forall t \in \{1,\dots,T-1\}$, which helps ease the learning of the GCMC model. In Section IV, we will compare the efficiency of this variance (accumulative representation) against the non-accumulative representation.

\subsection{Modeling Users' and Items' Dynamics}
By learning user and item embeddings for each time window~$t$, with $t \in \{1,\dots,T\}$,  we obtain two length-$T$ sequences of embeddings, one for the users and the other for the items. We denote these two sequences, respectively, by $U_t$ and $V_t$ with $t \in \{1, \dots, T\}$. We have $U_t \in  {\rm I\!R}^{N_U \times d}$, $V_t \in  {\rm I\!R}^{N_V \times d}$ where $N_U,N_V$ are the number of users and items.

We employ two RNNs to model the temporal information in these sequences of embeddings, one for the users and one for the items, which we refer to as the user-RNN and item-RNN, respectively. This is motivated by the success of RNN and its variants in learning and predicting sequential data~\cite{sutskever2014}. As we unify the dimensions of the user and item embeddings (both equal to $d$), we can have the user-RNN and item-RNN either sharing weights or operating separately. In Section IV, we will compare the results obtained with these two variants.

Using RNNs, we predict the embeddings at a time step $T+1$ from the embeddings of the previous $T$ time steps (from $t=1$ to $T$). By re-iterating this process, we can further infer the embeddings at later time steps, e.g., $T+2$ and $T+3$ and so on. Formally, considering the user embeddings, we have:
\begin{equation}
    \widehat{U}_{T+1}= f_{\text{RNN}}(U_1, \ldots, U_T), \\
  \label{eq:predrnn}
\end{equation}
with $\widehat{U}_{T+1}$ the predicted embeddings at time $T+1$ and $f_{\text{RNN}}(\cdot)$ the function implemented by the user-RNN.
The item embeddings at each time window can be predicted in the same way using the item-RNN whose operation is referred as $g_{\text{RNN}}$.

We employ the mean-squared-error (MSE) loss function to train the user- and item-RNNs. Concerning the user-RNN, at time step $t$, the MSE is calculated between the predicted embedding $\widehat{U}_t$ produced by applying the model on the sequence of prior embeddings, $\widehat{U}_1, \dots, \widehat{U}_{t-1}$, and the embedding produced by the GCMC model at time $t$, namely, $U_t$, as illustrated in Eq. (\ref{eq:loss2}).

\begin{equation}
    \mathcal{L}_{\text{user-RNN}} =\dfrac{1}{N}{\sum_{i=1}^{N} \Vert \widehat{U}_i-U_i \Vert_{F}^2},
    \label{eq:loss2}
\end{equation}
with $\Vert . \Vert_{F}$ the Frobenious norm. The loss function used to train the item-RNN is calculated analogously using the item embeddings.
\subsection{Predicting entry values at future time instances}
Using the trained user-RNN and item-RNN models as presented above, we can predict the user and item embeddings at any future time step. Following the same setting, we employ the $T$ bi-linear decoders learnt at time steps $t=\{1,\ldots, T\}$ and a LSTM-based RNN architecture to predict the bi-linear decoder weights at $t=T+1$. The selected loss function is MSE as illustrated in Eq. (\ref{eq:loss2}). With this, we are able to predict the user-item interaction probabilities at $t=T+1$.
Concretely, consider the time instance $T+1$, the predicted probability for rating $R_{i,j,T+1}$ to have value $r$ is calculated following Eq.~(\ref{eq:prob}), with the embeddings produced by the (user- and item-) RNNs at time $T+1$ and the bi-linear decoder produced by the RNN at time $T+1$. From the computed probabilities, we can produce the continuous-valued predictions according to:
\begin{equation}
    \widehat{R}_{i,j,t}=\sum_{r \in \mathcal{R}} r P (R_{i,j,t}=r)
    \label{eq:expect}
\end{equation}
where $\mathcal{R}=\{1,\ldots, R\}$ is the set of possible rating scores.
\section{Experiments}
In this section, we present our experimental study to assess the effectiveness of the proposed methods compared to the state of the art. We first describe the experimental settings and then report the obtained results.

\subsection{Experimental Settings}
We employ the Netflix and MovieLens datasets~\cite{Netflix,mldataset} in our experiments,  both widely used in recent literature \cite{rrn2019, Rianne2017, autorec, Alex2011} and with different characteristics regarding number of users, items and distribution of ratings. The Netflix dataset comprises a total of about 100M ratings, $480,189$ users and $17,770$ movies, whereas the MovieLens 1M (ML-1M) dataset has $6,040$ users, $3,900$ items and 1M observed ratings.

A data point (i.e. rating) of any of the two sets contains a movie and user identifier as well as the rating score and the time of the event. The Netflix timestamp is given as YYYY-MM-DD while the ML-1M is given as seconds since midnight Coordinated Universal Time (UTC) of January 1, 1970.

For the Netflix dataset, we follow the setup in~\cite{rrn2019} and consider a 6-month subset of the dataset (nearly 5M data points) with ratings occurring between July and December 2005. To respect causality considerations, ratings recorded in the month of December are kept for testing while those recorded between July and November are used for training. All the ratings are integer values in the range $[1-5]$. We split the data according to a time window of $1$ week. As the total time span of the data is $30$ weeks, we obtain $T=30$ interaction matrices, of which the first $26$ ones are used for training (3M ratings) and the rest are reserved for testing (1.8M ratings). This results in a train-test split of 62\%-38\%.

For the ML-1M dataset, we follow~\cite{Alex2011} and split the dataset according to a time window of 3 months. As the total time span of the data ranges from May 2000 to January 2003, we obtain $T=11$ time windows, where the first $9$ are used for training and the remaining are kept for testing,  resulting in a 99\%-1\% train-test split. Like on the Netflix dataset, the ratings are integers in the range $[1-5]$.

We compare the performance of our methods with that of state-of-the-art reference models, including non-temporal CF models such as the PMF~\cite{pmf}, Autorec~\cite{autorec} and GCMC models~\cite{Rianne2017} and temporal CF models~\cite{rrn2019,Koren2010,tcf,ntf,Alex2011,tmf,he2017neural,lfm}. The performance of the models are assessed using two metrics, namely, the root mean squared error (RMSE) and mean absolute error (MAE). For each model, we report the mean results obtained after five different runs employing the test and train sets explained above.

On the GCMC model \cite{Rianne2017}, the reported results are obtained by running their code on the whole matrix of ratings when $T=1$ with the best hyperparameters reported in their paper. Equivalently, reported results from \cite{rrn2019} on the Netflix dataset are collected from their papers. The temporal MF model from \cite{tmf} was re-implemented and run for the best parameters we found. We followed an equivalent process for \cite{tcf,autorec,he2017neural}.  Results on \cite{ntf,Alex2011,lfm} are taken from their paper since they follow the same experimental settings.

\begin{table*}[t]
\vspace{1cm}
    \caption{Comparison of our method and TCF methods on the Netflix and MovieLens datasets.}
    \begin{subtable}{.47\linewidth}
      \centering
        \caption{Average test RMSE scores for different TCF models on the Netflix Data Set.}

\begin{tabular}{ c| c}
\hline
\textbf{Method} & \textbf{RMSE} \\
\hline
\hline
Temporal MF \cite{tmf} & 1.112 \\
RRN \cite{rrn2019}  & 0.944 \\
TimeSVD++ \cite{Koren2010}& 0.962 \\
NCF \cite{he2017neural} & 0.947 \\
LFM \cite{lfm} & 0.936 \\
TG-MC (ours) & \textbf{0.931} \\
\hline
\end{tabular}

    \end{subtable}%
    \hspace{0.5cm}
    \begin{subtable}{.47\linewidth}
      \centering
        \caption{Average test MAE scores for different TCF models on the Movie-Lens 1M Data Set.}

\begin{tabular}{ c| c}
\hline
\textbf{Method}  & \textbf{MAE} \\
\hline
\hline
Temporal MF \cite{tmf} & 0.843\\
RRN \cite{rrn2019} & 0.793\\
AM$^{N=1}$ \cite{Alex2011} & 0.777\\
NTF \cite{ntf} &  0.689 \\
TG-MC (ours) & \textbf{0.664}\\
\hline
\end{tabular}

    \end{subtable}
    \label{table:all}
\end{table*}

\subsection{Hyperparameters Selection}
We empirically select the hyperparameters for the graph encoder, the user- and the item-RNNs.

\paragraph{The Graph-based Encoder} For this model, we employ a learning rate of $10^{-2}$, a dropout rate of $0.3$ and rectified linear unit (ReLU) as the activation function after both dense and GNN layers.

On the Netflix dataset, we performed grid search to select the best combination of the output dimensions of the GNN and dense layers ($H$ and $d$). We compared the results obtained by different combinations on a separate validation set containing $20\%$ of the known ratings in the training set at the last training time step. This procedure results in $H=500$ and $d=75$. For each time step, we train the corresponding graph-based encoder for $1,000$ epochs with a batch size of $100,000$ training ratings.
On the ML-1M dataset, we perform the same grid search procedure and accordingly set  $H=500$ and $d=50$. For each time step, we train the model for $2,500$ epochs with a batch size of $100,000$ training samples.

\paragraph{The user- and item-RNN models}
We experiment with different variants of RNNs to construct the user- and item- recurrent networks, including LSTM, GRU and vanilla RNN models, with one, two or three hidden layers. For each variant, we use the $\tanh$ activation function. As mentioned earlier, the weights between the user- and item- RNNs can be shared. For training, we employ the Adam optimizer with a learning rate of $10^{-2}$, running for $250$ epochs. Throughout our experimental study, we empirically observe that using LSTM models with two hidden layers give the best performance overall, and that sharing weights between the user- and item- recurrent models improves the performance. As such, we use this configuration when comparing our method to the reference models.
\subsection{Experimental Results}
\paragraph{Non-Accumulative versus Accumulative Representations}Table \ref{table:variations} compares the results obtained by our methods on the Netflix and ML-1M datasets when using the non-accumulative and accumulative data representations. Recall that with the former, only the ratings observed within a time window $t$ are used to learn the user and item embeddings ($U_t$ and  $V_t$ respectively), while with the latter, all ratings between the first and the $t-$th time windows are employed.

We can observe from the two tables that, given the same experimental conditions and independently of the employed dataset and RNN variant, the accumulative data representation yields better results in terms of RMSE and MAE. Furthermore, it is worth mentioning that more complex units like LSTMs and GRUs provide lower prediction errors than the vanilla RNN.

\paragraph{Comparison against Non-temporal CF models}
In this paper, we argue that (\textit{i}) learning user and item embeddings via GNNs and (\textit{ii}) modeling the temporal dynamics improve the performance of CF models. To confirm both points, we compare the performance of our method with that of both non-temporal and non-graph-based reference CF models.

Table~\ref{table:indep} shows the RMSE scores obtained by our method and \textit{non-temporal CF reference methods} on the Netflix and ML-1M datasets. As can be seen, our method yields the best performance on the Netflix dataset, followed by the PMF method. On the ML-1M dataset, the I-AutoRec model performs the best while our method has the second best performance. It should be noted that the performance difference between the two is relatively small (i.e., 0.001 point on RMSE on average), and that our method has lower MAE compared to the I-AutoRec model (0.664 versus 0.790, respectively).

Among the reference non-temporal models, the GCMC model~\cite{Rianne2017} employs graph neural network to learn the latent representations. In fact, this model can be seen as a special case of our method where the time span $\delta$ is defined so that all the known rating scores are enclosed in one matrix (i.e., $T=1$). However, directly applying the GCMC model on the TCF setting, where the training and testing sets are split according to the time stamps, results in poor performance on both the Netflix and ML-1M datasets, showing the benefits of modeling the temporal dynamics behind user and item embeddings in TCF.

\paragraph{Comparison with State-of-the-art TCF models}Table~\ref{table:all} compares the performance of our method and that of reference TCF methods on the Netflix and ML-1M datasets. For a fair comparison, we follow most recent TCF papers \cite{rrn2019,Koren2010,Liu2013} and report RMSE scores for the Netflix dataset, and MAE scores for the ML-1M dataset. It is worth re-calling that whenever applicable, we include the best scores reported in the corresponding papers in our comparison.
From the table, it is noted that our method yields the best performance on the Netflix dataset. The LFM model achieves the second best RMSE score, followed by the NCF model. On the ML-1M dataset, our method out-performs all reference TCF methods by large margins.

Among the reference TCF models, our method of modeling the temporal trajectories of user and item embeddings is similar that of the Temporal MF model~\cite{tmf}. The key difference is that we employ graph neural network to learn the embeddings at each time step, while the Temporal MF models follow a matrix-factorization approach. The results reported in Table~\ref{table:all} consistently show significant performance improvements obtained by the TG-MC model over the Temporal MF model. This justifies the benefits of using graph neural networks in our method.

\section{Conclusion}

In this paper, we have presented a method for temporal collaborative filtering (TCF), which combines graph neural network (GNN) and recurrent neural network (RNN) models to effectively (\textit{i}) learn the latent user and item representations, and (\textit{ii}) model the trajectories of these representations across time. To deal with the increased data sparsity in the TCF setting, we proposed to train the GNNs using an accumulative data representation technique.
Our comprehensive experiments on the Netflix and MovieLens 1M datasets justified the benefits of each of the proposed components, namely, the use of RNNs to model the temporal dynamics in the TCF settings, the use of GNNs to capture the latent representations of users and items and the benefits of training the models using accumulative data. The experimental results also showed that our method yielded favourable performance compared to several state-of-the-art TCF models.

\section*{Acknowledgement}
This research was supported by funding from the Flemish Government under the “Onderzoeksprogramma Artificiële Intelligentie (AI) Vlaanderen” programme.

\bibliographystyle{IEEEtran}


\section{Introduction}

Language is a constantly changing system by its nature, since it is a method of communication and a social instrument. As such, it should meet the needs of the speakers, and thus it adapts to changes in the society and the ever-changing  world. As a part of language, lexical meaning also evolves over time, with words undergoing diachronic (or temporal) semantic shifts \cite{traugott2001regularity}.

Tracing semantic change can be important either in itself, as a linguistic study, or for practical downstream applications, for example, in socio-linguistic research.  Manual analysis of such shifts is time-consuming and laborious even after the emergence of large representative corpora, since one needs to look through a lot of examples and lexicographic resources which often do not record current lexical changes in language due to limited resources. Thus, researchers are trying to model these processes using  advanced  computational  approaches often  based  on distributional semantics and dense word embeddings \cite{kutuzov:survey,tang_2018}.

However, this is still mostly done for English: often simply because manually annotated test data is not available for other languages. Recently, consistently annotated lexical semantic change test sets for multiple languages started to appear; see, for example, \newcite{schlechtweg2020semeval}. In this paper, we continue this vein of work by presenting \textit{RuSemShift}. \textit{RuSemShift}\footnote{\url{https://github.com/juliarodina/RuSemShift}} is the first historical semantic change dataset for Russian annotated according to the DURel framework \cite{durel} using a large crowd-sourcing platform, instead of personal intuitions of individual researchers. It allows to evaluate semantic change detection systems by their ability to estimate the shifts which occurred to Russian words either after 1917 (the fall of the Russian Empire) or after 1990 (the fall of the Soviet Union).

The rest of the paper is organized as follows: in Section~\ref{sec:background}, we put our research in the context of the related work. In Section~\ref{sec:data}, we present the employed corpora and the process of the dataset creation. Section~\ref{sec:annotation} describes the annotation itself. In Section~\ref{sec:evaluation}, we empirically evaluate several existing semantic change detection algorithms (based on static and contextualized embeddings) on \textit{RuSemShift} to check its sanity. Section~\ref{conclusion} summarizes our contributions and outlines future research.

\section{Related work}
\label{sec:background}

Works on language change from general linguistics like \newcite{traugott2001regularity} or \newcite{twentywords} as a rule contain only a small number of hand-picked examples. The \textit{DatSemShift} database \cite{zalizniak2018catalogue} features more than 4 000 semantic shifts across 800 languages. But it is focused on cognitive proximities between pairs of linguistic meanings (with a limited set of pre-defined senses): in this paradigm, a semantic shift is just a case of extended polysemy. The \textit{DatSemShift} database is extremely useful for identifying recurring cross-linguistic semantic shifts, but it is difficult to employ it for evaluation of unsupervised semantic change detection systems.

To our knowledge, the first Russian test set to evaluate lexical semantic change detection systems was created by \newcite{kutuzov-kuzmenko}. They used prior linguistic work to manually collect Russian words which changed their meaning from the pre-Soviet times through the Soviet times. \newcite{kutuzov-kuzmenko} also employed static word embedding models trained on the corresponding Russian diachronic corpora to detect semantic change for the words from the dataset (distinguishing changed words from stable ones). They concluded that Kendall’s $\tau$ \cite{kendall1948rank} and Jaccard similarity \cite{Jaccard:1901} between nearest neighbor lists worked best in this tasks. More recent work by \newcite{fomin} extended this research to more granular time bins (periods of 1 year): they analyzed sequential pairs of word embedding models trained on yearly corpora of Russian news from 2000 up to 2014. To evaluate their system, they created a test set which contained human judgements about how much the meaning of a word has shifted over the given years. Using this ground truth, \newcite{fomin} evaluated 5 algorithms for semantic change detection and provided solid foundation for future research in in this direction for Russian.

However, these datasets suffer from two serious issues. First, they are either produced by a single person \cite{kutuzov-kuzmenko} or annotated by the paper authors themselves \cite{fomin}. This makes them inherently subjective. Second, each of this datasets is created and annotated in a different manner, making them inconsistent and not comparable nor to themselves neither to similar efforts made for other languages. In addition, the test set from \cite{kutuzov-kuzmenko} features only binary labels (shifted or stable), making it useless for research in graded semantic change detection.

The \textit{RuSemShift} test set we present in this paper makes partial use of these existing test sets, but all the words are re-annotated from scratch. In \textit{RuSemShift}, we adhere to the language-agnostic \textit{Diachronic Usage Relatedness} (DURel) semantic change annotation methodology  proposed in \newcite{durel}. The intended use of the DURel framework is the creation of consistently and robustly annotated test sets containing words labeled with the degrees of their diachronic lexical semantic change. \newcite{durel} presented a test set for German annotated this way. In addition, English, German, Latin and Swedish test sets used in the SemEval-2020 shared task on unsupervised lexical semantic change detection \cite{schlechtweg2020semeval} were also created following the same approach. Thus, we deem  DURel to be the current de-facto standard for the annotation of semantic change datasets.

\begin{wrapfigure}{r}{0.4\textwidth}
\centering
\includegraphics[width=0.4\textwidth]{groups.png}
\caption{Number of \textit{sentence pairs} for each word from the time period $t1$ (EARLIER), the time period $t2$ (LATER) and from both periods (COMPARE).}
\label{fig:Groups}
\end{wrapfigure}
DURel employs the notion of usage relatedness borrowed from research  on word sense disambiguation task \cite{brown}. The idea is to measure the degree of semantic change as a function of mean relatedness across pairs of word’s occurrences in different time periods. The annotators are not required to know anything about diachronic change: they are presented with two sentences (both containing a target word) and asked to estimate how similar are the senses in which the target word is used. They should choose a score from the 4-point scale described below in Section~\ref{sec:annotation}.

A sample of target word usage pairs from the first time period $t_1$ form the so called EARLIER group and the usage pairs from later time period $t_2$ form the LATER group. To cover the cases that cannot be tracked by comparing mean relatedness of two time periods, \newcite{durel} directly compare the `old' and `new' meanings by creating the additional COMPARE group which contains pairs where the first sentences is from the $t_1$ time period and the second sentence is from the $t_2$ time period (see Figure~\ref{fig:Groups}). Each group contains 20 sentence pairs randomly sampled from the corresponding corpora. Target word’s \textit{w} degree of semantic change is quantified with two measures:

\begin{enumerate}
    \item $\Delta$LATER, which is the difference between mean relatedness of the EARLIER group and the LATER group:

    $\Delta LATER(w) = Mean_{LATER}(w) - Mean_{EARLIER}(w)$;
    \item COMPARE, which is the mean relatedness within the COMPARE group:

    $COMPARE(w) = Mean_{COMPARE}(w)$.
\end{enumerate}

Due to space limitations, it is impossible to provide a description of the advantages and disadvantages of these two measures here. We refer the reader to \newcite{durel} for the detailed discussion.

\section{Data Sources} \label{sec:data}
In this section, we describe our data sources. It can be looked at a sort of data statement \cite{bender-friedman-2018-data} for \textit{RuSemShift}. We first present the corpus we employ and its historical sub-corpora, and then move on to the process of preliminary target word selection. The data statement continues in the next Section~\ref{sec:annotation} with the description of our annotators and the annotation workflow in general.

\subsection{Corpora}
\textit{RuSemShift} covers 3 time periods of Russian language history, following \newcite{kutuzov-kuzmenko}:

\begin{enumerate}
  \item Texts produced from 1682 to 1916: the period of Russian monarchy before the revolution of 1917; further dubbed \textbf{pre-Soviet}.
  \item Texts produced from 1918 to 1990: the period of the existence of the Soviet Union; further dubbed \textbf{Soviet}.
  \item Texts produced from 1991 to 2017: the period after the fall of the Soviet Union: further dubbed \textbf{post-Soviet}.
\end{enumerate}

The wide coverage of these periods (several decades or even centuries each) makes it more likely that shifts in word usage will be caused by linguistic factors, and not only by extra-linguistic events. However, it is arguably still strongly influenced by cultural factors. The boundaries between time bins are related to rises and falls of political regimes, and some semantic shifts are inevitably related to that. Note that the first time period (the pre-Soviet times) is substantially longer temporally than the other two. This in theory can lead to multiple meaning shifts occurring \textit{within} this period. But this epoch is already the smallest in terms of corpus size (see below), so it was impossible to further divide it.

Our annotation framework requires diachronic corpora with Russian texts created in the time periods listed above. As a source of such texts, we used the \textit{Russian National Corpus} (RNC).\footnote{\url{http://ruscorpora.ru}}
RNC is well balanced and contains Russian texts of diverse genres produced from the middle of the 18th century up to the beginning of the 21st century. Note that the corpus itself is not our contribution: it is a prior work.

The main RNC corpus size is about 320 million word tokens (including punctuation). Since all the texts are annotated with the date of their creation, it is straightforward to separate the corpus into time-specific sub-corpora:

\begin{itemize}
  \item 94 million tokens in the pre-Soviet sub-corpus;
  \item 123 million tokens in the Soviet sub-corpus;
  \item 107 million tokens in the post-Soviet sub-corpus.
\end{itemize}

\subsection{Preliminary word lists}

To construct word lists for further annotation, we handpicked words that presumably have undergone semantic changes in the Soviet period compared to the pre-Soviet period or in the post-Soviet compared to the Soviet period. For each of these word lists we also randomly sampled a set of `filler' or `distractor' words, trying to reproduce the part of speech and frequency percentile distributions of the original target words as closely as possible. The purpose of fillers (which are assumed to be semantically stable) is to be able to evaluate the performance of semantic change detection systems in a more realistic setup: they are supposed to predict low change scores for fillers (or no change at all).

\subsubsection{Pre-Soviet to Soviet dataset ($RuSemShift_1$)}

The original target word list for the first pair of time bins was created in \newcite{kutuzov-kuzmenko}. It consists of 43 words that have undergone semantic changes through the period from the pre-Soviet to the Soviet times. The words were collected from general linguistic studies on lexical semantic change \cite{ozheg,twentywords};  there are 38 nouns and 5 adjectives. After the procedure of filler generation, the total number of words for annotation was 71. We emphasize again that only the changed word list was taken from  \newcite{kutuzov-kuzmenko}, the fillers and annotations were recreated from scratch by us.

\subsubsection{Soviet to Post-Soviet dataset ($RuSemShift_2$)}

The second test set is entirely our own contribution. It also contains manually chosen target words (35 nouns and 7 adjectives), primarily from the  \textit{`New Words and Meanings'} dictionary \cite{dic}. The dictionary includes words which acquired new common senses in Russian in the post-Soviet time period (such words have a special label in the dictionary). Note that these words are not neologisms: all of them occurred in the Soviet sub-corpus as well, so semantic change cannot be estimated by frequencies alone (as shown in Section~\ref{sec:evaluation}).
After the filler generation procedure, the test set consists of 69 words.

\section{Annotation} \label{sec:annotation}

The annotation procedure was carried out on the \textit{Yandex.Toloka}  crowd-sourcing platform\footnote{\url{https://toloka.yandex.ru/}}, which is more or less equivalent to the global Mechanical Turk or CrowdFlower platforms. Note that in the DURel dataset \cite{durel}, all five annotators were students of linguistics and two of them had historical background, which cannot be enforced when using crowd-sourcing platforms. However, \textit{Yandex.Toloka} allowed us to improve the quality of annotation by applying  various filters to limit who can annotate. We chose 10-30\% of the best annotators across the whole platform, keeping only native speakers of Russian, of the age 30 and more (to ensure them being familiar with older word senses) and possessing a university degree. We do not have any knowledge about the annotators' gender distribution.

The annotators who completed the tasks unrealistically fast were automatically filtered out. Furthermore, there were several \textit{control tasks}, consisting of sentence pairs manually annotated by ourselves (with the scores of 1 and 4 only, thus limited to obvious cases). The users who annotated such pairs incorrectly were blocked as well. Also, we accepted the judgments of an annotator only after checking some of them manually to make sure that the annotator had understood the task.

\begin{table}
\centering
\begin{tabular}{l l l}
\toprule
\textbf{Value} & \textbf{English judgments from \newcite{durel} } & \textbf{Judgments translated into Russian} \\
\midrule
0 & Cannot decide & \foreignlanguage{russian}{Не знаю}\\
1 & Unrelated & \foreignlanguage{russian}{Значения разные}\\
2 & Distantly Related & \foreignlanguage{russian}{Значения отдаленно похожи}\\
3 & Closely Related & \foreignlanguage{russian}{Очень похожие значения}\\
4 & Identical & \foreignlanguage{russian}{Употреблено в одном значении}\\
\bottomrule
\end{tabular}
\caption{Original 4-point scale from the DURel and its Russian translation used for the annotation.}
\label{tab:4pointscale}
\end{table}

For each word from our pre-constructed word lists, we extracted all unique sentence contexts from two corpora (\textit{pre-Soviet/Soviet} or \textit{Soviet/post-Soviet}) and randomly sampled 60 sentence pairs, 20 for each group (EARLIER, LATER and COMPARE). For the words that occurred less than 30 times in one of the corpora  we decreased the number of its sentence pairs to the closest value, divisible by 3 without a remainder. Final tables for the annotation contained $7846$ pairs for $71 + 69 = 140$ words. Each sentence pair was judged by not less than 5 annotators who used the scale presented in Table~\ref{tab:4pointscale}. The annotator interface of \textit{Yandex.Toloka} is shown in Figure~\ref{fig:Toloka}. For the cases when one sentence context was not enough to understand the meaning of the target word, we implemented an option to show extended contexts from the same corpora. Annotators were provided with detailed guidelines explaining the task and giving examples for each grade.

\begin{figure}[th]
\centering
\includegraphics[scale=0.5,keepaspectratio]{toloka.png}

\caption{Interface of the annotation task. In the first sentence, the word \foreignlanguage{russian}{`учреждение'} [uchrezhdenie] is used in the sense of \sense{decree, order}. In the second sentence, \foreignlanguage{russian}{`учреждение'} denotes \sense{institution}.}
\label{fig:Toloka}
\end{figure}

After all sentence pairs were annotated, we measured inter-rater agreement as Krippendorff’s $\alpha$ \cite{alpha} with ordinal scale, excluding 0 judgements (`cannot decide'). For $RuSemShift_1$, the agreement coefficient was 0.505, and for $RuSemShift_2$ its value was 0.53. Considering that the task is inherently ambiguous and complex, and also that all five annotators were different for each sentence pair, we believe this score is high enough. However, we also provide the filtered versions of both test sets, where controversial words that were annotated inconsistently (inter-rater agreement less than 0.2) are excluded. 24 words were filtered out from the $RuSemShift_1$ and 19 from the $RuSemShift_2$). We use these filtered test sets for evaluation in Section~\ref{sec:evaluation}.

\subsection{Analysis}

\begin{wrapfigure}{i}{0.6\textwidth}
\centering
\includegraphics[scale=0.3,keepaspectratio]{dataset2_delta.png}
\caption{Target words ($RuSemShift_2$) ranked by their $\Delta$LATER values.}
\label{fig:Delta}
\end{wrapfigure}
As stated in \newcite{durel}, both measures have their inherent limitations. $\Delta$LATER can fail to capture semantic change if a word loses an old sense and gains a new one within one time period. COMPARE tends to mix up polysemy with semantic change because of random choice of samples (can arguably be remedied using some kind of normalization). $\Delta$LATER naturally captures the differences between two types of meaning change: innovative shift (negative values) or reductive shift (positive values). But this is true only for high absolute $\Delta$LATER values. \newcite{durel} claim COMPARE to be more suitable for indicating the degree of semantic change, but prospective \textit{RuSemShift} users can choose any of these two measures or implement their own (since the raw annotation data is available).

Figure~\ref{fig:Delta} shows the words from the $RuSemShift_2$ ranked according to their $\Delta$LATER values. For most words, it is close to $0$ (no change), but one can also see groups with $\Delta LATER >> 0 $ and $\Delta LATER << 0$, indicating changes. Figure~\ref{fig:Distr} compares the distribution of annotators' judgments for two words with the highest and the lowest $\Delta$LATER values  (the adjective \foreignlanguage{russian}{`провальный'} [proval'nyj] `failed' and the noun \foreignlanguage{russian}{`инкубатор'} [inkubator] `incubator' correspondingly).

\begin{figure}
\begin{tabular}{ll}
\includegraphics[scale=0.5]{proval.png}
&
\includegraphics[scale=0.5]{incubator.png}
\end{tabular}
\caption{Distribution of human judgements for the $RuSemShift_2$ target words \foreignlanguage{russian}{`провальный'} `failed' (reductive change) and \foreignlanguage{russian}{`инкубатор'}  `incubator' (innovative change).}
\label{fig:Distr}
\end{figure}

For \foreignlanguage{russian}{`провальный'} (the $\Delta$LATER value of $1.78$), we can see that judgements are quite diverse in the EARLIER group and the 1-judgement (`unrelated senses') is prevalent, but in the LATER group, the 4-judgement (`identical senses') is considerably more frequent, while the COMPARE group also captures strong change, since the number of 1-judgements is higher than the number of 4-judgements. Almost all context pairs from the EARLIER group (that is, the Soviet time period) shown in Table~\ref{tab:proval_context} are related to the literal meaning of \foreignlanguage{russian}{`провал'}: \sense{a place where the surface collapsed inward} or the figurative sense of \sense{loss of consciousness} used frequently in the set expression \foreignlanguage{russian}{`провальный сон'} \textit{(`deep dream')}. In all the contexts from the LATER group (the post-Soviet time period), \foreignlanguage{russian}{`провальный'} is used in the sense of \sense{failed} which is more common in modern Russian. Thus, we can observe the expansion of this sense. As for the COMPARE group, sentences in pairs from each period support the same observation: there are only two usages from the earlier period that can be interpreted with the \sense{failed} sense. The word \foreignlanguage{russian}{`провальный'} did not lose its literal meaning, it just became much less frequent, and the old figurative meaning (as in \textit{`deep dream'}) is almost completely lost.\footnote{But is kept in the related word \foreignlanguage{russian}{`провал'} (\foreignlanguage{russian}{`провал в памяти'}/\textit{`lapse of memory'}).} Consequently, we can observe the word losing an old sense and gaining a new one at the same time.

\begin{table}
\small
\centering
\begin{tabular}{ l | p{6cm}| p{6cm} }
\toprule
\textbf{Group} & \textbf{Sentence 1} & \textbf{Sentence 2} \\
\midrule
EARLIER & \foreignlanguage{russian}{<...> выпили "микстуры" и спят где-нибудь сном провальным, пьяным <...>} \break \textit{‘<...> they drank a "potion" and sleeping somewhere in \textbf{deep} drunken \textbf{sleep} <...>’} \break \footnotesize{[Viktor Astaf'ev. Pechal'nyj detektiv (1982-1985)]} & \foreignlanguage{russian}{<...> Кщаре доходит до семидесяти пяти метров и что вообще здесь много провальных озер <...>} \break \textit{‘<...> Kshchare reaches seventy-five meters and in general there are many \textbf{deep lakes} <...>’} \break \footnotesize{[V. A. Solouhin. Vladimirskie prosyolki (1956-1957)]} \\
\midrule
LATER &
\foreignlanguage{russian}{<...> самые "бюджетные" программы оказываются самыми провальными в исполнении <...>} \break \textit{‘<...> the cheapest programs turn out to be the most \textbf{disastrous}<...>’} \break \footnotesize{[Ivan Golikov. Dohodnoe mesto // «Vsluh o…», 2003.05.19]}
& \foreignlanguage{russian}{<...> Подготовка к референдуму в Чечне до прошлой недели носила провальный характер <...>}  \break \textit{‘<...>Preparation for referendum in Chechnya until last week was \textbf{disastrous}<...>’} \break \footnotesize{[Aleksej Makarkin. Krizisnoe upravlenie «chechenizaciej» // «POLITKOM.RU», 2003.03.03]} \\
\midrule
COMPARE &
\foreignlanguage{russian}{<...> Наденька на минутку забылась провальным сном и когда открыла глаза <...>} \break \textit{‘<..> Nadenka \textbf{fainted} for a minute and when she opened her eyes <..>’} \break \footnotesize{[B. S. ZHitkov. Viktor Vavich. Kniga vtoraya (1941)]} &
\foreignlanguage{russian}{Провальное выступление сборной России на Олимпиаде <...>} \break \textit{‘The \textbf{failed} performance of the Russian team at the Olympics <...>’} \break \footnotesize
{[Sergej Podushkin. Opasnye igry na al'pijskom vozduhe. Gornolyzhniki nachinayut sezon // «Izvestiya», 2002.10.25]} \\ \midrule
\end{tabular}
\caption{Examples of sampled sentence pairs for the word \foreignlanguage{russian}{`провальный'} `failed'.}
\label{tab:proval_context}
\end{table}

For the word \foreignlanguage{russian}{`инкубатор'} (the $\Delta$LATER value of $-1.05$), the distributions are the opposite. The 4-judgment is prevalent in the EARLIER group and there is diversity in the LATER group. Indeed, in the EARLIER group (the Soviet period), \foreignlanguage{russian}{`инкубатор'} is used mostly in its literal meaning of \sense{incubator}, while in the LATER group (he post-Soviet period) there are many occurrences in the figurative sense of \sense{business incubator}. Thereby, the word \foreignlanguage{russian}{`инкубатор'} is undergoing an innovative meaning change in the post-Soviet times, as its figurative sense is becoming more and more widespread.

\section{Evaluation} \label{sec:evaluation}

\textit{RuSemShift} is mainly intended to be used by other researchers in the field of lexical semantic change detection for Russian. However, below we report the performance of several well-known change detection methods on our datasets, to set the baseline. We solved the task of ranking: that is, given a list of target words and two time-specific corpora, a system should predict semantic change degrees which would position the target words in the order as close to the gold one as possible. First we employed static distributional embeddings trained with the CBOW algorithm \cite{Mikolov_representation:2013}. After that, we tried several variations of contextualized embeddings, namely ELMo \cite{elmo}.

\subsection{Static embeddings}

In Table~\ref{tab:baseline}, we report the performance of the method based on static embeddings. We also use a very simple frequency-based baseline, where the degree of semantic change is estimated by the difference of target word absolute frequencies between two time periods. The `word2vec with Procrustes alignment' is the classic method of calculating cosine similarity between target word vectors in two CBOW embedding models trained on different time periods (we used the same splits of the Russian National Corpus as during the creation of \textit{RuSemShift}). The trained models were aligned using Orthogonal Procrustes as described in \newcite{hamilton2016cultural}.

We report the correlations between the predictions of these methods and the COMPARE and $\Delta$LATER values from $RuSemShift_1$ and $RuSemShift_2$. Note that we used the absolute values of $\Delta$LATER, leaving the distinguishing of innovative versus reductive semantic change for future work. This means that an ideal system will produce perfectly positive correlations with $\Delta$LATER and perfectly negative correlations with COMPARE (or vice versa, depending on the exact method), since the former increases as the degree of semantic change grows, while the latter increases as word usages become more similar.

\begin{table}
    \centering
    \begin{tabular}{l|cc|cc}
         \toprule
         \textbf{Dataset} & \multicolumn{2}{c|}{\textbf{$\Delta$LATER}} & \multicolumn{2}{c}{\textbf{COMPARE}} \\
         \midrule
         & Frequency & word2vec Procrustes & Frequency & word2vec Procrustes  \\
         \midrule
         $RuSemShift_1$ & -0.275 & \textbf{0.234} & 0.046  & \textbf{0.403*}  \\
         $RuSemShift_2$ & -0.024 & \textbf{0.118}  & -0.062  & \textbf{0.269}  \\
         \bottomrule
    \end{tabular}
    \caption{Spearman $\rho$ correlations of the frequency-based and word2vec-based predictions with \textit{RuSemShift} annotations. * denotes statistical significance at $p<0.05$.}
    \label{tab:baseline}
\end{table}

As expected, comparing cosine distance of Procrustes-aligned word embeddings far outperforms simply measuring frequency changes (this latter method produces predictions close to random in most cases). It can also be observed that $RuSemShift_2$ is more difficult than $RuSemShift_1$. A possible explanation is that Soviet and post-Soviet texts are on average less distant in time from each other than Soviet and pre-Soviet texts: the former pair of time bins lies entirely within 100 years, while the latter covers the time span of about 250 years. Because of that, semantic differences from $RuSemShift_1$ (between Soviet and pre-Soviet lexical meanings) are manifested more clearly in the corpora. Finally, $\Delta$LATER rankings are more difficult to reproduce than those for COMPARE; no method managed to achieve a statistically significant correlation in this case. This arguably stems from the nature of this measure: even though we used its absolute values, it is still focused rather on the nature of semantic shifts than on their degree, and this is not something which can be easily approximated by cosine similarity between Procrustes-aligned word embeddings. More advanced methods are required to better predict $\Delta$LATER values from data.

\subsection{Contextualized embeddings}
We trained ELMo \cite{elmo} models\footnote{Using the implementation from \url{https://github.com/ltgoslo/simple_elmo} with 3 epochs and the vocabulary of 100 000 most frequent words. The rest hyperparameters were left at their default values.} on the RNC texts to produce contextualized token representations for each time period. ELMo embeddings are inferred from bidirectional language models trained using two-layer long short-term memory network (LSTM) for next word predictions in both directions. Every token is represented as a linear combination of hidden layers and depends on the context in which the token appears.

All corpora were segmented into sentences, tokenized and lemmatized with a \textit{UDPipe 1.2} \cite{udpipe} model trained on the SynTagRus treebank \cite{ud_rus}. It is not yet well known whether contextualized embedding models should be trained on lemmatized or non-lemmatized texts, but \newcite{kutuzov-kuzmenko-lemma} showed that at least for Russian, lemmatization improves the performance in word sense disambiguation task. It also excludes word form bias, since we want to trace semantic shifts in lexemes rather than specific word forms.

We trained six ELMo models in three variants:
\begin{enumerate}
    \item a single model trained on the full RNC corpus with texts from all time periods (differentiation by time periods is made at the inference stage when token embeddings are produced);
    \item three models trained separately on each sub-corpus: pre-Soviet, Soviet and post-Soviet models;
    \item two models trained incrementally (initialized from the checkpoint of the model trained on texts from the previous time period): Soviet incremental model and post-Soviet incremental model.
\end{enumerate}

We extract ELMo  token embeddings for each word's usage in two adjacent time periods and estimate semantic change score for this word using the measures described below. Extracted contextualized embeddings of each target word from two time periods are represented as two time-specific matrices. We explored two semantic change detection measures: \textit{cosine similarity between averaged token embeddings}\footnote{This was not used with separately trained models, because it does not make sense to directly measure it between vectors from two different spaces.} and \textit{Jensen-Shannon divergence} which requires prior application of the clustering algorithm.

\begin{enumerate}
  \item \textit{Cosine similarity}. We compute average vectors from usage matrices, which gives us representations which resemble static type embeddings. Then we compute cosine similarity between these average embeddings as a measure of semantic change. The lower is the cosine similarity, the higher is the degree of semantic change.  This method is inspired by the PRT technique from \newcite{kutuzov2020uio}.

  \item \textit{Jensen-Shannon divergence} (JSD). In this measure, influenced by \newcite{dubossarsky2015bottom}, \newcite{addmore_2020} and \newcite{giulianelli2020}, word usage matrices from two time periods are first stacked into one matrix. Then, we standardize the vectors and obtain word usage clusters of token embeddings using the Affinity Propagation clustering algorithm \cite{frey2007affinity}. After obtaining clusters for each word, we calculate usage type (sense) probability distributions  for each time period by normalizing counts of word usages in the clusters. Then we compute the JSD score:
  \begin{equation}
JSD = \sqrt{\frac{D(p \parallel m) + D(q \parallel m)}{2}}
\end{equation}
\\ where \emph{D} is the Kullback-Leibler divergence, \emph{p} and \emph{q} are sense distributions and \emph{m} is the pointwise mean of \emph{p} and \emph{q}.
Higher JSD score indicates more intense change in the proportions of clustered word usage types across time periods.
\end{enumerate}

\begin{table}[th]
\small
\centering
\hspace*{-1cm}
\begin{tabular}{c|c|c|c|c|c}
\toprule
\textbf{Model type}  &\textbf{Dataset} & \multicolumn{2}{c|}{\textbf{Cosine similarity}} & \multicolumn{2}{c}{\textbf{JSD}} \\
 \midrule
&  & \multicolumn{1}{l}{\textbf{$\Delta$LATER}} & \textbf{COMPARE} & \multicolumn{1}{l}{\textbf{$\Delta$LATER}} & \textbf{COMPARE} \\
\midrule
\multirow{2}{*}{Single} & $RuSemShift_1$ & \textbf{-0.351}* & 0.246 & -0.158 & \textbf{0.385}* \\
 & $RuSemShift_2$ & \textbf{-0.300}* & \textbf{0.541}* & -0.147 & \textbf{0.364}* \\
\midrule
\multirow{2}{*}{Incremental} & $RuSemShift_1$ & 0.068 & 0.055 & -0.117 & -0.074 \\
 & $RuSemShift_2$ & 0.028 & 0.186          & 0.028 & 0.186 \\
\midrule
\multirow{2}{*}{Separate} & $RuSemShift_1$ & - & - & 0.201 & -0.283 \\
 & $RuSemShift_2$ & - & - & -0.064 & 0.100
\end{tabular}
\caption{Spearman $\rho$ correlations of the ELMo-based predictions with \textit{RuSemShift} annotations.}
\label{tab:scores}
\end{table}

Table~\ref{tab:scores} shows that incremental and separate ELMo models do not yield significant correlations with human judgments. As for the single model, it consistently outperforms static embeddings on $RuSemShift_2$ (both measures), and $RuSemShift_1$ ($\Delta$LATER): thus, in 3 out of 4 cases.
As already observed, COMPARE metrics is easier to approximate than $\Delta$LATER. Also, cosine similarity generally is better than JSD, despite the latter being much heavier computationally. Negative correlations with $\Delta$LATER are normal and caused by the nature of this measure: higher values indicate stronger change.

\section{Conclusion}
\label{conclusion}

We presented \textit{RuSemShift}, which consists of two publicly available test sets of Russian words manually annotated with the degrees of diachronic semantic change they experienced (the degree is a continuous score). Annotation process was based on the theoretically sound DURel framework \cite{durel}. One of the datasets is produced from re-annotated list of target words from prior work and another is completely new. The datasets allow to evaluate methods for lexical semantic change detection in Russian: either graded or binary (with any desired binarization threshold). They provide data on 3 large time periods: pre-Soviet (1682-1916), Soviet (1918-1990) and post-Soviet (1991-2017).

This is the first semantic change detection dataset for Russian created in a large-scale crowd-sourcing annotation effort. It is also important that \textit{RuSemShift} is fully compatible with semantic change datasets developed for other languages, for example those presented for the corresponding SemEval-2020 shared task \cite{schlechtweg2020semeval}. The dataset is available online\footnote{\url{https://github.com/juliarodina/RuSemShift}} under a Creative Commons Attribution-ShareAlike 4.0 International License.

As a sanity check (and to establish the baseline performance boundaries), we evaluated several semantic change modeling systems on  \textit{RuSemShift}. We managed to achieve significant correlation with human judgments both with static and with contextualized word embeddings, with the latter consistently outperforming the former. At the same time, simple frequency-based baseline failed to achieve any meaningful results, which signals that the dataset lacks simplistic frequency cues.

\textit{RuSemShift} is limited to nouns and a few adjectives. One of the possible future research directions is to extend the dataset with other parts of speech. Another drawback of the dataset is that it does not distinguish between different types of semantic change (e.g. narrowing, widening, metaphorization etc.). Nevertheless, we hope that in its current state, \textit{RuSemShift} will already  be of help to the researchers interested in tracing diachronic semantic shifts in Russian.

\section*{Acknowledgments}
This research was supported by the Russian Science Foundation grant 20-18-00206.

\bibliographystyle{coling}