Feature Request: Address the zero-similarity problem in `simrank_similarity`

Summary

networkx.algorithms.similarity.simrank_similarity implements Jeh and Widom's original SimRank recursion. This formulation has a known structural defect, the "zero-similarity" problem, which causes many structurally related node pairs to receive a similarity score of exactly zero. Therefore, I propose to implement a new similarity function based on SimRank* (Yu et al., VLDBJ 2019), which resolves this problem, and suggests that its closed-form counterpart PJsim (Nijhara et al., SIGMOD 2026) be considered as the computational backend, since it removes the iteration/tolerance trade-off that all current SimRank variants in NetworkX are subject to.

Background: the zero-similarity problem

Jeh and Widom's SimRank defines similarity recursively:

s(a, b) = 1                                                  if a = b
s(a, b) = C / (|I(a)||I(b)|) * sum_{i in I(a), j in I(b)} s(i, j)   if a != b

where I(x) is the in-neighbor set of x. This recursion only accumulates contributions from symmetric in-link paths, i.e. paths where the "source" node sits at equal distance from both a and b. Any path where the source is off-center, and any path of odd length (which can never have a center at all), is entirely ignored, not down-weighted, but ignored. Yu et al. formalize this: SimRank's score s(a, b) is zero if and only if there is no symmetric in-link path between a and b in the graph, regardless of how strongly connected a and b actually are.

On real citation and social graphs this is not an edge case. Yu et al. report that on a citation network (cit-HepPh), roughly 97.9% of node pairs are affected by "zero-similarity," and similar magnitudes show up on DBLP-derived graphs. This means simrank_similarity today silently returns 0.0 for the overwhelming majority of pairs on typical directed graphs, because the recursion structurally cannot see the paths connecting them.

Proposed fix: SimRank*

Yu et al. propose SimRank* as a replacement, where, instead of summing only over Qᵅ · (Qᵀ)ᵅ (symmetric, equal-length terms), SimRank* sums over all Qᵅ · (Qᵀ)ˡ⁻ᵅ terms for a given path length l, weighted by a binomial coefficient. The resulting series has a simple closed recursive matrix form (their Theorem 6):

S = (C/2) * (Q @ S + S @ Q.T) + (1 - C) * I

This is a bilinear matrix equation, structurally very close to the original SimRank recursion, and it is proven to have no "extreme" zero-similarity cases beyond genuine graph disconnection: s(a, b) = 0 only when a and b are truly unreachable from a common ancestor via any in-link paths. Complexity for the iterative solver is the same order as today's implementation, O(K·n·m) per full pass.

I, therefore, propose adding this as a new public function, e.g. nx.simrank_star_similarity(G, ...), mirroring the existing simrank_similarity signature (source, target, importance_factor, max_iterations, tolerance).

Iteration count vs. accuracy problem

SimRank*, like the current SimRank implementation, is still solved iteratively, so it inherits the same accuracy/runtime trade-off that max_iterations/tolerance expose today. Nijhara et al. (PJsim, SIGMOD 2026) show this trade-off exists in practice: reaching a tolerance (F-norm) of 1e-6 versus 1e-2 on their test graphs took roughly 6x longer on average.

Proposed further improvement: PJsim (closed-form solution)

PJsim reformulates the exact same SimRank* equation above as a Lyapunov equation (special case of Sylvester equation). Rearranging:

(I - C*Q) @ S + S @ (I - C*Q).T = 2(1 - C) * I,      Where @ is Kron product operation.

which is X @ S + S @ X.T = 2(1-C)*I with X = I - C*Q, i.e. a standard Lyapunov/Sylvester system. This has a direct, non-iterative solution via the Bartels–Stewart algorithm (real Schur decomposition of X, followed by block back-substitution), giving the exact fixed point of the SimRank* recursion in a single pass, with no tolerance parameter and no risk of not converging within max_iterations. Their complexity analysis:

• Naive vectorized solve: O(n^6) (impractical, mentioned only for completeness)
• Bartels–Stewart (PJsim_BS): O(n^3) time, O(n^2) space, works for any graph
• Eigen-decomposition variant (PJsim_EVD): also O(n^3), faster in practice when X is diagonalizable, but not universally applicable

Their experiments (SIGMOD 2026, Section 4) report PJsim_BS at 1.3x–2.2x speedup and PJsim_EVD at 2.9x–3.2x speedup over the iterative SimRank* solver run to convergence, on graphs ranging from a few thousand to ~500K nodes and up to ~3M edges, while producing results that match the converged iterative solution to within 1e-5–1e-6 tolerance.

Suggested scope for this issue

1. Add simrank_star_similarity implementing the SimRank* iterative recursion (Yu et al., Theorem 6) with the same call signature style as simrank_similarity.
2. Optionally expose a method={"iterative", "closed_form"} (or similar) argument, where "closed_form" solves the Lyapunov formulation via Bartels–Stewart (SciPy's scipy.linalg.solve_sylvester can solve this directly, so this could be implemented without a new heavy dependency) for exact, iteration-free results.
3. Document the zero-similarity problem in the docstring/notes of the existing simrank_similarity so users understand when scores of exactly 0.0` are a structural artifact rather than a meaningful "not similar" result, and point them to the new function.

References

• Yu, Weiren, Xuemin Lin, Wenjie Zhang, Jian Pei, and Julie A. McCann. "SimRank*: effective and scalable pairwise similarity search based on graph topology." The VLDB Journal 28, no. 3 (2019): 401–426. https://link.springer.com/article/10.1007/s00778-018-0536-3
• Nijhara, Prajjwal, Jainan Tandel, Rohit Prajapati, and Dip Sankar Banerjee. "PJsim: Towards Precise and Scalable Graph Similarity." Proceedings of the ACM on Management of Data 4, no. 3 (SIGMOD, 2026): Article 223. https://dl.acm.org/doi/10.1145/3802100
• Jeh, Glen, and Jennifer Widom. "SimRank: a measure of structural-context similarity." In Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 538–543. 2002. (current basis for nx.simrank_similarity)