Multi-graph-view subgraph mining for graph classification

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 vi...

Full description

Saved in:
Bibliographic Details
Published in:Knowledge and information systems 2016-07, Vol.48 (1), p.29-54
Main Authors: Wu, Jia, Hong, Zhibin, Pan, Shirui, Zhu, Xingquan, Cai, Zhihua, Zhang, Chengqi
Format: Article
Language:English
Subjects:
Algorithms
Analysis
Artificial intelligence
Classification
Computer Science
Computers
Data Mining and Knowledge Discovery
Database Management
Design
Feature selection
Graph theory
Graphs
Image retrieval
Information Storage and Retrieval
Information systems
Information Systems and Communication Service
Information Systems Applications (incl.Internet)
IT in Business
Learning
Methods
Mining
Optimization
Regular Paper
Scoring
Studies
Tasks
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0219-1377
0219-3116
DOI:10.1007/s10115-015-0872-1