Exploring Implicit Hierarchical Structures for Recommender Systems

1 Introduction

Recommender systems [Resnick and Varian, 1997] intend to provide users with information of potential interest based on their demographic profiles and historical data. Collaborative Filtering (CF), which only requires past user ratings to predict unknown ratings, has attracted more and more attention [Hofmann, 2004; Zhang et al., 2006; Koren, 2010]. Collaborative Filtering can be roughly categorized into memory-based [Herlocker et al., 1999; Yu et al., 2004; Wang et al., 2006] and model-based methods [Hofmann, 2004; Mnih and Salakhutdinov, 2007; Koren et al., 2009]. Memory-based methods mainly use the neighborhood information of users or items in the user-item rating matrix while model-based methods usually assume that an underlying model governs the way users rate and in general, it has better performance than memory-based methods. Despite the success of various model-based methods [Si and Jin, 2003; Hofmann, 2004], matrix factorization (MF) based model has become one of the most popular methods due to its good performance and efficiency in handling large datasets[Srebro et al., 2004; Mnih and Salakhutdinov, 2007; Koren et al., 2009; Gu et al., 2010; Tang et al., 2013; Gao et al., 2013].

• (a) Faith & Spirituality (b) Music &Musicals (c) half.com

Figure 1: Netflix Movie Hierarchical Structure and half.com Book Hierarchical Structure

Items in real-world recommender systems could exhibit certain hierarchical structures. For example, Figure 1(a) and 1(b) are two snapshots from Netflix DVD rental page 1 . In the figure, movies are classified into a hierarchical structure as genre→subgenre→detailed-category. For example, the movie Schindler's List first falls into the genre Faith Spirituality, under which it belongs to sub-genre Faith & Spirituality Feature Films and is further categorized as Inspirational Stories (see the hierarchical structure shown in Fig. 1(a)). Similarly, Fig. 1(c) shows an Antiques & Collectibles category from half.com 2 . We can also observe hierarchical structures, i.e., category→sub-category. For example, the book Make Your Own Working Paper Clock belongs to Clocks & Watches, which is a sub-category of Antiques & Collections. In addition to hierarchical structures of items, users' preferences also present hierarchical structures, which have been widely used in the research of decision making [Moreno-Jimenez and Vargas, 1993]. For example, a user may generally prefer movies in Faith Spirituality, and more specifically, he/she watches movies under the sub-category of Inspirational Stories. Similarly, an antique clock collector may be interested in Clocks & Watches subcategory under the Antiques & Collections category. Items in the same hierarchical layer are likely to share similar properties, hence they are likely to receive similar rating scores. Similarly, users in the same hierarchical layer are likely to share similar preferences, thus they are likely to rate certain items similarly [Lu et al., 2012; Maleszka et al., 2013]. Therefore, recently, there are recommender systems exploiting explicit hierarchical structures of items or users to improve recommendation performance [Lu et al., 2012; Maleszka et al., 2013]. However, explicit hierarchical structures are usually unavailable, especially those of users.

1 Snapshots are from http://dvd.netflix.com/AllGenresList

2 Snapshot is from http://books.products.half.ebay.com/antiquescollectibles W0QQcZ4QQcatZ218176

The gap between the importance of hierarchical structures and their unavailability motivates us to study implicit hierarchical structures of users and items for recommendation. In particular, we investigate the following two challenges - (1) how to capture implicit hierarchical structures of users and items simultaneously when these structures are explicitly unavailable? and (2) how to model them mathematically for recommendation? In our attempt to address these two challenges, we propose a novel recommendation framework HSR, which captures implicit hierarchical structures of users and items based on the user-item matrix and integrate them into a coherent model. The major contributions of this paper are summarized next:

• We provide a principled approach to model implicit hierarchical structures of users and items simultaneously based on the user-item matrix;
• We propose a novel recommendation framework HSR, which enables us to capture implicit hierarchical structures of users and items when these structures are not explicitly available; and
• We conduct experiments on two real-world recommendation datasets to demonstrate the effectiveness of the proposed framework.

The rest of the paper is organized as follows. In Section 2, we introduce the proposed framework HSR with the details of how to capture implicit hierarchical structures of users and items. In Section 3, we present a method to solve the optimization problem of HSR along with the convergence and time complexity analysis. In Section 4, we show empirical evaluation with discussion. In Section 5, we present the conclusion and future work.

2 The Proposed Framework

Throughout this paper, matrices are written as boldface capital letters such as A and Bi. For an arbitrary matrix M, M(i, j) denotes the (i, j)-th entry ofM. ||M||F is the Frobenius norm of M and Tr(M) is the trace norm of M if M is a square matrix. Let U = {u1, u2, . . . , un} be the set of n users and V = {v1, v2, . . . , vm} be the set of m items. We use X ∈ Rn×m to denote the user-item rating matrix where X(i, j) is the rating score from ui to vj if ui rates vj, otherwise X(i, j) = 0. We do not assume the availability of hierarchical structures of users and items, hence the input of the studied problem is only the user-item rating matrix X, which is the same as that of traditional recommender systems. Before going into details about how to model implicit hierarchical structures of users and items, we would like to first introduce the basic model of the proposed framework.

2.1 The Basic Model

In this work, we choose weighted nonnegative matrix factorization (WNMF) as the basic model of the proposed framework, which is one of the most popular models to build recommender systems and has been proven to be effective in handling large and sparse datasets [Zhang et al., 2006]. WNMF decomposes the rating matrix into two nonnegative low rank matrices U ∈ Rn×d and V ∈ Rd×m, where U is the user preference matrix with U(i, :) being the preference vector of ui, and V is the item characteristic matrix with V(:, j) being the characteristic vector of vj . Then a rating score from ui to vj is modeled as X(i, j) = U(i, :)V(:, j) by WNMF. U and V can be learned by solving the following optimization problem:

where ⊙ denotes Hadamard product and W(i, j) controls the contribution of X(i, j) to the learning process. A popular choice of W is - W(i, j) = 1 if ui rates vj , and W(i, j) = 0 otherwise.

2.2 Modeling Implicit Hierarchical Structures

In weighted nonnegative matrix factorization, the user preference matrix U and the item characteristic matrix V can indicate implicit flat structures of users and items respectively, which have been widely used to identify communities of users [Wang et al., 2011] and clusters of items [Xu et al., 2003]. Since both U and V are nonnegative, we can further perform nonnegative matrix factorization on them, which may pave the way to model implicit hierarchical structures of users and items for recommendation. In this subsection, we first give details about how to model implicit hierarchical structures based on weighted nonnegative matrix factorization, and then introduce the proposed framework HSR.

The item characteristic matrix V ∈ Rd×m indicates the affiliation of m items to d latent categories. Since V is nonnegative, we can further decompose V into two nonnegative matrices V1 ∈ Rm1×m and ˜V2 ∈ Rd×m1 to get a 2-layer implicit hierarchical structure of items as shown in Figure 2(a):

where m1 is the number of latent sub-categories in the 2-nd layer and V1 indicates the affiliation of m items to m1 latent sub-categories. We name ˜V2 as the latent category affiliation matrix for the 2-layer implicit hierarchical structure because it indicates the affiliation relation between d latent categories in the 1-st layer and m1 latent sub-categories in the 2-nd layer. Since ˜V2 is non-negative, we can further decompose the latent category affiliation matrix ˜V2 to V2 ∈ Rm2×m1 and ˜V3 ∈ Rd×m2 to get a 3-layer implicit hierarchical structure of items as shown in Figure 2(b):

Let ˜Vq-1 be the latent category affiliation matrix for the (q - 1)-layer implicit hierarchical structure. The aforementioned process can be generalized to get the q-layer implicit hierarchical structure from (q -1)-layer implicit hierarchical structure by further factorizing ˜Vq-1 into two non-negative matrices as shown in Figure 2(c):

Similarly, to model a p-layer user implicit hierarchical structure, we can perform a deep factorization on U as

where U1 is a n × n1 matrix, Ui (1 < i < p) is a ni-1 × ni matrix and Up is a np-1 × d matrix.

With model components to model implicit hierarchical structures of items and users, the framework HSR is proposed to solve the following optimization problem

An illustration of the proposed framework HSR is demonstrated in Figure 3. The proposed framework HSR performs a deep factorizations on the user preference matrix U and the item characteristic matrix V to model implicit hierarchical structures of items and users, respectively; while the original WNMF based recommender system only models flat structures as shown in the inner dashed box in Figure 3.

3 An OptimizationMethod for HSR

The objective function in Eq.(6) is not convex if we update all the variable jointly but it is convex if we update the variables alternatively. We will first introduce our optimization method for HSR based on an alternating scheme in [Trigeorgis et al., 2014] and then we will give convergence analysis and complexity analysis of the optimization method.

3.1 Inferring Parameters of HSR

Update Rule of Ui

To update Ui, we fix the other variables except Ui. By removing terms that are irrelevant to Ui, Eq.(6) can be rewritten as:

where Ai and Hi, 1 ≤ i ≤ p, are defined as:

And

The Lagrangian function of Eq.(7) is

where P is the Lagrangian multiplier. The derivative of L(Ui) with respect to Ui is

By setting the derivative to zero and using Karush-KuhnTucker complementary condition [Boyd and Vandenberghe, 2004], i.e., P(s, t)Ui(s, t) = 0, we get:

Eq.(12) leads to the following update rule of Ui as:

Update Rule of Vi

Similarly, to update Vi, we fix the other variables except Vi. By removing terms that are irrelevant to Vi, the optimization problem for Vi is:

where Bi and Mi, 1 ≤ i ≤ q, are defined as

and

We can follow a similar way as Ui to derive update rule for Vi as:

Algorithm 1 The Optimization Algorithm for the Proposed Framework HSR.

Input: X ∈ Rn×m, λ, p, q, d and dimensions of each layer Output: Xpred 1: Initialize {Ui}pi=1 and {Vi}qi=1 2: ˜U1, ˜V1 ←WNMF(X, d) 3: for i = 1 to p-1 do 4: Ui, ˜Ui+1 ←NMF( ˜Ui, ni) 5: end for 6: for i = 1 to q-1 do 7: ˜Vi+1, Vi ← NMF( ˜Vi, mi) 8: end for 9: Up = ˜Up, Vq = ˜Vq 10: repeat 11: for i = 1 to p do 12: update Bi and Mi using Eq.(15) and Eq.(16) 13: update Vi by Eq.(17) 14: end for 15: 16: for i = p to 1 do 17: update Ai and Hi using Eq.(8) and Eq.(9) 18: update Ui by Eq.(13) 19: end for 20: until Stopping criterion is reached 21: predict rating matrix Xpred =U1 . . .UpVq . . .V1

With the update rules for Ui and Vj, the optimization algorithm for HSR is shown in Algorithm 3.1. Next we briefly review Algorithm 3.1. In order to expedite the approximation of the factors in HSR, we pre-train each layer to have an initial approximation of the matrices Ui and Vi. To perform pretraining, we first use WNMF [Zhang et al., 2006] to decompose the user-item rating matrix into ˜U1 ˜V1 by solving Eq.(1). After that, we further decompose ˜U1 into ˜U1 ≈ U1 ˜U2 and ˜V1 ≈ ˜ V2V1 using nonnegative matrix factorization. We keep the decomposition process until we have p user layers and q item layers. This initializing process is summarized in Algorithm 3.1 from line 1 to line 9. After initialization, we will do fine-tuning by updating the Ui and Vi using updating rules in Eq.(13) and Eq.(17) separately. The procedure is to first update Vi in sequence and then Ui in sequence alternatively, which is summarized in Algorithm 3.1 from line 10 to line 20. In line 21, we reconstruct the user-item matrix as Xpred = U1 . . .UpVq . . .V1. A missing rating from ui to vj will be predicted as Xpred(i, j)3 .

3.2 Convergence Analysis

In this subsection, we will investigate the convergence of Algorithm 3.1. Following [Lee and Seung, 2001], we will use the auxiliary function approach to prove the convergence of the algorithm.

Definition [Lee and Seung, 2001] G(h, h′ ) is an auxiliary function for F(h) if the conditions

are satisfied

Lemma 3.1 [Lee and Seung, 2001] If G is an auxiliary function for F, then F is non-increasing under the update

Lemma 3.2 [Ding et al., 2006] For any matrices A ∈ Rn×n + ,B ∈ Rk×k + , S ∈ Rk×k + , S′ ∈ Rk×k + and A,B are symmetric, the following inequality holds

Now consider the objective function in Eq.(7), it can be written in the following form by expanding the quadratic terms and removing terms that are irrelevant to Ui

Theorem 3.3 The following function

3 The code can be downloaded from http://www.public.asu.edu/∼swang187/

is an auxiliary function for J (Ui). Furthermore, it is a convex function in Ui and its global minimum is

Proof The proof is similar to that in [Gu et al., 2010] and thus we omit the details.

Theorem 3.4 Updating Ui with Eq.(13) will monotonically decrease the value of the objective in Eq.(6).

Proof With Lemma 3.1 and Theorem 3.3, we have J (U(0) i ) = G(U(0) i ,U(0) i ) ≥ G(U(1) i ,U(0) i ) ≥ J(U(1) i ) ≥ . . . . That is, J (Ui) decreases monotonically.

Similarly, the update rule for Vi will also monotonically decrease the value of the objective in Eq.(6). Since the value of the objective in Eq.(6) is at least bounded by zero , we can conclude that the optimization method in Algorithm 3.1 converges.

3.3 Complexity Analysis

Initialization and fine-tuning are two most expensive operations for Algorithm 3.1. For line 3 to 5, the time complexity of factorization of ˜Ui ∈ Rni-1×d to Ui ∈ Rni-1×ni and ˜Ui+1 ∈ Rni×d is O(tni-1nid) for 1 < i < p, and O(tnn1d) for i = 1, where t is number of iterations takes for the decomposition. Thus the cost of initializing Ui's is O(td(nn1 +n1n2 + · · · +np-2np-1). Similarly, the cost of initializing Vi's is O(td(mm1 +m1m2 + · · · +mq-2mq-1) (line 6 to 8). The computational cost of fine-tuning Ui in each iteration is O(nni-1ni + nnim + ni-1nim). Similarly, the computational cost of fine-tuning Vi in each iteration is O(mmi-1mi + mmin + mi-1min). Let n0 = n,m0 = m, np = mq = d, then the time comlexity of finetuning is O(tf [(n + m)(∑pi=1 ni-1ni + ∑qj=1 mi-1mi) + nm(∑pi=1 ni + ∑qj=1 mj)]), where tf is the number of iterations takes to fine-tune. The overall time conplexity is the sum of the costs of initialization and fine-tuning.

4 Experimental Analysis

In this section, we conduct experiments to evaluate the effectiveness of the proposed framework HSR and factors that could affect the performance of HSR. We begin by introducing datasets and experimental settings, then we compare HSR with the state-of-the-art recommendation systems. Further experiments are conducted to investigate the effects of dimensions of layers on HSR.

4.1 Datasets

The experiments are conducted on two publicly available benchmark datasets, i.e., MovieLens100K 4 and Douban 5 . MovieLens100K consists of 100,000 movie ratings of 943 users for 1682 movies. We filter users who rated less than 20 movies and movies that are rated by less than 10 users from the Douban dataset and get a dataset consisting of 149,623 movie ratings of 1371 users and 1967 movies. For both datasets, users can rate movies with scores from 1 to 5. The statistics of the two datasets are summarized in Table 1.

4 http://grouplens.org/datasets/movielens/

5 http://dl.dropbox.com/u/17517913/Douban.zip

4.2 Evaluation Settings

Two widely used evaluation metrics, i.e., mean absolute error (MAE) and root mean square error (RMSE), are adopted to evaluate the rating prediction performance. Specifically, MAE is defined as

and RMSE is defined as

where in both metrics, T denotes the set of ratings we want to predict, X(i, j) denotes the rating user i gave to item j and ˜X(i, j) denotes the predicted rating from ui to vj. We random select x% as training set and the remaining 1 - x% as testing set where x is varied as {40, 60} is this work. The random selection is carried out 10 times independently, and the average MAE and RMSE are reported. A smaller RMSE or MAE value means better performance. Note that previous work demonstrated that small improvement in RMSE or MAE terms can have a significant impact on the quality of the topfew recommendation[Koren, 2008].

4.3 Performance Comparison of Recommender Systems

The comparison results are summarized in Tables 2 and 3 for MAE and RMSE, respectively. The baseline methods in the table are defined as:

• UCF: UCF is the user-oriented collaborative filtering where the rating from ui to vj is predicted as an aggregation of ratings of K most similar users of ui to vj . We use the cosine similarity measure to calculate user-user similarity.
• MF: matrix factorization based collaborative filtering tries to decompose the user-item rating matrix into two matrices such that the reconstruction error is minimized [Koren et al., 2009].
• WNMF: weighted nonnegative matrix factorization tries to decompose the weighted rating matrix into two nonnegative matrices to minimize the reconstruction error [Zhang et al., 2006]. In this work, we choose WNMF as the basic model of the proposed framework HSR.

• HSR-Item: HSR-Item is a variant of the proposed framework HSR. HSR-Item only considers the implicit hierarchical structure of items by setting p = 1 in HSR.
• HSR-User: HSR-User is a variant of the proposed framework HSR. HSR-Users only considers the implicit hierarchical structure of users by setting q = 1 in HSR.

(c) RMSE for MovieLens100K

60%

(d) MAE for MovieLens100K

60%

Figure 4: Parameter Analysis for HSR.

Note that parameters of all methods are determined via cross validation. Based on the results, we make the following observations:

• In general, matrix factorization based recommender systems outperform the user-oriented CF method and this observation is consistent with that in [Koren et al., 2009].
• Both HSR-Item and HSR-Users obtain better results than WNMF. We perform t-test on these results, which suggest that the improvement is significant. These results indicate that the implicit hierarchical structures of users and items can improve the recommendation performance.
• HSR consistently outperforms both HSR-Item and HSR-Users. These results suggest that implicit hierar-

chical structures of users and items contain complementary information and capturing them simultaneously can further improve the recommendation performance.

4.4 Parameter Analysis

In this subsection, we investigate the impact of dimensions of implicit layers on the performance of the proposed framework HSR. We only show results with p = 2 and q = 2, i.e., W⊙X ≈ W⊙ (U1U2V2V1) with U1 ∈ Rn×n1 ,U2 ∈ Rn1×d ,V1 ∈ Rd×m1 , and V2 ∈ Rm1×m, since we have similar observations with other settings of p and q. We fix d to be 20 and vary the value of n1 as {100, 200, 300, 400, 500} and the value of m1 as {200, 400, 600, 800, 1000}. We only show results with 60% of the datasets as training sets due to the page limitation and the results are shown in Figure 4. In general, when we increase the numbers of dimensions, the performance tends to first increase and then decrease. Among n1 and m1, the performance is relatively sensitive to m1.

5 Conclusion

In this paper, we study the problem of exploiting the implicit hierarchical structures of items and users for recommendation when they are not explicitly available and propose a novel recommendation framework HSR, which captures the implicit hierarchical structures of items and users into a coherent model. Experimental results on two real-world datasets demonstrate the importance of the implicit hierarchical structures of items and those of users in the recommendation performance improvement.

There are several interesting directions needing further investigation. First, in this work, we choose the weighted nonnegative matrix factorization as our basic model to capture the implicit hierarchical structures of items and users and we would like to investigate other basic models. Since social networks are pervasively available in social media and provide independent sources for recommendation, we will investigate how to incorporate social network information into the proposed framework.

6 Acknowledgements

Suhang Wang, Jiliang Tang and Huan Liu are supported by, or in part by, the National Science Foundation (NSF) under grant number IIS-1217466 and the U.S. Army Research Office (ARO) under contract/grant number 025071. Yilin Wang is supported by the NSF under contract/grant number 1135656. Any opinions expressed in this material are those of the authors and do not necessarily reflect the views of the NSF and ARO.