A significant number of graph database systems has emerged in the past few years. Most aim at the management of the property graph data structure: where graph elements can be assigned with properties. In this paper, we address the need to compare the performance of different graph databases, and discuss the challenges of developing fair benchmarking methodologies. We believe that, compared to other database systems, the ability to efficiently traverse over the graph topology is unique to graph databases. As such, we focus our attention on the benchmarking of traversal operations. We describe the design of the graph traversal benchmark and present its results. The benchmark provides the means to compare the performance of different data management systems and gives us insight into the abilities and limitations of modern graph databases.