Graph classification is an important tool for analyzing data with structure dependency, where subgraphs are often used as features for learning. In reality, the dimension of the subgraphs crucially depends on the threshold setting of the frequency support parameter, and the number may become extremely large. As a result, subgraphs may be incrementally discovered to form a feature stream and require the underlying graph classifier to effectively discover representative subgraph features from the subgraph feature stream. In this paper, we propose a  primal-dual incremental subgraph feature selection  algorithm ( ISF ) based on a max-margin graph classifier. The ISF algorithm constructs a sequence of solutions that are both primal and dual feasible. Each primal-dual pair shrinks the dual gap and renders a better solution for the optimal subgraph feature set. To avoid bias of ISF algorithm on short-pattern subgraph features, we present a new  incremental subgraph join feature selection  algorithm ( ISJF ) by forcing graph classifiers to join short-pattern subgraphs and generate long-pattern subgraph features. We evaluate the performance of the proposed models on both synthetic networks and real-world social network data sets. Experimental results demonstrate the effectiveness of the proposed methods.
['Haishuai Wang', 'Peng Zhang', 'Xing-Quan Zhu', 'Ivor W. Tsang', 'Ling Chen', 'Chengqi Zhang', 'Xindong Wu']
Incremental Subgraph Feature Selection for Graph Classification