WIMS'18(Hub在KNN图中的影响)-The Influe

2023-08-17 本文已影响0人 Caucher

hubness（exact入度）比较大的点，最终在nn-descent产生的Kgraph中的召回普遍比较高，hubness比较小的点则说不准，有的召回高，有的召回低。
原因：hubness小的点很快就会从最初的几轮迭代中被驱逐出去，所以后续得到refine的机会也不大，恶性循环。hubness大的点会在大部分点的NN-list里面，所以refine的机会也很大，良性循环。

image.png
如果采用不同的随机初始化图，hubness比较大的点方差很低，几乎总是高召回，hubness比较小的则方差很高，受随机化的影响比较大。
原因：hubness大的点如何初始化都会在大部分NN-list中，所以召回不大有变化；但是hubness小的点很受初始化出现频率的影响，出现频率高refine的机会也大一些，召回就能相对好一些，反之亦然。

image.png

（本文的实验都是基于标准高斯分布实验的，保证一个较高的本征维数）
基于以上两个预实验，作者提出了两个优化nn-descent的方法，一个是在Refine的时候随机把一些hub替换掉随机点，hub是过程中近似估计的；另一个是用更大的K'NN-list，效率换精度。