Jaccard Similarity is a lower-bound for Cosine Similarity

up:: Jaccard Similarity, Cosine Similarity

Given an undirected Simple Graph with Adjacency Matrix $A$ and nodes $i,j$, then their Jaccard similarity is

$$J_{ij}=\frac{(A^2{)}_{ij}}{deg(i)+deg(j)-(A^2{)}_{ij}}$$

Their cosine similarity is

$$\cos {\theta }_{ij}=\frac{(A^2{)}_{ij}}{\sqrt{deg(i)}\sqrt{deg(j)}}$$

Multiplying and dividing $J_{ij}$ by $\sqrt{deg(i)}\sqrt{deg(j)}$¹, we have

$$\begin{array}{rl}{J}_{ij}& =\frac{(A^2{)}_{ij}}{\sqrt{deg(i)}\sqrt{deg(j)}}\frac{\sqrt{deg(i)}\sqrt{deg(j)}}{deg(i)+deg(j)-(A^2{)}_{ij}}\\ & =\cos {\theta }_{ij}\frac{1}{\sqrt{\frac{deg(i)}{deg(j)}}+\sqrt{\frac{deg(j)}{deg(i)}}-\cos {\theta }_{ij}}\\ & \le \cos {\theta }_{ij}\frac{1}{\sqrt{\frac{deg(i)}{deg(j)}}+\sqrt{\frac{deg(j)}{deg(i)}}}\end{array}$$

since

$$\begin{array}{rl}\cos {\theta }_{ij}\le 1⟹-\cos {\theta }_{ij}\ge 1& \\ \therefore \forall \alpha \ge 0:\alpha -\cos {\theta }_{ij}& \ge 1-\alpha \\ & \ge 1\end{array}$$

with $\alpha =\sqrt{\frac{deg(i)}{deg(j)}}+\sqrt{\frac{deg(j)}{deg(i)}}$.

We need to consider two cases:

1. $deg(i)=deg(j)⟹\alpha =2$, in which case we simply have

$$\begin{array}{r}{J}_{ij}\le \frac{\cos {\theta }_{ij}}{2}<\cos {\theta }_{ij}\end{array}$$

2. $deg(i)>deg(j)$ without loss of generality, for which we have

$$\sqrt{\frac{deg(i)}{deg(j)}}>1$$

Since

$$\sqrt{\frac{deg(j)}{deg(i)}}\ge 0$$

we have that $\alpha >1$ as defined above.

Thus, we conclude that

$$J_{ij}<\cos {\theta }_{ij}$$

That is, the Jaccard similarity of two nodes is more stringent than their cosine similarity.

Footnotes

1. Assuming both have degree greater than $0$. ↩