Super-Graph Classification Based on Composite Subgraph Features and Extreme Learning Machine

A multi-graph is modeled as a bag of graphs, whose mutual relationships can be used to enhance the accuracy of multi-graph classification. However, to the best of our knowledge, research on utilizing those mutual relationships has not been reported. In this paper, we propose a novel super-graph model \(SG=(MG,AG)\), where MG denotes a multi-graph and AG represents a graph (named abstract-graph), that describes the mutual relationships among the graphs contained in MG. The super-graph classification problem is challenging to solve because of the very complex structure of the super-graph model. Furthermore, it is hard to directly select distinguished subgraphs, i.e., subgraph features, from super-graphs. A subgraph g of graph G is a graph that is isomorphic with one of the substructures of G. Moreover, the practical applications require the super-graph classification algorithm to have high precision. In this paper, we propose a concept and algorithm for selecting composite subgraph features, based on which a framework is proposed to solve the super-graph classification problem. Subgraph features denote subgraphs that can be used to distinguish super-graphs with different class labels. We first design a two-step approach to select k composite subgraph features from the subgraphs of super-graphs’ abstract-graphs and multi-graphs. Then, based on composite features and the subgraph feature representation of a super-graph, each super-graph SG is transformed into a 0-1 vector with k dimensions. If there exists a substructure in SG that is isomorphic with its i th composite feature, the i th component of the target vector is set to 1 (1 ≤ i ≤ k). Otherwise, it is set to 0. Based on the derived k-dimensional vectors, one of the existing classification algorithms is used to construct a prediction model to predict the class labels of the unseen super-graphs, such as naive Bayes or support vector machine (SVM). Specifically, we adapt the extreme learning machine (ELM) algorithm to further improve the accuracy of super-graph classification. In this paper, we propose a super-graph model and study the problem of super-graph classification. We first derive the concept of composite subgraph features that are selected by our proposed two-step method. Based on the mined composite subgraph features, we propose a super-graph classification framework (SGC) to solve the super-graph classification problem. Moreover, ELM can be used to further improve the classification accuracy. Extensive experiments on real-world image datasets show that our algorithm based on ELM is more accurate than the baseline algorithms.