Bag Constrained Structure Pattern Mining for Multi-Graph Classification

Publication Type:
Journal Article
Citation:
IEEE Transactions on Knowledge and Data Engineering, 2014, 26 (10), pp. 2382 - 2396
Issue Date:
2014-10-01
Filename Description Size
Thumbnailtkde.pdfPublished Version2.3 MB
Adobe PDF
Full metadata record
© 1989-2012 IEEE. 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.
Please use this identifier to cite or link to this item: