Multi-graph-view subgraph mining for graph classification

详细信息    查看全文

• 作者：Jia Wu ; Zhibin Hong ; Shirui Pan ; Xingquan Zhu…
• 刊名：Knowledge and Information Systems
• 出版年：2016
• 出版时间：July 2016
• 年：2016
• 卷：48
• 期：1
• 页码：29-54
• 全文大小：1,762 KB
• 刊物类别：Computer Science
• 刊物主题：Information Systems and Communication Service
  Business Information Systems
  
• 出版者：Springer London
• ISSN：0219-3116
• 卷排序：48

文摘

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.KeywordsMulti-graph-viewFeature selectionSubgraph miningGraph classification