Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: Note: I was called upon as an emergency review and only get to check the paper briefly.  

This paper proposes to study the generalization ability of GNNs for recommender systems (i.e., bi-partite graphs). Specifically, the authors establish the generalization guarantee by deriving the covering number. Based on the results, the authors propose the Item Mixture (IMix) method to enhance recommendation using the idea of Mixup in self-supervised learning. Experimental results demonstrate the effectiveness of the proposed method.  

strengths_and_weaknesses: Pros:  
(+) Studying the generalization ability of GNNs from the covering number perspective seems unexplored and interesting.  
(+) The proposed IMix method is intuitive to understand yet enjoy theoretical guarantees.  

Cons and concerns:  
(-) My primary concern is how the proposed analyses are related to recommender systems. Specifically, the GNN formulation in Eq. (2) seems to fit any graph beside the recommendation scenario (i.e., bi-partite graphs). If that is the case, should the results in Section 3 generalize to other GNNs? On the other hand, can the existing analyses for general GNNs (ref [17-24]) apply to bi-partite graphs? If yes, how are their results compared to this paper?  
  
(-) Though very recent, mixup-based techniques have been introduced in GNNs, which should be discussed.   
Mixup for Node and Graph Classification, WWW 2021  
G-Mixup Graph Data Augmentation for Graph Classification, ICML 2022  
  
(-) Experiments could be enhanced considering only two datasets (Gowalla and Yelp2018) and two baselines (NGCF and LightGCN) are adopted. 
  
(-) The organization and presentation of the paper could be improved. For example, there are confusing/unexplained sentences/symbols and inaccurate expressions (as detailed below). Besides, I would suggest separating related works into another section from the introduction.  
(1)  What is \hat{R}_u and \hat{R}_i (L81, P2)?  
(2)  The definition of transductive and inductive learning is confusing. In L133, the authors write, "The testing samples in inductive learning are drawn from some unknown distribution," while in L138, "we assume that all samples in Sm are i.i.d. according to D, denoted as Sm ∼ Dm". Are D and D^M the same? If not, how could the generalization error be bounded for an unknown distribution? (violating the no free lunch theorem?)  
(3)  Some superscripts have parenthesis while others do not.  
(4)  L188: "In addition, one recent work [33] gives a new theoretical finding that non-linearity does not contribute to improving expressive power of GNNs," which may not be accurate since [33] focuses on the over-smoothing issue of deep GNNs. Based on "How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks, ICLR 2021", non-linear activation functions are critical for GNNs to generalize.  

questions: See above
limitations: N.A.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper aims to present a theoretical analysis of GCN-based recommender systems, and proposes a method that balances empirical risk and model complexity. The authors first utilize the Covering number to obtain the Covering number bound for GCN-based models over bipartite graphs. Then, they derive two generalization guarantees for both inductive learning and transductive learning. Furthermore, they propose an algorithm, Item Mixture (IMix), that can improve the performance of recommender systems by mixing up two positive-negative item pairs. At last, they conduct expensive experiments to demonstrate the effectiveness of the proposed ideas.
strengths_and_weaknesses: Strengths

+The research problem studied in this paper is very interesting. The idea of using the Covering number to derive generalization bounds to GCNs could provide a new direction for further development.

+The derivation of theoretical analysis (generalization bounds and proof) is clear.

+The empirical results look good and consistent with the analysis.

Weaknesses

-The connection between the generalization bounds and Item Mixture (IMix) is not strong enough. The goal of IMix is to balance empirical error and model complexity. However, the motivation of IMix is more like a regularization loss to alleviate the overfitting than an algorithm to find an optimal solution for both reducing model complexity and improving recommendations. 

-The typical methods to measure model complexity are Vapnik-Chervonenkis Dimension (VC-Dimension) and Rademacher complexity. Why do the authors use the Covering number? It would be better if they provide a discussion about the advantages of the Covering number compared to those two measurements. 

-The theoretical findings include transductive learning and inductive learning. However, in the experiments, the authors do not design specific tests to compare these two settings.

questions: 1. Can the proposed method be extended to other GCN-based tasks?

2. IMix mixes item embeddings but not user embeddings. Are there any specific reasons? 

3. In the experiments, Xavier is used to initialize node features. Therefore, the model highly relies on graph structure. I’m wondering what the results would be if you include existing node features.

limitations: GCN-based recommender system is a relatively narrow direction for recommender systems. As the authors mentioned in their future work, it would be more applicable if they extend their work to GNN-based or knowledge graph-based systems.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper gave out the proof that why graph convolution network is able to improve the performance of recommender system and based on the theoretically analysis it proposes a new method iMix to power recommendation. The proofs focused on the generalization bound adopting the Covering number theory. It firstly exploited the properties of the user-item interaction graph in the recommender system. Then, it states that generalization error and empirical error can be coverage to 0 while supervised data is large enough. In terms of the generalization bound achieved, graph normalization showed its superiority while non-linear activation function was not necessary. iMix is model-agnostic, preserving the model expressiveness by mixing any two positive-negative item pair instead of discrete individual items. And iMix can well satisfy the generalization with a easily-met parameter. Experiment on generalization quantity, role of normalized graph, role of non-linear activation function, performance of iMix and its hyperparameters were conducted, and showed the consistency on proof and analysis.
strengths_and_weaknesses: Strengths:
a.	The paper gives a bunch of firm evidence for the proof, showing the author’s strong background and well understanding of the previous works. 
b.	The flow of the whole paper is intelligible, along with the process of logic and thought.
c.	The work is of the significance since so far there is not any other work gave such complete and theoretical analysis.

Weaknesses:
a.	This paper mostly focuses on the proof of generalization bound and the iMix effectiveness, on the contrary the novelty of new method for recommender is less.
b.	Notations given is in a variety and ambiguous, i.e., d for dimension size and node degree. Their definition and explanation also scatter. Notations table and description of the relations among notations is needed. 

questions: 1. There should be more optical images or graph that help reader better understand straightforward, e.g., the thought flow, proof flow, instead of full of mathematical equations.
2. For line 120, what does the Z means by? What’s its usage? It seems that it is different from the Z defined in line 72, which is confusing.
3. For line 206, it says it arbitrarily sample another embedding triplet (e_u,e_i,e_i'), whether it should be correctly written as (e_u,e_j,e_j')?
4. For line 230, there is an inequation that can conclude rank(Σ_X )<τ, but referenced to the appendix the inequation is different from the one here. How could that be? 
5. For line 231, the relation between τ and γ is confusing. It jumps without explanation. 
6. For line 232, it says, in the experiment minimum value of γ is 130.8. According to line 176, γ is equal to the maximum degree of the user-item interaction graph without graph normalization. So how can it be 130.8 in the experiment, especially a decimal rather than an integer?


limitations: This work focuses on the simple GCN based recommender system, while nowadays there are many other kinds of recommender system involving social relations on users and knowledge graph on items. The potential of suck kinds of recommender system is still not discovered yet, which means whether it is suitable for and outperforms the complex models. The role of graph spectral properties in generalization ability is still known, neither.
review_title: null

Meta-review: metareview: This paper proposes a method named Item Mixture (IMix) for recommendation systems. The proposed method is based on Mixup techniques and can enhance the generalization ability with theoretical guarantees. Some concerns regarding the relevance with respect to recommendation systems and the clarity of the paper have been initially raised, but have been addressed during the rebuttal. Now that the reviewers are uniformly positive, I recommend acceptance and encourage the authors to make necessary modifications to incorporate the additional contents of the rebuttal into the main paper.
confidence: Certain
Decision: Accept