"Before I joined Microsoft, I was a mathematician working in computational graph theory. I spent years thinking about graphs every day, so it was a habit that was hard to break. "
As a former BitKeeper developer, this is a key person for Microsoft to have on hand to improve git. BitKeeper got about 10X faster after it was used on the Linux kernel and many of the key performance wins were due to better graph traversal algorithms. Rick was a wizard at that sort of thing. The other was memory layout optimizations and caching. (my contribution)
So Rick made sure we walked the graph as little as necessary and I made sure the graph had an extremely compact representation containing as little information as possible and then once a target commit is found it is looked up in another store.
However, this quote was disturbing. "There are a few Git features that don’t work well with the commit-graph, such as shallow clones, replace-objects, and commit grafts. If you never use any of those features, then you should have no problems!" The joy of not having to write commercial software! Reading between the lines it appears they changed the default output order for 'git log' or some internal API and then didn't bother to fix the cases that depending on the old order.