Semi-supervised multi-graph classification using optimal feature selection and extreme learning machine

A multi-graph is represented by a bag of graphs. Semi-supervised multi-graph classification is a partly supervised learning problem, which has a wide range of applications, such as bio-pharmaceutical activity tests, scientific publication categorization and online product recommendation. However, to the best of our knowledge, few research works have be reported. In this paper, we propose a semi-supervised multi-graph classification algorithm to handle the semi-supervised multi-graph classification problem. Our algorithm consists of three main steps, including the optimal subgraph feature selection, the subgraph feature representation of multi-graph and the semi-supervised classifier building. We first propose an evaluation criterion of the optimal subgraph features, which not only considers unlabeled multi-graphs but also considers the constraints between the multi-graph level and the graph level. Then, the optimal subgraph feature selection problem is equivalently converted into the problem of mining m most informative subgraph features. Based on those derived m subgraph features, every multi-graph is represented by an m-dimensional vector, where the ith dimension equals to 1 if at least one graph involved in the multi-graph contains the ith subgraph feature. At last, based on these vectors, semi-supervised extreme learning machine(semi-supervised ELM) is adopted to build the prediction model for predicting the labels of unseen multi-graphs. Extensive experiments on real-world and synthetic graph datasets show that the proposed algorithm is effective and efficient.