Subgraph Matching Using Graph Neural Network

GnanaJothi Raja Baskararaja, MeenaRani Sundaramoorthy Manickavasagam

Department of Mathematics, V. V. Vanniaperumal College for Women, Virudhunagar, India..

DOI: 10.4236/jilsa.2012.44028                

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 identifying a target sub-graph in a graph.

Keywords

Subgraph Matching; Graph Neural Network; Backpropagation; Recurrent Neural Network; Feedforward Neural Network

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	F. Scarseli, M. Gori, A. C. Tsoi, M. Hagenbuchner and G. Monfardini, “The Graph Neural Network Model,” IEEE Transactions on Neural Networks, Vol. 20, No. 1, 2009, pp. 61-78. doi:10.1109/TNN.2008.2005605
[2]	F. Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner and G. Nfardini, “Computational Capabilities of Graph Neural Networks,” IEEE Transactions on Neural Networks, Vol. 20, No. 1, 2009, pp. 81-102. doi:10.1109/TNN.2008.2005141
[3]	A. Pucci, M. Gori, M. Hagenbuchner, F. Scarselli and A. C. Tsoi, “Applications of Graph Neural Networks to LargeScale Recommender Systems Some Results,” Proceedings of International Multiconference on Computer Science and Information Technology, Vol. 1, No. 6-10, 2006, pp.189-195.
[4]	V. Di Massa, G. Monfardini, L. Sarti, C. F. Scarselli, M. Maggini and M. Gori, “A Comparision between Recursive Neural Networks and Graph Neural Networks,” In-ternational Joint Conference on Neural Networks, 2006, pp. 778-785.
[5]	H. Bunke, “Graph Matching: Theoritical Foundations, Algorithms, and Applications,” Proceedings of International Conference on Vision Interface Vision Interface, Montreal, 14-17 May 2000, pp. 82-88.
[6]	O. Sammound, C. Solnon and K. Ghedira, “Ant Colony Optimization for Multivalent Graph Matching Problems,” 2006. liris.cnrs.fr/Documents/Liris-2395.pdf
[7]	D. Eppstein, “Subgraph Isomorphism in Planar Graphs and Related Problems,” Journal of Graph Algorithms and Applications, Vol. 3 No. 3, 1999, pp. 1-27.
[8]	C. Schellewald and C. Schnorr, “Subgraph Matching with Semidefinite Programming,” Proceedings of International Workshop on Combinatorial Image Analysis, Palmero, 14-16 May 2003, pp. 279-289.