Positive and unlabeled multi-graph learning

Jia Wu, Shirui Pan, Xingquan Zhu, Chengqi Zhang, Xindong Wu

Research output: Contribution to journalArticleResearchpeer-review

37 Citations (Scopus)


In this paper, we advance graph classification to handle multi-graph learning for complicated objects, where each object is represented as a bag of graphs and the label is only available to each bag but not individual graphs. In addition, when training classifiers, users are only given a handful of positive bags and many unlabeled bags, and the learning objective is to train models to classify previously unseen graph bags with maximum accuracy. To achieve the goal, we propose a positive and unlabeled multi-graph learning (puMGL) framework to first select informative subgraphs to convert graphs into a feature space. To utilize unlabeled bags for learning, puMGL assigns a confidence weight to each bag and dynamically adjusts its weight value to select 'reliable negative bags.' A number of representative graphs, selected from positive bags and identified reliable negative graph bags, form a 'margin graph pool' which serves as the base for deriving subgraph patterns, training graph classifiers, and further updating the bag weight values. A closed-loop iterative process helps discover optimal subgraphs from positive and unlabeled graph bags for learning. Experimental comparisons demonstrate the performance of puMGL for classifying real-world complicated objects.

Original languageEnglish
Article number7439802
Pages (from-to)818-829
Number of pages12
JournalIEEE Transactions on Cybernetics
Issue number4
Publication statusPublished - Apr 2017
Externally publishedYes


  • Classification
  • features
  • Graph
  • multi-instance (MI)
  • positive and unlabeled (PU) learning
  • subgraph

Cite this