SimRank

Many applications require a measure of "similarity" between objects. One obvious example is the "find-similar-document" query, on traditional text corpora or the World-Wide Web. More generally, a similarity measure can be used to cluster objects, such as for collaborative filtering in a recommender system, in which “similar” users and items are grouped based on the users’ preferences.

Various aspects of objects can be used to determine similarity, usually depending on the domain and the appropriate definition of similarity for that domain. In a document corpus, matching text may be used, and for collaborative filtering, similar users may be identified by common preferences. SimRank is a general approach that exploits the object-to-object relationships found in many domains of interest. On the Web, for example, two pages are related if there are hyperlinks between them. A similar approach can be applied to scientific papers and their citations, or to any other document corpus with cross-reference information. In the case of recommender systems, a user’s preference for an item constitutes a relationship between the user and the item. Such domains are naturally modeled as graphs, with nodes representing objects and edges representing relationships.

The intuition behind the SimRank algorithm is that, in many domains, similar objects are referenced by similar objects. More precisely, objects ${\displaystyle a}$ and ${\displaystyle b}$ are considered to be similar if they are pointed from objects ${\displaystyle c}$ and ${\displaystyle d}$, respectively, and ${\displaystyle c}$ and ${\displaystyle d}$ are themselves similar. The base case is that objects are maximally similar to themselves .[4]

It is important to note that SimRank is a general algorithm that determines only the similarity of structural context. SimRank applies to any domain where there are enough relevant relationships between objects to base at least some notion of similarity on relationships. Obviously, similarity of other domain-specific aspects are important as well; these can — and should be combined with relational structural-context similarity for an overall similarity measure. For example, for Web pages SimRank can be combined with traditional textual similarity; the same idea applies to scientific papers or other document corpora. For recommendation systems, there may be built-in known similarities between items (e.g., both computers, both clothing, etc.), as well as similarities between users (e.g., same gender, same spending level). Again, these similarities can be combined with the similarity scores that are computed based on preference patterns, in order to produce an overall similarity measure.

For a node ${\displaystyle v}$ in a directed graph, we denote by ${\displaystyle I(v)}$ and ${\displaystyle O(v)}$ the set of in-neighbors and out-neighbors of ${\displaystyle v}$, respectively. Individual in-neighbors are denoted as ${\displaystyle I_{i}(v)}$, for ${\displaystyle 1\leq i\leq \left|I(v)\right|}$, and individual out-neighbors are denoted as ${\displaystyle O_{i}(v)}$, for ${\displaystyle 1\leq i\leq \left|O(v)\right|}$.

Let us denote the similarity between objects ${\displaystyle a}$ and ${\displaystyle b}$ by ${\displaystyle s(a,b)\in [0,1]}$. Following the earlier motivation, a recursive equation is written for ${\displaystyle s(a,b)}$. If ${\displaystyle a=b}$ then ${\displaystyle s(a,b)}$ is defined to be ${\displaystyle 1}$. Otherwise,

${\displaystyle s(a,b)={\frac {C}{\left|I(a)\right|\left|I(b)\right|}}\sum _{i=1}^{\left|I(a)\right|}\sum _{j=1}^{\left|I(b)\right|}s(I_{i}(a),I_{j}(b))}$

where ${\displaystyle C}$ is a constant between ${\displaystyle 0}$ and ${\displaystyle 1}$. A slight technicality here is that either ${\displaystyle a}$ or ${\displaystyle b}$ may not have any in-neighbors. Since there is no way to infer any similarity between ${\displaystyle a}$ and ${\displaystyle b}$ in this case, similarity is set to ${\displaystyle s(a,b)=0}$, so the summation in the above equation is defined to be ${\displaystyle 0}$ when ${\displaystyle I(a)=\emptyset }$ or ${\displaystyle I(b)=\emptyset }$.

Let ${\displaystyle \mathbf {S} }$ be the similarity matrix whose entry ${\displaystyle [\mathbf {S} ]_{a,b}}$ denotes the similarity score ${\displaystyle s(a,b)}$, and ${\displaystyle \mathbf {A} }$ be the column normalized adjacency matrix whose entry ${\displaystyle [\mathbf {A} ]_{a,b}={\tfrac {1}{|{\mathcal {I}}(b)|}}}$ if there is an edge from ${\displaystyle a}$ to ${\displaystyle b}$, and 0 otherwise. Then, in matrix notations, SimRank can be formulated as

${\displaystyle {\mathbf {S} }=\max\{C\cdot (\mathbf {A} ^{T}\cdot {\mathbf {S} }\cdot {\mathbf {A} }),{\mathbf {I} }\},}$

where ${\displaystyle \mathbf {I} }$ is an identity matrix.

A solution to the SimRank equations for a graph ${\displaystyle G}$ can be reached by iteration to a fixed-point. Let ${\displaystyle n}$ be the number of nodes in ${\displaystyle G}$. For each iteration ${\displaystyle k}$, we can keep ${\displaystyle n^{2}}$ entries ${\displaystyle s_{k}(*,*)}$, where ${\displaystyle s_{k}(a,b)}$ gives the score between ${\displaystyle a}$ and ${\displaystyle b}$ on iteration ${\displaystyle k}$. We successively compute ${\displaystyle s_{k+1}(*,*)}$ based on ${\displaystyle s_{k}(*,*)}$. We start with ${\displaystyle s_{0}(*,*)}$ where each ${\displaystyle s_{0}(a,b)}$ is a lower bound on the actual SimRank score ${\displaystyle s(a,b)}$:

${\displaystyle s_{0}(a,b)={\begin{cases}1{\mbox{ }},{\mbox{ }}{\mbox{if }}a=b{\mbox{ }},\\0{\mbox{ }},{\mbox{ }}{\mbox{if }}a\neq b{\mbox{ }}.\end{cases}}}$

To compute ${\displaystyle s_{k+1}(a,b)}$ from ${\displaystyle s_{k}(*,*)}$, we use the basic SimRank equation to get:

${\displaystyle s_{k+1}(a,b)={\frac {C}{\left|I(a)\right|\left|I(b)\right|}}\sum _{i=1}^{\left|I(a)\right|}\sum _{j=1}^{\left|I(b)\right|}s_{k}(I_{i}(a),I_{j}(b))}$

for ${\displaystyle a\neq b}$, and ${\displaystyle s_{k+1}(a,b)=1}$ for ${\displaystyle a=b}$. That is, on each iteration ${\displaystyle k+1}$, we update the similarity of ${\displaystyle (a,b)}$ using the similarity scores of the neighbours of ${\displaystyle (a,b)}$ from the previous iteration ${\displaystyle k}$ according to the basic SimRank equation. The values ${\displaystyle s_{k}(*,*)}$ are nondecreasing as ${\displaystyle k}$ increases. It was shown in [4] that the values converge to limits satisfying the basic SimRank equation, the SimRank scores ${\displaystyle s(*,*)}$, i.e., for all ${\displaystyle a,b\in V}$, ${\displaystyle \lim _{k\to \infty }s_{k}(a,b)=s(a,b)}$.

The original SimRank proposal suggested choosing the decay factor ${\displaystyle C=0.8}$ and a fixed number ${\displaystyle K=5}$ of iterations to perform. However, the recent research [5] showed that the given values for ${\displaystyle C}$ and ${\displaystyle K}$ generally imply relatively low accuracy of iteratively computed SimRank scores. For guaranteeing more accurate computation results, the latter paper suggests either using a smaller decay factor (in particular, ${\displaystyle C=0.6}$) or taking more iterations.

CoSimRank is a variant of SimRank with the advantage of also having a local formulation, i.e. CoSimRank can be computed for a single node pair.[6] Let ${\displaystyle \mathbf {S} }$ be the similarity matrix whose entry ${\displaystyle [\mathbf {S} ]_{a,b}}$ denotes the similarity score ${\displaystyle s(a,b)}$, and ${\displaystyle \mathbf {A} }$ be the column normalized adjacency matrix. Then, in matrix notations, CoSimRank can be formulated as:

${\displaystyle {\mathbf {S} }=C\cdot (\mathbf {A} ^{T}\cdot {\mathbf {S} }\cdot {\mathbf {A} })+{\mathbf {I} },}$

where ${\displaystyle \mathbf {I} }$ is an identity matrix. To compute the similarity score of only a single node pair, let ${\displaystyle p^{(0)}(i)=e_{i}}$, with ${\displaystyle e_{i}}$ being a vector of the standard basis, i.e., the ${\displaystyle i}$-th entry is 1 and all other entries are 0. Then, CoSimRank can be computed in two steps:

1. ${\displaystyle p^{(k)}=Ap^{(k-1)}}$
2. ${\displaystyle s(i,j)=\sum _{k=0}^{\infty }C^{k}\langle p^{(k)}(i),p^{(k)}(j)\rangle }$

Step one can be seen a simplified version of Personalized PageRank. Step two sums up the vector similarity of each iteration. Both, matrix and local representation, compute the same similarity score. CoSimRank can also be used to compute the similarity of sets of nodes, by modifying ${\displaystyle p^{(0)}(i)}$.

• Fogaras and Racz [7] suggested speeding up SimRank computation through probabilistic computation using the Monte Carlo method.
• Antonellis et al.[8] extended SimRank equations to take into consideration (i) evidence factor for incident nodes and (ii) link weights.
• Yu et al.[9] further improved SimRank computation via a fine-grained memoization method to share small common parts among different partial sums.
• Chen and Giles discussed the limitations and proper use cases of SimRank.[3]

• PageRank

• Cai, Y.; Cong, G.; Jia, X.; Liu, H.; He, J.; Lu, J.; Du, X. (2009-12-01). "Efficient Algorithm for Computing Link-Based Similarity in Real World Networks". 2009 Ninth IEEE International Conference on Data Mining: 734–739. doi:10.1109/ICDM.2009.136. ISBN 978-1-4244-5242-2.