SLING: A Near-Optimal Index Structure for SimRank

Boyu Tian, Xiaokui Xiao

Abstract

SimRank is a fundamental measure for determining node similarity based on graph topology, yet its computation at scale has long been a bottleneck. This paper introduces SLING, a breakthrough index structure that achieves millisecond-scale query times on million-node graphs with provable accuracy. By reformulating SimRank through a novel "$\sqrt{c}$-walk" interpretation, SLING provides the first near-optimal theoretical bounds for SimRank indexing, offering speedups of up to 10,000x over existing state-of-the-art methods.

Introduction

SimRank captures the intuition that "two nodes are similar if they are pointed to by similar neighbors," making it invaluable for social network analysis, recommendation systems, and web mining. Despite its utility, SimRank is notoriously difficult to compute efficiently. Existing approaches typically fall into three categories: iterative methods (which are slow and memory-intensive), Monte Carlo methods (which require excessive sampling for accuracy), and linearization techniques (which often lack rigorous error guarantees). SLING addresses these challenges by providing a system that is simultaneously fast, memory-efficient, and mathematically rigorous.

Methods and Theoretical Framework

The core innovation of SLING is a new mathematical interpretation of SimRank. While traditional views treat SimRank as the probability of two infinite random walks meeting, SLING utilizes $\sqrt{c}$-walks: reverse random walks with a $1-\sqrt{c}$ stopping probability at each step.

Notation and Identity

The SimRank score $s(v_i, v_j)$ is computed using the following identity: $$s(v_i, v_j) = \sum_{\ell=0}^{\infty} \sum_{k=1}^{n} h^{(\ell)}(v_i, v_k) \cdot d_k \cdot h^{(\ell)}(v_j, v_k)$$

The notation used throughout the paper is summarized below:

Table of notation and descriptions used in the SLING framework.

Complexity Analysis

SLING achieves "near-optimal" complexity by exploiting the sparsity of similarity scores in large graphs. By indexing only "significant" hitting probabilities (HPs) above a threshold $\theta$, the index size is kept to $O(n/\epsilon)$.

Comparison of SLING (this paper) against existing algorithms in terms of query time, space overhead, and preprocessing time.

As shown in the comparison table above, SLING provides a $O(1/\epsilon)$ query time for single-pair queries, matching the theoretical lower bound $\Omega(1)$.

Implementation Details

  • Correction Factor ($d_k$) Estimation: SLING uses an asymptotically optimal sampling method to precompute these node-specific constants.
  • Local Update for HPs: A deterministic traversal identifies significant HPs, ensuring the index remains sparse.
  • On-the-fly Refinement: To further reduce memory, SLING can omit 1st and 2nd-hop HPs from the index and recompute them during query time without violating the $O(1/\epsilon)$ time complexity.

Experimental Evaluation

The authors evaluated SLING on 12 real-world datasets, ranging from small citation networks (GrQc) to million-node web graphs (LiveJournal with 4.8M nodes and Indochina with 7.4M nodes).

Key Results

  • Query Speed: SLING consistently answers single-pair queries in under 2.3 milliseconds on million-node graphs, representing a 10,000x speedup over the previous state-of-the-art (Linearize).
  • Single-Source Performance: For queries involving one node and all others, SLING is up to 110x faster than competitors.
  • Accuracy: Experimental results confirmed that SLING's error always remains within the theoretical $\epsilon$ bound, unlike heuristic methods.
  • Scalability: Preprocessing is "embarrassingly parallelizable" and supports out-of-core execution, allowing it to handle graphs exceeding RAM capacity.

Conclusion

SLING represents a significant advancement in SimRank computation, bridging the gap between theoretical optimality and practical efficiency. While it requires more space than some heuristic methods, its provable accuracy and millisecond-scale performance make it a robust choice for large-scale applications. Future work includes adapting SLING for dynamic graphs and extending the framework to other graph similarity measures.

Summary updated

BibTeX
@inproceedings{tian2016sling,
  author = {Boyu Tian and Xiaokui Xiao},
  title = {{SLING: A Near-Optimal Index Structure for SimRank}},
  booktitle = {SIGMOD},
  year = {2016},
  url = {https://openreview.net/forum?id=QOGyrMl_n6},
}
Figure