A Graduated Assignment Algorithm for Graph Matching.
AbstractA graduated assignment algorithm for graph matching is presented which is fast and accurate even in the presence of high noise. By combining graduated nonconvexity, two-way (assignment) constraints, and sparsity, large improvements in accuracy and speed are achieved. Its low order computational complexity [O(lm), where l and m are the number of links in the two graphs] and robustness in the presence of noise offer advantages over traditional combinatorial approaches. The algorithm, not restricted to any special class of graph, is applied to subgraph isomorphism, weighted graph matching, and attributed relational graph matching. To illustrate the performance of the algorithm, attributed relational graphs derived from objects are matched. Then, results from twenty-five thousand experiments conducted on 100 node random graphs of varying types (graphs with only zero-one links, weighted graphs, and graphs with node attributes and multiple link types) are reported. No comparable results have been reported by any other graph matching algorithm before in the research literature. Twenty-five hundred control experiments are conducted using a relaxation labeling algorithm and large improvements in accuracy are demonstrated.
Introduction
The process of approximately matching two abstract representations lies at the heart
of the development of artificial systems with human-like abilities such as vision. Con-
sequently, within the field of Computer Vision it has been the focus of much research.
Many algorithms for matching sets of features, such as points or line segments derived
from two images have been explored. One approach has been to represent the
images or objects in the form of graphs. A weighted graph may be used to formulate
a structural description of an object [1]. Such descriptions can be further enhanced
with parametric information and represented by attributed relational graphs (ARGs)
[2].
Because of the representational power of graphs, much effort has gone into the
development of efficient algorithms which can effectively match graphs. Two main
approaches have been tried. One approach involves the construction of a state-space
which is then searched with techniques similar to the branch and bound methods
employed in operations research [3]. These algorithms are of exponential time worst-case
complexity. However the assumption is made, that with the help of heuristics,
the size of each level of the resulting state-space search tree will be reduced to a low
order polynomial (as a function of the number of nodes of the graphs) [4]. However
even under these assumptions, the algorithm typically has a high-order polynomial
complexity. For example the method in [5], is approximately O(l 3
(where l and m are the number of links in the two graphs), though special instances
are faster.
The second approach employs nonlinear optimization methods (or heuristic approximations
thereof). The most successful of these methods use some form of relaxation
labeling [6, 7, 8, 9, 10, 11, 12, 13]. Relaxation labeling algorithms do not
search the state-space and generally have a much lower computational complexity
(O(lm) or perhaps even lower-see [10]) than tree search methods. Other nonlinear
optimization approaches are neural networks, [14, 15, 16, 17, 18, 19, 20, 21], linear
programming [22], symmetric polynomial transform [22], eigendecomposition [23], genetic
algorithms [24] and Lagrangian relaxation [25]. These techniques have so far
met with mixed results suffering from either speed or accuracy problems and have
often only been tried on the much easier problem of matching graphs with equal
number of nodes (though Young et al [19], Chen and Lin [20] and Suganthan et al
[21] work on graphs of unequal size and offer some other enhancements).
Our graduated assignment method falls under the rubric of nonlinear optimization.
Like relaxation labeling, it does not search a state-space and has a low order computational
complexity [O(lm)]. It differs from relaxation labeling in two major ways. The
softassign, incorporating a method discovered by Sinkhorn [26] is employed here to
satisfy two-way (assignment) constraints. Assignment constraints require the nodes of
both graphs to be equally constrained. A node in one graph can match to at most one
node in the other graph and vice versa. Relaxation labeling, a tool for classification,
only enforces a one-way constraint. Ton and Jain [10] use this concept of two-way
matching, but their technique is not guaranteed to satisfy the constraints, while the
softassign is [26, 27, 28]. Second, a continuation method-graduated non-convexity-
is used in an effort to avoid poor local minima [29, 30, 31, 32, 33], with a parameter
controlling the convexity. These two ideas are combined with a third-sparsity-an
old technique that has appeared within the relaxation labeling framework [34], which
is explicitly encoded to increase efficiency. The softassign, graduated non-convexity
and sparsity form the key components of our new algorithm.
Some of these elements have been explored before in graph matching algorithms.
briefly mentions trying to use a graduated non-convexity approach within the
relaxation labeling framework with some success. However he still uses the standard
one-way constraint of relaxation labeling. Chen and Lin [20] and Suganthan et al [21]
use a continuation method (deterministic annealing). They also try to enforce two-way
constraints, but via a penalty function-a method of constraint satisfaction that
has met with poor results in related combinatorial optimization problems [35, 36, 37].
We took the first steps towards the development of this algorithm by applying the
graduated assignment technique to a parametric assignment problem-point matching
(with point sets of equal in [38]. This was extended to points sets of unequal
size in [39, 40]. The method was first applied to graph matching (graphs of equal
in [40, 28]. However, because the graph matching objective used in [40, 28] was
originally designed for graphs with equal number of nodes [25] it could not handle
the much more interesting cases of graphs with missing and extra nodes and missing
and extra links. Moreover another difference is the novel and explicit encoding of
sparsity.
The graduated assignment technique is a specialized method of efficiently finding
good suboptimal solutions for certain types of optimization problems-those that can
use a match matrix to explicitly denote an assignment (correspondence) between one
set of objects and another. These objects may, for example, be sets of points located
in space, or nodes of a graph. The match matrix is a 0-1 matrix with 1's denoting that
a given object in one set is assigned to (corresponds to) a given object in the other set.
The rows and columns of this matrix add up to one, and in the case where the two sets
of objects are equal in size the match matrix is a permutation matrix. Graduated-
non-convexity [29] is used to turn these discrete variables into continuous ones in
order to reduce the chances of getting trapped in local minima. The technique is an
iterative one, where at each step, an estimate is made of the match matrix and then
the softassign (incorporating repeated row and column normalizations) [26] is used
to ensure that the match matrix remains the continuous analog of a true assignment
(all the rows and columns add up to one). A control parameter may be adjusted
at each step to slowly move the matrix closer to 0-1 values. The method has been
applied to assignment [27], parametric assignment [38, 39], and quadratic assignment
[40, 28] problems. The technique bears a close relationship to deterministic annealing
methods used in statistical physics that are now being applied to neural networks
Several experiments on graphs derived from real images were conducted to illustrate
the performance of the algorithm. Additionally over twenty-five thousand experiments
were conducted on randomly generated one-hundred node graphs of different
types (zero-one links, weighted links, weighted links and node attributes) under varying
degrees of noise. Because of both the speed of the algorithm and the advances in
computer technology (Indigo SGI workstations with the R4400 processor were used)
such large scale testing of a graph matching algorithm is for the first time possible.
previous results of this order have ever before been reported. We also ran about
twenty-five hundred control experiments using a relaxation labeling algorithm in order
to serve as a benchmark for our studies. Order of magnitude differences in accuracy
and speed are reported against this benchmark.
2 The Graduated Assignment Algorithm
2.1 Problem Definition
The graduated assignment algorithm will be described using the case of weighted
graph matching. We define the problem of weighted graph matching in the following
manner. Given two undirected graphs G and g which may be sparse and whose links
may take values in R 1 , find the match matrix M such that the following objective
function is minimized.
I
A
I
subject to 8a
I
1g.
Graphs G and g have A and I nodes respectively. fC aibj g is defined by:
ab or g ij is NULL
(2)
ab g and fg ij g are the adjacency matrices of the graphs, whose elements may be in
R 1 or NULL. These matrices are symmetric with NULL elements along the diagonal.
G ab is the weight of the link between nodes a and b of graph G. The matrix M
indicates which nodes in the two graphs
1 if node a in G corresponds to node i in g
The function c(\Delta; \Delta) is chosen as a measure of compatibility between the links of the
two graphs. This function is similar to the compatibility functions used within the
relaxation labeling framework [34, 11, 12]. By explicitly defining C to be 0 when a
link is missing (NULL) we are ensuring that C will also be sparse when the graphs
are sparse.
2.2 Intractability
The weighted graph matching problem, as formulated in the previous section, is NP-complete
for many definitions of the function c(\Delta; \Delta). On randomly generated graphs
c is defined as: c(G ab . The function c is so chosen, in order
to yield an expected value of zero when the link weights are randomly selected from
a uniform distribution in the interval [0; 1] as was the case in our experiments. The
expected value will be zero, because two points chosen from a uniform distribution
in the unit interval will be on average 1units apart.
When c is defined in the above manner, the weighted graph matching problem
contains the largest common subgraph problem [43] as a special case. That is, if the
links 2 f1; NULLg then the above objective (1) is equivalent to [44, 15]:
A
I
A
I
since c(1; using (2). A graph h is the largest common subgraph of graphs
ab
G
a
c d
l

Figure

1: Rectangle rule for subgraph isomorphism
G and g if and only if the minimum value of (3) is equal to the number of edges
in h. This can also be seen by applying the rectangle rule (Figure 1) of subgraph
isomorphism. When all the elements in (3) are restricted to zero or one, then all four
elements must be on for a match to occur, forming a rectangle. Therefore, finding the
minimum of (3) becomes equivalent to finding the maximum number of rectangles
which, in turn, is equivalent to finding the maximum number of matching links in the
two graphs, also known as the largest common subgraph problem. Since the largest
common subgraph problem is NP-complete [43] and it is a special case of our weighted
graph matching problem, the weighted graph matching problem is also NP-complete
(with the c function defined as above). Since we are dealing with an NP-complete
problem we must look for good suboptimal (approximate) solutions. (The preceding
is a simplification, since it ignores some technical distinctions between NP-complete
and NP-hard problems).
Note, that if fG ab if and only if the minimum of (3) is
equal to the number of edges in G since c(G ab
2.3 Graduated Assignment
The major problem we must tackle in finding good suboptimal solutions to the
weighted graph matching objective is two-way constraint satisfaction, i.e. the row
and column constraints on the match matrix (Figure 2).
A
A
A
R
I

Figure

2: The match matrix, M
To simplify the development, let us ignore the inequality constraints (ignore for the
moment the slacks in Figure 2) on the rows and columns. Therefore, the constraints
state that our match matrix must be a permutation matrix. permutation matrix
is a square zero-one matrix whose rows and columns add up to one.) We now use
continuation methods [29, 30, 31, 32] to turn our discrete problem into a continuous
one in order to reduce the chances of getting trapped in local minima. A continuation
method consists of minimizing a series of objective functions indexed by a control
parameter. As the parameter is increased the solution to the objective functions
approach that of the discrete problem.
First, we will examine the case where there is only one constraint. Imagine a
subproblem (within a larger problem) whose objective is to find the maximum element
within a set of numbers. That is, we are given a set of variables fX i g where X i
Then, we associate a variable m with each X i , such that
I
Our
is:
is the maximum number in fX i g
which is equivalent to finding fm i g which maximize
I
This discrete problem
may now be formulated as a continuous problem by introducing a control parameter
setting m as follows [32, 45] :
I
This is known as the softmax [46]. The exponentiation used within the softmax has
the effect of ensuring that all the elements of fm i g are positive. It is easily shown that
as fi is increased in the above, the m i corresponding to the maximum X i approaches
1 while all the other m i approach 0 (except in special cases of ties). In the limit as
fi !1, the m i corresponding to the maximum will equal 1 while all the other m i will
equal Therefore an algorithm using a continuation method to enforce a constraint
which selects the maximum among a group of elements could have the following form:
Initialize fi to fi 0
Begin A: (Do A until (fi - fi f
I
Do rest of algorithm - (fX i g may be updated) .
Increase fi
End A
However, in our problem we have a two-way constraint: A node in graph G must
correspond to only one node in graph g and vice versa. Fortunately, these two constraints
can be satisfied using a remarkable result due to Sinkhorn [26]. In [26], it
is proven that any square matrix whose elements are all positive will converge to a
doubly stochastic matrix just by the iterative process of alternatively normalizing the
rows and columns. doubly stochastic matrix is a matrix whose elements are all
positive and whose rows and columns all add up to one - it may roughly be thought
of as the continuous analog of a permutation matrix). Imagine a subproblem (within
a larger problem) whose objective is to find the best (maximum) assignment given
a square benefit matrix of numbers. That is, we are given a set of variables fX ai g
where X ai 2 R 1 . Then we associate a variable M ai 2 f0; 1g with each X ai , such
that 8a
I
Our aim is to find the matrix M (a
permutation matrix) which maximizes the following:
A
I
This is known as the assignment problem, a classic problem in combinatorial optimization
[47]. Therefore an algorithm using a continuation method to enforce a
two-way constraint which selects the maximum assignment among a group of elements
could have the following form:
Initialize fi to fi 0
Update M by normalizing across all rows:
I
Update M by normalizing across all columns:
Do rest of algorithm - (fX ai g may be updated) .
Increase fi
End A
Note that the exponentiation used by the continuation method has the effect of
ensuring that all the elements of the match matrix are positive before Sinkhorn's
method is applied. Just such an algorithm was used in [27] to exactly solve the
assignment problem (the global maximum is found). However, the weighted graph
matching problem we are trying to solve is much harder than the assignment problem
- it is similar to a quadratic assignment problem which is NP-complete [43] as opposed
to the assignment problem which can be solved in polynomial time [48]. Since
we have already described a method to solve the assignment problem, we will find
an approximate solution to our quadratic assignment problem by using a continuation
method to solve a succession of assignment problems. For each assignment the
continuation method returns the corresponding globally optimal doubly stochastic
matrix for the current value of the control parameter [27]. Since a doubly stochastic
matrix (and not a permutation matrix) is returned for each assignment problem at
the current value of the control parameter we term this a softassign.
Recall from (1) that our quadratic graph matching problem corresponds to the
minimization of the objective \Gamma 1P A
I
I
Given an initial
condition M 0 , the objective can be expanded about this initial condition via a Taylor
series approximation:
\Gamma2
A
I
A
I
A
I
A
I
A
I
where
A
I
Now minimizing the Taylor series expansion is equivalent to maximizing
A
I
An assignment problem! So our general procedure is: Start with some valid initial
value for M . Do a first order Taylor series expansion, taking the partial derivative.
Find the softassign corresponding to the current assignment. Take the resulting
substitute back in (4) and repeat. As we iterate we slowly increase our control
parameter fi. In the initial stages of our algorithm, when fi is small, the difference
between the current value of M ai and the previous value of M ai (i.e. M
will be small. Therefore the remainder of our Taylor series expansion will be small,
and our approximation via the Taylor series expansion will be good. Then after the
critical initial stages of our algorithm, when fi becomes large the softassign will push
the algorithm towards integer solutions.
One last detail needs to be resolved. The constraints on M are inequality con-
straints, not equality constraints. Therefore, we transform the inequality constraints
into equality constraints by introducing slack variables, a standard technique from
linear programming [49];
8a
I
and likewise for our column constraints. An extra row and column are added to the
matrix M to hold the slack variables (Figure 2). (This augmented matrix is denoted
by -
.) By incorporating slack variables, the graph matching algorithm can handle
outliers (spurious or missing nodes or links) in a statistically robust manner [50].
2.4 The Algorithm
The pseudo-code for the inexact graph matching algorithm is as follows (using the
variables and constants defined
Initialize fi to fi 0 , -
M ai to (1
Begin B: (Do B until M converges or # of iterations ? I 0 )
Begin C: (Do C until -
M converges or # of iterations ? I 1 )
Update -
M by normalizing across all rows:
Update -
M by normalizing across all columns:
End C
End A
Perform
Variable and constant definitions can be found in Table 1.
control parameter of the continuation method
initial value of the control parameter fi
maximum value of the control parameter fi
r rate at which the control parameter fi is increased
Ewg graph matching objective, equation (1)
match matrix variables
match matrix variables including the slacks (see Figure 2)
partial derivative of Ewg with respect to M ai
I 0 maximum # of iterations allowed at each value of the control parameter, fi
I 1 maximum # of iterations allowed for Sinkhorn's method
(back and forth row and column normalizations)

Table

1: Variable and constant definitions for the graduated assignment algorithm
A clean-up heuristic is necessary because the algorithm does not always converge
to a permutation matrix. For the experiments in this paper, we used a very simple
heuristic - we just set the maximum element in each column to 1 and all others
to 0. This heuristic will always return a permutation matrix from a row dominant
doubly stochastic matrix (the maximum element in each row occurs in a different
column), which was what the algorithm often returned, when a good solution was
found. However, it is not guaranteed to return a permutation matrix and better and
more sophisticated heuristics could be used. For example, we could as the final step
solve the assignment problem exactly, instead of just executing a softassign. (The
preceding discussion ignores the effect of the slack variables. The augmented match
matrix can never actually be a permutation matrix, however if the rows and columns
whose slacks variables are turned on-representing spurious or missing nodes-are
removed, a permutation matrix can be derived.)
For the experiments conducted in Section 3.2 on random 100 node graphs the
following values for the constants were used:
and I 30. The values of fi were chosen so that the elements of the match
matrix M would all be roughly of equal size after the initial temperature, and all be
close to either zero or one at the final temperature. The criterion for convergence
was:
A
I
In step B, In step C,

Figure

3 provides an overview of the algorithm.
exit upon
convergence
Softassign
aibj
Row Normalization
S a
Col. Normalization

Figure

3: Left: Overview of the graduated assignment graph matching algorithm.
fC aibj g is a sparse matrix containing similarity measures between the links of the two
graphs and M ai is the match matrix. Right: Softassign.
The stopping criterion in step C of the algorithm is a test for convergence as well
as a check to see if the maximum number of iterations have been exceeded. This is
more efficient because in practice it's unnecessary to always have an exactly doubly
stochastic matrix-something close to one works well also. With a stopping criterion
of one or one-half an iteration, the extreme version, we effectively obtain the one-way
constraint which does not work as well, but still works to a degree. However step C
is only O(np) (n and p are the number of nodes in the two graphs) as opposed to
O(lm) for the entire algorithm (l and m are the number of links in the two graphs),
so only in the case where the graphs are extremely sparse does the tradeoff between
number of iterations and accuracy here become an issue.
The O(lm) complexity follows from the fact that we have defined C to be 0 in the
case where a link is missing in either of the graphs. That bound may then be derived
since the number of iterations on all three loops of the algorithm are bounded by
constants, i.e. I 1 , I 0 and (log fi f \Gamma log fi 0 )= log fi r (from fi
When implementing this algorithm on graphs that are not fully connected, a sparse
data structure is essential to exploit the O(lm) computational complexity. While
working with large graphs (over 100 nodes) it is also advisable not to precompute the
compatibility coefficient, C aibj but to simply keep the two sets of links of the graphs
as sparse structures and recompute C aibj when needed, since C aibj can rapidly grow in
size. For example, two 200 node undirected graphs with 10% connectivity would need
a million element list of floating point numbers along with associated bookkeeping in
memory which can be a resource drain even with today's workstations. The increased
computation required is comparatively minor.
Also, when operating on undirected graphs it is important to take advantage of
symmetry. This can result in a speed-up factor of 4 since we have half as many links
in both graphs [! ( l)( m)]. Note for all the experiments described in this paper, this
technique was not implemented. Therefore all the execution times reported could be
improved with a minor modification.
2.5 Attributed Relational Graph Matching
The graduated assignment graph matching algorithm detailed in the preceding section
can handle attributed relational graphs (ARGs) by simply modifying Ewg in (1).
Attributed relational graphs are graphs whose nodes may be assigned values, called
attributes. Additionally such graphs may have multiple link types (relations) as well
as multiple attribute types [1, 2, 51]. We modify Ewg to handle ARGs in the following
manner:
A
I
A
I
R
A
I
where R is the number of link types and S is the number of attributes.
We omit a detailed description of the above objective which can be used to match
graphs with multiple link types and multiple attributes. For a fuller exposition of the
construction and use of graphs with multiple relations, attributes, and compatibility
functions see [11]. We demonstrate how the algorithm can be applied to more complex
graphs with another example. Suppose the weighted graph of the previous section
now has a single attribute. The objective function becomes:
I
A
I
A
I
The parameter ff indicates how much weight to give the attribute values and is
problem dependent. C (2)
aibj is defined in an identical manner to C aibj in (1). C (1)
ai is
defined by:
fG a g and fg i g are vectors corresponding to the nodes of the graphs, whose elements
may be in R 1 or NULL. Since there can be at most AI node attributes, we ignore
sparsity and do not explicitly define a zero value for the NULL cases. The only
difference between using the above objective (6) and the weighted graph matching
objective (1) in our algorithm is the addition of ffC (1)
ai to the Q ai term. Moreover none
of the reasoning used in the algorithm derivation is affected by the additional ff term.
The extension to attributed relational graphs as outlined above is straightforward,
though tedious.
2.6 Constructing an Objective with Constraints
The dynamics of the algorithm may also be motivated by taking the objective func-
tions, (1), (5), or (6), described above and adding an x log x smoothing function
and Lagrange multipliers to enforce the constraints. In the case of weighted graph
matching (1), the objective becomes:
A
I
A
I
A
- a (
I
In the above we are looking for a saddle point by minimizing with respect to M
and maximizing with respect to - and -, the Lagrange multipliers.
The x log x term is a smoothing function (also called an entropy term in statistical
physics), which serves to push the minimum of the objective away from the discrete
points. It convexifies the objective, with the parameter fi controlling the degree of
convexity. It is different from a barrier function, because it does not favor points in
the interior of the feasible set over those near the boundary [52].
Other smoothing functions may perform just as well, however (7) can be derived
using techniques from statistical physics which have been applied to other combinatorial
optimization problems [53, 41, 42, 32]. Yuille and Kosowsky [41] used a gradient
projection method to minimize an objective similar to (7) arising from TSP like problems
but such methods are typically quite slow. Peterson and Soderberg [32] and Van
der Bout and Miller [42] minimize an objective similar to (7) for graph partitioning
and TSP. They use a synchronous updating technique, where the values of a set of
variables are held fixed and updated simultaneously, and Peterson and Soderberg
show this technique has good convergence properties. Graduated assignment graph
matching uses a similar technique; the match variables, fM ai g, are updated simulta-
neously. However Peterson and Soderberg and Van der Bout and Miller enforce one
constraint via a softmax (and the other constraint via a penalty function). Graduated
assignment enforces both sets of constraints via softassign.
The dynamics of the graduated assignment algorithm are also similar to the
expectation-maximization (EM) algorithm when used within deterministic anneal-
ing, though EM also enforces just one constraint [54, 55].
3 Experimental Results
Several different types of experiments were conducted using the graduated assignment
algorithm. First, we repeated an experiment with attributed relational graphs
first constructed by Eshera and Fu [51] who used a tree-search method to perform
the matching. Second, we hand designed attributed relational graphs from real images
and matched them. Third, we generated tens of thousands of random graphs
of different types (zero-one graphs, weighted graphs, weighted graphs with binary
attributes) and tested them under varying conditions of noise. Finally, we ran a
relaxation labeling algorithm as a control for the above experiments on randomly
generated graphs.
3.1 Graphs from Images

Figure

4: Graphical representation of a wrench (model).
In [51], an image understanding system was developed using attributed relational
graphs as a way of representing object models or scenes. A state-space search algorithm
is described in [5] with a computational complexity of approximately O(l 3 m 2 ).
In one experiment outlined in [51], attributed relational graph matching was used to
locate an object within a multiobject scene. ARGs were produced from real images
using a multilayer graph transducer scheme. An ARG produced from an image of
a wrench (the model) was matched against an ARG produced from an image of a
number of overlapping objects which included the wrench (the scene). These graphs
are depicted in Figures 4 and 5. The multiple attributes on the nodes were line segment
length, arc segment length, arc segment span and contour length. The multiple
link types were joint, intersection and facing features. Figures 4 and 5 simply show
the pattern of connectivity of the two graphs, (they are clearly sparse) without the
attribute and link values. The nodes in Figure 5 that match to Figure 4 are high-
lighted. Because of the noise associated with the image processing, the corresponding
link and attribute values in the two graphs do not match exactly. We ran our graduated
assignment algorithm against these two sparse graphs consisting of 7 and 27
nodes respectively, with all the attribute and link values exactly as reported in [51],
but normalized to one, over the maximum value for each link and attribute type. The
algorithm returned a match matrix with the 100% correct assignment between the
two graphs using the compatibility functions outlined previously. Running time on

Figure

5: Graphical representation of a scene with a number of overlapping machine
parts.
an SGI Indigo workstation with an R4400 processor was under a second.
In the second experiment, we hand designed graphs from two real images, Figure
6 representing a model, and Figure 7 representing the scene in which we wish to
locate the model. We assumed a low-level image processing sub-system capable of
edge detection and curve grouping. Five curves were created for Figure 6 and thirteen
curves for Figure 7 (curves are not shown). Three types of features were then marked
for points on these curves, corresponding to whether they were points on straight
lines, curved lines or at discontinuities (break points) such as the end of the curve
or at an inflection point. The feature points marked in this manner are represented
by triangles, circles and squares respectively in Figures 6 and 7. 28 (model) and 84
(scene) feature points were produced in the two images. Attributed relational graphs
were then created from these sets of features in the following manner. Two graphs
were created with 28 and 84 nodes each. Each node had three binary valued attribute
types, corresponding to straight line, curved line or break point features. So the node
corresponding to a straight line would have its straight line attribute set to 1 and its
curved line and break point attributes set to 0. Then three different link types between

Figure

Image of coffee cup model with features hand labeled

Figure

7: Image of a table top scene with features hand labeled
nodes within a graph were created. The first link type was binary valued and set to 1
between any two nodes corresponding to feature points on the same curve. Between
any two nodes not on the same curve its value was NULL. The second link type was
binary valued and set to 1 only if two nodes were neighbors on the same curve. In all
other cases it was set to NULL. Finally, the third link type was set to the Euclidean
distance between any two feature points if its distance was - :2, NULL otherwise.
(The images were normalized over the unit square). Consequently, only nodes that
were relatively close in location had a link of the third type. Note that the sets of
links corresponding to all three link types were sparse. The graduated assignment
algorithm returned a match matrix with the 100% correct assignment between the two
graphs using the compatibility functions outlined previously. Notice the difference in
scale between the coffee cup in the model and the scene (approximately 1:3). Running
time on an SGI Indigo workstation was about seconds.
3.2 Randomly Generated Graphs
In all the experiments on randomly generated graphs, the following protocol was used.
A random 100 node graph of the appropriate type was generated. The nodes of the
graph were randomly permuted. Noise of various forms was added to the permuted
graph i.e. nodes were deleted, links were deleted or added, link weights were modified
or node attributes were modified. The graduated assignment algorithm was then
run on the two graphs (the original 100 node graph and the permuted graph). The
resulting assignment returned by the algorithm was then compared to the correct
assignment. The correct and incorrect matches were recorded and these numbers are
reported on all the succeeding figures. Only the correctness of the assignment of the
nodes in the permuted graph was considered. That is if the permuted graph had 40
nodes and matched correctly then we recorded
matches and reported 25% incorrect. Note this method only gives a lower bound on
the percent correct matches (since it can ignore good matches that don't correspond
to the original graph).
First, subgraph isomorphism was tested as shown in Figure 8. Links in these
graphs could only have a value equal to 1. Graphs were generated with 4, 8, 12,
16, 20, 24, and 28 percent connectivity. A connectivity of 4% meant that two nodes
would be connected with a probability of :04. The permuted graphs had either 2,
10, 20, or 30 percent of their nodes deleted. For each type of graph generated (i.e.
for a specific connectivity and size) 100 trials were run with 100 different randomly
Percent Connectivity
Percent
Incorrect
Matches
2%
10%
20%
30%

Figure

8: Subgraph isomorphism. Graphs of various sizes and connectivity run
against 100 node graphs. 700 trials per line. 2% (deleted), 10%, 20%, and 30% are
98, 90, 80,and 70 node graphs respectively.
generated graphs. So, for example, for 10% deleted nodes and 16% connectivity, 100
trials were run with each trial generated in the following way. A 100 node graph was
randomly generated with 16% connectivity. It was randomly permuted. 10% of its
nodes were deleted. Then the graduated assignment algorithm was used to match the
resulting 90 node graph to the original 100 node graph. The percent correct matches
were recorded. Then the total percent incorrect nodes over all 100 trials was plotted
as a point in Figure 8. From the plot we can see that less than 1% percent of the
nodes over 100 trials at (16% connectivity, 10% deleted) were mislabeled. Contrast
these results with related attempts to handle subgraph isomorphism with non-linear
optimization methods such as relaxation labeling which failed completely on this
problem (next section). Also see Simic [17] who could not reliably find matches for
all connectivities less than 30% in 75 node random graphs using a neural network
approach on the much easier problem of graph isomorphism (equal size graphs). We
ran 2800 experiments with subgraph isomorphism.
The second set of experiments were performed on weighted graphs (Figure 9). Link
weights were randomly chosen from a uniform distribution in the interval [0; 1]. Four
Percent Noise
Percent
Incorrect
Matches
Percent Noise
Percent
Incorrect
Matches
a
c
d
a
c
d

Figure

9: Weighted graph matching. Weighted graphs of various sizes and connectivity
run against 100 node graphs. 600 trials per line. Left - no deleted or spurious
links. Right - links 5% spurious, 5% deleted. (a) 40% deleted (60 node graph), 15%
connectivity. (b) 40% deleted, 10% connectivity. (c) 60% deleted, 15% connectivity.
(d) 60% deleted, 10% connectivity.
different types of graphs were generated, two at 40% deleted (a 60 node graph) with
10% or 15% connectivity, and two at 60% deleted (a 40 node graph) with 10% or
15% connectivity. Then uniform noise was added to the link weights. Trials were
conducted at 0, .02, .04, .06, .08, .1 standard deviations. 100 trials were run at each
standard deviation for each type of graph. The results of these experiments are plotted
on the left in Figure 9. On the right, the same experiments were rerun, but in addition,
links deleted or added. After the graphs were created, there was a .05 probability
that any link could be deleted. If c p was the connectivity probability, c p 2 f:10; :15g,
then there was a :05c p probability that a spurious link could be added between any
two nodes. The noise rate, :05 is multiplied by the connectivity to ensure that the
resulting graph remains sparse, despite the addition of spurious links. Contrast the
results reported here with other methods such as relaxation labeling which did very
poorly on this problem (next section). Also see the experiments of Almohamad
and Duffuaa (linear programming and symmetric polynomial transform) [22] and
Umeyama (eigendecomposition) [23] which were all conducted on fully connected
weighted graphs of equal nodes. Our experiments are conducted
on sparsely connected graphs 10 times as large and with large differences in size (60
node graphs are successfully matched against 100 node graphs). 4800 experiments
were conducted on weighted graphs.
Percent Noise
Percent
Incorrect
Matches
Percent Noise
Percent
Incorrect
Matches
a
a
c
c
d
d

Figure

10: Attributed relational graph matching. ARGs (10% connectivity,one
link type) of various sizes and number of binary attributes run against 100 node
graphs. 1100 trials per line. Left - no deleted or spurious links, no attributes mis-
labeled. Right - links 5% spurious, 5% deleted, 5% attributes mislabeled. (a) 60%
deleted (40 node graph), 5 binary attributes. (b) 60% deleted, 3 binary attributes.
(c) 80% deleted, 5 binary attributes. (d) 80% deleted, 3 binary attributes.
Our last series of experiments were conducted with attributed relational graphs

Figures

and 11). All graphs had either 3 or 5 binary valued attributes, i.e. all
attribute values were restricted to 0 or 1. The attributes were set equal to 1 with a
probability of 1
5g, is the number of attributes. All link values were
selected from a uniform distribution over the unit interval. The graphs in Figure

Figure

had one and two link types respectively. All graphs had 10%
connectivity. Experiments were run on graphs with 60% and 80% deleted nodes.
As in the weighted graph matching experiments uniform noise was added to the
links. Trials were conducted at f0, .02, .04, .06, .08, .1, .12, .14, .16, .18, .2g standard
deviations. 100 trials were run at each standard deviation for each type of graph. Also,
Percent Noise
Percent
Incorrect
Matches
Percent Noise
Percent
Incorrect
Matches
a a
c
c
d
d

Figure

Attributed relational graph matching. ARGs (10% connectivity,two
link types) of various sizes and number of binary attributes run against 100 node
graphs. 1100 trials per line. Left - no deleted or spurious links, no attributes mis-
labeled. Right - links 5% spurious, 5% deleted, 5% attributes mislabeled. (a) 60%
deleted (40 node graph), 5 binary attributes. (b) 60% deleted, 3 binary attributes.
(c) 80% deleted, 5 binary attributes. (d) 80% deleted, 3 binary attributes.
the plots on the right in Figures 10 and 11 had links deleted and spurious links added
with a probability of .05 as described in the weighted graph matching experiments. In
addition, in the plots on the right, attributes were mislabeled with a probability of .05.
As can be seen from these experiments, the addition of attribute information greatly
increases the ease with which the graphs can be matched. Addition of a second type
of link makes the matching process even easier. Under these conditions, with multiple
attributes and multiple links, even 20 node graphs can be matched to 100 node graphs
under conditions of high noise - see right hand plot of Figure 11. Related results (i.e.
the importance of attribute [unary] information) have also been reported within the
relaxation labeling framework [12]. The difference in performance between graduated
assignment and relaxation labeling is still large (next section). 17600 experiments
were run with attributed relational graphs. Running times for the experiments in
this section range between 20 seconds and 2 minutes on a SGI Indigo workstation
except for some of the subgraph isomorphism experiments involving graphs of higher
connectivity.
3.3 Comparisons to Relaxation Labeling
Percent Connectivity
Perent
Incorrect
Matches RL
GA

Figure

12: Comparison between graduated assignment and relaxation labeling on
subgraph isomorphism. 90 node graphs of varying connectivity run against 100 node
graphs. GA - 700 trials. RL - 70 trials
Percent Noise
Perent
Incorrect
Matches RL
GA

Figure

13: Comparison between graduated assignment and relaxation labeling on
weighted graph matching. 60 node graphs, 15% connectivity, 5% deleted links, 5%
spurious links run against 100 node graphs. GA - 600 trials. RL -
Percent Noise
Perent
Incorrect
Matches
RL
GA

Figure

14: Comparison between graduated assignment and relaxation labeling on
attributed relational graph matching. 40 node graphs, 10% connectivity, 3 binary
features, 5% deleted links, 5% spurious links, 5% attributes mislabeled run against
100 node graphs. GA - 1100 trials. PR - 110 trials
In contrasting graduated assignment with relaxation labeling (RL), note that relaxation
labeling is a tool for classification, also known as labeling. When performing
classification, a one-way constraint is usually more appropriate than an assignment
constraint since typically one would like to be able to assign multiple objects to the
same class i.e. have the same label. Despite these differences, we choose to compare
graduated assignment with relaxation labeling for three reasons. First, they are
both non-linear methods, in contrast to combinatorial approaches to graph matching.
Second, RL appears to be the most successful standard method available for graph
matching, at least, among non-linear methods. Third, because it is a widely known
method it can serve as a useful benchmark for our new approach. (Even if its relative
success can be disputed, being the most widely known non-linear method would
make it a suitable control.) Additionally, because it is widely known, we choose to
contrast our technique with the standard method of relaxation labeling [34] rather
then implement some enhancements such as variants of gradient projection or the
product combination rule [8, 56, 9]. The benchmark is simpler and clearer; possible
variations in implementations of these enhancements can be avoided. More impor-
tantly, while the enhancements offer some improvements over the original method
these improvements are relatively small [57] compared to the enormous differences in
performance between relaxation labeling and graduated assignment as demonstrated
by our experiments. We implement the original method exactly as outlined in [34].
We used compatibility functions identical to those used in the graduated assignment
experiments. All experiments outlined in the above section were repeated in exactly
the same manner, except that only 10 trials were run at each data point, instead of
100. This was partly because relaxation labeling ran between 5 and 15 times slower.
The results were unambiguous. Three representative examples have been directly
plotted against the same graduated assignment experiments so that the contrast can
be clearly seen. In Figure 12 the performance of both algorithms on the subgraph
isomorphism problem can be seen. Ninety node graphs of different connectivities are
matched against 100 node graphs. As is easy to see, relaxation labeling fails completely
on this problem. In fact on all the subgraph isomorphism experiments we ran,
relaxation labeling performed barely better then chance. In Figure 13, we compare
the relative performances on the weighted graph matching problem. Again there is
an enormous difference in performance. Relaxation labeling performs with a slight
improvement but overall quite poor, while graduated assignment performs very well
on this difficult example. Finally, we contrast the results on attributed relational
graph matching (Figure 14). On this problem, relaxation labeling does much better.
However graduated assignment performs almost perfectly even under conditions of
high noise and the gap in performance between the two methods remains very large.
Graphs are representations of flexibility and power perhaps capable of expressing the
large amount of information used by our visual systems to recognize objects. Unfor-
tunately, graph matching is an extremely difficult problem-an intractable one when
exact solutions are required. However, for many intractable problems, good heuristics
have been developed, which yield adequate solutions for many practical instances of
these problems. For example, good heuristics have been developed for the traveling
salesman problem [58]. In contrast, finding good heuristics for graph matching has
proven to be much more difficult. This is not surprising since graph matching is similar
to the quadratic assignment problem of which the traveling salesman problem is
but one special case.
In search of good heuristics, we have developed an optimization technique, graduated
assignment, specifically tailored to the type of objective functions used in graph
matching. A formal relationship can be established between this technique and methods
derived from statistical physics now being applied to neural networks [41, 28].
However, here we have primarily tried to motivate the method without recourse to
sophisticated mathematical techniques, by simply using techniques commonly employed
in well-known continuation methods. Essentially, the new algorithm has been
developed, by combining a method of two-way (assignment) constraint satisfaction-
the softassign, with continuation methods, while paying close attention to sparsity.
Powerful evidence has been provided of the algorithm's performance, including
experimental evidence on a scale never before provided for any graph matching tech-
nique. We have demonstrated that it will work on a problem from the research
literature [51], applied it to graphs from real images, tested it on a wide variety of
graphs under conditions of noise, and benchmarked it against relaxation labeling.
The method is universal-it is applicable to any type of graph. It has low order computational
complexity (O(lm)). And it is accurate-it will work on problems such as
subgraph isomorphism which have proved difficult for non-linear methods. Especially
noteworthy is the stability of our algorithm. Adding large amounts of noise to the
link weights and deleting or adding nodes or links will only cause gradual degradation
in performance. Graduated assignment graph matching holds enormous promise.

Acknowledgements

We thank Eric Mjolsness for his encouragement and support. We thank Suguna
Pappu and Manisha Ranade for assistance in preparing this manuscript. This work
was supported by ONR/DARPA grant N00014-92-J-4048 and the Yale Neuroengineering
and Neuroscience Center.



--R

"Structural descriptions and inexact match- ing"
"A step towards unification of syntactic and statistical pattern recog- nition"
"Branch and bound methods: A survey"
"Subgraph error-correcting isomorphisms for syntactic pattern recognition"
"A graph distance measure for image analysis"
"Scene labeling by relaxation opera- tions"
"Shape matching using relaxation techniques"
"A new probabilistic relaxation scheme"
"On the foundations of relaxation labeling processes"
"Registering Landsat images by point matching"
"Matching: invariant to translations, rotations and scale changes"
"Structural matching in computer vision using probabilistic relaxation"
"DPA: A deterministic approach to the MAP problem"
"Pattern recognition by graph matching- combinatorial versus continuous optimization"
"Optimization in model matching and perceptual organization"
"Algebraic transformations of objective functions"
"Constrained nets for graph matching and other quadratic assignment problems"
"Relaxation by the Hopfield neural network"
"Object recognition using multi-layer Hopfield neural network"
"A neural network approach to CSG-based 3-D object recognition"
"Pattern recognition by graph matching using the potts MFT neural networks"
"A linear programming approach for the weighted graph matching problem"
"An eigendecomposition approach to weighted graph matching problems"
"Application of genetic algorithms in graph match- ing"
"A Lagrangian relaxation network for graph matching"
"A relationship between arbitrary positive matrices and doubly stochastic matrices"
"The invisible hand algorithm: Solving the assignment problem with statistical physics"
"A novel optimizing network architecture with applications"

"Parallel and deterministic algorithms from MRFs: Surface reconstruction"
"Constructing simple stable descriptions for image partitioning"
"A new method for mapping optimization problems onto neural networks"
"Generalized graduated non-convexity algorithm for maximum a posteriori image estimation"

"Learning compatibility coefficients for relaxation labeling processes"
"On problem solving with Hopfield networks"
"On the stability of the traveling salesman problem algorithm of Hopfield and Tank"
"Clustering with a domain specific distance measure"
"New algorithms for 2-D and 3-D point matching: pose estimation and correspondence"
"Learning with preknowledge: clustering with point and graph matching distance measures"
"Statistical physics algorithms that converge"
"Graph partitioning using annealed networks"
Computers and intractability: a guide to the theory of NP-completeness
"Computing with structured neural networks"
"A common framework for image segmentation"
"Training stochastic model recognition algorithms as networks can lead to maximummutual information estimation of parameters"

Parallel and Distributed Computation: Numerical Methods

"On the unification of line processes, outlier rejection, and robust statistics with applications to early vision"
"An image understanding system using attributed symbolic representation and inexact graph-matching"
Linear and Nonlinear Programming
"Mean-field phase transitions and correlation functions for Gibbs random fields"
"Hierarchical mixtures of experts and the EM algorithm"
"Statistical physics, mixtures of distribu- tions, and the EM algorithm"
"Improving consistency and reducing ambiguity in stochastic labeling: an optimization approach"
"Relaxation matching techniques-a comparison"
Rinnooy Kan
--TR

--CTR
S. Nalin Pradeep , Mayur D. Jain , R. Balasubramanian , Rama Bhargava, Local and global tree graph structures for fingerprint verification, Proceedings of the 24th IASTED international conference on Signal processing, pattern recognition, and applications, p.287-293, February 15-17, 2006, Innsbruck, Austria
Joyce Y. Chai , Pengyu Hong , Michelle X. Zhou, Combining semantic and temporal constraints for multimodal integration in conversation systems, Proceedings of the HLT-NAACL workshop on Research directions in dialogue processing, p.1-3, May 31, 2003, Edmonton, Alberta, Canada
Jian-Wei Yang , Li-Feng Liu , Tian-Zi Jiang, Efficient fingerprint matching algorithm for integrated circuit cards, Journal of Computer Science and Technology, v.19 n.4, p.510-520, July 2004
Barend J. van Wyk , Michael A. van Wyk, A POCS-Based Graph Matching Algorithm, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.26 n.11, p.1526-1530, November 2004
K. G. Khoo , P. N. Suganthan, Evaluation of genetic operators and solution representations for shape recognition by genetic algorithms, Pattern Recognition Letters, v.23 n.13, p.1589-1597, November 2002
Philip Klein , Srikanta Tirthapura , Daniel Sharvit , Ben Kimia, A tree-edit-distance algorithm for comparing simple, closed shapes, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.696-704, January 09-11, 2000, San Francisco, California, United States
Philip N. Klein , Thomas B. Sebastian , Benjamin B. Kimia, Shape matching using edit-distance: an implementation, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.781-790, January 07-09, 2001, Washington, D.C., United States
Joyce Y. Chai , Pengyu Hong , Michelle X. Zhou, A probabilistic approach to reference resolution in multimodal user interfaces, Proceedings of the 9th international conference on Intelligent user interface, January 13-16, 2004, Funchal, Madeira, Portugal
Marco Carcassoni , Edwin R. Hancock, Correspondence Matching with Modal Clusters, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.25 n.12, p.1609-1615, December
Graphical models for graph matching: approximate models and optimal algorithms, Pattern Recognition Letters, v.26 n.3, p.339-346, February 2005
Anand Rangarajan , Alan Yuille , Eric Mjolsness, Convergence properties of the softassign quadratic assignment algorithm, Neural Computation, v.11 n.6, p.1455-1474, Aug. 15, 1999
Alessio Massaro , Marcello Pelillo, Matching graphs by pivoting, Pattern Recognition Letters, v.24 n.8, p.1099-1106, May
M. A. Lozano , F. Escolano, Protein classification by matching and clustering surface graphs, Pattern Recognition, v.39 n.4, p.539-551, April, 2006
Duck Hoon Kim , Il Dong Yun , Sang Uk Lee, A comparative study on attributed relational gra matching algorithms for perceptual 3-D shape descriptor in MPEG-7, Proceedings of the 12th annual ACM international conference on Multimedia, October 10-16, 2004, New York, NY, USA
Xuying Zhao , Yangsheng Wang , Zhongchao Shi, Combining fingerprint matchers based on D-S evidence theory, Proceedings of the 24th IASTED international conference on Signal processing, pattern recognition, and applications, p.76-80, February 15-17, 2006, Innsbruck, Austria
Alexey Kostin , Josef Kittler , William Christmas, Object recognition by symmetrised graph matching using relaxation labelling with an inhibitory mechanism, Pattern Recognition Letters, v.26 n.3, p.381-393, February 2005
Eunkwang Park , Kwangyun Wohn, Stereo and motion correspondences using nonlinear optimization method, Computer Vision and Image Understanding, v.101 n.3, p.194-203, March 2006
Tibrio S. Caetano , Terry Caelli, Approximating the problem, not the solution: An alternative view of point set matching, Pattern Recognition, v.39 n.4, p.552-561, April, 2006
Richard C. Wilson , Edwin R. Hancock , Bin Luo, Pattern Vectors from Algebraic Graph Theory, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.7, p.1112-1124, July 2005
Bin Luo , E. R. Hancock, A unified framework for alignment and correspondence, Computer Vision and Image Understanding, v.92 n.1, p.26-55, October
Jaewoo Kang , Jeffrey F. Naughton, On schema matching with opaque column names and data values, Proceedings of the ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California
Brett Allen , Brian Curless , Zoran Popovi, Articulated body deformation from range scan data, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
Joyce Y. Chai , Pengyu Hong , Michelle X. Zhou , Zahar Prasov, Optimization in multimodal interpretation, Proceedings of the 42nd Annual Meeting on Association for Computational Linguistics, p.1-es, July 21-26, 2004, Barcelona, Spain
Michelle X. Zhou , Zhen Wen , Vikram Aggarwal, A graph-matching approach to dynamic media allocation in intelligent multimedia interfaces, Proceedings of the 10th international conference on Intelligent user interfaces, January 10-13, 2005, San Diego, California, USA
Thomas Kmpke, Distance Patterns in Structural Similarity, The Journal of Machine Learning Research, 7, p.2065-2086, 12/1/2006
Dmitriy Bespalov , Ali Shokoufandeh , William C. Regli , Wei Sun, Scale-space representation of 3D models and topological matching, Proceedings of the eighth ACM symposium on Solid modeling and applications, June 16-20, 2003, Seattle, Washington, USA
Josep Llados , Enric Mart , Juan Jose Villanueva, Symbol Recognition by Error-Tolerant Subgraph Matching between Region Adjacency Graphs, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.10, p.1137-1143, October 2001
Andrew M. Finch , Richard C. Wilson , Edwin R. Hancock, An energy function and continuous edit process for graph matching, Neural Computation, v.10 n.7, p.1873-1894, Oct. 1998
Antonio Robles-Kelly , Edwin R. Hancock, Graph Edit Distance from Spectral Seriation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.3, p.365-378, March 2005
Fred DePiero , David Krout, An algorithm using length-r paths to approximate subgraph isomorphism, Pattern Recognition Letters, v.24 n.1-3, p.33-46, January
Thomas B. Sebastian , Benjamin B. Kimia, Curves vs. skeletons in object recognition, Signal Processing, v.85 n.2, p.247-263, February 2005
Marcello Pelillo, Matching Free Trees, Maximal Cliques, and Monotone Game Dynamics, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.11, p.1535-1541, November 2002
Ali Shokoufandeh , Sven Dickinson, Graph-theoretical methods in computer vision, Theoretical aspects of computer science: advanced lectures, Springer-Verlag New York, Inc., New York, NY, 2002
Brijnesh J. Jain , Fritz Wysotzki, Central Clustering of Attributed Graphs, Machine Learning, v.56 n.1-3, p.169-207
Antonio Robles-Kelly , Edwin R. Hancock, A Riemannian approach to graph embedding, Pattern Recognition, v.40 n.3, p.1042-1056, March, 2007
M. Fatih Demirci , Ali Shokoufandeh , Yakov Keselman , Lars Bretzner , Sven Dickinson, Object Recognition as Many-to-Many Feature Matching, International Journal of Computer Vision, v.69 n.2, p.203-222, August    2006
Yang , C.-J. Richard Shi, FROSTY: a program for fast extraction of high-level structural representation from circuit description for industrial CMOS circuits, Integration, the VLSI Journal, v.39 n.4, p.311-339, July 2006
Haili Chui , Anand Rangarajan, A new point matching algorithm for non-rigid registration, Computer Vision and Image Understanding, v.89 n.2-3, p.114-141, February
Aymeric Perchant , Isabelle Bloch, Fuzzy morphisms between graphs, Fuzzy Sets and Systems, v.128 n.2, p.149-168, June 2002
Thomas B. Sebastian , Philip N. Klein , Benjamin B. Kimia, Recognition of Shapes by Editing Their Shock Graphs, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.26 n.5, p.550-571, May 2004
Raghu Krishnapuram , Swarup Medasani , Sung-Hwan Jung , Young-Sik Choi , Rajesh Balasubramaniam, Content-Based Image Retrieval Based on a Fuzzy Approach, IEEE Transactions on Knowledge and Data Engineering, v.16 n.10, p.1185-1199, October 2004
Marcello Pelillo, Replicator Equations, Maximal Cliques, and Graph Isomorphism, Neural Computation, v.11 n.8, p.1933-1955, November 1999
Philip David , Daniel Dementhon , Ramani Duraiswami , Hanan Samet, SoftPOSIT: Simultaneous Pose and Correspondence Determination, International Journal of Computer Vision, v.59 n.3, p.259-284, September-October 2004
Marcello Pelillo , Kaleem Siddiqi , Steven W. Zucker, Matching Hierarchical Structures Using Association Graphs, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.21 n.11, p.1105-1120, November 1999
Huaijun Qiu , Edwin R. Hancock, Graph matching and clustering using spectral partitions, Pattern Recognition, v.39 n.1, p.22-34, January, 2006
Kaleem Siddiqi , Ali Shokoufandeh , Sven J. Dickinson , Steven W. Zucker, Shock Graphs and Shape Matching, International Journal of Computer Vision, v.35 n.1, p.13-32, Nov. 1999
Bin Luo , Edwin R. Hancock, Structural Graph Matching Using the EM Algorithm and Singular Value Decomposition, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.10, p.1120-1136, October 2001
Nikos Paragios , Mikael Rousson , Visvanathan Ramesh, Non-rigid registration using distance functions, Computer Vision and Image Understanding, v.89 n.2-3, p.142-165, February
Stefano Berretti , Alberto Del Bimbo , Enrico Vicario, Efficient Matching and Indexing of Graph Models in Content-Based Retrieval, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.10, p.1089-1105, October 2001
Jens Keuchel , Christoph Schnrr , Christian Schellewald , Daniel Cremers, Binary Partitioning, Perceptual Grouping, and Restoration with Semidefinite Programming, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.25 n.11, p.1364-1379, November
Michal A. van Wyk , Tariq S. Durrani , Barend J. van Wyk, A RKHS Interpolator-Based Graph Matching Algorithm, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.7, p.988-995, July 2002
Ali Shokoufandeh , Diego Macrini , Sven Dickinson , Kaleem Siddiqi , Steven W. Zucker, Indexing Hierarchical Structures Using Graph Spectra, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.7, p.1125-1140, July 2005
Dennis Shasha , Jason T. L. Wang , Rosalba Giugno, Algorithmics and applications of tree and graph searching, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin
model matching;graduated assignment;continuation method;attributed relational graphs;softassign;weighted graphs;relaxation labeling;graph matching