PJsim: Precise and Scalable Graph Similarity

A C++ implementation of SimRank* - a graph similarity measure based on the iterative formulation by Yu et al., and PJsim, which is an optimized closed-form solution using the Bartels-Stewart algorithm.

Overview

SimRank measures structural similarity between nodes in a directed graph. Two nodes are similar if they are referenced by similar nodes.

Core equation:

S = (c/2)(Q^T·S + S·Q) + (1-c)I

where Q is the column-stochastic transition matrix, c is the decay factor (default 0.6), and S is the similarity matrix.

Implementations

File	Method	Description
s_yu.cpp	Iterative	Yu et al. iterative formulation - simple and fast
pjsim_bs.cpp	Bartels-Stewart	Closed-form via Sylvester equation - exact solution
pjsim_evd.cpp	Eigenvalue Decomposition	For EVD-compatible graphs

Requirements

• C++17 or higher
• Eigen3 library

Installing Eigen

macOS (Homebrew):

brew install eigen

Ubuntu/Debian:

sudo apt-get install libeigen3-dev

Compilation

macOS:

EIGEN_PATH=$(brew --prefix eigen)/include/eigen3
g++ -std=c++17 -O2 -I$EIGEN_PATH s_yu.cpp -o s_yu
g++ -std=c++17 -O2 -I$EIGEN_PATH pjsim_bs.cpp -o pjsim_bs
g++ -std=c++17 -O2 -I$EIGEN_PATH pjsim_evd.cpp -o pjsim_evd

Linux:

g++ -std=c++17 -O2 -I/usr/include/eigen3 s_yu.cpp -o s_yu
g++ -std=c++17 -O2 -I/usr/include/eigen3 pjsim_bs.cpp -o pjsim_bs
g++ -std=c++17 -O2 -I/usr/include/eigen3 pjsim_evd.cpp -o pjsim_evd

Usage

./s_yu <edge_list_file>
./pjsim_bs <edge_list_file>

Input Format

Edge list (0-indexed nodes, one edge per line):

# source target
0 1
0 2
1 2

Example

./s_yu sample_graph.txt
./pjsim_bs sample_graph.txt

Algorithm Details

Iterative (s_yu.cpp)

Direct iteration until convergence. With c=0.6, ~50 iterations achieve machine precision. Complexity: O(K·n³).

Bartels-Stewart (pjsim_bs.cpp)

Solves the Sylvester equation A·X + X·B = C using complex Schur decomposition. Gives exact solution in O(n³).