Integrated Intelligent Research (IIR) International Journal of Web Technology

Volume: 01 Issue: 02 December 2012 Page No.50-56

ISSN: 2278-2389

Graph Matching Algorithm-Through Isomorphism

Detection
L. Ravi, K. Sujitha
Department of Computer Science, Sacred Heart College (Autonomous),
Tirupattur, Vellore, Tamil Nadu, India

Abstract- This Paper delivers a new algorithm to the problem of imprints under much less constraints are dealt in [4]. The
graph isomorphism detection. Basically this method is designed matching algorithm for a large number of model objects are
in such a way that, a model graph which is known prior is discusses in [5].In [6] the efficiency of graph matching is
compared with an unknown graph called input graph. Now the improved through the reduced storage capability.[7] represents
problem to be solved is to find a graph isomorphism from the the new method for effective recognition of handwritten Chinese
input graph which is given online with the one which is known as character. A systematic method for 3D model matching in robot
model graph. At dynamic time the input graph is compared with vision by using subgraph matching techniques is explained in [8].
the entire model graph for which there exists a graph The proposed method checks geometric constraints between and
isomorphism from the input graph are detected. The time current partial matching pairs and remaining possible pairs and
complexity depends on the number of input graphs given and significantly reduces the search space in [9]. Generalized Rete
size of the graphs. Furthermore it is independent of number of Networks algorithm for matching is given in [10]. An
model graphs given and the number of edges in any of the graph. incremental clustering system based on a new principle function
to group patterns represented by attributed graphs is presented in
Keywords- Graph matching, graph isomorphism, subgraph [11]. The ordering of graph, match _label and constraints, the
isomorphism. matching procedure of graph is illustrated in [12]. A new method
that combines the Graph Matching approach with Rule-Based
I. INTRODUCTION approaches from Machine Learning is specificer in [13]. The
computational algorithm for the matching explained in [14]. The
Graphs are powerful and universal data structure used in various proposed method can be used to solve other planar graph
sub fields of science and engineering. A graph consists of set of problems including connectivity, diameter, girth, induced
vertices and a set of edges. A graph may be directed or subgraph isomorphism, and shortest paths illustrated in [15].
undirected. When graphs are used for representation, the problem [16] Illustrates an are association graph from two (rooted) trees,
arises in comparing two or more objects. The similarity between based on the graph-theoretic notions of connectivity and the
two graphs is called as isomorphism. Hence this paper deals with distance matrix. The problem of comparing different objects to
the problem of graph isomorphism detection. So a new approach each other can be formulated as the search for correspondences
for solving this graph isomorphism in polynomial time is under between the attributed graphs representing the objects. Such
research. This research provides a similar small approach to correspondences can be established by subgraph isomorphism
solve the problem in polynomial time. In many applications a detection is discussed in [17]. An efficient subgraph
crucial operation is the comparison between two objects or isomorphism detection through the use of decomposition
between an object and a model to which the object could be approach is explained in [18]. An efficient algorithm for inexact
related. When structured information is represented by graphs graph matching is illustrate in [19].[20] explains how raster
this comparison is performed using some form of graph images are converted in Region Adjacency Graphs structures.
matching. Graph matching is the process of finding a The problem of computing a perfect matching of minimum cost
correspondence between the nodes and the edges of two graphs in an undirected weighted graph is given in [21]. An algorithm
that satisfies some (more or less stringent) constraints ensuring for graph isomorphism and subgraph isomorphism suited for
that similar substructures in one graph is mapped to similar dealing with large graphs is given in [22]. The algorithm exploits
substructures in the other. Although graph theory is one of the graph sparsity to improve computational efficiency is proposed
younger branches of mathematics, it is fundamental to a number in [23]. [24] explains an inexact graph-matching is a problem of
of applied fields, including operations research and computer potentially exponential complexity; the problem may be
science. Here, an implementation of the paper work is based on simplified by decomposing the graphs to be matched into smaller
the graph isomorphism on a directed graph.Enumeration subgraphs. In [25] illustrates the utility of the resulting method
algorithm with refinement procedure is used to find the subgraph for shape-analysis. A new filtering algorithm for the subgraph
isomorphism techniques are specifieed in [1]. An Algorithm isomorphism problem that exploits the global structure of the
gives the near optimum solution to the weighted undirected graph to achieve a stronger partial consistency is dealt in
graph matching problem is dealt in [2].The monocular [26].Learning graph matching is about designing efficient
description technique which is used for any kind of images, algorithms for approximately solving the quadratic assignment
including random dots also, two kinds of matching namely, local problem is deal in [27] .A novel graph indexing method to handle
matching and global matching is explain at in [3].The handle seal with the more general, inexact matching problem is proposed in
50
Integrated Intelligent Research (IIR) International Journal of Web Technology
Volume: 01 Issue: 02 December 2012 Page No.50-56
ISSN: 2278-2389
[28].Section1 deals with introduction. Basic definitions are mapping of the nodes of G1 onto the nodes of H such that all
explained in section2. Section3 discusses an approach of corresponding edge adjacencies are preserved. The problem is
proposed graph matching algorithm and explanations associated that of finding an efficient algorithm or approach for determining
with it. Results and discussions are explained in section4.Finally, whether one given graph (pattern graph, G1) is an isomorphic
in Section 5 deals with the conclusion and explains about further Graph of another graph (model graph, G2). Here, all graphs are
works and directions. supposed to be connected graphs. Its difficulty can be seen easily
from the fact that selecting out of the mn possibilities that arise
II. DEFINITIONS in the combinatorial matching of n nodes in the smaller graph to
m nodes in the larger graph, while preserving all the adjacencies.
Definition 1. Graph No efficient algorithm for this problem is known so far, and it
was conjectured by many experts that no polynomial-time
A graph is usually denoted by G(V,E) or by G = (V,E). A graph algorithm exists because of its Non Polynomial-completeness.
consists of set of vertices (V) together with a set of edges (E). Generally, for majority of practical applications, both pattern and
The number of vertices in a graph is usually denoted by n while model graphs are labeled graphs. Their label sets are known and
the number of edges is usually denoted by m. their sizes also. In the extreme case of the label set size being
one, a labeled graph becomes indistinguishable with an unlabeled
graph, so that labeled Graph isomorphism problem contains
Definition 2. Graph Isomorphism
unlabeled Graph isomorphism problem which is a well known
Non Polynomial-Complete problem. In fact, unlabeled Graph
Two graphs, G1 and G2, are isomorphic if there is a one-to-one isomorphism problems are usually used on theoretical analysis
correspondence between the vertices of G1 and those of G2 with since it can provide an up-bound of time complexity due to its
the property that the number of edges joining any two vertices of Non Polynomial-completeness.
G1 is equal to the number of edges joining the corresponding
vertices of G2.
3.2 New Algorithm
Definition 3. Matching The Graph Isomorphism problem is a frequent computation in
many applications, where the search and recognition of a smaller
Matching is defined as the comparison of two or more graphs, graph from a larger graph is needed. It deals with two different
graphs.
and then the resultant similarities are extracted as output. This is
known graph isomorphism. Here the matching is done by
1. Model graph
comparing the model graph which is stored in a file and an input
graph that is given at run time. A directed graph is taken for 2. Input graph.
matching.
Model graphs are known prior and with that model graph an input
III. GRAPH MATCHING ALGORITHM graph is to be compared. This algorithm provides a new approach
to compare model graph with more than one input graphs. It
compares with the model graph which is stored on a file prior with
3.1 Over view of the method the input graphs given at dynamic run time. Comparison is done
The concept of Graph isomorphism detection has been applied in between the first input graphs, then after that the results obtained
a variety of fields. For instance, a given graph G1 is isomorphic from the first comparison is compared with the second input
to a graph H of another given G2 if there exists a one-to one graph. If any match exists, then that is termed as the final result.

Table I NEW ALGORITHM

Step 1 : Get the input for the First Graph

Step 2 : Get the no. of nodes

51
Integrated Intelligent Research (IIR) International Journal of Web Technology
Volume: 01 Issue: 02 December 2012 Page No.50-56
ISSN: 2278-2389
Step 3 : Then get the vertices and its path on a adjacency matrix .

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

// PRINT i value and j value//

graph1[i][j]=Integer.parseInt(br.readLine());

Step 4: By default nodes pointing to the same node is kept zero. If that has to be entered manually,

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

graph1[i][j]=0;

Step 5: Then store first graph on to a file. Which acts as an model graph.

BufferedWriter ot = new BufferedWriter(new ileWriter("graph.txt"));

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

String str= Integer.toString(i);

String str1=Integer.toString(j);

String str2= Integer.toString(graph1[i][j]);

ot.write(str+"-");

ot.write(str1+"=");

ot.write(str2);

52
 Integrated Intelligent Research (IIR) International Journal of Web Technology
Volume: 01 Issue: 02 December 2012 Page No.50-56
ISSN: 2278-2389
ot.newLine();

Step 6 : Then obtain the second graph values and store in another array .

Step 7: Similarly the third graph value is obtained.

Step 8: Comparison between the model graphs and an input graph is made.

Step 9: Then the final match is obtained and displayed.

for(i=1;i<=z;i++)

{ for(j=1;j<=z;j++)

if(graph2[i][j]!=0 && graph3[i][j]!=0) {

if(s[k]==i && s[k+1]==j && s[k+2]==graph2[i][j] && s[k+2]==graph3[i][j])

// print graph[i][j] matrix

This graph matching algorithm provides the way to identify The following section explains an example of the proposed
matches or similarities between two or more graphs. It solves the
algorithm.
problem of Graph isomorphism which is one of the major
challenging aspects. The new method is introduced in this
algorithm where the nodes having same path in two model graphs (1) Get the model graph as first graph
are represented only once. And that value is compared with the
input graph that is given online. This partially reduces the time
complexity of an algorithm. And another method handled is, the
nodes pointing to itself is marked zero by default. This reduces the
time consumption while giving input.

Initially, first graph input is obtained and stored in an array. Then

the path between nodes is obtained on an adjacency matrix
graph1[i][j]. Graph1 is said to be a Model graph. Since a model
graph is to be known prior, It is initially stored on a file on local
system. Then similarly the second graph value is obtained and
stored on graph2[i][j]. Then values or paths between edges are
obtained. At last final comparison is done by retrieving the model (2) Generate Adjacency Matrix for model Graph1
graphs from file and compared with the input graphs that are
given online. This algorithm compares with more than one input [1] [2] [3] [4] [5]
graph and the match is found.
[1] 0 1 0 0 0
3.3 Example
[2] 0 0 0 1 0

[3] 1 0 0 0 0
53
Integrated Intelligent Research (IIR) International Journal of Web Technology
Volume: 01 Issue: 02 December 2012 Page No.50-56
ISSN: 2278-2389
[4] 0 0 1 0 1 Common nodes and path are:

[5] 1 0 1 0 0 1-2=1

(3) Get the input graph as graph 2 3-1=6

(4) Generate Adjacency Matrix for input Graph1 In first step the model graph gets input. The size of the model
graph depends on the user wish. Then the two input graphs get as
[1] [2] [3] [4] an input graph. The size of input graph also depends on user
wish. Then generate the adjacency matrix for model graph and
[1] 0 1 0 0 input graphs. Here the Model Graph and input graph which has
the value 0 and 1. The value 0 (Zero) denotes that there is no
[2] 0 0 0 1 path or connection between two vertices. Input is given as an
adjacency matrix. For e.g. 13 = 0 denotes that there is no link
[3] 1 0 0 0 between 1 and 3. 12= 1 denotes that the connection exists
between two edges. So these values are obtained in an array and
[4] 0 0 1 0 stored on a file using file stream. Then for comparison, each
value is fetched from a file compared with the rest of the paths. If
(5) Get the input graph2 two graphs has the same path, then that match is extracted and
then similarly it is done for all the rest of the nodes.Be default,
the diagonal Elements of an adjacency matrix is 0 (zero), since a
node cannot point to itself. The comparison is done after sorting
all the elements in ascending order, then by taking (1, 2) pair, it
checks all the resultant values in the adjacency matrix up to
(5,4 ).Then the final match is extracted.

3.4 Computational Complexity Analysis:

In this section a detailed analysis of the run time complexity of

the proposed algorithm for model graph and input graphs are
discussed. The analysis will be based on the following quantities:

L= the number of model graph

(6) Generate Adjacency Matrix for input Graph2
n= number of vertices of a model graph
[1] [2] [3]
m1= the number of vertices that are unique to each input graph
[1] 0 1 0
m=the total number of vertices in input graph
[2] 0 0 1
The computation steps that are performed can be estimated in
[3] 1 0 0 terms of calls of the nodes or vertices and the number of calls to
the procedure combine times the complexity of combine
(7) After comparisons, the matched graph is produced as itself.The best case for the algorithm arises when ach of the
vertices of the model graph is uniquely labeled. For a single
output model graph, there will be different vertices. It will be called n
times. Each call test m vertices of the input graph and
54
Integrated Intelligent Research (IIR) International Journal of Web Technology
Volume: 01 Issue: 02 December 2012 Page No.50-56
ISSN: 2278-2389
consequently, a total number of O(mn) steps. The number of be easy. It will also work for graphs where it has to establish a
matchings found by O(m/n). There will O(m ) calls to the one to one mapping between nodes in the second graph and
procedure to combine.Comparing the graphs of the mapping nodes with a larger degree in the first graph.
takes O(k) steps with k n.Thus, the total computational V. CONCLUSION AND FURTHER WORKS
complexity for matching a single model graph against an input
graphs is the best case bounded by O(mn+n2 m/n)=O(mn) In this research work the new algorithm for graph matching is
proposed. The new algorithm is based on the idea of finding an
isomorphism between a single model graph and the different
input graphs. In that at the run time the detection of the
isomorphism is found out from a model graph to some of input
graphs.The graph matching is performed with the labeled and
IV. RESULTS AND DISCUSSIONS
directed graphs. Graph matching algorithm is best suited for a
particular application which depends on the number and the size
As mentioned on the abstract, this algorithm will basically search of the underlying graphs, the kind of labels that occur in the
over the combination of matches for the similarities between two graphs, and the type of matching that is required. In brief, the
input graphs and a model graph. By "match", that is a mapping main conclusions from this research are that,The speed of graph
from single node of graph1 to a single node of model graph. matching can be significantly depends on the size of the model
Each step in the search algorithm will add a new match to the graph and the input graphs.The accuracy of graph matching can
isomorphism as developed so far. So once if this match extends be significantly improved without decreasing the speed.The new
to all nodes of input graphs, then it’s the end point of searching algorithm should not be applied to problem dealing with
algorithm. Else if that is not accomplished, then it has to unlabeled and undirected graphs with restricted connectivity. The
backtrack and attempt different matches. So the same process is algorithm has been presented in a general form without the
repeated until the maximum matches between two graphs are explicit use of domain features or heuristics. Therefore, it can be
found. regarded in a generic tool that is applicable to various tasks.The
new graph matching be implemented with the use of different
4.1 Results model graphs and n number of input graphs. The complexities of
As a result, this research obtains all the matches between an the graph matching approaches make it very difficult to take into
input graph and the model graph that has stored on a file priory. account all types of dependencies between the vertices and edges
The main modification of the algorithm is, the nodes are sorted in in the model graph and input graphs. At last, it is to be mentioned
the increasing order before matching and all the nodes are placed that there is a potential for parallelization inherent in the new
on a structure of array. And it also performs mapping between approach, which may be used for a further improvements of the
unsorted nodes, so that it can sort it down at the final stage and performance.
return mappings between nodes. Thus a final comparison results
are fetched as an output. REFERENCES
4.2 Discussions [1] J.R. Ullman, “An Algorithm for Subgraph Isomorphism”, Journal of the
Associationfor Computing Machinery, Vol. 23, No. 1, pp. 31-42, 1976.
At this point, this paper work tries to find much worse cases. It [2] Shinji Umeyama, “An Eigen decomposition Approach to Weighted Graph
seems obvious that it's going to have more backtracks if the Matching Problems”, IEEE Transactions on Pattern Analysis and Machine
graph is "highly automorphic", by which it means that large Intelligence, Vol.10. No.5, 1988.
portions of the graph are isomorphic to other portions. When it [3] Radu Horaud and Thomas Skordas,“Structural Matching for Stereo
Vision”, Proceedings of Ninth International Conference on Pattern
tried this, sure enough, there were lots and lots of backtracks. Recognition, pp. 439-445, 1988.
Then it realized that it ought to be worse when there was no [4] SeogWhan Lee and Jin H. Kim, “Attributed Stroke Graph Matching
isomorphism, so it hooked two opposite "corners” together with for
an edge in one graph which wasn't present in the second. To [5] Seal Imprint Verification”, Pattern Recognition Letters, Vol. 9, pp. 137
145,1989.
cancel out of this run after a long wait, because, it's pretty close [6] Whoi-Yul. Kim and Avinash C. Kak, “3-D Object Recognition Using
to the worst case. Since the corners had lower degrees than the Bipartite Matching Embedded in Discrete Relaxation”, IEEE Transaction
middle nodes, they were going to be examined after all the on Pattern Analysis and Machine Intelligence, Vol. 13, pp. 224-251, 1991.
[7] Si.Wei. Lu, Ying. Ren, and Ching.Y. Suen “Hierarchical Attributed Graph
middle nodes had been checked for isomorphism, and since they
Representation and Recognition of Handwritten Chinese
were the only non-isomorphic part, it was going to try zillions of Characters”,Pattern Recognition, Vol. 24, pp. 617-632, 1991.
backups. To verify this, instead of one graph between these two [8] E.K. Wong, “Model Matching in Robot Vision by Subgraph Isomorphism”,
nodes, it inserted several so their higher degree caused the Pattern Recognition, Vol. 25, No. 3, pp. 287-304, 1992.
[9] Chang.J. Cho and Jin.H. Kim, “Recognizing 3-D Objects by Forward
algorithm to examine them first. This caused the runtime to be Checking Constrained Tree Search”, Pattern Recognition Letters, Vol. 13,
almost immediate. One possibility which would have eliminated No. 8, pp. 587-597, 1992
this particular problem is to have just done a comparison of node [10]H.S. Lee and M.I. Schor, “Match Algorithms for Generalized Rete
degrees. Since it is already sorting nodes by degree, this should Networks”, Artificial Intelligence, pp. 255-270, 1992

55
Integrated Intelligent Research (IIR) International Journal of Web Technology
Volume: 01 Issue: 02 December 2012 Page No.50-56
ISSN: 2278-2389
[11]Dong Su Seong, Ho Sung Kim, and Kyu Ho Park,“Incremental
Clustering of Attributed Graphs”, IEEE Transaction on System, Man, and
Cybernetics,Vol.23, No. 5,pp. 1,399-1,411, 1993.
[12]Richard E. Blake, “Partitioning Graph Matching with Constraints”, Pattern
Recognition, Vol. 27, No. 3, pp. 439-446, 1994.
[13]Adrian Pearce, Terry Caelli, and Walter F. Bischof, “Rule graphs for Graph
Matching in Pattern Recognition”,Pattern Recognition, Vol.27, No.9,
pp.1,231-1, 246,1994.
[14]William J. Christmas,Josef. Kittler, and Maria Petrou, “Structural
Matching in Computer Vision Using Probabilistic Relaxation”, IEEE
Transaction on Pattern Analysis and Machine Intelligence, Vol. 17, No. 8,
pp. 749-764, 1995.
[15]David Eppstein, “Subgraph Isomorphism in Planar Graphs and Related
Problems”, Journal of Graph Algorithms and Applications, Vol. 3, No. 3,
pp. 1-27, 1999.
[16]H. Bunke, “Error Correcting Graph Matching: On the Influence of the
Underlying Cost Function”, IEEE Transactions On Pattern Analysis And
Machine Intelligence, Vol. 21, No. 9, 1999.
[17]Marcello Pelillo, Member, alee,m Siddiqi, and Steven W. Zucker, Fellow,
“Matching Hierarchical Structures Using Association Graphs”, IEEE
Transactions On Pattern Analysis And Machine Intelligence, Vol. 21, No,
11, 1999.
[18]Bruno T.Messmer and Horst Bunke, “Efficient subgraph isomorphism
detection – a decomposition approach”, IEEE Transactions on Knowledge
and Data Engineering, Vol. 12, No.2, 2000.
[19]Bin Luo and Edwin R. Hancock, “Structural Graph Matching Using the EM
Algorithm and Singular Value Decomposition”, IEEE Transactions On
Pattern Analysis And Machine Intelligence, Vol. 23, No. 10, 2001.
[20]Josep Lladoas, Enric Marti, and Juan Josea Villanueva, “Symbol
Recognition by Error-Tolerant Subgraph Matching between Region
Adjacency Graphs”,IEEE Transactions On Pattern Analysis And Machine
Intelligence, Vol. 23, No.10, 2001.
[21]Vladimir Kolmogorov, “Blossom V: A new implementation of a minimum
cost perfect matching algorithm”, Mathematical Programming
Computation, 2002.
[22]S. Bachl. F.-J. Randenburg,D. Gmach, “Computing and Drawing
Isomorphic Subgraphs”, Journal of Graph Algorithms and Applications,
Vol.8, No. 2, pp. 215–238, 2004.
[23]Luigi P.Cordella, Pasquale Foggia, Carlo Sansone,and Mario Vento, “A
(Sub)Graph Isomorphism Algorithm for Matching Large Graphs”, IEEE
Transactions On Pattern Analysis And Machine Intelligence, Vol. 26, No.
10, 2004.
[24]Ying Feng, Robert L. Goldstone, Vladimir Menkov, “A Graph Matching
Algorithm and Its Application to Conceptual System Translation”,
International Journal on Artificial Intelligence Tools World Scientific
Publishing Company, 2004.
[25][24] Huaijun Qiu, Edwin R. Hancock, “Graph matching and clustering
using spectral partitions”, Journal of pattern recognition, Vol. 23,
No.10,2006.
[26]Bin Luo, Richard C.Wilson, and Edwin R. Hancock, “A spectral approach
to learning structural variations in graphs”, The journal of pattern
reorganization society, Published by Elsevier Ltd, Pattern Recognition, Vol-
39, pp.1188 – 1198, 2006.
[27]Stephane Zampelli1, Yves Deville, Christine Solnon,Sebastien Sorlin, and
Pierre Dupont, “Filtering for Subgraph Isomorphism” ,Springer-Verlag
Berlin Heidelberg,2007.
[28]Tiberio S. Caetano, Julian J. McAuley,Li Cheng,Quoc V. Le, and Alex J.
Smola, “Learning Graph Matching”, IEEE Transactions On Pattern
Analysis And Machine Intelligence,Vol.31,No.6, 2009.
[29]Misael Mongiovi, Raffaele Di Natale, Osalba Giugno, Alfredo Pulvirenti ,
Alfredo Ferro And Roded Sharan, “SIGMA: A Set-Cover-Based Inexact
Graph Matching Algorithm” ,Journal of Bioinformatics and Computational
Biology, Vol. 8, No. 2, 2010.

56