Year: 2020

Abstract:
Collaborative filtering has shown great power in predicting potential user-item ratings by factorizing an observed user-item rating matrix into products of two sets of latent factors. However, the user-specific latent factors can only be learned in transductive setting and a model trained on existing users cannot adapt to new users without retraining the model. In this paper, we propose an inductive collaborative filtering framework that learns a hidden relational graph among users from the rating matrix. We first consider a base matrix factorization model trained on one group of users’ ratings and devise a relation inference model that estimates their underlying relations (as dense weighted graphs) to other users with respect to historical rating patterns. The relational graphs enable attentive message passing from users to users in the latent space and are updated in end-to-end manner. The key advantage of our model is the capability for inductively computing user-specific representations using no feature, with good scalability and superior expressiveness compared to other feature-driven inductive models. Extensive experiments demonstrate that our model achieves state-of-the-art performance for inductive learning on several matrix completion benchmarks, provides very close performance to transductive models when given many training ratings and exceeds them significantly on cold-start users.

heading: 1 INTRODUCTION
text: As information explosion has become one major factor affecting human life in the decade, recommender systems, which can filter useful information and contents of user’s potential interests, play an increasingly indispensable part in day-to-day activities. Recommendation problems can be generally formalized as matrix completion (MC) where one has a user-item rating matrix whose entries, which stand for interactions of users with items (ratings or click behaviors), are partially observed. The goal of MC is to predict missing entries (unobserved or future potential interactions) in the matrix based on the observed ones.
Modern recommender systems need to meet two important requirements in order for desirable effectiveness and practical utility. First of all, recommendation models should have enough expressiveness to capture diverse user interests and preferences so that the systems can accomplish personalized recommendation. Existing methods based on collaborative filtering (CF) or, interchangeably, matrix factorization (MF) have shown great power in this problem by factorizing the rating matrix into two classes of latent factors (i.e., embeddings) for users and items respectively, and further leverage dot-product of two factors to predict potential ratings (Koren et al., 2009; Rendle et al., 2009; Srebro et al., 2004; Zheng et al., 2016b). Equivalently, for each user, the methods consider a one-hot user index as input, assume a user-specific embedding function (which maps a user index to a latent factor), and use the learnable latent factor to represent user’s preferences in a low-dimensional space. One can select proper dimension size to control balance between capacity and generalization. Recent works extend MF with complex architectures, like multi-layer perceptrons (Dziugaite & Roy, 2015), recurrent units (Monti et al., 2017), autoregressive models (Zheng et al., 2016a), graph neural networks (van den Berg et al., 2017), etc., and achieve state-of-the-art results on most benchmarks.
The second requirement stems from a key observation from real-world scenarios: recommender systems often interact with a dynamic open world where new users, who are not exposed to models during training, may appear in test stage. This requires that models trained on one group of users
manage to adapt to unseen users. However, the above-mentioned CF models would fail in this situation since the user-specific embeddings are parametrized for specific users and need to be learned collaboratively with all other users in transductive setting. One brute-force way is to retrain the whole model with an augmented rating matrix, but extra time cost would be unacceptable for online systems. There are quite a few studies that propose inductive matrix completion models using user features (Jain & Dhillon, 2013; Xu et al., 2013; Cheng et al., 2016; Ying et al., 2018; Zhong et al., 2018). Their different thinking paradigm is to target a user-sharing mapping from user features to user representations, instead of from one-hot user indices used by CF models. Since the feature space is shared among users, such methods are able to adapt a model trained on existing users to unseen users. Nevertheless, feature-driven models often suffer from limited expressiveness with low-quality features that have weak correlation with target labels. For example, users with the same age and occupation (commonly used features) may have distinct ratings on movies and music. Unfortunately, high-quality features that can unveil user interests for personalized recommendation are often hard to collect due to increasingly concerned privacy issues.
A following question arises: Can we have a recommendation model that guarantees enough expressiveness for personalized recommendation and enables inductive learning? In fact, to simultaneously meet the two requirements is a non-trivial challenge when high-quality user features are unavailable. First, to achieve either of them, one needs to compromise on the other. In fact, the one-hot user indices (together with learnable user-specific embeddings) give a maximized capacity for learning distinct user preferences from historical rating patterns. To make inductive learning possible, one needs to construct a shared input feature space among users out of the rating matrix, as an alternative to one-hot user indices. However, the new constructed features have relatively insufficient expressive power. Second, the computation based on new feature space often bring extra costs for time and space, which limits model’s scalability to large-scale datasets.
In this paper, we propose an inductive collaborative filtering model (IRCF) 1 as a general CF framework that achieves inductive learning for matrix completion and meanwhile guarantees enough expressiveness and scalability. As shown in Fig. 1, we consider a base transductive matrix factorization model trained on one group of users (called support users) and a relation inference model that aims to estimate their relations to another group of users (called query users) w.r.t. historical rating patterns. The (multiple) estimated relational graphs enable attentively message passing from users to users in the latent space and compute user-specific representations in an inductive way. The output user representations can be used to compute product with item representations to predict ratings in the matrix, as is done by CF models. Compared with other methods, one key advantage of IRCF is the capability for inductively computing user-specific representations without using features.
Besides, our method possesses the following merits. 1) Expressiveness: A general version of our model can minimize reconstruction loss to the same level as matrix factorization under a mild condition. Also, we qualitatively show its superior expressiveness than feature-driven and local-graphbased inductive models that may fail in some typical cases. Empirically, IRCF provides very close performance to transductive CF models when given sufficient training ratings. 2) Generalization: IRCF manages to achieve state-of-the-art results on new (unseen) users compared with inductive models. Also, IRCF gives much better accuracy than transductive models when training data becomes sparse and outperforms other competitors in extreme cold-start recommendation. 3) Scal-
1The codes will be released.
ability: Our model enables mini-batch training and efficient inference. In experiments, IRCF is averagely ten times faster than local-graph-based inductive model. 4) Flexibility: As a general CF framework, IRCF is flexible to incorporate with various architectures (e.g. MLP-based, GNN-based, autoregressive, etc.) as a base transductive model as well as deal with implicit user feedbacks.

heading: 2 BACKGROUND AND RELATED WORKS
text: In this section, we present some background of the problem and discuss relationships to related works. We consider a general matrix completion (MC) problem which deals with a user-item rating matrix R = {rui}M×N where M and N are the numbers of users and items, respectively. For implicit feedback, rui is a binary entry which denotes whether user u rated (or clicked on, reviewed, liked, purchased, etc.) item i or not. For explicit feedback, rui records rating value of user u on item i. The entries of R are partially observed and the goal is to estimate the missing values in the matrix2. In the following, we introduce related works and highlight their differences to our paper. In Fig. 5, we provide an illustration for comparison with these methods.
General Collaborative Filtering. Existing methods for MC are generally based on collaborative filtering (CF) or, interchangeably, matrix factorization (MF) where user u (resp. item i) corresponds to a d-dimensional latent factor (i.e., one-hot embedding) pu (resp. qi).Then one has a prediction model r̂ui = f(pu,qi) where f can be basically specified as simple dot product or some complex architectures, like neural networks, graph neural networks, etc. One advantage of CF models is that the user-specific embedding pu (as learnable parameters) can provide enough expressive power for learning diverse personal preferences from user historical behaviors and decent generalization ability through collaborative learning with all the users and items. Furthermore, the user embeddings possess rich profile information as representation of user preferences and can benefit various downstream tasks, like target advertisement, user-controllable recommendation (Ma et al., 2019; Cen et al., 2020), influence maximization (Khalil et al., 2017; Manchanda et al., 2019), friend recommendation, etc. However, such user-specific embedding limits the model in transductive learning and when it comes to new users during test, one has to retrain the model (often associated with embeddings for both new and existing users as well as items) with new augmented rating matrix. Admittedly, one can consider local updates for embeddings of new users with fixed item embeddings learned from existing users. Nevertheless, such operation makes model learning for users independent from each other, which is prone for over-fitting compared with collaborative learning in CF models. Besides, it requires ‘incremental’ learning for each new user, while IRCF can deliver on-the-fly inference in online systems.
Feature-driven Recommendation. The CF models do not require any side information other than the rating matrix, but cannot be trained inductively due to the learnable user-specific embedding pu. To address the issue, one can leverage side information such as attribute features to achieve inductive learning. Define user features (like age, occupation, etc.) as au and item features (like movie genre, director, etc.) as bi. The feature-driven model targets a prediction model r̂ui = g(au,bi). Since the space of au is shared among users, a model trained on one group of users can adapt to other users without retraining. However, feature-driven models often provide limited performance since the shared feature space is not expressive enough compared to one-hot embedding space. Another issue is that high-quality features are hard to collect in practice. We note that our model does not require user features for inductive collaborative filtering.
Inductive Matrix Completion. There are a few existing works that attempt to handle inductive matrix completion using only user-item rating matrix. (Hartford et al., 2018) (F-EAE) puts forward an exchangeable matrix layer that takes a whole rating matrix as input and inductively outputs prediction for missing ratings. However, the scalability of F-EAE is limited since it requires the whole rating matrix as input for training and inference for users, while IRCF enables mini-batch training and efficient inference. Besides, (Zhang & Chen, 2020) (IGMC) proposes to use local subgraphs of user-item pairs in a bipartite graph of rating information as input features and further adopt graph neural networks as representation tool to encode subgraph structures for rating prediction. The model achieves inductive learning via replacing users’ one-hot index embeddings by shared input features (i.e., index-free local subgraph structures). Differently, IRCF maintains the ability to give
2Also, in some situations, one targets a ranking list of items for each user as top-N recommendation. In this paper, we focus on predicting missing values in the matrix and leave top-N recommendation for future works.
user-specific embeddings, which represent users’ preferences and interests and can be used for downstream tasks (like target advertisement, user-controllable recommendation, influence maximization, etc.) while F-EAE and IGMC can merely output a prediction score without such user representation. Moreover, the expressiveness of IGMC is limited since the local subgraph structures can be indistinguishable for users with distinct behaviors (see Section 3.2 for more discussions), while IRCF has equivalent expressiveness as original CF models.
Item-based CF Models. Some previous works use item embeddings as representation for users. (Cremonesi et al., 2010; Kabbur et al., 2013) proposes to use a combination of items rated by users to compute user embeddings and frees the model from learning parametric one-hot embeddings for users. Furthermore, there are quite a few auto-encoder architectures for recommendation problem, leveraging user’s rating vector (ratings on all the items) as observed input, estimate user embedding (as latent variables) based on that, and output prediction for missing values in the rating vector (Sedhain et al., 2015; Liang et al., 2018). With item embeddings and user’s rating history, these methods achieve inductive learning for users and can adapt to new users during test. On methodological level, IRCF has the following differences: 1) IRCF learns to use weighted combination of users’ embeddings to compute embeddings for new users, and such combination weights possess interpretability for underlying social influence or user proximity; 2) IRCF considers both users’ and items’ one-hot embeddings in general CF models that maintain better capacity than item-based CF models that only considers learnable parameters in item embedding space.

heading: 3 METHODOLOGY
text: We propose a new inductive collaborative filtering model without using features. We borrow the general idea from graph neural networks (GNNs) which define a computational graph over nodes and edges and further harness message passing through edges to obtain new node representations that aggregate neighbored information. Our high-level methodology stems from a key observation: there exist a (or multiple) latent relational graph among users that represents preference proximity and behavioral interactions3. Based on the relational graphs, we can leverage message passing, propagating learned embeddings from one group of users to others, especially, in an inductive way.
We formulate our model through two sets of users: support users (denoted by U1), for which we learn their embeddings in transductive setting, and query users (denoted by U2), for which we consider message passing to inductively compute their embeddings. Assume |U1| = M1 and |U2| = M2. Correspondingly, we have two rating matrices: R1 = {rui}M1×N (given by U1) and R2 = {ru′i}M2×N (given by U2). Note that there is no strict requirement for U1 and U2 in our formulation. Two common settings are U1 ∩ U2 = ∅, where query users are distinct from support users, and U1 = U2, where support users equal to query users in training. We consider both cases in Section 4.
We train a (transductive) matrix factorization model for U1 using R1, denoted as r̂ui = fθ(pu,qi), where pu ∈ Rd denotes user-specific embedding for user u in U1, qi ∈ Rd denotes item-specific embedding for item i and fθ can be simple dot-product or a neural network with parameter θ. In Appendix C, we present details for two specifications for fθ using neural network and graph convolution network, which are used in our implementation. Denote P1 = {pu}M1×d, Q = {qi}N×d and the objective function becomes
min P1,Q,θ DS1(R̂1, R1), (1)
where R̂1 = {r̂ui}M1×N , DS1(R̂1, R1) = 1T1 ∑ (u,i)∈S1 l(rui, r̂ui) and S1 ∈ ([M1] × [N ]) T1 is a set with size T1 containing indices of observed entries in R1. Here one can use cross-entropy or square loss for l(rui, r̂ui).
The key question is how to learn the relational graph among users and consider message passing for inductive representation learning. We next propose our inductive relation inference model.
3Social networks and following networks in social media can be seen as realizations of such relational graphs, but in most cases, the graphs are unobserved and implicitly affect user’s decisions and behaviors.

heading: 3.1 INDUCTIVE RELATION INFERENCE MODEL
text: Assume C = {cuu′}M1×M2 , where cuu′ ∈ R denotes weighted edge from user u ∈ U1 to user u′ ∈ U2, and define cu′ = [c1u′ , c2u′ , · · · cM1u′ ]⊤ the u′-th column of C. Then we express embedding of user u′ as pu′ = c⊤u′P1, the weighted sum of embeddings of support users. The rating can be predicted by r̂u′i = fθ(pu′ ,qi) and the problem can be formulated as
min C,Q DS2(R̂2, R2), (2)
where R̂2 = {r̂u′i}M2×N , DS2(R̂2, R2) = 1T2 ∑ (u′,i)∈S2 l(ru′i, r̂u′i) and S2 ∈ ([M2] × [N ]) T2 is a set with size T2 containing indices of observed entries in R2. The essence of above method is taking attentive pooling as message passing from support to query users. We first justify this idea by analyzing its capacity and then propose a parametrized model that enables it for inductive learning.
Theoretical Justification If we use dot-product for fθ in the MF model, then we have r̂u′i = p⊤u′qi. We compare (2) with using matrix factorization over R2:
min P2,Q DS2(R̂2, R2), (3)
where P2 = {pu′}M2×d and have the following theorem.
Theorem 1. Assume (3) can achieve DS2(R̂2, R2) < ϵ and the optimal P1 given by (1) satisfies column-full-rank, then there exists at least one solution for C in (2) such that DS2(R̂2, R2) < ϵ. The only condition that P1 is column-full-rank can be trivially guaranteed since d ≪ N . The theorem shows that the proposed model can minimize the reconstruction loss of MC to at least the same level as matrix factorization which gives maximized capacity for learning personalized user preferences from historical rating patterns.
Parametrization We showed that using attentive pooling does not sacrifice model capacity than CF models under a mild condition. However, directly optimizing over C is intractable due to its O(M1M2) parameter space and cu′ is user-specific which disallows inductive learning. Hence, we parametrize C with an attention network, significantly reducing parameters and enabling it for inductive learning. Concretely, we estimate the adjacency score between user u′ and user u as
cu′u = e⊤[Wqdu′ ||Wkpu]∑
u0∈U1 e ⊤[Wqdu′ ||Wkpu0 ]
, (4)
where e ∈ R2d×1, Wq ∈ Rd×d, Wk ∈ Rd×d are trainable parameters, || denotes concatenation and du′ = ∑ i∈Iu′
qi. Here Iu′ = {i|ru′i > 0} includes the historically rated items of user u′. The attention network captures first-order user proximity on behavioral level and also maintains secondorder proximity that users with similar historical ratings on items would have similar relations to other users. Besides, if Iu′ is empty (for extreme cold-start recommendation), we can randomly select a group of items or use (the embedding of) user’s attribute features as du′ if features are available. We provide details in Appendix D.
The normalization in (4) requires computation for all the support users, which limits scalability to large dataset. Therefore, we use sampling strategy to control the size of support users in relation graph for each query user and further consider multi-head attentions that independently sample different subsets of support users. The attention score given by the l-th head is
c (l) u′u = (e(l))⊤[W (l) q du′ ||W(l)k pu]∑
u0∈U(l)1 (e(l))⊤[W (l) q du′ ||W(l)k pu0 ]
, (5)
where U (l)1 denotes a subset of support users sampled from U1. Each attention head independently aggregates embeddings of different subsets of support users and the final inductive representation for user u′ can be given as
pu′ = Wo [∑ u∈U1 c (1) u′uW (1) v pu|| ∑ u∈U1 c (2) u′uW (2) v pu∥ · · · || ∑ u∈U1 c (L) u′uW (L) v pu ] , (6)
where Wo ∈ Rd×Ld and W(l)v ∈ Rd×d. To keep the notation clean, we denote pu′ = hw(du′) and w = ∪Ll=1{e(l),W (l) q ,W (l) k ,W (l) v } ∪ {Wo}.
There exist some common thinkings as for the rationals of our model and inductive graph representation learning (Hamilton et al., 2017; Ying et al., 2018; Zhang et al., 2018), which considers message passing from existing nodes to new nodes over graphs. Differently, IRCF jointly estimate neighbored nodes for a target node (given by attention scores) and learn node representations based on that, while the latter often assumes a given observed graph and directly learn node representations. Furthermore, IRCF can deal with nodes with new users with no historical edge, while the latter would fail for new nodes with no observed edge (if without node attribute features).
Optimization The training process consists of two contiguous stages. First, we pretrain a MF model in transductive setting via (1) and obtain embeddings P1, Q and network fθ. Second, we train our relation model hw with fixed P1, Q via
min w,θ DS2(R̂2, R2). (7)
We found that using fixed Q in the second stage contributes to much better performance on test ratings of query users than optimizing over it.
We further analyze the generalization ability of inductive model on query users. Also, consider fθ as dot-product operation and we assume cu′u ∈ R+ to simplify the analysis. In the next theorem, we show that the generalization error D(R̂2, R2) = E(u′,i)[l(ru′i, r̂u′i)] on query users would be bounded by the numbers of support users and observed ratings of query users.
Theorem 2. Assume that 1) D is L-Lipschitz, 2) for ∀r̂u′i ∈ R̂2 we have |r̂u′i| ≤ B, and 3) the L1-norm of cu′ is bounded by H . Then with probability at least 1 − δ over the random choice of S2 ∈ ([M2]× [N ])T2 , it holds that for any R̂2,
D(R̂2, R2) ≤ DS2(R̂2, R2) +O 2LHB√2M2 lnM1 T2 + √ ln(1/δ) T2  . (8)
(a) (b)
Figure 2: Feature-driven and local-graph-based models fail in (a) and (b), respectively. IRCF works in both cases with superior expressiveness.
The theorem shows that a smaller size of U1 would make the generalization error bound tighter. Looking at both Theorem 1 and 2, we will find that the configuration of U1 has an important effect on model capacity and generalization ability. On one hand, we need to make support users in U1 ‘representative’ of diverse user behavior patterns on item consumption in order to guarantee enough model capacity. Also, we need to control the size of U1 in order to maintain generalization ability. Based on these insights, how to properly select support users can be an interesting direction for future investigation. Our experiments in Section 4 provide more interesting discussions on this point.

heading: 3.2 DISCUSSIONS
text: To shed more lights on model expressiveness, we provide a comparison with feature-driven and local-graph-based inductive models through cases in Fig. 2. Here we assume ratings are within {−1, 1} (positive, denoted by red line, and negative, denoted by black line). The solid lines are observed ratings for training and dash lines are test ratings. In Fig. 2 (a), local-graph-based models can give right prediction relying on different 1-hop local subgraphs of (u1, i2) and (u2, i2), while feature-driven models will fail once u1 and u2 have the same features. In Fig. 2 (b), local-graphbased models will fail since (u1, i3) and (u2, i3) possess the same 1-hop local subgraphs though with distinct ground-truth ratings on i3. By contrast, CF models and IRCF can recognize that u3 has similar rating patterns with u1 and different from u2, thus pushing the embedding of u1 (resp. u2) close to (resp. distant from) u3, which guides the model to right prediction. Note that the first case becomes a common issue when the feature space is small while the second case becomes general when the rating patterns of users are not distinct enough throughout a dataset, which induces similar local subgraph structures. In short, IRCF achieves inductive learning and maintains as good expressiveness as transductive models.

heading: 4 EXPERIMENTS
text: In this section, we conduct experiments to verify the proposed model. We consider five benchmark datasets Douban, Movielens-100K (ML-100K), Movielens-1M (ML-1M), Movielens-10M (ML-10M) and Amazon-Books. The statistics of datasets and more details are in Appendix E.1. For Douban and ML-100K, we use the training/test split provided by (Monti et al., 2017), which is used by (van den Berg et al., 2017; Hartford et al., 2018; Zhang & Chen, 2020). For ML-1M and ML-10M, we also follow previous works and use 9:1 training/test spliting. For Amazon-Books with implicit user feedbacks, we use the last ten ratings of each user for test and the remaining for training.
We consider two specifications for fθ in our model: IRCF-NN, which adopts multi-layer perceptron for f (following the design of NNMF (Dziugaite & Roy, 2015)), and IRCF-GC, which uses graph convolution network for f (following the design of GCMC (van den Berg et al., 2017)). The details are in Appendix C. We also extend IRCF with user attribute features as IRCF-HY, a hybrid model that takes both user one-hot indices and features as input (see details in Appendix D.1), for coldstart recommendation. IRCF-HY considers one-hot/multi-hot embeddings for various features and further a neural network for prediction, following the design of Wide&Deep network (Cheng et al., 2016). In Appendix E.2, we present detailed information for hyper-parameter settings. We leave out 5% training data as validation set for parameter tuning and use early stoping strategy in training. For each dataset we run experiments with five different random seeds and report average results (the improvements in the paper are all significant so we omit confidence intervals for results).

heading: 4.1 COMPARATIVE EXPERIMENTS
text: There can be different configurations for support users and query users. To simulate real-world scenarios where new users are often with fewer historical ratings, we divide users into two sets: users with more than δ training ratings, denoted as U1, and users with less than δ training ratings, denoted as U2. We basically set δ = 30 for Douban and three Movielens datasets, and δ = 20 for Amazon-Books. Then we consider two situations: 1) we set U1 = U1 and U2 = U2, i.e., we treat U1 as support users and U2 as query users; 2) we set U1 = U2 = U1, i.e., we treat U1 as both
support and query users4. In the first case, we can use test performance on U2 to investigate model’s expressiveness in inductive learning; in the second case, we can use test performance on U2 to study model’s generalization on new unseen users during test. Other split ways like random split or using different δ’s and their impact on model performance are thoroughly discussed in Appendix F.
Comparison with transductive & inductive models We compare with three state-of-the-art transductive methods PMF (Salakhutdinov & Mnih, 2007), NNMF (Dziugaite & Roy, 2015), GCMC (van den Berg et al., 2017), three inductive feature-driven methods NIMC (Zhong et al., 2018), PinSAGE (Ying et al., 2018), BOMIC (Ledent et al., 2020), and two recently proposed inductive methods without using features F-EAE (Hartford et al., 2018) and IGMC (Zhang & Chen, 2020). For these competitors, we use all the training data for training. In Table 1, we report test RMSEs for all the users, inductive learning on query users and generalization on new users in Douban, ML-100k and ML-1M. As we can see, IRCF-NN gives very close RMSEs on all the users and query users to NNMF in three datasets while IRCF-GC performs nearly as well as GCMC. The empirical results prove that our inductive model possesses the same expressive power as corresponding transductive model. Compared with inductive methods, IRCF-GC achieves the best RMSEs for query users in three datasets. The results demonstrate the superior expressiveness of proposed inductive model comapred to other feature-driven and local-graph-based inductive models. Besides, for new unseen users, our model IRCF-GC gives state-of-the-art performance, achieving significant improvement over the best competitor, quantitatively 3.2% on Douban, 3.1% on ML-100K and 4.1% on ML-1M.
In Table 2, we compare IRCF-NN and IRCF-GC with PMF, NNMF and GCMC in ML-10M and Amazon-Books. Since the two datasets have no feature, we cannot train feature-driven methods. Also, F-EAE and IGMC are both hard to scale to such large datasets. In Amazon-Books, we replace square loss in our objective as cross-entropy loss and harness AUC as metric to align with implicit feedbacks. We can see that our inductive models achieve very similar RMSEs in ML-10M as transductive models, and even significantly outperform transductive models in Amazon-Books. In fact, Amazon dataset is a very sparse one with rating density 0.0012. One implication here is that our inductive model can provide better performance than transductive models for users with few ratings.
Comparison with cold-start recommendation models We also wonder if our inductive model can handle extreme cold-start users who have no historical rating. Note that cold-start users are different and more challenging compared to new (unseen) users. For new users, the model can still use observed historical ratings as input during test, though it cannot be trained on these ratings. In order to enable cold-start recommendation, we leverage attribute features in Movielens-1M. We use the dataset provided by (Lee et al., 2019), which contain attribute features and split warm-start and cold-start users, and follow its evaluation protocol: using the warm-start users’ training ratings for training and cold-start users’ test ratings for test. We compare with Wide&Deep network (Cheng et al., 2016), GCMC (using feature vectors) and two state-of-the-art cold-start recommendation models AGNN (Qian et al., 2019) and MeLU (Lee et al., 2019). In Table 3, we present test RMSEs for all the models, and we can see that our model IRCF-HY gives the best results, achieving 2.6% improvement over the best competitor MeLU even on the difficult zero-shot recommendation task. The result shows that our inductive model is a promising approach to handle new users with no historical behavior in real-world dynamic systems.
4In such case, we train the base MF model and inductive model over the same users in order.

heading: 4.2 FURTHER DISCUSSIONS
text: Sparse Data and Few-shot users A successful recommender system is supposed to handle data sparsity and few-shot users with few historical ratings. Here we construct several sparse datasets by using 50%, 20%, 10%, 5%, 1% and 0.1% training ratings in Movielens-1M, and then compare the test RMSEs of query users in Fig. 4(a). Also, in Fig. 4(b) we compare the test RMSEs for users with different numbers of historical ratings when under 50% sparsity. As shown in Fig. 4(a), as the dataset becomes sparser,the RMSEs of all the models suffer from a drop, but the drop rate of our inductive models IGCF-NN and IGCF-GC is much smaller compared with transductive models NNMF and GCMC. In Fig. 4(b), we find that users with more historical ratings usually have better RMSE scores compared with few-shot users. By contrast, our inductive models IRCF-NN and IRCF-GC exhibits a more smooth decrease and even outperform other transductive methods NNMF and GCMC for users with very few ratings. In the extrame cases with less than five historical ratings, notably, IRCF-GC achieves 2.5% improvement on RMSE compared with the best transductive method GCMC.
Attention Weight Distribution In Fig. 4(c) we visualize attention weights of IRCF-NN from query users to support users in Movielens-10M. As we can see, there is an interesting phenomenon that some of support users are very ‘important’ and most query users give high attention weights on them, which indicates that the representations of these support users are informative and a combination of them can provide powerful expressiveness for query users’ preferences. In Fig. 4(d) we further plot support users’ accumulated attention weights w.r.t. # historical ratings. We can see that larger attention weights concentrate on support users with more historical ratings. Such observation gives an important hint for selecting optimal support users: important support users are more likely to exist in users with more observed ratings. In Appendix F, we compare different split ways for support and query users and provide more discussions and results on this point.
Scalability Test We further investigate the scalability of IRCF-GC compared with two GNN-based counterparts IGMC and GCMC. We statistic the training time per epoch on Movielens-1M using a GTX 1080Ti with 11G memory. Here we truncate the dataset and use different numbers of ratings for training. The results are shown in Fig. 3 (with log-scale axis). As we can see, when dataset size becomes large, the training times per epoch of three models all exhibit linear increase. IRCF spends approximately one more time than GCMC, while IGMC is approximately ten times slower than IRCF. Nevertheless, while IRCF costs one more training time than GCMC, the latter cannot tackle new unseen users without retraining a model in test stage.

heading: 5 CONCLUSIONS
text: In this paper, we propose a new inductive collaborative filtering framework that learns hidden relational graphs among users to allow sufficient message passing in the latent space. The new model accomplishes inductively computation for user-specific representations without compromising on expressiveness and scalablity. Through extensive experiments, we show that the model can achieve state-of-the-arts performance on inductive matrix completion and outperforms transductive models for users with few training ratings. Interesting future directions include: 1) consider the selection for support users as a decision problem; 2) use meta-learning or transfer learning techniques over our inductive framework; 3) exploit our framework in cross-domain recommendation tasks.
The core idea of IRCF opens a new way for next generation of representation learning, i.e., one can consider a pretrained representation model for one set of existing entities and generalize their representations (through some simple transformations) to efficiently compute inductive representations for others, enabling the model to flexibly handle new coming entities in an open world. We believe that this novel and effective framework can inspire more researches in broad areas of AI.

heading: A LINKS TO RELATED WORKS
text: We provide a thorough discussion on the relationships and differences to related works. In Fig. 5 we present a illustration for comparison with different methods.

heading: B PROOFS IN SECTION 3

heading: B.1 PROOF OF THEOREM 1
text: Proof. The proof is trivial by construction. Assume the optimal P2 for (3) as P∗2. Since P1 given by (1) is column-full-rank, for any column vector p∗u′ in P ∗ 2 (u
′ ∈ U2), there exists c∗u′ such that c∗u′ ⊤P1 = p ∗ u′ . Hence, C ∗ = [c∗u′ ]u′∈U2 is a solution for (2) and gives DS2(R̂2, R2) < ϵ.

heading: B.2 PROOF OF THEOREM 2
text: Proof. With fixed a true rating matrix R2 to be learned and a probability distribution P over [M2]× [N ], which is unknown to the learner, we consider the problem under the framework of standard PAC learning. We can treat the matrix R2 as a function (u′, i) → ru′i. Let R, a set of matrices in RM2×N , denotes the hypothesis class of this problem. Then the input to the learner is a sample of R2 denoted as
T = ( (u′t, it, ru′tit)|(u ′ t, it) ∈ S2 ) ,
where S2 = {(u′t, it)} ∈ ([M2] × [N ])T2 is a set with size T2 containing indices of the observed entries in R2 and each (u′, i) in S2 is independently chosen according to the distribution
P . When using T as training examples for the learner, it minimizes the error DS2(R̂2, R2) = 1 T2 ∑ (u′,i)∈S2 l(ru′i, r̂u′i). We are interested in the generalization error of the learner, which is defined as D(R̂2, R2) = E(u′,i)∈P [l(ru′i, r̂u′i)].
The (empirical) Rademacher complexity of R w.r.t. the sample T is defined as
RadT (R) = 1
T2 Eσ
[ sup
R̂2∈R T2∑ t=1 σtr̂u′tit
] ,
where σt ∈ {−1, 1} is random variable with probability Pr(σt = 1) = Pr(σt = −1) = 12 . We assume l is L-Lipschitz w.r.t. the first argument and |l| is bounded by a constant. Then a general result for generalization bound of R is
Lemma 1. (Generalization bound (Mohri et al., 2012)): For a sample T with random choice of S2 = ([M2]× [N ])T2 , it holds that for any R̂2 ∈ R and confidence parameter 0 < δ < 1,
Pr(D(R̂2, R2) ≤ DS2(R̂2, R2) +G) ≥ 1− δ, (9) where,
G = 2L ·Rad(X ) +O √ ln(1/δ) T2  . Based on the lemma, we need to further estimate the Rademacher complexity in our model to complete the proof. In our model, R̂2 = C⊤P1Q and the entry r̂u′i is given by r̂u′i = p⊤u′qi = c ⊤ u′P1qi (where cu′ is the u′-th colunm vector of C). Define A as a set of matrices,
A = {A ∈ [0, 1]M2×M1 | : au′∥1 = M1∑ u=1 |au′u| = 1}.
Then we have
T2 ·RadT (R) = Eσ [ sup C∈C T2∑ t=1 σtc ⊤ u′t P1qit ] (10)
= Eσ [ sup C∈C M2∑ u′=1 c⊤u′ · ( ∑ t:ut=u′ σtR1,∗it )] (∵ R1,∗it = P1qi) (11)
≤ H · Eσ [ sup A∈A M2∑ u′=1 a⊤u′ · ( ∑ t:ut=u′ σtR1,∗it )] (12)
= H · Eσ [ M2∑ u′=1 max u∈[M1] ( ∑ t:ut=u′ σtruit )] . (13)
The last equation is due to the fact that au′ is a probability distribution for choosing entries in R1,∗it , the it-th column of matrix R̂1. In fact, we can treat the maxu∈[M1] inside the sum over all u
′ ∈ U2 as a mapping κ from u′ ∈ [M2] to u ∈ [M1]. Let K = {κ : [M2] → [M1]} be the set of all mappings from [M2] to [M1], and then the above formula can be written as
Eσ [ M2∑ u′=1 max u∈[M1] ( ∑ t:ut=u′ σtruit )] (14)
= Eσ [ sup κ∈K M2∑ u′=1 ∑ t:ut=u′ σtrκ(u′),it ] (15)
= Eσ [ sup κ∈K T2∑ t=1 σtrκ(ut),it ] (16)
≤ B √ T2 · √ 2M2 logM1. (17)
The last inequality is according to the Massart Lemma. Hence, we have RadT (R) ≤ HB √
2M2 logM1 T2 . (18)
Incorporating (18) into (9), we will arrive at the result in this theorem.

heading: C SPECIFICATIONS OF IRCF
text: In Section 3, we present a general framework for inductive relational collaborative filtering (IRCF) without using features. In the following, we provide two different specifications for fθ in IRCF with neural networks (IRCF-NN) and graph convolution networks (IRCF-GC) which are used in our experiments.

heading: C.1 NEURAL NETWORK AS BASED MODEL (IRCF-NN)
text: We follow the architecture in NNMF (Dziugaite & Roy, 2015) and use neural network for fθ. Here we combine a three-layer neural network and a shallow dot-product operation. Concretely,
fθ(pu,qi) = (p⊤u qi + nn([pu∥qi∥pu ⊙ qi]))
2 + bu + bi, (19)
where nn is a three-layer neural network using tanh activation, ⊙ denotes element-wise product and bu, bi are bias terms for user u and item i, respectively.

heading: C.2 GRAPH CONVOLUTION NETWORK AS BASED MODEL (IRCF-GC)
text: We follow the architecture used in GCMC (van den Berg et al., 2017) and adopt graph convolution network for fθ(). Besides user-specific embedding for user u and item-specific embedding for item i, we consider embeddings for user u’s rated items and users who rated on item i, i.e., the one-hop neighbors of user u and item i in user-item bipartite graph. Denote Nu = {i|rui ̸= 0} as user u’s rated items and Ni = {u|rui ̸= 0} as users who rated on item i. We consider graph convolution to aggregate information from neighbors,
mu = ReLU( 1 |Nu| ∑ i∈Nu Wqqi), (20)
ni = ReLU( 1 |Ni| ∑ u∈Ni Wppu). (21)
Then we define the output function
f(pu,qi, {pu}u∈Ni , {qi}i∈Nu) = nn′([pu ⊙ qi∥pu ⊙mu∥ni ⊙ qi∥ni ⊙mu]) + bu + bi, (22) where nn′ is a three-layer neural network using ReLU activation.

heading: D EXTENSIONS OF IRCF
text: IRCF can be extended to feature-based setting and flexibly deal with zero-shot learning, as is shown in Section 4. Here, we provide details of feature-based IRCF (IRCF-HY) which indeed is a hybrid model that considers both user features and one-hot user indices. Furthermore, we discuss in the views of transfer-learning and meta-learning that can be incorporated with our framework as future study.

heading: D.1 HYBRID MODEL WITH FEATURES (IRCF-HY)
text: Assume au denotes user u’s raw feature vector, i.e., a concatenation of all the features (often including binary, categorical and continuous variables) where categorical features can be denoted by one-hot or multi-hot vectors. If one has m user features in total, then au can be
au = [au1||au2||au3|| · · · ||aum].
Then we consider user-sharing embedding function yi() which can embed each feature vector into a d-dimensional embedding vector:
yu = [y1(au1)||y2(au2)||y3(au3)|| · · · ||ym(aum)]. Similarly, for item feature bi = [bi1||bi2||bi3|| · · · ||bin], we have its embedding representation:
zi = [z1(bi1)||z2(bi2)||z3(bi3)|| · · · ||zn(bin)]. Also, we assume user-specific index embedding pu and item-specific index embedding qi for user u and item i, respectively, as is in Section 3. The prediction for user u’s rating on item i can be
r̂ui = gθ(pu,yu,qi, zi), (23)
where gθ can be a shallow neural network with parameters denoted by θ. To keep notation clean, we denote Y = {y1,y2, · · · ,ym} and Z = {z1, z2, · · · , zn}. Then for support users in U1 with rating matrix R1, we consider the optimization problem,
min P1,Q,Y,Z,θ DS1(R̂1, R1), (24)
based on which we get learned feature embedding functions Y, Z as well as transductive embedding matrices P1, Q which we further use to compute inductive embeddings for query users.
For query users, feature embeddings can be obtained by the learned Y and Z in (24), i.e., yu′ = [yu′1(au′1)|| · · · ||yu′m(au′m)] where au′ is raw feature vector of user u′. Then we have a relation inference model hw that consists of a multi-head attention function and use user feature as input du′ = yu′ . The inductive user-specific representation can be given by pu′ = hw(du′) (i.e., (5) and (6)), similar as the CF setting in Section 3. The rating of user u′ on item i can be predicted by r̂u′i = gθ(pu′ ,yu′ ,qi, zi). Also, the optimization of the second stage is
min w,θ DS2(R̂2, R2). (25)

heading: D.2 ZERO-SHOT LEARNING
text: For zero-shot recommendation where test users have no historical rating, we have no information about users if without any side information. In such case, most CF models would fail for personalized recommendation and degrade to a trivial one which outputs the same result (or the same distribution) to all the users using the popularity of items. For IRCF, the set Au′ would be empty for users with no historical rating, in which situation we can randomly select a group of support users to construct Au′ used for computing attentive scores with support users. Another method is to directly use average embeddings of all the support users as estimated embeddings for query users. In such case, the model degrades to ItemPop (using the numbers of users who rated the item for prediction).
On the other hand, if side information is available, our hybrid model IRCF-HY can leverage user features for computing inductive preference embeddings, which enables zero-shot recommendation. We apply this method to zero-shot recommendation on Movielens-1M using features in Section 4 and achieve superior RMSE.

heading: D.3 TRANSFER LEARNING & META-LEARNING
text: Another extension of IRCF is to consider transfer learning on cross-domain recommendation tasks (Singh & Gordon, 2008) or when treating recommendation for different users as different tasks like (Lee et al., 2019). Transfer learning and meta learning have shown power in learning generalizable models that can adapt to new tasks. In our framework, we can also take advantage of transfer learning (few-shot learning or zero-shot learning) or mete-learning algorithms to train our relation inference model hw. For example, if using model-agnostic meta-learning algorithm for the secondstage optimization, we can first compute one-step (or multi-step) gradient update independently for each user in a batch and then average them as one global update for the model. The meta-learning can be applied over different groups of users or cross-domain datasets.

heading: E DETAILS IN IMPLEMENTATIONS
text: We provide implementation details that are not presented in Section 4 in order for reproducibility.

heading: E.1 DATASETS
text: The statistics of datasets used in our experiments are summarized in Table 4. We use the preprocessed versions of Douban and Movielens-100K provided by (Monti et al., 2017). For Movielens1M and Movielens-10M 5, we use the same 9:1 training/test split as previous works. The original ML-1M dataset has a few user features and a recent work (Lee et al., 2019) collects a new dataset with more features for both users and items6. We use this version for our feature-based setting on ML-1M in experiments. The raw dataset for Amazon-Books 7 is a very large and sparse one and we filter out infrequent items and users with less than five ratings.

heading: E.2 HYPER-PARAMETER SETTINGS
text: We present details for hyper-parameter settings in different datasets. We use L = 4 attention heads for our inductive relation inference model among all the datasets. For Douban and ML-100K, each attention head randomly samples 200 support users for computing attention weights. For ML-1M and ML-10M, we set sample size as 500; for Amazon-Books, we set it as 2000. We use Adam optimizer and learning rates are searched within [0.1, 0.01, 0.001, 0.0001]. For the first-stage transductive training, we consdier L2 regularization for user and item embeddings. The regularization weights are searched within [0.001, 0.002, 0.005, 0.01, 0.02, 0.05, 0.1, 0.2]. The mini-batch sizes are searched within [64, 256, 512, 1024, 2048] to keep a proper balance between training efficiency and performance. Also, different hyper-parameters for architectures are used in three implementations.
IRCF-NN. For Douban and ML-100K, we use embedding dimension d = 16 and neural size 48 − 32 − 32 − 1 for fθ. For ML-1M, ML-10M and Amazon-Books, we use d = 32 and neural size 96− 64− 64− 1 for fθ. IRCF-GC. For Douban and ML-100K, we use embedding dimension d = 32 and neural size 128− 32 − 32 − 1 for fθ. For ML-1M, ML-10M and Amazon-Books, we use d = 64 and neural size 256− 64− 64− 1 for fθ. IRCF-HY. We use embedding size d = 32 for each feature in ML-1M as well as user-specific and item-specific index embeddings. The neural size of gθ is set as 320− 64− 64− 1.

heading: E.3 DETAILS FOR COMPARATIVE METHODS
text: For each comparative model in our experiments, we mainly rely on the designs and setups in their papers and, if necessary, tune its hyper-parameters to obtain optimal results in each dataset. Here we provide some implementations details for MeLU (Lee et al., 2019), AGNN (Qian et al., 2019), IMC (Zhong et al., 2019), and BOMIC (Ledent et al., 2020).
5https://grouplens.org/datasets/movielens/ 6https://github.com/hoyeoplee/MeLU 7http://jmcauley.ucsd.edu/data/amazon/
• MeLU. We use the source codes provided by the paper8. The author provides two versions of the model, MeLU-1 and MeLU-5, different from using one-step or five-step local updates for each global update. We report the best results of the two in our experiments.
• AGNN. We build user-user (resp. item-item) graph according to cosine similarities of features and rating records of users (resp. items). In specific, we add an edge from i to j when i is among j’s top 10 nearest nodes. In order for the consistency of feature dimension, we use a linear model to transform the original one-hot or multi-hot representation of each feature into a vector with fixed dimension. When training the eVAE model, we use Euclidean distance instead of cross-entropy between the original features and reconstructed features for calculating reconstruction loss.
• IMC. We first use a two-layer neural network to transform the multi-hot user/item features into low-dimensional vector representations. Then we calculate the dot-product of the the features of user-item pairs to make predictions.
• BOMIC. We use the version BOMIC+ in our experiments. To be specific, the model incorporates user features, item features, item bias, user bias as well as user/item index embeddings to predict the possible rating between users and items.
Evaluation Metrics We provide details for our adopted evaluation metrics. In our experiments, we follow evaluation protocols commonly used in previous works in different settings. Three metrics used in our paper are as follows.
• AUC: This is a measurement for consistency of recommendation list ranked by predicted scores and ground-truth clicking list with 1s before 0s. It counts the average area under the curve of true-positive v.s. false-positive curve for one user’s ranking list:
AUCu =
∑ i∈I+u ∑ j∈I−u δ(ŷu,i,j > 0)
|I+u ||I−u | , (26)
where I+u = {i|rui > 0} and I−u = {j|ruj = 0} denote the sets of clicked items and not clicked items by user u respectively. The indicator δ(r̂ui > r̂uj) returns 1 when r̂ui > r̂uj and 0 otherwise. AUC is used For implicit feedbacks. Since we only have ground-truth positive examples (clicked items) for each user, we negatively sample five items as negative examples (non-clicked items) for each user-item rating in dataset.
• RMSE: Root Mean Square Error measures the averaged L2 distance between predicted ratings and ground-truth ratings:
RMSEu =
√√√√√ ∑ i∈I+u (r̂ui − rui)2
|I+u | . (27)
• MAE:Mean Absolute Error measures the averaged L1 distance between predicted ratings and ground-truth ratings:
MAEu =
∑ i∈I+u |r̂ui − rui|
|I+u | . (28)

heading: F DISCUSSIONS ON DIFFERENT CONFIGURATIONS FOR SUPPORT AND QUERY USERS
text: In our experiments in Section 4, we basically consider users with more than δ training ratings as U1 and the remaining as U2, based on which we construct support users and query users to study model’s expressiveness in inductive learning and generalization on new unseen users. Here we provide a further discussions on two spliting ways and study the impact on model performance.
• Threshold: we select users with more than δ training ratings as U1 and users with less than δ training ratings as U2.
8https://github.com/hoyeoplee/MeLU
We consider δ = [20, 30, 40, 50, 60, 70] and γ = [0.97, 0.85, 0.75, 0.68, 0.62, 0.57] (which exactly gives the same ratio of |U1| and |U1| as corresponding δ in threshold split9) in Movielens-1M dataset. For each spliting, we also consider two situations for support users and query users: 1) U1 = U1 and U2 = U2; U1 = U2 = U1. The results of IRCF-NN are presented in Table 5 where we report test RMSEs on all the users, query users and new users.
As we can see from Table 5, in threshold split, as δ increases (we have fewer support users and more query users and they both have more training interactions on average), test RMSEs for query users exhibit a decrease. The reason is two-folds: 1) since support usres have more training ratings, the transductive model can learn better representations; 2) since query users have more training ratings, the inductive model would have better generalization ability. On the other hand, with different spliting thresholds, test RMSEs for new users remain in a fixed level. The results demonstrate that our model performance on new unseen users is not sensitive to different split thresholds. However, in random split, when γ decreases (also we have fewer support users and more query users but their average training ratings stay unchanged), RMSEs for new users suffer from an obvious decrease. One possible reason is that when we use smaller ratio of support users in random split, important support users in the dataset are more likely to be ignored. (As is shown in Fig. 4(c) in Section 3, there exist some important support users that give high attention weights for query users.) If such support users are missing, the performance would be affected due to insufficient expressive power of inductive model.
Comparing threshold split and random split, we can find that when using the same ratio of support users and query users (i.e., the same column in Table 5), RMSEs on new users with threshold split are always better than those with random split. Such observation shows that support users with more training ratings would be more effective for inductive learning and again accord with the results in Fig. 4(d) which demonstrates important support users who give large attention weights for query users tend to exist in users with many training ratings.
9For example, using γ = 0.97 in random split will result in the same sizes of U1 and U2 as using δ = 20 in threshold split.

Review summaries:
This work explores a popular problem, i.e., collaborative filtering, in an inductive setting, which is very important for real-world recommender systems. To address the challenges in the inductive settings, i.e., learning accurate representations for users who do not occur in the training data, the authors propose to construct a relational graph between users in the training data and new users based on a standard matrix factorization model and then use an attentive message passing framework to inductively compute user-specific representations. Besides, the authors prove the expressive and generalization capabilities of the proposed framework. Extensive experiments are conducted to demonstrate the effectiveness of the proposed framework both in transductive and inductive settings, as well as the scalability.

This paper proposed an inductive collaborative filtering method, called IRCF. The goal is to possess expressiveness (against feature-driven methods) as well as generalization (against one-hot encoding based methods). In IRCF, there are a matrix factorization model for support users and a relation model for query users. The former is trained with transductive learning to obtain support users embeddings and item embeddings. The relation model then generates query user embeddings as weighted sum of support user embeddings by examining relational graph between support and query users.

This work proposed an inductive recommendation framework on user-item relation graphs. Such a framework relies on the user-item relations without the requirement of side-information and perceives certain flexibility in terms of the parametrization for user/item representations. The authors also provided theoretical analysis to highlight some mathematical insights out of this framework. The proposed method is evaluated on three real-world datasets and compared with several baselines.