The extraction of graph structures in Euclidean vector space is a topic of interest with applications in many fields, such as the analysis of vascular networks in the biomedical domain. While a number of approaches have been proposed to tackle the problem of graph extraction, a quantitative evaluation of those algorithms remains a challenging task: In many cases, manual generation of ground truth for real-world data is time-consuming, error-prone, and thus not feasible. While tools for generating synthetic datasets with corresponding ground truth exist, the resulting data often does not reflect the complexity that real-world scenarios show in morphology and topology. As a complementary or even alternative approach, we propose GERoMe, the graph extraction robustness measure, which provides a means of quantifying the stability of algorithms that extract (multi-)graphs with associated node positions from non-graph structures. Our method takes edge-associated properties into consideration and does not necessarily require ground truth data, although available ground truth information can be incorporated to additionally evaluate the correctness of the graph extraction algorithm. We evaluate the behavior of the proposed graph similarity measure and demonstrate the usefulness and applicability of our method in an exemplary study on both synthetic and real-world data.