Database Reference
In-Depth Information
each of the edit operations and use ecient tree search techniques to identify
the sequence of edit operations resulting in the lowest total edit cost [15,32].
The resultant lowest total edit cost is a measure of the distance between
the two graphs.
In general graph matching problems with unlabeled graphs, a unique
sequence of edit operations does not exist due to the occurrence of multiple
possible vertex mappings. The
ged
algorithms are required to search for
the edit sequence that results in a minimum edit cost. However, for the
class of graphs introduced in Section 2, vertex-weight value substitution is
not a valid edit operation because vertex-weight values are unique. As a
result, the combinatorial search reduces to the simple identification of ele-
ments (vertices and edges) inserted or deleted from one graph
G
to produce
the other graph
H
. The implementation requires linear time in size of the
problem.
If the cost associated with the insertion or deletion of individual ele-
ments is one, and edge-weight value substitution is not considered (i.e.,
we consider the topology only), the edit sequence cost becomes the differ-
ence between the total number of elements in both graphs, and all graph
elements in common.
Using the above cost function, let
=
V
G
,E
G
,w
V
,w
V
and
G
H
=
V
H
,E
H
,w
V
w
V
be two graphs the similarity of which is to be evaluated.
The
graph edit distance
d
1
(
G, H
) describing topological change that takes
place when going from graph
G
to
H
then becomes:
d
1
(
G, H
|V
G
|
|V
H
|−
|V
G
∩ V
H
|
|E
G
|
|E
H
|−
|E
G
∩ E
H
|.
)=
+
2
+
+
2
(4.1)
Clearly the edit distance, as a measure of topology change, increases
with increasing degree of change. Edit distance
d
1
(
G, H
) is bounded below
by
d
1
(
G, H
)=0when
H
and
G
are isomorphic (i.e., there is no change),
and above by
d
1
(
G, H
)=
|V
G
|
+
|V
H
|
+
|E
G
|
+
|E
H
|
when
G ∪ H
=
∅
,the
case where the graphs are completely different.
In the second graph edit distance measure studied in this paper, we
consider not only change in graph topology, but also in edge weight. For
this purpose, we assign a cost
c
to each vertex deletion and insertion, where
w
E
c>
0 is a constant. The cost of changing weight
(
e
)onedge
e ∈ E
G
into
)
. To simplify our notation
we let our graphs be completely connected (i.e., there is an edge
e ∈ E
H
is defined as
w
E
w
E
− w
E
(
e
)on
(
e
)
(
e
e ∈ E
H
between any two vertices in
G
andanedge
e ∈ E
H
between any two vertices
in
H
) and assign a weight equal to zero to edge
e ∈ E
G
(
e ∈ E
H
) if this edge
does not exist in
G
(
H
). Hence substitution of edge weights, edge deletions,
