在進(jìn)行各種圖處理、圖計算、圖查詢的時候，內(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ù)實時讀寫型的系統(tǒng)，增刪改查的性能問題會比較重要，它們比較關(guān)注上面 1-6 的操作；對于部分密集計算的系統(tǒng)，對批量讀取的性能會比較重視，側(cè)重上面 5-8 的操作。 不過遺憾的是，無論是常規(guī)的圖查詢，還是進(jìn)階的圖計算，根據(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)行一個簡單的定量分析

?

?

其中，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ù)據(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ù)圖計算系統(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，其原理是類似的。

?

?

CSR 的空間占用是 O(|V|+|E|)，在空間節(jié)省和順序查找上是極其高效的。但在大量插入時，壓縮稀疏矩陣和鄰接矩陣一樣，需要重新開辟空間，效率很低。所以，它適合于計算密集場景但不適合增改頻繁的場景。

CSR 還有一個顯著的優(yōu)點(diǎn)是可以快速獲取每個點(diǎn)的出入度，只要計算 N[x+1]-N[x]，這在判斷一些點(diǎn)是否為超級節(jié)點(diǎn)時很方便。如果不是稀疏矩陣的話，通常會用另外一個單獨(dú)的結(jié)構(gòu)來記錄出入度。

此外，CSR 不容易實現(xiàn)并發(fā)修改，其每次插入都需要對兩個矢量進(jìn)行位移，這并不高效。

鄰接鏈表 Adjacency List ?

和基于矩陣的方式不同，鄰接鏈表 AL 空間上有優(yōu)勢，但對于邊的讀寫上會略微慢一點(diǎn)（指針在內(nèi)存中不能連續(xù)移動）。AL 的做法是把鄰邊（出邊）用 list 或者有序 list 的方式串連起來。由此延伸的一個變種是鄰邊從 list 改為 array。

?

?

AL 相比 CSR 通常不能直接獲得點(diǎn)的出入度，可以通過可以單獨(dú)維護(hù)一個字段實現(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。

?

?

為了控制訪問顆粒度，每個葉子通常會被限定為固定的大小（頁）。這就是在數(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é)幾個變種的主要目的都是為了改善其弱項，大體思路都是分塊和 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ù)留插入位置留空。

事實上，原文中，對于邊矢量，其本質(zhì)是實現(xiàn)為一個 B-Tree，本文先簡化成一個 Array。?

?

?

可以看到，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++

事實上，CSR++[5]在設(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é) ?

最后，由于在圖查詢、圖存儲和圖計算不同場景下，對于圖結(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)程通信帶來的影響。

延伸閱讀 ?

最后，我們來了解下在圖計算/圖算法上的圖操作。

圖算法中的圖操作 在圖計算中，存在多種圖結(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)的所有鄰邊。

接近中心性，通過計算每個節(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)頁之間相互的超鏈接計算的技術(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 的計算過程如下： 假設(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)的值計算的方式如下：

這里的 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 值的計算結(jié)果同樣為零，所以 PageRank 會賦給每個頁面一個最小值。

因此，一個頁面的 PR 值直接取決于指向它的的頁面。如果在最初給每個網(wǎng)頁一個隨機(jī)且非零的 PR 值，經(jīng)過重復(fù)計算，這些頁面的 PR 值會趨向于某個定值，也就是處于收斂的狀態(tài)，即最終結(jié)果。

簡單來說，大多數(shù)迭代圖計算模型都是基于“找到一個點(diǎn)的全部鄰邊”、“找到一個點(diǎn)的另一個鄰點(diǎn)”操作。

AIGC 小課堂 ?

在 AIGC 小課堂部分，我們會用 NebulaGraph 接入的 aibot 來講解下文中的部分概念。你如果對 chatgpt 或者是 aibot 有興趣，可以來?https://discuss.nebula-graph.com.cn/?向 aibot 提出你的要求。

?

? ? ? ? 參考文獻(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).

編輯：黃飛

?