  The graph edit distance (GED) is a flexible distance measure which is widely
used for inexact graph matching. Since its exact computation is NP-hard,
heuristics are used in practice. A popular approach is to obtain upper bounds
for GED via transformations to the linear sum assignment problem with
error-correction (LSAPE). Typically, local structures and distances between
them are employed for carrying out this transformation, but recently also
machine learning techniques have been used. In this paper, we formally define a
unifying framework LSAPE-GED for transformations from GED to LSAPE. We also
introduce rings, a new kind of local structures designed for graphs where most
information resides in the topology rather than in the node labels.
Furthermore, we propose two new ring based heuristics RING and RING-ML, which
instantiate LSAPE-GED using the traditional and the machine learning based
approach for transforming GED to LSAPE, respectively. Extensive experiments
show that using rings for upper bounding GED significantly improves the state
of the art on datasets where most information resides in the graphs'
topologies. This closes the gap between fast but rather inaccurate LSAPE based
heuristics and more accurate but significantly slower GED algorithms based on
local search.
