SimRank 是一种经典的基于链接的图相似性算法， 它在具体应用中具有不同的查询模式。已有的SimRank估算方法存在三方面的局限：

首先，针对不同的 SimRank模式，希望有一个统一的计算框架，以支持不同应用。而几乎所有现有算法都是为特定模式而设计。

其次，由于不同的应用程序可能有不同估算精度要求，例如一些在线任务强调快速估计而其他一些应用则依赖于精准的计算，而已有的算法不能根据应用需求进行效率和准确性的灵活平衡。

第三，由于大多数现实世界的图表都是动态演化的，因此希望支持不依赖索引的高效在线计算。 而已有算法需要预先计算和维护处理在线查询的索引，不能灵活处理动态图。

针对上述问题，本文提出一个适用于所有 SimRank 的统一增量框架UISim， UISim基于路径重要性对计算空间进行优先级划分和重构， 通过增量式的查询调度，在计算效率和准确性上进行灵活的平衡。 另一方面，它创建并共享共同的“构建块”以支持不依赖索引的在线计算，因此可以有效地处理静态和动态图。我们在真实的数据集上进行了大量实验，实验表明 UISim 显著提升了不同模式的simrank相似度计算效率，能有效应用于大规模图近邻搜索推荐等场景。

2022-UISIM-TKDE-Early Access.pdf