La distancia de edición de gráficos (GED) es una herramienta poderosa para modelar la disimilitud entre gráficos. Sin embargo, evaluar el GED exacto es NP-duro. Para abordar este problema, se introdujeron métodos de estimación de GED, por ejemplo, durante los cuales se emplearon heurísticas. La naturaleza estocástica de estos métodos induce el problema de estabilidad. En este documento, proponemos el primer estudio formal de la estabilidad de las heurísticas de GED, comenzando por definir una medida de estas (in)estabilidades, es decir, el error relativo. Luego, se examinan los efectos de dos factores críticos en la estabilidad, a saber, el número de soluciones y la proporción entre los costos de edición. Las proporciones se calculan en cinco conjuntos de datos de diversas propiedades. Se proporcionan sugerencias generales para elegir adecuadamente estos factores, lo que puede reducir el error relativo en más de un orden de magnitud. Finalmente, verificamos la relevancia de la estabilidad para predecir el rendimiento de las heurísticas de GED, aprovechando un algoritmo de aprendizaje de costos de edición para optimizar el rendimiento y la regresión de los k-vecinos más cercanos para la predicción. Los experimentos muestran que los costos optimizados corresponden a proporciones mucho más altas y un orden de magnitud menor de errores relativos que el costo experto.