Sadly.... I'm noticing that folks that have done one MapReduce job are convinced it is the way to go for all jobs. It is scary just how fad based development can be.

To be fair, abstracting that fact away, the rest of the post is still an interesting thought experiment.

A better approach at the scale being discussed in the article would be to...?

What does 'scale' mean :) ? Solving graph problems are best done in-memory with a big machine (RAM!), otherwise you are an order of magnitude slower (at least) if you try to distribute. But if you really have no choice I would have a look if some of the graph databases has a good distributed model. My gut feeling tells me that even a bad approach there is faster than spark ...

I guess Titan DB would fit the bill: http://thinkaurelius.github.io/titan/

Facebook has blogged about scaling Apache Giraph to insane number of Vertices/Edges.