How Does Message Passing Improve Collaborative Filtering?

Thank you for your valuable feedback. We really appreciate your acknowledgment of our proposal's significance, theoretical soundness, and presentation. Please see below for our detailed response:

W1: Clarification on Equation 4.

• The purpose of Equation 4 is comparing differences between a vanilla matrix factorization model and the LightGCN model in terms of how user-item similarities are computed. Once we find any differences between these two models, we can individually ablate/remove the additional inductive biases given by LightGCN and observe the performance downgrade to determine their significance to the recommendation performance. Specifically, for matrix factorization models, the similarity computation is extremely intuitive and it is as simple as the inner product between the corresponding user and item embeddings (i.e., $s_{ij}=\mathbf{u}_i^\intercal \cdot \mathbf{i}_j$). Whereas for LightGCN, the similarity computation is a combination of the same inner product and inner products between adjacent node embeddings. In this paper, we start our analysis from perspectives of forward and backward passes.

• From the perspective of backward pass, the idea is that while incorporating similarities between adjacent nodes, the positive supervision signal from the target user-item pair is also back-propagated to adjacency node embeddings. This could improve the recommendation performance because of the idea behind collaborative filtering (i.e., in the case of matrix factorization, neighbors’ similarity scores are highly correlated with the similarity of the target user-item pair). To determine if this is the case and how much can such back propagation improve the recommendation performance, we remove the gradients flowed back to neighbor embeddings (i.e., in implementation, we freeze the detach gradient operation from pytorch) and accordingly observe the performance downgrade. This variant is denoted as LightGCN w/o grad., which surprisingly shows little performance downgrade.

• For the perspective of forward pass, the idea is that to calculate the similarity between a pair of user and item, LightGCN also incorporates a weighted summation of similarities adjacent nodes. The underlying assumption is that neighbors’ similarity scores are highly correlated with the similarity of the target user-item pair. To determine if this operation is helpful, we need one ablation that only removes the numerical values of neighbors’ similarities and keeps everything else intact. In this case, the most straightforward way is removing the neighbor similarities from the calculation yet at the same time keeping the gradients brought by this calculation so that we do not ablate both backward and forward passes at the same time. And this is one of our variants coined LightGCN w/o neigh. Info, which proves that neighbor information drives the good performance of message passing in LightGCN.

• This phenomenon indicates that (1) both additional representations passed from neighbors during the forward pass and accompanying gradient updates to neighbors during the back-propagation help the recommendation performance, and (2) within total performance gains brought by MP, gains from the forward pass dominate those brought by the back-propagation. Comparing LightGCN with LightGCN w/o neigh. Info, we notice that the incorporation of gradient updates brought by MP is relatively incremental (i.e., ~2%). However, to facilitate these additional gradient updates for slightly better performance, LightGCN is required to conduct MP at each batch, which brings tremendous additional overheads. This rationale motivates our further investigation and the proposal of TAG-CF.

W2: Additional resutsl for ranking metrics at 10.

• Thanks for pointing this out. We explore this setting following existing works such as LightGCN and UltraGCN. We agree with you that Recall and NDCG at 10 can better reflect the true performance. Following your suggestion, we accordingly report Recall and NDCG at 10 in the one-page supplemental material and we observe that TAG-CF consistently brings performance improvement to baseline models when we explore more strict metrics, which further validates our proposal.

W3, W4: Presentation improvement to the manuscript.

• Thanks for your suggestions. In Table 2, “OOM” refers to out-of-memory and we use “-” to represent out-of-memory as well because we want to avoid repetitive denotations. We will clarify this point in the table caption. Furthermore, we will double check spelling and grammatical errors remaining in the manuscript to ensure the readability.

In light of our answers to your concerns, we hope you consider raising your score. If you have any more concerns, please do not hesitate to ask and we'll be happy to respond.

Thank you for your valuable feedback. We really appreciate your acknowledgment of our proposal's efficiency and our experiment's extensiveness. Please see below for our detailed response:

W1, Q1: Missing related works

• Thanks for pointing this out. Please see G1 (general response) for details. In summary, we (i) add experiments over 4 efficient baselines, and (ii) add a dedicated section about related efficient training for matrix factorization (MF). TAGCF consistently improves efficient MF methods (i.e., GC-FC, SVD-GCN, SVD-AE, and Turbo-CF). On average, TAGCF improves these methods by 5.6%, 8.9%, 3.9%, 7.8%, and 7.6% on our five datasets resp.

W2: Analysis w.r.t. behaviors of TAG-CF

• In our paper, we claim that test-time message passing (MP) improves the performance of MF methods similarly to training-time MP. We discover that MP (both at training and testing time) helps low-degree users more than high-degree ones. In Table 2, the majority of cases (15/18 cases, or 83.3%) support this finding. In rare cases where high-degree users benefit more, the gap between groups is marginal and our proposed TAGCF still improves the performance (i.e., 6.7%, 2.3%, and 1.8% overall NDCG improvement). TAGCF consistently improves the performance of MF methods over 6 datasets (Table 2). Besides, we also apply TAGCF to training-free baselines (i.e., GFCF, SVD-GCN, SVD-AE, and Turbo-CF), as you suggest, and we observe that TAGCF consistently improves upon them. The added experiments can be found in the 1pg supplement. On average, TAGCF improves 4 training-free methods by 5.6%, 8.9%, 3.9%, 7.8%, and 7.6% on five datasets resp.

W3: Analysis and discussion about degree cut-off

• We agree with you that the behaviors of TAGCF are dependent on the degree cutoff, as we show that MP (both at training and testing time) improves for low-degree users more than high-degree ones. Empirically, we observe that the majority of cases (15/18 in Table 2) support our finding. Moreover, we prove that both BPR and DirectAU optimize the objective of MP with some additional regularization (i.e., dissimilarity between non-existing user/item pairs for BPR, and representation uniformity for DirectAU).
• Combining this theory with the prior empirical observations, we show that these two supervision signals inadvertently conduct MP in the backward step, even without explicitly treating interaction data as graphs (see lines 219-237). To substantiate, we slowly upsample low-degree training users and observe the improvement that TAGCF introduces at each upsampling rate (see Appx. E).

Q2: Definition of low-degree user

• We agree with your point: when the full set is used to calculate degree, experiments might be biased towards testing splits. We use the training set alone to calculate user degrees, as our findings are closely correlated with the amount of exposure a user embedding gets during training.

Q3: Degree cut-off selection

• There are 2 strategies to select degree cut-offs in TAG-CF+. One optimizes ranking performance, and the other focuses on budget (i.e. performance/cost ratio).
• For the former: We treat degree cut-offs as hyper-parameter tuning and select the one that with best validation metrics. We explore this in the original draft (circled optimal points in Figure 2/3).
• For the latter: GNN inference in industrial settings is prohibitively expensive especially for high-degree users, as their receptive field increases exponentially. As shown in Figure 2, performance gain from TAG-CF+ plateaus with a relatively small user degree. In these cases, the cost for further conducting TAG-CF+ on high-degree users grows exponentially, but doing so brings limited gains. Hence, we can also select the cut-off s.t. the performance/cost ratio starts to plateau. We will add this discussion to our manuscript.

Q4: Challenges in large-scale RecSys

• The challenges of applying TAGCF to large-scale RecSys are the utilization of graphs in large-scale ML pipelines. There are often O(100 million) users/items and O(trillion) of edges connecting them. Simply loading the entire sparse interaction matrix into CPU RAM is then infeasible. TAGCF utilizes graph knowledge while avoiding most of the computational overhead of MP. It is extremely flexible, simple to implement, and enjoys benefits of graph-based CF with minimal cost.

Q5: Other graph characteristics

• Thanks for pointing this out. We conduct additional experiments on Katz and Betweenness centrality. We split users equally into 3 buckets according to these characteristics and show the improvement brought by TAGCF to each bucket. Since these characteristics are expensive to compute, we only conduct this experiment on MovieLens-1M. We observe that improvement gradually increases as measurements go down, which echoes our observations on node degree.

Q6: Embedding dimension

• We conduct experiments on the improvement from TAGCF to MF with different dimensions. Due to time limitations and costs for training larger models, we only conduct experiments on Anime and MovieLens-1M. We observe that the performance of MF increases as the dimension increases. TAG-CF can consistently improve the performance of MF models with similar trends as observed in the original draft.

In light of our answers to your concerns, we hope you consider raising your score. If you have any more concerns, please do not hesitate to ask and we'll be happy to respond.

Thank you for your valuable feedback. We really appreciate your acknowledgment of our proposal's significance, insights, and efficiency. Please see below for our detailed response:

W1, Q1, Q2: Pre-training strategies for MF models

• We agree with you that the pre-training strategies are impactful for the results, as TAG-CF is a test-time augmentation framework whose performance significantly depends on the starting performance of the base model that it improves on. In Table 2 of our original manuscript, we applied TAG-CF to MF methods pre-trained by ENMF, DirectAU, and UltraGCN. In Table 5, we also applied TAG-CF to MF derived by BPR. All these applications of TAG-CF to MF methods pre-trained by different methods show consistent performance improvement. Nevertheless, as suggested by other reviewers, we also apply TAG-CF to four other training-free matrix factorization methods (i.e., GFCF, SVD-GCN, SVD-AE, and Turbo-CF). As shown in the one-page additional material, TAGCF can still consistently improve the performance of these efficient matrix factorization methods (i.e., GC-FC, SVD-GCN, SVD-AE, and Turbo-CF). On average, TAGCF improves these four methods by 5.6%, 8.9%, 3.9%, 7.8%, and 7.6% on Amazon-book, Anime, Gowalla, Yelp-2018, and MovieLens-1M respectively.

W2, Q3: Sensitivity experiments for m and n.

• Thanks for pointing this out. Please refer to G2 in our general response for details.

In light of our answers to your concerns, we hope you consider raising your score. If you have any more concerns, please do not hesitate to ask and we'll be happy to respond.

Thank you for your valuable feedback. We really appreciate your acknowledgment of our paper’s significance, written quality, and practicality. Our detailed response to your concerns is as follows:

W1.1: $|u_i|^2 = |i_j|^2 = 1$ does not hold in LightGCN

• We agree that $|u_i|^2 = |i_j|^2 = 1$ does not hold in LightGCN due to the message passing (MP) and the mean averaging across embeddings from different MP layers. All of these operations will void this assumption. However, the main purpose of this theorem to support our claim that matrix factorization (MF) methods with trending objective functions (e.g., BPR and DirectAU) partially optimize the objective of MP with some additional regularization (i.e., dissimilarity between non-existing user/item pairs for BPR, and representation uniformity for DirectAU). Hence, directly optimizing these two objectives for MF partially fulfills the effects brought by MP during the back-propagation. We will refine our theorem and restrict it to MF methods, where the assumption of $|u_i|^2 = |i_j|^2 = 1$ makes sense. We sincerely appreciate your constructive feedback and the refined theorem will be: “During the training of MF methods, objectives of BPR and DirectAU are strictly upper-bounded by the objective of message passing.”

W1.2: Directly training MF using the message passing objective

• The objective of MP layer is $\mathcal{O}=\min_\mathbf{Z}\{tr(\mathbf{Z}^\intercal\mathbf{L}\mathbf{Z}))\}$, which enforces embeddings of adjacent node to be similar. Training one MF model directly optimizing this objective is equivalent to BPR without negative sampling or DirectAU without the uniformity term, which will lead to overfitting and collapsing issues.
• The purpose of our theorem is to connect the gain brought by the MP to node degree. Our theorem shows that BPR and DirectAU partially conduct inadvertent MP during the back-propagation. In the case of CF, the amount of training signals for a user is directly proportional to the node degree. High-degree active users naturally benefit more from the inadvertent MP from objective functions, because they acquire more training signals. Hence, when explicit MP is applied to CF methods, the performance gain for high-degree users is less significant than that for low-degree users. Because the contribution of the MP over high-degree nodes has been mostly fulfilled by the inadvertent MP during the training.
• Retrospecting on your suggestion, we believe that studying the direct correlation between the objective of MP and matrix factorization models can provide understanding towards the role of MP for CF. Hence, we provide the value of the MP objective quantified by $\sum_{(i,j)\in\mathcal{D}} ||\mathbf{u}_i - \mathbf{i}_j||^2$ at different training steps. The results for MF trained with DirectAU on MovieLens-1M is shown below:

• We notice that the objective of MP is gradually optimized as the training progress and plateaus when the model converges, which echos with our finding that it optimizes the objective of MP with some additional regularizations.

W2: Missing important baselines

• Thanks for pointing this out. Please see G1 (general response) for details. In summary, we (i) add experiments over 4 efficient baselines, and (ii) add a dedicated section about related efficient training for matrix factorization (MF). TAGCF consistently improves efficient MF methods (i.e., GC-FC, SVD-GCN, SVD-AE, and Turbo-CF). On average, TAGCF improves these methods by 5.6%, 8.9%, 3.9%, 7.8%, and 7.6% on our five datasets resp.

W3, Q2: Insufficient conclusion in Figure 1

• In Figure 1, we indeed observe a local increasing trend in performance improvement from degree 16 to 20. However, when we compare the performance improvement of the whole low-degree users to that of the high-degree users, we can still observe that the improvement for low-degree users is larger than high-degree users (e.g., 4.8% on low-degree vs. 2.6% on overall for ENMF and 11.2% vs. 10.4% for UltraGCN). We do admit that there are certain cases where the low-degree improvement is slightly worse than the overall (i.e., 1.7% on low-degree vs. 1.8% on overall for MF). In fact, in these cases, the gaps in-between are very marginal (i.e., 0.1%) compared with gaps we observe for other cases (i.e., 2.2% and 0.8%). In Table 2, only 3 out of 18 cases (i.e., 16.7%) are scenarios where low-degree improvement is smaller and all remaining 15 cases (83.3%) support our findings that low-degree improvement is larger. Besides, even in these three rare cases, our proposed TAGCF still improves the performance (i.e., 6.7%, 2.3%, and 1.8% overall improvement in NDCG). So we believe that the conclusion we draw in this section is sufficient given abundant supporting evidence from experiments.

Q1: Setting in Table 1

We train both MF and LightGCN using the DirectAU loss and explore the same setting we have for Table 2. We individually tune hyper-parameters for MF and LightGCN (i.e., learning rate, batch size, and weight decay) to make sure that all models perform at their utmost, so that our findings are not based on weaker baselines. A vanilla MF model trained by DirectAU can already outperform LightGCN trained with BPR loss, which is the reason why we explore DirectAU loss for both MF and LightGCN in the first place. When we train both models using DirectAU, their performance gap is not as big as it is for gaps between models trained with BPR loss. We will include a dedicated section describing the hyper-parameters we used for each dataset.

Q3: Sensitivity experiments for m and n

• Thanks for pointing this out. Please refer to G2 in our general response for details.

In light of our answers to your concerns, we hope you consider raising your score. If you have any more concerns, please do not hesitate to ask and we'll be happy to respond.