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