Graph Classification Using Back Propagation Learning Algorithms

1. Introduction

Graphs play a pivotal role in the computational domains of various fields such as telecommunication network (Shi & Malik, 2000), social network analysis (Bouckaert et al., 2011), bioinformatics (Backstrom & Leskovec, 2011), chemical compounds (Ralaivola et al., 2005), vision analysis (Agrawal et al., 2013) etc., wherein the input data is represented by graphs to compute the levels of nodes and edges or that of graph itself. Graphs of different domains are collected and various features are computed. Thus a dataset is obtained for the collection of graphs. Each graph of a particular domain belongs to same class. For a collection of N graphs G_i = (V_i, E_i), i = 1,2,….,N, with vertices V_i = {v_i1, . . ., v_in} and edges E_i = {(v_ij, v_ik)|v_ij, v_ik ∈ V_i}, defined over a data set D, if G_i conforms to class y_i, C = {1, . . ., k} being the set of k class labels of different categories, the purpose of classification of graph is to train a model f: D → C by selecting representative sample of known class labels called training sets, to calculate the class label for any graph. The accuracy of the classification is obtained by comparing the computed output y′_i = f(G_i) obtained for the testing data set with the true class label y_i. The graph labelling of G_i in respect of the nodes and the edges may be drawn with reference to a common set of labels for the entire dataset D.

Due to the propagation of graph data, several researchers have proposed various effective methods for classifying the graph object. Usually, the values of the features of each graph are computed first and then a suitable feature selection algorithm is used for identifying the relevant features from the above mention features. It is worth noting that for any classifier, the identification of relevant features is most important to yield the best graph classification result in terms of higher accuracy.

One general approach is to use support vector machines (Gartner et al., 2003) by converting the graph data into a vector representation of lower dimension. Another way is to compare two graphs by using the Graph kernels to the structural features extracted from the graph. Here, the similarities between any two graphs in D are measured by constructing a kernel matrix Κ = {κ(G_i,G_j)}^N_i,_j=1, where the kernel function κ(G_i,G_j) is the inner-product between the vectors of G_i and G_j in the feature space of N dimension (Scholkopf & Smola, 2001). The Support Vector Machine (SVM) can then be applied to carry the graph classification for a well-defined kernel matrix K (Vapnik, 1995).

The neural networks can also be used to find the hidden depiction by extracting structural features as a set of latent parameters that cannot be directly observed from the graph structure. Here, each node representation is learned by using a low dimensional vector representing each vertex of the graph so that the vectors of corresponding vertices are located near each other in the Euclidean space. Such low dimensional representations can therefore be used for graph clustering and classification in various algorithms.

Most of the proposed graph classification techniques are though effective but are constrained by high computational overhead. Developing an effective graph classification algorithm in terms of high accuracy and less computational complexity thus becomes important to study.

In this paper, the Back propagation learning algorithms has been used to classify the graphs for which various graph based features are extracted and the most relevant features required for future graphs classification for prediction of unknown patterns in the datasets, are selected using feature extraction and selection algorithms. The experimental results reveal that the proposed feature-based Back propagation learning classification algorithms have better accuracy and less computational time complexity in comparison to other graph kernels. As the proposed technique is capable of capturing the structural differences between classes effectively, it can offer equally good results for large unlabeled graphs.