I just put a new paper up on the arXiv, and so I thought I would share it here. This was the final paper I wrote for my Ph.D., and it’s the one I’m most proud of, because by this point I was determining the direction that the research was going.
The paper is called “Metrics for Graph Comparison: a Practitioner’s Guide.” It’s a survey paper, comparing different tools that can be used to compare graphs. In research, so many people spend so much time developing new methods, and I always think to myself, “How does this compare to the standard method? Is it actually an improvement?” This paper attempts to take stock of a number of standard and cutting-edge methods in graph comparison, and see what works best.
The focus is on practicality, and so we only look at distances that are linear or near-linear (i.e. or ) in the number of vertices in the graph.1 We find that spectral methods (which are quite standard, and have been around for some time) are strong performers all around. They are robust, flexible, and have the added benefit of easy implementation - fast spectral algorithms are ubiquitous in modern computing packages such a MATLAB, SciPy, and Julia.
I’ve implemented many of these distances in my Python library NetComp,
which you can get via
pip install netcomp. Check it out, and feel free to
post issues and/or PRs if you want to add to/modify the library.
Let me know in the comments what you think! Or feel free to email me if you have more detailed questions about graph metrics. Happy Friday!
This is paired with the assumption that the graph is sparse, so the number of edges is ↩