SINCERE: Sequential Interaction Networks representation learning on Co-Evolving RiEmannian manifolds

A Riemannian manifold $(\mathcal{M},g)$ is a real and smooth manifold equipped with an inner product on tangent space $g_{\mathbf{x}}:\mathcal{T}_{\mathbf{x}}\mathcal{M}\times\mathcal{T}_{\mathbf{x}}\mathcal{M}\rightarrow\mathbb{R}$ at each point $\mathbf{x}\in\mathcal{M}$, where the tangent space $\mathcal{T}_{\mathbf{x}}\mathcal{M}$ is the first order approximation of $\mathcal{M}$ around $\mathbf{x}$, which can be locally seemed Euclidean. The inner product metric tensor $g_{\mathbf{x}}$ is both positive-definite and symmetric, i.e., $g_{\mathbf{x}}(\mathbf{v},\mathbf{v})\geq 0,g_{\mathbf{x}}(\mathbf{u},\mathbf{v})=g_{\mathbf{x}}(\mathbf{v},\mathbf{u})$ where $\mathbf{x}\in\mathcal{M}$ and $\mathbf{u},\mathbf{v}\in\mathcal{T}_{\mathbf{x}}\mathcal{M}$.

Hyperboloid and sphere are two common models for hyperbolic and spherical Riemannian geometry. However, hyperbolic space is not a typical vector space, which means we cannot calculate the embedding vectors with operators as if we use in Euclidean space. In order to overcome the gap among hyperbolic, spherical and euclidean geometry, we adopt the $\kappa$-stereographic model (Bachmann et al., 2020) as it unifies operations with gyrovector formalism (Ungar, 2008).

An $n$-dimension $\kappa$-stereographic model is a smooth manifold $\mathcal{M}_{\kappa}^{n}=\left\{\mathbf{x}\in\mathbb{R}^{n}\mid-\kappa\|\mathbf{x}\|_{2}^{2}<1\right\}$ equipped with a Riemannian metric $g_{\mathbf{x}}^{\kappa}=\left(\lambda_{\mathbf{x}}^{\kappa}\right)^{2}\mathbf{I}$, where $\kappa\in\mathbb{R}$ is the sectional curvature and $\lambda_{\mathbf{x}}^{\kappa}=2\left(1+\kappa\|\mathbf{x}\|_{2}^{2}\right)^{-1}$ is the point-wise conformal factor. To be specific, $\mathcal{M}_{\kappa}^{n}$ is the stereographic projection model for spherical space ($\kappa>0$) and the Poincaré ball model of radius $1/\sqrt{-\kappa}$ for hyperbolic space ($\kappa<0$), respectively. We first list requisite operators below, specific ones are attached in Appendix. Note that bold letters denote the vectors on the manifold.

M$\boldsymbol{\ddot{o}}$bius Addition. It is a non-associative addition $\oplus_{\kappa}$ of two points $\mathbf{x},\mathbf{y}\in\mathcal{M}_{\kappa}^{n}$ defined as:

M$\boldsymbol{\ddot{o}}$bius Scalar and Matrix Multiplication. The augmented M$\ddot{o}$bius scalar and matrix multiplication $\otimes_{\kappa}$ of $\mathbf{x}\in\mathcal{M}_{\kappa}^{n}\backslash\left\{\mathbf{o}\right\}$ by $r\in\mathbb{R}$ and $\boldsymbol{M}\in\mathbb{R}^{m\times n}$ is defined as follows:

Exponential and Logarithmic Maps. The connection between the manifold $\mathcal{M}_{\kappa}^{n}$ and its point-wise tangent space $\mathcal{T}_{\mathbf{x}}\mathcal{M}_{\kappa}^{n}$ is established by the exponential map $\exp_{\mathbf{x}}^{\kappa}:\mathcal{T}_{\mathbf{x}}\mathcal{M}_{\kappa}^{n}\rightarrow\mathcal{M}_{\kappa}^{n}$ and logarithmic map $\log_{\mathbf{x}}^{\kappa}:\mathcal{M}_{\kappa}^{n}\rightarrow\mathcal{T}_{\mathbf{x}}\mathcal{M}_{\kappa}^{n}$ as follows:

Distance Metric. The generalized distance $d_{\mathcal{M}}^{\kappa}\left(\cdot,\cdot\right)$ between any two points $\mathbf{x},\mathbf{y}\in\mathcal{M}_{\kappa}^{n},\mathbf{x}\neq\mathbf{y}$ is defined as:

In Riemannian geometry, curvature is the amount by which a curve deviates from being a straight line, or a surface deviates from being a plane, which is originally defined on the continuous smooth manifold. Sectional curvature and Ricci curvature are two success formulations for the discrete graph (Ye et al., 2020), describing the global and local structure, respectively.

Sectional Curvature. Sectional curvature is an equivalent but more geometrical description of the curvature of Riemannian manifolds compared to the Riemann curvature tensor (Lee, 2018). It is defined over all two-dimensional subspaces passing through a point and is treated as the constant curvature of a Riemannian manifold in recent work.

Ricci Curvature. Ricci curvature is the average of sectional curvatures and is mathematically a linear operator on tangent space at a point. In graph domain, it is extended to measure how the geometry of a pair of neighbors deviates from the case of gird graphs locally. Ollivier-Ricci (Ollivier, 2009) is a coarse approach to computing Ricci curvature while Forman-Ricci (Forman, 2003) is combinatorial and faster to compute.

Before presenting our proposed model, we summarize the important notations in Tab. 2. We may drop the subscript indices in later sections for clarity. The definitions of sequential interaction network and representation learning task are stated as follows:

As we place the user and item nodes on different Riemannian manifolds, they are recorded by the embedding matrix $\mathbf{U}$ and $\mathbf{I}$ respectively, which can be initialized with the feature vectors such as the user profiling or film description if available. Since the initialized $\mathbf{U}$ and $\mathbf{I}$ are in Euclidean space, we logarithmically map them to corresponding Riemannian space $\mathbb{U}_{\kappa_{u}}$ and $\mathbb{I}_{\kappa_{i}}$ with Eq. 5.

For the message propagation and information aggregation, the design of SINCERE not only incorporates the information across different geometric spaces via a unified formalism, but also guarantees that all operations are conformal invariant. For clarity of expressions, we define $\operatorname{map}$ operation to map the vectors in manifold $\mathcal{M}_{\kappa_{1}}$ to $\mathcal{M}_{\kappa_{2}}$ as $\operatorname{map}_{\kappa_{1}}^{\kappa_{2}}\left(\cdot\right):=\exp_{\mathbf{o}}^{\kappa_{2}}\left(\log_{\mathbf{o}}^{\kappa_{1}}\left(\cdot\right)\right)$. The aggregation operators of user and item are defined as follows:

where $\boldsymbol{M}$s are trainable matrices and $\mathbf{h}$ represents hidden state. The aggregation operator has three main components: hidden state aggregation, interaction aggregation and neighbor aggregation.

Take the user aggregation shown in Eq. 7 and Fig. 3 as an example: the first component is the update of user $j$ hidden representation for several layers, which can be cascaded for multi-hop message aggregation, and the second component aggregates the associated edge information to user $j$ and the third component aggregates items information which is interacted by user $j$. It is worth noting that the problem of ignoring the information propagation among the same type of nodes can be solved by stacking several layers. $\mathbf{e^{\prime}}_{u/i}^{T}$ in the interaction aggregation is either Early Fusion $\mathbf{e^{\prime}}_{u/i}^{T}=\textsc{Mlp}\left(\textsc{Pooling}\left(\mathbf{e}\in\mathcal{E}_{u/i}^{T}\right)\right)$ or Late Fusion $\mathbf{e^{\prime}}_{u/i}^{T}=\textsc{Pooling}\left(\textsc{Mlp}\left(\mathbf{e}\in\mathcal{E}_{u/i}^{T}\right)\right)$ and $\textsc{Pooling}(\cdot)$ can be one of the Mean Pooling and Max Pooling. $\mathbf{i^{\prime}}_{u}^{T}$ and $\mathbf{u^{\prime}}_{i}^{T}$ in neighbor aggregation are the weighted gyro-midpoints (Ungar, 2010) (specified in the Appendix) in item and user stereographic spaces, respectively. Take $\mathbf{i^{\prime}}_{u}^{T}$ as an example, which is defined as:

where $\alpha_{k}$ is attention weight and $\lambda_{\mathbf{x}}^{\kappa}$ is point-wise conformal factor.

After the aggregation of nodes and edges, we project embeddings to next-period manifolds for further training and predicting. The node updating equation is defined as follows:

where the curvature $\kappa^{T_{n+1}}$ of next interval can be obtained from Eq. 16.

We set the sequential interactions in Euclidean space instead of on Riemannian manifolds as user and item nodes. The intuition behind such design is that the tangent space which is Euclidean is the common space of different Riemannian manifolds and users and items are linked by sequential interactions. Specifically, for an edge $e_{k}\in\mathcal{E}$, the integration of its corresponding attribute $\mathbf{X}_{k}\in\mathcal{X}$ and timestamp $t_{k}\in\mathcal{T}$ is regarded as the initialized embedding. In order to capture the temporal information of interactions, we formalize the time encoder as a function $\Phi_{t}:\mathbb{R}\rightarrow\mathbb{R}^{d}$ which maps a continuous time $t_{k}$ to a $d$-dimensional vector. In order to account for time translation invariance in consideration of the aforementioned batch setup, we adopt the harmonic encoder (Xu et al., 2020) as follows:

where $\omega$s and $\theta$s are learnable encoder parameters. and $\left[\cdot\,;\cdot\right]$ is the concatenation operator. The definition of Eq. 12 satisfies time translation invariance. Thus, the initial embedding of the interaction $e_{k}$ can be represented as:

where $\sigma(\cdot)$ is the activation function and $\boldsymbol{W_{1}}$ is the training matrix.

Embedding vectors of the previous work are set on one fixed curvature manifold such as Poincaré Ball, while the fixed curvature is a strong premise assumption which cannot manifest the dynamics of the representation space. In fact, the curvature of the embedding space evolves over time, and thus we need to design curvature computation for both local curvature and global curvature, i.e., Ricci curvature and sectional curvature.

Sequential interaction networks are mostly bipartite graphs, which means there is no direct link connected between nodes of the same type. Therefore, to explore the local Ricci curvature in both user and item spaces, we need to extract new topologies from the input network. The rule of subgraph extraction is based on the shared neighbor relationship, e.g., users with common item neighbors are friends with each other. However, there will be several complete graphs which increase the complexity if we let all users with the same neighbors become friends. Here, we take sampling in extracting subgraph process to avoid long time cost. Then, the local curvature of any edge $(x,y)$ can be resolved by Ollivier-Ricci curvature $\kappa_{r}$ defined as follows:

where $W(\cdot,\cdot)$ is Wasserstein distance (or Earth Mover distance) which finds the optimal mass-preserving transportation plan between two probability measures. $m_{x}$ is the mass distribution of the node $x$ measuring the importance distribution of one node among its one-hop neighbors $\mathcal{N}(x)=\{x_{1},x_{2},...,x_{l}\}$, which is defined as:

where $\alpha$ is a hyper-parameter within $[0,1]$. Similar to previous work (Ye et al., 2020; Sia et al., 2019), we set $\alpha=0.5$.

Let $\mathbf{R}$ represent the vector of Ricci curvatures. Inspired by the bilinear form between Ricci curvature and sectional curvature, we design the global sectional curvature neural network called CurvNN as follows:

where $\boldsymbol{W_{2}}$ is the trainable matrix and Mlp means multilayer perceptron. The bilinear design of CurvNN allows us to obtain the sectional curvature of any sign.

The observation of the curvature is also important for us to train CurvNN. Therefore, we adopt a variant of the Parallelogram Law to observe the sectional curvature (Gu et al., 2019; Fu et al., 2021; Bachmann et al., 2020). Considering a geodesic triangle $abc$ on manifold $\mathcal{M}$ and $m$ is the midpoint of $bc$, two of their quantities are defined as: $\gamma_{\mathcal{M}}(a,b,c):=d_{\mathcal{M}}(a,m)^{2}+d_{\mathcal{M}}(b,c)^{2}/4-\left(d_{\mathcal{M}}(a,b)^{2}+d_{\mathcal{M}}(a,c)^{2}\right)/2$ and $\gamma_{\mathcal{M}}(m;b,c;a):=\frac{\gamma_{\mathcal{M}}(a,b,c)}{2d_{\mathcal{M}}(a,m)}$. The observed curvature is calculated in Algorithm 1. The observed curvature $\kappa_{o}$ will supervise the training of CurvNN to generate estimated curvature $\kappa_{e}$ accurately as possible.

Benefiting from the fact that the output of SINCERE is embedded representation of users and items, we can treat them as input to various downstream tasks, such as interaction prediction. If we easily add up the distance from different spaces, the distortion will be huge due to different geometry metrics. Therefore, we consider our optimization from two symmetric aspects, i.e., user and item. Specifically, we first map the item embedding to user space and calculate the distance under user geometry metric, and vice versa as follows:

Then, we regard Fermi-Dirac decoder, a generalization of Sigmoid, as the likelihood function to compute the connection probability between users and items in both spaces. Since we convert the distance into probabilities, the probabilities then can be easily summed. Moreover, we are curious about which geometric manifolds are more critical for interaction prediction, and then assign more weight to the corresponding probability. The likelihood function and probability assembling are defined as follows:

where $\Theta$ represents all learnable parameters in SINCERE, $r,t>0$ are hyperparameters of Fermi-Dirac decoder, and $\rho$ is the learnable weight. Users and items share the same formulation of the likelihood.

The main optimization is based on the idea of Pull-and-Push. We hope that the embedding in batch $T_{n}$ is capable of predicting the interaction in batch $T_{n+1}$, thus we utilize the graph in batch $T_{n+1}$ to supervise the previous batch. In particular, we expect a greater probability for all interactions that actually occur in next batch, but a smaller probability for all the negative samples. Given the large number of negative samples, we determine to use negative sampling (Gaussian) with rate of 20% and it can also avoid the problem of over-fitting. For the curvature estimator component, we wish that CurvNN can learn the global sectional curvature from the local structure (Ricci curvature) without observing in the prediction task. Therefore, we make the Euclidean norm of estimated curvature $\kappa_{e}$ and observed curvature $\kappa_{o}$ as our optimizing target. We calculate the total loss as follows:

The procedure of training SINCERE is given in appendix. The curvature estimator and cross-geometry operations are two main processes of SINCERE. To avoid excessive parameters, we use a shared curvature estimator for both user and item spaces. The primary computational complexity of SINCERE is approximated as $O(|\mathcal{U}|DD^{\prime}+|\mathcal{I}|DD^{\prime}+|\mathcal{E}|D^{\prime 2})+O(V^{3}\log V)$, where $|\mathcal{U}|$ and $|\mathcal{I}|$ are number of user and item nodes and $|\mathcal{E}|$ is the number of interactions. $D$ and $D^{\prime}$ are the dimensions of input and hidden features respectively and $V$ is the total number of vertices in the Wasserstein distance sub-problem. The former $O(\cdot)$ is the computational complexity of all aggregating and updating operations and the computation of other parts in our model can be parallelized and is computationally efficient. The latter $O(\cdot)$ is the complexity of Olliver-Ricci curvature. In order to avoid repeated calculation of Ricci curvature, we adopt an OFFLINE pre-computation that calculates Ricci curvatures according to different batch sizes and saves it in advance since the subgraph in each batch does not change.

Datasets. We conduct experiments on five dynamic real-world datasets: MOOC, Wikipedia, Reddit, LastFM and Movielen to evaluate the effectiveness of SINCERE. The description and statistic details of these datasets are shown in Appendix.

The goal of the future interaction prediction task is to predict the next item a user is likely to interact with based on observations of recent interactions. We here use two metrics, mean reciprocal rank (MRR) and Recall@10 to measure the performance of all methods. The higher the metrics, the better the performance. For fair comparison, all models are run for 50 epochs and the dimension of embeddings for most models are set to 128. We use a chronological train-valid-test split with a ratio of 80%-10%-10% following other baselines. We use the validation set to tune SINCERE hyperparameters using Adam optimization with a learning rate of $3\times 10^{-3}$.

During testing, given a former period of interactions, SINCERE first estimates the sectional curvature of the next period based on the structure information, then calculates the link probability between the specific user and all items and predicts a ranked top-$k$ items list. The experimental results are reported in Tab. 3, where all the baselines use the parameters of the best performance according to the original papers. In general, our method performs the best against other methods, demonstrating the benefits of dual spaces design and representation spaces dynamics. Among all methods, we find that SINCERE and DeePRed have the smallest gaps between MRR and Recall@10, which means not only can these two models find the exact items the user may interact with, but also can distinguish the ground truth from negative samples with higher ranks.

While predicting future interactions, we discover that the performance of two state-of-the-art methods JODIE and HILI have little vibration with the embedding size from 32 to 256 compared with other methods, which means they are insensitive to the embedding size. We argue that the robustness to embedding size is actually irrelevant to the merit of the model itself and we argue that JODIE and HILI have a relatively strong reliance on static embeddings which are one-hot vectors. To verify this, we have further investigation on the results of removing static embeddings (one-hot vectors). In Fig. 4, JODIE_Dy and HILI_Dy indicates the ones with no static embedding, JODIEs are in blue schemes and HILIs in green. The experimental result shows that there is a huge gap once the one-hot vectors are removed which verifies our assumption, while SINCERE performs the best in terms of MRR and Recall@10. Besides, HILI relies less on the static embeddings for the greater gain between HILI and HILI_Dy compared to JODIE.

The introduction of co-evolving $\kappa$-stereographic spaces is the basis of SINCERE. In order to analyze the effect of dynamic modeling and co-evolving $\kappa$-stereographic spaces, we conduct ablation experiments on four datasets with two variant models named SINCERE-Static and SINCERE-$\mathbb{E}$, respectively.

For SINCERE-Static, we setup the static curvature from the training beginning the same as last-batch curvature of the previous experiment to make the spaces steady. For SINCERE-$\mathbb{E}$, we fix the curvature to zero as the space is Euclidean. As shown in Tab. 4, the performance of SINCERE-Static is closer to SINCERE compared with SINCERE-$\mathbb{E}$ which is because the curvature set in SINCERE-Static can be seen as the pseudo-optimal curvature. The small gap indicates that there is some information loss in the training process even though the pseudo-optimal curvature is given. Fig. 5 gives an visualization of SINCERE-Static on Movielen dataset with curvature set to $-1$. The performance of fixing the space as Euclidean is somehow less competitive, which confirms that introducing dual dynamic Riemannian manifolds is necessary and effective.

To further investigate the performance of SINCERE, we conduct several experiments for SINCERE with different setups to analyze its sensitivity to hyperparameters.

Fig. 6 shows the impact of embedding dimension on the performance of three methods. $128$ seems an optimal value for DeePRed in most cases. As we discuss in Sec. 4.2, JODIE counts on the static embeddings which makes embedding size have almost no influence on it. However, we find that in some cases such as LastFM and Wikipedia, SINCERE performs better with dimension $64$ than $128$ and we argue that it is due to the strong representational power of hyperbolic spaces. In these cases, $64$ is capable enough to represent the networks.

The time spent in computing Ricci curvatures and the influence of subgraph extraction sampling ratio on SINCERE performance are shown in Fig. 7. We observe that the computing time decreases sharply with the number of total intervals increase. Besides, the performance (Recall@10) levels off from the sampling ratio $15\%$ to 20% as interval number grows. Such finding informs us that instead of increasing sampling rate to improve performance, it is far better to set a higher interval number considering the computational complexity of Ricci curvatures.