圖數據壓縮技術綜述*

李鳳英，楊恩乙，董榮勝

(桂林電子科技大學可信軟件重點實驗室,廣西 桂林 541004)

1 引言

隨著大數據時代的到來，數據規模以前所未有的方式不斷增長，數據結構也呈現出復雜性和多樣性。如何對其有效地描述、存儲和分析已成為當前的研究熱點和難點。圖通常被看成是一系列節點和節點關系的集合[1]，節點對應于實體，邊對應于實體關系，非常適合描述關聯性數據及內部有一定結構的數據，如社交網絡[2]、知識圖譜[3]等。

研究表明，大多數領域的問題都可以通過圖的相關理論來解決。在Web網絡分析[4]中，實體和它們的關系可以表示成有向無權圖，節點表示網頁，邊表示網頁之間的鏈接，節點標識表示不同的域名。在這種表示形式下，查詢給定的實體關系和偵測特定的團體，可以轉化為圖的鄰居查詢和子圖匹配[5 - 7]問題。在化學數據分析中，從給定的化合物集中挖掘常見的原子團，可以轉化為頻繁子圖查詢[8]問題。在蛋白質交互網絡分析中，衡量給定的某2個蛋白質發生作用的概率時，可以用不確定圖[9,10]建模得以解決。可見，圖在眾多領域都有著重要的研究價值。

隨著圖在各個領域的廣泛應用，傳統的圖存儲結構已經不能支持超大規模圖數據的管理和分析。比如具有一百萬個節點的社交網絡，鄰接矩陣的大小(2個節點之間的1條邊存儲空間為1 bit)大約為116 GB，大多數計算機不會有如此大的主存儲器來加載圖并執行社交網絡分析。中國互聯網絡中心2018年發布的《第41次中國互聯網絡發展狀況報告》[11]中提到，網頁的數量約為2 600億。若采用圖模型存儲上述網頁節點及節點關系，至少需要42 TB的存儲空間。并且隨著因特網的不斷發展，需要的存儲開銷也越來越大。如何存儲和操作上億萬個節點的圖數據，國內外研究人員主要從以下3個方向做了大量的研究：

(1)外部存儲技術[12,13]：針對大規模圖數據無法一次裝入內存問題，研究人員一方面將圖數據存儲到價格低廉、容量大的外部存儲器(硬盤或軟盤)，另一方面設計更加高效的I/O算法來避免更多的I/O開銷。

(2)分布式存儲技術[14]：將圖數據分割為多個部分，存儲到不同的分布式計算機中，但這會帶來更多的通信開銷和CPU資源消耗。

(3)圖數據壓縮技術[15 - 17]：主要思想是消除圖數據中的冗余信息，將圖數據以壓縮的形式存儲到內存中。

相對前2種技術，第(3)種技術時間開銷相對降低，而且可以適用于任何類型的圖數據。

本文主要從3個方面討論圖數據壓縮技術:

(1)基于鄰接矩陣的壓縮技術，主要思想是盡可能地壓縮鄰接矩陣中的“0”元素。

(2)基于鄰接表的壓縮技術，主要思想是利用節點的鄰居節點集的相似性和局部引用性來進行壓縮。

(3)基于形式化方法的壓縮技術，主要思想是對所給的圖進行編碼，使其轉化為布爾代數，再利用決策圖對布爾代數進行表示和化簡。

本文的結構如下：首先介紹3類壓縮技術，分別為基于鄰接矩陣的壓縮技術、基于形式化方法的壓縮技術和基于鄰接表的壓縮技術。在此基礎上，為了充分說明形式化方法對于圖數據壓縮的優勢，我們給出了相關的實驗數據對比，并預測了未來圖數據壓縮發展方向。

2 基于鄰接矩陣的壓縮技術

Broder等人[18]和Raghavan等人[19]的研究表明，大量的圖特征函數服從冪律分布，其鄰接矩陣往往具有一定的稀疏性和聚類性。Brisaboa等人[20]利用鄰接矩陣的特征提出了k2-tree，取得了較好的時間/空間均衡。k2-tree的構造過程主要包括以下2個步驟：

步驟1對于1個給定的n×n鄰接矩陣，首先判斷n是否為k的冪。若滿足條件，轉到步驟2；若n不是k的冪，增加矩陣中的行和列使得n=ks(s為正整數)，其中增加的行和列的元素用“0”填充，然后再轉到步驟2進行遞歸劃分。

步驟2進行遞歸劃分：根據MXQuntree規則[21]把矩陣劃分為k2個大小一致的子矩陣。如果子矩陣中的元素至少有1個為1，那么把這種矩陣標記為1,否則標記為0,自上而下，自左而右排列這些值，它們將作為根節點的4個兒子節點，樹的第1層節點構造完畢。將標記為1的矩陣再進行遞歸處理，它們的值將作為樹的第2層節點，如此重復直到劃分后的矩陣全部為0或者已經劃分到原始矩陣中的某個元素，遞歸停止。

如圖1所示是1個具有4個節點的網頁圖所對應的鄰接矩陣以及k2-tree(n是k的冪)。圖2所示是1個具有11個節點的網頁圖所對應的鄰接矩陣以及k2-tree(n不是k的冪)，矩陣中的深色部分是為滿足條件所增加的行和列。

Figure 1 k2-tree corresponding to 4*4 adjacency matrix(k=2)圖1 4×4 鄰接矩陣所對應的k2-tree(k=2)

Figure 2 Extension of matrix and construction of k2-tree when k=2圖2 k=2 時矩陣的拓展和k2-tree 構建

如圖2所示，若用鄰接矩陣來存儲節點數為11的網頁圖，需要的存儲空間為121 bit。若采用k2-tree存儲，存儲空間為72 bit。可見k2-tree比鄰接矩陣具有更好的空間利用率，并且隨著圖節點數目的不斷增加，k2-tree節省的存儲空間會越來越多。不僅如此，k2-tree還支持在常數時間范圍內查詢節點的直接鄰居和反向鄰居。

k2-tree能夠緊湊地表示圖數據，但傳統的k2-tree對于圖的鄰接矩陣的壓縮還存在不足：(1)網頁圖中的節點和鏈接分布嚴重依賴于URL排序。若采用傳統的k2-tree思想機械地劃分網頁圖，會導致稠密區域和稀疏區域劃分到同1個子矩陣中，這會使得空間利用率降低。(2)k2-tree的鄰居查詢時間與k2-tree的高度成正比，面對上億個節點的圖數據，若不對其進行處理，鄰居查詢時間會大大增加。

為了更加有效、緊湊地壓縮表示網頁圖，Claude等人[22]利用網頁圖中域特有的規律，提出了k2-partition。他們沿著對角線把圖劃分成不同的域，對不同的域用傳統的k2-tree表示，實現了較好的時間/空間均衡。以下用實例來說明如何對圖數據進行k2-partition表示。

采用傳統的k2-tree表示圖2中的矩陣需要72 bit的存儲空間，而采用k2-partition表示圖3和圖4中的矩陣，需要的存儲空間為64 bit，存儲空間需求有所改善，并且隨著圖節點的增加，效果會越來越明顯。在傳統的k2-tree中查詢給定節點的鄰居信息的時間與樹的高度成正比，在k2-partition中由于降低了樹的高度，因此能獲得更好的查詢時間。

Figure 3 Dividing the graph into domains圖3 對圖進行分域處理

Figure 4 k2-tree representation of different domains圖4 不同域的k2-tree表示

出于對多維數據如時序圖(節點關系隨時間改變的動態圖)、社交網絡圖和引文網絡圖緊湊表示的需要，Caro等人[23]利用k2-tree的構造思想提出了kd-tree。kd-tree是k2-tree的一般化形式，通常用來表示d維的二元矩陣，對于1個規模為n1×n2×…×nd的d維矩陣，將其遞歸地劃分為kd個子矩陣，為了簡化分析，假設對于每一個i(d≥i≥1)都有ni=n，其中每1個樹中的節點都擁有kd個兒子節點來表示對應的子矩陣。對于每1個子矩陣，按照從高維到低維的次序來確定kd-tree中的第1層至最后1層的值，如果子矩陣存在“1”值的元素，使用“1”來表示，如果為“0”，使用“0”來表示。圖5表示了不同維度下kd-tree(k=2)表示方法。

3 基于形式化方法的壓縮技術

Figure 5 Construction of kd -tree in different dimensions(d is the dimension of data,k=2)圖5 不同維度的kd-tree的構建(d為數據的維度，k=2)

二叉決策圖BDD(Binary Decision Diagram)作為一種新型的數據結構，不僅是解決布爾代數表示與計算的最為有效的工具[24 - 26],還是符號模型檢驗技術[27,28]的核心。2007年,楊志飛等人[29]將符號計算運用到大規模圖數據的壓縮表示中，核心思想是將圖中的節點進行二進制編碼，把圖中的鏈接關系轉化為布爾代數，進一步布爾代數可以通過有序二叉決策圖OBDD(Ordered Binary Decision Diagram)求解。利用布爾代數中節點取值的冗余，衍生出OBDD的化簡規則和刪除規則，以此來共享子圖，提高存儲效率。在這種表示形式下，查詢圖中節點的度數、判斷2個節點是否存在鏈接關系、向圖中增加或者刪除邊和圖的同構問題分別可以轉化為OBDD的可滿足性問題、OBDD的求值操作、OBDD的apply操作和OBDD的等價性判定[30]。將圖轉化為OBDD的具體思想為：對于1個具有n個節點的有向圖，利用布爾變量對節點和邊進行編碼，將其轉化為布爾表達式。如圖6a中具有4個節點，故需要2個布爾變量。對于圖6a中的有向邊，則需要2組布爾變量來分別表示有向邊的起點和終點，設有向邊的起點用x=x1x2表示，終點用y=y1y2表示，其中x1，x2，y1，y2∈{0,1}，由于節點0和節點1存在有向邊，設節點0的編碼為x′1x′2(表示x1取1，x2取1)，節點1的編碼為y′1y2(表示y1取1，y2取1)，則有向邊可表示為x′1x′2y′1y2。基于上述方法，編碼每1條邊，便可得到該圖對應的OBDD，如圖6b所示是圖6a有向圖所對應的OBDD。由于OBDD的終節點只能為0或1,所以它只能表示無權圖。Bahar等人[31]提出了代數決策圖ADD(Algebraic Decision Diagram)，進一步把布爾代數拓展到偽布爾代數，將無權圖拓展到帶權圖，進一步豐富了圖的布爾代數表示方法。將圖轉化為ADD的思想和OBDD類似，其中的區別在于ADD的終節點不再是0或1，而是圖中存在的每1條邊的權重值。如圖7所示是4個節點的帶權有向圖所對應的鄰接矩陣MG以及代數決策圖。

Figure 6 An OBDD representation of a digraph圖6 有向圖的OBDD表示

Figure 7 An ADD representation of a weighted graph圖7 帶權圖的ADD表示

隨著圖數據規模的不斷增長，如何更加有效地緊湊表示圖數據，成為當前的一個研究重點。文獻[20]提到k2-tree能很好地壓縮鄰接矩陣，實現較好的時間/空間均衡，但k2-tree還面臨以下問題：(1)k2-tree中還存在大量的同構子樹。(2)k2-tree只能對稀疏圖進行壓縮。(3)k2-tree只能表示靜態圖，不能向其中增加或者刪除邊。

針對上述問題，董榮勝等人[32]把多值決策圖MDD(Multi-value Decision Diagram)[33]和k2-tree進行結合,提出了k2-MDD，利用MDD的刪除規則和化簡規則以及多變量取值性質進行相同子圖的合并，構造過程主要包括3步：

步驟1將所給的鄰接矩陣用傳統的k2-tree表示。

步驟2刪除k2-tree中所有的0節點，合并k2-tree葉子節點中為1的節點。

步驟3對k2-tree每個分支進行二進制編碼(k=2)，節點值相等且兒子節點相同的節點合并(共享子圖)。

圖8所示是11個頂點的鄰接矩陣的k2-tree表示。圖9所示是傳統的k2-tree中的同構子樹的分布，相同的子樹用大小相等的方框注明。圖10表示k2-tree的MDD。

Figure 8 k2-tree representation of an adjacency matrix圖8 鄰接矩陣的k2-tree表示

Figure 9 Isomorphic subtree distribution of k2-tree圖9 k2-tree的同構子樹分布

Figure 10 MDD representation of a k2-tree圖10 k2-tree的MDD表示

4 基于鄰接表的壓縮技術

根據研究表明，如果所有網頁圖的URLs按照字典序排序，大多數的網頁圖具有以下2種特性[34,35]:

(1)局部性：對于某個頁面來說，它的直接鄰居集合彼此之間挨得很近。

(2)相似性：位置上靠得很近的一些網頁集，它們的后繼集很相似。

利用網頁的局部性，Boldi等人[36]提出了空隙編碼,其思想為用2個連續的節點標簽值來替代原始節點標簽值，設A(x)=(a1,a2,a3,…,an)，x為第x個節點的標簽值，a1,a2,a3,…,an為x的直接鄰居，則x對應的空隙編碼為B(x)=(c(a1-x),a2-a1-1,a3-a2-1,…,an-an-1-1)。式(1)為計算A(x)中a1的空隙編碼標簽值。

(1)

表1是網頁圖中截取的小部分鄰接表，表2是鄰接表對應的空隙編碼。

Table 1 Traditional adjacency table representation表1 傳統的鄰接表表示

Table 2 Void coding representation表2 空隙編碼表示

圖數據規模的不斷增長使得節點標簽值的位數不斷增加，空隙編碼的本質為壓縮節點的標簽值，減少所需要的存儲空間。

利用網頁的相似性，Suel等人[37]提出了參考壓縮，其思想是用1個節點的鄰接表來表示其余的鄰接表，設s(x),s(y)分別為2個節點的出度表，s(x)稱為參考表，s(y)稱為復制表，y-x稱為參考系數，用r表示。若s(x)的后繼在s(y)中也存在，那么復制表中對應位置為1，否則為0。進一步若s(y)的后繼在s(x)中不存在，記這些節點為額外節點。表3是鄰接表的參考壓縮。

上述2種技術都要求節點的直接鄰居集合是有序的，如果網頁圖需要保存最原始的鏈接順序，上面的方法并不適用。

Adler和Faust等人[38,39]2010年發現，

Table 3 Reference compressed of adjacency table表3 鄰接表的參考壓縮

鄰接表的節點之間的后繼有許多相似的信息，這意味著數據還存在一定的冗余[38,39]，Repair算法[40]應運而生。其算法思想是把所有節點的后繼看成1個序列T，每1次在序列中用s(s為從來沒有在T中出現的符號)替換T中最頻繁的符號對，直到序列T不再出現頻繁模式。假設圖G=(V,E)，T(G)=v1v1.1v1.2v1.3…v1.nv2v2.1v2.2v2.3…v2.n…vnvn.1vn.2vn.3…vn.n，其中v1為第1個節點的標簽值，v1.n為第1個節點的后繼。Ptrs[m]為1個指針數組，記錄每1個節點在序列T中的起始位置。圖11是給定圖的鄰接表的Repair壓縮。

Figure 11 Repair compression of an adjacent table圖11 鄰接表的Repair壓縮

Repair算法將1個鄰接表壓縮成1個字典規則R的集合，1個指針數組ptrs，1個序列T。每次查詢節點的信息時，僅僅需要找到該節點的起始位置和終止位置，然后進行部分解壓縮即可。但是，對于大規模圖而言，由于每次都要添加新的規則，字典規則R的集合越來越大，Bille等人[41]對該算法進行了改進,取得了很好的時間/空間均衡。

另1種基于鄰接表的壓縮稱為LZ78算法[42]，由Ziv和Lempel提出，其思想為建立1個字典表，每讀入1個字符，判斷其是否在字典表中，若不存在，則保存字符并建立索引。若存在，則保存索引并加上新的字符作為這個字符串的表示。

具體的算法流程如下[43]：

步驟1建立字典表，并將字典表設置為空。

步驟2依次讀取文本中的1個新的字符，設新字符為C。

步驟3在詞典中查找當前的前綴和新的字符的組合，也就是P+C：

(1)如果在字典表中找到了這個新組合，那么就把前綴P重新進行改寫，需要加上新讀取的字符C。

(2)如果字典表中沒有這個新組合,就要執行保存新組合的操作：

①輸出當前前綴的索引以及字符C。

②把前綴和新讀取的字符串保存在字典表中。

③重新改寫前綴P，將其設置為空。

(3)重復步驟2和步驟3，直到所有的字符串都完成編碼。

LZ78算法和Repair算法在對文本壓縮時有1個區別：T(G)=v1.1v1.2v1.3…v1.nv2.1v2.2v2.3…v2.n…vn.1vn.2vn.3…vn.n，表4所示是圖11所示的鄰接表的LZ78壓縮。

Table 4 LZ78 compression表4 LZ78壓縮結果

LZ78算法和Repair最大的區別在于在壓縮時不用存儲和維護字典表，因為字典表以結果形式輸出了，因此LZ78算法查詢節點信息的速度比Repair算法快，但由于每次解壓過程，從結果的最開始開始構造字典R，所以只能對鄰接表的邊表進行壓縮，限制了LZ78算法的性能。

5 圖數據壓縮技術比較

文獻[17]采用真實的網頁圖數據集和社交網絡數據集對其中提到的所有壓縮技術進行了對比，其數據集來自于米蘭大學LAW[44]，表5給出了網頁圖數據集的相關屬性，表6給出了社交網絡數據集的相關屬性。通過一系列的實驗對比，他們得出k2-tree的壓縮率明顯低于其他算法(Repair，LZ78等算法)的，能實現較好的時間/空間均衡。為了體現出符號計算對于大規模圖數據壓縮處理的優勢，本文將k2-tree分別與OBDD，k2-MDD 2種壓縮技術做了實驗對比，實驗結果如表7和表8所示。

Table 5 Web graph data set表5 網頁圖數據集

Table 6 Social network data set表6 社交網絡數據集

Table 7 Experimental results of web graph表7 網頁圖實驗結果 bit

Table 8 Experimental results of social network 表8 社交網絡實驗結果 bit

實驗結論：在k2-tree，k2-MDD,OBDD中，用1個位串T來記錄除最后1層節點的0值和1值，1個位串L來記錄最后1層節點的0值和1值，T和L的總和為需要的存儲空間。如表7所示，若采用OBDD來壓縮網頁圖，T和L的總和約為k2-tree的21%，若采用k2-MDD來壓縮網頁圖，T和L的總和約為k2-tree的3%，如表8所示，我們用社交網絡數據集來進行實驗對比，分別在enron，dblp-1，dblp-2，dewiki數據集上進行實驗，得到的T和L的總和分別為k2-tree的4.8%，5.1%，4.7%，3%，對存儲空間的需求得到有效的改善。

6 結束語

隨著圖在各個領域的廣泛應用，傳統的圖存儲結構已經不能支持大規模圖數據的管理和操作，如何有效地緊湊表示圖數據并且支持快速的訪問已經成為一項重要的研究任務。本文首先介紹圖數據應用概況和相關的圖數據壓縮表示技術，然后詳細闡述了3種圖數據壓縮技術，并給出了不同壓縮技術的優缺點。通過分析發現，基于形式化方法的圖壓縮技術在處理大規模圖數據時，具有很好的壓縮效果，這也是我們下一步研究的重點。對于圖數據的壓縮，未來可能會結合機器學習的聚類算法和形式化方法來更好地解決數據的冗余問題。由于篇幅有限，本文不可能涵蓋該領域所有的研究內容，希望這篇綜述能對圖數據壓縮技術的研究起到一定的參考作用。