A number of applications lend themselves to graph-oriented analytics, including:
- Finding bad guys (national intelligence)
- Finding bad guys (anti-fraud)
- Data mining the social graph (e.g., for advertising optimization on social networks, or to identify influencers)
There are plenty more graph-oriented applications, of course, such as the identification of biochemical pathways. But I want to focus for now on ones like those on my list. My key points are:
- There are Big Data problems that lend themselves to graphical data models.
- So far as I can tell, the database management community isn’t doing enough to address them. (If I’m wrong about that, please tell me. I plan to arrive in Lyon for VLDB/XLDB Wednesday of next week, and of course I can always be reached by email.)
Here’s what I mean.
Applications that analyze relationship graphs are commonly grouped under the name social network analysis. As I frequently point out, category names and definitions tend to be imperfect, and that one is no exception. In particular — and the Wikipedia article on social networks and social network analysis is an excellent example of this – the term tends to be construed to cover the linkages between people or organizations, but not between, say, physical addresses, email addresses, and all the other stuff those intelligence applications actually track. I tried to introduce the term relationship analytics a while back, but it unfortunately didn’t stick.
I only ever got familiar with one company that tried to do a true graph-oriented database management system, suitable for social network analysis/relationship analytics. It was called Cogito, and had some interesting ideas about graphical data structures. Unfortunately, Cogito didn’t stick either.
As per the “Metrics” section of the Wikipedia article linked above, there are a number of well-established metrics about the relationships of pairs or groups of node to each other. The usual way to calculate these metrics is to load the graph into memory and get to work. (Indeed, such uses seem to be driving a lot of the national intelligence adoption of Hadoop.) And while I’m perfectly willing to believe that relational database management systems can do a fine job of managing generic RDF, it’s less obvious that they’re well-suited to support standard graph-analysis metric computations.
The reason, in a nutshell, is that the relational approaches usually boil down to maintaining a table with a row for every node-edge-node triple, and then doing a lot of fast self-joins to identify paths. That can work if connectivity is low and paths are sparse. But for higher degrees of connectivity, such strategies can lead – BOOM! — to serious combinatorial explosion. And that’s not good, because a lot of this analysis focuses on finding exactly the parts of the graph where the connections run thickest.
Cogito’s idea was to say “What if, for every node, you could retrieve in only a few blocks all the paths leading from it, at least up to pathlength N?” Unfortunately, Cogito’s approach to creating this effect had too little to do with optimizer development or selectively redundant data storage, and too much to do with wishful thinking; not coincidentally, Cogito is no longer around. (I haven’t kept in touch with Cogito’s successor 7 Degrees, and the reason hasn’t been lack of effort or interest on my part.)
But suppose the idea had worked. Then – unlike today – it might be realistic to do on-the-fly analytics on Very Large Graphs, just as we do operational business intelligence of a more relational or MOLAP nature. That would be cool.
How cool would it be? Well, that’s a bit hard to say. Look again at the list of applications I put up top. Those are NOT ones people generally talk a lot about. Spooks and fraud-fighters are two very secretive kinds of folks. And, for a variety of reasons, the owners of the largest websites also are reluctant to publicize details of how they do or don’t profile individual users in vivid detail. And then there’s also the question of whether we even want to help improve technology whose main use is to improve the precision with which computers track individuals – but I don’t think that’s the front on which the privacy wars are best fought.
But if I were a computer science researcher right now, graph databases – optimized to support graph-analytic metrics — are one of the areas I’d look at to see if I could make an impact.