圖數(shù)據(jù)壓縮技術(shù)綜述*

李鳳英，楊恩乙，董榮勝

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

1 引言

隨著大數(shù)據(jù)時代的到來，數(shù)據(jù)規(guī)模以前所未有的方式不斷增長，數(shù)據(jù)結(jié)構(gòu)也呈現(xiàn)出復(fù)雜性和多樣性。如何對其有效地描述、存儲和分析已成為當前的研究熱點和難點。圖通常被看成是一系列節(jié)點和節(jié)點關(guān)系的集合[1]，節(jié)點對應(yīng)于實體，邊對應(yīng)于實體關(guān)系，非常適合描述關(guān)聯(lián)性數(shù)據(jù)及內(nèi)部有一定結(jié)構(gòu)的數(shù)據(jù)，如社交網(wǎng)絡(luò)[2]、知識圖譜[3]等。

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

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

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

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

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

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

本文主要從3個方面討論圖數(shù)據(jù)壓縮技術(shù):

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

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

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

本文的結(jié)構(gòu)如下：首先介紹3類壓縮技術(shù)，分別為基于鄰接矩陣的壓縮技術(shù)、基于形式化方法的壓縮技術(shù)和基于鄰接表的壓縮技術(shù)。在此基礎(chǔ)上，為了充分說明形式化方法對于圖數(shù)據(jù)壓縮的優(yōu)勢，我們給出了相關(guān)的實驗數(shù)據(jù)對比，并預(yù)測了未來圖數(shù)據(jù)壓縮發(fā)展方向。

2 基于鄰接矩陣的壓縮技術(shù)

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

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

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

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

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

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

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

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

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

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

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

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

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

3 基于形式化方法的壓縮技術(shù)

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

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

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

Figure 7 An ADD representation of a weighted graph圖7 帶權(quán)圖的ADD表示

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

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

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

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

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

圖8所示是11個頂點的鄰接矩陣的k2-tree表示。圖9所示是傳統(tǒng)的k2-tree中的同構(gòu)子樹的分布，相同的子樹用大小相等的方框注明。圖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的同構(gòu)子樹分布

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

4 基于鄰接表的壓縮技術(shù)

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

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

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

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

(1)

表1是網(wǎng)頁圖中截取的小部分鄰接表，表2是鄰接表對應(yīng)的空隙編碼。

Table 1 Traditional adjacency table representation表1 傳統(tǒng)的鄰接表表示

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

圖數(shù)據(jù)規(guī)模的不斷增長使得節(jié)點標簽值的位數(shù)不斷增加，空隙編碼的本質(zhì)為壓縮節(jié)點的標簽值，減少所需要的存儲空間。

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

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

Adler和Faust等人[38,39]2010年發(fā)現(xiàn)，

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

LZ78算法和Repair算法在對文本壓縮時有1個區(qū)別：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壓縮結(jié)果

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

5 圖數(shù)據(jù)壓縮技術(shù)比較

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

Table 5 Web graph data set表5 網(wǎng)頁圖數(shù)據(jù)集

Table 6 Social network data set表6 社交網(wǎng)絡(luò)數(shù)據(jù)集

Table 7 Experimental results of web graph表7 網(wǎng)頁圖實驗結(jié)果 bit

Table 8 Experimental results of social network 表8 社交網(wǎng)絡(luò)實驗結(jié)果 bit

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

6 結(jié)束語

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