Recommender systems aim to recommend items to users based on their interests. Traditional models usually adopt batch processing. Considering that user feedback is generated continuously, it becomes desirable to design models that are capable of learning as data arrives. In this work, we propose an incremental graph of sequential user interactions using implicit feedback from a data stream, with the assumption that user behavior can be extracted from such sequence of interactions as time passes. The model was evaluated by recommending items with diferent strategies, and such strategies were compared with an incremental matrix factorization algorithm, using a prequential approach. Results highlight the potential of the proposed method, which obtained superior accuracy than the baseline with generally better update and recommendation times.
• Information systems → Recommender systems; Data stream mining; • Theory of computation → Online algorithms.
Given the massive amount of data available in online services of various sorts, ways of filtering information to users are necessary in order to improve their interaction with the system. Recommender systems are designed to filter such data, guiding users through the item collection by presenting items based on their preferences.
Collaborative filtering (CF) is an efective technique to solve
this problem, in which the prediction of unknown user-item
preferences are inferred based on past user behavior. User feedback
can be explicit, e.g., a user assigns a specific rating to an item,
or implicit, which indirectly captures user behavior, for instance,
through browsing history [
While such approaches are generally efective in terms of predictive capability, there is the assumption that training data is always available for updating the model, and usually temporal sequence is disregarded. Considering that in many real scenarios intrinsically time-dependent data is generated continuously at unprecedented rates, it becomes impractical to update these models as new data is generated.
In that sense, learning and updating a model with one (or few) example(s) is preferable, and even required in real-world applications. To that end, incremental algorithms can be used for recommendation by treating feedback as a data stream, i.e., incorporating feedback into the model as data arrives and discarding examples after they are processed.
In this paper, we propose to incorporate implicit user feedback
into a graph in incremental fashion with the assumption that user
behavior can be extracted from the sequence of user interactions
as time progresses, capturing short-term and long-term interests.
To that end, edges are continuously included in the graph and their
weights are updated according to the sequential user interactions,
such that for each incoming user feedback in a data stream, a
directed edge connects the last item interacted by the user to the
current interaction, and the frequency in which this sequential
interaction occurs is reinforced in the weight of the edge. We
evaluated the proposed model by recommending items with diferent
strategies and compare the results with an incremental matrix
factorization method [
The remainder of this paper is organized as follows: Section 2 presents related work. Section 3 presents the proposed approach. Section 4 presents experiments and results. Conclusions and future work are presented in Section 5. 2
This section describes the related work, categorized as follows:
Time-dependent CF. These approaches treat feedback as a
chronological sequence, using time for modeling user preferences,
while implicitly capturing temporal dynamics [
Incremental CF. Recently, studies with incremental CF for
implicit feedback also known as one-class CF [
Graph-based methods. Regarding graph-based methods for
time-dependent recommendation, the following papers are
relevant to the scope of the present work. Xiang et al. [
Our work is influenced by Vinagre et al . [
This section presents the proposed approach, which treats the item recommendation problem under a data stream framework. That is, intrinsically time-dependent data (user feedback) is generated continuously at unprecedented rate and unpredictable order. In that sense, it is desirable to incrementally update the model, while being able to include new concepts and adapt old ones as new data arrives.
Considering the intrinsic relation between data and time, such that user preferences adjust over time, we assume that the sequence of user interaction can be important in defining user behavior. With such definition, potentially relevant item recommendations can be made to users based on past user behavior. As an example, the release of a film can lead a user to watch the director’s past work before watching the film. Another example is the birth of a child. As time progresses, the family can direct their purchases towards products intended for the children as they grow. In that sense, it is reasonable to assume that the sequence of interactions can be useful in modeling short-term and long-term user interest.
Consequently, the premise of this work is to learn user behavior from implicit feedback as time progresses, representing the interactions between users and items in a graph in incremental manner, allowing the inclusion of new incoming users and items continuously. Then, information extracted from past interactions represented in the graph can be used to generate future recommendations. 3.1
In order to continuously capture sequential interactions between users and items, we create a directed graph, where nodes represent items and edges represent user interactions, such that the edge direction indicates the order in which items where visited, i.e., sequential interaction. Thus, an edge from item i to item j exists if a user interacted with item i, and the next interaction was with item j. Therefore, for each new user interaction, the feedback is included into the graph by an edge that connects the last interacted item to the item of the new interaction.
To distinguish the relevance of edges, each edge has an associated weight, where the weights are inversely proportional to the frequency in which a transition is made by users. In other words, the higher the frequency of a sequential interaction of two items, the lower the edge weight between the two items, implicitly measuring the relevance of the edge for future recommendations. Notation used throughout this work is summarized in Table 1.
Figure 1 shows an example of the graph online maintenance, illustrating two possible scenarios based on sequential interaction. Consider the graph presented in Figure 1a and a user u, whose last interaction was with item 5. At some time t , u interacts with item 0. Since there is no edge connecting item 5 to item 0, the edge from item 5 to item 0 is inserted, as illustrated by the dotted edge in Figure 1b. Now consider that after t , u interacts with item 1. Since an edge from item 0 to item 1 exists, its weight must be updated, as denoted in Figure 1c.
We create a weighted directed graph G = (V , E, w ), where V = {v1, v2, ..., vn } ⊆ I denotes the set of nodes and E ⊆ V × V denotes the set of edges. Each edge e has an associated weight w (e ) ∈ R+. We define Su = {(v1, t1), (v2, t2), ..., (vn , tn )} as a list of items interacted by user u ∈ U ordered according to time t . The last interacted item by u is defined as liu ∈ I , i.e., the last element of Su . The graph is updated in an incremental manner considering the current observed interaction.
User feedback is modeled as a data stream, where each observation is defined as < u, i, t >, indicating that user u interacted with item i at time t , i.e., implicit feedback. When updating the graph considering the current observation, it is desirable that the model is able to include feedback from new incoming users and items, while also updating older concepts. In that sense, there are four possible scenarios, as presented in Algorithm 1: (1) User and item are unknown by the system (u < U and i < I ).
In this case, user and item are included in the system, a node for i is added to V , (i, t ) is included in Su and liu ← i; (2) User is unknown and item is known by the system (u < U and i ∈ I ). In this case, user is included in the system, (i, t ) is included in Su and liu ← i. Given that i is the first interaction of u and i is known, there is no change in the graph; (3) User is known and item is unknown by the system (u ∈ U and i < I ). In this case, item is included in the system and a node for i is added into V . In this scenario, u has already interacted with at least one item before. Since this is the first interaction by any user with i, an edge (liu , i ) is included in E, where w ((liu , i )) = 1. Lastly, (i, t ) is included in Su and liu ← i; (4) User and item are known by the system (u ∈ U and i ∈ I ).
In this case, the current sequential interaction is liu to i. If such interaction has happened before, i.e., (liu , i ) ∈ E, then w (e ) is updated according to Equation (1): w ((liu , i )) = w ((liu , i )) · ρ (1) where ρ ∈ (0, 1) is a parameter that controls the impact of the interaction in the edge weight. If this is the first time such interaction happens, an edge (liu , i ) is included in E, where w ((liu , i )) = 1. Lastly, (i, t ) is included in Su and liu ← i. D = < u, i, t >: data stream; liu = last item interacted by user u; for < u, i, t >∈ D do if u ∈ U then if i ∈ I then if (liu , i ) ∈ E then
w ((liu , i )) ← w ((liu , i )) · ρ; else end
E ← E ∪ {(liu , i )}; w ((liu , i )) ← 1; else
I ← I ∪ {i }; V ← I ∪ {i };
E ← E ∪ {(liu , i )}; end else
U ← U ∪ {u }; if i < I then
I ← I ∪ {i };
V ← I ∪ {i }; end end Su ← Su ∪ {(i, t )}; liu ← i; end
Algorithm 1: Online graph update 3.2
To evaluate the information that is inserted in the graph over time, we tested a few approaches to generate recommendations for users based on items in the list of interactions S. As baseline for comparisons we use the in-degree centrality, that can be seen as a popularity measure. The in-degree centrality captures the number of predecessors that a node has, and is calculated as: indeдree (v ) = |P (v ) | , |V |−1 where P (v ) is the set of predecessors of node v. A recommendation is generated by calculating the in-degree centrality of all items and then recommending the k items with the highest values. This recommendation method does not distinguish users and simply recommends items with high centrality. We refer to this algorithm as in-degree.
To assess the influence of the most recent interaction on user
interest, two strategies based only on the last item interacted by the
user u, i.e., liu were evaluated. In these approaches, candidate items
are filtered out as items that are successors to liu . The first strategy
considers the in-degree centrality. To generate recommendations
to a user u, we calculate the in-degree centrality for all successors
of liu . The k items with highest values are then recommended to u.
We refer to this algorithm as in-degree_liu. The second strategy,
edge_weight_liu, considers the weight of edges that connects liu
to its successors as a measure of item relevance. Considering the
manner in which the graph is constructed, this approach values the
amount of times a sequential interaction happens. Candidate items
j are ordered according to the weight of the edge that connects
(a) Example of a graph before updates based on user
interactions.
(b) Insertion of edge from item 5 to item 0 based on a
sequential interaction.
(c) Weight update of edge from item 0 to item 1 based on
a sequential interaction.
liu to j, and the k items with the lowest weight are recommended.
A similar approach has been shown to be efective in addressing
cold-start issues in Trevisiol et al. [
To model long-term interest, recommendations to a user u are generated based on the entire list of interactions Su . Two approaches that filter candidate items as successors to nodes in Su were tested. The first approach measures the influence of sequential item interaction, where the relevance of candidate items are measured according to the weight of edges, similar to edge_weight_liu . The value a(j ) that represents a candidate item j is the lowest weight between all the edges that connects a node in Su to j, i.e., a(j ) = min(w ((v, j ))), ∀v ∈ Su , w ((v, j )) < 1. The k items with lowest a(j ) are then recommended to u. We refer to this algorithm as edge_weight_Su. The second approach, path_count_Su, considers an item j to be relevant to u based on the number of short paths between items in Su and j, i.e., an item j is relevant to u if j is successor to several items in Su . To recommend k items to u, for each candidate item j we associate a value c (j ) that counts the amount of predecessors of j in Su , i.e., c (j ) = P(v, j ) ∈E 1, ∀v ∈ Su , w ((v, j )) < 1. The k candidate items with highest c (j ) are recommended. We discard information from edges where w (e ) = 1 since they indicate that the sequential interaction occurred only once.
Assuming that user preferences change over time, we have adapted strategies edge_weight_Su and path_count_Su to generate recommendations based on the r most recent user interactions. The resulting approaches, edge_weight_r and path_count_r, filter candidate items j for a user u as successors to the last r items in the ordered list of interactions Su . Considering rSu as the last r items in Su , edge_weight_r associates for each candidate item j a value ar (j ) = min(w ((v, j ))), ∀v ∈ rSu , w ((v, j )) < 1 and recommends the k items with the lowest ar (j ). Algorithm path_count_r associates for each candidate item j a value cr (j ) = P(v, j ) ∈E 1, ∀v ∈ rSu , w ((v, j )) < 1 and recommends the k items with highest cr (j ). The impact of parameter r is evaluated through experiments reported in Section 4.4. 4
In this section we report the experiments performed to evaluate the recommendations generated by the proposed approach, describe the evaluation methodology and discuss the obtained results. We compare the results with ISGD and present an analysis based on the results. 4.1
In order to evaluate the proposed approach on a data stream, a
suitable evaluation methodology is required. In that sense, we use
the prequential evaluation protocol proposed by Vinagre et al. [
We measure accuracy through the HitRate@N metric at cutofs of N ∈ {1, 5, 10}. HitRate@N returns 1 if item i is within the N first recommended items, and 0 otherwise. 4.2
Two datasets from the movie domain were used, as summarized
in Table 2. The MovieLens-1M dataset1 contains around 1.000.000
timestamped ratings in a 1 to 5 scale. The Netflix dataset 2
contains around 100.000.000 timestamped ratings in a 1 to 5 scale. To
simulate continuous implicit feedback, we discarded ratings below
5 and sorted events chronologically, where events are defined as
< user , item, time >. For the Netflix dataset, we dropped users and
items with less than 10 interactions, and then selected ratings from
10.000 randomly selected users.
We compare the accuracy of the recommendation methods
described in Section 3.2 with ISGD [
Besides HitRate@N to evaluate accuracy, we also measure the
average time to update the model and to generate recommendations.
As stated in Section 3.1, edge weights are updated based on Equation
1, that updates the weight of an edge based on parameter ρ. In the
subsequent experiments, we set ρ = 0.9. Applying the same value
of ρ for every update does not distinguishing the importance of an
interaction and simply decreases the weight based on the number
of sequential interactions. All experiments were implemented in
Python 2.7, with the NetworkX library [
As discussed in Section 3.2, algorithms edge_weight_r and path_count_r generate recommendations to a user u based on the r most recent interactions in Su . To that extent, we conducted experiments to evaluate the impact of r in the accuracy of both algorithms with metric HitRate@10. The results of these experiments for both datasets are presented in Figure 2. 1https://grouplens.org/datasets/movielens/1m/ 2https://netflixprize.com/
For the MovieLens-1M dataset in Figure 2a, starting from r = 20, we can see that accuracy increases for algorithm edge_weight_r as r decreases until its peak at r = 3. For all values of r , edge_weight_r obtained accuracy above 0.11%. We emphasize that r = 1 corresponds to algorithm edge_weight_liu . For the path_count_r algorithm, we can see that accuracy tends to grow as we decrease r until its peak at r = 5, and then decreases considerably after r = 3. The decrease occurs because it becomes more dificult to distinguish candidate items with less edges to them.
For the Netflix dataset in Figure 2b, starting from r = 30, the accuracy for algorithm edge_weight_r slightly increases as r decreases until reaching its peak at r = 7. After r = 7 the accuracy remains steady until reaching r = 3 and then drops considerably. For algorithm path_count_r , accuracy reaches its peak at r = 13 and then decreases as r decreases.
Overall, edge_weight_r is relatively stable to r , obtaining similar accuracy for diferent values of r , while path_count_r is less stable, given that it needs more feedback to distinguish candidate items. We note that the recommendation time is associated with r , since the algorithms iterate the successors to the last r nodes in Su . Thus, recommendation time can be reduced by lowering r . In that sense, considering that lower values of r can obtain reasonable accuracy while generating faster recommendations, it is interesting to consider the most recent interactions when modeling user behavior. For overall results presented next, for the MovieLens-1M dataset we set r = 3 to edge_weight_r and r = 5 to path_count_r . For the Netflix dataset we set r = 7 and r = 13 respectively.
Table 3 presents overall results for all algorithms. Accuracy is measured through HitRate@N with N ∈ {1, 5, 10} and time is measure through average update and recommendation times, with the best results highlighted in bold.
Observing the results presented in Table 3, we can see that edge_weight_r has better accuracy compared to all other methods for both datasets, also being the second fastest method. ISGD is outperformed in accuracy by all graph-based methods, and the two in-degree methods obtained the worst accuracy among the graph-based methods.
Although algorithms edge_weight_Su and path_count_Su obtained superior results to the baselines, they have a high recommendation time, since recommendation time is proportional to the size of Su , which can make these algorithms impractical in some scenarios. However, time is substantially decreased with improved accuracy with its counterparts that only consider the most r recent interactions, i.e., edge_weight_r and path_count_r .
Comparing methods in-degree_liu and edge_weight_liu , we can see that edge_weight_liu outperforms in-degree_liu both in accuracy and recommendation time, with edge_weight_liu presenting competitive results for MovieLens-1M, also being the fastest algorithm overall.
For both datasets, the three strategies based on edge_weight are among the four best algorithms, together with path_count_r . These results suggest the potential of including information from sequential interactions into the recommendations.
In terms of update time, both ISGD and graph-based methods achieve competitive results, with graph-update being faster since the update consists in inserting a new edge or updating an edge (a) MovieLens-1M weight based on the current interaction. Considering recommendation time, all algorithms but those that generate recommendations based on Su present acceptable time, since recommendation time is proportional to the number of items. We note that ISGD is more eficient in terms of space complexity since it grows linearly to the number of users and items, while the space complexity for the graph with an adjacency list is O (|V | + |E |).
In Figure 3 we present the accuracy of all algorithms over time with a moving average of the HitRate@10 metric for both datasets with a window of size n = 5000 to further evaluate the learning behavior of all algorithms through time. The evolution reinforces that edge_weight_r is superior than other algorithms throughout most of the time for both datasets. For the MovieLens-1M, all algorithms present similar behavior, with similar peaks and a decrease at the end. For both datasets, graph-based methods outperforms ISGD over time. 5
In this work, we proposed an incremental graph of sequential user interactions using implicit feedback, with the assumption that user behavior can be inferred from such sequence of interactions through time. We evaluated the model by recommending items with diferent strategies on two movie domain datasets and compared results with an incremental matrix factorization algorithm, ISGD, using (a) MovieLens-1M prequential evaluation. In terms of accuracy, the graph-based methods outperformed ISGD, generally with better recommendation time. The best results were achieved by considering the weight of the edges that connect the r most recent user interactions with the candidate items.
A limitation of the proposed approach is that it requires
suficient data from several users in order to distinguish items based
on the sequential interactions. In future work we aim to explore
ways to overcome this limitation. Another aspect is how to update
the edges according to user sessions. In that sense, future work
also include evaluation of dynamic values for ρ, for instance, based
on the time elapsed between the interactions of u with liu and
i, considering the similarity between liu and i and based on the
number of interactions made by u. We also intend to include loss of
edge relevancy through time, explore diferent ways of generating
recommendations based on the graph, such as including
information from both edge_weight and path_count into recommendations
and make comparisons with other incremental algorithms, such as
item-based K-nearest neighbors [
The authors would like to thank CAPES for the financial support.