Graph Convolution Network based Recommender Systems: Learning Guarantee and Item Mixture Powered Strategy
Authors: Leyan Deng
Defu Lian
Chenwang Wu
Enhong Chen
Venue: NeurIPS 2022 Accept (2022)
Keywords: generalization ability
recommender system
graph learning

Abstract: Inspired by their powerful representation ability on graph-structured data, Graph Convolution Networks (GCNs) have been widely applied to recommender systems, and have shown superior performance. Despite their empirical success, there is a lack of theoretical explorations such as generalization properties. In this paper, we take a first step towards establishing a generalization guarantee for GCN-based recommendation models under inductive and transductive learning. We mainly investigate the roles of graph normalization and non-linear activation, providing some theoretical understanding, and construct extensive experiments to further verify these findings empirically. Furthermore, based on the proven generalization bound and the challenge of existing models in discrete data learning, we propose Item Mixture (IMix) to enhance recommendation. It models discrete spaces in a continuous manner by mixing the embeddings of positive-negative item pairs, and its effectiveness can be strictly guaranteed from empirical and theoretical aspects.

Graph Convolution Network based Recommender Systems: Learning Guarantee and Item Mixture Powered Strategy
Leyan Deng', Defu Lian 15+ Chenwang Wu', Enhong Chen School of Data Science, University Science and Technology of China School of Computer Science and Technology, University Science and Technology of China {dleyan, wcw1996) 0maal..mmmmammmmmm .utu..t.. edu. en, {liandefu, cheneh) edu
Abstract
Inspired by their powerful representation ability on graph-structured data, Graph Convolution Networks (GCNs) have been widely applied to recommender systems, and have shown superior performance. Despite their empirical success, there is lack of theoretical explorations such as generalization properties. this paper, take first step towards establishing generalization guarantee for GCN-base recommendation models under inductive and transductive learning. We mainly investigate the roles of graph normalization and non-linear activation, providing some theoretical understanding, and construct extensive experiments to further verify these findings empirically. Furthermore, based on the proven generalization bound and the challenge of existing models discrete data learning, we propose Item Mixture (IMix) to enhance recommendation. It models discrete spaces in continuous manner by mixing the embeddings of positive-negative item pairs, and its effectiveness can be strictly guaranteed from empirical and theoretical aspects.
Introduction
With the explosive growth of online information, Internet users rely on recommender systems to alleviate such information overload 222
4 6). In order to take full advantage of the rich graph structure with high-hop neighbors in recommender systems, recent studies have begun to apply Graph Convolution Networks (GCNs) 77 to recommender systems. As expected, GCN-based models have emerged as one of the most attractive approaches to recommender systems due their powerful graph representation abilities. However, these works only demonstrate the effectiveness of GCNs empirically and do not provide theoretical guarantees.
GCN-based Recommendation. [8] was the first to introduce GCN into recommender systems. Specifically, GCN in their approach was applied to the user-user and item-item graphs learn auxiliary information, respectively. GC-MC [9] proposed to apply GCN to the user-item interaction graph to learn the relations between users and items. SpectralCF [10] directly discovered all possible connectivity between users and items from the spectral domain of the user-item graph. However, SpectralCF fails capture the information high order. NGCF [II] further proposed employing the element- wisee product between users and embeddings to augment the item features that users care about and the user features that items are selected by. Some works 11
[.] observed that removing the non-linear activation not only simplifies the update operation, but also retains or enhances the recommendation performance. LightGCN [12] further removed the feature transformation to simplify the design of GCN. However, these changes only depend on the empirical
12
Corresponding author.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

results, without theoretical guarantees. In addition to the user-item interaction matrix, there exist studies combining the social network [] and knowledge graph [77 to enhance the representations of users and items. In this paper, we mainly consider the user-item interaction matrix, i.e. bipartite graph.
Generalization Analysis for GNNs. Due to the numerical success 18 g several theoretical studies have been devoted establishing generalization guarantees for Graph Neural Networks (GNNs). In inductive learning, 20 studied the generalization capability of GNNs by the VC- dimension, which is polynomial with respect to (w.r.t.) the number of parameters and the number of nodes in the graph. (21) provided the first data-dependent bounds via Rademacher Complexity for message passing GNNs and did not allow the analysis of graph information. Subsequently, [22] derived a tighter bound for GNNs based on the PAC-Bayes framework. In transductive learning, 23 analyzed the uniform stability of (single layer) GCNs and thereby deriving their generalization guarantees. They proved that the graph filter, which makes the largest absolute eigenvalue independent of the graph size, satisfies this uniform stability criterion.
[24] derived a Rademacher complexity based bound for two layers GCN model. [25] provided more informative bound according to the relations between normalized graph and input feature at the first layer. However, these works mentioned above only focused on node or graph classification tasks, different from recommendations. The recent works [26 27 have studied the link prediction and graph embedding tasks; however, they did not concern with the specific models.
Contributions and paper structure. The main contributions are shown as follows:
1) We quantify the model complexity for GCN-based recommender systems on the bipartite graph via -oovering number. And then, in Section 3 relate the Covering number to the generalization error under inductive and transductive settings, leading to the generalization guarantees.
2) Motivated by the proven bound that generalization needs to compromise empirical risk and model complexity and the fact that the recommendation model overfits the sampled discrete data, we propose simple but effective augmentation strategy, Item mixture (IMix) in Section 4 It makes discrete sample space continuous by mixing positive-negative item pairs about the same user. Notably, we theoretically demonstrate that it is beneficial for recommendation generalization.
3) In Section 5 extensive evaluations are conducted on two datasets, Gowalla and Yelp2018. First, to confirm the previous theoretical foundation, we present the corresponding numerical results, mainly including graph normalization and non-linear activation. Second, we validate the effectiveness of the proposed IMix on different models, and the experimental results consistently show that the recommendation performance is significantly improved after configuring IMix.
We conclude in Section 6
All proofs and more experimental results are provided in the appendix.
2 Preliminary
In this section, we first formulate the problem of collaborative filtering (CF) based recommender system. We then describe the GCN-based CF models in detail.
2.1 Problem Formulation
We use and E I to denote the user and item, and use R ((, E U1 i e I} denote the collected user-item interactions. Let Z = {(u, i)lu E U E I} to be the set of user-item pairs, for any triplet (z, 2 y). y +1 if the preference between user-item pair 2 E Z is higher than 1. Let f E F u x I - R be a recommender system. For any user-item pair E Z, the model predicts a preference score f(2) by the learned user representation e, and item representation e,, In this paper, we consider the inner-product as the preference function, i.e., f(=) = e/ e;, To optimize the recommendation ability of f. we adopt a pairwise ranking loss as follows, for any (z, &,,2
e' E 2, otherwise
loss [<v[[(()(()))))))))))>)=)))()))) - f(2'))).
2

---

2.2 GCN-based Recommendation
Let Zu. De E Re be the user and item feature, where the input dimension. Without loss of generality, fix the collected user-item interactions matrix R IR [ where each entry Rui 1 if user has interacted with item i. Let A and A to be the adjacency matrix and the corresponding laplacian matrix, which are both block anti-diagonal matrices since the graph is bipartite. We formalize these twO matrices as follows.
R and Á
R.,
A =
R
R
the existing GCN-based collaborative filtering models can be generalized into two steps. Note that we omit the update formula of items for the sake of brevity.
Following 28
(1) Update operation. The most straightforward layer-wise updations inspired by the GNN techniques, and they can be summarized as follows,
h 1+1
Wihh ( + Σ aue W', iEA
(I)
where u.. = [R.] represents the assigned weights of user u to item i; Nu, is the set of adjacent items of user u. Some recent works [I]] further adopt the element-wise product between nodes with their neighbors to leverage the consistency between user preferences and item attributes. This operation formulated as.
h ++1 = Φ
W
Σ iEN
and (Win) + W (h) h()
In this paper, we focus on the more complex operation defined in Eq. 2 since the Eq. seen special case of it when W!- = O.
can be
(2) Final node representation. The CF-based recommender systems require the representation of users and items for the final prediction task. The mainstream approaches include linear combination and concatenation, respectively defined as,
Linear combination:
e. eu= = h e, = h O h
Concatenation:
where a' is learnable parameter hyper-parametes is the network depth. In this paper, for convenience, we only consider the embeddings the last layer as the final representation, i.e., e, = h.. We will prove that the generalization analysis can be easily extended to other integration operations in appendix.
Generalization for GCN-based Recommender Systems
We first investigate the model complexity of GCN- recommender system via covering number with specific radius in Section 3.1 Then we link the -covering number and generalization errors for inductive and transductive learning in Section 3.2 which finally yield the meaningful bounds.
Assumptions. To establish the generalization guarantee, let us immediately make some mild assumptions that are easy to implement. For the loss function, assuming / R + |-B, B] is any bounded Ci-lipschitz continuous function. For the non-linear activation function, we assume is Cy-lipschitz continuous with some C₂ > 0, ((0) 0 For the weight matrices, assume that W/, W! E Radd are shared across layers, and have bounded norms || | B₁ and [ I Bz. For the input feature, we assume max ||æu||2 S B, and max
VET | S B.
weld
3.1 Covering Number for GCN-based Recommender Systems
In classical learning theory, the complexity function class closely related to the generalization ability (29). and the typical complexity measurements are VC-Dimension [30) and Rademacher

---

complexity [3I] In this paper, we adopt the covering number 32 to investigate the model complexity of GCN- recommender systems. Based on the properties bipartite graphs, we study the complexity by combining the recommendations of GCN-based models for any user-item pairs.
Lemma (Covering number bound). Under Assumptions, we further assume that [| co || S b for any E U, i E I, and I = [L] let || boo Given sample set S with size n, the covering number of F over with specific is bounded as
(1+ 4(7 + (1++))MBIvd (
4ybMBBvd
4ybM B2vd
log.V e, 1lo0) S de log
E
Moreover, when S 4M 4MMddaaa (77 + (1:1,bBb))
log (Fis 1100) - 2d log 8. 1) Bdb
where
- 1,)3(2() (2C))
M = CC + B:)² 2C -
+ C C= C=C,(B++7(,, + + B2b)].
Remark The key idea of the proof is to exploit the properties of the bipartite graph in the recommender system. To investigate the complexity of the recommendation for any user-item pair generated by GCN-based models, we establish the connection between the complexities of function space and weight space. Here C describes the layer-wise updation complexity, which the important term for the following generalization analysis. According to the norm bound of hidden states, the assumption can be naturally satisfied when the activation function bounded. And we will discuss the role of unbounded activation in Section 3 Note that the layer- layer-wise complexity reduces to C C7 + 11 when ignoring element-wiss between users and items, which means that there is no need to discuss the value of b.
3.2 Generalization Bound for Inductive & Transductive Learning
Transductive and inductive learning are both commonly used in GNNs and recommender systems. The primary difference between these two settings is whether the testing set depends on the training set. The testing samples in inductive learning are drawn from some unknown distribution, while in transductive learning, they are sampled without replacement from a fixed data set. In the following, we first relate the generalization error for two settings to the covering number of GCN-based recommendations then derive the final generalization guarantees using Lemmal] [
Inductive Learning. Let D to be fixed but unknown distribution over 2 x Z (-1,+1), assume that all samples in training set S., = {2,, 2/, y:) are i.i.d. according to D, denoted as S. DD and aim make accurate prediction for any unobserved samples (2, v) D. Under this inductive setting, the empirical error over the training set S. and the corresponding generalization error is defined as follows,
m (m)(1) - ( [(,([(z)) - - ((+)),
Empirical error:
Generalization error:
(): f(z)))]
Under inductive learning, we can derive the following generalization emror bound by the complexity term according to the covering number.
Lemma 2. Let F be real-valued function class taking values in [-e,e], and assume that O F. Under assumptions, for any function f in a class F, with probability of least 8 over an i.i.d. size-m training set, we have
C(f) S ()) + 4C1 inf
4a m
+
12
22m/m
V VlggN (Fis el -11)) 112 + +B
log 4/8
as0
m
m
Transductive Learning. For the transductive learning setting, the full samples are observed prior to learning. Given a fixed set = ((2,, #/, y1) y:)) m++ labeled training set S,, with size m is selected from S uniformly at random. The goal of transductive learning is predict the labels of the samples

---

in testing set Su = =Sm Under this transductive setting, the formulation of empirical error Lm (f) similar Eq. (3), and the generalization error is defined as follows,
C,( 1 _ (1)
(()(((())- f(z())
Following the same strategy adopted in proving Lemma 2 we again need perform a generalization bound under transductive setting via covering number of function class. As shown above, the generalization and empirical eπror under transductive setting do not depend on any underlying distributions. The important difference induces two versions of generalization analysis. For the transductive learning, consider the transductive Rademacher complexity [K] defined both the training and testing data. Then the covering number bounded generalization error can be derived by the interdependence between model complexity measurements [34 35
Lemma 3. Let F be real-valued function class taking values in [-c, c). and assume that O F. m++
L. Let Q = - + m. Q2 = (m+a-1/2)(E 1/2/max(m,,)) and oo < 5.05. Under assumptions, for any function f in class F, with probability of at least 1 - 5 over random partitions of S, we have
4a
12
2evm+u
(u( 5mm (f) 20;
inf aso
+
V log (Fis, (1-1))dd 11a)
vm u
t
Q1Q2
+ BeoQ1 min(m, u) + 2B
In
2
Armed with Lemma 2 Lemma 3 and Lemma we now present the generalization error bounds for
inductive and transductive learning.
Proposition (Generalization Bound). Under assumptions, for any function in a class F, in inductive learning, with probability of least 8, we have,
24C|
L(F) (f) +
2log 1)) C2L (B, +Bi) B.)
(4)
vm
16C:
2 2og
+ +BV
m
m
Accordingly, in transductive learning, with probability of at least 1 -6 6, we have,
24CI
C.(s) (f) Vm+ +u C2L / (8(m (
dB, BB,
4C/v2mu
Q1Q2 2
1 8"
+ BcoQ1 min(mm u) (
In
(m + u)²
Remark 2. Proposition states that the gap between generalization error and empirical error con- verges uniformly to 0 with the rate of / /log m)/m. We first discuss several obvious findings about the dependency of the bound on some terms. For the hidden dimension d, the generaliza- tion bound scales as (dd log d); for the input feature norms B, and B,, the bound scales as
O (BB, +B)+B)) B.) Vlog(B.. + B.) The most important term is the layer-wise complexity C, which depends on the value y according the graph structure, the spectral norms of weight matrices B, and B2, and the value of Cs and according to the non-linear activation function. A natural idea constrain the weight matrices during training such that the generalization bound would not grow exponentially with the network depth L. which is a regularization techniques commonly used machine learning. The subsequent discussions focus on the 7, C.. and to investigate the influence of graph normalization and non-linear activation functions.
Role of graph normalization. It is easy to see that 7 is equal to the maximum degree Drax of the user-item interaction graph without graph normalization. Therefore, fixed other terms in C, the generalization bound grows O(D For the random- walk graph, i.e., A = D- A, y 1, and for symmetric normalized graph, i.e., A D-1/2 1/2 S DDmax/ Dmins and hence, the growth is much smaller than the unnormalized graph.
5

---

Role of non-linear activation. As pointed above, the activation functions affect the generalization performance through two quantities: the Lipschitz constant Co and the norm bound of hidden states b. Due to the most activation functions satisfy the condition Co < 1, and particularly LeakyReI.U, ReL.U, and Tanh are 1-Lipschiitz, Co presents negligible influence. For the norm bound i, while the bounded activation naturally provides explicit value, the unbounded function can also satisfy the assumption by constraints on the weight matrices. As discussed in Remark [ weight regularization is widely used in machine learning and can help improve model generalization performance to prevent overfitting, In addition, one recent work [36] gives a new theoretical finding that non-linearity does not bring considerable expressive power to improve representation learning in GNNs, but negatively increase the difficulty of model training. Therefore, this generalization bound provides theoretical support for removing the activation function to simplify the model without incurring performance penalty.
Item Mixture Powered Recommendation
The upper bound in Proposition I Iinspires us that the generalization needs to balance empirical risk and model complexity. Most models 37 IT inevitably lead excessive complexity in pursuit of high expressiveness, but simple models may lead to higher empirical errors, so it is valuable to reduce the complexity while ensuring model expressiveness. In addition, the recommendation algorithm is trained based on the limited discrete data obtained by sampling, making the model perform well in the discrete space of sampling and prone to overfitting. Considering the above and inspired by Mixup (38), we propose Item Mixture (IMix) to power recommendation, which forces the model to deal with regions between discrete samples continuously by mixing any two positive-negative item pairs. In addition, IMix does not make changes to the model, while we can theoretically prove that it reduces the model complexity, and then enjoys generalization. Below we give specific details.
Since the original representations of items are discrete and unprocessable (e.g.. orange or apple), we suggest mixing their embeddings. Specifically, given triplet (,, with a label yos where y: = 1 if user u prefers item i to i', otherwise y; = 0. The embeddings of (u,i, i,)) are (ew,, Bi, ev) computed according to Section 2.2 we arbitrarily sample another triplet (u, j.J" with label yj of the same user. If y/ yý, we can obtain mixed embedding triplet (e.. E., e.) = (eu, + (1 A)e; dey + (1 - ))err with X ~ D2 = Beta(a, B), otherwise, (E.., e;, Ex) = (e.,, Xe, + Ajey, Xew + (1 ))e,). So in IMix, we will train the recommendation model on the new mixed embeddings. We consider the logistic loss ((f(z), y) = log(1 + ef()))- yf(),, the standard loss and IMix loss are defined as
Standard loss:
Cald
1
Σ k=1
f(eTT (ei, - e (.))88)..
m
(5)
1 m
IMix loss:
LLMiz
m k=1 E(e!" (ě,, ēे ). yk).
Considering the motivation above, IMiX preserves the model expressiveness without modification of the model structure. Besides, it transforms the learning of discrete sample pairs into the learning of continuous regions between sample pairs, which may help to alleviate the overfitting.
Notably, although IMix is inspired by the generalization bound in Proposition it decoupled from the model structure. Therefore, it is theoretically applicable to any embedding- based recommendation model, and we will show its performance non- GCN-G models in Appendix A.33
Next, we theoretically guarantee the effectiveness of the proposed IMix. Following a similar approach in (39), we adopt second-order Taylor expansion state the IMiX training loss is approximately equivalent to standard empirical error with a regularization term
Consider training set Sm, denote by D,, all users and D; all item-pairs in Sm, where (i, E D; if (i',) E Ds. We assume that the samplings of user and item-pair are independent, and for Vu E Du, (i, Dr, (u, i')) E Sm. For convenience. let Yu,,, denote the label of (u,,,t".
Lemma 4. Consider the symmetric dataset S. and denote E m (e - (eix ex, the
second-order approximation of IMix loss defined in Eq. (5) is given by
Lmir no cstd__ + (1 2)2 2m Σ k=
e (1 (1+ ee )²
T Eev
cus

---

where = cuy (ei, - =xi
Then we are ready to investigate the following function
class:
let Σ
B(x2))) [ee - ex, (eiz - -e e
e
Fmnse= {F, such that E ((g.ee))
Yea
ST.
uu
Remark 3. Let vu)) [Item)a, similar to [39 40 we assume that the distribution of (ei ex) is p-retentive for some P E 10.1/2). that is, if for any non-zero vector ea, (Ea (e - ex)) 2 (R,y) (e e. Suppose there exists a loss func- tion, which is Ci - lipschitz continuous and bounded by [-B, B). for any f E F with probability of at least 6, we have the following bound generalization error.
c( ((f) + 2Cr [ (2) P
rank(E) [Da
2 log 2/6
+ B
(6)
m
we consider the function class with a general regularization technique on the weight matrices, as we discussed above, the constraint on weights will ultimately control the node representation. Therefore, for the general condition, we focus on the function class Fotd
||le,.l (F.) + ||e: T).
then the similar proof strategy would yield the generalization error bound L()) S (())+00 [.
By 2/6 we can conclude that when rank(Ex) < T, IMix has a better generalization. is easily met because т tends to be large to pursue high performance. For example, in the experiment, the embedding size d is 64 (noted that rank(Ex) d), while the minimum value of r is 130.8.
5 Experiments
In this section, we conduct extensive experiments to validate our theoretical findings and the effec- tiveness of the proposed IMix.
using two datasets: (1) Gowalla, contains 1,027,370 check-in information from 29,858 users to 40,981 locations; (2) Yelp2018, comprises 31,668 users who have reviewed 38,048 items (e.g., restaurants, bars) with 1,561,406 times. The training set, validation set, and test set are randomly sampled in ratio of 7 :
Dataset. We follow existing work [I] [2]
Model Structure. Two competitive GCN-based algorithms, NGCF []]] and LightGCN 12 are used to construct experiments. Among them, NGCF explicitly models the high-order connectivity between users and items through message construction and message aggregation, thereby improving the expressiveness of embedding. LightGCN, on the other hand, is keenly aware that the nonlinear activation function and feature transformation of NGCF have no specific semantics the recom- mendation, so it is simplified to only a domain message aggregation module. Correspondingly, these models are configured with the proposed IMix denoted as NGCF-IMix and LightGCN-IMix, respectively.
We use the public implementation version of LightGCN and follow the default parameters their algorithms unless otherwise specified. More details are provided in Appendix A.
Metries. The recommendation performance is measured by the positive items' rankings in the test set. Recall and NDCG. Recall cutoff K, denoted Recall @ K, denotes the proportion of positive items predicted to be correct. NDCG at a cutoff K, denoted as NDCG@ K, measures the reward for the positive items' position in the top-K recommendation list. For these two metrics, we truncate the ranked list K to 20.
We use two ranking metrics widely used in recommender systems 41 42 43
5.1 Numerical Discussion
In this subsection, we discuss the implication of the generalization bound defined in Proposition, and the results are built on NGCF because is more similar to traditional GCNs.
petpss//giiaan how.a///ooooacooo/////ttCCC
7

---

8.64
ReCAAOK
MDCGag
0.44
0.27
0.0
0.00
0.20
NCCC
0.23
0/22
0.89
1,20
0.85
000 1,00
Layer Namber
Layer Number
Lg Norm of Wrogght
11 Norm of Welgght
The generalizaton affect of Layers
The generalzation affect of weight nomes
Figure 1: (a): the effect of number of layers L on Generalization Performance on Gowalla. (b): the effect of weight norms B1, B2 on Generalization Performance on Gowalla.
Quantitative Analysis. We investigate the effects of two major values the generalization gap, which represents the differences between recommendation performances in training and testing sets. We consider the number of layers L, shown in the left part of Fig. As the number of layers increases, the generalization gaps of ndeg@ K and recall K significantly increase. The empirical results imply that the generalization error is proportional the number of layers, consistent with the theoretical analysis. We also consider the spectral norms of weight matrices B₁ and B2, as shown in the right part of Fig. T We compare the generalization abilities with different weight norms. As the norms increase, the generalization gaps increase steadily. Compared with the number of layers, we can observe that the weight norms increase more slowly. The theoretical reason is that the generalization performance is L-th order with respect to the weight norms B3 and B2, and exponential with respect to the number of layers L.
The Role of Normalized Graph. We compare the generalization performances with different normal- ized graphs, as shown in the left part of Fig. [ It is clear that the two normalized graphs have higher generalizations than the unnormalized graph. This result is consistent with the theoretical findings. The comparison between normalized graphs depends on the specific user-item interaction graph.
0.14
0,708
0.1
0.70
n.re
0.10
0.06
0.00
0.09
Rocal
Mitrod
0086
Mechal Lnaeetats
0.64
0.6
0-1A 3
0.04
+1 Epodit
Roreel
0075
Riyeren
100 Spochs
25
53
75.
100
132
150 175
206
25
50
75
100
105
193
-5
200
25 90
75 109 125 Epocter
156 175 200
Epocha
(0) The genera ization affect of normallzed graph
The coneraization affect of activation function
Figure 2: (a): the effect of normalized graph on Generalization Performance on Gowalla. (b): the effect of activation function Generalization Performance Gowalla.
The Role of Non-linear Activation Function. We study the role non- non-lineat activation function in GCN-based recommender systems. Since most activation functions are all 1-Lipschitz continuous, compare the generalization performances with the popular activation functions, including LeakyReLU, ReLU, Sigmoid, and Tanh. Furthermore, function. As shown in the right part of Fig. 2 these models present similar performances, which provide theoretical support for removing activation functions. Although the Sigmoid presents great recommendations at first, overfitted as the training continued, while the performance of other models is still improved, and their optimal performance tends to be unified.
compare these results with the model without activation
5.2 Performance Analysis of LMix
Effectiveness Validation. We apply the proposed IMix to NGCF and LightGCN and perform detailed comparison, shown in Table The percentage relative improvement is shown in parentheses. Obviously, the proposed augmentation strategy (corresponding to NGCF-IMix and LightGCN-IMix) significantly improves the performance of the corresponding models (NGCF and LightGCN). For example, in the Gowalla dataset, the best performance of NGCF on Recall 20 is 1308, while with IMix configured, the performance improves to an encouraging 0. 1496. addition, the improvements of IMix on NGCF are larger than that LightGCN, We reasonably believe that
8

---

Table 1: Overall evaluation. All models' performance is improved after configured with IMix.
Dataset
Gowalla
Velp2018
Layer #
Method
Recall @20
NDCG@2)
Recall @20
NDCG @:2
NGCF NGCF-IMix
0.1308
0.1032
0.0419
0,0336
layer
0. (.1451(+10093%)
0.1146(+11.05%
0.0492(+17.42%%
0.0360(+7.1490)
NGCF
0.1274
0.1050
0.0431
0,0348
2 layer
NGCF-IMix
0.1454(+14.13%)
0.1164(+10.86%)
(.0491(+13.92%)
0.0391(+12.366)
NGCF
0,1303
0,1082
0.0435
0,0353
layer
NGCT-IMix
0.1496(+14.81%)
0.1191(+10.07%)
0.0504(+15.86%)
0.0405(+14.33%)
LighIGCN
0.1556
0.1340
0.0526
0.0427
layer
LightGCN-IMA IMix
0. 0.1699(+9.199)
0.1436(+7.16%)
0.0562(+6.8458)
0.0458(+7.26%)
LightGCN LighiGCN-IMix (7.6645.5566)
0.16
0,1425
0.0564
0.0462
layer
0.1507(+5.75%)
0.0621(+10.10%)
0.0507(+9.74%)
LighIGCN 0.1759
0.1500
0.0602
0.0492
layer
LighiGCN-IMix
0. 1793(+1.93%)
1.1524(+1.66%
(.0644(+6.98%)
0.0527(47.11%)
0.17
0.16
0.885
0.15
Nocroggn
0.13
DUR0
0.74
1011
0.72
Melric
0.40
Netior
0005
Ugh00ch-M Mi
0/006
Ug
Epocha
Epocha
Epocha
(0]
Yel2018
Figure 3: Test curves (Recall and NDCG@20) for 200 epochs of training,
LightGCN is more expressive (better performance), and the benefit of the boosting strategy decreases accordingly. Nonetheless, the performance on LightGCN is also pleasant surprise.
Besides, Fig. 3 presents the performance curves regarding Recall and NDCG for the test set during the training of LightGCN-based models (LightGCN and SighGCC--MMx) Throughout the training process, LightGCN- IMix consistently outperforms LightGCN. After 50 epochs, LightGCN shows different degrees of overfitting. On the contrary, the performance of LightGCN-IME improved, and their gap gradually enlarged. We reasonably believe that the proposed strategy adds depa-depn regularization term to LightGCN (Lemma 4) which helps to alleviate overfitting.
is still further
0.17
Lig eGCh
0.145
Lgg BUAC
2:03
0.003
LightscC
0/048
0/166
+
8.599
8.7
0.12
0.044
0.042
0.3
0.10
0.110
0-155
0.555
2044
0.400
0/06
52
Feature
Pentum
Fasture
Feotire
(8) Gownls
Yw
Figure 4: Performance comparison of different embedding sizes.
s hyperparam- eters: different feature sizes (dimension of x. and 2;) and hidden layer sizes (dimension of W and W!). Here, the number of layers is set 1, and the results shown in Fig. and Fig. 5
Sensitivity w.r.t Model Hyperparameters. We also explore the impact of the model's
In Fig. we find that the larger the feature size, the more beneficial Moreover, LightGCN-IMix is better than LightGCN, and even more, the better the performance of the original model, the better the improvement after configuring IMix, which highlights the superiority of the proposed IMix.
to the recommendation.

---

0.44
0111
3119
0/900
D/MB
0.32
9.33
Virffat
Verfal NGCF-M
Virfed NGDI-Ma
NGOF-Ma
1GCF-88L
0.3
2:134
6044
8.33
0137
0042
0.31
Hidden Laper Sizo
Layer Sum
Hilden Layne Stze
Hitden Layer Stm
(a] Gowalla
Yep2010
Figure 5: Performance comparison of different hidden layer size.
Fig. reeeelss that the hidden layer size does not cause a significant change in model performance, performance sufficiently satisfactory, which provides
while when the hidden layer size is only support for the practicality of GCN-based algorithms. In addition, with similar conclusions to Fig. and Table the IMix-configured models outperform the original models in all cases. In conclusion, we validate the effectiveness of IMix.
Conclusion and Future Work
GCNs achieve superior empirical success recommender systems but lack theoretical understanding. In this paper, provide model complexity analysis for GCN-based recommendations via Covering number, and then induce the generalization error bounds in inductive and transductive learning. We report several theoretical findings and again verify them via experimental results. Inspired by the generalization analysis, we introduce an augmentation strategy, Item Mixture, to improve the recommendation generalization by mixing item embeddings.
There are several interesting future directions. First, it would be interesting to further analyze the user-item bipartite graph with social relationship and knowledge graph. The second is to extend our analysis to investigate the plausibility of the other GNN-based variants. The third is to study the role of graph spectral properties in generalization ability.
Acknowledgments and Disclosure of Funding
The work was supported by grants from the National Key R&D Program of China (No. 20212D0111801 and the National Natural Science Foundation China (No. 62022077).
References
[1] Paul Covington, Jay Adams, and Emre Sargin. Deep neural networks for youtube recommenda- tions. In Proceedings of the 10th ACM conference on recommender systems, pages 191-198, 2016.
[2] Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William I. Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery Data Mining, pages 973.983, 2018.
[3] Fajie Yuan, Xiangnan He. Alexandros Karatzoglou, and Liguang Zhang. Parameter-efffciient transfer from sequential behaviors for user modeling and recommendation. In Proceedings of the 43rd International ACM SIGIR Conference Research and Development in Information Retrieval, pages 1478. 2020.
[4] Binbin Jin, Defu Lian, Zheng Liu, Qi Liu, Jianhui Ma. Xing Xie, and Enhong Chen. Sampling- decomposable generative adversarial recommender. Neural Information Processing Systems, January 2020.
[5] Defu Lian, Qi Liu, and Enhong Chen. Personalized ranking with importance sampling. In Proceedings of The Web Conference 2020, WWW '20, page 1093-1103, New York, NY, USA, 2020. Association for Computing Machinery.
10

---

[6] Jin Chen, Defu Lian, Binbin Jin, Xu Huang, Kai Zheng, and Enhong Chen. Fast variational autoencoder with inverted multi-index for collaborative filtering. In Proceedings of the ACM Web Conference 2022, WWW '22, page 1944-1954, New York, NY, USA, 2022. Association for Computing Machinery.
[7] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint 16Xiv::600002000 2016.
[8] Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodola, Jan Svoboda, and Michael M Bronstein. Geometric deep learning on graphs and manifolds using mixture model cnns. Proceedings of the IEEE conference on computer vision and pattern recognition, pages 5115-5124, 2017.
[9] Rianne van den Berg. Thomas N Kipf, and Max Welling, Graph convolutional matrix completion. arXiv preprini arXiv: 007.7706622223 2017.
[10] Lei Zheng, Chun-Ta Lu, Fei Jiang, Jiawei Zhang, and Philip S Yu. Spectral collaborative filtering. In Proceedings of the 12th ACM conference on recommender systems, pages 311-319, 2018.
[11] Xiang Wang, Xiangnan He, Meng Wang, Fuli Feng, and Tat-Seng Chua. Neural graph collabo- rative filtering. In Proceedings of the 42nd international ACM SIGIR conference on Research and development in Information Retrieval, pages 165-174, 2019.
[12] Xiangman He, Kuan Deng, Xiang Wang. Yan Li, Yongdong Zhang, and Meng Wang. Lightenn: Simplifying and powering graph convolution network for recommendation. In Proceedings of the 43rd International ACM SIGIR conference on research and development in Information Retrieval, pages 639-648, 2020.
[13] Lei Chen, Le Wu, Richang Hong, Kun Zhang, and Meng Wang. Revisiting graph based collaborative filtering: A linear residual graph convolutional network approach. Proceedings of the AAAI Conference on Artificial Intelligence, 34:27-34, 33, 04 2020.
[14] Le Wu, Yonghui Yang, Kun Zhang, Richang Hong, Yanjic Fu, and Meng Wang. Joint item recommendation and attribute inference: An adaptive graph convolutional network approach. In Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 679-688, 2020.
[15] Zhiwei Liu, Lin Meng, Fei Jiang, Jiawei Zhang, and Philip S Yu. Deoscillated graph collabora- tive filtering. arXiv preprint arXiv:201 1.02/00, 2020.
[16] Wenqi Fan, Yao Ma, Qing Li, Yuan He, Erie Zhao, Jiliang Tang, and Dawei Yin. Graph neural networks for social recommendation. In The World Wide Web Conference, pages 417-426, 2019.
[17] Hongwei Wang, Fuzheng Zhang, Mengdi Zhang, Jure Leskovee, Miao Zhao, Wenjie Li, and Zhongyuan Wang. Knowledge-awar graph neural networks with label smoothness regular- ization for recommender systems. Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, pages 968-977, 2019.
[18) Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Junction tree variational autoencoder for molecular graph generation. In International conference on machine learning, pages 2323-2332. PMLR, 2018
[19] Bing Yu, Haoteng Yin, and Zhanxing Zhu. Spatio-temporal graph convolutional networks: deep learning framework for traffic forecasting, arXiv preprint arXiv:1709.0487. 2017.
[20] Franco Scarselli, Ah Chung Tsoi, and Markus Hagenbuchner. The vapmik-chervonenkis dimension of graph and recursive neural networks. Neural Networks, 108:248-222 2599, 2018.
[21] Vikas Garg, Stefanie Jegelka, and Tommi Jaakkola. Generalization and representational limits of graph neural networks. In International Conference on Machine Learning, pages 3419-3430. PMLR, 2020.

---

[22] Renjie Liao, Raquel Urtasun, and Richard Zemel. A pac-bayesian approach to generalization bounds for graph neural networks. arXiv preprint arXiv:2012.07690, 2020.
[23] Saurabh Verma and Zhi-Li Zhang. Stability and generalization of graph convolutional neural networks. In Proceedings of the 25th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pages 1539-1548, 2019.
[24] Shaogao Lv. Generalization bounds for graph convolutional neural networks via rademacher complexity, arXiv preprint arXiv:2102.10225: 2021.
[25] Pascal Esser, Leena Chennuru Vankadara, and Debarghya Ghoshdastidar. Learning theory can (sometimes) explain generalisation in graph neural networks. Advances in Neural Information Processing Systems, 34, 2021.
[26] Yihan Gao, Chao Zhang, Jian Peng, and Aditya Parameswaran. The importance of norm regularization in linear graph embedding: Theoretical analysis and empirical demonstration. arXiv preprint arXiv: /802.03560 2018.
[27] Atsushi Suzuki, Atsushi Nitanda, Linchuan Xu, Kenji Yamanishi, Mare Cavazza, et al. General- ization bounds for graph embedding using negative sampling: Linear vs hyperbolic. Advances in Neural Information Processing Systems, 34, 2021.
[28] Shiwen Wu, Fei Sun, Wentao Zhang, and Bin Cui. Graph neural networks in recommender systems: a survey. arXiv preprint arXiv:2011.02266 2020.
[29] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018
[30] Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K Warmuth. Learnability and the vapnik-chervonenkis dimension. Journal of the ACM (JACM), (6(4))6299-9)))) 995, 1989.
[31] Peter L Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463-482, 2002.
[32] Ding-Xuat Zhou, The covering number in learning theory. Journal of Complexity, 18(3):739- 767, 2002.
[33] Ran EI- Yaniv and Dmitry Pechyony. Transductive rademacher complexity and its applications. Journal of Artificial Intelligence Research, 35:193-234, 2009.
[34] Minshuo Chen, Xingguo Li, and Tuo Zhao. On generalization bounds of a family of recurrent neural networks. arXiv preprint arXiv:1910.1294/ 2019.
[35] Peter Bartlett, Dylan J Foster, and Matus Telgarsky. opectrally-normaliin margin bounds for neural networks. arXiv preprint /706. 2017.
[36] Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. arXiv preprint arXiv: 10947, 2019.
[37] Jiancan Wu, Xiang Wang. Fuli Feng, Xiangnan He, Liang Chen, Jianxun Lian, and Xing Xie. Self-supervised graph learning for recommendation. In Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 726-735, 2021.
[38] Hongyi Zhang, Moustapha Cisse, Yann N Dauphin, and David Lopez-Paz. mixup: Beyond empirical risk minimization. arXiv preprint 17Xiv:1110.99. 2017.
[39] Linjun Zhang, Zhun Deng, Kenji Kawaguchi, Amirata Ghorbani. and James Zou. How does mixup help with robustness and generalization? arXiv preprint arXiv:2010.04819, 2020.
[40] Raman Arora, Peter Bartlett, Poorya Mianjy, and Nathan Srebro. Dropout: Explicit forms and capacity control. 03 2020.
[41] Haoyu Wang, Defu Lian, and Yong Ge. Binarized collaborative filtering with distilling graph convolutional networks. arXiv preprint 1906.018909999
12

---

[42] Shuyi Ji, Yifan Feng, Rongrong Ji, Xibin Zhao, Wanwan Tang, and Yue Gao. Dual channel hypergraph collaborative filtering. In Proceedings of the 26th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pages 2020-2029, 2020.
[43] Xiang Wang, Hongye Jin, An Zhang, Xiangnan He, Tong Xu, and Tat-Seng Chua. Disentangled graph collaborative filtering. In Proceedings of the 43rd international ACM SIGIR conference on research and development in information retrieval, pages 1001-1010, 2020.
[44] Yehuda Koren, Steffen Rendle, and Robert Bell. Advances in collaborative filtering. Recom- mender systems handbook, pages 91-142, 2022.
[45] Xiaotian Han, Zhimeng Jiang, Ninghao Liu, and Xia Hu. G-mixup: Graph data augmentation for graph classification. arXiv preprint arXiv:220..07179, 2022.
[46] Yiwei Wang, Wei Wang, Yuxuan Liang, Yujun Cai, and Bryan Hooi. Mixup for node and graph classification. In Proceedings of the Web Conference 202/, pages
2021.
[47] Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of machine learning research, 9(11), 2008.
[48] S. Shalev-Shwartz and S. Ben-David. Understanding Machine Learning: From Theory to Algo- rithms. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014.
13


Reviews:
[{"review_id": "zZ25UugNP98", "reviewer": "Reviewer_UAWr", "summary": "Note: I was called upon as an emergency review and only get to check the paper briefly.  \n\nThis 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.  \n", "questions": "See above", "limitations": "N.A.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros:  \n(+) Studying the generalization ability of GNNs from the covering number perspective seems unexplored and interesting.  \n(+) The proposed IMix method is intuitive to understand yet enjoy theoretical guarantees.  \n\nCons and concerns:  \n(-) 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?  \n  \n(-) Though very recent, mixup-based techniques have been introduced in GNNs, which should be discussed.   \nMixup for Node and Graph Classification, WWW 2021  \nG-Mixup Graph Data Augmentation for Graph Classification, ICML 2022  \n  \n(-) Experiments could be enhanced considering only two datasets (Gowalla and Yelp2018) and two baselines (NGCF and LightGCN) are adopted. \n  \n(-) 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.  \n(1)  What is \\hat{R}_u and \\hat{R}_i (L81, P2)?  \n(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?)  \n(3)  Some superscripts have parenthesis while others do not.  \n(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.  \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "VpeFdKaEbcy", "reviewer": "Reviewer_YVVZ", "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.", "questions": "1. Can the proposed method be extended to other GCN-based tasks?\n\n2. IMix mixes item embeddings but not user embeddings. Are there any specific reasons? \n\n3. 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.\n", "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.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n+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.\n\n+The derivation of theoretical analysis (generalization bounds and proof) is clear.\n\n+The empirical results look good and consistent with the analysis.\n\nWeaknesses\n\n-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. \n\n-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. \n\n-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.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Vgp_LhPgDG1", "reviewer": "Reviewer_sKUH", "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.", "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.\n2. 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.\n3. 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')?\n4. 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? \n5. For line 231, the relation between τ and γ is confusing. It jumps without explanation. \n6. 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?\n\n", "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.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\na.\tThe paper gives a bunch of firm evidence for the proof, showing the author’s strong background and well understanding of the previous works. \nb.\tThe flow of the whole paper is intelligible, along with the process of logic and thought.\nc.\tThe work is of the significance since so far there is not any other work gave such complete and theoretical analysis.\n\nWeaknesses:\na.\tThis 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.\nb.\tNotations 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. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept