They don't have a brilliantly simple method; just graph-specific heuristics. The example they gave in the paper was that, if they've got a graph corresponding t

They don't have a brilliantly simple method; just graph-specific heuristics. The example they gave in the paper was that, if they've got a graph corresponding to web pages and the links between them, to group together vertices representing pages from the same domain. So, yeah, they're going to have a lot of cross-node messaging.