CoSimRank: A Flexible & Efficient Graph-Theoretic Similarity Measure

Haveliwala (2002) introduced Personalized PageRank – or topic-sensitive PageRank – based on the idea that the uniform damping vector $p^{\left(0\right)}$ can be replaced by a personalized vector, which depends on node $i$. We usually set $p^{\left(0\right)}\left(i\right)=e_i$, with $e_i$ being a vector of the standard basis, i.e., the $i{}^{\text{th}}$ entry is 1 and all other entries are 0. The PPR vector of node $i$ is given by:

where $A$ is the stochastic matrix of the Markov chain, i.e., the row normalized adjacency matrix. The damping factor $d\in \left(0,1\right)$ ensures that the computation converges. The PPR vector after $k$ iterations is given by $p^{\left(k\right)}$.

To visualize this formula, one can imagine a random surfer starting at node $i$ and following one of the links with probability $d$ or jumping back to the starting node $i$ with probability $\left(1-d\right)$. Entry $i$ of the converged PPR vector represents the probability that the random surfer is on node $i$ after an unlimited number of steps.

To simulate the behavior of SimRank we will simplify this equation and set the damping factor $d=1$. We will re-add a damping factor later in the calculation.

Note that the personalization vector $p^{\left(0\right)}$ was eliminated, but is still present as the starting vector of the iteration.

Let $p\left(i\right)$ be the PPR vector of node $i$. The cosine of two vectors $u$ and $v$ is computed by dividing the inner product $⟨u,v⟩$ by the lengths of the vectors. The cosine of two PPR vectors can be used as a similarity measure for the corresponding nodes [12, 1]:

This measure $s\left(i,j\right)$ looks at the probability that a random walker is on a certain edge after an unlimited number of steps. This is potentially problematic as the example in Figure 1 shows. The PPR vectors of suit and dress will have some weight on tailor, which is good. However, the PPR vector of law will also have a non-zero weight for tailor. So law and dress are similar because of the node tailor. This is undesirable.

We can prevent this type of spurious similarity by taking into account the path the random surfer took to get to a particular node. We formalize this by defining CoSimRank $s\left(i,j\right)$ as follows:

where $p^{\left(k\right)}\left(i\right)$ is the PPR vector of node $i$ from Eq. 2 after $k$ iterations. We compare the PPR vectors at each time step $k$. The sum of all similarities is the value of CoSimRank, i.e., the final similarity. We add a damping factor $c$, so that early meetings are more valuable than later meetings.

To compute the similarity of two vectors $u$ and $v$ we use the inner product $⟨\cdot ,\cdot ⟩$ in Eq. 4 for two reasons:

1. 1.

   This is similar to cosine similarity except that the 1-norm is used instead of the 2-norm. Since our vectors are probability vectors, we have

   $$\frac{⟨p\left(i\right),p\left(j\right)⟩}{\left|p\left(i\right)\right|\left|p\left(j\right)\right|}=⟨p\left(i\right),p\left(j\right)⟩$$

   for the 1-norm.³³This type of similarity measure has also been used and investigated by Ó Séaghdha and Copestake (2008), Cha (2007), Jebara et al. (2004) (probability product kernel) and [13] (Fisher kernel) among others.

2. 2.

   Without expensive normalization, we can give a simple matrix formalization of CoSimRank and compute it efficiently using fast matrix multiplication algorithms.

Later on, the following iterative computation of CoSimRank will prove useful:

The matrix formulation of CoSimRank is:

We will see in Section 5 that this formulation is the basis for a very efficient version of CoSimRank.

As the PPR vectors have only positive values, we can easily see in Eq. 4 that the CoSimRank of one node pair is monotonically non-decreasing. For the dot product of two vectors, the Cauchy-Schwarz inequality gives the upper bound:

where $\parallel x\parallel$ is the norm of $x$. From Eq. 2 we get ${\parallel p^{\left(k\right)}\parallel }_1=1$, where $\parallel \cdot {\parallel }_1$ is the 1-norm. We also know from elementary functional analysis that the 1-norm is the biggest of all p-norms and so one has $\parallel p^{\left(k\right)}\parallel \le 1$. It follows that CoSimRank grows more slowly than a geometric series and converges if :

If an upper bound of $1$ is desired for $s\left(i,j\right)$ (instead of $1/\left(1-c\right)$), then we can use $s^{\prime }$:

The use of weighted edges was first proposed in the PageRank patent. It is straightforward and easy to implement by replacing the row normalized adjacency matrix $A$ with an arbitrary stochastic matrix $P$. We can use this edge weighted PageRank for CoSimRank.

We often want to compute the similarity of nodes in two different graphs with a known node-node correspondence; this is the scenario we are faced with in the lexicon extraction task (see Section 6). A variant of SimRank for this task was presented by Dorow et al. (2009). We will now present an equivalent method for CoSimRank. We denote the number of nodes in the two graphs $U$ and $V$ by $\left|U\right|$ and $\left|V\right|$, respectively. We compute PPR vectors $p\in {ℝ}^{\left|U\right|}$ and $q\in {ℝ}^{\left|V\right|}$ for each graph. Let $S^{\left(0\right)}\in {ℝ}^{\left|U\right|\times \left|V\right|}$ be the known node-node correspondences. The analog of CoSimRank (Eq. 4) for two graphs is then:

The matrix formulation (cf. Eq. 6) is:

where $A$ and $B$ are row-normalized adjacency matrices. We can interpret $S^{\left(0\right)}$ as a change of basis. A similar approach for word embeddings was published by Mikolov et al. (2013). They call $S^{\left(0\right)}$ the translation matrix.

To be able to directly compare to prior work in our experiments, we also present a method to integrate a set of typed edges $𝒯$ in the CoSimRank calculation. For this we will compute a similarity matrix for each edge type $\tau$ and merge them into one matrix for the next iteration:

This formula is identical to the random surfer model where two surfers only meet iff they are on the same node and used the same edge type to get there. A more strict claim would be to use the same edge type at any time of their journey:

We will not use Eq. 5.3 due to its space complexity.

CoSimRank can also be used to compute the similarity $s\left(V,W\right)$ of two sets $V$ and $W$ of nodes, e.g., short text snippets. We are not including this method in our experiments, but we will give the equation here, as traditional document similarity measures (e.g., cosine similarity) perform poorly on this task although there also are known alternatives with good results [30]. For a set $V$, the initial PPR vector is given by:

We then reuse Eq. 4 to compute $s\left(V,W\right)$:

In summary, modifications proposed for SimRank (weighted and typed edges, similarity across graphs) as well as modifications proposed for PageRank (sets of nodes) can also be applied to CoSimRank. This makes CoSimRank a very flexible similarity measure.

We will test the first three extensions experimentally in the next section and leave similarity of node sets for future work.

We propose CoSimRank as an efficient algorithm for computing the similarity of nodes in a graph. Consequently, we compare against the two main methods for this task in NLP: SimRank and extensions of PageRank.

We also compare against the MEE (Multi-Edge Extraction) variant of SimRank [6], which handles labeled edges more efficiently than SimRank:

where $A_{\tau }$ is the row-normalized adjacency matrix for edge type $\tau$ (see edge types in Table 1).

Apart from SimRank, extensions of PageRank are the main methods for computing the similarity of nodes in graphs in NLP (e.g., Hughes and Ramage (2007), Agirre et al. (2009) and other papers discussed in related work). Generally, these methods compute the Personalized PageRank for each node (see Eq. 1). When the computation has converged, the similarity of two nodes is given by the cosine similarity of the Personalized PageRank vectors. We implemented this method for our experiments and call it PPR+cos.

We use TS68, a test set of 68 synonym pairs published by Minkov and Cohen (2012) for evaluation. This gold standard lists a single word as the correct synonym even if there are several equally acceptable near-synonyms (see Table 3 for examples). We call this the one-synonym evaluation. Three native English speakers were asked to mark synonyms, that were proposed by a baseline or by CoSimRank, i.e. ranked in the top 10. If all three of them agreed on one word as being a synonym in at least one meaning, we added this as a correct answer to the test set. We call this the “extended” evaluation (see Table 2).

Synonym extraction is run on the English graph. To calculate PPR+cos, we computed $20$ iterations with a decay factor of $0.8$ and used the cosine similarity with the 2-norm in the denominator to compare two vectors. For the other three methods, we also used a decay factor of $0.8$ and computed $5$ iterations. Recall that CoSimRank uses the simple inner product $⟨\cdot ,\cdot ⟩$ to compare vectors.

Our evaluation measures are proportion of words correctly translated by word in the top position (P@1), proportion of words correctly translated by a word in one of the top 10 positions (P@10) and Mean Reciprocal Rank (MRR). CoSimRank’s MRR scores of 0.37 (one-synonym) and 0.59 (extended) are the same or better than all baselines (see Table 2). CoSimRank and SimRank have the same P@1 and P@10 accuracy (although they differed on some decisions). CoSimRank is better than PPR+cos on both evaluations, but as this test set is very small, the results are not significant. Table 3 shows a sample of synonyms proposed by CoSimRank.

Minkov and Cohen (2012) tested cosine and random-walk measures on grammatical relationships (similar to our setup) as well as on cooccurrence statistics. The MRR scores for these methods range from 0.29 to 0.59. (MRR is equivalent to MAP as reported by Minkov and Cohen (2012) when there is only one correct answer.) Their best number (0.59) is better than our one-synonym result; however, they performed manual postprocessing of results – e.g., discarding words that are morphologically or semantically related to other words in the list – so our fully automatic results cannot be directly compared.

We evaluate lexicon extraction on TS1000, a test set of 1000 items, [17] each consisting of an English word and its German translations. For lexicon extraction, we use the same parameters as in the synonym extraction task for all four similarity measures. We use a seed dictionary of 12,630 word pairs to establish node-node correspondences between the two graphs. We remove a search keyword from the seed dictionary before calculating similarities for it, something that the architecture of CoSimRank makes easy because we can use a different seed dictionary $S^{\left(0\right)}$ for every keyword.

Both CoSimRank methods outperform SimRank significantly (see Table 4). The difference between CoSimRank with and without typed edges is not significant. (This observation was also made for SimRank on a smaller graph and test set [17].)

PPR+cos’s performance at $14.8\mathrm{\%}$ correct translations is much lower than SimRank and CoSimRank. The disadvantage of this similarity measure is significant and even more visible on bilingual lexicon extraction than on synonym extraction (see Table 2). The reason might be that we are not comparing the whole PPR vector anymore, but only entries which occur in the seed dictionary (see Eq. 9). As the seed dictionary contains 12,630 word pairs, this means that only every fourth entry of the PPR vector (the German graph has 47,439 nodes) is used for similarity calculation. This is also true for CoSimRank, but it seems that CoSimRank is more stable because we compare more than one vector.²²significantly worse than CoSimRank ($\alpha =0.05$, one-tailed Z-Test)

We also experimented with the method of Fogaras and Rácz (2005). We tried a number of different ways of modifying it for weighted graphs: (i) running the random walks with the weighted adjacency matrix as Markov matrix, (ii) storing the weight (product of each edge weight) of a random walk and using it as a factor if two walks meet and (iii) a combination of both. We needed about 10,000 random walks in all three conditions. As a result, the computational time was approximately 30 minutes per test word, so this method is even slower than SimRank for our application. The accuracies P@1 and P@10 were worse in all experiments than those of CoSimRank.

Table 5 compares the run time performance of CoSimRank with the baselines. We ran all experiments on a 64-bit Linux machine with 64 Intel Xenon X7560 2.27Ghz CPUs and 1TB RAM. The calculated time is the sum of the time spent in user mode and the time spent in kernel mode. The actual wall clock time was significantly lower as we used up to 64 CPUs.

Compared to SimRank, CoSimRank is more than 40 times faster on synonym extraction and six times faster on lexicon extraction. SimRank is at a disadvantage because it computes all similarities in the graph regardless of the size of the test set; it is particularly inefficient on synonym extraction because the English graph contains a large number of edges (see Table 1).

Compared to PPR+cos, CoSimRank is roughly four times faster on synonym extraction and has comparable performance on lexicon extraction. We compute 20 iterations of PPR+cos to reach convergence and then calculate a single cosine similarity. For CoSimRank, we need only compute five iterations to reach convergence, but we have to compute a vector similarity in each iteration. The counteracting effects of fewer iterations and more vector similarity computations can give either CoSimRank or PPR+cos an advantage, as is the case for synonym extraction and lexicon extraction, respectively.

CoSimRank should generally be three times faster than typed CoSimRank since the typed version has to repeat the computation for each of the three types. This effect is only visible on the larger test set (lexicon extraction) because the general computation overhead is about the same on a smaller test set.

Here we address inducing a bilingual lexicon from a seed set based on grammatical relations found by a parser. An alternative approach is to induce a bilingual lexicon from Wikipedia’s interwiki links [29]. These two approaches have different strengths and weaknesses; e.g., the interwiki-link-based approach does not require a seed set, but it can only be applied to comparable corpora that consist of corresponding – although not necessarily “parallel” – documents.

Despite these differences it is still interesting to compare the two algorithms. Rapp et al. (2012) kindly provided their test set to us. It contains 1000 English words and a single correct German translation for each. We evaluate on a subset we call TS774 that consists of the 774 test word pairs that are in the intersection of words covered by the WINTIAN Wikipedia data [29] and words covered by our data. Most of the 226 missing word pairs are adverbs, prepositions and plural forms that are not covered by our graphs due to the construction algorithm we use: lemmatization, restriction to adjectives, nouns and verbs etc.

Table 6 shows that CoSimRank is slightly, but not significantly worse than WINTIAN on P@1 (43.0 vs 43.8), but significantly better on P@10 (73.6 vs 55.4).⁴⁴We achieved better results for CoSimRank by optimizing the damping factor, but in this paper, we only present results for a fixed damping factor of 0.8. The reason could be that CoSimRank is a more effective algorithm than WINTIAN; but the different initializations (seed set vs interwiki links) or the different linguistic representations (grammatical relations vs bag-of-words) could also be responsible.

The results on TS774 can be considered conservative since only one translation is accepted as being correct. In reality other translations might also be acceptable (e.g., both street and road for Straße). In contrast, TS1000 accepts more than one correct translation. Additionally, TS774 was created by translating English words into German (using Google translate). We are now testing the reverse direction. So we are doomed to fail if the original English word is a less common translation of an ambiguous German word. For example, the English word gulf was translated by Google to Golf, but the most common sense of Golf is the sport. Hence our algorithm will incorrectly translate it back to golf.

As we can see in Table 7, we also face the problems discussed by Laws et al. (2010): the algorithm sometimes picks cohyponyms (which can still be seen as reasonable) and antonyms (which are clear errors).

Contrary to our intuition, the edge-typed variant of CoSimRank did not perform significantly better than the non-edge-typed version. Looking at Table 1, we see that there is only one edge type connecting adjectives. The same is true for verbs. The random surfer only has a real choice between different edge types when she is on a noun node. Combined with the fact that only the last edge type is important this has absolutely no effect for a random surfer meeting at adjectives or verbs.

Two possible solutions would be (i) to use more fine-grained edge types, (ii) to apply Eq. 5.3, in which the edge type of each step is important. However, this will increase the memory needed for calculation.