Query from Sketch: A Common Subgraph Correspondence Mining Framework

摘要

We investigate a subgraph mining framework, that can connect similar entities according to their structure and attribute similarities. We take one mapping between two related points chosen from the query and target graph as one vertex in the correspondence graph and decide the weight of the edge based on the similarity score. In this way, we transform the problem to a dense subgraph discovery problem. To adapt this method to large scale, we choose the candidate group by some effective pruning methods. We also add some techniques to make our method more flexible to fit uncertain user sketched input. We investigate how changes to certain parameters in the algorithm can influence the results. By integrating all these adjustments into the framework, we can provide a method that exhibits both accuracy and flexibility in many situations with a degree of generality. Experiments on both certain and uncertain query graphs can give satisfactory and informative results.