Sunday, May 09, 2010

graph visualizations as sexy as fractals

I love to display mathematical phenomena -- often for me the proof is in the visualization. If you ever steal one of my personal research notebooks you'll see that the number of graphs I've been drawing over the years has been increasing at a steady rate. This is a habit I acquired from studying Probabilistic Graphical Models and the machine learning-heavy curriculum at CMU.

Back in high school I was amazed by the beauty of fractals based on Newton's method for finding roots, but as I've slowly been shifting my mode of thought from continuous optimization problems to discrete ones, automated graph visualization is as close as I've ever gotten to being an artist. Here is one such sexy graph visualization from Yifan Hu's gallery.

Andrianov/lpl1 via sfdp by Yifan Hu

I have been using Graphviz for about 8 years now, and I just can't get enough. I never thought it would produce anything as beautiful as this! I generally used graphviz to produce graphs like this:

Inspired by Yifan Hu and his amazing multilevel force directed algorithm for visualizing graphs I've started using sfdp for some of my own visualizations. sfdp is now inside graphviz, and can be used with the -K switch as follows (also with overlap=scale):

$ dot -Ksfdp -Tpdf memex.gv > memex.pdf

Inspired by Yifan Hu's coloring scheme based on edge length, I color the edges using a standard matlab jet colormap with shorter edges being red and longer ones being blue. To get the resulting lengths of edges, I actually run sfdp twice -- once to read off the vertex positions (this is what the graph drawing optimization produces), and once again to assign the edge colors based on those lengths. I could process the resulting postscript with one run like Yifan, but I don't want to figure out how to parse postscript files today. Here is an example using some of my own data.

Car Concept Visual Memex via sfdp by Tomasz Malisiewicz

This is a visualization of the car subset of the Visual Memex I use as an internal organization of visual concepts to be used for image understanding. If you click on this image, it will show you a significantly larger png.

As a sanity check, I also created a visualization of a standard UF Sparse Matrix (here is both mine and Yifan's result)
UTM1700b via sfdp by Yifan Hu

UTM1700b via sfdp by Tomasz Malisiewicz

As you can see, the graphs are pretty similar, modulo some coloring strategy differences -- but since the colors are somewhat arbitrary this is not an issue. If you click on these pictures you can see the PDFs which were generated via graphviz. Now only if my real-world computer vision graph were as structured as these toy problems then others could view me as both an artist and a scientist (like a true Renaissance man).