Hacker News Reader

Comment by jbooth | Hacker News Reader

Graph problems are really hard to scale out because any node could theoretically be connected to any other node. That means you can't just break the graph into 5 chunks because some edges will cross server boundaries.

The only way I've seen it done in Hadoop is to store a big file listing every edge as a pair and do N passes if you want to do a calculation with a distance of N. Not the most elegant approach but with enough horsepower it'll work.

View on HN

We've experimented with this, and we've found that with "social network" graphs (that is, scale-free networks whose degree distribution follows a power law) it's possible to determine "good" partitions on which to split the nodes. "Communication" (that is, algorithms that run across edges) within a partition is fast, and message-passing between partitions is minimized.

Is your algorithm general or is it based on details specific to your data?

If it's general and not secret sauce, mind posting a brief description? Appreciated

These are hard problems to solve, even approximately, and nothing we're doing is original. Like quantitative finance, a lot of the original research comes from outside the field (ie. "quasi-clique detection in protein-protein interaction networks"). For those that are interested, there's a lot of information in recent public or easily-available research papers. A weekend spent programming a good idea from a paper is well worth it.

For better or worse, we don't use any graph-specific heuristics beyond general assumptions of the graph's structure (which may or may not be correct, but that's another story...). We're dealing with a massive sparse graph whose vertex set, but not edge set, fits in memory (RAM). Embarrassingly, the edges are stored in a database in MySQL; we might be running the world's largest graph on MySQL, but I think we get better performance from MySQL than we could from any other products. Needless to say, we're not using anything relational. Like a lot of graphs (the Web, social networks, etc.), the number of edges is several orders of magnitude larger than the size of the vertex set, so we plan accordingly.

Perhaps my use of the term "partition" above is incorrect; these aren't perfect partitions (they don't exist, except in theory), but are what's known as "quasi-cliques" (the field of graph theory is rife with jargon).

We're happy with what we've come up with; contrary to most, the limits we face are mostly due to limited storage capacity rather than limited computation time or network capacity, which is essential for handling growth.

Sorry if all of this has been too general; there's not too much I can say specifically without revealing our "secret sauce". :D

Google has published a very short paper about a program, called Pregel, which expresses graph algorithms using message passing between vertices. Apparently its scaling doesn't suck:

http://www.royans.net/arch/pregel-googles-other-data-process...

They do try to group related vertices as much as possible, but if edges span computers, that's okay too. I assume that it works best when the interconnect between computers is low-latency, though.

Yeah, but that is hard. You probably need some clustering heuristic that autolocates nodes and edges on hosts near their neighbors, a way to distribute that work, and even still, the latency penalty for the cross-node lookups will be significant and require a lot of optimization.

Unless they've thought of some brilliantly simple method that I haven't, which is certainly possible.

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.

In practice though, is the degree of connectedness really ever that high? I was under the impression that many real world phenomena (from social networks to biological interaction networks) exhibit small-world phenomena and you tend to get more well-connected subgraphs that are connected by important hub nodes. So it would seem to me like applying some careful heuristics (and keeping track of important bottlenecks/hubs) would still allow you to do computations in chunks.

Would love an expert on the subject to chime in.

It's not, a lot of the time, but in order to take advantage of that you generally need some domain-specific hack. More general solutions generally assume the possibility of interconnectedness at any point, ie, you can't rule it out, which means you'll need some kind of fast internode lookup mechanism as mentioned by pjscott.

Reply on news.ycombinator.com