作者来自英伟达

编者：本文只介绍图结构，GPU部分暂时省略。

编者的总结（图结构方面）

1. 是NSSG的一个改版，用一个K较大的KNN-Graph做初始化，然后在其中通过两条绕路性进行排序，裁掉2/3的边；然后与反向图merge，固定留一半的反向边增强导航性。
2. 相比之下，NSSG用两条邻居做candiate，用RNG裁边；反向边的加入和正向边同等待遇进入裁边；最终有DFS加入补充连通性。
3. candidate选取和裁边规则的改动可能是有并行性和构建效率的考虑，对反向边的bias可能主要考虑DFS去掉了，且没有二跳邻居进来，就多加一些长边。
4. CPU性能和NSSG差不多。

编者的思考

1. 加了反向边之后SCC几乎就是只有1个，意味着是一个连通图，但搜索精度似乎并没有显著提高，和note那一篇结论不一致。
2. 作者提了两个连通性的metric，2跳可达度和SCC的个数，但是并没有证明这两个metric和query性能之间的联系，即连通度是如何起作用的。
3. 这两个metric对于NSSG是什么样子并不清楚。如果CAGRA在这两个指标上比NSSG要好，那么查询性能为什么没提高？如果CAGRA和NSSG差不多，那么新提出来的方法意义何在？若意义是构建效率和并行性，那就应该证明CAGRA和NSSG的构建结果的相似性保障。
4. 尽管作者没有证明，但编者觉得2跳可达度是一个不错的metric，它代表了逃离cluster的能力。

CAGRA图是以KNN图作为base进行Refine，refine分成两步，prune和merge:

image.png

1. prune

• 如下图，CAGRA会对每个点的邻居进行排序，按照它们和该点的距离由近到远排序，并用这个排序代替该边的长度；
• 从一个点X出发，找到所有邻居的二跳Route，比如对于邻居B，X->A->B，就是一个二跳Route，并从中筛选中有效二跳Route，即二跳的长度（顺序）都比直接到达（X->B）要更短，有效二跳route的个数，就是一条有向边的一个rank；个数越大，这条边越不重要。
• prune即删除route个数较大的边。

• 这个方法的motivation是作者认为从任意点出发，二跳可达点的个数是可达性的一个标准，因此尽可能地去裁掉可以通过有效二跳route可达的边。
  【编者注1：这其实是一个贪心的策略，因为每删除一条边，rank值都会发生变化，因为原本二跳可达的，删除某个邻居点后，就会变得二跳不可达，这个算法没有考虑这个级联关系。】
  【编者注2：用initial sort index去做距离的近似勉强可以接受，因为考虑到两个点如果比较相近，它们的kNN分布也会比较接近。】

  
  image.png

2. merge

• 把第一步生成的剪枝图的反向图构建出来，设置度数上限为d；
• rank方面，作者说按照剪枝图的rank排序；
  【编者注：感觉不合理，因为rank只在同一个source的情况下有意义，它代表一条边的不可绕路性的一个量化，这里把它反过来了情况完全变化，意义已经发生改变，这里只能理解为随机删掉了一部分溢出的边而已】
• 然后对于每个点，从剪枝图和反向图各取d/2条边，反向图边不够的，就从剪枝图里多拿点。

3. evalution

• pruning对于2-hop可达度很有帮助；

• 反向边的引入对于减少图中总SCC的个数很有帮助，已经减少到了1,2.

  
  image.png

• CPU下查询水平和NSSG差不多

  
  image.png