  The graph edit distance (GED) measures the dissimilarity between two graphs
as the minimal cost of a sequence of elementary operations transforming one
graph into another. This measure is fundamental in many areas such as
structural pattern recognition or classification. However, exactly computing
GED is NP-hard. Among different classes of heuristic algorithms that were
proposed to compute approximate solutions, local search based algorithms
provide the tightest upper bounds for GED. In this paper, we present K-REFINE
and RANDPOST. K-REFINE generalizes and improves an existing local search
algorithm and performs particularly well on small graphs. RANDPOST is a general
warm start framework that stochastically generates promising initial solutions
to be used by any local search based GED algorithm. It is particularly
efficient on large graphs. An extensive empirical evaluation demonstrates that
both K-REFINE and RANDPOST perform excellently in practice.
