IEEE TRANSACTIONS ON NEURAL NETWORKS AND LEARNING SYSTEMS, VOL. 25, NO. 7, JULY 2014

1407

Selecting Graph Cut Solutions via Global Graph Similarity
Canh Hao Nguyen, Nicolas Wicker, and Hiroshi Mamitsuka

Abstract— Graph cut is a common way of clustering nodes on similarity
graphs. As a clustering method, it does not give a unique solution
under usually used loss functions. We specifically show the problem insimilarity graph-based clustering setting that the resulting clusters might
be even disconnected. This is counter-intuitive as one wish to have goodclustering solutions in the sense that each cluster is well connected andthe clusters are balanced. The key property of good clustering solutions
is that the resulting graphs (after clustering) share large components
with the original ones. We wish to detect this case by deriving a graphsimilarity measure that shows high similarity values to the originalgraph for good clustering solutions. The similarity measure considers
global connectivities of graphs by treating graphs as distributions in(potentially different) Euclidean spaces. The global graph comparisonis then turned into distribution comparison. Simulation shows that thesimilarity measure could consistently distinguish different qualities ofclustering solution beyond what could be done with the usually used loss
functions of clustering algorithms.

Index Terms— Graph cut, graph embedding, graph similarity,
Hilbert–Schmidt information criterion.
I. I NTRODUCTION
The problem is that clustering algorithms might produce manysolutions with the same optimality. The loss functions of clustering
algorithms might not be able to detect the bad solutions due to theirlimitations. It is particularly the case in graph-based clustering [4],[9], [10], [15], [21]. The loss functions are usually the cut quality
involving a small cut value (total weight cut) and the balance ofclusters. However, the gap is that the small cut value does not directly
lead to the well connectedness within clusters as desired. Detecting
a cluster being connected or not is computationally expensive to be
used as a loss function in clustering.
To simplify the discussion, we limit to the case of cutting a graphinto two clusters. We show the cases in which the optimal solutions,
if they were actually returned from the clustering algorithms, are
not unique. Hence, even if we suppose that the algorithms work as
desired, the solutions might have different qualities. For our problem
setting of graph-based clustering, an optimal solution of the problemof finding two clusters might have disconnected clusters. Graph cut
methods in computer vision [2], [3], [8], [19], while having thesame objective of coherent clusters, require the clusters to follow
supervised information rather than only the balance of clusters ingraph cut-based clustering setting.
We wish to be able to select the good solutions from many equally
optimal solutions of graph cut, two-cluster clustering algorithms using
the usual criteria that clustering algorithms use. This is not supposed
Manuscript received November 18, 2012; revised August 20, 2013; accepted
November 21, 2013. Date of publication December 12, 2013; date of current
version June 10, 2014. This work was supported in part by KAKENHI, MEXT,
Japan, under Grant 24300054.
C. H. Nguyen and H. Mamitsuka are with the Bioinformatics Center,
Institute for Chemical Research, Kyoto University, Uji 611-0011, Japan(e-mail: canhhao@kuicr.kyoto-u.ac.jp; mami@kuicr.kyoto-u.ac.jp).
N. Wicker is with the UFR de Mathématiques, Université Lille 1, Villeneuved’Ascq 59655, France (e-mail: nicolas.wicker@math.univ-lille1.fr).
Color versions of one or more of the figures in this paper are available
online at http://ieeexplore.ieee.org.
Digital Object Identifier 10.1109/TNNLS.2013.2292975

to be used to replace the clustering loss functions, but to address
the issue, which is failed to be accommodated by the graph cut loss
functions. Finally, we wish to find a criterion that, even though it
might be too expensive to be used as a clustering objective function,
should be more expressive to distinguish some bad solutions that are
failed to be recognized by the usual loss functions. A problem ofgraph cut with spectral clustering was illustrated in [20]. However,this brief does not give a single criterion to compare clusteringsolutions. It is possible to use this criterion to multicluster clustering
problem. However, as one has to combine the criterion on moreclusters, like other criteria, it is harder to analyze why it should workor fail.
The usual objective of clustering is to find clusters, which arebalanced in size and well connected within each cluster. Hence, agood clustering solution, in terms of the objective function, shouldhave two large clusters that each shares many edges with the originalgraph. On the other hand, a bad one might have clusters of unevensizes, and there might be disconnected clusters. As the former caseis cut with a smaller value in the sense of having a less number ofconnected components, the resulting graph after cut is closer to theoriginal one than that of the latter case. To distinguish the two cases,
we need to design a graph comparison method that considers global
connectivities of graphs. Specifically, we need a similarity measurethat makes the former case more similar to the original graph thanthe latter case is. This is a new graph similarity criterion that has notbeen addressed before.
We formalize this requirement as the problem of comparing labeledgraphs with the same node set. The problem is stated as follows.
Graph G i = (V, E i ), ∀i = 1, 2, . . . with the node set V fixed. We
wish to be able to compare the graphs, such as a similarity function
between G i and G j , considering global connectivities of the graphs.
There are many ways to compare graphs proposed in the literature.
Almost all of them are based on the parts of the graphs as features
for comparison. The examples include walks, paths [12], [16], andsubgraphs of the graphs [5]. The idea behind all these methods isthat the properties of a graph are determined by its parts separately.
Therefore, these methods do not reflect the topology of a graph as awhole, such as connectivity. Another line of work is based on graphedit distance [6]. However, in our special case of graphs with thesame node set, edit distance becomes the number of different edges.
The role of each edge is different for the global connectivity of thewhole graph (for example, some edges are bridges while others arenot). In this case, the difference of a bridge in the graph would be
more than other edges, while edit distance treats them all equally. We
wish to be able to incorporate graph connectivity into our comparison
as well. There are some other works using graph Laplacians [24] forfeature extractions.
In this brief, we first show the conditions in which the undesirable
solutions with disconnected clusters might be obtained in even the
optimal clustering solutions in graphs. We propose to use graphLaplacians to compare graphs with the same node set to reflect its
global connectivity. As graph Laplacians allow embeddings of graphs
into Euclidean spaces, we instead compare the embeddings. Hence,
the method is called graph embedding-based graph comparison.

2162-237X © 2013 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission.
See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.

1408

IEEE TRANSACTIONS ON NEURAL NETWORKS AND LEARNING SYSTEMS, VOL. 25, NO. 7, JULY 2014

We also show extensions of the comparison using eigendecompositions of the graph Laplacians. We show the properties of the comparison to observe the importance of edges toward global connectivity of
the whole graph, which is different from edit distance where all theedges have an equal weight. We provide some experiments to showthat our similarity measure of graphs can detect the good solutions
from the bad one in two-cluster clustering problem.

Case 1: s(D) ≤ s(C̄) + s(D  ), thencut(D, D̄)cut(D, D̄)cut(C, C̄)≤=s(D)min(s(C), s(C̄))
min(s(D), s( D̄))cut(C, C̄)cut(D  , D̄  )cut(D  , D̄  )≤.
=s(D  )
min(s(C), s(C̄))
min(s(D  ), s( D̄  ))Then, using the weighted average of fractions, we have

II. P ROBLEM W ITH G RAPH C UT-BASED C LUSTERING

cut(D, D̄) + cut(D  , D̄  )cut(C, C̄)≤s(D) + s(D  )min(s(C), s(C̄))
cut(C, C̄)=s(C)cut(C, C̄)<s(C̄)
cut(C, C̄)=.
min(s(C), s(C̄))

It is commonly known that, even though the clustering algorithms
return the optimal solutions according to their loss functions, there
might be undesirable solutions. Following are some undesirable
properties of the solutions.
1) There are many different solutions. This is a result of thenonconvexity of the loss functions.
2) For graph-based clustering, some clusters are not connected.
This section aims to provide the conditions in which the solutions
are not desirable. This is the problem we are trying to solve.
One of the common graph-based clustering algorithms is based ongraph cut [4] as follows. Given a graph G = (V, E), a graph cut
problem is to divide the set of nodes into two subsets that: 1) areeven in size or volume and 2) have a small number of edges between
the two subsets. Let X̄ denote the complement of any set X in V .
One looks for a cut (C, C̄) (C ⊂ V ) that minimizes the loss functionl(C, C̄) =cut(C, C̄)min(s(C), s(C̄))

This is a contradiction.
Case 2: by the definition of C, we have s(D) > s(C̄) + s(D  ).
Thencut(D, D̄)cut(C, C̄)≤min(s(C), s(C̄))
min(s(D), s( D̄))cut(D, D̄)cut(D, D̄) + cut(D  , D̄  )
≤
.
⇔
s(C̄)
s(C̄) + s(D  )(1)where s(·) could be the total degrees (volume) or total number ofnodes (size) of a set. The 
cut function in the numerator can beinstantiated as cut(C, C̄) = (i, j )∈E,V ∈C,V ∈C̄ wi j . In our setting,ij
we allow s to be any positive modular function (s(C∪D)+s(C∩D) =s(C)+s(D), ∀C, D ⊆ V ). Examples of s include the commonly usednormalized Cheeger cut and ratio Cheeger cut. There are other loss
functions for graph-based clustering [10], [21]. These loss functions
have different drawbacks, such as favoring more unbalanced clusters[4]. Further discussion is out of the scope of this brief.
The problem with graph cut for clustering using the above loss
functions is that the cut (C, C̄), which minimizes the loss functions lmight be disconnected. The following theorem shows the necessary
and sufficient conditions for this to happen.
Theorem 1: Suppose that (C, C̄) is a cut that minimizes the costfunction in (1). Suppose that the C-induced subgraph G  of G is
disconnected, then the following conditions hold:1) s(C) < s(C̄);2) for D as any union of the nodes in any set of maximallyconnected components of G  , thenl(C, C̄) = l(D, D̄).
Proof:Let D  be the complement of D in G  , thenD ∪ D = C, D ∩ D  = 0 and D̄ = C̄ ∪ D  . Because D is aset of maximally connected components, D is not connected to D 
in G. Thencut(C, C̄) = cut(D, D̄) + cut(D  , D̄  ).
Proving the first condition by contradiction. Suppose thatmin(s(C), s(C̄)) = s(C̄) < s(C), meaning that the larger cluster
is disconnected.
Without loss of generality, assume that s(D) ≥ s(D  ). Then, there
are two cases. In both cases, we use the assumption that C minimizes
the loss function in (1).

As all components in the inequalities are nonnegative, the second
inequality does not hold, leading to a contradiction. Both cases leadto contradictions. Hence, the larger cluster is not disconnected. The
first condition is proved.
Second condition:min(s(C), s(C̄)) = s(C)= s(D) + s(D  )= min(s(D), s( D̄)) + min(s(D  ), s( D̄  )).
Thencut(C, C̄)cut(D, D̄)≤min(s(C), s(C̄))
min(s(D), s( D̄))cut(C, C̄)cut(D  , D̄  )≤min(s(C), s(C̄))
min(s(D  ), s( D̄  ))cut(C, C̄)cut(D, D̄) + cut(D  , D̄  )≤min(s(C), s(C̄))
min(s(D), s( D̄)) + min(s(D  ), s( D̄  ))cut(C, C̄)=.
min(s(C), s(C̄))
This shows that all the three inequalities above must be equalities,thencut(D, D̄)cut(C, C̄)=.
min(s(C), s(C̄))
min(s(D), s( D̄))
The implication of the theorem is that, given any optimal graphcut that produces a disconnected cluster, equally optimal solutions
can be obtained by cutting only some of the maximally connectedcomponents of the disconnected cluster.
Theorem 1: Given (D, D̄) and (D  , D̄  ) are two optimal solutionsof (1). If D ∩ D  = ∅, cut(D, D  ) = 0, and s(D) + s(D  ) ≤ 1/2s(V ),then (D ∪ D  , D̄ ∩ D̄  ) is also an optimal solution of (1).

IEEE TRANSACTIONS ON NEURAL NETWORKS AND LEARNING SYSTEMS, VOL. 25, NO. 7, JULY 2014

Proof:cut(D, D̄)
=
s(D)

1409

embed nodes for different purposes of learning methods on the nodes[22]. For the moment, we just use the inverse of graph Laplacian as
the kernel for the node setcut(D  , D̄  )s(D  )cut(D, D̄) + cut(D  , D̄  )=s(D) + s(D  )cut(D ∪ D  , D̄ ∩ D̄  ).
=s(D ∪ D  )K i = L −1i .

Thus, the combined cut (D ∪ D  , D̄ ∩ D̄  ) is also optimal.
This theorem gives a way to combine the optimal solutions to makenew solutions without losing its optimality. It also shows that it ispossible to obtain the optimal solutions with a disconnected cluster.
We conclude that the type of loss functions as in (1) cannot
guarantee the well connectedness of clusters. We aim to fix this case.
III. G RAPH E MBEDDING -BASED G RAPH C OMPARISON
To consider graph connectivity, we use the embeddings of graphsthat reflect their global connectivities. We propose to embed thegraphs into Euclidean spaces and compare them. We use graphLaplacians [7] for embedding and Hilbert–Schmidt information criterion (HSIC) [13] for graph comparison. We first review the HSIC
to be used later in our similarity measure of graphs. We then propose
our graph embedding-based similarity measure (ges), its equivalent
formulation and its extensions.

(4)

Step 2 (Graph Comparison): The kernel encodes a sampling
distribution; hence the problem of comparing graphs becomes the
problem of comparing distributions. We specifically use HSIC as asimilarity measure (to be specific, a kernel) between the distributions.
We define our graph embedding-based graph comparison with thefollowing similarity measure.
Definition 1: The similarity of two graphs ges is defined to bedefges(G 1 , G 2 ) = (n − 1)2 · HSIC(K 1 , K 2 )(5)= trace(K 1 K 2 ).
For HSIC being a kernel between the distributions, our similarity
measure is also a kernel (a similarity measure) between the graphs.
Other similarity measures or dissimilarity measures such as Euclidean
distance between the graphs can be constructed on the top of thiskernel as usual.
Similarly, the distance between the two graphs can be defined basedon ges(G 1 , G 2 ), called graph embedding-based distance (ged), as
ged(G, G  ) = ges(G, G)+ges(G  , G  ) − 2ges(G, G  ). (6)C. Spectral Computation and Extensions

A. HSICHSIC is a measure of statistical independence between thetwo random variables. Let x be a random variable in thedomain X and z is another random variable in Z. Let F and
G be the feature spaces on X and Z with kernels k : X × X → R
and l : Z ×Z → R, respectively. Drawing samples (x, z) and (x  , z  )from a joint probability distribution p(x,z) , then HSIC is computed
via kernel functions as
HSIC( p(x,z) , F, G) = E x,x  ,z,z  [k(x, x  )l(z, z  )]+E x,x  [k(x, x  )]E z,z  [k z,z  ]−2E x,z E x  [k(x, x  )]E z  [k(z, z  )] .

(2)

Empirical estimation of HSIC is as follows:
HSIC( p(x,z) , F, G) =1
trace(KHLH)(n − 1)2(3)

where H is the centering matrix.
Considering the nodes of a graph in its embedded space
as a set of samples of a random variable. Specifically,
K 1 is a kernel for a sample of a random variable, and K 2 is a kernel
for a sample for another variable. HSIC between the two variables,
intuitively the correlation information between the two embeddingsof the same node set, can be computed asdef

HSIC(G 1 , G 2 ) = HSIC( p(K 1 ,K 2 ) )1
trace(K 1 K 2 ).
=(n − 1)2(K i are already centered as a property of eigenvectors of graphLaplacians).
B. Graph Embedding-Based Graph Comparison
To reflect the global connectivities of graphs, we use graphLaplacians. The procedure has two steps as follows.
Step 1 (Graph Embedding): We use graph Laplacians to embed
nodes of a graph into an Euclidean space. There are many ways to

It is known that there are many ways of defining kernels from graphLaplacians by spectral transforms. We show that for all the kernels
obtained by spectral transforms, there is a formulation to compute
the graph similarity measure using eigenvalues and eigenvectors of
the graph Laplacians, as in [23]. Moreover, the formulation allows
natural extensions of the similarity measure that are not available
from the distribution comparisons.
Suppose that the graph Laplacians are eigendecomposed
as L 1 = U D(λ)U T and L 2 = V D(μ)V T , in whichD(x) denotes a diagonal matrix with diagonal entries are thevector x. It is known that there are many kernels built on graph Laplacian with spectral transform g(λ), then K 1 = U D(g(λ))U T [22]. For
example, the kernels K 1 , K 2 as in (4), g(λ) = 1/λ (for λ > 0, andg(0) = 0).
Theorem 2: Suppose that the two graphs G 1 and G 2 define ajoint distribution of nodes, denoted as p(G 1 , G 2 ), then the similarity
defined in (5), as a HSIC between the two distributions defined by K 1
and K 2 , is computed with their eigenvalues (λi , μ j ) and eigenvectors(u i , v j ) as follows:ges(G 1 , G 2 ) =Proof:ng(λi ) · < u i , v j >2 ·g(μ j ).

(7)

i, j =1

ges(G 1 , G 2 ) = trace(K 1 K 2 )= trace U D(g(λ))U T · V D(g(μ))V T= trace D( g(λ))U T · V D(g(μ))V T ·
U D( g(λ))
 = trace D( g(λ))U T V D( g(μ)) ·D( g(μ))V T U D( g(λ))
 = trace D( g(λ))U T V D( g(μ)) ·



(8)
[D( g(λ))U T V D( g(μ))]T .
√√T=
D( g(λ))U V D( g(μ)), then Mi j=
 Let M
2,g(λi )u iT v j g(μ j ). Note that tr ace(M M T ) =Mi, j i j

1410

IEEE TRANSACTIONS ON NEURAL NETWORKS AND LEARNING SYSTEMS, VOL. 25, NO. 7, JULY 2014

Denote β = 1 − eT L −1 e. Then, ignoring the component with uin this brief.
Case 1: β = 0

then
ges(G 1 , G 2 ) = trace(K 1 K 2 )= trace(M M T )ng(λi )· < u i , v j >2 ·g(μ j ).
=

T −1
L −1
1 = (L − e × e )

(9)

ij

This completes the proof.
Note that the graph Laplacian-based comparison has the form
ges(G 1 , G 2 ) =nf (λi , μ j ) < u i , v j >2

(10)i, j =1

with f (λi , μ j ) = g(λi )g(μ j ). This allows extensions of the comparison by any other function f instead of g(λi )g(μ j ). Some examples,
as in [23] are:1) f (λi , μ j )=Breg(g(λ), g(μ)), where Breg means
Bregman divergence [1] between the two vectors. In thiscase, the comparisons are also Bregman divergences;2) f (λi , μ j ) = s(g(λ), g(μ)), where s denotes any similarity
measure such as correlation.
IV. E DGE W EIGHTING P ROPERTY
We show how the similarity measure gives different weights todifferent edges in a graph to reflect its importance to connectivity of
the graph, as opposed to edit distance.
Proposition 1: Edit distance between the two graphs G and G 1 isthe number of different edges between the two graphs.
Given a graph G = (V, E), we remove one edge, namely E kl fromG to become G 1 = (V, E 1 ). The similarity measure ges(G, G 1 ) isdifferent from edit distance that edges give different weights. In otherwords, some edges are more important than others, according to theirroles in the graph’s connectivity.
Theorem 3: The similarity function ges(G, G 1 ), as well as thekernel for the new graph, are all dependent on (functions of) theedge.
Proof: We demonstrate by graphs with one edge difference. We show that the similarity measure ges(G, G 1 ) andK 1 are dependent on the edge, as opposed to edit distance, which is
independent of edge, which was removed.
Let e ∈ Rn denote a vector with ek = 1 and el = −1, where
the remaining coordinates are 0. From the way graph Laplacians areconstructed, we have
L = L 1 + e · eT .
We prove here the results for connected graphs. Results fornonconnected graphs can be considered by decomposing the graphinto the connected subgraphs and merging the results. Once the graph
G is connected, its Laplacian L is of rank n − 1. Note that the nullspace of L is spanned by the vector o = {1, · · · 1}T ∈ Rn , meaningthat any vector x ∈ Rn that x T o = 0 is in the range of L (for any
graph L only).
Denote: J ∈ Rn×n is a matrix of all 1 as in [14], then J = ooT .
Therefore
1
1(I − L L −1 )(−e) = J (−e) = − ooT e = 0.
nnThis is the vector denoted as u in [18].
From [18] (theorem 5), we want to find the update of pseudoinverse1 of L 1 .
1 x −1 also denotes the pseudoinverse of a matrix x as well, whereappropriate.

= L −1 +L −1 eeT L −1.
1 − eT L −1 eHence, the amount of update from the inverse of the original graphLaplacian is
L −1 eeT L −1.
1 − eT L −1 e
The denominator β means the ratio of the number of spanning trees
in the graph that pass through e to the total number of spanning trees.
β = 0 means that removing the edge e does not disconnect the graph.
In other words, e is not a bridge. β = 0 means e is a bridge. 1 − β isalso known as the resistance distance in electronic circuit or chemistry[17], or Euclidean commute time distance in social networks [11].
Case 2: β = 0, using theorem 6 in [18]. Let q = |L −1 e|
T −1
L −1
1 = (L − e × e )11= L −1 − L −1 e(L −1 e)T L −1 − L −1 (eT L −1 )T eT L −1qq1
+ 2 ((L −1 e)T L −1 (eT L −1 )T )L −1 eeT L −1q
1 T −1 1 −1 T eT L −3 e T= L −1− L −1
ee L −1 .
ee L + L ee −qqq2

Hence, the amount of update from the inverse of the original graphLaplacian is
eT L −3 e T
1ee− L −1 eeT L −1 + L −1 eeT −qq

L −1 .

Both cases prove that, the similarity between the original and a
new graph (by removing one edge) is a function depending on theedge itself. This is totally different from the edit distance in which
the importance of an edge in graph connectivity is not detected.
V. E XPERIMENT
As in Section II, the problem with graph cuts is that the loss
functions only concern two criteria: the total amount of weight cut
and the balance of the clusters. One of the purposes of graph cutbased clustering is to have highly connected clusters; it makes sense
to require all nodes in the same cluster to connect to each other.
However, this condition is not reflected in the loss functions in (1).
We show by simulation that our similarity measure or distance canreflect whether the clusters are connected or not among clusteringsolutions of the same loss function. It is the case that graph cut
algorithms may find many possible optimal solutions with respect
to the loss function but, intuitively, some solutions make more sensethan others. The simulation graph is shown in Fig. 1 (the first graph).
The graph is designed based on the result of the previous sections.
The simulation shows different graph cuts, which are all optimal[for ratio cut loss function, an instantiation of (1)]. The graph is cut
by red slides, producing disconnected clusters, resulting in graph G (the second graph). Graph is cut by blue dotted slides, producing
connected clusters, resulting in graph G ∗ (the third graph).
According to the previous section, they are equally optimal cuts,
so as the cuts by any single red slide. This makes it impossible forthe loss function to determine whether the cut results in disconnectedclusters or not.

IEEE TRANSACTIONS ON NEURAL NETWORKS AND LEARNING SYSTEMS, VOL. 25, NO. 7, JULY 20141411

solutions having the loss functions close to the optimal one. We foundthat for all the solutions having a similar graph cut loss’s values, theones with the smallest ged values are usually the ones with connectedclusters. This means that, for solutions with loss functions close to
optimal ones, we can also rely on the distance to select connected
solutions. This result extends the optimal solutions selection in theabove simulation to a real world case.
VI. C ONCLUSION

Fig. 1. Simulation graph: each round-shaped area A, B, C, or D is a cliquewith all edges of weight 1. All the edges between cliques: A-B, C-B withweight w, B-C with weight 2w. The second graph is the resulting graph cut
by red slides (G  ). The last graph is the one cut by the blue dotted slide (G ∗ ).
TABLE IC OMPARING D ISTANCES d1 V ERSUS d2 AND S IMILARITY VALUES s1
V ERSUS s2 . I T S HOWS T HAT G RAPH G ∗ I S U SUALLY M ORE
S IMILAR TO G THAN G  I S

We studied the problem of clustering on graphs by graph cuts.
We showed the conditions that make the clusters not well connected.
We proposed to detect these cases by comparing the resulting
graphs after cut with the original graph using a graph similarity
measure considering global graph connectivity. We proposed thegraph embedding-based graph comparison that first embeds graphs
into Euclidean spaces and then compares the embeddings in thespaces. We showed that the comparison does consider the global
connectivities of graphs, as opposed to edit distance. It was confirmed
by our experiments that the similarity and distance measure canconsistently distinguish between the clustering solutions with disconnected clusters and the ones without disconnected clusters. Studying
more on the relationship between the types of global connectivity
and the ways of embedding would be interesting future work. Our
methods also can be applied to other scenarios such as comparing
biological networks for phylogenetic tree construction.
R EFERENCES

Fig. 2. Normalized cut losses versus the ged distances of many clusteringsolutions with small losses.

We compare distances with the original graph: d1 = ged(G, G  )and d2 = ged(G, G ∗ ). We also show the similarities between the newgraphs to the original one: s1 = ges(G, G  ) and s2 = ges(G, G ∗ ).
The similarities and distances are shown in Table I.
We observed that the distance of G  to G is always greater thanthat of G ∗ to G, i.e., d1 > d2 . Likewise, the similarity of G  to G
is always smaller than that of G ∗ to G, i.e., s1 < s2 . Hence, graphs
G ∗ are consistently more similar to G than G  to G. It means thatthe graphs with disconnected clusters are farther than the graphs withconnected clusters. This shows that as the graphs G ∗ have connectedclusters, they tend to be more similar to the original graph G. We
conclude that our similarity measure and its induced distance candetect the good clustering solutions while the loss functions in (1)cannot.
We also show the effectiveness of the ged distance on a real
network of Zachary’s karate club2 in Fig. 2. We show the distanceagainst the normalized cut loss function for different clustering
2 www-personal.umich.edu/∼mejn/netdata/[1] A. Banerjee, S. Merugu, I. S. Dhillon, and J. Ghosh, “Clustering with
Bregman divergences,” J. Mach. Learn. Res., vol. 6, pp. 1705–1749,
Dec. 2005.
[2] Y. Boykov and O. Veksler, Graph Cuts in Vision and Graphics: Theories
and Applications. New York, NY, USA: Springer-Verlag, 2006.
[3] Y. Boykov, O. Veksler, and R. Zabih, “Fast approximate energy minimization via graph cuts,” IEEE Trans. Pattern Anal. Mach. Intell.,vol. 23, no. 11, pp. 1222–1239, Nov. 2001.
[4] T. Bühler and M. Hein, “Spectral clustering based on the graphp-Laplacian,” in Proc. 26th Annu. ICML, 2009, pp. 81–88.
[5] H. Bunke and K. Shearer, “A graph distance metric based on the
maximal common subgraph,” Pattern Recognit. Lett., vol. 19, nos. 3–4,
pp. 255–259, Mar. 1998.
[6] H. Bunke and G. Allerman, “A metric on graphs for structural patternrecognition,” in Proc. 2nd EUSIPCO, 1983, pp. 257–260.
[7] F. R. K. Chung, Spectral Graph Theory. Providence, RI, USA: AMS,
1994.
[8] P. A. V. de Miranda, A. X. Falcão, and J. K. Udupa, “Synergistic arcweight estimation for interactive image segmentation using graphs,”
J. Comput. Vis. Image Understand., vol. 114, no. 1, pp. 85–99,
Jan. 2010.
[9] I. S. Dhillon, Y. Guan, and B. Kulis, “Kernel k-means: Spectral clustering and normalized cuts,” in Proc. 10th ACM SIGKDD Int. Conf. Knowl.
Discovery Data Mining, 2004, pp. 551–556.
[10] C. Ding, X. He, H. Zha, M. Gu, and H. D. Simon, “A minmaxcut spectral
method for data clustering and graph partitioning,” Lawrence Berkeley
Nat. Lab., Berkeley, CA, USA, Tech. Rep. 54111, 2003.
[11] F. Fouss, A. Pirotte, J.-M. Renders, and M. Saerens, “Random-walkcomputation of similarities between nodes of a graph with application tocollaborative recommendation,” IEEE Trans. Knowl. Data Eng., vol. 19,
no. 3, pp. 355–369, Mar. 2007.
[12] T. Gärtner, P. A. Flach, and S. Wrobel, “On graph kernels: Hardness
results and efficient alternatives,” in Proc. 16th Annu. Conf. Comput.
Learn. Theory 7th Kernel Workshop, 2003, pp. 129–143.
[13] A. Gretton, O. Bousquet, A. J. Smola, and B. Schölkopf, “Measuring
statistical dependence with Hilbert-Schmidt norms,” in Proc. 16th Int.
Conf. Algorithmic Learn. Theory, 2005, pp. 63–77.
[14] I. Gutman and W. Xiao, “Generalized inverse of the Laplacian matrix andsome applications,” Bull., Classe des Sci. Math. et Natturalles, vol. 129,
no. 29, pp. 15–23, 2004.
[15] L. W. Hagen and A. B. Kahng, “Fast spectral methods for ratio cut
partitioning and clustering,” in Proc. IEEE/ACM Int. Conf. Comput.
Aided Design, Nov. 1991, pp. 10–13.

1412

IEEE TRANSACTIONS ON NEURAL NETWORKS AND LEARNING SYSTEMS, VOL. 25, NO. 7, JULY 2014[16] H. Kashima, K. Tsuda, and A. Inokuchi, “Marginalized kernels between
labeled graphs,” in Proc. 20th ICML, 2003, pp. 321–328.
[17] D. J. Klein and M. Randic, “Resistance distance,” J. Math. Chem.,
vol. 12, no. 1, pp. 81–95, 1993.
[18] C. D. Meyer, “Generalized inversion of modified matrices,” SIAM J.
Appl. Math., vol. 24, pp. 315–323, May 1973.
[19] P. A. Miranda and A. X. Falcão, “Links between image segmentation
based on optimum-path forest and minimum cut in graph,” J. Math.
Imag. Vis., vol. 35, no. 2, pp. 128–142, Oct. 2009.
[20] B. Nadler and M. Galun, “Fundamental limitations of spectral clustering,” in Proc. Adv. NIPS, 2007, pp. 1017–1024.

[21] J. Shi and J. Malik, “Normalized cuts and image segmentation,”
IEEE Trans. Pattern Anal. Mach. Intell., vol. 22, no. 8, pp. 888–905,
Aug. 2000.
[22] A. J. Smola and R. I. Kondor, “Kernels and regularization on graphs,”
in Proc. 18th Annu. Conf. Learn. Theory, 2003, pp. 144–158.
[23] N. Wicker, C. H. Nguyen, and H. Mamitsuka, “A new dissimilarity
measure for labeled graphs,” Linear Algebra Appl., vol. 438, no. 5,
pp. 2331—2338, Mar. 2013.
[24] R. C. Wilson, E. R. Hancock, and B. Luo, “Pattern vectors from algebraic
graph theory,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 27, no. 7,
pp. 1112–1124, Jul. 2005.