Efficient pattern matching for graphs with multi-Labeled nodes

Ali Shemshadi, Quan Z. Sheng, Yongrui Qin

Research output: Contribution to journalArticle

5 Citations (Scopus)

Abstract

Graph matching is important for a wide variety of applications in different domains such as social network analysis and knowledge discovery. Despite extensive research over the last few decades, graph matching is still challenging particularly when it comes with new conditions and constraints. In this paper, we focus on a new class of graph matching, in which each node can accept multiple labels instead of one. In particular, we address the problem of finding the top-k nodes of a data graph which best match a labeled query node from a given pattern graph. We firstly prove this to be an NP-Complete problem. Then, to address this issue and improve the scalability of our approach, we introduce a more flexible graph simulation, namely surjective simulation. This new graph simulation reduces the unnecessary complexity that is due to the unnecessary constraints imposed by the existing definitions while achieving high-quality matching results. In addition, our approach is associated with an early stop strategy to further boost the performance. To approximate the maximum size of a simulation, our approach utilizes Metropolis Hastings algorithm and ranks the top-k matches after computing the set of surjective simulations. The experimental results over social network graphs demonstrate the efficiency of the proposed approach and superiority over existing approaches.

Original languageEnglish
Pages (from-to)256-265
Number of pages10
JournalKnowledge-Based Systems
Volume109
Early online date9 Jul 2016
DOIs
Publication statusPublished - 1 Oct 2016

Fingerprint

Pattern matching
Electric network analysis
Data mining
Scalability
Labels
Computational complexity
Node
Graph
Simulation

Cite this

Shemshadi, Ali ; Sheng, Quan Z. ; Qin, Yongrui. / Efficient pattern matching for graphs with multi-Labeled nodes. In: Knowledge-Based Systems. 2016 ; Vol. 109. pp. 256-265.
@article{a545195c1d7d4aaa8792c3c098a10da6,
title = "Efficient pattern matching for graphs with multi-Labeled nodes",
abstract = "Graph matching is important for a wide variety of applications in different domains such as social network analysis and knowledge discovery. Despite extensive research over the last few decades, graph matching is still challenging particularly when it comes with new conditions and constraints. In this paper, we focus on a new class of graph matching, in which each node can accept multiple labels instead of one. In particular, we address the problem of finding the top-k nodes of a data graph which best match a labeled query node from a given pattern graph. We firstly prove this to be an NP-Complete problem. Then, to address this issue and improve the scalability of our approach, we introduce a more flexible graph simulation, namely surjective simulation. This new graph simulation reduces the unnecessary complexity that is due to the unnecessary constraints imposed by the existing definitions while achieving high-quality matching results. In addition, our approach is associated with an early stop strategy to further boost the performance. To approximate the maximum size of a simulation, our approach utilizes Metropolis Hastings algorithm and ranks the top-k matches after computing the set of surjective simulations. The experimental results over social network graphs demonstrate the efficiency of the proposed approach and superiority over existing approaches.",
keywords = "Graph matching, Graph simulation, Metropolis hastings, Multi-labeled graph",
author = "Ali Shemshadi and Sheng, {Quan Z.} and Yongrui Qin",
note = "No Full Text in Eprints. HN 17/10/2017",
year = "2016",
month = "10",
day = "1",
doi = "10.1016/j.knosys.2016.07.009",
language = "English",
volume = "109",
pages = "256--265",
journal = "Knowledge-Based Systems",
issn = "0950-7051",
publisher = "Elsevier",

}

Efficient pattern matching for graphs with multi-Labeled nodes. / Shemshadi, Ali; Sheng, Quan Z.; Qin, Yongrui.

In: Knowledge-Based Systems, Vol. 109, 01.10.2016, p. 256-265.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Efficient pattern matching for graphs with multi-Labeled nodes

AU - Shemshadi, Ali

AU - Sheng, Quan Z.

AU - Qin, Yongrui

N1 - No Full Text in Eprints. HN 17/10/2017

PY - 2016/10/1

Y1 - 2016/10/1

N2 - Graph matching is important for a wide variety of applications in different domains such as social network analysis and knowledge discovery. Despite extensive research over the last few decades, graph matching is still challenging particularly when it comes with new conditions and constraints. In this paper, we focus on a new class of graph matching, in which each node can accept multiple labels instead of one. In particular, we address the problem of finding the top-k nodes of a data graph which best match a labeled query node from a given pattern graph. We firstly prove this to be an NP-Complete problem. Then, to address this issue and improve the scalability of our approach, we introduce a more flexible graph simulation, namely surjective simulation. This new graph simulation reduces the unnecessary complexity that is due to the unnecessary constraints imposed by the existing definitions while achieving high-quality matching results. In addition, our approach is associated with an early stop strategy to further boost the performance. To approximate the maximum size of a simulation, our approach utilizes Metropolis Hastings algorithm and ranks the top-k matches after computing the set of surjective simulations. The experimental results over social network graphs demonstrate the efficiency of the proposed approach and superiority over existing approaches.

AB - Graph matching is important for a wide variety of applications in different domains such as social network analysis and knowledge discovery. Despite extensive research over the last few decades, graph matching is still challenging particularly when it comes with new conditions and constraints. In this paper, we focus on a new class of graph matching, in which each node can accept multiple labels instead of one. In particular, we address the problem of finding the top-k nodes of a data graph which best match a labeled query node from a given pattern graph. We firstly prove this to be an NP-Complete problem. Then, to address this issue and improve the scalability of our approach, we introduce a more flexible graph simulation, namely surjective simulation. This new graph simulation reduces the unnecessary complexity that is due to the unnecessary constraints imposed by the existing definitions while achieving high-quality matching results. In addition, our approach is associated with an early stop strategy to further boost the performance. To approximate the maximum size of a simulation, our approach utilizes Metropolis Hastings algorithm and ranks the top-k matches after computing the set of surjective simulations. The experimental results over social network graphs demonstrate the efficiency of the proposed approach and superiority over existing approaches.

KW - Graph matching

KW - Graph simulation

KW - Metropolis hastings

KW - Multi-labeled graph

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

U2 - 10.1016/j.knosys.2016.07.009

DO - 10.1016/j.knosys.2016.07.009

M3 - Article

VL - 109

SP - 256

EP - 265

JO - Knowledge-Based Systems

JF - Knowledge-Based Systems

SN - 0950-7051

ER -