Subgraph Similarity Search in Large Graphs

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 unlabelled and the notion of similarity is also not well defined. We study the problem of searching an induced sub graph 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 unlabelled. We use graph let kernels [1] to define graph similarity. Graph let kernels are known to perform better than other kernels in different applications