Boosting for graph classification with universum

Shirui Pan, Jia Wu, Xingquan Zhu, Guodong Long, Chengqi Zhang

Research output: Contribution to journalArticleResearchpeer-review

Abstract

Recent years have witnessed extensive studies of graph classification due to the rapid increase in applications involving structural data and complex relationships. To support graph classification, all existing methods require that training graphs should be relevant (or belong) to the target class, but cannot integrate graphs irrelevant to the class of interest into the learning process. In this paper, we study a new universum graph classification framework which leverages additional “non-example” graphs to help improve the graph classification accuracy. We argue that although universum graphs do not belong to the target class, they may contain meaningful structure patterns to help enrich the feature space for graph representation and classification. To support universum graph classification, we propose a mathematical programming algorithm, ugBoost, which integrates discriminative subgraph selection and margin maximization into a unified framework to fully exploit the universum. Because informative subgraph exploration in a universum setting requires the search of a large space, we derive an upper bound discriminative score for each subgraph and employ a branch-and-bound scheme to prune the search space. By using the explored subgraphs, our graph classification model intends to maximize the margin between positive and negative graphs and minimize the loss on the universum graph examples simultaneously. The subgraph exploration and the learning are integrated and performed iteratively so that each can be beneficial to the other. Experimental results and comparisons on real-world dataset demonstrate the performance of our algorithm.

Original languageEnglish
Pages (from-to)53-77
Number of pages25
JournalKnowledge and Information Systems
Volume50
Issue number1
DOIs
Publication statusPublished - 2017
Externally publishedYes

Keywords

  • Boosting
  • Graph classification
  • Graph mining
  • Supervised learning
  • Universum

Cite this

Pan, Shirui ; Wu, Jia ; Zhu, Xingquan ; Long, Guodong ; Zhang, Chengqi. / Boosting for graph classification with universum. In: Knowledge and Information Systems. 2017 ; Vol. 50, No. 1. pp. 53-77.
@article{1632204ce027477c9c08039d088201cd,
title = "Boosting for graph classification with universum",
abstract = "Recent years have witnessed extensive studies of graph classification due to the rapid increase in applications involving structural data and complex relationships. To support graph classification, all existing methods require that training graphs should be relevant (or belong) to the target class, but cannot integrate graphs irrelevant to the class of interest into the learning process. In this paper, we study a new universum graph classification framework which leverages additional “non-example” graphs to help improve the graph classification accuracy. We argue that although universum graphs do not belong to the target class, they may contain meaningful structure patterns to help enrich the feature space for graph representation and classification. To support universum graph classification, we propose a mathematical programming algorithm, ugBoost, which integrates discriminative subgraph selection and margin maximization into a unified framework to fully exploit the universum. Because informative subgraph exploration in a universum setting requires the search of a large space, we derive an upper bound discriminative score for each subgraph and employ a branch-and-bound scheme to prune the search space. By using the explored subgraphs, our graph classification model intends to maximize the margin between positive and negative graphs and minimize the loss on the universum graph examples simultaneously. The subgraph exploration and the learning are integrated and performed iteratively so that each can be beneficial to the other. Experimental results and comparisons on real-world dataset demonstrate the performance of our algorithm.",
keywords = "Boosting, Graph classification, Graph mining, Supervised learning, Universum",
author = "Shirui Pan and Jia Wu and Xingquan Zhu and Guodong Long and Chengqi Zhang",
year = "2017",
doi = "10.1007/s10115-016-0934-z",
language = "English",
volume = "50",
pages = "53--77",
journal = "Knowledge and Information Systems",
issn = "0219-1377",
publisher = "Springer-Verlag London Ltd.",
number = "1",

}

Boosting for graph classification with universum. / Pan, Shirui; Wu, Jia; Zhu, Xingquan; Long, Guodong; Zhang, Chengqi.

In: Knowledge and Information Systems, Vol. 50, No. 1, 2017, p. 53-77.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Boosting for graph classification with universum

AU - Pan, Shirui

AU - Wu, Jia

AU - Zhu, Xingquan

AU - Long, Guodong

AU - Zhang, Chengqi

PY - 2017

Y1 - 2017

N2 - Recent years have witnessed extensive studies of graph classification due to the rapid increase in applications involving structural data and complex relationships. To support graph classification, all existing methods require that training graphs should be relevant (or belong) to the target class, but cannot integrate graphs irrelevant to the class of interest into the learning process. In this paper, we study a new universum graph classification framework which leverages additional “non-example” graphs to help improve the graph classification accuracy. We argue that although universum graphs do not belong to the target class, they may contain meaningful structure patterns to help enrich the feature space for graph representation and classification. To support universum graph classification, we propose a mathematical programming algorithm, ugBoost, which integrates discriminative subgraph selection and margin maximization into a unified framework to fully exploit the universum. Because informative subgraph exploration in a universum setting requires the search of a large space, we derive an upper bound discriminative score for each subgraph and employ a branch-and-bound scheme to prune the search space. By using the explored subgraphs, our graph classification model intends to maximize the margin between positive and negative graphs and minimize the loss on the universum graph examples simultaneously. The subgraph exploration and the learning are integrated and performed iteratively so that each can be beneficial to the other. Experimental results and comparisons on real-world dataset demonstrate the performance of our algorithm.

AB - Recent years have witnessed extensive studies of graph classification due to the rapid increase in applications involving structural data and complex relationships. To support graph classification, all existing methods require that training graphs should be relevant (or belong) to the target class, but cannot integrate graphs irrelevant to the class of interest into the learning process. In this paper, we study a new universum graph classification framework which leverages additional “non-example” graphs to help improve the graph classification accuracy. We argue that although universum graphs do not belong to the target class, they may contain meaningful structure patterns to help enrich the feature space for graph representation and classification. To support universum graph classification, we propose a mathematical programming algorithm, ugBoost, which integrates discriminative subgraph selection and margin maximization into a unified framework to fully exploit the universum. Because informative subgraph exploration in a universum setting requires the search of a large space, we derive an upper bound discriminative score for each subgraph and employ a branch-and-bound scheme to prune the search space. By using the explored subgraphs, our graph classification model intends to maximize the margin between positive and negative graphs and minimize the loss on the universum graph examples simultaneously. The subgraph exploration and the learning are integrated and performed iteratively so that each can be beneficial to the other. Experimental results and comparisons on real-world dataset demonstrate the performance of our algorithm.

KW - Boosting

KW - Graph classification

KW - Graph mining

KW - Supervised learning

KW - Universum

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

U2 - 10.1007/s10115-016-0934-z

DO - 10.1007/s10115-016-0934-z

M3 - Article

VL - 50

SP - 53

EP - 77

JO - Knowledge and Information Systems

JF - Knowledge and Information Systems

SN - 0219-1377

IS - 1

ER -