PJsim: Towards Precise and Scalable Graph Similarity

Quantifying node similarity is central to graph analysis, particularly in social networks. SimRank, a popular measure by Jeh and Widom, defines similarity recursively: two nodes are similar if they are referenced by similar nodes. However, its limitation to equal-length paths leads to the ''zero-similarity'' problem, where structurally related nodes may score zero due to the lack of symmetric in-neighbor paths, especially in sparse or hierarchical graphs. While several variants of SimRank have been proposed to overcome this problem, most rely on iterative methods that approximate the solution by exploring paths of varying lengths. These approaches often require expensive convergence checks and can struggle with scalability on large graphs. To address these limitations, we propose PJsim, a novel, exact, and closed-form solution for SimRank computation. PJsim reformulates the recursive similarity definition as Sylvester equations and solves them via block transformations. Our experiments on real-world and synthetic graphs demonstrate that PJsim consistently delivers higher accuracy than traditional methods and runs up to 3.22x faster on synthetic datasets and 2.15x faster on real-world graphs, compared to state-of-the-art solutions addressing the zero-similarity problem.