Toward representation independent similarity search

Finding similar entities over data graphs is an important problem with many applications. Current similarity search algorithms use intuitively appealing heuristics that leverage the link information in the data graph to quantify the de-gree of similarity between its entities. In this paper, using examples from real-world data sets, we show that people represent the same information using data graphs with dif-ferent shapes. We argue that in order for a similarity search algorithm to be usable and effective, it should be repre-sentation independent: it should return essentially the same answers for a query over different graphs that represent the same information. We formalize this property and show that the outcome of current similarity search algorithms de-pend highly on data representation. Hence, they may be effective on some datasets and ineffective over others. We also perform an empirical study and analyze the sensitivity of current methods against changes in data representation. Our results indicate that the output of these algorithms are highly affected by changes in data representation. 1