Positive and unlabeled multi-graph learning

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

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

49 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
Pages (from-to)818-829
Number of pages12
JournalIEEE Transactions on Cybernetics
Issue number4
Publication statusPublished - 1 Apr 2017
Externally publishedYes


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


Dive into the research topics of 'Positive and unlabeled multi-graph learning'. Together they form a unique fingerprint.

Cite this