Semi-supervised Learning Meets Factorization: Learning to Recommend with Chain Graph Model

SSL uses unlabeled data to either modify or reprioritize hypotheses obtained from labeled data alone (Seeger, 2002). Among the existing SSL techniques, graph-based SSL is the most promising one, which alleviates data sparsity problem by performing label propagation on the affinity graphs, and its main insight is graph-based smoothness (Zhu et al., 2003; Fang et al., 2014). In the literature, several different objective functions are proposed to realize graph-based smoothness, e.g., Harmonic Function (HF) (Zhu et al., 2003) and Green’s Function (GF) (Ding et al., 2007). Take HF for example, it minimizes the rating difference between close nodes and thus achieves smoothness on $\mathcal{G}$, which is the same as propagate the known labels to the unknown ones on the affinity graph (Zhu and Ghahramani, 2002). So far, there are several research directly adopting SSL to do rating prediction (Wang et al., 2006; Ding et al., 2007; Wang and King, 2010). However, as described in Section 1, directly adopting them in RS suffers from scalability and unreliable affinity problems.

Generally, existing LFMs can be divided into three types: basic matrix factorization (MF) that only uses U-I rating matrix to do prediction, side information aided MF that uses other side information besides the U-I rating matrix, and latent factor restriction models that consider user/item affinity graphs.

First, regression-based latent factor model (RLFM) (Agarwal and Chen, 2009) and factorization machines (Rendle, 2010) were proposed to incorporate context information to improve recommendation performance. However, these context information are not always available and hard to obtain, and thus they are out of the scope of this paper. Second, the integration of factor model and LDA (fLDA) (Agarwal and Chen, 2010) further incorporates item content information into RLFM. Third, Wang et al. propose collaborative topic regression (CTR) (Wang and Blei, 2011), which systematically combines PMF and latent Dirichlet allocation (LDA) (Blei et al., 2003). CTR uses PMF to factorize U-I rating information and uses LDA to mine item content information. It has been proven that CTR outperforms fLDA in a similar setting, since fLDA largely ignores the other users ratings (Wang and Blei, 2011). Later, CTR-SMF (Purushotham et al., 2012) was proposed to factorize not only rating information but also user social information to make a better recommendation.

However, existing LFMs only fit the model by minimizing the difference between the rare known ratings and the predicted ratings, and do not consider rating smoothness nature between similar U-I pairs.

LFR is actually not the smoothness insight as captured in SSL, i.e., rating smoothness. LFR is much stronger than rating smoothness constrain, because LFR leads to rating smoothness, but not the other way around. Take an item affinity graph for example: based on the assumption of LFR, all the ratings of the connected items should be similar, since neighbors have similar latent factors. That is, LFR indicates smoothness exists everywhere on an affinity graph. Our experiments in Section 7 will demonstrate that this overly strong assumption will fail particularly in data sparsity scenarios.

CGM is a probabilistic model that combines Bayesian network and Markov random field. Bayesian network is useful to express causal relationships between random variables (Bishop, 2006), and it is popularly used in the existing LFMs (Mnih and Salakhutdinov, 2007; Agarwal and Chen, 2009; Wang and Blei, 2011), which use Bayesian network to express the rating generation procedure. Markov random field is suited to express soft constraints between random variables (Bishop, 2006), and its applications also include recommender systems (Domingos and Richardson, 2001). Chain graph models contain both Bayesian network and Markov random field, and thus can represent a broader class of distributions, and it has been used in applications include image de-noising (Mackey, 2007), while, surprisingly, not in RS so far.

There are existing works try to bridge collaborative filtering and SSL (Cao et al., 2013; Zhang et al., 2014; Yang et al., 2017). For example, Semi-SAD (Cao et al., 2013) tried to combine the idea of collaborative filtering and SSL for shilling attack detection tasks. The semi-supervised co-training (CSEL) framework (Zhang et al., 2014) first proposes two context-aware factorization models by leveraging “more general” sources such as age and gender of a user, or the genres. Then, it builds a semi-supervised learning process by assembling two models generated with the above context-aware model. This method belongs to context-aware recommendation approaches and needs to use contextual information, e.g., user age and item category, which is out-of-the-scope of our paper. Preference and context embedding (PACE) (Yang et al., 2017) aim to bridge collaborative filtering and graph-based SSL to do point-of-interest (POI) recommendation through a neural approach, which is the most relevant and state-of-the art model. Specifically, PACE uses Skipgram (Mikolov et al., 2013) to model graph-based context information as the SSL part, and uses a multi-layer neural network to model user-POI interaction information as the collaborative filtering part.

In this paper, we propose a novel CGM to marry LFM with SSL to do the geneal recommendation tasks, and we also propose a confidence-aware approach to solve the overly strong assumption of LFR. Our work is different from it mainly from the following three aspects: (1) PACE only aims to do POI recommendation, while our model can be applied into most recommendation scenarios; (2) The objective function of PACE is designed for binary ratings (i.e., a rating $r_{ij}\in\{0,1\}$), while our model is suitable for any rating scales (i.e., a rating $r_{ij}\in\mathds{R}$); (3) PACE assumes the affinity graph is reliable due to its application to POI recommendation where affinity graph can be built using location information. In contrast, as one of the main contributions of our work, we propose a solution for alleviating the graph unreliable problem in many general recommendation situations. We will show the comparison results in experiments: the performance of PACE is limited in the general recommendation scenarios where affinity graph is unreliable.

We first define our recommendation problem. Given a user set $\mathds{U}=\{u_{1},...,u_{I}\}$ and an item set $\mathds{V}=\{v_{1},...,v_{J}\}$, there are totally $I\times J$ ratings, among which only $\mathscr{L}$ ratings are known, and our recommendation task is to predict the unknown ratings, with the size of $\mathscr{U}=I\times J-\mathscr{L}$.

As described in Section 1, SSL and LFM are popularly used to solve the above recommendation problem, however, they have their own merits and disadvantages. Since we want to marry SSL with LFM, we first use a toy example to illustrate how SSL and LFM make recommendation separately. Let $\bm{R}$ be the U-I rating matrix, with each element $R_{ij}$ denoting the rating that $u_{i}$ gives to $v_{j}$. Let $\bm{r}$ be the predicted U-I rating matrix, with its real-valued rating $r_{ij}$ denoting the predicted rating of $u_{i}$ on $v_{j}$. Figure 1 (a) shows a U-I rating matrix example, where we have two users ($u_{1}$ and $u_{2}$), two items ($v_{1}$ and $v_{2}$), and two known U-I rating pairs ($R_{11}$ and $R_{22}$). Our mission is to predict the two unknown U-I pairs ($r_{12}$ and $r_{21}$).

Graph-based SSL makes recommendation mainly based on the smoothness idea on affinity graphs. Since each data object in RS is a U-I rating pair, to make recommendation, SSL first needs to build a U-I pairwise affinity graph, and then propagates the known U-I rating pairs to the unknown ones. Let $\mathcal{G}=(\mathcal{V},\mathcal{E})$ be a U-I pairwise affinity graph with nodes $\mathcal{V}$ denoting data objects, edges $\mathcal{E}$ denoting the affinitive relationship between nodes, and weight matrix between edges $P$ denoting the affinitive relation strength between nodes. Figure 1 (b) shows how to adopt SSL to do recommendation, where the affinity graph $\mathcal{G}$ is shown in dash lines, and we do not show the edge weight for conciseness. Predictions will be made by propagating $R_{11}$ and $R_{22}$ to $r_{12}$ and $r_{21}$. That is, the purpose of SSL is rating smoothness on affinity graphs, and SSL captures the mutual dependency between ratings.

LFM makes recommendation mainly based on the dimensionality reduction idea. Let $\bm{U}\in{}\mathds{R}^{K\times{}I}$ and $\bm{V}\in{}\mathds{R}^{K\times{}J}$ be the user and item latent feature matrixes, with their column vectors $\bm{U_{i}}$ and $\bm{V_{j}}$ representing the K-dimensional latent vectors of $u_{i}$ and $v_{j}$ respectively. Figure 1 (c) shows how to use LFM to do recommendation. LFM predicts the unknown ratings by learning user and item latent factors through regressing on the known ones. In this example, LFM predicts $r_{12}$ and $r_{21}$ by learning $U_{1}$, $U_{2}$, $V_{1}$, and $V_{2}$ through regressing on $R_{11}$ and $R_{22}$. That is, the purpose of LFM is rating regression, and LFM captures the causal dependency between latent factors and ratings.

Although LFM and SSL have different purpose, they both are actually used to capture different dependency between different variables. To marry LFM with SSL, we need a model so that such different dependency between different variables can be captured.

We identify probabilistic CGM, a powerful tool for representing the relationship between variables, to be ideal for marrying LFM with SSL. CGM is a combination of Bayesian network and Markov random field (Koller and Friedman, 2009; McCarter and Kim, 2014). First, Bayesian network, i.e, directed probability graphical model, is commonly used to model the causal dependency between variables. Second, Markov random field, i.e., undirected probability graphical model, is used to model the mutual dependency between variables.

To marry LFM with SSL, the proposed CGM should serve for two goals, as we described in the above example: (1) Rating regression. The predicted rating should be close to the observed rating; (2) Rating smoothness. The predicted ratings should be smooth between close U-I pairs. Thus, we call our model Regression and Smoothness-based Chain Graph Model (RSCGM).

Our proposed RSCGM combines Bayesian network and Markov random field. Figure 1 (d) shows an our proposed CGM example, where we use the directed graph (shows with solid arrows) to model rating generation and known rating regression procedures, and use the undirected graph (shows with dash lines) to model the rating smoothness constrain on an affinity graph. RSCGM is a three layer probabilistic graphical model. The first layer is the latent factor layer, and its nodes are latent variables, i.e., $\bm{U}$ and $\bm{V}$. The second layer is the prediction layer, and its nodes are the predicted ratings, i.e., $\bm{r}$. The third layer is the observation layer, and its nodes are the observed data, i.e., $\bm{R}$. From the latent factor layer to the prediction layer, it is a Bayesian network which denotes the rating generation procedure; I.e., we use $r_{ij}={\bm{U_{i}}}^{T}\bm{V_{j}}$ as the prediction of a U-I pair. The prediction layer is a Markov random field which denotes the prediction smoothness constrain. From the prediction layer to the observation layer, it is another Bayesian network which denotes the rating regression objective, i.e., the predicted rating should be close to the observed rating.

We then derive the conditional probabilities of variables in each layer.

In Eq. (6), we define the first term $\phi_{1}(\bm{U},\bm{V},\bm{r})=\delta(\bm{r}-\bm{U}^{T}\bm{V})$ with $\delta()$ denoting the Dirac delta function (Dirac, 1958), and the property of Dirac delta function indicates that integrating out $\bm{r}$ is equivalent to replacing $\bm{r}$ with $\bm{U}^{T}\bm{V}$, which is the rating generation procedure. The second term $\phi_{2}(\bm{r})=exp\{-E\}$ is probability that constrains rating smoothness with $E$ denoting the rating smoothness energy function on affinity graphs, i.e., the confidence-aware joint-smoothness objective function that we will present in Section 5.

We will present how to learn the MAP distribution over the user and item latent factors in Section 6.

Pairwise smoothness has severe scalability problem. As Section 1 mentioned, building such an affinity graph requires $O{(I\times J)}^{2}$ for $I$ users and $J$ items, i.e., Challenge $\mathcal{II}$. To solve it, we propose an efficient way to perform smoothness.

In RS, each data object connects two elements, i.e., user and item. Thus, rating smoothness implies smoothness exists on two elements, i.e., user and item, and we term it “joint smoothness”. We try to find the relationship between pairwise and joint smoothness. Figure 2 shows a derivation example from pairwise to joint smoothness, where we have three users and two items, and we simply use $(i,j)$ to denote $(u_{i},v_{j})$ pair. For any two pairs on $\mathcal{G}$, e.g., $(u_{i},v_{j})$ and $(u_{k},v_{o})$ ($i\neq j$ or $k\neq o$), based on HF (Zhu et al., 2003), pairwise objective energy function in Eq. (1) can be further divided into the following three terms based on different $(u_{i},v_{j})$ and $(u_{k},v_{o})$ combinations:

where

First, we remove the diagonal edges from the pairwise graph, i.e., remove ${{\mathcal{L}}_{P}^{\prime}}$ from Eq. (9). Figure 2(b) shows the result after we remove the diagonal edges from Figure 2(a). We use $\delta_{U}$ to denote the difference between $r_{ij}$ and $r_{kj}$, i.e., $\delta_{U}=|r_{ij}-r_{kj}|$, $\delta_{V}$ to denote the difference between $r_{kj}$ and $r_{ko}$, i.e., $\delta_{V}=|r_{kj}-r_{ko}|$, and $\delta_{P}$ to denote the difference between $r_{ij}$ and $r_{ko}$, i.e., $\delta_{P}=|r_{ij}-r_{ko}|$. We know that the difference between $r_{ij}$ and $r_{ko}$ has a upper bound of $\delta_{u}+\delta_{v}$, since $|r_{ij}-r_{ko}|=|r_{ij}-r_{kj}+r_{kj}-r_{ko}|\leq|r_{ij}-r_{kj}|+|r_{kj}-r_{ko}|$, i.e, $\delta_{P}\leq\delta_{U}+\delta_{V}$. In other words, the rating smoothness between $(u_{i},v_{j})$ and $(u_{k},v_{j})$ and the rating smoothness between $(u_{k},v_{j})$ and $(u_{k},v_{o})$ will result in the rating smoothness between $(u_{i},v_{j})$ and $(u_{k},v_{o})$. Thus, we can still achieve diagonal rating smoothness after we remove diagonal edges.

Second, we compute the edge affinity weight. The U-I pairwise affinity is determined by both user and item affinity, and thus, we take pairwise affinity as a function of user affinity and item affinity. Specifically, we assume $P_{ij,ko}=F_{P}(F_{U}(u_{i},u_{k}),F_{V}(v_{j},v_{o}))$, where $0\leq F_{U}(u_{i},u_{k})\leq 1$ is a function of the similarity between $u_{i}$ and $u_{k}$, $0\leq F_{V}(v_{j},v_{o})\leq 1$ is a function of the similarity between $v_{j}$ and $v_{o}$, and $0\leq F_{P}(F_{U},F_{V})\leq 1$ is a function of the similarity between $(u_{i},v_{j})$ and $(u_{k},v_{o})$. We also assume $F_{U}(u_{i},u_{i})=1$ for all the users and $F_{V}(v_{j},v_{j})=1$ for all the items, which means that the similarity between a node itself is 1. For any $v_{j}$, since $P_{ij,kj}=F_{P}(F_{U}(u_{i},u_{k}),1)$ holds, i.e., the weight between any $(u_{i},v_{j})$ and $(u_{k},v_{j})$ pairs is the same regardless of $v_{j}$, we can represent all such weights with one, i.e., $W_{ik}=P_{ij,kj}$ which is the similarity between $u_{i}$ and $u_{k}$. Similarly, we use $S_{jo}=P_{kj,ko}$ to represent the similarity between $v_{j}$ and $v_{o}$.

Next, since $W_{ik}=P_{ij,kj}$ and $S_{jo}=P_{kj,ko}$, we can merge nodes, as shown in Figure 2(c). Specifically, we merge nodes $(u_{i},v_{j})$ for the $v_{j}$ into one node $u_{i}$ which has $J$ labels, and we merge nodes $(u_{i},v_{j})$ for all the $u_{i}$ into one node $v_{j}$ which has $I$ labels, as shown in Figures 2(d) and 2(e). That is, we decompose the pairwise graph into user and item joint graphs, and decrease the time complexity to build joint affinity graphs to $O(I^{2}+J^{2})$ by computing the similarity between users and items separately. Thus, ${{\mathcal{L}}_{U}^{\prime}}$ and ${{\mathcal{L}}_{V}^{\prime}}$ change to:

Finally, to achieve joint smoothness, we need to leverage the effect of user and item rating smoothness. To do this, we use two parameters, i.e., $\lambda_{F}$ and $\lambda_{G}$, to control the global smoothness degree on $\mathcal{G}_{1}$ and $\mathcal{G}_{2}$. Combining Eq. (11) and Eq. (12), we define joint smoothness objective as:

where a bigger $\lambda_{F}$ corresponds to a higher user rating smoothness degree on $\mathcal{G}_{1}$ and a bigger $\lambda_{G}$ a higher item rating smoothness degree on $\mathcal{G}_{2}$. We will perform experiments to compare pairwise and joint smoothness in Section 7.4.

We now explain how to build user and item affinity graphs.

We suggest to build user affinity graph using whatever information that is available to capture the affinitive relationships between users, e.g., ratings and user social relationships. For example, user social relationships also indicate users’ common interests, and thus can be taken as the user affinity graph.

One can also build item affinity graph using whatever information that is available to capture the affinitive relationships between items, e.g., ratings and item content information. Frequently, cosine similarity, Jaccard’s coefficient (JC), and Pearson correlation coefficient (PCC) are used to measure rating similarity between items (Ma et al., 2011).

The quality of the affinity graphs, e.g., the reliability and density of the graph, significantly affects the recommendation result. The joint affinity graphs we build are unreliable, since we use rare existing information. Thus, we propose a confidence-aware approach to realize smoothness on them. We will further study the effects the affinity graph on recommendation performance during experiments.

We finally present a confidence-aware approach to realize smoothness, which solves Challenge $\mathcal{III}$ (i.e., unreliable affinity).

The built affinity graphs are unreliable, and thus full smoothness, i.e., assuming smoothness exists everywhere, will be an overly strong assumption. We identify to solve this by using selective smoothness approach. As described in Section 2, rating smoothness can be viewed as propagating known ratings to unknown ones. Since the user affinity graph is unreliable, intuitively, smoothness confidence will decrease with the rating propagation length.

To achieve confidence-aware user rating smoothness, we propose a confidence decay parameter, i.e., $0\leq\alpha\leq 1$, to control rating propagation length. Figure 3 shows a user affinity graph, where we have three users and two items. Although we use only one edge $W_{ik}$ to express the similarity for $(u_{i},v_{j})$ and $(u_{k},v_{j})$ pairs, there is actually a smoothness confidence between them. From Figure 3, we can see how the rating smoothness confidence decreases with propagation length. For example, the smoothness confidence between $(u_{3},v_{1})$ and $(u_{2},v_{1})$ should be bigger than that between $(u_{2},v_{1})$ and $(u_{1},v_{1})$, since the label of $(u_{3},v_{1})$, i.e., $R_{31}$, will first be propagated to $(u_{2},v_{1})$ and then to $(u_{1},v_{1})$.

In general, suppose we have two users ($u_{i}$ and $u_{k}$) and an item ($v_{j}$), we define the smoothness confidence between $(u_{i},v_{j})$ and $(u_{k},v_{j})$ pairs as:

where $\alpha$ is the confidence decay parameter that ranges in [0, 1], and $|d_{i,j,k}|=min\{|d_{i,j}|,|d_{k,j}|\}$ with $|d_{i,j}|$ and $|d_{k,j}|$ denoting the distances from $u_{i}$ and $u_{k}$ to a user whose rating on $v_{j}$ is given, respectively.

The proposed confidence-aware smoothness approach, on one hand, alleviates the overly strong assumption of fully smoothness, and, on the other hand, reduces computation. For $u_{i}$ and $u_{k}$ on $\mathcal{G}_{1}$ and any $v_{j}$, given smoothness confidence in Eq. (14) and following Eq. (11), we define confidence-aware user rating smoothness energy function as:

Similar to user rating smoothness, for $v_{j}$ and $v_{o}$ on $\mathcal{G}_{2}$ and any $u_{k}$, following Eq. (12), we define confidence-aware item rating smoothness energy function as,

where $C_{k,j,o}=\alpha^{|d_{k,j,o}|+1}$ has the similar meaning to Eq. (14).

Following Eq. (13), combining Equations (15) & (16), we define confidence-aware joint smoothness energy function as:

Having $E_{J}$ will enable us to obtain $\phi_{2}(\bm{r})$ shown in Eq. (6).

Our proposed RSCGM is a general model to marry SSL with LFM. As described in Section 2, there are mainly two kinds of LFMs in existing work. Thus, we apply RSCGM into both of them, i.e., a basic MF (BMF) (Mnih and Salakhutdinov, 2007) and a content-based MF (CMF) (Wang and Blei, 2011). BMF assumes zero mean Gaussian on both user and item latent factors, i.e., $\mu_{i}^{U}=\mu_{j}^{V}=0$, while CMF assumes zero mean Gaussian on user latent factor and an item topic allocation mean Gaussian on item latent factor, i.e., $\mu_{i}^{U}=0$ and $\mu_{j}^{V}=\theta_{j}$, where $\theta_{j}$ is the topic allocation learned from item content information using topic modeling technique (Wang and Blei, 2011).

For CMF scenario, we compare RSCGM with the following state-of-the-art methods:

• •

  CMF (Wang and Blei, 2011) is a popular content information aided MF approach.

• •

  CMF-SMF (Purushotham et al., 2012) adds user social factorization in CMF.

• •

  CMF-ULFR (Chen et al., 2014) adds ULFR on CMF.

• •

  CMF-UILFR (Gu et al., 2010) adds UILFR on a weighted nonnegative MF approach. To make a fair comparison, we also replace the weighted nonnegative MF approach with CMF.

• •

  PACE (Yang et al., 2017) proposes a neural approach to bridge collaborative filtering and SSL, and we have distinguished our work from it in Section 2.3. Note that PACE can only support binary ratings and thus we only compare with it on Delicious and Lastfm datasets.

Since ratings range in {‘0’, ‘1’} on Delicious and Lastfm, we use Precision and Recall to evaluate prediction performance (Wang and Blei, 2011; Purushotham et al., 2012). For each user, precision and recall are defined as follows:

where M is the returned items. We compute the average of all the users’ precision and recall in the test dataset as the final result.

We compare our proposed model, i.e., RSCGM, with the state-of-the-art approaches on all the four dataset to prove the effectiveness of our approach. Our experiments are divided into two parts: comparison with the existing BMF-based models and comaprision with the existing CMF-based models.