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

14 Citations (Scopus)

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