Graph-enhanced Optimizers for Structure-aware Recommendation Embedding Evolution

Authors: cong  xu
jun  wang
jianyong  wang
wei  zhang
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 13:30:53

Abstract: Embedding plays a key role in modern recommender systems because they are virtual representations of real-world entities and the foundation for subsequent decision-making models.  In this paper, we propose a novel embedding update mechanism, Structure-aware Embedding Evolution (SEvo for short), to encourage related nodes to evolve similarly at each step. Unlike GNN (Graph Neural Network) that typically serves as an intermediate module, SEvo is able to directly inject graph structural information into embedding with minimal computational overhead during training.  The convergence properties of SEvo along with its potential variants are theoretically analyzed to justify the validity of the designs.  Moreover, SEvo can be seamlessly integrated into existing optimizers for state-of-the-art performance. Particularly SEvo-enhanced AdamW with moment estimate correction demonstrates consistent improvements across a spectrum of models and datasets, suggesting a novel technical route to effectively utilize graph structural information beyond explicit GNN modules.

Main paper: 
 introduction: 
 Surfing Internet leaves footprints such as clicks [15] , browsing [5] , and shopping histories [58] . For a modern recommender system [6, 12] , the entities involved (e.g., goods, movies) are typically embedded into a latent space based on these interaction data. As the embedding takes the most to construct and is the foundation to subsequent decision-making models, its modeling quality directly determines the final performance of the entire system. According to the homophily assumption [31, 59] , it is natural to expect that related entities have closer representations in the latent space. Note that the similarity between two entities refers specifically to those extracted from interaction data [47] or prior knowledge [37] . For example, goods selected consecutively by the same user or movies of the same genre are often perceived as more relevant. Graph neural networks (GNNs) [2, 10, 14] are a widely adopted technique to exploit such structural information, in concert with a weighted adjacency matrix wherein each entry characterizes how closely two nodes are related. Rather than directly injecting structural information into embedding, GNN typically serves as an intermediate module in the recommender system. However, designing a versatile GNN module suitable for various recommendation scenarios is challenging. This is especially true for sequential recommendation [8, 51] , which needs to take into account both structural and sequential information at the same time. Moreover, the post-processing fashion inevitably increases the overhead of training and inference, limiting the scalability for real-time recommendation.In this work, we aim to directly inject graph structural information into embedding through a novel embedding update mechanism. Figure 1 (a) illustrates a normal embedding evolution process, in 3) The L-layer approximation with a faster convergence guarantee.which the embedding E is updated at step t as follows:EQUATIONNote that the variation ∆E is primarily determined by the (anti-)gradient. It points to a region able to decrease a loss function concerning recommendation performance [35] , but lacks an explicit mechanism to ensure that the variations between related nodes are similar. The embeddings thus cannot be expected to capture model pairwise relations while minimizing the recommendation loss.Conversely, structural information can be effectively learned if related nodes evolve similarly at each update. The structure-aware embedding evolution (SEvo), depicted in Figure 1 (b), is developed for this goal. A special transformation is applied so as to meet both smoothness and convergence [57] .Given that these two criteria inherently conflict to some extent, we resort to a graph regularization framework [57, 7] to balance them. While analogous frameworks have been used to understand feature smoothing and modify message passing mechanisms for GNNs [28, 60] , applying this to variations is not as straightforward as to features [24] or labels [19] . Previous efforts are capable of smoothing, but cannot account for strict convergence. The specific transformation form must be chosen carefully; subtle differences may slow down or even kill training. Through comprehensive theoretical analysis, we develop an applicable solution with a provable convergence guarantee.Apart from the anti-gradient, the variation ∆E can also be derived from the moment estimates. Therefore, existing optimizers, such as SGD [41] and Adam [23] , can benefit from SEvo readily. In contrast to Adam, AdamW [27] decouples the weight decay from the optimization step, making it more compatible with SEvo as it is unnecessary to smooth the weight decay as well. Furthermore, we recorrect the moment estimates of SEvo-enhanced AdamW when encountering sparse gradients. This modification enhances its robustness across a variety of recommendation models and scenarios. Extensive experiments over six public datasets have demonstrated that it can effectively inject structural information to boost recommendation performance. It is important to note that SEvo does not alter the inference logic of the model, so the inference time is exactly the same and very little computational overhead is required during training.The main contributions of this paper can be summarized as follows. 1) The graph regularization framework [57, 7] has been widely used for feature/label smoothing. To the best of our knowledge, we are the first to apply it to variations as an alternative to explicit GNN modules for recommendation.2) The final formulation of SEvo is non-trivial (previous iterative [57] or Neumann series [39] approximation methods proved to be incompatible in this case) and comes from comprehensive theoretical analyses. 3) We further present SEvo-enhanced AdamW by integrating SEvo and recorrecting the original moment estimates. These modifications demonstrate consistent performance, yielding average 9%∼23% improvements across a spectrum of models. For larger-scale datasets containing millions of nodes, the performance gains can be as high as 40%∼139%. 4) Beyond interaction data, we preliminarily explore the pairwise similarity estimation based on other prior knowledge: node categories to promote intra-class representation proximity, and knowledge distillation [18] to encourage a light-weight student to mimic the embedding behaviors of a teacher model. 
structure-aware embedding evolution: 
 In this section, we first introduce some necessary terminology and concepts, in particular smoothness. SEvo and its theoretical analyses will be detailed in Section 2.2 and 2.3. The proofs hereafter are deferred to Appendix A.Notations and terminology. Let V = {v 1 , . . . , v n } denote a set of nodes and A = [w ij ] ∈ R n×n a symmetric adjacency matrix, where each entry w ij = w ji characterizes how closely v i and v j are related. They jointly constitute the graph G = (V, A). For example, V could be a set of movies, and w ij is the frequency of v i and v j being liked by the same user. Denoted by D ∈ R n×n the diagonal degree matrix of A, the normalized adjacency matrix and the corresponding Laplacian matrix are defined as Ã = D -1/2 AD -1/2 and L = I -Ã, respectively. For ease of notation, we use ⟨•, •⟩ to denote the inner product, ⟨x, y⟩ = x T y for vectors and ⟨X, Y⟩ = Tr(X T Y) for matrices. Here, Tr(•) denotes the trace of a given matrix.Smoothness. Before delving into the details of SEvo, it is necessary to present a metric to measure the smoothness [57, 7] of node features X as a whole. Denoted by x i , x j the row vectors of X andEQUATION)This term is often used as graph regularization for feature/label smoothing [24, 19] . A lower J smoothness indicates smaller difference between closely related pairs of nodes, and in this case X is considered smoother. However, smoothness alone is not sufficient from a performance perspective. Over-emphasizing this indicator instead leads to the well-known over-smoothing issue [26] . How to balance variation smoothness and convergence is the main challenge to be addressed below.The entities involved in a recommender system are typically embedded into a latent space [6, 12] , and the embeddings in E ∈ R n×d are expected to be smooth so that related nodes are close to each other. As discussed above, E is learnable and updated at step t by Eq. ( 1), where the variation ∆E is mainly determined by the (anti-)gradient. For example, ∆E = -η∇ E L when gradient descent with a learning rate of η is used to minimize a loss function L. However, the final embeddings based on this evolution process may be far from sufficient smoothness because: 1) The variation ∆E points to the region able to decrease the loss function concerning recommendation performance, but lacks an explicit smoothness guarantee. 2) As numerous item embeddings (millions of nodes in practice) to be trained together for a recommender system, the variations of two related nodes may be quite different due to the randomness from initialization and mini-batch sampling.We are to design a special transformation ψ(•) to smooth the variation so that the evolution deduced from the following update formula is structure-aware,EQUATIONRecall that, in this paper, the similarity is confined to quantifiable values in the adjacency matrix A, in which more related pairs are weighted higher. Therefore, this transformation should encourage pairs of nodes connected with higher weights to evolve more similarly than those connected with lower weights. This can be boiled down to structure-aware transformation as defined below.Definition 1 (Structure-aware transformation). The transformation ψ(•) is structure-aware ifEQUATIONOn the other hand, the transformation must ensure convergence throughout the evolution process, which means that the transformed variation should not differ too much from the original. For the sake of theoretical analysis, the ability to maintain the update direction will be used to qualitatively depict this desirable property below, though a quantitative squared error will be employed later.Definition 2 (Direction-aware transformation). The transformation ψ(•) is direction-aware ifEQUATIONThese two criteria inherently conflict to some extent. We resort to a hyperparameter β ∈ [0, 1) to make a trade-off and the desired transformation is the corresponding minimum; that is,EQUATIONA larger β indicates a stronger smoothness constraint and ψ * (∆E) reduces to ∆E when β → 0.Geometrically, as shown in Figure 1 (c), ψ * (∆E) can be interpreted as a projection of ∆E onto the region with proper smoothness. Taking the gradient to zero could give a closed-form solution, but it requires prohibitive arithmetic operations and memory overhead, which is particularly timeconsuming in recommendation due to the large number of nodes. Zhou et al. [57] suggested a L-layer iterative approximation to circumvent this problem (with ψ0 (∆E) = ∆E):ψiter (∆E) := ψL (∆E), ψl (∆E) = β Ã ψl-1 (∆E) + (1 -β)∆E.The resulting transformation is essentially a momentum update that aggregates higher-order information layer by layer. Analogous message-passing mechanisms have been used in previous GNNs such as APPNP [24] and C&S [19] . However, this commonly used approximate solution is incompatible with SEvo; sometimes, variations after the transformation may be opposite to the original direction, resulting in a failure to converge.Theorem 1. The iterative approximation is direction-aware for all possible normalized adjacency matrices and L ≥ 0, if and only if β < 1/2. In contrast, the Neumann series approximation ψnsa (∆E) = (1β) L l=0 β l Ãl ∆E is structure-aware and direction-aware for any β ∈ [0, 1).As suggested in Theorem 1, a feasible compromise for ψiter is to restrict β to [0, 1/2), but this may cause a lack of smoothness. The Neumann series approximation [39] appears to be a viable alternative as it qualitatively satisfies both desirable properties. Nonetheless, this transformation can be further improved for a faster convergence rate based on the analysis presented next.In general, the recommender system has some additional parameters θ ∈ R m except for embedding to be trained. Therefore, we analyze the convergence rate of the following gradient descent strategy:E t+1 ← E t -η ψnsa ∇ E L(E t , θ t ) , θ t+1 ← θ t -η ′ ∇ θ L(E t , θ t ),wherein SEvo is performed on the embedding and a normal gradient descent is applied to θ.To make the analysis feasible, some mild assumptions on the loss function should be given: L : R n×d × R m → R is a twice continuously differentiable function whose first derivative is Lipschitz continuous for some constant C. Then, we obtain the following properties.Theorem 2 (Informal). If η = η ′ = 1/C, the convergence rate after T updates is O(C/((1 - β) 2 T )). If we adopt a modified learning rate of η = 1 (1-β L+1 )Cfor embedding, the convergence rate could be improved to O(C/((1β)T )).Remark 1. Our main interest is to justify the designs of SEvo rather than to pursue a particular convergence rate, so some mild assumptions suggested in [32] are adopted here. By introducing the steepest descent for quadratic norms [1] , better convergence can be obtained with stronger assumptions.Two conclusions can be drawn from Theorem 2. 1) The theoretical upper bound becomes worse when β → 1. This makes sense since ψnsa (∇ E L) is getting smoother and further away from the original descent direction. 2) A modified learning rate for embedding can significantly improve the convergence rate. This phenomenon can be understood readily if we notice the fact that∥ ψnsa (∆E)∥ F ≤ (1 -β L+1 )∥∆E∥ F .Thus, the modified learning rate is indeed to offset the scaling effect induced by SEvo. In view of this, we directly incorporate this factor into SEvo to avoid getting stuck in the learning rate search, yielding the final desired transformation:EQUATIONIt can be shown that ψ is structure-aware and direction-aware, and converges to ψ as L increases. M t [i] ← β 1 M t-1 [i] + (1 -β 1 )G t [i] if G t [i] ̸ = 0 β 1 M t-1 [i] + (1-β1) 1-β t-1 1 M t-1 [i] otherwise , V t [i] ← β 2 V t-1 [i] + (1 -β 2 )G 2 t [i] if G t [i] ̸ = 0 β 2 V t-1 [i] + (1-β2) 1-β t-1 2 V t-1 [i] otherwise ;Compute bias-corrected first/second moment estimates:Mt ← M t /(1 -β t 1 ), Vt ← V t /(1 -β t 2 ); Update via SEvo:E t ← E t-1 -η ψ Mt / Vt + ϵ; β -ηλE t-1 .Output: optimized embeddings E.SEvo can be seamlessly integrated into existing optimizers since the variation involved in Eq. ( 3) can be extended beyond the (anti-)gradient. For SGD with momentum, the variation becomes the first moment estimate, and for Adam this is jointly determined by the first/second moment estimates. AdamW is also widely adopted for training recommenders. Unlike Adam whose moment estimate is a mixture of gradient and weight decay, AdamW decouples the weight decay from the optimization step, which is preferable since it makes no sense to require the weight decay to be smooth as well. However, in very rare cases, SEvo-enhanced AdamW fails to work very well. We next try to ascertain the causes and then improve the robustness of SEvo-enhanced AdamW.Denoted by g := ∇ e L ∈ R d the gradient for a node embedding e and g 2 := g ⊙ g the element-wise square, AdamW estimates the first and second moments at step t using the following formulasm t = β 1 m t-1 + (1 -β 1 )g t-1 , v t = β 2 v t-1 + (1 -β 2 )g 2 t-1, where β 1 , β 2 are two momentum factors. Then the original AdamW updates embeddings by e t = e t-1η • ∆e t-1 , ∆e t-1 := mt / vt . Note that the bias-corrected estimates mt = m t /(1β t 1 ) and vt = v t /(1β t 2 ) are employed for numerical stability [23] . In practice, only a fraction of nodes are sampled for training in a minibatch, so the remaining embeddings have zero gradients. In this case, the sparse gradient problem may introduce some unexpected 'biases' as depicted below.Proposition 1. If a node is no longer sampled in subsequent p batches after step t, we have∆e t+p-1 = κ • β p 1 √ β p 2 ∆e t-1, and the coefficient of κ is mainly determined by t.Considering a common case β 2 ≈ β 1 , the right-hand side approaches O(β p/2 1 ). The step size for inactive nodes then gets slower and slower during idle periods. This seems reasonable as their moment estimates are becoming outdated; however, this effect sometimes prevents the variation from being smoothed by SEvo. We hypothesize that this is because SEvo itself tends to assign more energy to active nodes and less energy to inactive nodes. So this auto-attenuation effect of the original AdamW is somewhat redundant. Fortunately, there is a feasible modification to make SEvo-enhanced AdamW more robust: Theorem 3. Under the same assumptions as in Proposition 1, ∆e t+p-1 = ∆e t-1 if the moment estimates are updated in the following manner when g t = 0,m t = β 1 m t-1 + (1 -β 1 ) 1 1 -β t-1 1 m t-1 , v t = β 2 v t-1 + (1 -β 2 ) 1 1 -β t-1 2 v t-1 . (8)As can be seen, when sparse gradients are encountered, the approach in Theorem 3 is actually to estimate the current gradient from previous moments. The coefficients 1/(1β t-1 1 ) and 1/(1β t-1 1 ) are used here for unbiasedness (refer to Appendix A.3 for detailed discussion and proofs). We summarize the SEvo-enhanced AdamW in Algorithm 1 and the modifications for Adam and SGD in Appendix B.1, with an empirical comparison presented in Section 3.3.The previous discussion lays the technical basis for injecting graph structural information, but the final recommendation performance is determined by how 'accurate' the similarity estimation is. Following other GNN-based sequence models [48, 49] , the number of consecutive occurrences across all sequences will be used as the pairwise similarity w ij . In other words, items v i and v j that appear consecutively more frequently are assumed more related. Notably, we would like to emphasize that SEvo can readily inject other types of knowledge beyond interaction data. We have made some preliminary efforts in Appendix C and observed some promising results. 
experiments: 
 In this section, we comprehensively verify the superiority of SEvo. We focus on sequential recommendation for two reasons: 1) This is the most common scenario in practice; 2) Utilizing both sequential and structural information is beneficial yet challenging. We showcase that SEvo is a promising way to achieve this goal. It is worth noting that although technically SEvo can be applied to general graph embedding learning [4] , we contend SEvo-AdamW is especially useful for mitigating the inconsistent embedding evolution caused by data sparsity, while effectively injecting structural information in conjunction with other types of information.Due to space constraints, this section presents only the primary results concerning accuracy, efficiency, and some empirical evidence that supports the aforementioned claims. We begin by introducing the datasets, evaluation metrics, baselines, and implementation details. Following [22, 13] , we filter out users and items with less than 5 interactions, and the validation set and test set are split in a leave-one-out fashion, namely the last interaction for testing and the penultimate one for validation. This splitting allows for fair comparisons, either for sequential recommendation or collaborative filtering. The dataset statistics are presented in Table 1 .Evaluation metrics. For each user, the predicted scores over all items will be sorted in descending order to generate top-N candidate lists. We consider two widely-used evaluation metrics, HR@N (Hit Rate) and NDCG@N (Normalized Discounted Cumulative Gain). The former measures the rate of successful hits among the top-N recommended candidates, while the latter takes into account the ranking positions and assigns higher scores in order of priority.Baselines. We select four GNN-based models (LightGCN [16] , SR-GNN [48] , LESSR [8] , and MAERec [51] ) as performance and efficiency benchmarks. Since this study is not to develop a new model, four classic sequence models (GRU4Rec [17] , SASRec [22] , BERT4Rec [40] , and STOSA [13] ) are utilized as backbones to validate the effectiveness of SEvo. Besides, MF-BPR [35] is also considered here as a backbone without sequence modeling. We carefully tune the hyperparameters according to their open-source code and experimental settings.Implementation details. Since the purpose is to study the effectiveness of SEvo, only hyperparameters concerning optimization are retuned, including learning rate ([1e-4, 5e-3]), weight decay ([0, 0.1]) and dropout rate ([0, 0.7]). Other hyperparameters in terms of the architecture are consistent with the corresponding baseline. For a fair comparison, the number of layers L is fixed to 3 as in other GNN-based recommenders. As for the hyperparameter in terms of the degree of smoothness, we found β = 0.99 performs quite well in practice. The loss functions follow the suggestions in the respective papers, given that SEvo can be applied to any of them.In this section, we are to verify the effectiveness of SEvo in boosting recommendation performance. Table 2 compares the overall performance and efficiency over four widely used datasets, and Table 3 further provides the results on two large-scale datasets with millions of nodes.Firstly, GNN-based models seem to over-emphasize structural information but lack full exploitation of sequential information. Their performance is only on par with GRU4Rec. On the Tools dataset, SR-GNN and LESSR are even inferior to LightGCN, a collaborative filtering model with no access to sequential information. MAERec makes a slightly better attempt to combine the two by learning structural information through graph-based reconstruction tasks. It employs a SASRec backbone for recommendation to allow for a better utilization of sequential information. Despite the identical recommendation backbone, SASRec trained with SEvo-enhanced AdamW enjoys significantly better performance. Not to mention the consistent gains on other state-of-the-art methods such as BERT4Rec and STOSA, from 2% to 30% according to the last two columns of Table 2 . Overall, the promising improvements from the SEvo enhancement suggest a different route to exploit graph structural information, especially in conjunction with sequence modeling. 2 and Table 3 , it can be inferred that the performance gain increases as the number of items increases. This can be explained by the fact that the randomness of sampling leads to a much more inconsistent evolution when more and more nodes are encountered [56] . SEvo thus plays an increasingly important role as it is capable of imposing direct consistency constraints on embeddings.Since SASRec is a pioneer in the field of sequential recommendation, it will serve as the default backbone for subsequent studies.Convergence comparison. In Section 2.3, we theoretically verified the necessity of rescaling the original Neumann series approximation for faster convergence. Figure 2a shows the loss curves of SASRec trained with AdamW under identical settings other than the form of SEvo. Without rescaling, SASRec exhibits significantly slower convergence, consistent with the conclusion in Theorem 2. While the theoretical worst-case convergence rate of the corrected SEvo is only 1% of the normal gradient descent when β = 0.99, its practical performance is much better. SASRec trained with SEvo-enhanced AdamW initially converges marginally slower and catches up in the final stage. Smoothness evaluation. Figure 2b demonstrates the variation's smoothness throughout the evolution process and the eventual embedding differences from β = 0 to β = 0.999. (I) → (II): The original variations exhibit a similar degree of smoothness, but after transformation, they are quite different--smoother as β increases. (II) → (III): Consequently, the embedding trained with a stronger smoothness constraint becomes smoother as well. The structure-aware embedding evolution successfully makes related nodes closer in the latent space. Although smoothness is not the sole quality measure of embedding, combined with the analyses above, we can conclude that SEvo injects appropriate structural information under the default setting of β = 0.99.SEvo for various optimizers. It is of interest to study whether SEvo can be extended to other commonly used optimizers such as SGD and Adam. Figure 3a compares NDCG@10 performance on Beauty and MovieLens-1M. For a fair comparison, the hyperparameters are tuned independently. It is evident that the performance of SGD, Adam, and AdamW improves significantly after integrating SEvo, with AdamW achieving the best as it does not need to smooth the weight decay.Neumann series approximation versus iterative approximation. Theorem 1 suggests that the Neumann series approximation is preferable to the commonly used iterative approximation because the latter is not always direction-aware and thus a conservative hyperparameter of β is needed to ensure convergence. This conclusion can also be drawn from Figure 3b . When only a little smoothness is required, their performance is comparable as both approximations differ only at the last term. The iterative approximation however fails to ensure convergence once β > 0.7 on the Beauty dataset, potentially resulting in a lack of smoothness.Moment estimate correction for AdamW. We compare SEvo-enhanced AdamW with or without moment estimate correction in Figure 3c , in which average relative improvements against the baseline are presented for each recommender. Overall, the two variants of SEvo-enhanced AdamW perform comparably, significantly surpassing the baseline. However, in some cases (e.g., GRU4Rec and STOSA), the moment estimate correction as suggested in Theorem 3 is particularly useful to improve performance. Recall that BERT4Rec is trained using the output softmax from a separate fully-connected layer that is fully updated at each step. This may explain why the correction has little effect on BERTRec. In conclusion, the results underscore the importance of the proposed modification in alleviating bias in moment estimates.We further explore the potential of applying SEvo to other types of prior knowledge. On the one hand, the category smoothness constraint can also be fulfilled through SEvo (see Appendix C.2), leading to progressively stronger clustering effects as β increases. This provides compelling visual evidence of why SEvo is inherently structure-aware. On the other hand, SEvo is arguably an efficient tool for transferring embedding knowledge (see Appendix C.3). Notice that the learning of other modules cannot be guided in the same way, so SEvo alone is still inferior to state-of-the-art knowledge distillation methods [21, 55] . Fortunately, SEvo and other methods can work together to further boost the recommendation performance. 
related work: 
 Recommender systems are developed to enable users to quickly and accurately find relevant items in diverse applications, such as e-commerce [58] , online news [15] and social media [5] . Typically, the entities involved are embedded into a latent space [6, 12, 54] , and then decision models are built on top of the embedding for tasks like collaborative filtering [16] and context/knowledge-aware recommendation [46, 44] . Sequential recommendation [36, 25] focuses on capturing users' dynamic interests from their historical interaction sequences. Early approaches adapted recurrent neural networks (RNNs) [17] and convolutional filters [42] for sequence modeling. Recently, Transformer [45, 11] has become a popular architecture for sequence modeling due to its parallel efficiency and superior performance. SASRec [22] and BERT4Rec [40] use unidirectional and bidirectional selfattention, respectively. Fan et al. [13] proposed a novel stochastic self-attention (STOSA) to model the uncertainty of sequential behaviors.Graph neural networks [2, 10] are a type of neural network designed to operate on graph-structured data, in concert with a weighted adjacency matrix to characterize the pairwise relations between nodes. GNN equipped with this adjacency matrix can be used for message passing between nodes.The most relevant work is the optimization framework proposed in [57] for solving semi-supervised learning problems via a smoothness constraint. This graph regularization approach has recently inspired a series of work [7, 28, 60] . As opposed to applying it to smooth node representations [24] or labels [19] , it is employed here primarily to balance smoothness and convergence on the variation.Structural information in recommendation is typically learned through GNN as well, with specific modifications made to cope with like data sparsity [52, 29] . LightGCN [16] is a pioneering collaborative filtering work on modeling user-item relations, which removes nonlinearities for easier training. To further utilize sequential information, previous efforts focus on equipping sequence models with complex GNN modules, but this inevitably increases the computational cost of training and inference, making it unappealing for practical recommendation. For example, SR-GNN [48] and LESSR [8] need dynamically construct adjacency matrices for each batch of sequences. Differently, MAERec [51] proposes an adaptive data augmentation to boost a novel graph masked autoencoder, which learns to sample less noisy paths from semantic similarity graph for subsequent reconstruction tasks. The resulting strong self-supervision signals help the model capture more useful information. 
broader impact and limitations: 
 Utilizing both sequential and structural information is beneficial yet challenging, and SEvo proposed in this paper suggests a novel and effective technical route for this purpose. Compared to other explicit GNN modules, SEvo is light-weight and easy-to-use in practice. These insights may inspire future research efforts regarding structure-aware optimization. However, there are still some limitations. Firstly, the training-free nature of SEvo makes it versatile, but also limits the expressive power. For a specific task, a sophisticated GNN module may be more desirable for achieving higher recommendation accuracy. Secondly, it might not be so straightforward to apply SEvo to the scenario involving multiple types of prior knowledge. Some efforts [43, 33] in the field of multiple graph learning have proposed some technically feasible solutions. However, these approaches still encounter challenges in terms of efficiency, particularly in the context of recommendation systems.Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [Yes]Justification: All experiments are conducted on public datasets and the code can be found in the supplementary material.Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
conclusion and future work: 
 In this work, we have proposed a novel update mechanism for injecting graph structural information into embedding. Theoretical analyses of the convergence properties motivate some necessary modifications to the proposed method. SEvo can be seamlessly integrated into existing optimizers. For AdamW, we recorrect the moment estimates to make it more robust. Besides, an interesting direction for future work is extending SEvo to multiplex heterogeneous graphs [3] , as real-world entities often participate in various relation networks. Furthermore, we believe that SEvo holds potential for application to dynamic graph structures and incremental updates [53] . Two challenges may be encountered in practice: the computational overhead associated with the ongoing adjacency matrix normalization, and how to adaptively weaken the outdated historical information. Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes]Justification: The implementation details of baselines and ours can be found in Appendix B.3 and Section 3, respectively.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments? Answer: [Yes] Justification: 1) Paired t-test is performed over 5 independent runs (see Table 2 ). 2) 1-sigma error bars are marked in most figures and tables. Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [Yes]Justification: The broader impact has been discussed in Section 5.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: This work poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes]  
 
 Appendix: A.1 Proof of Theorem 1In this part, we are to prove the structure-aware/direction-aware properties of the L-layer iterative approximation [57] :EQUATIONand the L-layer Neumann series approximation [39] :EQUATION) Fact 1. If L is odd, the geometric series S(x) = L k=0x l is monotonically increasing when x ≤ 0.Proof. It is easy to show thatS(x) = 1 -x L+1 1 -x ,and the derivative w.r.t x ̸ = 1 isS ′ (x) = Lx L+1 -(L + 1)x L + 1 (1 -x) 2 .If L is odd, S ′ (x) is positive when x ≤ 0 and in this case S(x) is monotonically increasing.Lemma 1. Given a normalized adjacency matrix Ã ∈ R n×n , let the symmetric matrix deduced from the Neumann series approximation beEQUATIONDenoted by λ min (P), λ max (P) the smallest and largest eigenvalues of P, respectively, then we have ∀β ∈ [0, 1)EQUATION)Proof. It is easy to shown that the eigenvalues of P are in the form ofEQUATIONwhereλ 1 ≤ λ 2 • • • ≤ λ n denote the eigenvalues of Ã.Recall that these eigenvalues all fall into [-1, 1] and λ n = 1 can be achieved exactly [38] . Hence,EQUATIONis the largest eigenvalue of P.In addition, notice that the last term (1β)β L λ L is non-negative when L is even. Then, we can get a lower bound no matter L is odd or even:EQUATION)The minimum of S(λ) must be achieved in [-1, 0] because S(-λ) ≤ S(λ) for any λ > 0. In fact, in view of Fact 1, we know that S(λ) ≥ S(-1). Hence, we haveEQUATIONThe last inequality holds because 2⌊(L -1)/2⌋ + 2 ≥ L. Therefore, the smallest eigenvalue of P must be greater than1 -β 1 + β (1 -β L ).Proposition 2. The Neumann series approximation is structure-aware and direction-aware for any β ∈ [0, 1).Proof. In view of Lemma 1, we knowλ min (P) ≥ 1 -β 1 + β (1 -β L ) > 0, ∀β ∈ [0, 1), so P is positive definite and thus ψnsa (•) is direction-aware. Also, notice that P has the same eigenvectors as Ã, and so does L. Hence, it is also structure-aware:⟨ ψnsa (x), L ψnsa (x)⟩ = ⟨ ψnsa (x), L ψnsa (x)⟩ = ⟨Px, LPx⟩ = ⟨x, P T LPx⟩ ≤ ⟨x, Lx⟩.The last inequality follows from the fact λ max (P) ≤ 1.Lemma 2. Given a normalized adjacency matrix Ã ∈ R n×n , let the symmetric matrix deduced from the iterative approximation beEQUATION)We have λ min (P ′ ) > 0, ∀β < 1/2.Proof. This conclusion is trivial for the case of L ≤ 1. Let us assume that L ≥ 2. Firstly, rewrite Eq. ( 17) asEQUATIONwhere P := (1β)L-1 l=0 β l Ãl . P is positive definite in view of Lemma 1 and β L ÃL is positive semidefinite when L is even. Therefore, only the case of L ≥ 3 needs to be proved. For a vector x, we haveEQUATION)The first two inequalities follow from Lemma 1. The last inequality holds by noting the fact that, for L ≥ 3 andEQUATION)Proposition 3. The iterative approximation is direction-aware for all possible normalized adjacency matrices and L ≥ 0, if and only if β < 1/2.Proof. If β < 1/2, we have λ min (P ′ ) > 0 according to Lemma 2, and thus ψ is direction-aware. Conversely, if β ≥ 1/2, we can construct an adjacency matrix Ã such that λ min (P ′ ) ≤ 0 for some L. Let us assume that L = 1 andEQUATIONIn this case, we haveEQUATIONwhose eigenvalues are 1 and 1 -2β. The latter is non-positive for any β ≥ 1/2.Remark 2. The construction of Ã in Eq. ( 22) is not unique. In fact, any bipartite graph can be used as a counterexample.Corollary 1 (The proof of Theorem 1). The iterative approximation is direction-aware for all possible normalized adjacency matrices and L ≥ 0, if and only if β < 1/2. In contrast, the Neumann series approximationEQUATIONis structure-aware and direction-aware for any β ∈ [0, 1).Proof. This is a corollary of Proposition 2 and Proposition 3.Proposition 4. The rescaled Neumann series approximation ψ is structure-aware and directionaware, and converges to the optimal solution as L increases.Proof. The convergence to the optimal solution is obvious by noting thatEQUATIONSimilar to Proposition 2, it can be proved that 1 1-β L+1 P is positive definite with a largest eigenvalue ≤ 1. Therefore, the rescaled transformation is also structure-aware and direction-aware.Before delving into the proof of the convergence, we would like to claim that the lemmas below are well known and can be found in most textbooks [32, 1] on convex optimization. For the sake of completeness, we provide here these proofs. Hereinafter, we use ∥X∥ 2 to denote the spectral norm which returns the largest singular value of the matrix X. Lemma 3. For a twice continuously differentiable function f :EQUATION)Proof. For a Taylor expansion of f (x), there exists a z = τ x + (1τ )y for some τ ∈ [0, 1] such thatf (y) = f (x) + ⟨∇f (x), (y -x)⟩ + (y -x) T ∇ 2 f (z)(y -x) 2 ≤ f (x) + ⟨∇f (x) T (y -x)⟩ + C 2 ∥y -x∥ 2 2 .Lemma 4. For a positive definite matrix P, let ∥x∥ P := (x T Px) Proof. Firstly,∥Px∥ 2 = ∥P 1/2 P 1/2 x∥ 2 ≤ ∥P 1/2 ∥ 2 ∥x∥ P ≤ √ b∥x∥ P .Secondly,∥x∥ 2 = ∥P -1/2 P 1/2 x∥ 2 ≤ ∥P -1/2 ∥ 2 ∥x∥ P ≤ 1 √ a ∥x∥ P .Theorem 4. Let f : R n × R m → R be a twice continuously differentiable function bounded below, and its Hessian matrix satisfiesEQUATIONfor some constant C. The following gradient descent scheme is used to train x, y:EQUATION)where P is deduced from the L-layer Neumann series approximation. Then, after T updates, we have,EQUATIONwhere ϵ = f (x, y)f (x * , y * ) andEQUATIONProof. The update formula (29) can be unified intoz t+1 := x t+1 y t+1 = x t y t - ηP 0 0 η ′ I =: P ∇f (x t , y t ).It is easy to show thata := min( 1-β 1+β (1 -β L )η, η ′ ) ≤ λ min ( P) ≤ λ max ( P) = max((1 -β L+1 )η, η ′ ) =: b. Specifically, a = 1-β 1+β (1 -β L ) 1 C , if η = η ′ = 1 C 1-β 1+β 1-β L 1-β L+1 1 C , otherwise , b = (1 -β L+1 ) 1 C , if η = η ′ = 1 C 1 C , otherwise .In view of Lemma 3 and Lemma 4, we haveEQUATION)Denoted byEQUATIONwe havemin 0≤t≤T ∥∇f (x t , y t )∥ 2 2 ≤ 1 T + 1 T t=0 ∥∇f (x t , y t )∥ 2 2 ≤ 1 T + 1 T t=0 2C γ (f (x t , y t ) -f (x t+1 , y t+1 )) = 2C γ(T + 1) (f (x 0 , y 0 ) -f (x T +1 , y T +1 )) ≤ 2C γ(T + 1)ϵ.Theorem 5 (The proof of Theorem 2). If η = η ′ = 1/C, after T updates, we haveEQUATION)If we adopt a modified learning rate for embedding:EQUATION)the convergence rate could be improved to O C/((1β)T ) .Proof. This is true for L = 0, since in this case the update mechanism becomes a normal gradient descent regardless of η = 1/C or η = According to Theorem 4, we havemin t≤T ∥∇L(E t , θ t )∥ 2 2 ≤ 2C γ(T + 1) ϵ,where ϵ = L(E, θ) -L(E * , θ * ) andγ = 1-β 1+β (1 -β L )(1 + β L+1 ), if η = η ′ = 1 C 1-β 1+β 1-β L 1-β L+1 , otherwise .Notice that, for η = η ′ = 1/C, lim β→1EQUATIONand for η =EQUATION)Therefore,1 γ = O(1/(1 -β) 2 ), if η = η ′ = 1 C O(1/(1 -β)), if η = 1 (1-β K+1 )C , η ′ = 1 C .The remainder of the proof is straightforward.Adam(W) [23] uses the bias-corrected moment estimates for updating because they are unbiased when the actual moments are stationary throughout the training. Below, Lemma 5 formally elaborates on this, and Theorem 6 extends Theorem 3 with a proof of unbiasedness.). Denoted by mt = m t /(1-β t 1 ) and vt = v t /(1-β t 2 ) the bias-corrected estimates, if the first and second moments are stationary, i.e.,t ] = E[g], E[g 2 t ] = E[g 2 ], ∀t = 1, 2, . . . ,then these bias-corrected estimates are unbiased:E[ mt ] = E[g], E[v t ] = E[g 2 ], ∀t = 1, 2, . . . . Proposition 5.If a node is no longer sampled in subsequent p batches after step t, we haveEQUATIONwhere the coefficient of κ is mainly determined by t.Proof. In this case, the iterative formula becomesm t+j = β j 1 m t + 0, v t+j = β j 2 v t + 0, ∀j = 0, 1, . . . , p.Therefore,∆e t+p-1 = mt+p vt+p = 1 -β t+p 2 1 -β t+p 1 m t+p √ v t+p = 1 -β t+p 2 1 -β t+p 1 β p 1 β p 2 m t √ v t = β p 1 1 -β t+p 2 β p 2 (1 -β t+p 1 ) m t √ v t = β p 1 (1 -β t 1 ) 1 -β t+p 2 β p 2 (1 -β t+p 1 ) 1 -β t 2 mt √ vt = β p 1 β p 2 • (1 -β t 1 ) 1 -β t+p 2 (1 -β t+p 1 ) 1 -β t 2 =:κ ∆e t-1 .It is easy to show thatEQUATION)Theorem 6 (The proof of Theorem 3). Under the same assumptions as in Lemma 5 and Proposition 1, the bias-corrected estimates are unbiased and ∆e t+p-1 = ∆e t-1 if the estimates are updated in the following manner when g t = 0,EQUATIONProof. We first show the unbiasedness of m t and the proof for v t is completely analogous. It remains only to show thatE[m t ] = (1 -β t 1 )E[g]. This is trivial for t = 0. Assuming that this also holds in the case of t -1, it can be proved by induction.If g t ̸ = 0, E[m t ] = β 1 E[m t-1 ] + (1 -β 1 )E[g t ] = β 1 (1 -β t-1 1 )E[g] + (1 -β 1 )E[g] = (1 -β t 1 )E[g]. If g t = 0, E[m t ] = β 1 E[m t-1 ] + (1 -β 1 ) 1 1 -β t-1 1 E[m t-1 ] = 1 -β t 1 1 -β t-1 1 E[m t-1 ] = (1 -β t 1 )E[g].If the node is no longer sampled in subsequent p batches after step t, we havem t+j = β 1 m t+j-1 + (1 -β 1 ) 1 1 -β t+j-1 1 m t+j-1 = 1 -β t+j 1 1 -β t+j-1 1 m t+j-1 = 1 -β t+j 1 1 -β t+j-1 1 1 -β t+j-1 1 1 -β t+j-2 1 m t+j-2 = • • • = 1 -β t+j 1 1 -β t 1 m t , ∀j = 1, 2, . . . , p.Analogously, we have,v t+j = 1 -β t+j 2 1 -β t 2 v t , ∀j = 1, 2, . . . , p.Therefore, the conclusion can be deduced frommt+p = 1 1 -β t+j 1 m t+p = 1 1 -β t 1 m t = mt , vt+p = 1 1 -β t+j 2 v t+p = 1 1 -β t 2 v t = vt .For a L-layer LightGCN, it can be formulated as followsF = ψ(E) := L l=0 α l Ãl E,where α l , l = 0, . . . , L represent the layer weights. According to the linear nature of the gradient operator, it can be obtained that∇ E L = ψ(∇ F L).Hence, denoted by ζ(•) the gradient processing procedure of an optimizer, we can establish that LightGCN is identical to the following system:F(t) = ψ(E(t)) = ψ(E(t -1) -η∆E(t -1)) = ψ(E(t -1)) -ηψ(∆E(t -1)) = F(t -1) -ηψ • ζ • ψ(∇ F L).When ζ(•) 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 ζ(•) 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 present the algorithms of SEvo-enhanced Adam and SGD in 2 and Algorithm 3, respectively.In this study, we perform experiments on six public datasets. Specifically, the Beauty, Toys, and Tools datasets are extracted from Amazon reviews published in 20142 , while Electronics and Clothing are sourced from Amazon reviews published in 2018 3 . Additionally, the MovieLens-1M dataset is made available by GroupLens M t ← β 1 M t-1 + (1 -β 1 )G t , V t ← β 1 V t-1 + (1 -β 2 )G 2t ; Compute bias-corrected first/second moment estimates:Mt ← M t /(1 -β t 1 ), Vt ← V t /(1 -β t2 ); Update via SEvo:E t ← E t-1 -η ψ Mt / Vt + ϵ; β .Output: optimized embeddings E.Algorithm 3: SGD with momentum enhanced by SEvo. Differences from the original SGD are colored in blue. The matrix operation below are element-wise. Input: embedding matrix E, learning rate η, momentum factors µ, β ∈ [0, 1), weight decay λ.foreach step t do G t ← ∇ E L + λE t-1 ; // Get gradients M t ← µM t-1 + G t ;// Moment update Update via SEvo:E t ← E t-1 -η ψ M t ; β .Output: optimized embeddings E.Four GNN-based baselines for performance and efficiency benchmarks:• LightGCN [16] is a pioneering collaborative filtering model that simplifies graph convolutional networks (GCNs) by removing nonlinearities for easier training. It uses only graph structural information and has no access to sequential information.• SR-GNN [48] and LESSR [8] are two baselines dynamically constructing session graph. The former employs a gated graph neural network to obtain the final node vectors, while the latter utilizes edge-order preserving multigraph and a shortcut graph to address the lossy session encoding and ineffective long-range dependency capturing problems, respectively.• MAERec [51] learns to sample less noisy paths from a semantic similarity graph for subsequent reconstruction tasks. However, we found that the official implementation treats the recommendation loss and reconstruction loss equally, leading to poor performance here. Therefore, an additional weight is attached to the reconstruction loss and a grid search is performed in the range of [0, 1]. Almost all hyperparameters are tuned for competitive performance.Four sequence backbones to validate the effectiveness of SEvo:• GRU4Rec [17] applies RNN [9] to recommendation with specific modifications made to cope with data sparsity. In addition to the learning rate in {1e-4, 5e-4, 1e-3, 5e-3} and weight decay in [0, 0.1], we also tune the dropout rate for node features in the range of [0, 0.7].• SASRec [22] and BERT4Rec [40] are two pioneering works on sequential recommendation equipped with unidirectional and bidirectional self-attention, respectively. For BERT4Rec which employs a separate fully-connected layer for scoring, the weight matrix therein will also be smoothed by SEvo. In addition to some basic hyperparameters, the mask ratio is also researched for BERT4Rec.• STOSA [13] is one of the state-of-the-art models. It aims to capture the uncertainty of sequential behaviors by modeling each item as a Gaussian distribution. The hyperparameters involved are tuned similarly to SASRec.Four knowledge distillation methods used in Appendix C.3:• KD [18] and DKD [55] are two logits-based approaches to transfer knowledge. DKD decomposes the classical KD loss into target class knowledge distillation loss and non-target class knowledge distillation loss.• RKD [34] and HTD [21] are two ranking-based approaches. The former focuses the distillation of relational knowledge through distance-wise and angle-wise alignments, while the latter emphasizes the distillation of hierarchical topology by dividing nodes into multiple groups and requiring intra-group and inter-group alignments.Here, we preliminarily explore the exploitation of more types of knowledge besides consecutive occurrences. We first investigate some elementary factors for interaction data, and then introduce the applications of SEvo to node categories and knowledge distillation. Recent GNN-based sequence models [48, 49] , as well as the SEvo-enhanced models reported in Section 3, estimate the pairwise similarity w ij between items v i and v j based on their co-occurrence frequency in sequences. In other words, items that appear consecutively more frequently are assumed more related. Yet there are some factors that deserve a closer look: (1) The maximum sequence length K for construction to investigate the number of interactions required for accurate estimation;0 0 0 0 0 0 0 0 2 0 0 2 0 2 0 0 2 0 0 0 0 0 0 2 0 2 0 0 1 1 0 1 1 1 0 0 1 0 0 1 0 0 1 0 0 0 1 1 1 0 0 1 0 0 + … + … = A Last K=3, H=1, Frequency v1 v2 v3 v2 v2 v3 v2 v1 v2 v3 v2 v1 v3 v2 0 0 0 0 0 2 0 2 0 0 1 1 1 0 0 1 0 0 + … + … = A Last K=3, H=1, Frequency v1 v2 v3 v2 v1 v3 v2 0 0 0 0 0 2 0 2 0 0 1 1 1 0 0 1 0 0 + … + … = A Last K=3, H=1, Frequency v1 v2 v3 v2 0 1 0 0 1 0 1 0 1 1 0 1 0 1 0 0 1 0 0 1 0 1 0 1 0 1 0 0 1 1 0 1 1 1 0 0 1 0 0 1 0 0 1 0 0 0 1 1 1 0 0 1 0 0 + … + … = A v2 First K=3, H=1, Frequency v1 v2 v3 v1 v2 v3 v1 v3 v2 v1 v3 v2 v1 v3 v2 0 1 0 1 0 1 0 1 0 0 1 1 1 0 0 1 0 0 + … + … = A v2 First K=3, H=1, Frequency v1 v2 v3 v1 v3 v2 0 1 0 1 0 1 0 1 0 0 1 1 1 0 0 1 0 0 + … + … = A v2 First K=3, H=1, Frequency v1 v2 v3 v1 v3 v2 v1 v3 v2 v1 v3 v2 0 0 0 0 0 0 0 1 2 0 1 2 0 2 0 0 2 0 0 0 0 0 1 2 0 2 0 0 1 1 0 1 1 1 0 1 1 0 1 1 1 0 1 1 0 0 1 1 1 0 1 1 1 0 + … + … = A Last K=3, H=2, Frequency v1 v2 v3 v2 v2 v3 v2 v1 v2 v3 v2 v1 v3 v2 0 0 0 0 1 2 0 2 0 0 1 1 1 0 1 1 1 0 + … + … = A Last K=3, H=2, Frequency v1 v2 v3 v2 v1 v3 v2 0 0 0 0 1 2 0 2 0 0 1 1 1 0 1 1 1 0 + … + … = A Last K=3,(2) Using only the first K versus last K interactions in each sequence to compare the utility of early and recent preferences; (3) Allowing related items to be connected by a walk of length ≤ H rather than strict consecutive occurrences; (4) Frequency-based similarity versus distance-based similarity. The former weights all related pairs equally, while the latter weights inversely to their walk length. For example, given a sequence v 2 → v 1 → v 3 with a maximum walk length of H = 2, Algorithm 4: Python-style algorithm for similarity estimation based on interaction data. the frequency-based similarity of (v 2 , v 3 ) gives 1, while the distance-based similarity is 1/2 (as the walk length from v 2 to v 3 is 2). Figure 4 illustrates these four variants and Algorithm 4 details a step-by-step process. We further compare these four potential factors in Figure 5: • Figure 5a shows the effect of confining the maximum sequence length to the first/last K items, so only the early/recent preferences will be considered. In constrast to early interactions, recent ones imply more precise pairwise relations for future prediction, even for small K. With the increase of the maximum sequence length, the recommendation performance on Beauty improves steadily, but not the case for MovieLens-1M. This suggests that shopping relations may be more consistent than movie preferences.• Figure 5b explores the relations beyond strict consecutive occurrences; that is, two items are considered related once they co-occur within a path of length ≤ H. For the shopping and movie datasets, estimating similarity beyond co-occurrence frequency appears less reliable overall. We also compare frequency-based similarity with distance-based similarity that decreases weights for more distant pairs. It is clear that the distance-based approach performs more stably as the maximum walk length H increases.Sometimes embeddings are expected to be smooth w.r.t. a prior knowledge. For example, in addition to the interaction data, each movie in the MovieLens-1M dataset is associated with at least one genre. It is natural to assume that movies of the same genre are related to each other. Heuristically, we can define the similarity w ij to be 1 if v i and v j belong to the same genre and 0 otherwise.As can be seen in Figure 6 , such smoothness constraint can also be fulfilled through SEvo, leading to progressively stronger clustering effects as β increases. However, the resulting performance gains are slightly less than those based on interaction data (see Table 4 ). One possible reason is that the movie genres are too coarse to provide particularly useful information. In conclusion, while smoothness is an appealing inductive bias, its utility depends on how well the imposed structural information agrees with the performance metrics of interest.In addition to the affinity matrix extracted from interaction data or relation data, the pairwise similarity can also be estimated from a heavy-weight teacher model. Recall that Knowledge Distillation (KD) [18] encourages a light-weight student model to mimic the behaviors (e.g., output distribution) of the teacher model, so the learned student model achieves both accuracy and efficiency. In general, higher-dimensional embeddings are capable of better fitting the underlying distribution between entities. The pairwise similarities extracted from a teacher model, needless to say, can be used to guide the embedding evolution of a student model. Unlike interaction or relation data, the deduced graph is dense if only the distance function is applied. Therefore, some graph construction steps including sparsification and reweighting should be involved as well. We attempt to use the widely used KNN graph here, and leave a more comprehensive study of graph construction [20] as a future work. Specifically, the distance between each pair v i , v j is estimated using a cosine similarity distance function:EQUATIONThen, K-nearest neighbors are selected for each node; that isEQUATION)This sparsification is neccessary for several reasons: 1) SEvo with a dense adjacency matrix is computationally prohibitive to conduct; 2) Generally, only the top-ranked neighbors are reliable for next distillation. Finally, the adjacency matrix is obtained through reweighting and symmetrizing:w ij = ŵij + ŵji , ŵij := exp(-d ij /τ ),where τ > 0 is the kernel bandwidth parameter. Structural information may be injected by imposing J smoothness as a regularization term; that is,EQUATIONwhere λ ≥ 0 is a hyperparameter governing the degree of smoothness. We conduct this ablation study in Figure 7 with a λ from 10 -6 to 0.01. As can be seen, incorporating a smoothness regularization term could slightly improve the recommendation performance, but it is not optimal. SEvo performs better because the gradient of the regularization term may be in conflict with the primary loss function.Table 7 : SEvo using different approximation layers L.HR@1 HR@10 NDCG@10 HR@1 HR@10 NDCG@10 As L increases, SEvo gets closer to the exact solution while accessing higher-order neighborhood information. Table 7 lists the performance of different layers, which reaches its peak around L = 3 and starts to decrease then. A possible reason is that the higher-order information is over-smoothed and thus not as reliable and easy to use as the lower order information. Similar phenomena have been found in previous works [50, 8] on applying GNNs to recommendation.The time complexity of SEvo is mainly determined by the arithmetic operations of Ãl ∆E, l = 1, 2, . . . , L. Assuming that the number of non-zero entries of Ã is S, the complexity required is about O(LSd). Because the recommendation datasets are known for high sparsity (i.e., S is very small), the actual computational overhead can be reduced to a very low level, almost negligible. , with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility.In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.https://cseweb.ucsd.edu/~jmcauley/datasets/amazon/links.htmlhttps://cseweb.ucsd.edu/~jmcauley/datasets/amazon_v2https://grouplens.org/datasets/movielens/1m 


Decision: Post rebuttal, all reviewers have agreed to accept the paper. I concur that the paper offers a valuable graph embedding update mechanism for recommender models. Therefore, I recommend acceptance. Please ensure that the necessary revisions are incorporated into the final version.

Reviews: review: paper_summary: paper_summary: This paper proposes SEvo, an embedding updating mechanism that directly injects the graph information into the optimization process. This paper points out two critical criteria for directly injecting graph structure information into the embedding updating process for recommendation. Based on the proposed two criteria, this paper makes efforts to derive a solution named SEvo for injecting the graph structure information directly. SEvo is model-agnostic and can be implemented in various optimizers. The experiments are detailed, and the algorithm is theoretically guaranteed.
strength_weakness: strength_weakness: 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?
questions: questions: I am curious about the differences in gradient descent between SEvo and methods that explicitly model the neighborhood relationship with graph structure (e.g., LightGCN). The modified embedding updating mechanism in SEvo also includes components of the adjacent matrix, which looks similar to the graph propagation mechanism in GNN-based methods. 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)?
limitations: limitations: See weaknesses and questions.
paper_summary: paper_summary: The paper introduces Structure-aware Embedding Evolution (SEvo), a novel embedding update mechanism for recommender systems. SEvo directly integrates graph structural information into embeddings, ensuring that related nodes evolve similarly with minimal computational overhead. This approach differs from traditional Graph Neural Networks (GNNs), which typically serve as intermediate modules. SEvo is designed to enhance existing optimizers, particularly AdamW, to improve recommendation performance by incorporating moment estimate corrections. Theoretical analysis confirms the convergence properties of SEvo, and experiments demonstrate consistent improvements across various models and datasets.
strength_weakness: strength_weakness: 1. Uncleared relationship related to recommender system

2. Key points need further explanation.
questions: questions: 1. I do not see the relationship between your method and recommendation task. Your method aims to change gradient direction based on graph topology. It is more suitable to study it under more general graph datasets. Recommendation task has no relationship with your method.

2. In line 116, the author mentioned “These two criteria inherently conflict to some extent”. Why are structure-aware and direction-aware inherently in conflict? Do you have any explanation on this point?

3. 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?
limitations: limitations: See weakness and questions
paper_summary: paper_summary: This paper proposes Structure-aware Embedding Evolution (SEvo) to improve recommender systems by directly integrating graph structural information into embeddings. Unlike traditional methods, authors propose guide embedding update momentum with graph smoothing regularization. The proposed method can be integrated with a wide range of optimizers for neural networks, e.g., AdamW. The proposed method significantly increases performance metrics on several recommender datasets for standard models and outperforms GNNs.
strength_weakness: strength_weakness: * 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. 
* 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.
* 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
* SEvo accelerates momentum only over first-order neighbors. However, for some graph-related tasks, it is critical to handle long-range dependencies.
questions: questions: * How does SEvo work in mini-batch fashion? Does it require specific batch preparations, or should it be smaller on average?
* 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?
* Can high-order proximity / long-range dependencies be incorporated using SEvo?
limitations: limitations: * The time and space complexity analyses of the method are required to understand its scalability.
paper_summary: paper_summary: In this paper, the authors propose a novel optimization algorithm that is talored for recommender systems. It incorporates graph structural information into the optimization process, aleviating the burden of performing GNN for RS. The convergence of the algorithm is theoretically demonstrated. Besides, it could be incorporated into existing well-performed optimizers like AdamW. The experiments are conducted to test its effectiveness on different types of recommendation models and consistent performance improvements are observed.
strength_weakness: strength_weakness: 1. The technique in Section 2.4 is a little too specific for AdamW.
2. 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?
questions: questions: In Table 6, the proposed optimization algorithm even improves the GNN-based recommendation models. What is the reason for this phenomenon?
limitations: limitations: The authors have addressed the limitations in Section 5 and Appendix.

Comments: title: Keep score unchanged
Acknowledgment of Clarifications and Updated Final Rating
My concern has been addressed.
comment: We sincerely thank you for your time and valuable comments. If you have any further questions please let us know.
I have acknowledged the rebuttal from authors and keep my score unchanged.
We are delighted to learn that our responses have addressed your concerns. We sincerely appreciate the time you spent reviewing our paper!
Thank you for your detailed and thoughtful rebuttal. I appreciate the time and effort you have taken to address my concerns.

Having carefully considered your responses, I am satisfied with the clarifications and additional insights provided. Your explanations have resolved the issues I initially raised, and I now have a clearer understanding of the contributions and significance of your work.

I appreciate your efforts and will be revising my final rating to reflect the improvements made.
We thank you for the engagement with our work and for your effort during the rebuttal.
Thank the author for addressing my concern. I will keep my rating.