I didn't get a chance to look at the paper, but I wanted to share my experience working at two social network companies and publishing an academic paper on the topic of machine learning on a social network graph. Many people think it's necessary to use graph based machine learning (or graph databases).
In practice I found it almost always better to just use a "flat" representation and do regular machine learning (or database schemas). I would love to hear if others disagree.