Title: Multi-class instance-incremental framework for classification in fully dynamic graphs

Authors: Hardeo Kumar Thakur; Anand Gupta; Sreyashi Nag; Ritvik Shrivastava

Addresses: Department of Computer Science and Technology, Manav Rachna University, Faridabad, India ' Department of Computer Engineering, Netaji Subhas Institute of Technology, University of Delhi, Delhi, India ' Department of Instrumentation and Control Engineering, Netaji Subhas Institute of Technology, University of Delhi, Delhi, India ' Department of Information Technology, Netaji Subhas Institute of Technology, University of Delhi, Delhi, India

Abstract: Existing work in the area of graph classification is mostly restricted to static graphs. These static classification models prove ineffective in several real life scenarios that require an approach capable of handling data of a dynamic nature. Further, the limited work in the domain of dynamic graphs mainly focuses on solely incremental graphs which fail to accommodate fully dynamic graphs (FDG). Hence, in this paper, we propose a comprehensive framework targeting multi-class classification in fully dynamic graphs by utilising the efficient Weisfeiler-Lehman graph kernel (W-L) with a multi-class support vector machine (SVM). The framework iterates through each update using the instance-incremental method while retaining all historical data in order to ensure higher accuracy. Reliable validation metrics are utilised for the model parameter selection and output verification. Experimental results over four case studies on real-world data demonstrate the efficacy of our approach.

Keywords: fully dynamic graph; FDG; dynamic graph; graph classification; multi-class classification.

DOI: 10.1504/IJCSE.2020.105214

International Journal of Computational Science and Engineering, 2020 Vol.21 No.1, pp.69 - 83

Received: 17 Dec 2016
Accepted: 25 Nov 2017
Published online: 22 Feb 2020 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article