引言
最近，基于近鄰圖的近似最近鄰搜尋算法（ANNS）取得了最優的效率和精度權衡。在圖索引上，路徑的單調性對相關ANNS算法的搜尋性能起着至關重要的影響。幾種目前最優的ANNS算法比如HNSW，NSG普遍能使搜尋路徑盡可能的單調遞減，進而避免由于“繞遠路”而降低搜尋效率。本文介紹的幾種proximity graphs是這些ANNS算法的基礎，與目前的實用算法相比，這些proximity graphs有着嚴格的形式化定義，這給理論分析相關性質帶來便利，進而也給實用的ANNS算法提供理論保證和優化方向。接下來，我們主要分析proximity graphs的單調性，proximity graphs包括德勞内圖（Delaunay Graph, 它與voronoi diagram對偶）、Relative Neighborhood Graph (RNG)、Gabriel Graph (GG)、Minimum Spanning Trees (MST)。
首先給出結論：Delaunay Graph 是單調的圖，而RNG, GG和MST都不是單調的圖。
何為圖的單調性
在此之前，我們需要先了解一下什麼是單調路徑？對于圖G上的一個m個依次鄰接的頂點形成的路徑 ( v 1 , v 2 , ⋯ , v m ) (v_{1},v_{2},\cdots, v_{m}) (v1,v2,⋯,vm)，若 d i s t ( v 1 , v m ) > d i s t ( v 2 , v m ) > ⋯ > d i s t ( v m − 1 , v m ) dist(v_1,v_m) > dist (v_2, v_m) > \cdots > dist(v_{m-1},v_m) dist(v1,vm)>dist(v2,vm)>⋯>dist(vm−1,vm)，則該路徑是一條單調路徑， d i s t ( , ) dist(,) dist(,)表示兩個頂點之間的距離。如果一個圖G的任意兩個頂點之間均存在單調路徑，則圖G便是單調圖了。
如何證明一個圖不是單調的
隻需要舉一個反例就行了。任意畫幾個點，分别根據RNG, GG和MST的定義建立相應的圖結構，很容易找到不存在單調路徑的例子。
證明DG是單調的
下面證明DG是單調的。在此之前先給出一個定理。
定理1. 對于DG中的任意兩個頂點 v a v_a va和 v j v_j vj，存在一個德勞内邊 e a k e_{ak} eak滿足 d ( v k , v j ) < d ( v a , v j ) d(v_k, v_j) < d(v_a, v_j) d(vk,vj)<d(va,vj)。
證明：給定在資料集S上的DG。 v a v_a va可能在DG的邊界（如圖1(a)）或在DG的内部（如圖1(b)）兩種情況。但無論哪一種情況， v a v_a va對應的Voronoi diagram（圖1中虛線圍成的綠色多邊形區域，記為 V ( v a ) V(v_a) V(va)）都不包含其它點（這是由定義保證的），是以 v j v_j vj一定落在 V ( v a ) V(v_a) V(va)外面。是以，連接配接 v a v_a va和 v j v_j vj的線段一定經過 V ( v a ) V(v_a) V(va)的至少一條邊。記這條邊為 e a k e_{ak} eak的垂直平分線 h a k h_{ak} hak， v j v_j vj和 v k v_k vk在 h a k h_{ak} hak的同一側，故 d ( v k , v j ) < d ( v a , v j ) d(v_k, v_j) < d(v_a, v_j) d(vk,vj)<d(va,vj)。
圖1 (a)$v_a$位于邊界，(b)$v_a$位于内部
下面證明DG是單調的。
證明：我們隻需證明DG中的任意兩個點 v a v_a va和 v j v_j vj，總存在一條由 v a v_a va至 v j v_j vj的單調路徑。若 v j v_j vj是 v a v_a va的鄰居，則單調路徑是顯然的。接下來，我們考慮 v a v_a va與 v j v_j vj不鄰接的情況。根據定理1，存在一條邊 e a k 1 e_{ak_1} eak1，滿足 d ( v k 1 , v j ) < d ( v a , v j ) d(v_{k_1},v_j) < d(v_a,v_j) d(vk1,vj)<d(va,vj)，存在邊 e k 1 k 2 e_{k_{1}k_2} ek1k2，滿足 d ( v k 2 , v j ) < d ( v k 1 , v j ) d(v_{k_2}, v_j) < d(v_{k_1},v_j) d(vk2,vj)<d(vk1,vj) … …，最終，存在邊 e k i j e_{k_ij} ekij，滿足 d ( v j , v j ) < d ( v k i ) , v j ) d(v_j, v_j) < d(v_{k_i)},v_j) d(vj,vj)<d(vki),vj)。進而路徑 ( v a , v k 1 , ⋯ , v k i , v j ) (v_a, v_{k_1}, \cdots,v_{k_i},v_{j}) (va,vk1,⋯,vki,vj)滿足 d ( v a , v j ) > d ( v k 1 , v j ) > d ( v k 2 , v j ) > ⋯ > d ( v k i , v j ) > d ( v j , v j ) d(v_a, v_j) > d(v_{k_1}, v_j) > d(v_{k_2},v_j) > \cdots > d(v_{k_i},v_j) > d(v_j, v_j) d(va,vj)>d(vk1,vj)>d(vk2,vj)>⋯>d(vki,vj)>d(vj,vj)，即是一條單調路徑。
RNG幾乎是單調的
雖然不能確定RNG是單調的，但在大部分情況下RNG是單調的，而且RNG是幾乎所有單調圖的子圖。
圖2 邊$e_{ik}$不屬于RNG
如圖2所示，邊 e i j ∈ e_{ij} \in eij∈ RNG，則 l u n e ( i , j ) lune(i,j) lune(i,j)（紅色圓弧包圍的部分）是空的，即裡面沒有其它點（RNG的定義決定的）。是以，一條從 v i v_i vi至 v j v_j vj且不包含 e i j e_{ij} eij的單調路徑的中間點必然落在紅色圓弧上，即圖3所示的 v k 1 v_{k_1} vk1。
圖3 邊$e_{ij}$是備援邊
在圖3中， ( v i , v k 1 , v j ) (v_i, v_{{k_1}},v_j) (vi,vk1,vj)是單調路徑，此時， e i j e_{ij} eij就是備援邊，因為可通過其它單調路徑由 v i v_i vi到 v j v_j vj。是以，就RNG而言，若存在備援邊，則可替代單調路徑的中間點必須落在圖2的紅色圓弧上，發生這種情況的機率是非常小的。
參考文獻
Kurup, G. D. (1992). A database organized on the basis of similarities with applications in computer vision.
部落格位址：mzwang.top