Graph Visualization is Difficult, but is it Useful?

I'm currently preparing some material for a lecture on visualization that William Cohen and Natalie Glance have kindly invited me to give as part of their course on Social Media Analysis (I'll probably share the paper here when it is complete). Naturally, one of the topics that permeates this area is network or graph visualization.

Creating good graph visualizations is hard, but often not always for the reasons people think. You might think that it is difficult to get all the edges of the graph represented without too many crossings, or perhaps it is hard because of the complexity of the algorithms (that is to say, it can take a long time to compute the best layout). When you get right down to it, graph visualization is difficult because it is often done without a clear purpose.

Of course, an easy way out of this dilemma, and one that I will confess to in the creation of examples like those found in the gallery on this blog, is to make the purpose of the visualization primarily aesthetic or artistic. However, this only leads to the double take reaction: that's cool - what is it?

Ben Shneiderman and Aleks Aris of the University of Maryland, have been working on an approach to better presenting graphical information by building systems that use what they call a semantic substrate. The semantic substrate essentially creates a meaningful partition of the nodes (e.g. in to specific classes), lays them out initially according to that substrate and then render the edges. This effectively wholly removes the problem of locating the nodes in a manner determined by the nature of the graph.

There are a number of similar examples that perhaps form steps on the evolution to this approach, the most obvious being the use of a geographic map as a substrate.

Below is an example from their paper 'Network Visualization by Semantic Substrates' which depicts the relationship between cases within and between the different levels of the US judicial system. In addition, the substrate (represented by boxes) has an additional left to right constraint representing the date of the court cases.

Comments

[Adrian Heilbut]

Thanks for pointing out this paper - the approach is very nice. The problem of making meaningful visualizations of large graphs is something I've struggled with in the past with protein interaction data. I think that often people end up looking at graphs through exploring local neighbourhoods around one node at a time.

Another idea that this work reminds me of is the PRISM algorithm developed by Segre and Kishony (Nat. Genet, 2004). There, rather than defining classes of nodes a priori, they use characteristics of the graph to define the classes. They are working with graphs with seeral different types of edges, and they look for subsets of nodes that share exactly the same types of edges - that is, they relate to other parts of the graph in a similar way. By partitioning the graph in this manner, they are able to come up with clusters that are functionally meaningful, as well as a visualization in which the nature of the relationships between the clusters is apparent.

[Nathan]

This approach looks pretty promising. I always feel a bit jaded when I see another graph visualization, but more exploration functionality seems to really bring the viz out of art/aesthetic land.