Random-Walk Based Approximate k-Nearest Neighbors Algorithm for Diffusion State Distance
Random-Walk Based Approximate k-Nearest Neighbors Algorithm for Diffusion State Distance
复制标题
基于随机游走的扩散状态距离近似 k 最近邻算法
DOI：
10.1007/978-3-030-97549-4_1
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Wu, K.
中科院分区：
文献类型：
--
作者：
Cowen, L.;Hu, X.;Lin, J.;Shen, Y.;Wu, K.
扩散状态距离 (DSD) 是一种依赖于数据的度量，它使用数据驱动的扩散过程来比较数据点，并为学习高维数据的底层结构提供了强大的工具。虽然在 DSD 度量中找到精确的最近邻在计算上是昂贵的，但在本文中，我们提出了一种新的基于随机游走的算法，该算法凭经验以有效的方式准确地找到近似最近邻。给出了真实世界蛋白质-蛋白质相互作用网络的数值结果，以说明所提出算法的效率和鲁棒性。当用于预测蛋白质的功能标签时，近似 k 最近邻集表现良好。
Diffusion State Distance (DSD) is a data-dependent metric that compares data points using a data-driven diffusion process and provides a powerful tool for learning the underlying structure of high-dimensional data. While finding the exact nearest neighbors in the DSD metric is computationally expensive, in this paper, we propose a new random-walk based algorithm that empirically finds approximatek-nearest neighbors accurately in an efficient manner. Numerical results for real-world protein-protein interaction networks are presented to illustrate the efficiency and robustness of the proposed algorithm. The set of approximatek-nearest neighbors performs well when used to predict proteins’ functional labels.