Journal of Intelligent Learning Systems and Applications, 2012, 4, 274-278
http://dx.doi.org/10.4236/jilsa.2012.44028 Published Online November 2012 (http://www.SciRP.org/journal/jilsa)
Subgraph Matching Using Graph Neural Network
GnanaJothi Raja Baskararaja, MeenaRani Sundaramoorthy Manickavasagam
Department of Mathematics, V. V. Vanniaperumal College for Women, Virudhunagar, India.
Email: gnanajothi_pcs@rediffmail.com, smmeenarani@gmail.com
Received May 4th, 2012; revised August 1st, 2012; accepted August 8th, 2012
ABSTRACT
Subgraph matching problem is identifying a target subgraph in a graph. Graph neural network (GNN) is an artificial
neural network model which is capable of processing general types of graph structured data. A graph may contain many
subgraphs isomorphic to a given target graph. In this paper GNN is modeled to identify a subgraph that matches the
target graph along with its characteristics. The simulation results show that GNN is capable of iden tifying a target sub-
graph in a graph.
Keywords: Subgraph Matching; Graph Neural Network; Backpropagation; Recurrent Neural Network;
Feedforward N eural Net w or k
1. Introduction
In many practical and engineering applications the un-
derlying data are often represented in terms of graphs.
Graphs generally represent a set of objects (nodes) and
their relationships (edges). In an image, nodes represent
the regions of the image that have same intensity or color,
and the edges represent the relationship among these
regions.
Subgraph matching has a number of practical applica-
tions such as object localization and detection of active
parts in a chemical compound. Subgraph matching is
mainly analyzed in object localization problem. For ex-
ample in military areas to identify a particular object, say
tank from a satellite photograph, the whole area can be
converted into a graph with nodes having labels repre-
senting color, area, etc. of the region. The subgraph which
represents a tank can be made identified by subgraph ma-
tching. The suspected area to which a tank belongs can
be restricted and the corresponding restricted graph can
be considered for identification.
F. Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner,
and G. Monfardini have proposed a GNN structure which
can be considered as an extension of recurrent neural net-
work (RNN) to process very general types of graphs. The
GNN model implements a function
that maps a graph
G into an m-dimensional Euclidean space. The function
depends on the node, so that the classification depends
on the properties of the node. F. Scarselli, M. Gori, A. C.
Tsoi, M. Hagenbuchner, and G. Monfardini have ap-
plied GNN to different types of problems such as
Mutagenesis problem [1], subgraph matching problem
[1], Clique problem [2], Half Hot problem [2], and Tree
depth problem [2]. A. Pucci, M. Gori, M. Hagenbuchner,
F. Scarselli, and A. C. Tsoi [3] have applied GNN to the
movie lens data set and have discussed the problems and
limitations encountered by GNN while facing this par-
ticular practical problem. A comparison between GNN
and RNN is made by V. Di Massa, G. Monfardini, L.
Sarti, F. Scarselli, M. Maggini, and M. Gori [4] and they
have shown that problem GNNs outperforms RNNs in an
experimental comparision on an image classification.
In the subgraph matching problem discussed by F.
Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, and G.
Monfardini [1], the goal of the problem is to identify all
the nodes of a larger graph which also belong to the con-
sidered subgraph. In this paper, the train ed GNN is iden-
tifying a subgraph that matches the target graph along
with its characteristics.
The structure of the paper is organized as follows:
Section 2 describes GNN in the linear case, Section 3
explains subgraph matching problem, Section 4 gives the
proposed algorithm for generating the graphs and identi-
fying the subgraph in the training data. Experimental
results and discussion are given in Section 5.
2. Graph Neural Networks
A graph G = (V,E), where V is a set of points called
nodes, and E is a collection of arcs connecting two nodes
of V. Let ne[n] be the set of nodes connected to the node
n by arcs in E. Figure 1 represents example graph with 5
nodes. The nodes of G are attached with random label
c
n
lR
. A state vector
n
R
is attached to each node n,
Copyright © 2012 SciRes. JILSA