WIXLIB

duced to let applications assign additional informationto nodes and edges. Such an item of information represented as attribute value is for instance the rating valueof an edge which represents user rating value over a specific item.3.2 MovieLens. As the method introduced in Section 4.1 is capable to incorporate heterogeneous information source types, we decided to use the MovieLens [8] 1M dataset, which we have found relativelyrich in user and item attributes. MovieLens 1M is published by Grouplens1 . The rating data also contain atime stamp, which is important for the evaluation ofour methods. The dataset contains 1 000 209 anonymous ratings of 3 883 movies made by 6 040 MovieLensusers who joined MovieLens in 2 000.MovieLens 1M contains three data files in a proprietary tabular format. The data files hold user, item andrating data. The user data file contains user attributesabout each user, as user id, gender, age, occupation andzip-code. The item data file contains item attributesabout each movie, as movie id, title and list of genres.The ratings data file contains the user ratings on items,as user id, movie id, rating and time stamp.Gender to represent gender, Occupation to representoccupation and ZipCodeRegion to represent U.S. region. The type ZipCodeRegion is a calculated attributevalue. The original dataset contains U.S. zip codes. Thefirst digit of the U.S. zip code system represents postalregion, which information has been encoded into the attribute nodes. Item attributes are represented similarly.Nodes of type Genre represent item genre, nodes of typeYearOfPublishing represent different years when particular movies were published.The following edge types have been introducedto represent relations between the entities in theknowledge base PersonAgeCategory, ItemGenre, ItemYearOfPublishing and ItemRating.Edge types starting with Person represent relationsbetween users and user attribute nodes representinguser attribute values. For instance edges of typePersonAgeCategory represent the information revealing that a person belongs to an age category,PersonGender represents the gender of a person,PersonOccupation represents the occupation of a person, PersonZipCodeRegion represents the place in U.S.region where a person lives. Edge types starting withItem except ItemRating represent relations betweenitems and nodes representing item attribute values.Edges of type ItemGenre represent the informationshowing which specific genre a movie belongs to,ItemYearOfPublishing represents that a movie waspublished in a specific year.Edges of type ItemRating existing between usersand items represent that a user rated an item with aspecific value of rating. In this case the rating value wasassigned to the edge as an edge attribute. The edges ofthis type have a special, additional attribute, the ratingvalue. During the import process the rating values aretransformed to the [0.2, 1] real interval from the [1, 5]integer interval by dividing the rating values by 5.Figure 1: A detailed view of the MovieLens database 4 Recommendation.represented in a directed graphCold start is a common and frequently mentioned problem of recommender systems. Collaborative filtering hasThe MovieLens 1M data is represented with the no reliable information to derive recommendations fromknowledge base introduced in Section 3.1. As il- for a newcoming user because the user did not expresslustrated on Figure 1, the following node types interest in a sufficient number of items. Content basedare introduced to represent entities Person, Item, methods also need information to be able to model theAgeCategory, Gender, Occupation, ZipCodeRegion, taste of the user. Based on this information, relevantGenre and YearOfPublishing. Nodes of type Person items can be recommended. Knowledge based methodsrepresent users, nodes of type Item represent movies. are a possible solution for this problem but their drawUser attribute values are represented with nodes. Node back is that these methods in most cases also requiretype AgeCategory is used to represent age category, user interaction. Our objective is to start recommending relevant items as early as possible. To accomplishthis, the highest possible amount of information is rep1 http://www.grouplens.org/

resented and a calculation method is defined, which hasthe ability to derive useful information from heterogeneous data. This strategy ensures high coverage. Wedefine the coverage as the percentage of the cases therecommendation method was able to provide a ratingestimation until the corresponding step.We introduce a spreading activation [15] based technique, which – because of the similar technique – wecall recommendation spreading. Spreading activation isa well-known method in the field of semantic networks,neural networks and associative networks [1]. By utilizing spreading activation, our calculation method is ableto combine different paths between the source node (i.e.the person we are generating recommendations for) andthe recommended nodes (i.e. the items we are recommending). The method is sensitive to the length of eachpath, in order to downgrade the influence of nodes topographically far from the node in question, i.e. the nodethe recommendations are generated for.relax and activation relax values are the parameters ofour spreading method.Another feature of our spreading methods is thethreshold constant. If the activation of a node fallsbelow the threshold constant, its activation will beset to zero [2]. The threshold is introduced to avoidunnecessary computation of activations close to zero.This parameter is called activation threshold.There are various options to define the terminationcriteria for recommendation spreading. A relativelysimple solution is the one based on iteration step, i.e. tostop the iteration after a certain iteration step count isreached. A delta based termination criterion could alsobe used meaning to run the iteration until there is nosignificant change in the activations [17]. We decided touse a step limit, because we think that this terminationcriterion fits better to our intended purpose. In arecommendation scenario a method is necessary, whichdelivers nodes topographically close to the source nodes.It is also important to mention that calculating a delta4.1 Spreading. Recommendation spreading is an it- based termination criterion is resource intensive, whileerative method. In the initial step, the activation of step limit is cheap to compute. A limit on iterationthe source nodes, is set to a constant value, in most steps has been introduced, which parameter is calledcases to 1. The source nodes are the nodes the rec- step limit.ommendations are generated for. In the simplest casethe set of source nodes consists of one node, the node 4.2 Network Based Comparison. In the followingrepresenting a person to generate the recommendations we are comparing collaborative filtering with our apfor.2 In each step for each node a part of the activa- proach.Figure 2 illustrates a simtion is distributed to the neighbouring nodes, anotherpart is kept at the activating node. The former parame- plified collaborative filteringU1ter, which determines the amount of distributed activa- scenario. Nodes labeled withR2R1R3tion is called spreading relax. The latter parameter, “U” represent users, nodes lawhich determines the amount of activation kept at the beled with “I” indicate items.I1I2I3node is named activation relax. Both parameters Edges labeled with “R” repreR5R4R6are real numbers and are global settings for the whole sent ratings. In this samplenetwork. The outgoing activation is divided along the scenario we are generating ratU2U3outgoing edges based on the weight of the edges. All ing estimation for user “U1”.these spreading values are summed up at each receiving User “U1” rated two items,R7R8node. This way the sum of the activations received by “I1” and “I2” in common withI4the destination nodes is the same amount as the activa- user “U2”. User “U1” ratedtions distributed from the source node. If it’s important item “I3” in common with userto keep the sum of the activations at a constant level in “U3”. The rating estimation Figure 2: Collaborathe network, the sum of activation relax and spreading for item “I4” is calculated as tive Filteringrelax must be equal to one.3 The concrete spreading a weighted sum of rating “R7”and “R8”. The weights for rating “R7” are influenced2 It is possible to start the recommendation spreading fromby dashed edges, namely “R1”, “R2”, “R4” and “R5”,multiple nodes. For example if a user is browsing an item, then the weights for rating “R8” are influenced by dottedthe spreading can be started from the two nodes representing the edges, “R3” and “R6”.user and the item. This way the final recommendation result canFigure 3 illustrates our approach, where we showbe influenced by both the user and the browsed item.3 Setting the weights to appropriate values won’t preventhow heterogeneous information can be incorporated tospreading methods to lose activation. In a case of a node withno outgoing edges the node cannot redistribute its activation toany neighbouring node, thus its activation will be lost. A possiblesolution to overcome this problem is to bind all nodes to the sourcenode with a backlink edge. This method has other advantages asdiscussed by Zielger et al. [17], called avoidance of dead ends.

produce rating estimation. Nodes labeled with “U”represent users, nodes labeled with “I” indicate items,the node labeled with “A” represents age category.Age category is an example how to represent userattributes. Item attributes can be represented similarly.Edges labeled with “R” represent ratings, edges labeledwith “A” mean user belongs to an age category, edgelabeled with “S” means item similarity. User “U1”rated item “I1” and “I2” in common with user “U2”.The dashed edges (R1, R2, R4, R5) represent theinfluence of user similarity on the weight of rating “R7”on final estimation. User “U1” belongs to the sameage group “A” with user “U3”. The solid edges (A1,A2) represent the same age group relation and theirinfluence to the weight of rating “R8”. It also illustrateshow user and item attributes can influence the finalrecommendation result. The dotted path (R3,S1,R6)starts from user “U1” with a rating edge, continues withan edge representing item similarity and ends with arating edge. The semantics behind this path could bedescribed as user “U1” and user “U4” rated a similaritem. Activation received through the dotted pathspecifies the weight of rating “R9”.U14.3 Rating Weights. TheR1R3introduced recommendationR2A1method can also be treatedI1I3as the generalization of collaborative filtering in the caseS1I2Aof representation of heteroR4I4geneous information. WhileA2R5calculating recommendationR6spreading,the activationflowed through each ratingU2U3U4edge is accumulated.WeR8R7R9denote this value with a,which variable is indexed withI5the edge. To calculate theweighted sum of estimatedrating, these accumulated val- Figure 3: Recommenues are used as the weights of dation Spreadingrating values belonging to thespecific edge. Recommendation spreading calculatesrating estimations with the following formulaPe EItemRating i e v e i6 v (rv,i r v )aePr̂u,i r̄u e EItemRating i e v e i6 v ae, where r̂u,i is the estimated rating value for user u onitem i, r̄u and r v denote the average of the already issuedratings by user u and v respectively, rv,i is the knownrating value of user v on item i, ae is the aggregatedactivation flowed through via edge e, EItemRating {e E tE (e) ItemRating} is the set of edges of typeItemRating.Rating edges are drawn between users and items.This means that in the sample case shown in Figure 3user similarity between U1 and U2 can be defined as theactivation arrived from U1 to U2 through the network. 44.4 Flow direction. The knowledge base representsthe information with a weighted directed graph. Figure 3 shows a sample spreading scenario. If “Item 5”would be recommended to “User 1”, a directed pathbetween these nodes couldn’t be found. With a recommendation spreading method flowing only in the direction of the edges coverage would be lost. Spreading onan undirected graph also means that if a node receivedan activation in step i, in step i 1 it will spread a partof its activation back to the node it received activationfrom through the previously receiving edge.5Evaluation.5.1 Evaluation Method. We call our evaluationmethod time series evaluation, which is an iterativemethod based on time stamped data. The evaluationiterates through time stamped data of sample items inascending order, while repeating the following operations1. take the next rating sample from the database,2. ask for rating estimation from the recommenderengine,3. calculate the rating error and record it to theevaluation log,4. add the true rating value to the knowledge base asan edge of type ItemRating.Before starting the evaluation, the knowledge base isfilled with all the information found in the MovieLens1M dataset except the ItemRating edges. We decidedto use this method to simulate real life scenarios, witha focus on the ability of comparing methods in thebeginning, cold start steps, when there is only a lowamount of rating information available in the knowledgebase. The knowledge base is filled with additionalinformation (ItemRating edges) during the evaluationprocess.5.2 Numerical Experiment. We were interested incomparing different step limit settings to collaborative filtering. Table 1 summarizes the methods whichwere evaluated in the experiment. For easier reference4 The statement holds, because U2 has only one outgoing ratingedge. The activation leaves from U2 only via R7.

NameMethodCFS3S4S5S6S7S8Collaborative FilteringRecommendation SpreadingRecommendation SpreadingRecommendation SpreadingRecommendation SpreadingRecommendation SpreadingRecommendation SpreadingMethodparameters–Step limit: 3Step limit: 4Step limit: 5Step limit: 6Step limit: 7Step limit: 8Table 1: Engines and configurationslater we assigned a name to these methods which canbe found in the first column of the table. We evaluatedthe recommendation spreading method on the MovieLens 1M dataset represented as described in Section 3.2.Time series evaluation method was conducted as described in Section 5.1. As we were interested in howthe methods perform in the information sparse environment, we ran the experiment on the first 10 002 ratingvalues of the sample dataset. The benchmark method inthe experiments is collaborative filtering with a Pearsoncorrelation based similarity calculation method. Theactivation relax parameter of the spreading methodhas been set to 0.5, the spreading relax has been alsoset to 0.5. The activation threshold of spreadingmethods has been set to 0, meaning no thresholding,in order to see the pure, unoptimized performance ofspreading methods.Figure 4: Comparing the MAE of recommendationspreading and collaborative filtering5.4 Coverage. Figure 5 compares the coverage of S3and CF methods. The horizontal axis of the figurerepresents evaluation steps, the vertical axis representsthe coverage at the corresponding step. Figure 5shows that recommendation spreading provides highercoverage than collaborative filtering. The difference oncoverage is also high in the beginning steps, when theknowledge graph is more sparse on true rating values. Itmeans that recommendation spreading performs betterin the cold start case than collaborative filtering. Weexplain this by treating the coverage problem as finding5.3 Rating Estimation Error. Figure 4 comparesa path between two nodes. While collaborative filteringtwo methods, namely S3 and CF. We decided to comcan operate on a restricted set of edges (only onpare S3 with CF as S3 is the most restricted spreadingthe ItemRating edges), recommendation spreading canmethod. Spreading methods running for higher steputilize any type of edge. This is the reason the spreadinglimits have a higher chance to deliver recommendationbased method can reach the item node in a higherestimations of better quality. The horizontal axis of thenumber of cases.figure represents evaluation steps, the vertical axis represents the MAE until the corresponding step. SeeingEngine Coverage MAEthe step interval below 1 000, the figure shows that thenamerecommendation spreading method has a higher coverCF6 1180,170 4age in the cold start case. Furthermore, in this regionS37 8970,171 0the quality of the estimated values of S3 are higher thanS47 8970,171 0the estimated values of the CF method, which statementS57 9100,171 1holds until approximately the 3 000th step. To sumS67 9100,170 8marize the information on Figure 4, recommendationS77 9100,170 7spreading converges faster and it has a higher coverageS87 9100,170 5in the cold start case. Coverage is defined as the percentage of cases the recommendation method was ableto provide a rating estimation at until the corresponding Table 2: Coverage and MAE of different engines at theevaluation step.last evaluation step

Figure 5: Comparing the coverage of recommendationspreading and collaborative filteringTable 2 contains the coverage and MAE values ofthe engines in the experiment at the last evaluationstep. The MAE values are very similar, differing only atthe third digit. It means that recommender spreadingis a method which successfully combines heterogeneousinformation sources with the same estimation error ascollaborative filtering on the MovieLens 1M dataset.Regarding coverage, Table 2 provides two insights. Asthe spreading method has more options to reach thedestination node from the source node, this method isable to estimate ratings in more cases. The secondconsequence is that a higher spreading step limitvalue does not necessarily lead to a significantly highercoverage. It means that this parameter is sensitive tothe underlying data or application domain and shouldbe fine tuned for each dataset or application.6Conclusion.The results show that a rating estimation method wasdeveloped which has very similar prediction error as collaborative filtering has. As by its nature recommendation spreading works from a higher number of ratingestimations, the method has a higher coverage than thebenchmark method has. Comparing recommendationspreading methods configured to different spread steplimits shows that while the coverage increases withthe step limit, the precision of rating estimation doesnot increase or decrease. It means if an application ofthe method needs an estimation on a specific item, theiteration can be stopped as spreading reached the noderepresenting the item, because further spreading doesnot increase the precision.Next to its higher coverage, an important propertyof recommendation spreading is its faster convergence.The results can be explained by a higher number ofrating values reached to aggregate. As the results alsoshow that the higher the number of aggregated ratingvalues leads to the lower error of rating estimation,the faster convergence can be the consequence of theaggregation of a higher number of rating values also inthe beginning, cold start case. It was also shown that inthe long term, the introduced method has very similarprecision as collaborative filtering has. It means thata method was developed which is able to combine ahigher number of ratings while not increasing the errorof rating estimation.We would like to extend the knowledge base orthe recommendation engines with an additional information, the information type weight function. Typeweights express the strength of a relation type. Thisinformation can be used by the calculation method. Introducing type weights, our intention is to let the modelor the calculation method store the importance of different relation types. For example the weight of therelation type representing friendship can be set to 0.8,the weight of the relation type representing country ofproduction can be set to 0.4. The values express theimportance of the various information types. The calculation methods can use this information when calculating recommendations, for instance by multiplying therelation type weight with the relation weight. The potential of introducing type weights can be found in thelearning capability of the recommendation methods. Ifa calc

recommendation result by restricting the amount of infor-mation the recommendation method can operate on. In this paper we introduce an adaptive rating estimation method, which is capable to incorporate heterogeneous information sources and improves the recommendation quality. To represent heterogeneous information, a graph based