Incremental Graph of Sequential Interactions for Online Recommendation with Implicit Feedback Murilo F. L. Schmitt Eduardo J. Spinosa Federal University of Paraná Federal University of Paraná Curitiba, Paraná, Brazil Curitiba, Paraná, Brazil muriloschmitt@gmail.com spinosa@inf.ufpr.br ABSTRACT While such approaches are generally effective in terms of predic- Recommender systems aim to recommend items to users based on tive capability, there is the assumption that training data is always their interests. Traditional models usually adopt batch processing. available for updating the model, and usually temporal sequence is Considering that user feedback is generated continuously, it be- disregarded. Considering that in many real scenarios intrinsically comes desirable to design models that are capable of learning as data time-dependent data is generated continuously at unprecedented arrives. In this work, we propose an incremental graph of sequential rates, it becomes impractical to update these models as new data is user interactions using implicit feedback from a data stream, with generated. the assumption that user behavior can be extracted from such se- In that sense, learning and updating a model with one (or few) ex- quence of interactions as time passes. The model was evaluated by ample(s) is preferable, and even required in real-world applications. recommending items with different strategies, and such strategies To that end, incremental algorithms can be used for recommen- were compared with an incremental matrix factorization algorithm, dation by treating feedback as a data stream, i.e., incorporating using a prequential approach. Results highlight the potential of feedback into the model as data arrives and discarding examples the proposed method, which obtained superior accuracy than the after they are processed. baseline with generally better update and recommendation times. In this paper, we propose to incorporate implicit user feedback into a graph in incremental fashion with the assumption that user CCS CONCEPTS behavior can be extracted from the sequence of user interactions as time progresses, capturing short-term and long-term interests. • Information systems → Recommender systems; Data stream To that end, edges are continuously included in the graph and their mining; • Theory of computation → Online algorithms. weights are updated according to the sequential user interactions, such that for each incoming user feedback in a data stream, a di- KEYWORDS rected edge connects the last item interacted by the user to the Recommender Systems; Data Streams; Incremental Learning; Im- current interaction, and the frequency in which this sequential plicit Feedback interaction occurs is reinforced in the weight of the edge. We eval- Reference Format: uated the proposed model by recommending items with different Murilo F. L. Schmitt and Eduardo J. Spinosa. 2020. Incremental Graph of strategies and compare the results with an incremental matrix fac- Sequential Interactions for Online Recommendation with Implicit Feedback. torization method [23] using a prequential protocol [21], obtaining In 3rd Workshop on Online Recommender Systems and User Modeling (ORSUM superior accuracy and generally better update and recommendation 2020), in conjunction with the 14th ACM Conference on Recommender Systems, times. September 25th, 2020, Virtual Event, Brazil. The remainder of this paper is organized as follows: Section 2 presents related work. Section 3 presents the proposed approach. 1 INTRODUCTION Section 4 presents experiments and results. Conclusions and future Given the massive amount of data available in online services of work are presented in Section 5. 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 effective technique to solve 2 RELATED WORK this problem, in which the prediction of unknown user-item pref- This section describes the related work, categorized as follows: erences are inferred based on past user behavior. User feedback Time-dependent CF. These approaches treat feedback as a can be explicit, e.g., a user assigns a specific rating to an item, chronological sequence, using time for modeling user preferences, or implicit, which indirectly captures user behavior, for instance, while implicitly capturing temporal dynamics [19]. Approaches through browsing history [9]. Traditional CF approaches such as such as matrix and tensor factorization models have been studied neighborhood methods (K-nearest neighbors) and latent factor mod- [8, 26]. In Das et al. [4], an approach for news recommendation els (matrix factorization) usually adopt batch data processing. using pLSA, MinHash clustering and covisitation counts was pro- posed. The covisitation is implemented as a graph, such that nodes ORSUM@ACM RecSys 2020, September 25th, 2020, Virtual Event, Brazil represent items and edges represent covisitation of items. Baluja Copyright © 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). et al. [2] proposed personalized video recommendation based on covisitation graphs. Assuming that recent data better reflects the ORSUM@ACM RecSys 2020, September 25th, 2020, Virtual Event, Brazil Murilo F. L. Schmitt and Eduardo J. Spinosa interests of users, techniques to increase importance of recent feed- recommendation in an online manner. To that end, we compare our back were proposed, such as decay functions [5, 6, 10] and sliding- approach with ISGD using the prequential evaluation described in windows [13, 15, 22]. Data pre-processing approaches to capture Vinagre et al. [21, 23]. user interest drifts were studied by Cao et al. [3]. For comprehen- sive reviews considering algorithms and methodologies related to 3 PROPOSED APPROACH this topic, we refer the reader to the works of Vinagre et al. [25] This section presents the proposed approach, which treats the item and Quadrana et al. [17]. recommendation problem under a data stream framework. That Incremental CF. Recently, studies with incremental CF for im- is, intrinsically time-dependent data (user feedback) is generated plicit feedback also known as one-class CF [16], have been devel- continuously at unprecedented rate and unpredictable order. In oped. Vinagre et al. [21] proposed an incremental version of the that sense, it is desirable to incrementally update the model, while Stochastic Gradient Descent method [9] (ISGD), which updates the being able to include new concepts and adapt old ones as new data model based solely on the current observation in a data stream. arrives. The paper also proposes a prequential evaluation methodology Considering the intrinsic relation between data and time, such that allows the continuous monitoring of the systems’ predictive that user preferences adjust over time, we assume that the sequence capacity. Considering that in Vinagre et al. [21] all user feedback of user interaction can be important in defining user behavior. With is treated as positive, a follow-up study [24] proposed a recency- such definition, potentially relevant item recommendations can be based scheme to perform negative preference imputation into ISGD made to users based on past user behavior. As an example, the (RAISGD). In Anyosa et al. [1], an incremental co-factorization al- release of a film can lead a user to watch the director’s past work gorithm (CORAISGD) was proposed and compared to RAISGD on before watching the film. Another example is the birth of a child. music domain datasets, obtaining superior results. Ramalho et al. As time progresses, the family can direct their purchases towards [18] presented a robust comparison between incremental matrix products intended for the children as they grow. In that sense, it and tensor factorization. is reasonable to assume that the sequence of interactions can be Graph-based methods. Regarding graph-based methods for useful in modeling short-term and long-term user interest. time-dependent recommendation, the following papers are rele- Consequently, the premise of this work is to learn user behav- vant to the scope of the present work. Xiang et al. [26] incorporate ior from implicit feedback as time progresses, representing the short-term and long-term user preferences into a bipartite graph, interactions between users and items in a graph in incremental Session-based Temporal Graph (STG), where nodes represents users, manner, allowing the inclusion of new incoming users and items items and sessions, and edges balance the influence of short-term continuously. Then, information extracted from past interactions and long-term preferences. User and item nodes are connected represented in the graph can be used to generate future recommen- based on past user interactions, representing long-term preferences. dations. Item and user-session nodes are connected based on user inter- actions in a time window, representing short-term interests. To address cold-start issues, Trevisiol et al. [20] proposed the use of 3.1 Incremental Graph of Sequential two graphs, named BrowseGraph and ReferrerGraph to make news Interactions recommendation to new users. BrowseGraph [11, 12] is built accord- In order to continuously capture sequential interactions between ing to users’ browsing behavior, where nodes represent web-pages users and items, we create a directed graph, where nodes represent and edges connect nodes based on users’ transitions between pages. items and edges represent user interactions, such that the edge ReferrerGraph is a subgraph of the BrowseGraph induced by user direction indicates the order in which items where visited, i.e., sessions with the same referrer domain. To predict the next page to sequential interaction. Thus, an edge from item i to item j exists a newcoming user, the neighbors of both graphs where considered if a user interacted with item i, and the next interaction was with as candidates, and four strategies to select the next page where used: item j. Therefore, for each new user interaction, the feedback is random, content-based, most popular and edge-weight-based, with included into the graph by an edge that connects the last interacted the edge-based approach obtaining the best results. For location rec- item to the item of the new interaction. ommendations, Zhang et al. [27] proposed to incorporate sequential To distinguish the relevance of edges, each edge has an associ- patterns from users’ check-in behaviors in a location-location transi- ated weight, where the weights are inversely proportional to the tion graph in incremental manner, where nodes represent locations, frequency in which a transition is made by users. In other words, the edges represent transitions between locations, and edge weights are higher the frequency of a sequential interaction of two items, the based on transitions count. The proposed method, LORE, integrates lower the edge weight between the two items, implicitly measuring sequential influences with social and geographical information to the relevance of the edge for future recommendations. Notation make recommendations. used throughout this work is summarized in Table 1. Our work is influenced by Vinagre et al. [23] and Trevisiol et al. Figure 1 shows an example of the graph online maintenance, [20]. Vinagre et al. [23] highlights the importance of updating a illustrating two possible scenarios based on sequential interaction. model incrementally by proposing an online evaluation protocol Consider the graph presented in Figure 1a and a user u, whose last and also an algorithm capable of updating the model based solely interaction was with item 5. At some time t, u interacts with item on the current observation in a data stream (ISGD). The work of 0. Since there is no edge connecting item 5 to item 0, the edge from Trevisiol et al. [20] demonstrates the potential of the BrowseG- item 5 to item 0 is inserted, as illustrated by the dotted edge in raph approach for cold start issues, which is directly related to Figure 1b. Now consider that after t, u interacts with item 1. Since Incremental Graph of Sequential Interactions with Implicit Feedback ORSUM@ACM RecSys 2020, September 25th, 2020, Virtual Event, Brazil Table 1: Table of notation. D = < u, i, t >: data stream; liu = last item interacted by user u; Notation Description for < u, i, t >∈ D do if u ∈ U then U Set of users, U = {u 1 , u 2 , ..., um } if i ∈ I then I Set of items, I = {i 1 , i 2 , ..., i n } if (liu , i) ∈ E then V Set of nodes, V w ((liu , i)) ← w ((liu , i)) · ρ; E Set of edges, E else w (e) Weight of edge e E ← E ∪ {(liu , i)}; Su Ordered list of interactions by user u w ((liu , i)) ← 1; liu Last item interacted by user u end else I ← I ∪ {i}; an edge from item 0 to item 1 exists, its weight must be updated, as V ← I ∪ {i}; denoted in Figure 1c. E ← E ∪ {(liu , i)}; We create a weighted directed graph G = (V , E, w ), where V = end {v 1 , v 2 , ..., vn } ⊆ I denotes the set of nodes and E ⊆ V × V denotes else the set of edges. Each edge e has an associated weight w (e) ∈ U ← U ∪ {u}; R + . We define Su = {(v 1 , t 1 ), (v 2 , t 2 ), ..., (vn , tn )} as a list of items if i < I then interacted by user u ∈ U ordered according to time t. The last I ← I ∪ {i}; interacted item by u is defined as liu ∈ I , i.e., the last element of Su . V ← I ∪ {i}; The graph is updated in an incremental manner considering the end current observed interaction. end User feedback is modeled as a data stream, where each observa- Su ← Su ∪ {(i, t )}; tion is defined as < u, i, t >, indicating that user u interacted with liu ← i; item i at time t, i.e., implicit feedback. When updating the graph considering the current observation, it is desirable that the model is end able to include feedback from new incoming users and items, while Algorithm 1: Online graph update also updating older concepts. In that sense, there are four possible scenarios, as presented in Algorithm 1: 3.2 Recommendation methods (1) User and item are unknown by the system (u < U and i < I ). To evaluate the information that is inserted in the graph over time, In this case, user and item are included in the system, a node we tested a few approaches to generate recommendations for users for i is added to V , (i, t ) is included in Su and liu ← i; based on items in the list of interactions S. As baseline for compar- (2) User is unknown and item is known by the system (u < U isons we use the in-degree centrality, that can be seen as a popularity and i ∈ I ). In this case, user is included in the system, (i, t ) is measure. The in-degree centrality captures the number of prede- included in Su and liu ← i. Given that i is the first interaction |P (v ) | cessors that a node has, and is calculated as: indeдree (v) = |V |−1 , 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 where P (v) is the set of predecessors of node v. A recommendation and i < I ). In this case, item is included in the system and is generated by calculating the in-degree centrality of all items a node for i is added into V . In this scenario, u has already and then recommending the k items with the highest values. This interacted with at least one item before. Since this is the first recommendation method does not distinguish users and simply interaction by any user with i, an edge (liu , i) is included in recommends items with high centrality. We refer to this algorithm E, where w ((liu , i)) = 1. Lastly, (i, t ) is included in Su and as in-degree. liu ← i; To assess the influence of the most recent interaction on user (4) User and item are known by the system (u ∈ U and i ∈ I ). interest, two strategies based only on the last item interacted by the In this case, the current sequential interaction is liu to i. If user u, i.e., liu were evaluated. In these approaches, candidate items such interaction has happened before, i.e., (liu , i) ∈ E, then are filtered out as items that are successors to liu . The first strategy w (e) is updated according to Equation (1): considers the in-degree centrality. To generate recommendations to a user u, we calculate the in-degree centrality for all successors w ((liu , i)) = w ((liu , i)) · ρ (1) 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, where ρ ∈ (0, 1) is a parameter that controls the impact of edge_weight_liu , considers the weight of edges that connects liu the interaction in the edge weight. If this is the first time such to its successors as a measure of item relevance. Considering the interaction happens, an edge (liu , i) is included in E, where manner in which the graph is constructed, this approach values the w ((liu , i)) = 1. Lastly, (i, t ) is included in Su and liu ← i. amount of times a sequential interaction happens. Candidate items j are ordered according to the weight of the edge that connects ORSUM@ACM RecSys 2020, September 25th, 2020, Virtual Event, Brazil Murilo F. L. Schmitt and Eduardo J. Spinosa (a) Example of a graph before updates based on user in- (b) Insertion of edge from item 5 to item 0 based on a teractions. sequential interaction. (c) Weight update of edge from item 0 to item 1 based on a sequential interaction. Figure 1: An example of graph update based on a few user interactions. Considering the graph in (a) and a user u whose last interaction was with item 5, (b) presents a scenario where u interacts with item 0 by inserting the edge connecting 5 to 0. In (c), u interacts with item 1 after interacting with 0, and the weight of the edge connecting 0 to 1 is updated. liu to j, and the k items with the lowest weight are recommended. The resulting approaches, edge_weight_r and path_count_r, fil- A similar approach has been shown to be effective in addressing ter candidate items j for a user u as successors to the last r items cold-start issues in Trevisiol et al. [20]. in the ordered list of interactions Su . Considering rSu as the last To model long-term interest, recommendations to a user u are r items in Su , edge_weight_r associates for each candidate item j generated based on the entire list of interactions Su . Two approaches a value ar (j) = min(w ((v, j))), ∀v ∈ rSu , w ((v, j)) < 1 and recom- that filter candidate items as successors to nodes in Su were tested. mends the k items with the lowest ar (j). Algorithm path_count_r The first approach measures the influence of sequential item in- associates for each candidate item j a value c r (j) = (v, j ) ∈E 1, ∀v ∈ P teraction, where the relevance of candidate items are measured rSu , w ((v, j)) < 1 and recommends the k items with highest c r (j). according to the weight of edges, similar to edge_weight_liu . The The impact of parameter r is evaluated through experiments re- value a(j) that represents a candidate item j is the lowest weight ported in Section 4.4. 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 4 EXPERIMENTS a(j) are then recommended to u. We refer to this algorithm as In this section we report the experiments performed to evaluate the edge_weight_Su . The second approach, path_count_Su , consid- recommendations generated by the proposed approach, describe ers an item j to be relevant to u based on the number of short paths the evaluation methodology and discuss the obtained results. We between items in Su and j, i.e., an item j is relevant to u if j is succes- compare the results with ISGD and present an analysis based on sor to several items in Su . To recommend k items to u, for each can- the results. didate item j we associate a value c (j) that counts the amount of pre- decessors of j in Su , i.e., c (j) = (v, j ) ∈E 1, ∀v ∈ Su , w ((v, j)) < 1. P 4.1 Evaluation The k candidate items with highest c (j) are recommended. We dis- card information from edges where w (e) = 1 since they indicate In order to evaluate the proposed approach on a data stream, a that the sequential interaction occurred only once. suitable evaluation methodology is required. In that sense, we use Assuming that user preferences change over time, we have the prequential evaluation protocol proposed by Vinagre et al. [21]. adapted strategies edge_weight_Su and path_count_Su to generate For each incoming event < u, i, t >, the model is first tested and recommendations based on the r most recent user interactions. then updated based on the following steps: (1) If u is a known user, use the current model to recommend N items to u, otherwise go to step 3; Incremental Graph of Sequential Interactions with Implicit Feedback ORSUM@ACM RecSys 2020, September 25th, 2020, Virtual Event, Brazil (2) Score the recommendation list given the observed item i; For the MovieLens-1M dataset in Figure 2a, starting from r = 20, (3) Update the model with the observed event; we can see that accuracy increases for algorithm edge_weight_r as (4) Proceed to the next observation; r decreases until its peak at r = 3. For all values of r , edge_weight_r We measure accuracy through the HitRate@N metric at cutoffs obtained accuracy above 0.11%. We emphasize that r = 1 corre- of N ∈ {1, 5, 10}. HitRate@N returns 1 if item i is within the N first sponds to algorithm edge_weight_liu . For the path_count_r algo- recommended items, and 0 otherwise. rithm, 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 4.2 Datasets decrease occurs because it becomes more difficult to distinguish candidate items with less edges to them. Two datasets from the movie domain were used, as summarized For the Netflix dataset in Figure 2b, starting from r = 30, the in Table 2. The MovieLens-1M dataset1 contains around 1.000.000 accuracy for algorithm edge_weight_r slightly increases as r de- timestamped ratings in a 1 to 5 scale. The Netflix dataset2 con- creases until reaching its peak at r = 7. After r = 7 the accuracy tains around 100.000.000 timestamped ratings in a 1 to 5 scale. To remains steady until reaching r = 3 and then drops considerably. simulate continuous implicit feedback, we discarded ratings below For algorithm path_count_r , accuracy reaches its peak at r = 13 5 and sorted events chronologically, where events are defined as and then decreases as r decreases. < user , item, time >. For the Netflix dataset, we dropped users and Overall, edge_weight_r is relatively stable to r , obtaining similar items with less than 10 interactions, and then selected ratings from accuracy for different values of r , while path_count_r is less stable, 10.000 randomly selected users. given that it needs more feedback to distinguish candidate items. We note that the recommendation time is associated with r , since Table 2: Dataset description. the algorithms iterate the successors to the last r nodes in Su . Thus, recommendation time can be reduced by lowering r . In that sense, Dataset Events Users Items Sparsity considering that lower values of r can obtain reasonable accuracy while generating faster recommendations, it is interesting to con- MovieLens-1M 226.310 6.014 3.232 98.84% sider the most recent interactions when modeling user behavior. Netflix 666.178 10.000 5.309 98.75% 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. 4.3 Methodology Table 3 presents overall results for all algorithms. Accuracy is We compare the accuracy of the recommendation methods de- measured through HitRate@N with N ∈ {1, 5, 10} and time is mea- scribed in Section 3.2 with ISGD [23]. The initial models were built sure through average update and recommendation times, with the on the first 20% of each dataset, while the remaining 80% were used best results highlighted in bold. for incremental evaluation and learning, simulating a data stream. Observing the results presented in Table 3, we can see that For ISGD, recommendations are generated by estimating the rating edge_weight_r has better accuracy compared to all other meth- of all candidate items, sorting such estimations and selecting N ods for both datasets, also being the second fastest method. ISGD items with the highest values. is outperformed in accuracy by all graph-based methods, and the Besides HitRate@N to evaluate accuracy, we also measure the two in-degree methods obtained the worst accuracy among the average time to update the model and to generate recommendations. graph-based methods. As stated in Section 3.1, edge weights are updated based on Equation Although algorithms edge_weight_Su and path_count_Su ob- 1, that updates the weight of an edge based on parameter ρ. In the tained superior results to the baselines, they have a high recom- subsequent experiments, we set ρ = 0.9. Applying the same value mendation time, since recommendation time is proportional to the of ρ for every update does not distinguishing the importance of an size of Su , which can make these algorithms impractical in some interaction and simply decreases the weight based on the number scenarios. However, time is substantially decreased with improved of sequential interactions. All experiments were implemented in accuracy with its counterparts that only consider the most r recent Python 2.7, with the NetworkX library [7] for graph manipulation, interactions, i.e., edge_weight_r and path_count_r . and executed on an Intel Core i7-4770 of 3.4 GHz with 16 GB RAM Comparing methods in-degree_liu and edge_weight_liu , we can running Ubuntu 16.04. see that edge_weight_liu outperforms in-degree_liu both in accu- racy and recommendation time, with edge_weight_liu presenting 4.4 Results competitive results for MovieLens-1M, also being the fastest algo- rithm overall. As discussed in Section 3.2, algorithms edge_weight_r and path_count_r For both datasets, the three strategies based on edge_weight generate recommendations to a user u based on the r most recent are among the four best algorithms, together with path_count_r . interactions in Su . To that extent, we conducted experiments to eval- These results suggest the potential of including information from uate the impact of r in the accuracy of both algorithms with metric sequential interactions into the recommendations. HitRate@10. The results of these experiments for both datasets are In terms of update time, both ISGD and graph-based methods presented in Figure 2. achieve competitive results, with graph-update being faster since 1 https://grouplens.org/datasets/movielens/1m/ the update consists in inserting a new edge or updating an edge 2 https://netflixprize.com/ ORSUM@ACM RecSys 2020, September 25th, 2020, Virtual Event, Brazil Murilo F. L. Schmitt and Eduardo J. Spinosa (a) MovieLens-1M (b) Netflix Figure 2: Impact of parameter r in the accuracy of algorithms edge_weight_r and path_count_r . Table 3: Results for all algorithms. Accuracy is measure by HitRate@N with N ∈ {1, 5, 10}, and time is reported by average update and recommendation times in milliseconds, with the best results highlighted in bold. HitRate@N Time (ms) Dataset Algorithm 1 5 10 Update Rec. ISGD 0.007 0.030 0.055 0.06 3.43 in-degree 0.012 0.046 0.080 0.01 1.87 in-degree_liu 0.012 0.051 0.093 0.01 1.24 edge_weight_liu 0.032 0.093 0.134 0.01 0.10 MovieLens-1M edge_weight_Su 0.017 0.064 0.105 0.01 5.00 path_count_Su 0.014 0.058 0.102 0.01 4.77 edge_weight_r 0.033 0.101 0.154 0.01 0.23 path_count_r 0.021 0.081 0.135 0.01 0.32 ISGD 0.002 0.011 0.021 0.06 5.68 in-degree 0.007 0.026 0.048 0.02 4.21 in-degree_liu 0.007 0.027 0.047 0.02 3.13 edge_weight_liu 0.017 0.043 0.061 0.02 0.20 Netflix edge_weight_Su 0.018 0.052 0.078 0.02 24.96 path_count_Su 0.009 0.035 0.061 0.02 23.97 edge_weight_r 0.021 0.059 0.089 0.02 1.28 path_count_r 0.010 0.042 0.072 0.02 2.13 weight based on the current interaction. Considering recommenda- most of the time for both datasets. For the MovieLens-1M, all algo- tion time, all algorithms but those that generate recommendations rithms present similar behavior, with similar peaks and a decrease based on Su present acceptable time, since recommendation time at the end. For both datasets, graph-based methods outperforms is proportional to the number of items. We note that ISGD is more ISGD over time. efficient 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|). 5 CONCLUSION AND FUTURE WORK In Figure 3 we present the accuracy of all algorithms over time In this work, we proposed an incremental graph of sequential user with a moving average of the HitRate@10 metric for both datasets interactions using implicit feedback, with the assumption that user with a window of size n = 5000 to further evaluate the learning behavior can be inferred from such sequence of interactions through behavior of all algorithms through time. The evolution reinforces time. We evaluated the model by recommending items with differ- that edge_weight_r is superior than other algorithms throughout ent strategies on two movie domain datasets and compared results with an incremental matrix factorization algorithm, ISGD, using Incremental Graph of Sequential Interactions with Implicit Feedback ORSUM@ACM RecSys 2020, September 25th, 2020, Virtual Event, Brazil (a) MovieLens-1M (b) Netflix Figure 3: Evolution of HitRate@10 as events arrive for both datasets with window size n = 5000. prequential evaluation. In terms of accuracy, the graph-based meth- [5] Yi Ding and Xue Li. 2005. Time weight collaborative filtering. In Proceedings of ods outperformed ISGD, generally with better recommendation the 14th ACM international conference on Information and knowledge management. 485–492. time. The best results were achieved by considering the weight of [6] Yi Ding, Xue Li, and Maria E Orlowska. 2006. Recency-based collaborative the edges that connect the r most recent user interactions with the filtering. In Proceedings of the 17th Australasian Database Conference-Volume 49. 99–107. candidate items. [7] Aric A. Hagberg, Daniel A. Schult, and Pieter J. Swart. 2008. Exploring Network A limitation of the proposed approach is that it requires suffi- Structure, Dynamics, and Function using NetworkX. In Proceedings of the 7th cient data from several users in order to distinguish items based Python in Science Conference, Gaël Varoquaux, Travis Vaught, and Jarrod Millman (Eds.). Pasadena, CA USA, 11 – 15. on the sequential interactions. In future work we aim to explore [8] Yehuda Koren. 2009. Collaborative filtering with temporal dynamics. In Proceed- ways to overcome this limitation. Another aspect is how to update ings of the 15th ACM SIGKDD international conference on Knowledge discovery the edges according to user sessions. In that sense, future work and data mining. 447–456. [9] Yehuda Koren, Robert Bell, and Chris Volinsky. 2009. Matrix factorization tech- also include evaluation of dynamic values for ρ, for instance, based niques for recommender systems. Computer 42, 8 (2009), 30–37. on the time elapsed between the interactions of u with liu and [10] Nathan N Liu, Min Zhao, Evan Xiang, and Qiang Yang. 2010. Online evolu- tionary collaborative filtering. In Proceedings of the fourth ACM conference on i, considering the similarity between liu and i and based on the Recommender systems. 95–102. number of interactions made by u. We also intend to include loss of [11] Yuting Liu, Bin Gao, Tie-Yan Liu, Ying Zhang, Zhiming Ma, Shuyuan He, and edge relevancy through time, explore different ways of generating Hang Li. 2008. BrowseRank: letting web users vote for page importance. In Proceedings of the 31st annual international ACM SIGIR conference on Research recommendations based on the graph, such as including informa- and development in information retrieval. 451–458. tion from both edge_weight and path_count into recommendations [12] Yiqun Liu, Min Zhang, Shaoping Ma, and Liyun Ru. 2009. User Browsing Graph: and make comparisons with other incremental algorithms, such as Structure, Evolution and Application.. In WSDM (Late Breaking-Results). [13] Pawel Matuszyk, João Vinagre, Myra Spiliopoulou, Alípio Mário Jorge, and João item-based K-nearest neighbors [14], RAISGD [24] and CORAISGD Gama. 2015. Forgetting methods for incremental matrix factorization in recom- [1]. mender systems. In Proceedings of the 30th Annual ACM Symposium on Applied Computing. 947–953. [14] Catarina Miranda and Alípio Mário Jorge. 2009. Item-based and user-based incre- ACKNOWLEDGMENTS mental collaborative filtering for web recommendations. In Portuguese Conference on Artificial Intelligence. Springer, 673–684. The authors would like to thank CAPES for the financial support. [15] Olfa Nasraoui, Jeff Cerwinske, Carlos Rojas, and Fabio Gonzalez. 2007. Per- formance of recommendation systems in dynamic streaming environments. In Proceedings of the 2007 SIAM International Conference on Data Mining. SIAM, REFERENCES 569–574. [16] Rong Pan, Yunhong Zhou, Bin Cao, Nathan N Liu, Rajan Lukose, Martin Scholz, [1] Susan C Anyosa, João Vinagre, and Alípio M Jorge. 2018. Incremental matrix and Qiang Yang. 2008. One-class collaborative filtering. In 2008 Eighth IEEE co-factorization for recommender systems with implicit feedback. In Companion International Conference on Data Mining. IEEE, 502–511. Proceedings of the The Web Conference 2018. 1413–1418. [17] Massimo Quadrana, Paolo Cremonesi, and Dietmar Jannach. 2018. Sequence- [2] Shumeet Baluja, Rohan Seth, Dharshi Sivakumar, Yushi Jing, Jay Yagnik, Shankar aware recommender systems. ACM Computing Surveys (CSUR) 51, 4 (2018), Kumar, Deepak Ravichandran, and Mohamed Aly. 2008. Video suggestion and dis- 1–36. covery for youtube: taking random walks through the view graph. In Proceedings [18] Miguel Sozinho Ramalho, Joao Vinagre, Alípio Mário Jorge, and Rafaela Bastos. of the 17th international conference on World Wide Web. 895–904. 2019. Incremental multi-dimensional recommender systems: co-factorization [3] Huanhuan Cao, Enhong Chen, Jie Yang, and Hui Xiong. 2009. Enhancing recom- vs tensors. In 2nd Workshop on Online Recommender Systems and User Modeling. mender systems under volatile userinterest drifts. In Proceedings of the 18th ACM 21–35. conference on Information and knowledge management. 1257–1266. [19] Yue Shi, Martha Larson, and Alan Hanjalic. 2014. Collaborative filtering beyond [4] Abhinandan S Das, Mayur Datar, Ashutosh Garg, and Shyam Rajaram. 2007. the user-item matrix: A survey of the state of the art and future challenges. ACM Google news personalization: scalable online collaborative filtering. In Proceed- Computing Surveys (CSUR) 47, 1 (2014), 3. ings of the 16th international conference on World Wide Web. 271–280. ORSUM@ACM RecSys 2020, September 25th, 2020, Virtual Event, Brazil Murilo F. L. Schmitt and Eduardo J. Spinosa [20] Michele Trevisiol, Luca Maria Aiello, Rossano Schifanella, and Alejandro Jaimes. [24] João Vinagre, Alípio Mário Jorge, and João Gama. 2015. Collaborative filtering 2014. Cold-start news recommendation with domain-dependent browse graph. with recency-based negative feedback. In Proceedings of the 30th Annual ACM In Proceedings of the 8th ACM Conference on Recommender systems. 81–88. Symposium on Applied Computing. 963–965. [21] João Vinagre, Alípio Jorge, and João Gama. 2014. Evaluation of recommender [25] João Vinagre, Alípio Mário Jorge, and João Gama. 2015. An overview on the systems in streaming environments. In Proceedings of the Workshop on Recom- exploitation of time in collaborative filtering. Wiley interdisciplinary reviews: mender Systems Evaluation: Dimensions and Design in conjunction with the 8th Data mining and knowledge discovery 5, 5 (2015), 195–215. ACM Conference on Recommender Systems (RecSys 2014). [26] Liang Xiang, Quan Yuan, Shiwan Zhao, Li Chen, Xiatian Zhang, Qing Yang, and [22] João Vinagre and Alípio Mário Jorge. 2012. Forgetting mechanisms for scalable Jimeng Sun. 2010. Temporal recommendation on graphs via long-and short-term collaborative filtering. Journal of the Brazilian Computer Society 18, 4 (2012), preference fusion. In Proceedings of the 16th ACM SIGKDD international conference 271–282. on Knowledge discovery and data mining. 723–732. [23] João Vinagre, Alípio Mário Jorge, and João Gama. 2014. Fast incremental matrix [27] Jia-Dong Zhang, Chi-Yin Chow, and Yanhua Li. 2014. Lore: Exploiting sequential factorization for recommendation with positive-only feedback. In International influence for location recommendations. In Proceedings of the 22nd ACM SIGSPA- Conference on User Modeling, Adaptation, and Personalization. Springer, 459–470. TIAL International Conference on Advances in Geographic Information Systems. 103–112.