CoLA-Former: Graph Transformer Using Communal Linear Attention for Lightweight Sequential Recommendation

1 Introduction

User behaviors often exhibit continuity, manifesting as historical sequences [Ma et al., 2024]. This promotes the research of Sequential Recommendation (SR) systems which aim to effectively deliver personalized products [Chen et al., 2023], contents [Hu et al., 2024], and services [Zhou et al., 2020] to users. Among various SR methods, Graph-based Sequential Recommender systems (GSRs) excel in capturing intricate relationships between users and items in nonEuclidean spaces [Liu et al., 2024b; Wang et al., 2024]. Numerous advancements have been made to enhance GSRs, including GCN-based approaches [Chang et al., 2021; Zhang et al., 2023b], GAT-based techniques [Zhang et al., 2023a; Wu et al., 2023a], GCL-based methods [Zhang et al., 2024a;

∗Corresponding Authors.

Zhang et al., 2022], and those based on Graph Transformers [Luo et al., 2024; Xia et al., 2023].

As one of the most representative GSRs, Graph Transformer-based methods have received considerable attention due to their capability of apprehending the deep and global correlations among nodes [Fan et al., 2021]. However, the Self-Attention (SA) component within its encoder (as shown in Figure 1 (a)) brings quadratic complexity [Guo et al., 2023]. Some researchers replaced the SA with Linear Attention (LA) [Katharopoulos et al., 2020; Han et al., 2023]. The LA substitutes the Softmax operation with custom kernel functions, allowing it to decouple the computation and change the order to compute K⊤V first. This reduces the complexity from O(N 2 × d) to O(N × d2 ) [Han et al., 2023]. Nevertheless, these methods still face the following challenges:

(1) The recommendation accuracy decreased. In contrast to the Softmax, the kernel functions in LA do not incorporate nonlinear reweighting of the similarities between queries and keys. As a result, LA-based models struggle to accentuate the significant features within the attention map, resulting in a decreased prediction accuracy. Besides, these attentive calculations in Graph Transformer-based SRs overlook the item correlations among different training batches. Such an insufficient global weighting strategy also leads to a decrease in the model's performance [Guo et al., 2023].

(2) The parameter scale remains substantial. Although the application of linear attention reduces the computational complexity of global weighting [Katharopoulos et al., 2020], there still remains substantial learnable feature matrices in the stacked encoders of the Graph Transformer. Furthermore, for each encoder layer, the model repeatedly generates a set of Query, Key, and Value vectors for every input feature [Zhang et al., 2023a]. Such a strategy also diminishes the efficiency of the Graph Transformer-based models.

To tackle the above challenges, we propose a Communal Linear Attention-enhanced Graph TransFormer for Sequential Recommendation, namely CoLA-Former. Specifically, we introduce a communal linear attention mechanism with dual normalization (i.e., the CoLAttention presented in Figure 1 (c)). It employs low-rank communal units to linearly measure the item correlations on sequential graphs. With the usage of dual normalization, such a mechanism is able to reduce the model's sensitivity to the scale of input features, while focusing on significant features on the attention maps. Meanwhile, the communal units operate independently from the Graph Transformer's encoders and are reusable across various training batches. This design simultaneously enables the model to consider inter-batch item correlations and reduces the parameter scale. Furthermore, we devise a low-rank approximation component. It reduces the size of trainable parameters in the weight matrix via factorization and utilizes weight distillation to retain key features for the Graph Transformer. Experimental results on three real-world datasets indicate that CoLA-Former excels in both accuracy and efficiency over twelve state-of-the-art competitive methods.

The main contributions of this work are listed as follows.

• We propose a lightweight yet efficient Graph Transformer network for sequential recommendation, namely CoLA-Former.
• We present a communal linear attention mechanismwith linear computational complexity but only a minor loss of prediction accuracy.
• We optimize the structure of Graph Transformer to consider inter-batch item correlations and improve the parameter efficiency.
• We devise a low-rank approximation component that reduces the parameter scale and distills significant features for CoLA-Former.

2 RelatedWorks

Sequential Recommendation. Recently, researchers have applied various approaches for the SR task, including RNNbased techniques [Liu et al., 2024a; Yue et al., 2024], GNN-oriented methods [Zhang et al., 2024a; Zhang et al., 2023b], Transformer-inspired architectures [Du et al., 2024; Shi et al., 2024], and self-supervised learning strategies [Zhao et al., 2024; Liu et al., 2024b]. As one of the most representative graph-based SR methods, Graph Transformer [Luo et al., 2024; Li et al., 2023] has achieved remarkable performance. It enables the global weighting when learning node representations on the sequential graphs [Xia et al., 2023; Fan et al.,

2021]. However, these methods have quadratic complexity, hindering their deployment to the resource-constrained scenarios [Zhang et al., 2023a].

Lightweight Recommendation. Explorations of lightweight recommendation [Zhou et al., 2023; Xu et al., 2024; Zhang et al., 2024b] could be roughly classified into two categories. One is to compress the original collaborative matrices [Li et al., 2021; Zhou et al., 2023]. Another one is to optimize the model structures [He et al., 2020; Yue et al., 2024; Gao et al., 2024]. As for the Graph Transformer-based methods, one practical lightweight solution is to replace the SelfAttention (SA) with the Linear Attention (LA) mechanism [Katharopoulos et al., 2020; Han et al., 2023]. The LA significantly reduces the computational complexity by utilizing custom kernel functions [Liu et al., 2023]. However, these LA-based lightweight solutions inevitably decrease the recommendation accuracy of Graph Transformers, and their parameter scales remain substantial as well.

3 Methodology

3.1 Preliminaries

Notations

Let I = {I1, I2, . . . , In} be the set of all items, while U = {u1, u2, . . . , uk, . . . , um} denotes the set of all users, where uk represents the k-th user. The set of all sequences is defined as S = {S1, S2, . . . , Sk, . . . , Sm}, where Sk denotes the historical interaction sequence of uk. Subsequently, we specify the definition of Sk as Sk = {I k 1 , I k 2 , . . . , I k j , . . . , I k tk }, where I k j denotes the j-th interacted item in the sequence, tk is the length of the sequence. Furthermore, we define Pk = {pk1 , pk2 , . . . , pkj , . . . , pktk } as the set recording the exact position of each interaction within the sequence Sk. Pk ∈ P, and P denotes the set of all positional information.

Problem Definition

Given uk, Sk, and Pk, the SR task aims to suggest the subsequent item I k tk+1 that uk is likely to interact with. The probability of each candidate for recommendation is denoted as:

where P (I k tk+1 |uk, Sk, Pk) is the probability of recommending item I k tk+1 to uk, f(uk, Sk, Pk) denotes the approximation function for estimating the probability.

Sequential Graph Construction

The user behavioral sequences are treated as inputs of the model. We then utilize them to construct the sequential graph for CoLA-Former. Two types of associations are taken into consideration during the graph construction, i.e., user-item interactive relations and item-item sequential dependencies. The sequential graph is defined as G = {V, E}, where V denotes the set of nodes, and E represents the set of edges. The adjacency matrix A ∈ R(m+n)×(m+n) of the graph G is denoted as:

where RI→I ∈ Rn×n is the adjacency matrix carrying the sequential dependencies among items, each entry Rij is 1 if item Ij is the successor of item Ii, otherwise 0; RU→I ∈ Rn×m represents the user-item interaction matrix, each entry Rki is 1 if there is an interaction between user uk and item Ii, otherwise 0; RI→U ∈ Rm×n denotes the transpose matrix of RU→I .

3.2 Framework of CoLA-Former

The framework of CoLA-Former is shown in Figure 2. The model consists of four key components, i.e., the neighbor aggregation (Section 3.3), the stacked encoders (Section 3.4), the prediction layer (Section 3.5), and the low-rank approximation (Section 3.6). We elaborate on the above components in subsequent sections.

3.3 Neighbor Aggregation

The CoLA-Former model treats the sequential graph G as its input and initializes the node embeddings for items and users randomly at the initial layer. Specifically, the item embeddings E(0) I are initialized in Rn×d , and the user embeddings E(0) u are initialized in Rm×d . The architecture of the model comprises L graph convolution layers, where L is a hyper-parameter that determines the depth of the network. Inspired by LightGCN [He et al., 2020], CoLA-Former omits both feature transformation and nonlinear activation functions within the graph convolution operations, retaining only the neighbor aggregation mechanism for node representation learning. Due to the sequential nature of the input graph G, it requires additional consideration of the sequential dependencies between items during the message aggregation stage. In terms of other components, such as Laplacian regularization and the layer-wise message passing strategy, CoLA-Former maintains consistency with LightGCN's methodology.

Taking user uk as an example, the embedding of uk is denoted as euk ; the embedding of uk's interaction sequence Sk is represented as eSk , and the j-th item embedding within the sequence is denoted as eI k j . Then, the graph convolution operation at the l-th (0 < l < L) layer in CoLA-Former is defined as:

where Nu denotes the set of users that interact with item I k j , uq represents q-th user within Nu; NI denotes the set of neighbor items of I k j within multiple sequences, I k j-1 represents one of the neighbor items to I k j .

The node representations for all users E(l) u ∈ Rm×d and items E(l) I ∈ Rn×d at the l-th layer are denoted as:

where WU andWI denote the linear transformation matrix that aligns the dimensions of input features and the outputs.

3.4 Stacked Encoders

After the neighbor aggregation, we follow the principle of Graph Transformer [Xia et al., 2023; Sun et al., 2019] to refine the item embeddings via multiple encoders. As illustrated in Figure 2, β encoders are stacked at each graph convolution layer of the CoLA-Former. However, without any recurrence or located methods, the encoders are not aware of the order of the input sequence. To make use of the sequential information, we inject learnable positional embeddings EP into the input item embeddings EI at the bottoms of the stacks.

Learnable Positional Encoding

Since an item in the sequential graph belongs to multiple sequences with distinct positional information, the overlapping position encodings may interfere with one another. To this end, we introduce a learnable position encoding. It treats the position of each item as learnable vectors and maintains an external position matrix CP to preserve the vectors. Such a design allows the model to iteratively update the positional representations during the model training, reflecting the typical positions of items in the majority of users' sequences. For each item, we initialize its learnable position encoding by computing the average of its relative positions in varying sequences. Taking item I k j ∈ Sk as an example, its positional embedding epkj ∈ R1×d is initialized as:

where NS is the set of all sequences that contain item Ij, pkj is the absolute position of I k j in the sequence Sk.

Then, the position embeddings ePk ∈ Rtk×d of sequence Sk are detailed as ePk = [epk1 , epk2 , . . . , epkj , . . . , epktk ]. Finally, we obtain the Query vector QSk for sequence Sk by adding ePk to eSk , where eSk is the representation of Sk.

CoLAttention

After obtaining the query vectors for all sequences, the encoder utilizes CoLAttention to consider the global correlations within sequences. Different from the self-attention [Chen et al., 2023] and linear attention [Liu et al., 2023], the key vectors and value vectors in CoLAttention are derived from two low-rank communal units, i.e., CK ∈ Rd×α and CV ∈ Rd×α. As the dimensions of the communal units are much lower than that of the input sequence representations (i.e., α ≪ tk), the complexity of CoLAttention approximates linearity, i.e., O(n×α× d). Besides, these communal units are reusable and shared across multiple encoders and training batches. This design improves the parameter efficiency and makes the significant features from the attention maps transmissible.

The calculation of CoLAttention is depicted in Figure 1 (c), which is formulated as:

where ai,j ∈ Rtk×α represents the low-rank attention map of CoLAttention, ˆeSk ∈ Rtk×d is the refined sequence representations, α denotes the hyper-parameter that controls the dimension of communal units.

Instead of using the softmax function which is sensitive to the scale of input features, we adopt a double normalization [Guo et al., 2023] from the field of computer vision to the CoLAttention. Such a mechanism separately normalizes columns and rows of the attention map ai,j, mitigating the sensitivity and enhancing model performance. After detailing the calculation for each single attention head, we define the sequence representations weighted by multiple heads as {ˆe(1) Sk , ˆe(2) Sk , . . . , ˆe(v) Sk , . . . , ˆe(h) Sk }, where h is the head number. Then, the refined sequence embeddings ¯eSk are formulated as:

where WM is the learnable weighting matrix.

Subsequently, we perform an residual link to obtain the updated representations ˜eSk .

Point-wise Conv1D

The multi-head attention structure in CoLAttention is adept at capturing long-range dependencies. However, the model still struggles to capture the local features and short-range dependencies within sequences [Kreuzer et al., 2021]. To this end, we develop a lightweight local weighting layer via a pointwise Conv1D layer, which operates on each individual item embedding of ˜eSk and their immediate neighbors. This localized operation allows the model to focus on short-range dependencies and patterns. Specifically, both the kernel size and the stride of the point-wise Conv1D are set to 1 for linearly local weightings [Wu et al., 2023b]. The calculation is denoted as:

where ∗ denotes the one-dimensional convolutions, Wc ∈ Rd×d represents the convolution kernel, bc ∈ R1×d is the bias term.

By incorporating point-wise Conv1D layers into the stacked encoders, CoLA-Former strikes a balance between capturing both local and global information. We perform another residual link to generate the output representations ˜zSk . Then, the refined representations of all items E(t) I in the t-th

(0 < t < β) encoder are derived as:

whereWS denotes the learnable transformation matrix.

The refined item representations from the t-th encoder are treated as the input of the (t + 1)-th encoder. We define the output item embeddings of the β encoder as the output item representations ˆE(l) I ∈ Rn×d for the l-th CoLA-Former layer.

3.5 Prediction Layer

Follow the Multiple Layer Aggregation Protocol (MLAP) in LightGCN [He et al., 2020], the summed representations for all users and sequences are resulted by aggregating embeddings frommultiple convolution layers:

where EU and ES denote the resulted node representations for users and sequences, respectively.

After obtaining the final sequence representation ES, we concatenate it with the user representations EU , and then feed them into the prediction layer (as shown in Eqn. (14)).

where Wf ∈ Rn×2d represents the weighting matrix that transforms the dimensions of predictions to the number of all candidates, bf ∈ Rn×1 is the bias term that adjusts the activation threshold.

Then, we minimize the cross-entropy loss function LCE to optimize the learnable parameters, which is formalized as:

3.6 Low-Rank Approximation

The integration of CoLAttention has successfully diminished computational complexity and augmented parameter efficiency. Nevertheless, the stacked encoders still retain a significant quantity of learnable weighting matrices. Inspired by the success of low-rank approximation in Computer Vision [Guo et al., 2024], we propose to apply this technique to the CoLA-Former to further reduce the parameter scale.

Factorization

We assume that all the learnable weights in the stacked encoders are denoted as WE ∈ Rdin×dout . Then, we factorize the matrix as:

where X denotes the input features that are multiplied by the learnable feature matrices within the stacked encoder architecture, UE ∈ Rdin×γ and VE ∈ Rdout×γ are low-rank matrices, γ controls the rank.

Referring to the setting of PELA [Guo et al., 2024], we seek the low-rank approximation of the original matrix and deliberately choose a smaller γ= 14 min(din, dout). Then, we exploit the well-known SVD approach [Wu et al., 2022] to perform the low-rank approximation as:

where Σ ∈ Rdin×dout is the singular value matrix, U∗ ∈ Rdin×din and V∗ ∈ Rdout×dout are complex unitary matrices. Then, the low-rank matrices are formalized via the following transformation (i.e., truncated singular value decomposition):

The resulting approximated weight matrix ˆWE is denoted as:

Weight Distillation

Although the application of truncated Singular Value Decomposition successfully reduces the scale of the learnable matrix, it inherently leads to the loss of features. To this end, we further propose a weight distillation component to align the weights of the approximated weights ˆWE with the original weights WE. For β layer stacked encoders, the weight distillation loss is defined as follows:

where M is the identity mapping method that transfers the feature to the target feature space. In this way, the output features from each encoder layer of the low-rank model are expected to share a similar distribution with that of the original one.

4 Experiments

In this section, we conduct experiments to demonstrate the superiority of CoLA-Former in terms of the prediction accuracy and model efficiency. We aim to answer the following four Research Questions.

• RQ1: What is the performance of CoLA-Former in terms of the prediction accuracy on the SR tasks?
• RQ2: How is the training efficiency and parameter scale of CoLA-Former compared with other state-of-the-art methods?
• RQ3: What is the contribution of key components to CoLA-Former for the recommendation performance?
• RQ4: How do the hyper-parameters affect the performance of CoLA-Former?

4.1 Experimental Setups

Datasets

We evaluate the performance of CoLA-Former on three realworld datasets, i.e., Amazon-Food, Douban and MovieLens. Specifically, Amazon-Food dataset is a collection of food product reviews from Amazon, encompassing a vast array of items and customer feedback recommendation research [Xia et al., 2023]. MovieLens dataset is a widely-used collection of movie ratings provided by the GroupLens Research Project, offering a rich resource for collaborative filtering and recommendation system studies [Gao et al., 2024]. Douban dataset contains book reviews and ratings from the Chinese social media platform Douban, which is utilized for sentiment analysis and recommendation research [Zhang et al., 2023a].

Evaluation Metrics

In experiments, two common evaluation metrics are adopted to assess the performance of CoLA-Former, i.e., Top-N Recall (RC@N) [Yue et al., 2023] and Top-NMean Reciprocal Rank (MRR@N) [Zhang et al., 2023a], where N={5, 20}.

Implementation Details

CoLA-Former is implemented with Pytorch 2.1.2. The model training is accelerated via NVIDIA® RTX 3090 (24GB) GPU. We employ the Xavier [Glorot and Bengio, 2010] for the initialization of the learnable parameters and treat Adam [Kingma and Ba, 2015] as the optimizer. For the model training, we set the batch size as 256 and the dropout rate as 0.2. The learning rate is set to 0.003 for Amazon-Food, 0.001 for MovieLens, and 0.001 for Douban. Besides, we uniformly set the embedding size to 64 for CoLA-Former and other competitive baselines to ensure the fairness of experimental results. As for other hyper-parameters of baselines, we follow the optimal setup reported in their papers and fine-tune them on each dataset.

Baselines

To validate the effectiveness of CoLA-Former, we compare its performance with 12 competitive baselines: 1) Sequential Recommendations (SRs). SASRec [Kang and McAuley, 2018]; S3 -Rec [Zhou et al., 2020]; MLSI [Hu et al., 2024]; RDCRec [Zhao et al., 2024]; 2) Lightweight Sequential Recommendations (LSRs). LSAN [Li et al., 2021]; LRURec [Yue et al., 2024]; SMLP4Rec [Gao et al., 2024]; 3) Graph-based Sequential Recommendations (GSRs). SURGE [Chang et al., 2021]; TGSRec [Fan et al., 2021]; GCL4SR [Zhang et al., 2022]; TGT [Xia et al., 2023]; MG-Former [Luo et al., 2024].

4.2 Prediction Performance (RQ1)

Table 1 shows the comparison of prediction accuracy between CoLA-Former and the other twelve competitive methods. The observations and analysis are given as follows: 1) Most GSRs (i.e., TGSRec, GCL4SR, TGT, MG-Former, and CoLA-Former) exhibit superior predictive performance compared to other sequential recommendation methods. This observation indicates that GSRs excel in capturing the intricacies of user interactions and the dependencies inherent in sequential data. 2) CoLA-Former achieves the best performance on each evaluation metric across all datasets, demonstrating the effectiveness of our proposed model in addressing the SR tasks. 3) CoLA-Former outperforms the recently proposed LSRs (i.e., LSAN, LRURec, SMLP4Rec). This observation indicates that CoLA-Former achieves an optimal trade-off between lightweight efficiency and predictive precision compared to other lightweight approaches. 4) CoLAFormer exhibits superior performance compared to other Graph Transformer-based GSRs (i.e., TGSRec, TGT, and MG-Former). This observation indicates that our lightweight design has not decreased the recommendation accuracy of the Graph Transformer but has even improved it.

4.3 Lightweight Performance (RQ2)

In this section, we validate the lightweight design performance of CoLA-Former by comparing its time consumption and parameter scale with the most competitive baselines (i.e., LRURec, SMLP4Rec, TGT, MG-Former).

Time Consumption. We vary the proportion of the input data to be {0.2, 0.4, 0.6, 0.8, 1.0} on three datasets to assess the training time consumption of different methods. As shown in Figure 3 (a) to (c), CoLA-Former requires less training time than recently proposed LSRs (i.e., LRURec and SMLP4Rec) and Graph Transformer-based GSRs (i.e., TGT and MG-Former), demonstrating improved training efficiency. Moreover, the time consumption of CoLA-Former increases at a much slower pace than the other baseline methods as the dataset size grows, highlighting its superior scalability for large-scale data.

Parameter Scale. We also compare the parameter scale of CoLA-Former with the other competitive methods. As depicted in Figure 3 (d), CoLA-Former requires fewer parameters than other Graph Transformer-based GSRs (i.e., TGT and MG-Former). This observation demonstrates that the lightweight design within CoLA-Former effectively diminishes the parameter scale of the Graph Transformer, resulting in enhanced lightweight performance. Besides, CoLAFormer requires notably fewer learnable parameters than the other LSR methods, making it more suitable for resourceconstrained SR scenarios.

4.4 Ablation Studies (RQ3)

In this section, we perform a series of ablation studies across two datasets (i.e., MovieLens and Douban) to assess the contributions of each component within CoLA-Former. The details of variant methods are as follows: 1) CoLAr/p SA denotes the variant method that replaces the CoLAttention with selfattention. 2) CoLAr/p LA represents the variant that replaces the CoLAttention with linear attention. 3) CoLAw/o P denotes the variant that removes the learnable positional encoding. 4) CoLAw/o C1D is the variant that removes the Point-wise Conv1D. 5) CoLAw/o LRA denotes the variant that disables the low-rank approximation. 6) CoLAw/o ALL is another variant that disables all components in CoLA-Former.

From Table 2 and Figure 4, we have the following observations: 1) CoLA-Former and CoLAw/o LRA significantly outperform CoLAr/p SA and CoLAr/p LA in both prediction accuracy and parameter consumption, showcasing the superiority of the CoLAttention. 2) CoLA-Former and CoLAw/o LRA achieve better prediction performance than CoLAw/o P and CoLAw/o C1D, demonstrating the effectiveness of the learnable positional encoding and the pointwise Conv1D. 3) CoLA-Former has similar predictive performance with CoLAw/o LRA, but with a significantly reduced parameter scale. This observation indicates that our low-rank approximation component achieves a reasonable trade-off between prediction accuracy and parameter scale.

4.5 Hyper-parameters Analysis (RQ4)

1) The hyper-parameter α controls the dimension of the communal units. Figures 5 (a) to (c) present the performance of CoLA-Former for different α values in {16, 32, 64, 128, 256} across three diverse datasets. The experimental results show that varying α values do not significantly affect the model's predictive capabilities. In other words, CoLA-Former is able to function with a lower alpha value (even the α is set to 16), highlighting its lightweight efficiency. 2) The hyperparameter L controls the depth of the convolutional layer. As depicted in Figures 5 (d) to (f), CoLA-Former exhibits optimal performance at the layer depth of 2, which is in line with the majority of graph convolution-based models. 3) β and h are two significant hyper-parameters that control the number of encoder layers and attention heads, respectively. As shown in Figures 5 (g) to (i), CoLA-Former reaches the best performance on all datasets when β=3 and h=2. This observation indicates that the model's efficacy in sequential recommendation tasks is not directly proportional to the number of attention heads or encoders. Optimal performance is achieved with a judiciously selected minimal number of these components.

5 Conclusion

In this work, we introduce a lightweight Graph Transformerbased GSRs called CoLA-Former. In its encoder, we design the CoLAttention to linearly consider the inter-batch global correlations among items. This design achieves linear complexity of global weighting but with less loss of the prediction accuracy. Moreover, we present a low-rank approximation component. It factorizes the high-dimensional weight matrix into two smaller matrices and preserves the significant features via weight distillation. Such a component significantly reduces the scale of the learnable weights.

Acknowledgments

This research is supported by the National Natural Science Foundation of China (Grant No. 62472263, 52374221, 62072288, 62176243), the National Key R&D Program of China (Grant No. 2022ZD0119501), the Taishan Scholar Program of Shandong Province, Shandong Youth Innovation Team, the Natural Science Foundation of Shandong Province (Grant No. ZR2024MF034, ZR2022MF268).