Subgraph Matching Using Graph Neural Network

Affiliation(s)

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

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

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.

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.

Cite this paper

G. Baskararaja and M. Manickavasagam, "Subgraph Matching Using Graph Neural Network,"*Journal of Intelligent Learning Systems and Applications*, Vol. 4 No. 4, 2012, pp. 274-278. doi: 10.4236/jilsa.2012.44028.

G. Baskararaja and M. Manickavasagam, "Subgraph Matching Using Graph Neural Network,"

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.

[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.