Dual-level Reweighting for Positive-Unlabeled Graph Classification

The problem of graph classification has drawn much attention in the last decade. Conventional approaches on graph classification focus on mining discriminative subgraph features under supervised settings. The feature selection strategies strictly follow the assumption that both positive and negative graphs exist. However, in many real-world applications, the negative graph examples are not available. In this paper we study the problem of how to select useful subgraph features and perform graph classification based upon only positive and unlabeled graphs. This problem is challenging and different from previous works on PU learning, because there are no predefined features in graph data. Moreover, the subgraph enumeration problem is NP-hard. We need to identify a subset of unlabeled graphs that are most likely to be negative graphs. However, the negative graph selection problem and the subgraph feature selection problem are correlated. Before the reliable negative graphs can be resolved, we need to have a set of useful subgraph features. In order to address this problem, we first derive an evaluation criterion to estimate the dependency between subgraph features and class labels based on a set of estimated negative graphs. In order to build accurate models for the PU learning problem on graph data, we propose an integrated approach to concurrently select the discriminative features and the negative graphs in an iterative manner. Experimental results illustrate the effectiveness and efficiency of the proposed method.