Home // DBKDA 2016, The Eighth International Conference on Advances in Databases, Knowledge, and Data Applications // View article

Subgraph Similarity Search in Large Graphs

Authors:
Kanigalpula Samanvi
Naveen Sivadasan

Keywords: Similarity Search; Subgraph Similarity Search; Graph Kernel; Nearest Neighbors Search.

Abstract:
One of the major challenges in applications related to social networks, computational biology, collaboration networks, etc., is to efficiently search for similar patterns in their underlying graphs. These graphs are typically noisy and contain thousands of vertices and millions of edges. In many cases, the graphs are unlabeled and the notion of similarity is also not well defined. We study the problem of searching an induced subgraph in a large target graph that is most similar to the given query graph. We assume that the query graph and target graph are undirected and unlabeled. We use graphlet kernels to define graph similarity. Our algorithm maps topological neighborhood information of vertices in the query and target graphs to vectors and these local information are combined to find global similarity. We conduct experiments on several real world networks and we show that our algorithm is able to detect highly similar matches when queried in these networks. Our implementation takes about one second to find matches on graphs containing thousands of vertices and million edges, excluding the time for one time pre-processing. Computationally expensive parts of our algorithm can be further scaled to standard parallel and distributed frameworks.

Pages: 84 to 93

Copyright: Copyright (c) IARIA, 2016

Publication date: June 26, 2016

Published in: conference

ISSN: 2308-4332

ISBN: 978-1-61208-486-2

Location: Lisbon, Portugal

Dates: from June 26, 2016 to June 30, 2016