Bag constrained structure pattern mining for multi-graph classification

Jia Wu, Xingquan Zhu, Chengqi Zhang, Philip S. Yu

Research output: Contribution to journalArticle

94 Citations (Scopus)


This paper formulates a multi-graph learning task. In our problem setting, a bag contains a number of graphs and a class label. A bag is labeled positive if at least one graph in the bag is positive, and negative otherwise. In addition, the genuine label of each graph in a positive bag is unknown, and all graphs in a negative bag are negative. The aim of multi-graph learning is to build a learning model from a number of labeled training bags to predict previously unseen test bags with maximum accuracy. This problem setting is essentially different from existing multi-instance learning (MIL), where instances in MIL share
well-defined feature values, but no features are available to represent graphs in a multi-graph bag. To solve the problem, we propose a Multi-Graph Feature based Learning (gMGFL) algorithm that explores and selects a set of discriminative subgraphs as features to transfer each bag into a single instance, with the bag label being propagated to the transferred instance. As a result, the multi-graph bags form a labeled training instance set, so generic learning algorithms, such as decision trees, can be used to derive learning models for multi-graph classification. Experiments and comparisons on real-world multi-graph tasks demonstrate the algorithm performance.
Original languageEnglish
Pages (from-to)2382-2396
Number of pages15
JournalIEEE Transactions on Knowledge and Data Engineering
Issue number10
Publication statusPublished - 1 Oct 2014
Externally publishedYes


  • data mining
  • graph theory
  • learning (artificial intelligence)
  • pattern classification
  • bag constrained structure pattern mining
  • multigraph classification
  • multigraph learning task
  • class label
  • multigraph learning model
  • labeled training bags
  • multiinstance learning
  • MIL
  • multigraph bag
  • multigraph feature based learning algorithm
  • gMGFL algorithm
  • discriminative subgraphs
  • bag label
  • labeled training instance set
  • decision trees
  • Training
  • Laplace equations
  • Electronic mail
  • Supervised learning
  • Graph classification
  • multi-instance learning
  • multi-graph, subgraph features
  • multi-graph
  • subgraph features

Fingerprint Dive into the research topics of 'Bag constrained structure pattern mining for multi-graph classification'. Together they form a unique fingerprint.

Cite this