Graph-enhanced Optimizers for Structure-aware Recommendation Embedding Evolution

We thank the reviewer for finding our work innovative. Each comment (presented in italics) is followed by its corresponding response.

W1: The technique in Section 2.4 is a little too specific for AdamW.

Thank you for your feedback. AdamW was chosen as an example because it is the most widely used optimizer in recommender systems other than Adam. Similar modifications can also be implemented for other optimizers if they incorporate an exponential moving average momentum term (e.g., Adamax [R1], AMSGrad [R2], AdaBelif [R4]) and can decouple the weight decay regularization [R3].

W2: Table 5 seems to have an error. In the last row, 0.568 is not the best result. Is it just a typo? Or does +DKD not further improve the performance in this case?

Thank you for pointing out this mistake. We reviewed the results (for the 5 seeds shown above) and found that '+DKD' indeed does not improve the HR@10 performance. Furthermore, the overall comparison in Table 2 indicates the common conclusion: the application of SEvo is primarily beneficial for the top-ranked targets. This is understandable as SEvo encourages the related nodes to be closer; conversely, it may adversely affect the targets being less related to the historical items. To address this problem, graphs describing multiplex relations should be introduced, which is left as future work as discussed in Section 5. We will further analyze this interesting observation in the revised manuscript. Thank you once again for your meticulous review.

Q1: In Table 6, the proposed optimization algorithm even improves the GNN-based recommendation models. What is the reason for this phenomenon?

We believe that it is challenging to exploit both structural and sequential information for these GNN-based recommenders. LESSR and MAERec have developed sophisticated architectures for this purpose; however, they remain suboptimal in effectively utilizing either structural or sequential information alone. To be specific, the local session graph used by LESSR is insufficient to model the necessary structural and sequential information. In contrast, MAERec has improved its performance in this regard due to the use of two separate modules; however, effectively fusing these modules remains a challenging task.

[R1] Kingma D. P., et al. Adam: A method for stochastic optimization. ICLR, 2015.

[R2] Reddi S. J., et al. On the convergence of adam and beyond. ICLR, 2018.

[R3] Loshchilov I., et al. Decoupled weight decay regularization. ICLR, 2019.

[R4] Adabelief optimizer: Adapting stepsizes by the belief in observed gradients. NeurIPS, 2020.

We thank the reviewer for finding our work intriguing. Each comment (presented in italics) is followed by its corresponding response.

W1: The paper is difficult to follow. It would be nice to see a simple summary of the SEvo pipeline in the form of a scheme or algorithm.

Thank you for your constructive feedback. The SEvo pipeline can be summarized as follows (the algorithms for SEvo-enhanced SGD/Adam/AdamW are detailed in Appendix B.1):

1. Compute gradients for embeddings;
2. Update moment estimates (with certain modifications discussed in Section 2.4);
3. Smooth the variations according to Eq. (7);
4. Update the embeddings.

W2: The SEvo formulae use the normalized adjacency matrix, so propagation of the gradients over the sampled node neighborhood is required. Suppose we have a large graph with a relatively high degree of each node. Mini-batch may have poorly correlated nodes, so many node embeddings should be updated simultaneously. This can lead to memory consumption issues and a notable increase in training time.

As discussed in Appendix D.4, the complexity required for SEvo is comparable to that of the simplest GCN solely with neighborhood aggregation. Therefore, SEvo can be readily used for large graphs to which other GCNs can be applied.

W3/Q2: The tables report only the average time across different datasets. The detailed computational (or non-aggregated graphs with time) and space complexity is required to understand the ability of the method to scale. How does the model training time scale with the size of the graph? Could you provide a graph epoch time vs. graph size e.g. for a SASRec?

We present the computational and memory costs below (more training and inference times have been detailed in Appendix D.4). The graph size increases from Tools to Clothing.

We have the following observations:

1. Compared to vanilla SASRec, the implementation of SEvo incurs minimal computational and memory costs.
2. Due to the high sparsity of recommendation datasets, the additional cost increases acceptably as the graph size increases.
3. The costs associated with SEvo are negligible compared to other GNN-based sequence models, including SR-GNN, LESSR, and MAERec. Surprisingly, the training time for these models on Tools (the smallest dataset) greatly exceeds the time required for SEvo on Clothing (the largest dataset). This limitation hinders their application in real recommendation scenarios.

W4/Q3: SEvo accelerates momentum only over first-order neighbors. However, for some graph-related tasks, it is critical to handle long-range dependencies. Can high-order proximity / long-range dependencies be incorporated using SEvo?

Thanks for the comment but there is a misunderstanding about this. SEvo can intrinsically handle long-range dependencies as reflected in Eq. (7). Moreover, as investigated in Appendix D.3 and Table 7, SEvo can benefit from long-range dependencies when $L > 1$, with better results when $L=$ 2 or 3.

Q1: How does SEvo work in mini-batch fashion?

Graph sampling methods [R1, R2] can be applied in a manner similar to that employed for other GCNs. Furthermore, it is worth noting that graph partition approaches [R3, R4] are more appropriate here, as the items/entities in a mini-batch are not necessarily included in the graph utilized for SEvo. When the original graph is too large for practical applications, it can be pre-sliced into multiple subgraphs for subsequent training. Moreover, if these smaller subgraphs are mutually exclusive, parallel updates can be performed for better acceleration and accuracy.

Q1.5: Does it require specific batch preparations, or should it be smaller on average?

Do you mean the sampled/sliced sub-graphs should be smaller on average? We think the bigger the better, if possible.

L1: The time and space complexity analyses of the method are required to understand its scalability.

As discussed in Appendix D.4, the time complexity of SEvo is mainly determined by the arithmetic operations of $\mathbf{\tilde{A}}^l \Delta \mathbf{E}, l=1,2, \ldots, L$. Assuming that the number of non-zero entries of $\mathbf{\tilde{A}}$ is $S$, the complexity required is about $\mathcal{O}(LSd)$. On the other hand, the additional space complexity of SEvo is $\mathcal{O}(S)$ for the storage of the normalized adjacency matrix. Because the recommendation datasets are known for high sparsity (i.e., $S$ is very small), the actual overhead can be reduced to a very low level.

[R1] Hamilton W. L., et al. Inductive representation learning on large graphs. NeurIPS, 2017.

[R2] Zou D., et al. Layer-dependent importance sampling for training deep and large graph convolutional networks. NeurIPS, 2019.

[R3] Chiang W., et al. Cluster-GCN: An efficient algorithm for training deep and large graph convolutional networks. KDD, 2019.

[R4] Liu X., et al. Survey on graph neural network acceleration: An algorithmic perspective. IJCAI, 2022.

We thank the reviewer for finding our work novel. Each comment (presented in italics) is followed by its corresponding response.

W1/Q1: Uncleared relationship related to recommender system. It is more suitable to study it under more general graph datasets. Recommendation task has no relationship with your method.

Thank you for pointing out the lack of a clear statement of the motivation in this manuscript. We agree that technically SEvo can be applied to a wider range of graph datasets; however, it is more appropriate to discuss its application in a recommendation scenario for two practical considerations.

1. Embedding is particularly important in modern recommender systems and its quality directly affects the subsequent decisions. However, due to data sparsity [R2], millions of item embeddings cannot be consistently updated through a simple recommendation-driven loss function. To this end, SEvo-enhanced AdamW introduces a graph regularization framework for consistent embedding evolution while simultaneously modifying AdamW to effectively address the challenges posed by extremely sparse gradients.

2. Compared to embedding learning for general graph datasets [R1], a major challenge for recommendation is how to effectively injecting structural information while leveraging other types of information (e.g., sequential information). SEvo excels in this aspect as it has minimal impact on the forward process (this can be empirically demonstrated through comparisons with other GNN-based sequence recommenders).

In summary, SEvo-enhanced AdamW is specifically designed to address the challenges of data sparsity and injecting multiple types of information, which rarely co-exist in general graph datasets. We will further emphasize these challenges in the revised manuscript.

Q2: Why are structure-aware and direction-aware inherently in conflict? Do you have any explanation on this point?

Given an adjacency matrix $\mathbf{\tilde{A}}$, the smoothest direction is along its principal eigenvector $\mathbf{D}^{1/2} \mathbf{1}$, ensuring that $\mathcal{J}_{smoothness}(\mathbf{D}^{1/2}) = 0$. However, the region around this smoothest direction tends to be an infeasible descent direction. Therefore, we have to resort to Eq. (6) for a trade-off.

Q3: We have already enhanced smoothness during the forward-pass during neighborhood aggregation. Why do authors think it is necessary to further enhance it during the backward pass? Will it lead to more severe over smoothing problem?

Thank you for your insightful comment. We agree that if the forward process already involves neighborhood aggregation, re-enhancing smoothness during the backward pass may exacerbate the over-smoothing issue. However, as stated in the introduction, SEvo is not intended to replace those sophisticated GNNs but rather to offer an easy-to-use and plug-and-play alternative for structural information learning. In addition, if the base model fails to exploit the structural information adequately during the forward pass (e.g., LESSR and MAERec), SEvo can still facilitate the learning (the comparison on Beauty as an example):

[R1] Chami I., et al. Low-dimensional hyperbolic knowledge graph embedding. arXiv preprint, 2020.

[R2] Chen Z., et al. A systematic literature review of sparsity issues in recommender systems. TORS, 2024.

We thank the reviewer for finding our work well-motivated and well-organized. Each comment (presented in italics) is followed by its corresponding response.

W1: The reason behind the success of SEvo on large-scale datasets remains unclear. I am extremely curious about this. The improvement is unbelievably huge, making me doubt the reported results. A level of 5% in practice industrial application is extremely huge. However, the experiment results show that SASRec equipped with SEvo performs twice as well as the vanilla SASRec. I believe that if the reported results are true, this performance even exceeds the SOTA method by a large margin since SASRec is still a strong baseline in practice. Has the author carefully tuned the base model?

Thank you for your constructive feedback. We did carefully tune the base model and the following hyper-parameters were grid-searched:

The best checkpoint, determined by the validation metric, was used for the final comparison. In the attached PDF within the global response, we illustrate partial results in terms of the Electronics dataset. We were as surprised as the reviewers by SEvo's success with these large-scale datasets. At this point, the following observations may provide valuable insights.

• The training process of the base model exhibits increased instability on larger-scale datasets. This can be attributed to the sampling randomness: only a small fraction of items are sampled for training within a mini-batch, resulting in the remaining embeddings receiving zero gradients and being updated along the outdated and inconsistent directions. This problem gets worse as the dataset grows larger and sparser. SEvo and the specific modifications to AdamW (Section 2.4) have a positive impact on this issue. In this scenario, even the embeddings of highly inactive items will be updated appropriately throughout the training process.

• In real industrial applications, this performance gap may not be as large because the embeddings are typically trained more adequately beyond a link prediction task [R2]. Hence, the data sparsity problem can be greatly alleviated. Moreover, the rich side information (e.g., attributes [R1], behaviors [R3]) can further minimize the impact of poor embedding quality.

Q1: Could you please give an example showcasing the differences in gradient descent (e.g., comparing the gradient descent processes of LightGCN and MF-BPR+SEvo)?

Thank you for your insightful question. We investigate the gradient descent process of LightGCN and find an interesting connection to SEvo. For a $L$-layer LightGCN, it can be formulated as follows

$$\mathbf{F} = \psi (\mathbf{E}) := \sum_{l=0}^L \alpha_l \mathbf{\tilde{A}}^l \mathbf{E},$$

where $\alpha_l (l=0, \ldots, L)$ represent the layer weights. According to the linear nature of the gradient operator, it can be obtained that

$$\nabla_{\mathbf{E}} \mathcal{L} = \psi (\nabla_{\mathbf{F}} \mathcal{L}).$$

Hence, denoted by $\zeta(\cdot)$ the gradient processing procedure of an optimizer, we can establish that LightGCN is identical to the following system ($\mathbf{F}(t) := \mathbf{F}_t$ due to OpenReview's inability to recognize '_' in very long formulas):

$$\mathbf{F}(t) = \psi( \mathbf{E}(t) ) = \psi( \mathbf{E}(t-1) - \eta \Delta \mathbf{E}(t-1) ) = \psi( \mathbf{E}(t-1) ) - \eta \psi( \Delta \mathbf{E}(t-1) ) = \mathbf{F}(t-1) - \eta \psi \circ \zeta \circ \psi ( \nabla_{\mathbf{F}} \mathcal{L} ).$$

When $\zeta(\cdot)$ is an identity mapping (i.e., standard gradient descent), LightGCN is equivalent to MF-BPR with SEvo being applied twice at each update. However, when $\zeta(\cdot)$ is not an identity mapping (e.g., an optimizer with momentum or weight decay is integrated), they cannot be unified into a single system. Compared to explicit GNNs, SEvo is easy-to-use and has minimal impact on the forward pass, making it more suitable for assisting recommenders in simultaneously utilizing multiple types of information. These connections in part justify why SEvo can inject structural information directly. We will emphasize this point in the revised manuscript.

[R1] Chen Q., et al. Behavior sequence transformer for e-commerce recommendation in Alibaba. DLP-KDD, 2019.

[R2] Bai T., et al. A contrastive sharing model for multi-task recommendation. WWW, 2022.

[R3] Yang Y., et al. Multi behavior hypergraph-enhanced transformer for sequential recommendation. KDD, 2022.