CoSimRank: A Flexible & Efficient Graph-Theoretic Similarity Measure

Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics, pages 1392–1402, Baltimore, Maryland, USA, June 23-25 2014. c⃝2014 Association for Computational Linguistics CoSimRank: A Flexible & Efficient Graph-Theoretic Similarity Measure Sascha Rothe and Hinrich Sch¨utze Center for Information & Language Processing University of Munich sascha@cis.lmu.de Abstract We present CoSimRank, a graph-theoretic similarity measure that is efficient because it can compute a single node similarity without having to compute the similarities of the entire graph. We present equivalent formalizations that show CoSimRank’s close relationship to Personalized Page- Rank and SimRank and also show how we can take advantage of fast matrix mul- tiplication algorithms to compute CoSim- Rank. Another advantage of CoSimRank is that it can be flexibly extended from ba- sic node-node similarity to several other graph-theoretic similarity measures. In an experimental evaluation on the tasks of synonym extraction and bilingual lexicon extraction, CoSimRank is faster or more accurate than previous approaches. 1 Introduction Graph-theoretic algorithms have been successfully applied to many problems in NLP (Mihalcea and Radev, 2011). These algorithms are often based on PageRank (Brin and Page, 1998) and other central- ity measures (e.g., (Erkan and Radev, 2004)). An alternative for tasks involving similarity is Sim- Rank (Jeh and Widom, 2002). SimRank is based on the simple intuition that nodes in a graph should be considered as similar to the extent that their neighbors are similar. Unfortunately, SimRank has time complexity O(n3) (where n is the num- ber of nodes in the graph) and therefore does not scale to the large graphs that are typical of NLP. This paper introduces CoSimRank,1 a new graph-theoretic algorithm for computing node similarity that combines features of SimRank and PageRank. Our key observation is that to compute the similarity of two nodes, we need not consider 1Code available at code.google.com/p/cistern all other nodes in the graph as SimRank does; in- stead, CoSimRank starts random walks from the two nodes and computes their similarity at each time step. This offers large savings in computa- tion time if we only need the similarities of a small subset of all n2 node similarities. These two cases – computing a few similari- ties and computing many similarities – correspond to two different representations we can compute CoSimRank on: a vector representation, which is fast for only a few similarities, and a matrix repre- sentation, which can take advantage of fast matrix multiplication algorithms. CoSimRank can be used to compute many vari- ations of basic node similarity – including similar- ity for graphs with weighted and typed edges and similarity for sets of nodes. Thus, CoSimRank has the added advantage of being a flexible tool for dif- ferent types of applications. The extension of CoSimRank to similarity across graphs is important for the application of bilingual lexicon extraction: given a set of corre- spondences between nodes in two graphs A and B (corresponding to two different languages), a pair of nodes (a ∈ A, b ∈ B) is a good candidate for a translation …

Content truncated to 500 words