Multi-graph-view subgraph mining for graph classification

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

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

21 Citations (Scopus)


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
Issue number1
Publication statusPublished - 1 Jul 2016
Externally publishedYes


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


Dive into the research topics of 'Multi-graph-view subgraph mining for graph classification'. Together they form a unique fingerprint.

Cite this