在進(jìn)行各種圖處理、圖計(jì)算、圖查詢的時候，內(nèi)存或是硬盤中如何存儲圖結(jié)構(gòu)是一個影響性能的關(guān)鍵因素。本文主要分析了幾種常見的內(nèi)存圖結(jié)構(gòu)，及其時間、空間復(fù)雜度，希望對你有所啟發(fā)。
通常來說，對于圖結(jié)構(gòu)的幾種常見的基礎(chǔ)操作：
- 插入一個點(diǎn)
- 插入一個邊
- 刪除一個邊
- 刪除一個點(diǎn)的全部鄰邊
- 找到一個點(diǎn)的全部鄰邊
- 找到一個點(diǎn)的另一個鄰點(diǎn)
- 全圖掃描
- 獲取一個點(diǎn)的入度或者出度
這些圖相關(guān)的操作，除了要關(guān)心時間復(fù)雜度之外，需要考慮空間占用的問題。
對于大多數(shù)實(shí)時讀寫型的系統(tǒng)，增刪改查的性能問題會比較重要，它們比較關(guān)注上面 1-6 的操作；對于部分密集計(jì)算的系統(tǒng)，對批量讀取的性能會比較重視，側(cè)重上面 5-8 的操作。
不過遺憾的是，無論是常規(guī)的圖查詢，還是進(jìn)階的圖計(jì)算，根據(jù) RUM 猜想[1]，讀快、寫快、又省空間這樣”既要又要也要”的好事是不存在的。
下面，我們介紹幾個數(shù)據(jù)結(jié)構(gòu)并給出少量的定量分析。
我們先從三個典型的方案（鄰接矩陣、壓縮稀疏矩陣和鄰接表）說起，再介紹幾種近幾年的研究的變種結(jié)構(gòu) PCSR、VCSR、CSR++。
鄰接矩陣 Adjacency Matrix
用矩陣來表示圖結(jié)構(gòu)是大學(xué)里數(shù)據(jù)結(jié)構(gòu)課程中都學(xué)過的知識，也是一種非常直觀的辦法。
點(diǎn) i 與點(diǎn) j 之間有一條邊，等價對應(yīng)于矩陣上 $M_{ij}$ 為 1。當(dāng)然，這里的點(diǎn) ID 是需要連續(xù)排列無空洞。
用矩陣來表示圖結(jié)構(gòu)有明顯的好處，可以復(fù)用大量線性代數(shù)的研究成果：比如圖上模式匹配類的問題等價于矩陣的相乘。
下面是一個模式匹配問題，它的大體意思是在全圖上尋找這樣一種圖結(jié)構(gòu)：
Match (src)-[friend * 2..4]->(fof)
WHERE src.age > 30
RETURN fof
對于這樣一個問題可以直接對應(yīng)右邊的矩陣操作：
比如，2 跳遍歷等價于矩陣 F 自乘；2 - 4 跳遍歷分別等價于 F2、F3、F^4；取屬性等價于乘以一個過濾矩陣。
更進(jìn)一步，由于矩陣操作是天生可以分塊并行加速，這在性能上有極大的優(yōu)勢。
下面，我們對鄰接矩陣操作進(jìn)行一個簡單的定量分析
| 操作 | 時間復(fù)雜度 | 備注 |
|---|---|---|
| 插入一個點(diǎn) | O(n^2) | 對于矩陣來說，增加一個點(diǎn)意味著整個矩陣的維度增加，通常需要另外開辟一塊空間 |
| 插入一個邊 | O(1) | 增加一個邊只是將對應(yīng)的位置置 1 |
| 刪除一個邊 | O(1) | 置0 |
| 刪除一個點(diǎn)的全部鄰邊 | O(n) | 對于某個點(diǎn)所有出邊的刪除對應(yīng)某一行的置0。入邊對應(yīng)某一列，可以批量操作 |
| 找到一個點(diǎn)的全部鄰邊 | O(n) | |
| 找到一個點(diǎn)的給定鄰點(diǎn) | O(1) | |
| 全圖掃描 | O(n^2) |
其中，n=|V|，m=|E|。
優(yōu)化上，批量操作（CPU Cache/SSD block）可以線性增加性能，例如 O(n) 可以降低到 O(n/B)，但不影響定量分析。
由于絕大多數(shù)圖結(jié)構(gòu)是極其稀疏的，因此簡單用鄰接矩陣來表示圖結(jié)構(gòu)，其內(nèi)存會有夸張的浪費(fèi)。更為嚴(yán)重的是，當(dāng)有多種邊類型時，每種邊類型各需要一個鄰接矩陣。這使得裸用矩陣在實(shí)際情況中只能處理很小數(shù)據(jù)量的場景。當(dāng)然，對于現(xiàn)代服務(wù)器動輒幾百 G 的內(nèi)存，如果只有幾億點(diǎn)邊的數(shù)據(jù)量，像是 twitter2010，這并不會是很嚴(yán)重的問題。但大多數(shù)情況下，條件允許的話，大家還是希望找到一些更加經(jīng)濟(jì)的結(jié)構(gòu)。
壓縮稀疏矩陣 CSR/CSC
壓縮稀疏矩陣是一種非常流行和緊湊的圖結(jié)構(gòu)表示方式，大多數(shù)圖計(jì)算系統(tǒng)都采用 CSR。
這里簡單介紹一下 CSR 的結(jié)構(gòu)：
對于點(diǎn) IDx，取鄰居 ID 就是 F[N[x]] 到 F[N[x+1]-1]。
例如，查找點(diǎn) ID2 的鄰居，對應(yīng)為 F[N[2]] 到 F[N[2+1]-1]，對應(yīng)到上圖也即 1 6 8。查找點(diǎn) ID7 的鄰居，對應(yīng)為 F[N[7]] 到 F[N[7+1]-1]，也就是 2 和 4。
另外，CSR 記錄的僅是出邊的信息，如果要考慮入邊就使用 CSC，其原理是類似的。
| 操作 | 時間復(fù)雜度 | 備注 |
|---|---|---|
| 插入一個點(diǎn) | O(1) | 在點(diǎn)矢量尾部增加 |
| 插入一個邊 <u,v> | O(m+n) | 邊矢量，從 u 對應(yīng)的鄰居開始，都向后移動一位；點(diǎn)矢量，從 u 對應(yīng)位置開始每個值加 1 |
| 刪除一個邊 | O(m+n) | 插入邊的逆過程 |
| 刪除一個點(diǎn) v 的全部鄰邊 | O(m+n) | 邊矢量移動 deg(v) 位，點(diǎn)矢量 u 對應(yīng)位置置 0 |
| 找到一個點(diǎn)的全部鄰邊 | O(deg(v)) | |
| 找到一個點(diǎn)的給定鄰點(diǎn) | O(log(deg(v))) | deg(v) 內(nèi)的排序查找 |
| 全圖掃描 | O(m+n) |
CSR 的空間占用是 O(|V|+|E|)，在空間節(jié)省和順序查找上是極其高效的。但在大量插入時，壓縮稀疏矩陣和鄰接矩陣一樣，需要重新開辟空間，效率很低。所以，它適合于計(jì)算密集場景但不適合增改頻繁的場景。
CSR 還有一個顯著的優(yōu)點(diǎn)是可以快速獲取每個點(diǎn)的出入度，只要計(jì)算 N[x+1]-N[x]，這在判斷一些點(diǎn)是否為超級節(jié)點(diǎn)時很方便。如果不是稀疏矩陣的話，通常會用另外一個單獨(dú)的結(jié)構(gòu)來記錄出入度。
此外，CSR 不容易實(shí)現(xiàn)并發(fā)修改，其每次插入都需要對兩個矢量進(jìn)行位移，這并不高效。
這里推薦兩個相關(guān)的開源項(xiàng)目，可以進(jìn)一步了解下 CSR 的使用：
- https://github.com/DrTimothyAldenDavis/GraphBLAS
- https://github.com/GraphBLAS/LAGraph
鄰接鏈表 Adjacency List
和基于矩陣的方式不同，鄰接鏈表 AL 空間上有優(yōu)勢，但對于邊的讀寫上會略微慢一點(diǎn)（指針在內(nèi)存中不能連續(xù)移動）。AL 的做法是把鄰邊（出邊）用 list 或者有序 list 的方式串連起來。由此延伸的一個變種是鄰邊從 list 改為 array。
| 操作 | 時間復(fù)雜度 | 備注 |
|---|---|---|
| 插入一個點(diǎn) | O(1) | 尾插入 |
| 插入一個邊 <u,v> | O(log(deg(u))) | 有序 list |
| 刪除一個邊 | O(log(deg(u))) | |
| 刪除一個點(diǎn) v 的全部鄰邊 | O(1) | |
| 找到一個點(diǎn)的全部鄰邊 | O(deg(u)) | |
| 找到一個點(diǎn)的給定鄰點(diǎn) | O(log(deg(u))) | |
| 全圖掃描 | O(n+m) |
AL 相比 CSR 通常不能直接獲得點(diǎn)的出入度，可以通過可以單獨(dú)維護(hù)一個字段實(shí)現(xiàn)該功能。
此外，鄰接表并不需要 ID 連續(xù)排布，對于頻繁增刪點(diǎn)的場景特別友好。AL 對于并發(fā)修改的支持也更友好，天然在點(diǎn)級別有并行度。當(dāng)然，對于超級節(jié)點(diǎn)，直接用 list 的方式，還是會有些性能的問題要考慮；優(yōu)化上可能會進(jìn)一步改造成 Blocked list 的方式，可以帶來更好的數(shù)據(jù)局部性和細(xì)顆粒度。
由于 ID 不用嚴(yán)格連續(xù)排布，AL 的一個常見變種就是 Tree。
Tree
在這種結(jié)構(gòu)中，一個點(diǎn)和其所有的鄰邊被建模成了 key-value，key 是點(diǎn) ID，value 是所有鄰邊的編碼。Key 通過 Tree 的方式組織在一起。這里的樹可以是 B-Tree 等各變種 Tree。雖然本文沒有討論圖屬性，但 value 中也是可以存放 value。
| 操作 | 時間復(fù)雜度 | 備注 |
|---|---|---|
| 插入一個點(diǎn) | O(log(n)) | |
| 插入一個邊 <u,v> | O(deg(u) log(n)) | |
| 刪除一個邊 | O(deg(u) log(n)) | |
| 刪除一個點(diǎn) v 的全部鄰邊 | O(log(n)) | |
| 找到一個點(diǎn)的全部鄰邊 | O(deg(u) log(n)) | |
| 找到一個點(diǎn)的給定鄰點(diǎn) | O(log(n deg(u)) | |
| 全圖掃描 | O(n+m) |
為了控制訪問顆粒度，每個葉子通常會被限定為固定的大小（頁）。這就是在數(shù)據(jù)庫類系統(tǒng)里面最常見的辦法 B-tree。為了增改方便，也可以把每頁的 in-place update 改成 Copy-On-Write 的方式；一個典型的代表就是 LLAMA[2]，但這種多版本的讀取通常會需要更多的空間，并且當(dāng)有大量累積修改時，需要定期的多版本合并以降低跨快照讀。某種程度上，它和 LSM-Tree 的思路有些接近。
基于 CSR 的變種 PCSR 和 VCSR
由于 CSR 在空間和讀性能上有很大的優(yōu)勢，但在插入時的耗時和空間上都很弱，因此本節(jié)幾個變種的主要目的都是為了改善其弱項(xiàng)，大體思路都是分塊和 buffer。
在 CSR 的邊矢量進(jìn)行增刪時可以注意到，主要耗時是在對于矢量的元素位移上。因此，一個直觀的思路是預(yù)留一些插入空白位，在刪除時也不立刻回收這些空白。
而分塊思想，是指將一些局部數(shù)據(jù)放在同一個分塊內(nèi)，例如 Tree 中每個 page 就是一種分塊的方式。與此對應(yīng)的是，buffer 空白之間的連續(xù)區(qū)域。
PCSR
PCSR [3]的基本思想是：對于點(diǎn)矢量，其元素從一個值改為對應(yīng)邊矢量中對應(yīng)鄰邊位置的 <起點(diǎn),終點(diǎn)>。而對于邊矢量，在這些分塊所對應(yīng)邊界放置哨兵 sentinel，上圖中的 S，上圖的 “-“ 對應(yīng)預(yù)留插入位置留空。
事實(shí)上，原文中，對于邊矢量，其本質(zhì)是實(shí)現(xiàn)為一個 B-Tree，本文先簡化成一個 Array。
| 操作 | 時間復(fù)雜度 | 備注 |
|---|---|---|
| 插入一個點(diǎn) | O(1) | 直接在點(diǎn)矢量和邊矢量的尾插入 |
| 插入一個邊 <u,v> | O(log(deg(u)) | 邊矢量對應(yīng)分片的二分+空位查找 |
| 刪除一個邊 | O(log(deg(u)) | |
| 刪除一個點(diǎn)v的全部鄰邊 | O(1) | 邊矢量對應(yīng)分片置空，點(diǎn)矢量對應(yīng) ID 位置置空 |
| 找到一個點(diǎn)的全部鄰邊 | O(deg(u)) | |
| 找到一個點(diǎn)的給定鄰點(diǎn) | O(log(deg(u)) | |
| 全圖掃描 | O(n+m) |
可以看到，PCSR 的預(yù)留位置多少都是需要重平衡，不能過多也不能不足。特別是大批量增刪時，對預(yù)留位置的處理會是一個較重的操作。
此外，如果把 PMA 的 B-Tree 以及需要 rebalance 的本質(zhì)考慮進(jìn)去，其和前述 Tree 方式的區(qū)別并不是很大。
VCSR
VCSR[4]主要是對 PCSR 的一個改進(jìn)，其樸素思想是 PCSR 的留空是均勻的，而大多數(shù)圖結(jié)構(gòu)的出入度，是存在 20-80 這樣的冪率特征，而 PCSR 的一個主要痛點(diǎn)是頻繁的 rebalance。VCSR 的做法是為每個分塊預(yù)留空間正比于其分塊內(nèi)的點(diǎn)的數(shù)量，即：邊矢量中，一個分塊內(nèi)，如果點(diǎn)的數(shù)量多，就多預(yù)留一些空位。在直覺上，點(diǎn)數(shù)量多時，其分塊對應(yīng)的邊插入會更多一些，這樣可以減少 rebalance 的頻率。
此外，VCSR 還有些版本號之類的優(yōu)化。
CSR++
事實(shí)上，CSR++[5]在設(shè)計(jì)上其實(shí)更接近一種 AL/Tree 的變種，而不是 CSR。它主要有三個方面的優(yōu)化：
第一，對于 Vertex Array 再分段，將一個大的 Array 拆成多段，這樣可以有更細(xì)的讀寫顆粒度。通過 段 ID + 點(diǎn) ID 來定位每個點(diǎn)和其鄰邊。
第二，Vertex Array 中每個元素，除了記錄點(diǎn) ID 之外，對于鄰邊數(shù)量很少的點(diǎn)，直接把鄰居 ID 也對齊地塞 inline 進(jìn)去。
對于大多數(shù)的點(diǎn)，其鄰邊就不需要單獨(dú)的 Edge Array 來存儲了。
可以看到這種方式在圖比較稀疏的時候，對于 CPU Cache 掃描是很友好的。
第三，對于每個點(diǎn)的鄰邊，采用copy-on-write、標(biāo)記刪除等常見的優(yōu)化辦法，構(gòu)建成類似 std::vector 結(jié)構(gòu)。
小結(jié)
最后，由于在圖查詢、圖存儲和圖計(jì)算不同場景下，對于圖結(jié)構(gòu)的讀寫掃描和生命周期都有些不同的要求，不同的數(shù)據(jù)結(jié)構(gòu)也有不同的優(yōu)劣。
當(dāng)然，本文只是討論了圖結(jié)構(gòu)可以放在內(nèi)存中的情況。當(dāng)不得不把部分?jǐn)?shù)據(jù)放在硬盤上時，問題就完全不同了。當(dāng)然本文也沒有討論不同 CPU 對于不同距離內(nèi)存的性能差異 NUMA，或者跨進(jìn)程通信帶來的影響。
延伸閱讀
最后，我們來了解下在圖計(jì)算/圖算法上的圖操作。
圖算法中的圖操作
在圖計(jì)算中，存在多種圖結(jié)構(gòu)算法，可能會涉及多種基礎(chǔ)操作。
中心性 Centrality Algorithms，一種衡量一個節(jié)點(diǎn)在整個網(wǎng)絡(luò)圖中所在中心程度的算法，包括：度中心性、接近中心性、介數(shù)中心性等，會涉及“找到一個點(diǎn)的全部鄰邊”、“找到一個點(diǎn)的另一個鄰點(diǎn)”、“全圖掃描”的操作組合。
- 度中心性通過節(jié)點(diǎn)的度數(shù)，即關(guān)聯(lián)的邊數(shù)來刻畫節(jié)點(diǎn)的受歡迎程度，這將會要求找到一個點(diǎn)的所有鄰邊。
- 接近中心性，通過計(jì)算每個節(jié)點(diǎn)到全圖其他所有節(jié)點(diǎn)的路徑和來刻畫節(jié)點(diǎn)與其他所有節(jié)點(diǎn)的關(guān)系密切程度，這將會要求進(jìn)行全圖掃描，查找點(diǎn)和圖中所有點(diǎn)的路徑信息。
- 介數(shù)中心性，則用于衡量一個頂點(diǎn)出現(xiàn)在其他任意兩個頂點(diǎn)對之間最短路徑上的次數(shù)，從而來刻畫節(jié)點(diǎn)的重要性，這將會要求進(jìn)行全圖掃描，找到一個點(diǎn)和它的鄰點(diǎn)及路徑信息
PageRank，又稱網(wǎng)頁排名、谷歌左側(cè)排名，是一種由搜索引擎根據(jù)網(wǎng)頁之間相互的超鏈接計(jì)算的技術(shù)作為網(wǎng)頁排名的要素之一的排名方法。它以 Google 公司創(chuàng)辦人拉里·佩奇 Larry Page 之姓來命名。Google 用它來體現(xiàn)網(wǎng)頁的相關(guān)性和重要性，在搜索引擎優(yōu)化操作中是經(jīng)常被用來評估網(wǎng)頁優(yōu)化的成效因素之一。一般來說，PageRank 的值越高，表示其被很多其他網(wǎng)頁鏈接到，說明它的重要性很高；而如果一個 PageRank 很高的網(wǎng)頁鏈接到其他網(wǎng)頁，被鏈接的網(wǎng)頁的 PageRank值也會隨之提高。PageRank 的計(jì)算過程如下：
假設(shè)由 4 個網(wǎng)頁組成的集合：A、B、C、D，每個頁面的初始 PageRank 值相同，為了滿足概率值為 0-1 之間，假設(shè)這個值為 0.25。
如果所有頁面都只鏈接至 A，如下圖，則 A 點(diǎn)的值將是 B、C、D 的 PageRank 值的和。
倘若是下圖這種圖結(jié)構(gòu)：
B 鏈接到 C，D 鏈接到 B 和 C，A 點(diǎn)的值計(jì)算的方式如下：
這里的 2、1、3，分別是 B 點(diǎn)對外鏈接的 2 條邊，C 點(diǎn)對外鏈接的 1 條邊，D 點(diǎn)對外鏈接的 3 條邊。
換句話說，算法將根據(jù)每個頁面連出總數(shù)平分該頁面的 PR 值，并將其加到其所指向的頁面：
最后，所有這些 PR 值被換算成百分比形式再乘上一個修正系數(shù)。
由于“沒有向外鏈接的網(wǎng)頁”傳遞出去的 PR 值會是0，這時候如果遞歸的話，會導(dǎo)致指向它的頁面的 PR 值的計(jì)算結(jié)果同樣為零，所以 PageRank 會賦給每個頁面一個最小值。
因此，一個頁面的 PR 值直接取決于指向它的的頁面。如果在最初給每個網(wǎng)頁一個隨機(jī)且非零的 PR 值，經(jīng)過重復(fù)計(jì)算，這些頁面的 PR 值會趨向于某個定值，也就是處于收斂的狀態(tài)，即最終結(jié)果。
簡單來說，大多數(shù)迭代圖計(jì)算模型都是基于“找到一個點(diǎn)的全部鄰邊”、“找到一個點(diǎn)的另一個鄰點(diǎn)”操作。文章來源：http://www.zghlxwxcb.cn/news/detail-437318.html
AIGC 小課堂
在 AIGC 小課堂部分，我們會用 NebulaGraph 接入的 aibot 來講解下文中的部分概念。你如果對 chatgpt 或者是 aibot 有興趣，可以來 https://discuss.nebula-graph.com.cn/ 向 aibot 提出你的要求。文章來源地址http://www.zghlxwxcb.cn/news/detail-437318.html
參考文獻(xiàn)
- Athanassoulis, M., Kester, M. S., Maas, L. M., et al. (2016). Designing Access Methods: The RUM Conjecture. In EDBT (pp. 461-466).
- Macko, P., Marathe, V. J., Margo, D. W., et al. (2015). Llama: Efficient Graph Analytics Using Large Multiversioned Arrays. In 2015 IEEE 31st International Conference on Data Engineering (pp. 363-374). IEEE.
- Wheatman, B., & Xu, H. (2018). Packed Compressed Sparse Row: A Dynamic Graph Representation. In 2018 IEEE High Performance Extreme Computing Conference (HPEC) (pp. 1-7). IEEE.
- Islam, A. A. R., Dai, D., & Cheng, D. (2022). VCSR: Mutable CSR Graph Format Using Vertex-Centric Packed Memory Array. In 2022 22nd IEEE International Symposium on Cluster, Cloud and Internet Computing (CCGrid) (pp. 71-80). IEEE.
- Firmli, S., Trigonakis, V., Lozi, J. P., et al. (2020). CSR++: A Fast, Scalable, Update-Friendly Graph Data Structure. In 24th International Conference on Principles of Distributed Systems (OPODIS'20).
到了這里，關(guān)于解析內(nèi)存中的高性能圖結(jié)構(gòu)的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
