Boosting for multi-graph classification

Jia Wu, Shirui Pan, Xingquan Zhu, Zhihua Cai

Research output: Contribution to journalArticleResearchpeer-review

Abstract

In this paper, we formulate a novel graph-based learning problem, multi-graph classification (MGC), which aims to learn a classifier from a set of labeled bags each containing a number of graphs inside the bag. A bag is labeled positive, if at least one graph in the bag is positive, and negative otherwise. Such a multi-graph representation can be used for many real-world applications, such as webpage classification, where a webpage can be regarded as a bag with texts and images inside the webpage being represented as graphs. This problem is a generalization of multi-instance learning (MIL) but with vital differences, mainly because instances in MIL share a common feature space whereas no feature is available to represent graphs in a multi-graph bag. To solve the problem, we propose a boosting based multi-graph classification framework (bMGC). Given a set of labeled multi-graph bags, bMGC employs dynamic weight adjustment at both bag- and graph-levels to select one subgraph in each iteration as a weak classifier. In each iteration, bag and graph weights are adjusted such that an incorrectly classified bag will receive a higher weight because its predicted bag label conflicts to the genuine label, whereas an incorrectly classified graph will receive a lower weight value if the graph is in a positive bag (or a higher weight if the graph is in a negative bag). Accordingly, bMGC is able to differentiate graphs in positive and negative bags to derive effective classifiers to form a boosting model for MGC. Experiments and comparisons on real-world multi-graph learning tasks demonstrate the algorithm performance.

Original languageEnglish
Article number06848779
Pages (from-to)430-443
Number of pages14
JournalIEEE Transactions on Cybernetics
Volume45
Issue number3
DOIs
Publication statusPublished - Mar 2015
Externally publishedYes

Keywords

  • Boosting
  • graph classification
  • multi-graph
  • multi-instance learning
  • subgraph mining

Cite this

Wu, Jia ; Pan, Shirui ; Zhu, Xingquan ; Cai, Zhihua. / Boosting for multi-graph classification. In: IEEE Transactions on Cybernetics. 2015 ; Vol. 45, No. 3. pp. 430-443.
@article{b659c7ff5c4a42979fd6464b4fddd124,
title = "Boosting for multi-graph classification",
abstract = "In this paper, we formulate a novel graph-based learning problem, multi-graph classification (MGC), which aims to learn a classifier from a set of labeled bags each containing a number of graphs inside the bag. A bag is labeled positive, if at least one graph in the bag is positive, and negative otherwise. Such a multi-graph representation can be used for many real-world applications, such as webpage classification, where a webpage can be regarded as a bag with texts and images inside the webpage being represented as graphs. This problem is a generalization of multi-instance learning (MIL) but with vital differences, mainly because instances in MIL share a common feature space whereas no feature is available to represent graphs in a multi-graph bag. To solve the problem, we propose a boosting based multi-graph classification framework (bMGC). Given a set of labeled multi-graph bags, bMGC employs dynamic weight adjustment at both bag- and graph-levels to select one subgraph in each iteration as a weak classifier. In each iteration, bag and graph weights are adjusted such that an incorrectly classified bag will receive a higher weight because its predicted bag label conflicts to the genuine label, whereas an incorrectly classified graph will receive a lower weight value if the graph is in a positive bag (or a higher weight if the graph is in a negative bag). Accordingly, bMGC is able to differentiate graphs in positive and negative bags to derive effective classifiers to form a boosting model for MGC. Experiments and comparisons on real-world multi-graph learning tasks demonstrate the algorithm performance.",
keywords = "Boosting, graph classification, multi-graph, multi-instance learning, subgraph mining",
author = "Jia Wu and Shirui Pan and Xingquan Zhu and Zhihua Cai",
year = "2015",
month = "3",
doi = "10.1109/TCYB.2014.2327111",
language = "English",
volume = "45",
pages = "430--443",
journal = "IEEE Transactions on Cybernetics",
issn = "2168-2267",
number = "3",

}

Boosting for multi-graph classification. / Wu, Jia; Pan, Shirui; Zhu, Xingquan; Cai, Zhihua.

In: IEEE Transactions on Cybernetics, Vol. 45, No. 3, 06848779, 03.2015, p. 430-443.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Boosting for multi-graph classification

AU - Wu, Jia

AU - Pan, Shirui

AU - Zhu, Xingquan

AU - Cai, Zhihua

PY - 2015/3

Y1 - 2015/3

N2 - In this paper, we formulate a novel graph-based learning problem, multi-graph classification (MGC), which aims to learn a classifier from a set of labeled bags each containing a number of graphs inside the bag. A bag is labeled positive, if at least one graph in the bag is positive, and negative otherwise. Such a multi-graph representation can be used for many real-world applications, such as webpage classification, where a webpage can be regarded as a bag with texts and images inside the webpage being represented as graphs. This problem is a generalization of multi-instance learning (MIL) but with vital differences, mainly because instances in MIL share a common feature space whereas no feature is available to represent graphs in a multi-graph bag. To solve the problem, we propose a boosting based multi-graph classification framework (bMGC). Given a set of labeled multi-graph bags, bMGC employs dynamic weight adjustment at both bag- and graph-levels to select one subgraph in each iteration as a weak classifier. In each iteration, bag and graph weights are adjusted such that an incorrectly classified bag will receive a higher weight because its predicted bag label conflicts to the genuine label, whereas an incorrectly classified graph will receive a lower weight value if the graph is in a positive bag (or a higher weight if the graph is in a negative bag). Accordingly, bMGC is able to differentiate graphs in positive and negative bags to derive effective classifiers to form a boosting model for MGC. Experiments and comparisons on real-world multi-graph learning tasks demonstrate the algorithm performance.

AB - In this paper, we formulate a novel graph-based learning problem, multi-graph classification (MGC), which aims to learn a classifier from a set of labeled bags each containing a number of graphs inside the bag. A bag is labeled positive, if at least one graph in the bag is positive, and negative otherwise. Such a multi-graph representation can be used for many real-world applications, such as webpage classification, where a webpage can be regarded as a bag with texts and images inside the webpage being represented as graphs. This problem is a generalization of multi-instance learning (MIL) but with vital differences, mainly because instances in MIL share a common feature space whereas no feature is available to represent graphs in a multi-graph bag. To solve the problem, we propose a boosting based multi-graph classification framework (bMGC). Given a set of labeled multi-graph bags, bMGC employs dynamic weight adjustment at both bag- and graph-levels to select one subgraph in each iteration as a weak classifier. In each iteration, bag and graph weights are adjusted such that an incorrectly classified bag will receive a higher weight because its predicted bag label conflicts to the genuine label, whereas an incorrectly classified graph will receive a lower weight value if the graph is in a positive bag (or a higher weight if the graph is in a negative bag). Accordingly, bMGC is able to differentiate graphs in positive and negative bags to derive effective classifiers to form a boosting model for MGC. Experiments and comparisons on real-world multi-graph learning tasks demonstrate the algorithm performance.

KW - Boosting

KW - graph classification

KW - multi-graph

KW - multi-instance learning

KW - subgraph mining

UR - http://www.scopus.com/inward/record.url?scp=85027920186&partnerID=8YFLogxK

U2 - 10.1109/TCYB.2014.2327111

DO - 10.1109/TCYB.2014.2327111

M3 - Article

VL - 45

SP - 430

EP - 443

JO - IEEE Transactions on Cybernetics

JF - IEEE Transactions on Cybernetics

SN - 2168-2267

IS - 3

M1 - 06848779

ER -