Linear Algebra and its Applications 438 (2013) 2331–2338

Contents lists available at SciVerse ScienceDirect

Linear Algebra and its Applications
journal homepage: w w w . e l s e v i e r . c o m / l o c a t e / l a a

A new dissimilarity measure for comparing labeled graphs
Nicolas Wicker a,∗ , Canh Hao Nguyen b , Hiroshi Mamitsuka bab

Laboratoire Painlevé, Université de Lille 1, 59655 Villeneuve d’Ascq, France
Bioinformatics Center, ICR, Kyoto University, Gokasho, Uji, Kyoto 611-0011, Japan

ARTICLE INFOABSTRACT

Article history:
Received 6 June 2012
Accepted 6 October 2012
Available online 30 November 2012

We use spectral graph theory to compare graphs that share the samenode set, taking into account global graph structures. We propose ageneral framework using eigendecomposition of graph Laplacians.
We show its special cases and propose a new dissimilarity measurethat avoid problems of spectral analysis. The new dissimilarity emphasizes the importance of small eigenvalues which are known tocarry the main information on graphs. General properties of the dissimilarity are discussed. The dissimilarity provides an efficient andintuitive tool for graph analysis.
© 2012 Elsevier Inc. All rights reserved.

Submitted by Shaun Fallat
AMS classification:
05C50
15A18
Keywords:
Labeled graph dissimilarity
Spectral graph comparison
Graph Laplacian

1. Introduction
Graphs have been a topic of much interest due to many emerging data analysis applications having
graph representation. For that reason, graph data analysis has been one of the focuses. To name a few,
such problems exist in Systems Biology [7], Chemoinformatics [11] and web data. One of the tasksof data analysis is to define similarities or distances among structured objects, comparing graphs is a
topic of much interest. The comparison is common in various scenarios such as similarity graph search,
QSAR, or machine learning on graphs such as graph kernels [12].
Our target here is the problem of comparing different labeled graphs sharing the same node set.
This is a special case of comparing graphs in general. While general graph comparison methods can beapplied, there are methods that can only be applied in this particular problem setting. This problem∗ Corresponding author. Tel.: +33 320434226.
E-mail addresses: nicolas.wicker@math.univ-lille1.fr (N. Wicker), canhhao@kuicr.kyoto-u.ac.jp (C.H. Nguyen), mami@kuicr.
kyoto-u.ac.jp (H. Mamitsuka).
0024-3795/$ - see front matter © 2012 Elsevier Inc. All rights reserved.
http://dx.doi.org/10.1016/j.laa.2012.10.021

2332

N. Wicker et al. / Linear Algebra and its Applications 438 (2013) 2331–2338

arises in the case of comparing biological networks to see the similarities and differences between
species, building phylogenetic trees [6].
The simplest solution is to consider the adjacency matrices as vectors and compare them directly.
The most famous one is certainly the edit-distance [10,4], also named Levenshtein distance, which was
initially developed to compare strings [8] and whose principle is simply to count the number of edges
that are present in one graph and not in the other. Many other distance measures approximate editdistances to account for its high computational complexity [13]. In this particular problem setting,edit-distance naturally becomes the number of different edges in the graphs. This means that alledges in the graph are considered of the same importance. This does not take into account global
graph structures, which could be a problem in the case that global graph structures matter.
Many other measures are based on substructures such as maximal common subgraph [2,5]. This isbased on the hypothesis that the semantics of the whole graph structures are based on the semanticsof their subgraphs. The candidate subgraphs usually are walks, paths, frequent subgraphs [12]. In thesemethods, graph comparison bases solely on the existence of subgraphs. These measures fail to keep
the graph structure as a whole and may not contain global structures for our interest. An attempt ofusing the global graph structures is to use graph spectra to reduce the problem of comparing graphs
to the problem of comparing vectors [9].
In this work, we use spectral graph theory to compare graph in order to take into account global
graph structures. We show a general framework and property of graph comparison using graph spectra.
We show that some other similarity or dissimilarity measures are just special cases. A problem of theframework is that one needs to do a spectral transformation that gives high weights to the eigenvalues
that are close to zero [3], and also ignores zero ones. Another problem is that graph comparison has
to be invariant under different eigenspace bases, a problem of spectral representation. We propose
a new dissimilarity measure that tackles these problems directly. Its advantages are shown on some
canonical examples and as well as its properties.
2. Graph Laplacian-based graph comparison
We show a simple example in which a graph is considered as a matrix or vector in Fig. 1. It isnoteworthy that this is equivalent to the edit-distance for our problem setting. We show that thisdistance is not adequate. The reason is that graphs have structures that are not easily seen in matrices
or vectors. This motivates to use a representation that takes structure information into account. For
that reason, we use the structure information contained in eigenvectors and eigenvalues of graphnormalized Laplacians, henceforth simply called Laplacians.
In Fig. 1, we have five graphs G1 , G2 , G3 , G4 and G5 . The difference between G1 and G2 is only
one edge. There is also only one edge difference between G1 and G3 but G3 is not connected. Whileconsidering graphs as matrices or vectors, the distance between G1 and G2 is the same as between
G1 and G3 . However, G3 is totally different as it is not connected. Graph Laplacian can show thisinformation in its eigenspectrum. G4 and G5 are two extremal graphs, namely the totally disconnected
graph composed of 18 vertices and K18 the complete graph of size 18.

Fig. 1. Three graphs compared with our similarity.

N. Wicker et al. / Linear Algebra and its Applications 438 (2013) 2331–2338

2333

Table 1
Correlation-based similarity.
G1
1
0.996
0.997
NaN
0.888

G1
G2
G3
G4
G5

G2
0.996
1
0.993
NaN
0.882

G3
0.997
0.993
1
NaN
0.883

G4
NaN
NaN
NaN
NaN
NaN

G5
0.888
0.882
0.883
NaN
1

Table 2
Bregman divergences.
G1
0
0.210
0.123
24.127
5.118

G2
0.210
0
0.33
24.414
5.412

G3
0.123
0.33
0
24.3755.364

G424.12724.41424.375019.059

G5
5.118
5.412
5.364
19.05902.1. General graph Laplacian-based graph comparison
Let us consider two graphs G1 (V1 , E1 ) and G2 (V2 , E2 ) which share the same set of vertices. Their
Laplacians L1 and L2 have eigenvalues in increasing order λ1 , . . . , λn and μ1 , . . . , μn respectively.
The corresponding eigenvectors are denoted u1 , . . . , un and v1 , . . . , vn . We suppose that they are
orthonormal, which is always possible as the Laplacians are symmetric.
We propose a general framework to compare graphs in the following form:
F (G1 , G2 ) =i,jf (λi , μj )|ui , vj |k ,(1)

for any k ∈ N , k > 0. The function f : (R, R) → R is a comparison between eigenvalues. The
measure F is a similarity or dissimilarity function according to f .
Special realizations of this measure are:
1. Correlation-based similarity. A natural similarity where unit length normalization of eigenvalues
and dot product are used in f .
C (G1 , G2 ) = 

1



2
2
i λi
i μi i,j

λi μj ui , vj 2 .

2. Bregman divergence (dissimilarity) with squared norm [1].
B(G1 , G2 ) =i,j(λi − μj )2 ui , vj 2 .

3. New dissimilarity measure. We propose a new dissimilarity measure between the two graphs
as follows:D(G1 , G2 ) = (λi − μj )2i,j

λi + μj

ui , vj 2 .

(2)

Values are given for all graph pairs of Fig. 1 in Tables 1–3. Interestingly, D(G1 , G2 ) = 0.122 andD(G1 , G3 ) = 0.124 showing that G1 is closer to G2 than to G3 . Thus, the lack of connectivity has acost in the distance, due to the weighting by the eigenvalue inverses. This must be compared to thecorresponding values obtained for the Bregman divergence, G1 is then closer to G3 than to G2 which

2334

N. Wicker et al. / Linear Algebra and its Applications 438 (2013) 2331–2338
Table 3New dissimilarity measure.
G1
0
0.122
0.124
18
2.876

G2
0.122
0
0.244
18
3.057

G3
0.124
0.244
0
18
3.078

G4
18
18
18
0
18

G5
2.876
3.057
3.078
18
0

is not a desirable result. On the contrary, the correlation based similarity has the same feature as the
proposed dissimilarity, making G1 closer to G2 than to G3 . The drawback of this similarity is that when
all eigenvalues are equal to 0 or close to it the normalization factor cannot be computed anymore. Let
us remark at this point that our dissimilarity measure can also be naturally extended by continuity
when eigenvalues are equal to 0. Indeed, if we consider two small eigenvalues x and y. If they are
equal, (x − y)2 /(x + y) = 0, otherwise let us suppose without loss of generality that x > y, then(x − y)2 /(x + y) < (x − y)2 /(x − y) = x − y which tends to 0 when x tends to 0. Considering theseresults, we have focused our study on the new dissimilarity d. It is indeed a dissimilarity and not a
distance, it is sufficient to notice in the previous example that D(G3 , G1 ) + D(G1 , G5 ) < D(G3 , G5 ) to
make it clear.
2.2. Invariance property
We show that among all those possible graph comparisons in (1), only for k = 2, the comparisons
are invariant under different eigenvector bases of the graph Laplacian. Since the eigenvector bases are
not supposed to be unique, we mean that only k = 2 should be used for all these graph comparisons.
Theorem 1. The similarity/dissimilarity measures
F (G1 , G2 ) =i,jf (λi , μj )|ui , vj |kare invariant to the choice of eigenspace bases if and only if k = 2.
Proof. We want to prove that the measure F is invariant regardless of the choices of eigenvector bases.
Since choices only happen for eigenvectors of the same eigenvalues, it is sufficient to prove that F isinvariant if and only if k = 2.

Without loss of generality, if we suppose that v1 , . . . , vl and v1 , . . . , vl are two eigenvector bases
corresponding to one eigenvalue μ of L2 . The invariance of F can be boiled down to its invariance inthe two bases. The necessary and sufficient condition for F to be invariant for any f is that for any unit
vector ul
i=1

f (λ, μ)|u, vi |k =

l

i=1



f (λ, μ)|u, vi |k .

(3)This is equivalent to:l
i=1|u, vi |k =

l

i=1



|u, vi |k .

It is easy to see that for k = 2, this quantity is the length of the projection of u in the eigensubspaceof μ.

N. Wicker et al. / Linear Algebra and its Applications 438 (2013) 2331–2338

2335

Now we prove the other way around that, for k  = 2, the equality in (3) does not hold in general. We

construct a general counterexample as follow. Since the sets {v1 , . . . , vl } and {v1 , . . . , vl } are distinct,
we can always choose a vector u in the former set not present in the latter one. Then,l
i=1|u, vi |k = 1,

because u is in the set. On the other hand,
l

i=1



|u, vi |k >

l

i=1



u, vi 2 = 1

for k < 2, and
l

i=1



|u, vi |k <

l

i=1



u, vi 2 = 1

for k > 2. Therefore, in general, the equality in (3) does not hold for k  = 2. 
Corollary 1. The dissimilarity function we proposed is invariant under any choice of eigenspace base.
This desirable property has been proved in Theorem 1, remarking that|u, v2 | = u, v2 .

3. Properties of the new dissimilarity measure
We can show some properties of the new dissimilarity measure. In particular, it behaves well withregard to graph connectivity.
Theorem 2. Dissimilarity D(G1 , G2 ) = 0 implies that the Laplacians L1 and L2 eigendecompositions of
G1 and G2 are equal.
Proof. First we prove that ∀i ∈ 1, . . . , n, λi = μi . Let us consider that there is an eigenvalue λwhich has multiplicity m1 in L1 and m2 in L2 with m1  = m2 . Then, the subspace Eλ⊥ orthogonal
to the eigenspace Eλ of L1 for eigenvalue λ has dimension n − m1 . As D(G1 , G2 ) = 0 the eigenvectors corresponding to λ in L2 are orthogonal to Eλ⊥ , so that Eλ⊥ has dimension n − m2 leading to acontradiction.
Now, we can prove that the eigenspaces are the same. If we take any eigenvalue λ, for L1 , obviously,
Eλ is orthogonal to all other eigenspaces. As for L2 , its eigenspace Fλ for eigenvalue λ is also orthogonal
to Eλ⊥ as D(G1 , G2 ) = 0, so that Fλ = Eλ . This is true for every eigenvalue λ and so the proof iscompleted. 
An important consequence of this theorem is that if D(G1 , G2 ) = 0, the Laplacians and hence thegraphs are the same.
4. Experiments
We conducted some experiments to demonstrate the properties of our dissimilarity measure incomparison with the correlation-based similarity, the Bregman divergence and the edit distance. The
experimental setting was as follows. We started with a canonical graph G consisting of 9 disconnected

N. Wicker et al. / Linear Algebra and its Applications 438 (2013) 2331–2338

0.998
0.996
0.994
0.992

Correlation−based similarity

1.000

2336

0

20

40

60

80

100

Number of random edges

3
2
1
0

Bregman divergence4

Fig. 2. Results for the correlation-based similarity. Horizontal axis shows the indices of graphs Wi and Bi and vertical axis shows thecorrelation-based similarity: C (G, Wi ) (bullets) and C (G, Bi ) (circles).

0

20

40

60

80

100

Number of random edges
Fig. 3. Results for Bregman divergence. Horizontal axis shows the indices of graphs Wi and Bi and vertical axis shows the Bregman
divergence: B(G, Wi ) (bullets) and B(G, Bi ) (circles).

subgraphs. Each subgraph was a 3-regular graph with 25 nodes. We generated 100 graphs, denoted
Bi , ∀i = 1 · · · 100 , by adding randomly i edges connecting two nodes belonging to 2 different subgraphs of the 9 subgraphs (between subgraph edges). We also generated 100 other graphs, denoted
Wi , ∀i = 1 · · · 100, by adding randomly i edges connecting any two nodes in the same subgraph of the
9 subgraphs of G (within subgraph edges). It was our idea to generate the Bi graphs so that by addingedges between subgraphs, the connectivity of the graphs would change more than in the case of addingedges within subgraphs in the Wi graphs (the former case connects disconnected subgraphs while thelatter does not). We wished dissimilarity measures reflect that graphs Bi are more dissimilar to G thanits counterpart, Wi to G.
Experimental results are shown in Figs. 2, 3 and 4 for the correlation-based similarity, the Bregman
divergence and the new dissimilarity measure. The following are observed.

2337

2.5
2.0
1.5
1.0
0.0

0.5

New dissimilarity

3.0

3.5

N. Wicker et al. / Linear Algebra and its Applications 438 (2013) 2331–2338

0

20

40

60

80

100

Number of random edges
Fig. 4. Results for the new dissimilarity measure. Horizontal axis shows the indices of graphs Wi and Bi and vertical axis shows thedissimilarity measure: D(G, Wi ) (bullets) and D(G, Bi ) (circles).

1. The edit-distance, in our problem setting being the number of different edges, is the same for
the Bi and Wi graph pairs, so graphs are not shown for it.
2. The correlation-based similarity and the Bregman divergence in Figs. 2 and 3 respectively, do
not show much difference between the Bi and Wi graph pairs.
3. The new dissimilarity measure, as in Fig. 4, shows for the Bi and Wi graph pairs that graph Bi are
more dissimilar than Wi , as we wish for in our experimental setup.
We conclude that, our proposed new dissimilarity measure is able to distinguish the differences ofgraphs with different graph connectivities while the others are not.
5. Conclusion
We have presented a framework for comparing graphs with the same node set, taking into accountglobal graph structures. Properties of the framework are shown as well as special cases, including a
new graph dissimilarity that is straight-forward to compute and, at the same time, has some niceproperties. First, it is invariant under different graph eigenspace bases, making it independent of theeigendecomposition process. Second, a zero dissimilarity actually indicates that the two graphs areequal. Then, we have specifically aimed at having a dissimilarity giving more weight to eigenspaces
with small eigenvalues. The measure proves to be able to take into account global structures in the toy
example and the experiments.
References[1] A. Banerjee, S. Merugu, I.S. Dhillon, J. Ghosh, Clustering with Bregman divergences, J. Mach. Learn. Res. 6 (2005) 1705–1749.
[2] H. Bunke, K. Shearer, A graph distance metric based on the maximal common subgraph, Pattern Recognit. Lett. 19 (3–4) (1998)
255–259.
[3] F.R.K. Chung, Spectral Graph Theory, American Mathematical Society, 1997.
[4] M.A. Eshera, K.S. Fu, A graph distance measure for image analysis, IEEE Trans. Syst. Man Cybern. 14 (1984) 398–407.
[5] M.-L. Fernández, G. Valiente, A graph distance metric combining maximum common subgraph and minimum common supergraph, Pattern Recognit. Lett. 22 (6–7) (2001) 753–758.
[6] M. Heymans, A.K. Singh, Deriving phylogenetic tree from the similarity analysis of metabolic pathways, Bioinformatics 26 (17)(2003) 138–146.
[7] H. Hu, X. Yan, Y. Huang, J. Han, X.J. Zhou, Mining coherent dense subgraphs across massive biological networks for functional
discovery, Bioinformatics 21 (1) (2005) 213–221.

2338

N. Wicker et al. / Linear Algebra and its Applications 438 (2013) 2331–2338[8] V.I. Levenshtein, Binary codes capable of correcting deletions, insertions, and reversals, Sov. Phys. Dokl. 10 (1966) 707–710.
[9] B. Luo, R.C. Wilson, E.R. Hancock, Spectral embedding of graphs, Pattern Recognit. 36 (2003) 2213–2230.
[10] A. Sanfeliu, K.S. Fu, A distance measure between attributed relational graphs for pattern recognition, IEEE Trans. Syst. Man
Cybern. 13 (1983) 353–362.
[11] N. Trinajstic, J.V. Knop, W.R. Muller, K. Syzmanski, S. Nikolic, Computational Chemical Graph Theory: Characterization, Enumeration and Generation of Chemical Structures by Computer Methods, Prentice Hall, 1991.
[12] S.V.B. Vishwanathan, N.N. Schraudolph, R. Kondor, K.M. Borgwardt, Graph kernels, J. Mach. Learn. Res. 11 (2010) 1201–1242.
[13] Z. Zeng, A.K.H. Tung, J. Wang, J. Feng, L. Zhou, Comparing stars: on approximating graph edit distance, Proc. VLDB Endowment
2 (1) (2009) 25–36.