知識圖譜壓縮及查詢算法研究

張偉娟，韓 斌

（江蘇科技大學計算機學院，江蘇鎮江 212003）

0 引言

大數據的爆發式增長導致知識圖譜的數據規模不斷增加，由此對知識圖譜進行查詢時載入內存的存儲空間也消耗過大。針對以上問題，目前廣泛采取的解決措施有：分布式或者并行處理、使用便宜且空間大的硬盤以及使用壓縮技術減少空間。分布式并行處理時存在通信開銷大、存取結構復雜以及數據安全難以保障的問題，而空間大的硬盤價格又相對較高。為了實現高效查詢，本文在圖數據存儲形式上采取圖壓縮技術［1］以減小知識圖譜規模。

對知識圖譜的壓縮是為了更好地進行查詢，獲取用戶所需要的信息。可達性查詢［2］是圖查詢方向的一個重要內容。隨著知識圖譜的不斷發展，如何在知識圖譜上進行可達性查詢具有非常重要的現實意義。本文在圖壓縮的基礎上對知識圖譜［3］進行可達性查詢，通過查詢結果判斷壓縮后的圖數據是否會影響查詢效率。

1 相關工作與基本概念

很多研究針對不同的圖數據結構進行壓縮。當數據結構為鄰接表時，Alexandre 等［4］通過聚類和適當的頂點重排以放大鄰接表的復制特性，實現更好的壓縮比。這種方法適用于圖分析任務的核心，如計算PageRank 值，可以很好地節省一部分存儲空間。數據結構為矩陣時，Yu 等［5］在GOFMM 算法基礎上通過消息傳遞接口將其拓展到分布式內存設置上，并且提出一種異步式算法，因此可以從分布式方向上實現分層壓縮思想。針對圖數據的分布式壓縮方向，Payam 等［6］通過Slepian-Wolf 定理導出分布式無損壓縮的速率區域，而分布式壓縮數據使用還需要考慮耦合性等方面的影響。

傳統的圖壓縮技術已經非常成熟，但是針對知識圖譜而言的圖壓縮技術還有待研究。一般圖數據分為有向圖、無向圖，而知識圖譜是帶有語義信息的有向圖形式的知識庫。現有的圖數據壓縮方法不會考慮到知識圖譜中的語義關系，因而要針對知識圖譜設計符合其特性的圖壓縮方法。Katsuhiko 等［7］基于知識圖向量嵌入模型方面提出一種二值化的B-CP 分解算法，這種算法通過二進制值替換實值參數以減小模型規模，雖然減少了知識圖的嵌入模型規模，但不適用于圖數據結構方向的壓縮。李高超等［8］提出的GComIdx 算法就是利用有序的鍵值存儲節點和邊，為查詢提出二級索引和節點索引，并采用傳統壓縮算法降低磁盤空間，這種壓縮方式只是單純利用壓縮完的數據塊載入時間和解壓縮時間小于整體直接載入的時間。這種方式不僅要將圖數據轉化為數據集，還要劃分歸類，并不適用于知識圖譜的存儲模式，反而適用于關系數據庫。而適用于知識圖譜存儲模式的結構概要模型的圖壓縮技術ASSG 算法［9］就是根據節點的標簽及其rank 值劃分節點，這種方法比較粗糙，因為rank 值只是用來衡量節點和出度等于0 的節點的最大距離值。再如OBSQ 壓縮方法［10］也是計算節點語義相似度，將計算好的閾值節點劃分到一起，然后在原本圖結構的基礎上構建邊，不斷調整得到最終壓縮圖。這兩種方法只是單純考慮了節點和框架，并沒有考慮到邊標簽的語義信息，因此這兩種方法并不適合語義豐富的知識圖譜。Wahyudi 等［11］提出一種圖屬性模型的壓縮方式-GPC 算法，這種壓縮方法雖然適合語義豐富的知識圖譜，但為了進一步消除節點以及對節點無關的邊，使得圖的規模進一步縮小，不能完整地保存圖譜的結構信息。

針對圖數據結構的查詢有多種方式，如可達性查詢和子圖匹配查詢，不同查詢方法采用針對不同查詢的圖壓縮設計。本文提出的壓縮算法將節點合并、邊壓縮，在查詢過程中若采用子圖匹配查詢，則已經壓縮的圖數據還需要將其還原并進行子圖匹配，會極大延長查詢時間，若采用可達性查詢，無須還原壓縮后的圖數據，只需判斷兩點之間是否可達，即實體之間是否存在關系，用來檢驗壓縮之后的查詢效率十分方便。因此，本文采用可達性查詢檢驗壓縮后的查詢效率。該方法主要用來判斷兩個節點之間是否可達。早期的可達性查詢研究方法可以分為3 類：Hop 類標簽［12］、傳遞閉包和在線索引類。針對Hop 類查詢算法而言，不需對原圖進行遍歷并且不需要傳遞閉包，從時間和空間復雜度上取得了較好的均衡。其典型算法除傳統的2 跳標簽［13］、3 跳標簽［14］，在2 跳標簽的基礎上又提出了PLL 算法［15］、PPL 算法［16］以及分布式算法［17］。本文采用效果較優的PLL 算法檢驗壓縮后圖的查詢效率。

本文涉及的一些基本概念如下：

定義1資源描述框架（Resource Description Framework，RDF）［18］是一種用于表述萬維網資源的標記語言。通過RDF 以節點—邊—節點的形式展現對資源的描述，其中第一個節點可看作主語（Subject，S）、邊看作謂語（Predicate，P），第二個節點可看成賓語（Object，O），SPO 就是一條三元組記錄。用“小李子的英文名是Leonardo DiCaprio”表示的三元組如圖1 所示，其中“www.kg.com/person/8”是國際資源標識符（Internationalized Resource Identifier，IRI），用來唯一標識“小李子”這個實體，“Kg：EnglishName”用來表示實體和實體之間的關系。

Fig.1 Example of triples圖1 三元組示例

定義2資源描述框架模式（Resource Description Framework Schema，RDFs）［19］是在RDF 的基礎上，提供了一個以“http：//www.w3.org/2000/01/rdf-schema#”為命名空間的詞匯表，作為用戶描述特定領域中類和屬性的標準。其本質是在RDF 的基礎之上描述RDF 數據，使之具象化。比如人和動物、工具這3 個類之間的關系，3 個類分別可以有具體的多個屬性，3 個類之間的關系也可以建立多個屬性值。因此，知識圖譜的數據可以用RDF 數據進行存儲，也可以以有向圖的形式進行存儲。

如表1 所示，這組三元組表述了spinach3 為一種蔬菜，spinach1 是一種綠葉蔬菜，蔬菜類是綠葉蔬菜類的父類，farmer 管理蔬菜，farmer1 管理著spinach2 等。以RDF 圖的形式呈現如圖2 所示，其中“rdf：type”“rdfs：range”“rdf：sub-ClassOf”均是RDFs 用來描述數據，依次代表資源與類之間的實例關系、值域、類與類之間的繼承關系。

Table 1 RDF graph example表1 RDF圖實例

Fig.2 RDFs in directed graph form圖2 有向圖形式的RDFs

定義3 原圖數據結構可用G=(V，E，T，L)表示，其中G為有向圖，V為所有頂點的集合，記V={vi|vi∈V，0 ≤i≤|V|}，E為所有邊的集合，記為E={ei|ei=(s，t) ∈E，s，t∈V}，T為所有屬性值的集合函數，L為邊標簽集合函數。

定義4 等價關系標簽是在對原圖進行壓縮時提出，即不同邊的屬性值相同，記為T(E1)=T(E2)。

定義5 簡圖是原圖基礎上壓縮過后的圖，用G1(V1，E1，T1，L1)表示，其中V1 為簡圖中頂點的集合，E為簡圖中邊的集合，T為簡圖中屬性值的集合函數，L為簡圖中邊標簽集合函數。

查詢過程中所用符號說明如表2所示。

Table 2 Description of symbols used表2 所用符號說明

2 CER壓縮算法設計

針對ASSG 算法存在的壓縮粗糙問題，本文在此基礎上進行改進優化，提出一種適用于知識圖譜的等價關系的壓縮算法CER（Compression based on Equivalence Relation）。在劃分節點時不再采用具有相同標簽和rank 值的等價節點進行劃分，而是采用具有語義關系的等價關系標簽劃分節點。等價關系標簽可能導致的結果有兩種：一種是實體的屬性值一致，另一種是實體屬性值不一致。當多條相同關系（等價邊）的兩個實體（節點）具有相同的屬性值（節點等價），則這多條邊可壓縮為同一條邊；當多條相同關系（等價邊）的多個實體（節點）具有不相同的屬性值（節點不等價），則將這多個實體（節點）劃分為一類并排序。這種保存不會像ASSG 算法模糊邊及邊標簽信息。通過這種壓縮劃分，n個節點會劃分為一個新的節點，而邊則不會再冗余，從而構建出一個全新簡潔的知識圖譜，方便載入內存及查詢。

以上文的RDF 實例圖為例，基于等價關系的壓縮算法主要分為兩個步驟：①遍歷知識圖譜上所有邊標簽信息，若邊標簽相同且一端存在度為1 的節點，則將具有相同屬性值的邊劃分為一類，得到知識圖譜中的關系集合S={S1，S2，S3，...Sn}，其中Si為具體相同屬性值的邊標簽集合；②判斷Si 一端的節點屬性值是否相同。若其中一對節點屬性值不相同但另一對節點屬性值相同且度為1，則將已經劃分在邊集合的邊分裂開來，將具有相同屬性值的節點劃分為一類并在內部進行編碼排序；若兩對節點的屬性值均相同且其中一對度為1，則將邊標簽進行壓縮，并將具有相同屬性值的節點劃分為一類，即得到知識圖譜中相同屬性值的節點集合。若不滿足上述兩個條件，比如兩對節點的屬性值均不相同，或者一對節點屬性值不相同但另一對節點屬性值相同且度不為1等一系列情況，則將邊分裂開來。

該算法從知識圖譜的邊標簽上進行劃分，并不會影響知識圖譜的結構。等價關系的知識圖譜壓縮方法具體示例如圖3所示。

Fig.3 Compressed graph based on equivalence relation圖3 基于等價關系的壓縮圖

在圖3 中，按照CER 壓縮算法順序，首先找到具有相同屬性值且一端存在度為1 的節點的邊標簽為“rdf：type”、“far：host”；然后判斷邊集合內兩端節點的屬性值，以邊標簽“rdf：type”為例，經判斷其一端屬性值相同，為根圓錐狀、鮮綠色等屬性，而另一端蔬菜和綠葉蔬菜的具體屬性值并不相同，因此將其邊標簽“rdf：type”從邊集合中分裂出來，將“en：spinach1”、”en：spinach3”度為1 且相同屬性值合并到同一個節點集；而以邊標簽“far：host”為例，度數為1 的節點為“en：farmer1”和“en：farmer2”，經判斷其屬性值相同，均為勞作、勤勞等屬性；另一端的節點屬性值相同，則對邊標簽“far：host”進行壓縮，并將節點“en：farmer1”和“en：farmer2”放在一個頂點集合中。經過以上壓縮，得到最終壓縮圖。CER 壓縮算法思路如算法1所示。

算法1等價關系的壓縮算法（CER）

本文算法中，第1 行對壓縮圖進行初始化，第2 行遍歷邊標簽；第3 行到第4 行是找到相同的邊標簽，并將其存放入S集合。第5 行到第8 行是判斷邊標簽兩端節點的屬性值，若只有一對節點屬性值相同且度數均為1，則對壓縮進S集合的邊(s，t)進行分裂，同時將屬性值相同的節點存放進節點集合Pi。第9 行同理可得，當節點u和節點s的屬性值相同且度數值均為1 而節點v和節點t的屬性值不同時，分裂(s，t)，Pi集合存放v、t。第10 行到第13 行是針對兩對節點的屬性值均相同且其中一對度為1 的情況，壓縮邊標簽，劃分頂點集。第14 行描述了第3 種情況，即不滿足上述條件的剩余情況下，將存放進S集合的邊標簽分裂出來。等價關系的壓縮算法主要是對邊標簽進行操作，劃分節點集合，時間復雜度為O（|E|log|V|）。此壓縮算法壓縮力度不大，但是可完整保存圖的結構信息，并保全知識圖譜的語義信息。

本文通過PLL 算法檢驗CER 壓縮算法之后是否可提高查詢效率。PLL 算法是在2-hop 的基礎上改進而來，通過剪枝減少遍歷節點數目。傳統的2-hop label 只是通過出、入節點的標簽判斷是否可達，而PLL 算法是在判斷出、入標簽時若已經滿足可達條件，則無需進行BFS 遍歷后續節點。計算步驟為：首先計算各節點的(|outG(u)|+1) ×(|inG(u)|+1)，按照結果進行降序排列，然后進行廣度優先遍歷，在入標簽Lin中加入遍歷得到的節點；同理反向廣度優先遍歷得到出標簽Lout的值。若在構建標簽的過程中發現出標簽和入標簽中已經存在相同的節點值，即可達，則中斷遍歷，對下一個節點進行遍歷。遍歷結束，得到出入標簽之后，查詢是否可達只需要判斷Lout和Lin中是否存在交集。經過預處理將知識圖譜轉化為簡化有向圖，其中節點1和2的屬性值、5和6的屬性值相同，如圖4所示。

在圖4 中，右圖為壓縮后的有向圖，其中A={a1，a2，a3，...，ai}代表邊標簽相同且節點類型不相同的頂點集合，B={b1，b2，b3，...，bi}代表邊標簽相同且節點類型相同的頂點集合。對于右圖使用PLL 算法構建索引如表3所示，按照計算結果排序為3、4、a1、b1、6。以節點3 為例，對節點3 進行正向廣度優先搜索，得到節點b1、4，則在b1、4 的入標簽中加入節點3；反向廣度優先搜索得到節點a1，則在a1 的出標簽中加入節點3。在反向遍歷節點4 這一步時，得到節點3、a1；由于節點a1 到節點4 已經通過節點3可達，則無需將節點4放入節點a1的入標簽中。

Fig.4 Simplified directed graph圖4 簡化的有向圖

可達性查詢，比如Query(a1 →6)=1，這是因為存在相同節點3。

Table 3 PLL labels of vertices in compressed graph表3 壓縮圖中頂點的PLL標簽

3 實驗

3.1 實驗環境

本文實驗所用的機器CPU 配置為Inte（lR）Core（TM）i5-8250U CPU @ 1.60GHz 1.80GHz，內存為8.00G，硬盤為500GB，操作系統為Ubuntu16.04 LTS，算法使用C++語言編寫完成。

3.2 實驗數據

本文所采用的3 個知識圖譜來自各領域的公開泛用數據集，用來評估所提出算法的壓縮率、壓縮時間和查詢時間。其包括Yago 的部分數據集、CN-DBpedia 數據集和XLore 數據集。其中，Yago 的部分數據集包含Wikipedia、WordNet 和GeoNames 3 個來源；CN-pedia 是來源中文百科網站的結構化數據集，其層級為8，有110 萬+個屬性值；XLore 是來源于清華大學的多語言知識圖譜，包含44 萬+個屬性和豐富的語義關系。這些數據需要預處理對實體進行編碼，整理為有向圖的形式，數據集中的頂點集和邊集的信息如表4 所示，其中|V|代表節點的數量，|E|代表邊的數量。

3.3 壓縮效率比較

本文主要比較ASSG 壓縮算法、OBSQ 壓縮算法、GPC壓縮算法和CER 壓縮算法在3 個數據集上的壓縮率、壓縮時間等性能度量，具體如表5所示。

Table 4 Data sets information表4 數據集信息

Table 5 Description of the performance metrics used表5 所用性能度量說明

通過節點和邊兩個方面比較整體壓縮效率，壓縮率越低壓縮效果越好。節點壓縮效率為壓縮后節點個數和壓縮前節點個數之比；邊的壓縮效率為壓縮后邊的個數和壓縮前邊的個數之比。

如圖5 所示，CER 算法在節點壓縮效率上優于OBSQ算法和ASSG 算法，稍遜色于GPC 算法，CER 壓縮算法在壓縮完成后的節點壓縮率均值為39%。這4種算法都是節點壓縮的算法，但是OBSQ 算法和ASSG 算法僅通過圖的結構特征進行劃分壓縮，GPC 算法通過消除節點的方式極大降低了節點壓縮率，卻使圖結構變得粗糙。而CER 考慮了邊標簽信息以及節點之間的屬性值，同時保留了圖結構。針對同一個類型的實體可以全部吸收兼并，極大減少了重復的邊標簽，比如針對屬性值均為植物類節點所在的同一邊標簽均可進行壓縮，實現壓縮效率最大化。

Fig.5 Node compression ratio圖5 節點壓縮率之比

從圖6 可以看出，CER 算法的邊壓縮率比OBSQ 算法和ASSG 算法及GPC 算法低，節點壓縮率的均值為45%。可以看出，邊的壓縮效率不如節點的壓縮效率，這是因為OBSQ 算法和ASSG 算法都是考慮節點和前驅后繼節點之間的關系以壓縮邊，而不考慮邊標簽信息。GPC 算法是消除節點和邊以達到壓縮目的，類似剪枝，邊壓縮率相對前兩者有所提高，但是并沒有考慮壓縮過后的圖結構；而CER 算法更大程度地考慮了圖結構，并非只要邊標簽相同就進行壓縮，提高了壓縮精度。綜上，從節點壓縮率和邊壓縮率而言，CER 壓縮效率優于其他3種算法。

Fig.6 Edge compression ratio圖6 邊壓縮率之比

表6 展示了在3 種數據集上度為1 的實體數量。度為1 的節點不一定都會被壓縮，因此節點壓縮率之比大于等于度不為1 的頂點數占比。表6 驗證了圖5 的節點壓縮率之比的合理性。

Table 6 Number of entities with degree 1表6 度為1的實體數量

從表7 的壓縮時間看，本文CER 算法的壓縮時間小于OBSQ 算法和ASSG 算法，略接近于GPC 算法。OBSQ 算法由于在遍歷圖譜時需計算各節點間的語義相似度，還要劃分到給定閾值，因而計算所需的時間遠大于壓縮時間；ASSG 算法由于需要計算rank 值，計算也耗時過長。GPC算法和CER 算法需遍歷整個圖并直接進行壓縮，壓縮不深入，相比其他兩種算法，這兩種算法壓縮時間較少。GPC算法從節點和邊同時入手，而CER 算法從先找出相同屬性值的邊標簽集合入手，所需時間與GPC 算法基本持平。

Table 7 Compression time（1 000×s）表7 壓縮時間（1 000×s）

表8 描述了PLL 算法在原圖和壓縮圖上針對100 000節點對的隨機查詢時間。在壓縮圖上的隨機查詢時間均小于在原圖上的查詢時間。這是因為CER 算法在原圖基礎上進行壓縮之后邊標簽的壓縮極大減小了原圖規模，節點合并縮短了構建出入標簽的時間，即構建索引的時間減少，從而使得查詢時間也隨之減少，在一定程度上提高了查詢效率，降低了查詢難度。

Table 8 Random query time（ms）表8 隨機查詢時間（ms）

圖7 展示了基于4 種壓縮算法的隨機查詢時間之比。其中，CER 算法的隨機查詢時間相對較快，這是因為GPC算法和CER 算法的節點壓縮率和邊壓縮率高于其他兩種壓縮算法，而GPC 壓縮算法是將消除的點和邊均保留在實體節點中，從而在構建PLL 出入標簽時由于索引空間過大而導致查詢時間也相應增加。

Fig.7 Random query time ratio圖7 隨機查詢時間之比

4 結語

本文提出了面向知識圖譜的等價關系壓縮算法CER，通過該壓縮算法上的PLL 查詢算法檢驗壓縮后的查詢效果。實驗結果表明，相對于其他壓縮算法，該算法在邊壓縮效率和查詢時間上有較大提升，且適用于大規模的知識圖譜。這種方法保證了原圖譜的結構和語義信息，也從一定程度上減少了原始圖譜的空間規模。該方法考慮的是邊標簽方向的壓縮，節點壓縮方向也是后續可以研究的問題。該方法只針對度為1 的節點的壓縮，在未來工作中可嘗試在此基礎上進行再次壓縮；或者不僅僅局限于度為1的節點，而是對其他節點壓縮方法也進行更為深入的研究。