<p>While simple random graph models often have a strong theoretical basis, graphs with complex constraints can only be generated by heuristic algorithms. Using these methods, there is no guarantee that the generated graphs are sufficiently random. However, this is important knowledge in many applications of random graphs, such as creating realistic and diverse synthetic datasets. To address this problem, we propose a randomness measure based on pairwise graph distances, and we present four new feature-based graph distance measures tailored to graphs with bounded frequencies of small subgraphs (graphlets). Three of the distances use features derived from graphlet frequencies, while the fourth is derived from the joint degree distribution and therefore much easier to compute. We evaluate these distances in a series of experiments on synthetic and real networks. Our experimental results show that two graphlet-based distances do not reliably show good results and, in particular, do not reproduce the expected trends in experiments on measuring randomness. However, our novel Radial Graphlet Distribution Distance is effective, and comparable in performance to state-of-the-art methods. These findings highlight the importance of selecting an appropriate graph distance. Finally, we show that our easy-to-compute Joint Degree Distance is a viable alternative to graphlet-based distances, especially for measuring randomness in sets of very large networks.</p>