標題：基于導向型的向外傳播的圖進行快速近似最近鄰搜索
本文作者來自浙江大學和阿里巴巴，據作者在文中寫道：本文的NSG算法已經在淘寶的電商場景中，被整合進10億級別的搜索引擎。
圖像通過特征抽取，實際上以高維向量表示，如SIFT,GIFT等表示法，因此圖像搜索算法，就是高維向量的（近似）最近鄰搜索。
代碼地址：https://github.com/ZJULearning/nsg

編者的總結和思考：

本文的亮點第一個是（隱晦地）引入了角度問題（60°），完成了圖的多方向擴展，也就是基于MSNET圖設計了MRNG圖，雖然這個在之前有DPG做思路導引，但是這是第一次做完善。
第二個重要的貢獻是為graph-based ANNS提供了理論保障，雖然是在理想情況下，比如嚴格的 MRNG, NNG就都是MSNET（單調圖），通過現在的貪心搜索算法，可以在一定步數之內，達到另一個點。（文中原話：圖中任意兩點一定存在一條（嚴格）遞增路徑，這條遞增路徑可以由貪心算法得到。）雖然：a) 事實上目前所有的graph-based ANNS都是對于基本圖的一種近似；b) 對于路徑長度上界的推導基于均勻分布的數據但是這個理論保障提供了一個重要的優(yōu)化方向。
第三個亮點是固定入口導航點，之前的工作中，入口點到底怎么選是一個很重要的問題，HNSW，FANNG等工作都在這里做過工作；在NSG中，固定了一個接近于質心的點做入口點（即導航點），在構建時，直接考慮從導航點直接搜過去，然后把路徑上的邊作為候選集進行賦邊（有長有短）。
第四個點（彌補策略）是從導航點開始做一棵最小生成樹來保證連通性。起因在于節(jié)點的出度有限制，這樣就不能保證NSG的導航點（和某些密集區(qū)域）有足夠的連通度。為了保證最起碼的可導航性，做了一顆DFS樹來補邊，但其實又可能超過了出度限制，這一點在glove, wordvec數據集上體現非常明顯。
編者認為，NSG給予唯一的導航點過大壓力，入口單一，又是從這個入口開始建圖的，直接影響圖索引的形狀，可能會讓算法在不同的數據分布（數據集）上表現差異很大。
后面Wang et.al.證明了NSG的選邊策略其實和HNSW的是等同的，但是二者對于邊的候選集其實不一樣：HNSW是在已經建了一部分的圖上做貪心KNN搜索，獲得候選集；NSG把KNN圖的鄰居，以及在已有圖上做近似搜索找到的最近鄰做候選集。
問題角度方面，考慮到了索引大小和構建速度，這也將這一問題引入了一個新方向（AI領域）。盡管如此，本文的超線性構建速度，相比于DB領域的構建速度，在大數據集上慢了幾乎100倍，最后的實驗數據也證明了這一點。那么在10億級別的大數據上，該方法還不足夠實用。2019年NIPS發(fā)表的一篇基于磁盤的方法，反而在這一點上做的更好：http://m.itdecent.cn/p/07ed2202f107。
此外，方法仍然是memory-based（雖然比HNSW，FANNG之類的要節(jié)省很多），不是disk-based的，擴展性仍然存在問題，不可能把大數據集都放進內存。如果沒有至強機器作為依托，這種算法就缺乏更通用的價值。

ABSTRACT

基于圖的KNN算法雖然搜索速度快，效果好，但是索引的構建速度太慢了。
本文進一步提升了基于圖的KNN算法的搜索效率，同時提升了可擴展性，可以達到10億級別數據的索引構建，主要有4個層面：

確保圖的連通性；
降低圖的平均出度；
縮短搜索路徑；
減少索引大小。

提出了兩種圖結構，一種稱為MRNG(Monotonic Relative Neighborhood Graph，單調相關鄰居圖)，可以保證非常高的搜索效率；基于MRNG，設計了NSG（Navigating Spreading-out Graph，導向性的向外傳播圖），可以實現較低的索引構建復雜度。

1. INTRODUCTION

論文的背景介紹部分，2021年TPAMI期刊中寫的更為詳細，在我的博客中已有講述：http://m.itdecent.cn/p/029be522fa89。其中相關的方法的典型論文在本文集中大部分都有講述。

有遞增屬性（在圖中從起點到query的路徑上每一個點都離query更近一些）的圖包括MSNET圖、泰森圖等。有遞增屬性，但是遞增的級別沒有明確表示。

近期提出的RNG圖，搜索復雜度是多重對數級別；
NSWN圖，僅平均路徑長度就是多重對數級別的；

更別說這些個索引的構建復雜度極高，至少也是 $O(n^2)$ 的，對大數據集來說沒有實踐意義。
【編者注：上面這部分舉的例子年份都很早，都在10年以前，參考價值有限?！?/p>

既然完整構建這種遞增屬性圖很困難，那么可以只構建近似的就可以了。很多工作就是這樣做的。KNN圖是泰森圖的一種近似表示。

GNNS,IEH,Efanna算法就是基于KNN圖來設計的；
NSW是基于NSWN的算法；
【編者注：實際上是基于狄洛尼圖】
FANNG近似了RNG圖；
HNSW本質上是一個大雜燴，結合了泰森圖、NSWN和RNG圖的優(yōu)勢。
【編者注：實際上基于狄洛尼圖和RNG】

上述這些近似方法很多都是基于直覺在做，缺乏嚴格的理論支撐。為了做出提升，作者首先研究了近似KNN算法在圖中是如何運行的。
無論圖是何種形式的，搜索都是貪婪算法，類似A*-搜索。因此要想加速搜索，需要縮短搜索路徑，同時減少圖的出度。因此有了摘要中所說的4個層面。

IEH,Efanna,HNSW，或者用隨機樹，或者是多層圖來加速，然而內存占用就會非常高，這也是不可接受的?！揪幷咦ⅲ翰粌H引入了新的結構，數據也被復制了多次】

2. PRELIMINARIES

2.1 Problem Setting

2.2 Non-Graph-Based ANNS Methods

2.3 Graph-Based ANNS Methods

幾乎和期刊中一模一樣，具體內容在http://m.itdecent.cn/p/029be522fa89。
補充一些期刊中沒有的討論內容：

Delauney圖：
- Delauney圖上的高維搜索復雜度非常高；
- Delauney圖在高維上幾乎是全連接的，使得搜索效率嚴重退化；
- KNN圖是Delauney圖的一種近似，構建速度仍然極慢。
- DPG算法基于KNN圖做了角度的改良，然而降低了搜索效率，索引也變的更大。
Relative Neighborhood Graphs (RNG)：
- RNG的出度通常非常低，是一個和維數相關的常量；
- RNG沒有遞增屬性，因此也就沒有了搜索路徑長度保證；
- MSNET是RNG的一個改良，有搜索長度保證，但是總構建復雜度是 $O(n^3)$ ，太高了；
- FANNG和HNSW采取了一些邊選擇策略降低了圖的出度，但是也沒有一些理論分析。
Navigable Small-World Networks：
- 基于小世界模型，度數和鄰居均基于概率分布來賦予；
- 搜索路徑是多重對數級別的（經驗上來看）；
- 構建復雜度是O(n^2);
- NSW和HNSW均為近似NSW圖?！驹诒疚募?，有這兩種方法的詳細介紹】

3. ALGORITHMS AND ANALYSIS

3.1 Motivation

摘要中提到本文要從4個層面入手，改良基于圖的算法。其中第一點：確保圖的連通性，具體來說，如果起始位點不固定，圖就必須是強連通的；如果固定，就要保證所有點都在起始點為根的DFS-Tree上。

3.2 Graph Monotonicity And Path Length

本文首先討論有關Monotonic Search Networks (MSNET)的性質。

定義：MSNET的定義是一個有向圖，在這個圖上任意兩點之間都存在一條遞增路徑（每一步都距離終點更近）。
- 這也就意味著，MSNET是一個強連通圖，因為任兩點之間都有一條路。
之前定義MSNET的文章認為，在此圖中，用貪婪算法從一個點尋找到另一個點，不需要走“回頭路”?！盎仡^路”是說到達某一個local optimal之后，返回歷史軌跡，然后調轉一個方向。當時沒有給出嚴格證明，本文給了一個嚴格證明，即用貪婪算法，不走“回頭路”，就能找到一條遞增路。
一個等價定義：MSNET還可以這樣定義：對于一對點p,q，在以q為球心，pq為半徑的球內，必然存在一個點r使得有向邊pr是MSNET中的邊。
- 證明：如果p的所有邊都不指向球內，則p->q的路徑必然不是一個遞增路徑，充分性得證。如果每一條邊都可以往以q為球心的，半徑更小的球上指向，則此指向路徑，就是一個遞增路徑，必要性得證。
  
  image.png
路徑長度：在數據隨機分布，排除極端情況（直線分布）下，MSNET圖任意兩點的遞增路徑的長度為。d是維數，的定義比較復雜，看不出物理意義，當做是常量就可以了。
- 【證明略】。
- MSNET圖的路徑長度是有保障了，但是度數卻沒有任何保障。

3.3 Monotonic Relative Neighborhood Graph(MRNG)

本文提出一種新的MSNET圖，稱為MRNG。

HNSW和FANNG為了使圖稀疏一些都轉而使用RNG，然而RNG并不足夠稱為MSNET。RNG出度有保障，但是路徑長度沒保障（因為不一定是遞增路）。
RNG圖的定義：在RNG圖（無向圖）中，對于任意邊pq，分別以p和q為球心，pq為半徑畫球相交得到一個月牙形狀的空間 $lune_{pq}$ ，這個空間里不能有其它點。如下圖a。下面這個例子p->q就沒有增長路徑。

image.png

作者發(fā)現問題在于RNG的賦邊策略。受此啟發(fā)，作者設計了圖結構叫做MRNG（Monotonic Relative Neighborhood Graph）。

MRNG：MRNG是一個有向圖，對于圖中任意一個有向邊pq，不能有另一個點，使得有向邊pr也是圖中的邊。反過來定義，如果中沒有其它點和p相連了，pq這條有向邊就要連起來。
- 這相當于泛化了RNG的定義。RNG徹底不允許 $lune_{pq}$ 中有點，MRNG允許，只不過不能和p相連。如上圖3，MRNG有更多的邊，且設計為有向邊。
MRNG最好的一點是：它是一個MSNET圖，雖然不是最小的吧，但是也足夠稀疏。這意味著圖上的任意兩點，greedy algorithm可以通過遞增路徑找到。
- 因為一個點的兩條出邊夾角必然大于60°，因為lune是兩個等邊三角形拼成的。
- 這也就暗示我們，構造MRNG圖，要從近距離到遠距離為某一點選邊，否則容易白選（被短邊替換掉）【編者注：正如HNSW的做法那樣】。
NNG定義：NNG是一個有向圖，對于每個點，只有一條出邊，指向1NN。
- 顯然，無論是MRNG，還是RNG，必然都包含NNG。因為最短距離為中心的lune肯定不包含其他點，否則就不是最短距離。
- MRNG包含NNG，是非常重要的性質，否則即使按照選擇策略，也非常容易構造出非遞增路徑。
MRNG度數性質：MRNG中節(jié)點的最大度數是個常量。
- 有數學定理可以證明，對于有限維空間 $E^d$ ，固定一個頂點，可以通過有限個圓錐覆蓋整個空間。圓錐個數只和d有關。

到此為止，我們可以確定，MRNG的搜索總復雜度，是近似對數的 $O(cn^{1/d}logn/\Delta r)$ 。

3.4 MRNG Construction

雖然搜索性質如此漂亮，但是構建代價不容樂觀。
構建從完全圖開始剪枝選邊。對于每個點p，和各個其他點的距離都要算一次，并排序，排好序，該列表表示為R。首先將距離p最近的點加入到鄰居集L中。然后每次從R中取一個點r，如果r和L中任意一個點l構成的三角形prl,pr不是最長的那條邊，就把r放進L里。
- 可以通過幾何證明這構造的是MRNG圖。
- 由于距離計算，排序，驗證，最終復雜度為 $O(n^2+n^2logn+n^2c)$ ，c是平均出度。盡管這比之前的MSNET圖構建要好半個量級，但還是無法實際應用的。

3.5 NSG:Practical Approximation For MRNG

既然精確的MRNG構建太復雜，那么就考慮構造一個近似的。引出本文的索引方法NSG（Navigating Spreading-out Graph）。

3.5.1 NSG構建過程

首先構造一個近似KNN圖；
尋找質心點：
- 首先計算整個數據集的中心位置；
- 然后把這個位置當做query，在KNN圖上找到和它（近似）最近的點，作為導航點；
- 之后這個導航點就作為所有查詢的入口點。
為每個點p賦邊：
- 把p作為query，從導航點開始，在KNN圖上做貪婪搜索，路徑上的點都作為備選集；
- 從備選集中選擇至多m個點，選擇策略即MRNG選擇策略。
構建DFS樹：
- 以導航點為根，做DFS，形成DFS樹，如果有節(jié)點在DFS結束之后仍然沒有在樹中，則補充邊，將它們鏈接到近似最近鄰上（貪婪算法）。

3.5.2 Motivations

MRNG要求任兩點之間都有遞增路徑，這太嚴格了。在NSG中，我們只嘗試從導航點開始，到任何點都有遞增路徑。搜索時我們也從導航點開始，這樣搜索的復雜度不變，但是構建復雜度大大降低了。
賦邊時候候選集太大了。相反，NSG的候選集非常小，只包含兩部分：
- kNN：上面我們提到過，NNG在MRNG中的作用非常大，必須包含。但是找精確的NNG太麻煩了，因此就用近似的kNN圖來代替。作者解釋，稍微拆一點應該沒關系。
- 搜索路徑：因為NSG的搜索就是從導航點開始的，因此我們構建時就把p當做Query，從導航點開始找搜索路徑做候選集。這樣能更加逼近真實情況。
NSG的構建方法可能導致導航點和密集區(qū)域點的出度爆炸問題。因此在構建過程中強制限制為一個超參m。但是連通度又成了問題。為了保證至少從導航點開始是連通的，構建DFS樹來解決這個問題。
- 但是，可想而知，此時搜索路徑必然會相對長一些。
  【編者注：有種最小生成樹的感覺】

到此為止，我們回顧摘要了提到的四個層面：

確保圖的連通性：DFS樹
降低圖的平均出度：m超參
縮短搜索路徑：NSG可近似MRNG
減少索引大?。簝H僅一個稀疏圖

就都可以有一個解決方案。

3.5.3 Indexing Complexity of NSG

構建索引的復雜度包含兩部分，KNN圖的構建和NSG圖構建。
KNN圖的構建可以用nn-descent（小圖，復雜度 $O(n^{1.16})$ ），Faiss（大圖，復雜度 $O(nlogn)$ ），不在本文討論范圍內，復雜度稱f(n)
由于KNN圖是泰森圖的近似，泰森圖也是一種MSNET圖，所以搜索復雜度 $O(kn^{1/d}logn/\Delta r)$ 。

由于對所有點都做了一次搜索，所以復雜度為 $O(kn^{1+d/d}logn/\Delta r)$ ；
候選集選擇是非?？斓?， $O(nlm)$ ，l是候選集大小，這個候選集只有路徑上的點，不會很大；
DFS樹的構建基本也是線性的。

因此總的復雜度為 $O(kn^{1+d/d}logn/\Delta r+f(n))$ 。基本上是超線性的一個水平。
這里的d不是維數了，可以理解為一個常量，這個復雜度也是從具體的數據集和實驗里模擬出來的，并不是數學推導而來，詳細過程見下圖：

image.png

3.6 Search On NSG

搜索就是從導航點開始，貪婪搜索，因為是MRNG近似，所以搜素復雜度也近似為對數級別。

4. EXPERIMENTS

4.1 Million-Scale ANNS

1M的數據集機器配置：i7-4790K CPU and 32GB memory.
5M的數據集機器配置：Xeon E5-2630 CPU and 96GB memory.

數據集為：