DGR: A General Graph Desmoothing Framework for Recommendation via Global and Local Perspectives

1 Introduction

Personalized recommendation is a vital technology in various domains, such as social media, e-commerce, and career recommendation, aiming to recommend items based on users' interests by mining and matching the embeddings of users and candidate items [Wang et al., 2021b; Wang et al., 2021a; Li et al., 2024]. The interaction information between users and items can naturally be represented as a bipartite graph, making Graph Convolutional Networks (GCNs) [He et al., 2020] an effective approach to learning user and item embedding vectors. Specifically, conventional GCN-based recommendation models, such as NGCF [Wang et al., 2019a], LightGCN [He et al., 2020] and DGCF [Wang et al., 2020b] exclusively leverage the message passing mechanism to aggregate local information and directly incorporate the signals captured from historical interaction data into the embedding vectors, which have witnessed both the training efficiency and better performance.

∗Chao Wang and Yanyong Zhang are both corresponding authors

Unfortunately, as mentioned in [Chen et al., 2020b; Liu et al., 2021; Chen et al., 2022a; Cai et al., 2023; Zhou et al., 2023; Peng et al., 2022; Wang et al., 2023b; Xia et al., 2023], GCN-based recommendation models face the inherent over-smoothing problem, where all user and item embeddings converge toward similarity during the message passing process. It causes a failure in personalized recommendation, resulting in the same recommendation results for every user [Zhou et al., 2023]. Moreover, data in recommendation systems are often highly sparse, making it more difficult to model relationships between users and items due to limited direct user-item interaction information. Consequently, the existing GCN-based recommendation struggles to accurately capture the differences in the fine-grained relationships among users and items.

Recently, significant efforts have been devoted to addressing the over-smoothing problem in GCN-based recommendation. For example, many well-known GCN-based recommendation models, such as LightGCN [He et al., 2020] and NGCF [Wang et al., 2019a], opt to incorporate outputted embeddings from each layer into the final readout embeddings, preserving node information characteristics and slightly alleviating the over-smoothing problem. Meanwhile, there are also some works proposed to adjust the message passing processes [He et al., 2023; Peng et al., 2022; Liu et al., 2021] or adopt self-supervised learning to maintain the distinctiveness of user and item embeddings [Xia et al., 2023; Xia et al., 2022; Cai et al., 2023; Wu et al., 2021; Lin et al., 2022]. However, most of these approaches are specifically designed for individual models, leaving a strong need for a general desmoothing framework in GCN-based recommendation systems.

Indeed, to make full use of the sparse information from the user-item interactions, it is essential to take into consideration both the global and local topological perspectives with model-free solutions. Specifically, on the one hand, with the mathematical nature of the global topological structure, the message passing mechanisms in existing GCN models often lead to the rapid convergence of all node embeddings and cause over-something. Therefore, the first challenge lies in modifying the message passing layer to distinguish user item embeddings. On the other hand, local collaborative relations, which encourage similar embeddings for the neighbors, are also critical for recommendation performance [Wang et al., 2023a; Mao et al., 2021]. It is also challenging to mine those collaborative signals from the local topological structure during desmoothing process.

In this paper, we introduce the Desmoothing Framework for GCN-based Recommendation Systems (DGR), a novel, universally applicable, and easy-to-use approach to tackle the over-smoothing problem from both global and local perspectives and enhance personalized recommendation in GCNbased recommendation systems. Our approach encompasses two primary modules: Global Desmoothing Message Passing (GMP) and Local Node Embedding Correction (LEC). The GMP module is designed to counteract the global trend of user and item embeddings approximating overly to the limit state of infinite-layer graph convolutions, i.e., the oversmoothing point. It introduces vector perturbations at each layer to steer embeddings away from the over-smoothing point. Simultaneously, the LEC module focuses on preserving and emphasizing the local collaborative signals, particularly in sparse data scenarios. It works by maintaining local collaborative relationships between users and neighboring items and incorporating highly correlated items to strengthen the local topological information. Differing from previous methods that targeted improvements in individual GCN-based recommendation systems, our DGR framework is a general, model-free solution, easily adaptable across various GCN-based models. To substantiate our claims, we have rigorously tested DGR with five popular recommendation models across five public benchmark datasets. The results from these extensive experiments, along with several case studies, have convincingly demonstrated the effectiveness and broad applicability of our framework in enhancing personalized recommendations in GCN-based systems.

2 Preliminaries

In this section, we first introduce the essential background knowledge about GCN-based recommendation systems and the concept of the over-smoothing point.

2.1 GCNs in Recommendation Systems

GCNs are the representative models for complex graphstructured data [Wang et al., 2023c; Chen et al., 2022b; Chen et al., 2022c] and have obtained great success in recommendation, where the interaction information between users and items can naturally be represented as a bipartite graph [Wu et al., 2024]. LightGCN is one of the foundational frameworks for many GCN-based recommendation models [Cai et al., 2023; Yu et al., 2023; Shuai et al., 2022]. It simplifies GCNs by eliminating non-linear feature transformations, retaining only the message passing. Each layer is defined as:

where E(k) ∈ R(Nu+Ni)×T is the k-th layer node embedding matrix, T is the embedding size, Nu and Ni denote the number of users and items, ˜A ∈ R(Nu+Ni)×(Nu+Ni) is the normalization of the adjacent matrix A of the user-item graph with self-loop, i.e.,

where R ∈ RNu×Ni is the user-item interaction matrix, each entry Rui is 1 if user u has interacted with item i otherwise 0. INu and INi are identity matrics with sizes of Nu and Ni, respectively. ˆDis a (Nu+Ni)×(Nu+Ni) diagonal matrix, in which each entry ˆDij denotes the number of nonzero entries in the i-th row vector of the adjacency matrix A.

Note that, the initial definition of the LightGCN layer has removed the self-loop connections on nodes. However, as the original paper claims, the layer combination operation plays a similar role by summing the weighted node embeddings at each layer as the final output representation. Along this line, we can rewrite the above message passing process for user embedding eu and item embedding ei as follows,

where Vu and Vi denote the neighbor node set of user u and item i with size of du and di, respectively. The readout node embeddings eu and ei are the combination of embeddings outputted by each message passing layer. Then, the model prediction is defined as the inner product of user and item final embedding representations:

which is used as the ranking score for recommendation. Meanwhile, the Bayesian Personalized Ranking (BPR) loss is employed, which is a pairwise loss that encourages the possibility of an observed interaction to be higher than its unobserved counterparts, i.e.,

where σ(·) is the sigmoid function, D = {(u, i, j) |Ru,i = 1,Ru,j = 0} denotes to the pairwise training dataset, and j denotes the sampled item that user u has not interacted with.

2.2 Over-Smoothing Point

However, the GCN-based recommendation usually suffers performance degradation as the number of message passing layers k increases due to the well-known over-smoothing problem [He et al., 2020; Wang et al., 2019b]. Specifically, the node embedding ek (the row of E(k) ) will all converge to the corresponding final point when k tends to infinity, called the over-smoothing point. Theoretically according to Theorem 1 in [Chen et al., 2020c], we can derive that:

where du,di represent the degrees of user node u and item node i, respectively. Nedge is the total number of edges in the user-item graph. We can then obtain Over-smoothing Steady State Matrix M via:

where we denote the over-smoothing point as m, which is the row of M. According to [Chen et al., 2020c], the rows of M are linearly correlated with each other. In other words, the high-order power of normalized adjacent matrix ˜A tends to undergo a rank collapse as k increases.

Actually, in the context of recommendation, the oversmoothing problem can be more serious due to the long tail and the high sparsity. On the one hand, in the item-user graph, most interactions occur on the popular users or items, which have a higher degree than most common nodes. As a result, with Equation 7, those nodes' embeddings would converge at a higher rate and have a stronger impact on pushing the convergence of other nodes' embeddings. On the other hand, the high sparsity makes nodes interact more with local neighborhoods, due to limited direct user-item interactions. As a result, the node embeddings prefer to converge more rapidly.

To provide visual insights of the evolution of the node embeddings as the layer number of message-passing increases, we conduct an empirical analysis on MovieLens1M dataset in Figure 1 to illustrate the evolution of user or item embeddings during the message passing process. Specifically, we calculate the distance between all node embeddings and oversmoothing steady state matrix as follows:

where D (E(k) ,M) is the mean Euclidean distance between the k-th layer node embeddings E(k) and over-smoothing steady state matrix M. The e(k) i and mi are the i-th row of E(k) and M respectively. Figure 1 shows a rapidly decreasing trend as the layer k increases, indicating that node embeddings tend to converge towards the over-smoothing point as the layer number of message-passing increases. This convergence phenomenon poses a risk of recommendation failure.

3 Our Framework

In this section, we present the technical details of our proposed Desmoothing Framework for GCN-based Recommendation Systems (DGR). As shown in Figure 3, our DGR model is a model-free approach and can be exploited for enhancing various GCN-based recommendation systems by plugging into two components: Global Desmoothing Message Passing (GMP) and Local Node Embedding Correction (LEC), which prevents global user and item embeddings from over-smoothing point but maintain similarities among their neighbor nodes. In the following, we will introduce those two components respectively, with a necessary analysis of the complexity.

3.1 Global DesmoothingMessage Passing

As discussed in Section 2.2, due to the mathematical nature of global topological structure, the embedding e(k) ∈ E(k) of each user or item will converge to the corresponding oversmoothing point m ∈ M as stacking GCN layers. As a result, each user or item embedding is linearly correlated with each other and cannot be distinguished. To prevent the oversmoothing problem, an effective way is to slow down the convergence rate during each message passing step. Along this line, we propose a simple but effective plug-in module after each message passing layer to perturb the node embeddings away from the final over-smoothing point. Figure 2 provides an illustrative understanding of our proposed approach.

Specifically, the black curve represents the updating trajectory of an embedding vector for a user or an item, approximating the over-smoothing point (the red point). After the k-th original message passing steps, the node embedding evolves from e(k-1) to ˆ e(k) as Equation 3. We denote the updating vector as ⃗a = ˆ e(k) - e(k-1) . It can be decomposed into two orthogonal components ⃗b and ⃗c, where ⃗b is parallel to the direction of ek-1 -m and ⃗c is perpendicular to it. Intuitively, ⃗b pushes the embedding vector to the corresponding

𝐆𝐥𝐨𝐛𝐚𝐥 𝐃𝐞𝐬𝐦𝐨𝐨𝐭𝐡𝐢𝐧𝐠 𝐌𝐞𝐬𝐬𝐚𝐠𝐞 𝐏𝐚𝐬𝐬𝐢𝐧𝐠

𝐋𝐨cal Node Embedding Correction

over-smoothing point. Therefore, we punish the vector updating in this direction with a parameter α:

where N denotes the set of neighbor items or users, and AGG denotes the aggregation operation defined in Equation 3. Note that ⃗b and m - ˆe(k) have the same direction (without sign) but different scales. Here, we use the latter to perturb the node embedding, abstaining from the use of matrix orthogonal decomposition in the computation, which enhances both robustness and usability.

Our approach to desmooth during message passing is characterized by its simplicity and intuitive nature. In practice, it has demonstrated remarkable effectiveness. Actually, we can also validate the effectiveness with the following proposition.

Proposition 1. With the plug-in module defined in Equation 9, the distance between any node embedding e and the corresponding over-smoothing point m would increase, i.e,

where || · ||p is the p-norm distance between vectors.

The proof is obvious by bringing Equation 9 into Equation 10. The above inequality suggests that our approach prevents the collapse of user or item embeddings into the oversmoothing point by increasing the distance between them.

3.2 Local Node Embedding Correction

In this subsection, we further focus on how to deal with the over-smoothing problem from the local graph perspective. Differently from the global view, the similarities between some local neighbor nodes are beneficial for collaborative filtering. It is challenging to maintain collaborative relations from local user-item interactions while maintaining distinctiveness among all node embeddings.

Here, we propose a general additional loss for GCN-based recommendations to handle the local user and item embedding learning process. Intuitively, the main idea is to preserve the similarity of the readout embeddings of highly neighbor and correlated item and user nodes. Meanwhile, The borders between similar nodes and unrelated nodes are referred to as the boundary nodes. Previous studies [Abbasnejad et al., 2020; Goyal et al., 2019; Wang et al., 2021c] have shown that samples in boundary nodes are often discriminative in revealing underlying data patterns, offering the potential for improved model performance. Therefore, we also hope to increase the divergence among those of boundary nodes. As shown in Figure 3, given a positive pair of the user u (like u1) and the clicked item i (i3), we first sort other neighbor item nodes i′ (i4, i5) based on the distance metric between two items i and i′ . Items with lower distances are considered to have higher correlation (similar nodes sim) and nodes with higher distances are considered marginal nodes mar. The numbers of similar nodes and marginal nodes are set as K1 and K2. Then, the additional loss term is defined as follows: LLEC =

where N + denotes the positive pairwise training dataset, S(i) is the set of similar nodes about node i, M(i) is the set of marginal nodes about node i, and ωu,sim , ωu,mar are the normalization coefficients. In particular, when sorting the items, we filter out the items far enough away from the node i whose distance is above a threshold θ to only preserve boundary nodes inspired by [Wang et al., 2021c]. Here, we apply the co-occurrence similarity as the distance metric between two items, which is proportional to the number of users linked to both two items. Note that, the co-occurrence similarity is consistent with the idea of collaborative filtering [Wang et al., 2020a; Chen et al., 2021]. Hence the loss can be effectively adopted and added to common GCN-based collaborative filtering models. The overall algorithm process of our LEC loss can be found in Appendix.

With our proposed LEC, we finally derive the following training objective for GCN-based recommendation models:

where LCF represents the original loss function of the GCNbased recommendation model like BPR loss in Equation 5, and hyper-parameter λ is to balance the LEC loss.

3.3 Comparison with ExistingMethods

Recently, several works in the field of GCNs have been proposed to alleviate the over-smoothing problem. Here, we discuss the relations between our approach with them to provide a more comprehensive understanding.

Residual Connection. Motivated by the success of ResNet [He et al., 2016], the residual connection has been the common sense to make GNNs go deeper and perform better, like LT-OCF [Choi et al., 2021], LightGCN [He et al., 2020], SGC [Wu et al., 2021], DeepGCN [Li et al., 2019], and GCNII [Chen et al., 2020c]. Taking GCNII as an example, it incorporates initial node embeddings into the output of each layer, which can be succinctly summarized as:

where ˆe(k) and e(0) are defined similarly to that in Equation 9. Intuitively, like our GMP approach, GCNII also perturbs the original node embedding ˆe(k) with another vector (e(0) - ˆe(k) ) of the direction moving away from oversmoothing point. The illustration of detailed embedding vector updating can be found at Appendix, which is considered to be a hidden reason that GCNII can also prevent embeddings from excessively converging to the over-smoothing point.

Normalization-based Methods. A proven way to reduce the over-smoothing effect is to normalize node embeddings to preserve the distinctiveness of embeddings during training. EGNN [Zhou et al., 2021a] and Parinorm [Zhao and Akoglu, 2019] measure over-smoothing using Dirichlet energy and Total Pairwise Squared Distance(TPSD) respectively and optimize a GCN within a constrained range of Dirichlet energy and TPSD to preserve the distinctiveness of node embeddings individually. Additionally, Differentiable Group Normalization (DGN) [Zhou et al., 2020] and NodeNorm [Zhou et al., 2021b] use node-wise normalization. Although they maintain the embedding distances between nodes to avoid excessive similarity among global node embeddings in the optimization process, these methods of optimizing node embeddings lack any directionality and can even introduce noise that affects the performance of shallow GCN models. DGR maintains node embedding distinctiveness while providing a clear direction, which is to move away from over-smoothing point. Moreover, its application to shallow GCN models also leads to substantial improvements while normalization-based methods lead to a performance decrease.

Topology-based Methods. Some other approaches propose to modify the topological structure in each message passing layer to alleviate over-smoothing by randomly dropping edges or nodes in graphs, such as DropEdge [Rong et al., 2019] and AdaEdge [Chen et al., 2020a]. However, those approaches also damage the local topological structure around each node to some extent, which is critical in recommendations for modeling collaborative signals. In contrast, our approach not only penalizes the tendency of node embeddings approximating overly to be similar, but also maintains the topological structure and similarities among neighbor nodes.

Consequently, our method yields a more stable performance enhancement for recommendation. Another topology-based model IMP-GCN [Liu et al., 2021] groups users with similar interests based on topological relationships and conducts separate message passing for each group to alleviate oversmoothing problem, which has the similar main idea with our proposed LEC, encouraging similar nodes to have comparable embeddings on the local graph.

3.4 Complexity Analysis

Actually, our approach is easy-to-use and model-free, which can be exploited into various GCN-based recommendation systems with a limited complexity cost. Assuming the original LightGCN backbone, the computational complexity can be represented as: O((Nu+Ni) ¯ dTK), where T is the dimensionality of node embeddings, K is the number of graph convolutional layers, and ¯ d is the average number of neighboring nodes. After applying our DGR, the computational complexity becomes: O((Nu + Ni)( ¯ d + 1)TK). It can be observed that DGR only brings a limited linear increase in computational complexity. As for the space complexity, DGR only introduces additional (Ni+Nu)T parameters into the original GCN backbone. Furthermore, our experiments will demonstrate significant and robust improvements in DGR across various datasets and recommendation systems.

4 Experiments

To verify the effectiveness of the proposed DGR, we conduct extensive experiments based on five public benchmark datasets and report detailed analysis results in the section.

4.1 Experimental Setup

Datasets and Evaluation. Following many recent GCNbased recommendation systems [He et al., 2020; Mao et al., 2021; Yu et al., 2023], five public benchmark datasets are used in our paper including Gowalla, Yelp2018, MovieLens1M, Netflix and Douban-Book. These datasets vary in domains, scale, and density. The statistics of the datasets can be found in Appendix. We partitioned each dataset into training, and testing sets using a 4:1 ratio. Recall@K and Normalized Discounted Cumulative Gain (NDCG)@K are chosen as the evaluation metrics that are popular in the evaluation of GCN-based recommendations.

Baseline Models. To demonstrate the generalizability, we incorporate our DGR into five widely-use GCN-based recommendation models including LightGCN [He et al., 2020], SGL [Wu et al., 2021], SimGCL [Yu and Qin, 2020], XSimGCL [Yu et al., 2023] and MixGCF [Huang et al., 2021]. In addition, we include two traditional recommendation models, BPRMF [Rendle et al., 2012] and NGCF [Wang et al., 2019b]. The latest state-of-the-art models, IMP-GCN and LayerGCN [Zhou et al., 2023], are also included, which effectively mitigate the over-smoothing promblem in recommendation systems.

Experimental Setting. The experimental implementation details can be found in Appendix.

4.2 Overall Performance

Table 1 summarizes the comparison of baseline models before and after integrating the proposed DGR with the percentage of relative improvement at each metric. The main observations are as follows:

(1) The baseline models incorporating DGR all exhibit performance improvements on all datasets, while also achieving state-of-the-art results. It demonstrates the effectiveness of the DGR, which unlocks the potential of personalized recommendation for GCN-based recommendation systems by mitigating the over-smoothing problem. In the vast majority of cases, the five popular models with DGR significantly outperform competitive traditional and recent state-of-the-art models. Baselines and Baselines with DGR in Table 1 apply the same layers of GCNs, which demonstrates that our proposed DGR can significantly improve shallow GCN-based recommendation models.

(2) Compared to all other models, DGR yields the substantial improvement for XSimGCL and SimGCL among all datasets. In particular, XSimGCL with DGR achieves a remarkable increase of 11.21% in Recall@20 and 16.22% in NDCG@20 on the MovieLens1M. We believe that XSimGCL and SimGCL employ the approach of adding noise to node embeddings instead of using complex data augmentation for graph self-supervised learning. This method may not effectively leverage topological information in the local graph, and introducing noise makes the model directionless. In contrast, DGR enables them to maintain distinctiveness among all user and item embeddings under the guidance of global topology while paying closer attention to the local topological information of local user-item interactions, leading to the enhanced performance.

(3) Comparing the performance on different datasets, DGR exhibits the substantial average improvement on MovieLens1M among all baseline models, which has the highest density, at 2.7%. The DGR can improve recommendation performance remarkably by slowing down its tendency towards over-smoothing. Meanwhile, DGR also has stable improvements on sparse datasets such as Yelp2018 with 0.13% density. This is because DGR can effectively utilize the limited neighbors of each user (item) node to capture collaborative signals by learning on the local graph.

4.3 Further Analysis of DGR

In this section, we provide more experimental analysis of our proposed DGR for better understanding.

Ablation Study of DGR. We conduct the ablation experiments on Douban-Book by individually applying GMP, LEC, and DGR on different models. From Table 2, we can find that both GMP and LEC contribute to the improvements of model performance. The performance improvements provided by DGR is greater than the sum of the performance improvements from GMP and LEC, which implies that the synergistic combination of these two components is better suited for the desmoothing task in the context of recommendation. Additionally, we observe that GMP leads to a more remarkable performance improvement than LEC in LightGCN, SGL, and SimGCL. However, this trend is reversed in XSimGCL and MixGCF. We believe the primary reason is that the first three models are already capable of effectively capturing collaborative information during the aggregation of neighboring items(users), which makes global over-smoothing their performance bottleneck. Meanwhile, the latter two models are perceived as lacking the ability to capture collaborative signals from user-item interactions.

Case Study. The Row-diff is a metric to measure the degree of over-smoothing, proposed by [Zhao and Akoglu, 2019], where a lower row-diff score indicates a larger degree of oversmoothing. Its calculation formula is as follows:

where E(k) is the node embedding matrix obtained after training k layers of GCN until convergence. In order to validate the ability of DGR to mitigate over-smoothing, we separately train baseline models and baseline models with DGR until convergence to obtain a converged embedding matrix. The row-diffs of node embeddings are computed respectively and shown in Table 3. It is evident that the application of DGR to the baseline models leads to a significant reduction in the degree of over-smoothing.

Impact of Model Depth. Although the DGR significantly enhances the shallow GCN-based recommendations as shown in Table 1, further exploration is needed to understand its desmoothing ability in deep GCN-based recommendations. We evaluate the five models with and without DGR across a range of model depths. We conduct these experiments on the Douban-Book dataset. The results of LightGCN are shown in Figure 4 while the results of other models can be found in Appendix. It is notable that models with DGR display a slower decline in performance as the number of layers increases, in contrast to those without DGR. This observation suggests that DGR possesses a robust desmoothing capability, which can effectively alleviate the detrimental effects of over-smoothing on recommendation performance in deep models.

Impact of hyper-parameters. As mentioned in Equation 9, the hyper-parameter α determines the extent to which all embeddings deviate from the over-smoothing point. It has a significant impact on the model performance. Here, We take LightGCN as the representation example to incorporate our DGR model with varying α values on Douban-Book dataset as shown in Figure 5, while the results of other models can be found in Appendix. The optimal value of α varies across different layers. Therefore, we explore the optimal α separately for each layer across a range of values, i.e., [0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0].

5 Conclusion

In this work, we proposed a general and easy-to-use Desmoothing Framework for GCN-based Recommendation Systems(DGR), to alleviate the over-smoothing problem in GCN-based recommendation systems, thereby unlocking the potential for personalized recommendation. We approached this problem from both global and local perspectives. Specifically, with the guidance of the global structure, we introduced Global Desmoothing Message Passing(GMP), which penalizes the tendency of node embeddings approximating overly to be similar. In addition, we introduced Local Node Embedding Correction (LEC) for the readout embeddings to preserve the local collaborative relations between users and their neighboring items in the local graph. Extensive experiments based on five public datasets and five popular GCNbased recommendation models have demonstrated the effectiveness of our proposed DGR.

Acknowledgements

This work was partially supported by Project funded by China Postdoctoral Science Foundation (Grant No.2023M730785).