Continuous-Time Sequential Recommendation with Temporal Graph Collaborative Transformer, (CIKM'21)

Paper Link

Official Github

Abstract

Challenges

1. 기존의 SR(Sequential Recommendation) 방법들(GRU4Rec, SASRec, etc.)은 sequential patterns를 활용하지만, temporal collaborative signals를 무시한다.
2. Collaborative signals의 temporal effects를 표현하는 temporal collaborative signals를 추론해야 한다.
3. Temporal collaborative signals와 seuqnetial patterns를 동시에 encode해야 한다.

Address

1. Temporal collaborative signals이 중요한 이유를 밝히고 이를 활용하고자 한다.
2. TCT layer를 통해 signals에 temporal effects를 가진 temporal node embeddings를 추론한다.
3. GNN을 통해 sequential patterns와 temporal collaborative sigals를 통합한다.

Ⅰ. Introduction

기존의 SR 방법들은 시간 순으로 과거 interaction 정보를 활용한다. 즉, sequential patterns를 이용해 model을 학습시킨다. 예를 들어, transformer의 self-attention module을 SR model에 적용 시킨 연구들에서는 과거의 items에 weight를 부여하고 aggregation한다.

하지만, 이러한 연구들은 sequential patterns를 활용하지만, temporal collaborative signals를 무시하고 있어 만족 할만한 성능을 이끌어 내지 못한다.

Figure 1: A toy example of temporal collaborative signals. Given the items that users $𝑢_1$, $𝑢_2$, $𝑢_3$ and $𝑢_4$ like in the past timestamps $𝑡_1$, $𝑡_2$, $𝑡_3$ and $𝑡_4$, the target is to recommend an item to $𝑢_4$ at $𝑡_5$ as the next item after $𝑖_2$.

Temporal collaborative signals의 효과를 fig. 1을 통해 직관적으로 알아보자. Fig. 1은 $u_4$가 $t_5$에서 interaction할 item을 예측하는 예제이다.

만약 sequential patterns만 사용한다면, $u_1, u_3$에 있는 $i_2 \rightarrow i_3$ sequential pattern이 2번 나타나므로 $i_3$을 에측할 것이다. 하지만 temporal collaborative signal을 고려한다면, $i_4$를 추천할 것이다. $u_2, u_4$는 $t_1$에 $i_1$과 interaction을 하였고, 각각 $t_3, t_4$에 $i_2$와 interaction을 하였기 때문에 높은 user similarity를 가진다고 볼 수 있다. 이는 저자들이 sequential patterns와 temporal collaborative signals를 통합하려는 동기를 부여했다.

여기서 해결해야 할 점이 2가지가 있다.

1. Collaborative signals와 seuqnetial patterns를 동시에 encode해야 한다. 기존의 방법들 user간의 관계성 즉, collaborative signals를 활용하지 않는다.
2. Collaborative signals의 영향을 temporal 관점에서 측정해야 한다. 예를 들어, fig. 1에서 $u_2, u_4$는 $i_1$을 $t_1$에 interaction을 했지만, 각각 $t_3, t_4$에 $i_2$와 interaction을 하였다. 시차가 있기 때문에 시차를 무시하고, $u_4$에 끼치는 $u_2$의 $i_1$와 $i_2$의 기여도가 같다고 가정하는 것은 문제가 있다. 따라서 collaborative signals의 중요성을 시간에 기반해 구해야 한다.

Self-attention은 sequence에서 item-item의 관계만 학습한다. 그리고 items의 temporal correlations을 capture하는 module이 없다. 그래서 저자들은 새로운 model TGSRec(Temporal Graph Sequential Recommender)를 제안한다. TGSRec은 2가지 components를 가진다.

TCT(Temporal Collaborative Transformer) layer

첫 번재 component는 기존의 transformer module을 발전시킨 것이다. Sequence에서 collaborative signals을 explicit하게 modeling하고, sequence에서 items의 temporal correlations를 표현한다.

TCT layer는 user-item interactions 사이의 collaborative attention을 사용하고, temporal 정보를 결합시킨다. Collaborative attention의 query input은 target node가 되고 key, value input은 target node의 이웃 nodes가 된다. 이를 통해 TCT layer는 시간 정보를 고려하여 이웃 nodes과의 interaction 중요성을 학습한다.

즉, TCT layer는 temporal collaborative signals를 capture하는 것이다.

Graph Information Propagation

Figure 2: The associated CTBG of Figure 1 and the inference of temporal embeddings of $u_4$ and $i_4$ at $t_5$.

두 번째 component는 저자들이 제안한 Fig. 2(a)의 CTBG (Continuous Time Bipartite Graph)를 기반으로 TCT layer에서 학습된 temporal collaborative attention을 전파한다.

CTBG는 edge의 attribute로 timestamp가 있는 graph로, 한 user의 neighbor items는 sequential patterns를 유지하고 있다. 저자들은 CTBG에 기반해 학습된 한 node의 temporal collaborative information을 neighbor nodes에 전파한다.

결론적으로 저자들은 특정 timestamp에서 추론되는, 동적인 temporal embedding을 사용할 것을 제안한다. Fig. 2(b)는 TCTlayer를 통해 추론된 time $t_5$에서 $u_4$와 $i_4$의 temporal inference이다. 이때, 과거 interactions의 영향을 구분짓기 위해 temporal 정보를 활용한다.

Contributions

Temporal Collaborative Transformer

Collaborative signals과 temporal effects를 동시에 modeling 해서 temporal collaborative signals를 추론한다.

Graph Sequential Recommendation

Sequential patterns와 temporal collaborative signals를 통합한다.

Ⅱ. Related Work

생략

Ⅲ. Definition And Preliminaries

모든 temporal interactions를 표현하기 위해 edge의 attribute로 temporal information을 가지는 CTBG를 제안한다.

$\mathcal{I}_u(t)$

the set of items interacted with the user $u$ before timestamp $t$

$\mathcal{I} \backslash \mathcal{I}_u(t)$

Remaining items.

Continuous-Time Recommendation

특정 timestamp $t$에서 주어진 user set $\mathcal{U}$와 item set $\mathcal{I}$, 관련된 CTBG가 주어진다. 이 때, user $u$의 continuous-time recommendation는 $\mathcal{I} \backslash \mathcal{I}_u(t)$에서 ranking list를 만드는 것이다.

Continuous-Time Sequential Recommendation

특정 user $u$와 해당 user의 미래 timestamps set $\mathcal{T}_u > T$이 주어졌을 때, 모든 timestamp $t \in \mathcal{T}_u$에 대해 continuous-time recommendation을 수행하는 것이다. 그래서 다른 work들과 다르게 prediction을 진행하려면 미래의 timestamps가 반드시 필요하다.

Ⅳ. Proposed Model

TGSRec은 3개의 modules를 가진다.

Embedding layer

SR 문제를 graph embedding method와 연결하기 위해 nodes와 timestamps를 동일한 방식으로 encode한다.

Temporal Collaborative Transformer (TCT) layer

이웃의 temporal 영향을 구분하기 위해 temporal collaborative attention mechanism을 고안하고, temporal node embedding을 추론하기 위해 node와 time embedding 모두 aggregation 한다.

Prediction layer

마지막 TCT layer의 output embedding으로 score를 계산한다.

ⅰ. Embedding layer

저자들은 2가지 유형의 embedding: long-term embeddings and continuous-time embedding

Long-Term User/Item embeddings

Long-term collaborative signals representation을 위해 user/item의 long-term embeddings가 필요하다. 우리가 아는 일반적인 user/item embedding $\in \mathcal{R}^d$이다.

\[\begin{split} \textbf{E} &= \big[\textbf{E}_\mathcal{U};\textbf{E}_\mathcal{I} \big] \in \mathbb{R}^{d\times |\mathcal{V}|}\\ \mathcal{V} &= \mathcal{U} \cup \mathcal{I} \end{split}\]

Embedding table $\textbf{E}$는 temporal user/item embeddings를 추론하기 위한 초기 state이다. Training process 동안 $\textbf{E}$는 최적화 된다.

Continuous-Time embedding

Scalar timestamps를 vector encoding한다. 즉, timestamp마다 time embedding을 얻는다.

\[\Phi: T \mapsto \mathbb{R}^{d_T}, T \in \mathbb{R}^+\]

Time span은 temporal effect를 표현하고, sequential patterns를 알아내는데 중요한 역할을 한다. 이러한 time span은 time embeddings의 내적으로 표현된다. 그리고 time span을 통해 temporal effects를 정의한다.

한 user에 대해 한 쌍의 interactions $(u, i, t_1), (u, j, t_2)$이 주어졌을 때, temporal effect $\psi(t_1 - t_2)$는 다음과 같이 정의된다.

\[\begin{equation} \psi(t_1 - t_2) = \mathcal{K}(t_1, t_2) = \Phi(t_1) \cdot \Phi(t_2) \in \mathbb{R} \end{equation}\]

• $\mathcal{K}$: temporal kernel

Temporal effect $\psi$는 두 timestamps간 temporal correlation을 측정한다. 고려해야 할 점은 관찰되지 않은 미래의 timestamp도 encoding을 하여, 어떠한 time sapn이라도 추론될 수 있어야 한다는 것이다. 즉, 임의의 timestamp pair의 temporal effect가 time representation의 내적으로 inductive하게 추론되어야 한다.

이는 absolute time difference를 사용하지 않고, eq. 1처럼 kernel $\mathcal{K}$로 time representation을 modeling함으로써 해결 가능하다. 이때, kernel은 continuous하고 tranlation-invariant 해야 하고, Bochner’s Theorem을 사용해 이를 달성한다.

\[\begin{equation} \Phi(t) \mapsto \sqrt{\frac{1}{d_T}}[\text{cos}(\omega_1 t), \text{sin}(\omega_1 t), \dots, \text{cos}(\omega_{d_T} t), \text{sin}(\omega_{d_T} t)]^\top \end{equation}\]

• $\boldsymbol{\omega} = [\omega_1, \dots, \omega_{d_T}]^\top$은 학습 가능한 parameter이다.

ⅱ. Temporal Collaborative Transformer

TCT layer의 강점은 다음과 같다.

1. Timestamps 간의 correlation인 temporal effects $\psi$를 explicit하게 표현하는 temporal embeddings와 user/item embeddings로부터 information을 얻는다.
2. Itme-item interaction만 고려하던 기존의 self-attention mechanism을 발전시킨 collaborative attention module로 user-item의 중요성을 modeling한 collaborative signals를 explicit하게 활용한다.

먼저 user node를 예시로 들어 information을 construction하고 aggregation하는 것을 보여줄 것이다. 그리고 collaborative attention mechanism을 통해 interaction의 중요성을 추론할 것이다. 마지막으로 item node 관점에서 이를 일반화 한다.

Information Construction

각 TCT layer의 input은 long term node embeddings와 time embeddings의 조합으로 이뤄진다. 이를 통해 temporal information과 collaborative signals를 통합할 수 있게 된다.

예를 들어, time $t$에서 user $u$에 대한 $l$ 번째 TCT layer의 query $h_u^{l-1}(t)$는 다음과 같다.

$t$는 꼭 user가 특정 item과 interaction이 일어난 시간이 아니라, 임의의 시간인 것 같다.

\[\begin{equation} \textbf{h}_u^{(l-1)}(t) = \textbf{e}_u^{(l-1)}(t) || \Phi(t), \end{equation}\]

• $h_u(t) \in \mathbb{R}^{d+d_T}$: time $t$에서 user $u$의 information.
• $e_u(t) \in \mathbb{R}^d$ : user $u$의 temporal embedding
• $\Phi(t) \in \mathbb{R}^{d_T}$: time $t$의 time vector

||는 concatenation을 의미한다. Summation 등도 사용할 수 있지만, 간결함을 위해 concatenation을 사용한다. 그리고 concatenation을 사용함으로써 eq. 7처럼 해석을 좀 더 직관적으로 할 수 있게 된다.

Layer가 1일 때, input의 temporal embedding $e_u^{(0)}$은 $\textbf{E}_u$로 long-term user embedding으로 time과는 무관하다. Layer가 1보다 클 때는 temporal embedding은 이전 TCT layer에서 생성된 것을 사용한다.

$e_u(t)$라고 표기하는 것은 1번째 layer이후, $t$에 따라 temporal embedding 값이 달라지기 때문인 것 같다.

Query node 외에도 그것의 neithbors의 temporal collaborative information을 전파해야 한다. 저자들은 time $t$ 이전에 $u$와 interaction이 일어난 서로 다른 sample $S$를 무작위로 뽑는다.

\[\mathcal{N}_u(t) = \{(i,t_s)|(u,i,t_s) \in \mathcal{E}_t \text{ and } t_s < t\}\]

각 $(i, t_s)$ 쌍마다 $l$ 번째 layer의 input information은 다음과 같다.

\[\begin{equation} \textbf{h}_i^{(l-1)}(t_s) = \textbf{e}_i^{(l-1)}(t_s) || \Phi(t_s), \end{equation}\]

• $h_i(t_s) \in \mathbb{R}^{d+d_T}$: time $t_s$에서 item $i$의 information.
• $e_u(t_s) \in \mathbb{R}^d$ : item $i$의 temporal embedding
• $\Phi(t_s) \in \mathbb{R}^{d_T}$: time $t_s$의 time vector

유사하에 Layer가 1일 때, input의 temporal embedding은 $\textbf{E}_i$이고, 1보다 클 때는 이전 TCT layer에서 생성된 것이다.

Information Propagation

Information을 construct한 뒤, sampling된 이웃의 inforamtion을 propagate하여 temporal embedding $e_u$을 추론해야 한다. 이웃 nodes는 time $t$와 관련되어 있기 때문에, information propagation을 통해 sequential patterns와 temporal collaborative signals를 통합할 수 있다. 저자들은 아래와 같이 linear combination으로 information을 propagation한다.

\[\begin{equation} \textbf{e}_{\mathcal{N}_u}^{(l)}(t) = \sum_{(i, t_s) \in \mathcal{N}_u(t)} (\pi_t^u(i, t_s))^{(l)}\textbf{W}_v^{(l)}h_i^{(l-1)}(t_s) \end{equation}\]

• $\pi_t^u(i, t_s)$는 time $t$에서 user $u$의 temporal inference에 interaction $(u,i,t_s)$이 끼치는 영향을 의미한다.
• $\textbf{W}_v \in \mathbb{R}^{d\times(d+d_T)}$는 linear transformation matrix이다.

Temporal Collaborative Attention

여기서는 information propagation에서 살펴 본 $\pi_t^u(i, t_s)$를 collaborative attention mechanism으로 측정한다. Neighboring interactions와 temporal information은 과거 interaction의 importance에 기여하고, $\pi_t^u(i, t_s)$는 neighboring interactions와 temporal information을 동시에 고려한다. 그래서 오직 item-item correlations만 고려하는 self-attention mechanism과 다르게 temporal collaborative signals를 capture하는 더 유용한 mechanism이다.

\[\begin{equation} (\pi_t^u(i, t_s))^{(l)} = \frac{1}{\sqrt{d+d_T}}\big(\textbf{W}_k^{(l)}h_i^{(l-1)}(t_s)\big)^\top\textbf{W}_q^{(l)}\textbf{h}_u^{(l-1)}(t) \end{equation}\]

• $\textbf{W}_k^{(l)}, \textbf{W}_q^{(l)}$은 transformation matrices이다.
• $1/\sqrt{d+d_T}$은 scalar factor로, user와 item의 dimension이 커질수록 내적의 값이 커지는 것을 방지하기 위한 regularization이다.

저자들은 dot-product로 attention을 구한다. Eq. 3,4에 기반해, transformation matrices를 무시하면 Eq. 6은 아래와 같아진다.

\[\begin{equation} \textbf{e}^{(l-1)}_u(t) \cdot \textbf{e}_i^{(l-1)}(t_s) + \Pi(t)\cdot\Pi(t_s) \end{equation}\]

첫 번째 term은 user-item collaborative signal이고 두 번째 term은 Eq. 1에서 정의한 temporal effect이다. Layer가 더 쌓이면, collaborative signal과 temporal effect는 entangle된다. 그렇기 때문에, dot-product attention은 temporal collaborative signals의 영향을 특성화할 수 있다.

이후 sampling된 모든 이웃 interactions에 대해 softmax로 normalize한다.

\[\begin{equation} \pi_t^u(i, t_s) = \frac{\text{exp}\big( \pi_t^u(i, t_s) \big)}{\sum_{(i^\prime, t_s^\prime \in \mathcal{N}_u(t))}\text{exp}\big(\pi_t^u(i^\prime, t^\prime_s)\big)} \end{equation}\]

구현은 Eq. 4에서 구한 이웃의 information을 stacking하여 matrix로 나타낸다. 그리고 temporal collaborative attention module의 input인 query, key, value도 matrix로 표현하면, 다음과 같다.

\[\begin{split} & \textbf{H}_{\mathcal{N}_u}^{(l-1)}(t) \in \mathbb{R}^{(d + d_t) \times S}, \\ & \textbf{K}_u^{(l-1)}(t) = \textbf{W}_k^{(l)}\textbf{H}_{\mathcal{N}_u}^{(l-1)}(t), \\ & \textbf{V}_u^{(l-1)}(t) = \textbf{W}_v^{(l)}\textbf{H}_{\mathcal{N}_u}^{(l-1)}(t), \\ & \textbf{q}_u^{(l-1)}(t) = \textbf{W}_q^{(l)}\textbf{h}_u^{(l-1)}(t), \\ \end{split}\]

이는 Fig. 3에 초록색으로 나타나 있다. 간결함과 모호성을 없애기 위해, layer와 time $t$없이 Eq. 6과 8을 합치서 Eq. 5를 나타내면 아래와 같아진다.

\[\begin{equation} \textbf{e}_{\mathcal{N}_u} = \textbf{V}_u \cdot \text{softmax} \bigg( \frac{\textbf{K}_u^\top q_u}{\sqrt{d + d_T}} \bigg) \end{equation}\]

이는 Transformer에 있는 dot-product attention 형태로, multi-head attention 연산을 적용할 수 있고, 각 head에서 나온 information을 concatenate으로 aggregation한다.

Information Aggregation

$l$ 번째 node의 embedding을 어기 위해 TCT layer 마지막 단계에서는 Eq. 3에 있는 query information과 Eq. 5에 있는 이웃 information을 FFN으로 aggergate한다.

\[\begin{equation} \textbf{e}^{(l)}_u(t) = \text{FFN}\bigg( \textbf{e}_{\mathcal{N_u}}^{(l)}(t) || \textbf{h}_u^{(l-1)}(t) \bigg) \end{equation}\]

• $e_u^{(l)}(t)$는 layer $l$에서 time $t$일 때 user $u$의 temporal embedding이다.
• FFN은 2개의 linear layer와 RELU activation 함수로 이뤄져 있다.

Generalization to items

Item이 query일 때도 앞에서 user와 했던 것과 유사하게 진행된다. 단지 Eq. 4, 5에서 neighbor가 user-time pair가 되는 것이다.

ⅲ. Model Prediction

Test의 input으로 $(u,i,t)$ triplet이 사용된다. 그리고 TCT layer를 통해 마지막 layer에서 $\text{e}_u^L(t), \textbf{e}_i^L(t)$을 얻어서 내적을 통해 score를 계산한다.

\[\begin{equation} r(u,i,t) = \textbf{e}_u^{(L)}(t) \cdot \textbf{e}_i^{(L)}(t) \end{equation}\]

ⅳ. BPR Loss

Optimization으로 BPR loss를 사용한다.

\[\begin{equation} \mathcal{L}_{\text{bpr}} = \sum_{(u,i,j,t) \in \mathcal{O}_T} -\text{log} \sigma(r(u,i,t) - r(u,j,t)) + \lambda||\Theta||^2_2 \end{equation}\]

• $\mathcal{O}_T$는 training samples를 뜻한다.
• $\Theta$는 모든 학습 가능한 parameter이다.
• $\sigma(\cdot)$은 sigmoid function이다.

Traning samples는 다음과 같다.

\[\mathcal{O}_T = \{(u,i,j,t)|(u,i,t) \in \mathcal{E}_t, j \in \mathcal{I}\backslash\mathcal{I}_u(t)\}\]

Ⅴ. Experiments

생략…