Overkill Analytics

I’d like to start this blog by discussing my first Kaggle data science competition – specifically, the “GigaOM WordPress Challenge”.   This was a competition to design a recommendation engine for WordPress blog users; i.e. predict which blog posts a WordPress user would ‘like’ based on prior user activity and blog content.   This  post will focus on how my engine used the WordPress social graph to find candidate blogs that were not in the user’s direct ‘like history’ but were central in their ‘like network.’

My Approach

My general approach – consistent with my overkill analytics philosophy – was to abandon any notions of elegance and instead blindly throw multiple tactics at the problem.   In practical terms, this means I hastily wrote ugly Python scripts to create data features, and I used oversized RAM and CPU from an Amazon EC2 spot instance to avoid any memory or performance issues from inefficient code.   I then tossed all of the resulting features into a glm and a random forest, averaged the results, and hoped for the best.   It wasn’t subtle, but it was effective. (Full code can be found here if interested.)

The WordPress Social Graph

From my brief review of other winning entries, I believe one unique quality of my submission was its limited use of the WordPress social graph.   (Fair warning:  I may abuse the term ‘social graph,’ as it is not something I have worked with previously.)   Specifically, a user ‘liking’ a blog post creates a link (or edge) between user nodes and blog nodes, and these links construct a graph connecting users to blogs outside their current reading list:

Defining user-blog relationships by this ‘like graph’ opens up a host of available tools and metrics used for social networking and other graph-related problems.

Node Distance, a.k.a. Two Degrees of Separation

The simplest of these graph metrics is the concept of node distance within graphs.  In this case, node distance is the smallest number of likes required to traverse between a particular user node and a particular blog node.   In the diagram above, for example, User A and Blog 4 have a node distance of 3, while User C and Blog 5 have a distance of 5.

The chart below breaks down likes from the last week of the final competition training data (week 5) by the node distance between the user and the liked blog within their prior ‘like graph’ (training data weeks 1-4):

As you can see, nearly 50% of all new likes are from blogs one ‘edge’ from the user – i.e., blogs the user had already liked in the prior four weeks.    These ‘like history’ blogs are a small, easily manageable population for a recommendation engine, and there are many relevant features that can be extracted based on the user’s history with the blog.   Therefore, the like history set was the primary focus of most contest submissions (including mine).

However, expanding the search for candidates one more level – to a distance of 3 edges/likes traversed – encompasses 90% of all new likes.   A ‘distance 3’ blog wold be a blog that is not in the subject’s immediate like history but that is in the history of another user who had liked at least one blog in common with the subject.   This is admittedly a large space (see below), but I think it significant that >90% of a user’s liked blogs in a given week can be found by traversing through just one common reader in the WordPress graph.   Finding the key common readers and common blogs, therefore, is a promising avenue for finding recommendation candidates that are new to the subject user.

Node Centrality, a.k.a. Finding The Common Thread

As referenced above, the main problem with using the distance 3 blogs as recommendation candidates is that the search space is far too large – most users have tens of thousands of blogs in their distance 3 sets:

As seen from the above chart, while a significant portion of users (~20%) have a manageable distance 3 blog set (1,000 to 2,000 blogs), the vast majority have tens of thousands of blogs within that distance.   (Some post-competition inspection shows that many of these larger networks are caused by a few ‘hyper-active’ users in the distance 3 paths.  Eliminating these outliers could be a reasonable way to create a more compact distance 3 search set.)

One could just ignore the volume issues and run thousands of distance 3 blog candidates per user through the recommendation engine.  However, calculating the features and training the models for this many candidate blogs would be computationally intractable (even given my inclination for overkill).  To get a manageable search space, one needs to find a basic, easily calculable feature that identifies the most probable liked blogs in the set.

The metric I used was one designed to represent node centrality, a measure of how important a node is within a social graph.  There are many sophisticated, theoretically sound ways to measure node centrality, but implementing them would have required minutes of exhaustive wikipedia reading.   Instead, I applied a highly simplified calculation designed to measure a blog node’s three-step centrality within a specific user’s social graph:

• Step 1(a):  Calculate all three-step paths from the subject user in the graph (counting multiple likes between a user and blog and multiple possible paths);
• Step 1(b): Aggregate the paths by the end-point blog; and
• Step 1(c): Divide the aggregated paths by the total paths in step 1(a).
• Step 2: ???
• Step 3: Profit.

The metric is equivalent to the probability of reaching a blog in three steps from the subject user, assuming that at each outbound like/edge has an equal probability of being followed.   It is akin to Google’s original PageRank, except only the starting user node receives an initial ‘score’ and only three steps are allowed when traversing the graph.

I don’t know if this is correct or theoretically sound, but it worked reasonably well for me – substantially lifting the number of likes found when selecting candidates from the distance 3 graph:   

As shown above, if you examine the first 500 distance 3 blogs by this node centrality metric, you can find over 20% of all the likes in the distance 3 blog set.   If you selected 500 candidates by random sample, however, only 3% of the likes from this population would be found.   While I am certain this metric could be improved greatly by using more sophisticated centrality calculations, the algorithm above serves as a very useful first cut.

Some Very Simple Code

I’d feel remiss not putting any code in this post.   Unfortunately, there was a lot of bulky data handling code I used in this competition to get to the point where I could run the analysis above, so posting the code that produced this data would require a lot of extra files.  I’d happily send it all to anyone interested, of course, just e-mail me.

However, in the interest of providing something, below is a quick node distance algorithm in Python that I used after the fact to calculate node distances in the like graph.  This is just a basic breadth-first search implemented in Python, with the input graph represented as a dictionary with node names as keys and sets of connected node names as values:

def distance(graph, start, end):
	# return codes for cases where either the start point 
	# or end point are not in the graph at all
	if start not in graph: return -2
	if end not in graph: return -3
	# set up a marked dictionary to identify nodes already searched
	marked = dict((k, False) for k in graph)
	marked[start] = True
	# set a FIFO queue (just a python list) of (node, distance) tuples

	queue = [(start, 0)]
	# as long as the queue is full...
	while len(queue):
		node = queue.pop(0)
		# if the next candidate is a match, return the candidate's distance 
		if node[0] == end:
			return node[1]
		# otherwise, add all the nodes connected to the candidate if not already searched
		# mark them as searched (added to queue) and associate them with candidate distance + 1
		else:
			nextnodes = [nn for nn in graph.get(node[0], set()) if marked[nn] == False]
			queue.extend((nn, node[1]+1) for nn in nextnodes)
			marked.update(dict((nn, True) for nn in nextnodes))
	# if you fall through, return a code to show no connection
	return -1

Conclusion

In the end, this node centrality calculation served as a feature in my recommendation engine’s ranking and – more importantly – as a method of identifying the candidates to be fed into the engine.   I have not done the work to see how much this feature and selection method added to my score, but I know as a feature it added 2%-3% to my validation score, a larger jump than many other features.   Moreover, my brief review of the other winner’s code leads me to think this may have been a unique aspect of my entry – many of the other features I used were closely correlated elements in the other’s code.

More crucially, for actual implementation by Automattic the ‘like graph’ is a more practical avenue for a recommendation engine, and is probably what the company uses to recommend new posts.   Most of the work we did in the competition differentiated between posts from blogs the user was already reading – useful, but not a huge value-add to the WordPress user.   Finding unseen blog posts in which a user may have interest would be a more relevant and valuable tool, and finding new blogs for the user with high centrality in their social graph is a reasonable way to find them.   From my work on the competition, I believe these methods would be more promising avenues than NLP and topic-oriented methods.

The above posts covers all of my thinking in applying network concepts to the WordPress challenge problem, but I am certain  I only scratched the surface.   There are a host of other metrics that make sense to apply (such as eccentricity, closeness and betweenness).   If you work for WordPress/Automattic (and that is the only conceivable reason you made it this far), I’d be happy to discuss additional ideas, either on this blog or in person.