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).

12 comments:

  1. The one graph which I've created from my own data (Car Concept Visual Memex) needs a bit of explaining in case you're wondering what it means.

    The graph (a subset of the Visual Memex) is a visualization of thousands of car instances from the LabelMe dataset. Each vertex is a particular car instance (an exemplar), and an edge connects two car exemplars if they are considered similar by my distance function learning algorithm. Not all cars are similar to all cars, and the magic is figuring out which ones should connect to which others.

    I describe the visual memex building process in my NIPS 2009 paper: Beyond Categories: The Visual Memex Model for Reasoning About Object Relationships.

    The colors here are arbitrary, the actual edge length is an output of the graphviz optimization process, and not necessarily related to the edge "similarity" strength.

    ReplyDelete
  2. Thanks reddit for giving me my first blog post with over 1000 views in 24 hours! I guess everybody loves sexy mathematical visualizations.

    ReplyDelete
  3. Anonymous6:09 PM

    thanks for the pretty pictures, but is it possible to post the .gv files so we can play with this ourselves?

    ReplyDelete
  4. I'll post my sfdp scripts, some matrices, as well the resulting .gv files and .pdf files once I have more time -- perhaps this weekend. I'll just make a new post out of it.

    -Tomasz

    ReplyDelete
  5. james8:21 PM

    It would be amazing if you could put your scripts up. I never realised graphviz could make such pretty pictures! I have some sparse matrices that I've been wanting to visualise for some time and sfdp looks perfect. Thanks!

    ReplyDelete
  6. Anonymous5:46 PM

    I would also very much like to take a look at the scripts you used! I'ven been trying to get to grips with sfdp, but so far, performance is a big problem with a graph with ~42,000 edges and ~20,000 nodes. Any hints? Thanks a lot!

    ReplyDelete
  7. Are you realistically planning on posting your scripts?

    If not, I'll continue spending 1% of the time graphing and 99% of the time playing trial-and-error with stuff from graphviz's "documentation" to get it to look decent.

    ReplyDelete
  8. Andrew, are you not getting good colors? Or is the layout strange? Did you try using sfdp?

    ReplyDelete
  9. Anonymous12:28 AM

    hello from the future, april 2011. I'd love to see your pictures; they seem to link to an older location though... cheers!

    ReplyDelete
  10. Anonymous4:23 PM

    Must say I am very curious how you manage to create this, frankly, magnificent drawings. In other words... Any hope that you could post a tutorial or some minimal working example that includes how you render the colors and so on using matlab?

    Be much appriciated.

    /Casper

    ReplyDelete
  11. The code is now up on Github! Just post an issue on Github if you're having problems, or submit a pull request if you've enhanced the wrappers.

    http://quantombone.blogspot.com/2012/01/drawing-sexy-graphs-in-matlab.html

    ReplyDelete
  12. You can also go to the github page with my matlab graphviz sfdp wrapper scripts:
    https://github.com/quantombone/graphviz_matlab_magic

    ReplyDelete