Multi-graph-view subgraph mining for graph classification

Jia Wu, Zhibin Hong, Shirui Pan, Xingquan Zhu, Zhihua Cai, Chengqi Zhang

Research output: Contribution to journalArticleResearchpeer-review

Abstract

In this paper, we formulate a new multi-graph-view learning task, where each object to be classified contains graphs from multiple graph-views. This problem setting is essentially different from traditional single-graph-view graph classification, where graphs are collected from one single-feature view. To solve the problem, we propose a cross graph-view subgraph feature-based learning algorithm that explores an optimal set of subgraphs, across multiple graph-views, as features to represent graphs. Specifically, we derive an evaluation criterion to estimate the discriminative power and redundancy of subgraph features across all views, with a branch-and-bound algorithm being proposed to prune subgraph search space. Because graph-views may complement each other and play different roles in a learning task, we assign each view with a weight value indicating its importance to the learning task and further use an optimization process to find optimal weight values for each graph-view. The iteration between cross graph-view subgraph scoring and graph-view weight updating forms a closed loop to find optimal subgraphs to represent graphs for multi-graph-view learning. Experiments and comparisons on real-world tasks demonstrate the algorithm’s superior performance.

Original languageEnglish
Pages (from-to)29-54
Number of pages26
JournalKnowledge and Information Systems
Volume48
Issue number1
DOIs
Publication statusPublished - Jul 2016
Externally publishedYes

Keywords

  • Feature selection
  • Graph classification
  • Multi-graph-view
  • Subgraph mining

Cite this

Wu, Jia ; Hong, Zhibin ; Pan, Shirui ; Zhu, Xingquan ; Cai, Zhihua ; Zhang, Chengqi. / Multi-graph-view subgraph mining for graph classification. In: Knowledge and Information Systems. 2016 ; Vol. 48, No. 1. pp. 29-54.
@article{b0cc0a7a5cdf4eab842dd31c9a3016e7,
title = "Multi-graph-view subgraph mining for graph classification",
abstract = "In this paper, we formulate a new multi-graph-view learning task, where each object to be classified contains graphs from multiple graph-views. This problem setting is essentially different from traditional single-graph-view graph classification, where graphs are collected from one single-feature view. To solve the problem, we propose a cross graph-view subgraph feature-based learning algorithm that explores an optimal set of subgraphs, across multiple graph-views, as features to represent graphs. Specifically, we derive an evaluation criterion to estimate the discriminative power and redundancy of subgraph features across all views, with a branch-and-bound algorithm being proposed to prune subgraph search space. Because graph-views may complement each other and play different roles in a learning task, we assign each view with a weight value indicating its importance to the learning task and further use an optimization process to find optimal weight values for each graph-view. The iteration between cross graph-view subgraph scoring and graph-view weight updating forms a closed loop to find optimal subgraphs to represent graphs for multi-graph-view learning. Experiments and comparisons on real-world tasks demonstrate the algorithm’s superior performance.",
keywords = "Feature selection, Graph classification, Multi-graph-view, Subgraph mining",
author = "Jia Wu and Zhibin Hong and Shirui Pan and Xingquan Zhu and Zhihua Cai and Chengqi Zhang",
year = "2016",
month = "7",
doi = "10.1007/s10115-015-0872-1",
language = "English",
volume = "48",
pages = "29--54",
journal = "Knowledge and Information Systems",
issn = "0219-1377",
publisher = "Springer-Verlag London Ltd.",
number = "1",

}

Multi-graph-view subgraph mining for graph classification. / Wu, Jia; Hong, Zhibin; Pan, Shirui; Zhu, Xingquan; Cai, Zhihua; Zhang, Chengqi.

In: Knowledge and Information Systems, Vol. 48, No. 1, 07.2016, p. 29-54.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Multi-graph-view subgraph mining for graph classification

AU - Wu, Jia

AU - Hong, Zhibin

AU - Pan, Shirui

AU - Zhu, Xingquan

AU - Cai, Zhihua

AU - Zhang, Chengqi

PY - 2016/7

Y1 - 2016/7

N2 - In this paper, we formulate a new multi-graph-view learning task, where each object to be classified contains graphs from multiple graph-views. This problem setting is essentially different from traditional single-graph-view graph classification, where graphs are collected from one single-feature view. To solve the problem, we propose a cross graph-view subgraph feature-based learning algorithm that explores an optimal set of subgraphs, across multiple graph-views, as features to represent graphs. Specifically, we derive an evaluation criterion to estimate the discriminative power and redundancy of subgraph features across all views, with a branch-and-bound algorithm being proposed to prune subgraph search space. Because graph-views may complement each other and play different roles in a learning task, we assign each view with a weight value indicating its importance to the learning task and further use an optimization process to find optimal weight values for each graph-view. The iteration between cross graph-view subgraph scoring and graph-view weight updating forms a closed loop to find optimal subgraphs to represent graphs for multi-graph-view learning. Experiments and comparisons on real-world tasks demonstrate the algorithm’s superior performance.

AB - In this paper, we formulate a new multi-graph-view learning task, where each object to be classified contains graphs from multiple graph-views. This problem setting is essentially different from traditional single-graph-view graph classification, where graphs are collected from one single-feature view. To solve the problem, we propose a cross graph-view subgraph feature-based learning algorithm that explores an optimal set of subgraphs, across multiple graph-views, as features to represent graphs. Specifically, we derive an evaluation criterion to estimate the discriminative power and redundancy of subgraph features across all views, with a branch-and-bound algorithm being proposed to prune subgraph search space. Because graph-views may complement each other and play different roles in a learning task, we assign each view with a weight value indicating its importance to the learning task and further use an optimization process to find optimal weight values for each graph-view. The iteration between cross graph-view subgraph scoring and graph-view weight updating forms a closed loop to find optimal subgraphs to represent graphs for multi-graph-view learning. Experiments and comparisons on real-world tasks demonstrate the algorithm’s superior performance.

KW - Feature selection

KW - Graph classification

KW - Multi-graph-view

KW - Subgraph mining

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

U2 - 10.1007/s10115-015-0872-1

DO - 10.1007/s10115-015-0872-1

M3 - Article

VL - 48

SP - 29

EP - 54

JO - Knowledge and Information Systems

JF - Knowledge and Information Systems

SN - 0219-1377

IS - 1

ER -