Can I read NeMa: fast graph search with label similarity on EtoBox?

NeMa: fast graph search with label similarity by Khan, Arijit; Wu, Yinghui; Aggarwal, Charu C.; Yan, Xifeng is a Computer Science article available to read on EtoBox.

What is NeMa: fast graph search with label similarity about?

It is increasingly common to find real-life data represented as networks of labeled, heterogeneous entities. To query these networks, one often needs to identify the matches of a given query graph in a (typically large) network modeled as a target graph. Due to noise and the lack of fixed schema in the target graph, the query graph can substantially differ from its matches in the target graph in both structure and node labels, thus bringing challenges to the graph querying tasks. In this paper, we propose NeMa (Network Match), a neighborhood-based subgraph matching technique for querying real-life networks. (1) To measure the quality of the match, we propose a novel subgraph matching cost metric that aggregates the costs of matching individual nodes, and unifies both structure and node label similarities. (2) Based on the metric, we formulate the minimum cost subgraph matching problem. Given a query graph and a target graph, the problem is to identify the (top- k ) matches of the query graph with minimum costs in the target graph. We show that the problem is NP-hard, and also hard to approximate. (3) We propose a heuristic algorithm for solving the problem based on an inference mod

Who reads NeMa: fast graph search with label similarity?

Author

Khan, Arijit; Wu, Yinghui; Aggarwal, Charu C.; Yan, Xifeng

Publisher

Very Large Data Base Endowment Inc. (ISSN 2150-8097)

Published

2013

Language

EN

Field

Computer Science (Physical Sciences)