A Distributed Platform to Ease the Development of Recommendation Algorithms on Large-Scale Graphs

1 Introduction

The creation of novel and more effective recommendation algorithms for social networks is currently facing major challenges regarding data processing. This can be explained by two facts. Firstly, since social networks grown in popularity, the volume of data originating from these platforms has grown in size as well. Secondly, the development of most experimental recommendation algorithms for social networks are implemented as single-machine, single-threaded applications [Durand et al., 2013; Wang et al., 2014; Guo and Lu, 2007].

In the field of distributed graph processing frameworks, there are many execution models and architectures [Malewicz et al., 2010; Low et al., 2012] but are mainly in-memory which, for small clusters imposes a hard limit on scalability. On the other hand, graph databases 12 provide persistence, but usually do not provide execution facilities neither custom task distribution.

1 Titan, http://thinkaurelius.github.io/titan/

2 Neo4J, http://neo4j.com/

Therefore, in our view, there is a pressing need for a new support that takes advantage of distributed data stores and provides abstractions to (optionally) allow users to exploit low-level tuning execution mechanisms, while additionally offering a simple graph traversal API tailored to recommendation algorithms. The thesis proposes Graphly, a distributed graph database and processing platform that simplifies the creation of distributed graph algorithms by providing a simple query API for graphs, while supporting fine tuning of task execution. This fine tuning is provided through mapping strategies, a non-invasive way of distributing queries through a computer cluster.

GraphRec extends Graphly's query API by providing wellknow recommendation algorithms for graphs, e.g., HITS [Najork, 2007], SALSA [Najork, 2007], WhoToFollow [Gupta et al., 2013], among others such as [Armentano et al., 2012]. Together, Graphly and GraphRec provide a platform that can also be of great use for the recommendation systems research community to develop and evaluate novel recommendation algorithms on real-sized graphs. Furthermore, the mapping strategies provided by Graphly allow to adjust these algorithms to the cluster being used.

The remainder of this document is organized as follows. Section 2 introduces Graphly and GraphRec. Section 3 illustrates how mapping strategies affect the execution of recommendation algorithms. Finally, Section 4 elaborates some conclusions and future work.

2 Graphly and GraphRec

Graphly is a graph database and processing platform targeted to small, heterogeneous cluster setups. Besides providing tools to store and query a persistent graph database, Graphly implements job mapping strategies that allow tuning the algorithm's execution to the current cluster setup (e.g. round robin, location aware).

GraphRec is an extension of Graphly's query API that includes several well-known algorithms as built-in primitives from which novel algorithms can be built upon. A usage example of the SALSA algorithm [Najork, 2007] in GraphRec would be:

Where the as operation casts the current query to a GraphRec query, and then, the salsa operation is executed during 100

iterations. The authority and hub values are stored on each vertex under the a and h properties respectively. The salsa operation updates the authority and hub scores according to SALSA algorithm:

• 2: auth(v) = � auth(w) out (u)in(w)
• 3: hub(v) = � hub(w) in(v)out (w)
• 4: endfor

1: forall v inVdiv u→v � u→w v→u � w→u

3 Experiments

As part of a more extensive experimental evaluation, we tested the SALSA implementation in GraphRec on an 8-node cluster with different job mapping strategies and 3 groups of users: a 5-user group, a 25-user group and a 50-user group. The first strategy is a Location-Aware strategy that maps vertices to where they are located. The second and third strategies uses the maximum and the currently available RAM memory measures respectively to map vertices. Finally, the Round Robin metric simply divides vertices equally among cluster nodes. Figure 1 shows the results in terms of recommendation time, network usage and memory usage. From the results, we argue that strategies can be helpful on different scenarios. For example, if the amount of RAM memory is not the same for each node, a memory-based strategy might scale better for huge datasets but will perform poorly in terms of network usage. Moreover, if the cluster is shared among different users, a dynamic memory strategy might work better than a static strategy. On the other hand, if the cluster uses an slow network, e.g. Wi-Fi, a location-aware strategy provides better performance but does not take into account the capabilities of each node.

4 Conclusions

The main contribution of this work is a support platform for creating new graph-based recommendation algorithms that hides distributed concerns while still allowing fine tuning of the underlying distributed execution.As future work, the inclusion of other non-invasive strategies like job-stealing and caching strategies are planned. Another natural extension of this work is the creation of hybrid strategies, e.g. a LocationAware strategy that takes into account memory or CPU characteristics or both to split jobs. Currently the division of work is implemented through a fork-join algorithm, but the inclusion of alternative processing models for graphs, e.g. Pregel [Malewicz et al., 2010], is being implemented. Providing implementations of commonly used algorithms in both models (Fork-Join and Pregel) will help to compare the impact of model selection on the algorithm and how mapping strategies affect response time and cluster usage on different execution models.