Database Reference
In-Depth Information
G
H
V
In the case of two graphs
and
with the same vertex set
,and
w
E
w
E
(different) edge-weights
and
,the
(Umeyama) graph distance
is
expressed as:
)=
u,v∈V
w
E
)
2
− w
E
G, H
u, v
u, v
.
dist(
(
)
(
(3.2)
In spite of the computational diculty of finding a permutation matrix
P
which minimises
(
P
), in the restricted case of orthogonal (permutation)
matrices, one can use the spectra (eigendecompositions) of the adjacency
matrices
A
G
and
A
H
. In fact, for Hermitian matrices
A
J
,
B
∈ M
nn
(
R
)
with corresponding spectra
σ
(
A
)=
{α
1
>α
2
> ··· >α
n
}
and
σ
(
B
)=
, and with eigendecompositions
A
=
U
A
D
A
U
A
{β
1
>β
2
> ··· >β
n
}
and
B
=
U
B
D
B
U
B
(
U
are unitary, and
D
are diagonal matrices):
(
·
)
(
·
)
n
a
i
− b
i
)
2
=min
Q
QAQ
T
−
2
,
(
B
(3.3)
i
=1
where the minimum is taken over all unitary matrices
Q
. Equation (3.3)
justifies the use of the adjacency matrix spectra; given two weighted graphs
G
and
H
with respective spectra
σ
(
A
G
)=
{λ
1
,λ
2
,...,λ
n
1
}
and
σ
(
A
H
)=
{µ
1
,µ
2
,...,µ
n
2
},
the
largest positive eigenvalues are incorporated into the graph distance
measure [26] as:
k
i
=1
λ
i
− µ
i
)
2
min
i
=1
λ
i
,
j
=1
µ
j
(
,
dist(
G, H
)=
(3.4)
where
is an arbitrary summation limit, but empirical studies in pattern
recognition and image analysis show that
k
20 is a good choice. Notice
that similar approaches to distance measures can be applied to the case of
Laplacian spectra.
k ≈
4. Graph Edit Distance
In this section we introduce a graph distance measure, termed graph edit
distance
ged
, that is based on graph edit operations. This distance measure
evaluates the sequence of edit operations required to modify an input graph
such that it becomes isomorphic to some reference graph. This can include
the possible insertion and deletion of edges and vertices, in addition to
weight value substitutions [31]. Generally,
ged
algorithms assign costs to
