  Statistical phylogenetic inference methods use tree rearrangement operations
to perform either hill-climbing local search or Markov chain Monte Carlo across
tree topologies. The canonical class of such moves are the
subtree-prune-regraft (SPR) moves that remove a subtree and reattach it
somewhere else via the cut edge of the subtree. Phylogenetic trees and such
moves naturally form the vertices and edges of a graph, such that tree search
algorithms perform a (potentially stochastic) traversal of this SPR graph.
Despite the centrality of such graphs in phylogenetic inference, rather little
is known about their large-scale properties. In this paper we learn about the
rooted-tree version of the graph, known as the rSPR graph, by calculating the
Ricci-Ollivier curvature for pairs of vertices in the rSPR graph with respect
to two simple random walks on the rSPR graph. By proving theorems and direct
calculation with novel algorithms, we find a remarkable diversity of different
curvatures on the rSPR graph for pairs of vertices separated by the same
distance. We confirm using simulation that degree and curvature have the
expected impact on mean access time distributions, demonstrating relevance of
these curvature results to stochastic tree search. This indicates significant
structure of the rSPR graph beyond that which was previously understood in
terms of pairwise distances and vertex degrees; a greater understanding of
curvature could ultimately lead to improved strategies for tree search.
