Dealing with large scale graphs

To a hammer everything looks like a nail but one great hammer to have in your toolbox is the graph. The ACL anthology alone lists more than 300 results for the query "graph based". Graphs based formalisms allow us to write down solutions in succinct linear algebra representation. However implementation of such solutions for large problems, or even for small datasets with blown-up graph representations can be challenging in limited resource environments. While some go for interesting approximate solutions, an alternative solution is to pool in several limited resource nodes into a map-reduce cluster and design a parallel algorithm to conquer scale with concurrency. This is easier said than done since designing some parallel algorithms requires a different perspective of the problem. This is well worth the effort as the new insights gained will reveal connections between things you already knew. For instance, in our TextGraphs 2009 paper we started out scaling up Label Propagation but eventually the connection to PageRank became obvious. To me this was a bigger learning moment than getting Label Propagation work for large graphs. [Preprint Copy]

For the actual implementation, we used Hadoop (surprise!) although bulk synchronous parallel models make more sense given the locality of the operations in most graph algorithms.