有向圖上k步可達查詢處理

杜明 林鏗 周軍鋒

摘 要：給定一個有向圖，一個k步可達查詢u→？kv用來回答在該圖中是否存在一條從頂點u到頂點v且長度不大于k的有向路徑。k步可達查詢是一種基本的圖操作并在過去十年間被廣泛地研究。已有的k步可達查詢算法仍存在許多弊端，例如不可達查詢效率低，索引規模大和索引構建時間長等。本文針對上述問題提出了2種優化方法，分別是基于互逆拓撲序號以及基于等價頂點的圖壓縮方法.前者提高了不可達查詢的效率，后者減少了索引規模和索引構建時間。實驗結果表明，本文提出的方法可以有效地處理k步可達查詢，并支持大規模數據的處理。

關鍵詞： 有向圖;k步可達查詢;圖壓縮

文章編號： 2095-2163（2021）01-0008-07?中圖分類號：TP301.6?文獻標志碼：A

【Abstract】Given a directed graph， a k-hop reachability query u→？kv is used to answer whether there is a directed path from vertex u to vertex v and the length of the path is not greater than k. The k-hop reachability query is a basic graph operation and has been extensively studied in the past years. Existing algorithms still have many drawbacks， such as being inefficient for unreachability queries， large index size and long index construction time. This paper proposes two optimization approaches to make improvements， i.e.， the mutual reversed topological order and the graph compression based on equivalent vertices. The former improves the efficiency of unreachability queries， and the latter reduces the index size and index construction time. The experimental results show that the proposed method can effectively improve the performance of k-hop reachability queries processing and support large-scale graph processing.

【Key words】directed graph; k-hop reachability query; graph compression

0?引?言

隨著互聯網的快速發展，各種數據的規模日益龐大。圖是一種常見的數據表示模型，其中每個實體被簡單地抽象成圖中的一個頂點，實體間的關系被抽象成2個頂點之間的一條邊。圖被廣泛地應用于各類領域，如社交網絡、通信網絡、交通網絡等等[1-3]。在圖模型上的一個基本操作是回答2個頂點之間的可達性查詢，即判斷在圖中是否存在一條從源頂點u出發到目標頂點v結束的一條有向路徑。可達性查詢在過去被廣泛地研究[4-8]，然而在實際應用中，可達性查詢僅能回答2個實體之間是否存在某種關系，而無法回答這種關系的強弱程度。

另一種更有價值的操作是回答2個頂點之間的k步可達查詢[9-10]，即判斷在圖中是否存在一條從源頂點u出發到目標頂點v結束的一條有向路徑，并且滿足該路徑的長度不超過k。k步可達查詢相較于可達性查詢能提供更多關于2個頂點之間的信息，本質上，可達性查詢是一種特殊的k步可達查詢，即當k取∞時。k步可達查詢在現實生活中有很多實際的應用。比如在交通網絡中，經常需要回答在2個地點之間是否存在一條路程不超過某個閾值的路線。又比如在社交網絡中，通過2個實體之間的距離來判斷這2個實體產生關聯的可能性。

現有k步可達查詢算法大多只能運行在有向無環圖上，而有向圖上的k步可達查詢的相關研究卻寥寥無幾。在有向圖上回答k步可達查詢的基本方法是BFS[11]或者DFS [12]。基于遍歷的方法因為不具備良好的擴展性，因而查詢效率低下。另一個簡單的實現方法是將任意2個頂點之間的最短路徑信息預先通過鄰接矩陣的方式存儲起來，回答查詢時僅需要O（1）的時間內即可返回結果。但是這種方法需要的空間代價過大，無法應用于大規模數據圖。

針對上述算法存在的問題，文獻[9]提出了一種基于2-hop索引PLL。PLL的基本思想是通過為每個頂點預先建立一組出標簽和一組入標簽，這2組標簽分別保存了部分頂點與該頂點之間的最短路徑信息，這些部分頂點被稱為hop點。2個頂點之間的k步可達查詢問題可以被轉化為判斷兩點間最短路徑的長度是否小于等于k的問題。

PLL算法本身也存在低效性的問題。首先，如果一個查詢頂點對之間是不可達的，那么PLL算法需要遍歷源頂點的所有出標簽以及目標頂點的所有入標簽才能判斷出這對查詢頂點對是不可達的。其次，PLL算法在所有的頂點上構建索引，因此導致構建的索引的時間較長，同時構建的索引規模也較大。

針對PLL算法存在的以上2種問題，本文提出了2種針對性的優化方法。第一種是基于互逆拓撲序號來加快不可達查詢的效率，第二種是基于等價頂點的圖壓縮方法，通過去除圖中的冗余頂點和冗余邊，使得圖盡可能地小。實驗結果表明，本文提出的優化方法可以顯著改善索引的構建速度，索引規模更小。

1?相關工作

1.1?問題定義

給定一個有向圖G=（V，E），其中V={v1，v2，…，vn}是圖中頂點的集合，E={（u，v）|u，v∈V}是圖中邊的集合。當一條邊e=（u，v）∈E時，表示存在一條從頂點u指向頂點v的有向邊。對于每個頂點u，本文使用scc（u）來表示頂點u所在的強連通分量。同時使用outG（u）={v|（u，v）∈E}來表示頂點u的出鄰居集合以及使用inG（u）={v|（v，u）∈E}表示頂點u的入鄰居集合。用degout（u）=|outG（u）|表示頂點u的出度，degin（u）=|inG（u）|表示頂點u的入度。

在一個有向無環圖中，拓撲排序是將圖中頂點從偏序狀態轉化為全序狀態。一個頂點u的拓撲序號是頂點全序關系的序號，拓撲序號大的頂點與拓撲序號小的頂點之間不存在有向路徑。

如果2個頂點u，v滿足outG（u）=outG（v）并且inG（u）=inG（v），即頂點u和頂點v存在相同的出鄰居集合以及相同的入鄰居集合，則稱這2個頂點互為等價頂點。直觀上，2個頂點等價意味著二者可達相同的頂點集合，且可達二者的頂點集合也相同。

問題定義?給定一個有向圖G和一個k步可達查詢u→？kv，如果在G中存在一條從u出發到v的有向路徑，并且該路徑的長度不超過k，則返回TRUE，否則返回FALSE。

1.2?相關算法

1.2.1?PLL算法

PLL（Pruned Landmark Labeling）算法的基本思想是為圖中的每一個頂點u預先構建2組標簽Lout（u）={（h1，d1），…，（hi，di）}和Lin（u）={（h1，d1），…，（hj，dj）}。其中，Lout（u）保存了從頂點u可以到達的部分頂點以及頂點u到這些頂點之間的距離，類似地，Lin（u）保存了從部分可以到達頂點u的頂點以及這些頂點到頂點u之間的距離。每個頂點標簽中的每一對元素（h，d）表示hop點h以及h和該頂點之間的最短距離d。

PLL算法將2個查詢頂點對之間的k步可達查詢轉化為了判斷源頂點u和目標頂點v的最短距離是否小于等于k的問題。由于標簽中的hop點序號是以升序排列的，因此判斷2個標簽中是否存在一個公共的hop點的時間復雜度為O（n+m），其中n，m分別表示出標簽和入標簽中元素的個數。

PLL算法使用剪枝策略保證了建立的索引中盡可能地減少冗余的最短路徑信息。具體的做法是在對每一個hop點進行BFS遍歷的過程中，如果已經建立的2-hop索引能夠回答該hop點到當前遍歷的頂點之間的最短路徑信息，則PLL算法不會將該hop點加入到當前遍歷的頂點的2-hop標簽中，同時不再從當前遍歷的頂點執行BFS遍歷。

1.2.2?K-Reach算法

K-Reach算法[9，13]的基本思想是首先求解有向圖G的最小頂點覆蓋集C，然后在求解得到的C上建立傳遞閉包，這個傳遞閉包只包含了C中各個頂點之間的可達信息。

當回答一個k步可達查詢u→？kv時，根據查詢頂點對u，v是否屬于C分為如下3種情況：

（1）頂點u和頂點v都屬于最小頂點覆蓋集，此時可以直接通過建立的傳遞閉包來回答查詢。

（2）頂點u和頂點v中只有一個屬于C，在這種情況下需要通過遍歷那個非最小頂點覆蓋集頂點的出鄰居集合的傳遞閉包或者入鄰居集合的傳遞閉包來回答查詢。

（3）頂點u和頂點v中都不屬于C，這是最壞的情況，需要遍歷頂點u的出鄰居集合的傳遞閉包以及v的入鄰居集合的傳遞閉包來回答查詢。

K-Reach算法存在如下問題：首先該算法構建的傳遞閉包索引只能用于回答k等于特定值的k步可達查詢。其次，當查詢頂點對不屬于最小頂點覆蓋集時，需要遍歷查詢頂點對的所有鄰居頂點的傳遞閉包。最后，隨著k值的增大，每個頂點的傳遞閉包數量將呈指數上升，因此該算法將無法有效地擴展到大圖上。

2?優化方法

2.1?基于互逆拓撲序號的查詢優化方法

在有向無環圖中，一個頂點的拓撲序號是該頂點在拓撲排序中被處理的順序。如果一個頂點的拓撲序號大于另一個頂點的拓撲序號，則前者必然不可達后者，反之不成立。因此，在一個有向無環圖中，可以通過判斷2個頂點的拓撲序號大小來快速地回答2個頂點間的不可達情況。

但是在有向圖中，由于可能存在強連通分量，而拓撲排序必須在無環圖中才能進行，因此必須對有向圖進行一定的變換。在本文中采取的解決方案是將每一個強連通分量（SCC）壓縮成一個超級頂點，從而將有向圖轉換成有向無環圖。Tarjan算法是用來求解強連通分量的經典算法，該算法可以在線性時間內求解出每個頂點所屬的強連通分量。對于屬于同一個強連通分量中的頂點，將為其賦予相同的拓撲序號。

在拓撲排序中，對于一個頂點來說，不同的處理順序可以生成不同的拓撲序號，一個直觀的想法就是為每個頂點設置多個拓撲序號從而過濾掉等多的不可達查詢。然而，每個拓撲序號都需要一個整型的存儲空間，過多的拓撲序號會導致索引規模增長。因此，本文提出構建互逆的拓撲序號來達到最佳的查詢效率以及較小的空間開銷。

互逆拓撲序號的大致思想是為每個頂點建立2個拓撲序號。如果建立頂點u的第一個拓撲序號要先于建立頂點v的第一個拓撲序號，則在建立第二個拓撲序號時，要優先處理頂點v的拓撲序號。這種機制保證了每個頂點的2個拓撲序號構成的區間盡可能地大，從而可以判斷等多的不可達情況。至此，研究可得算法1、算法2的代碼設計詳見如下。

算法1?genTopo（G=（V，E））

輸入：G=（V，E）

輸出：所有頂點的互逆拓撲序號

1?G' ← tarjan（G）

2?construct（G'，X）

3?construct（G'，Y）

4?return （X，Y）

算法2?construct（G=（V，E），T）

1?將入度為0的頂點按照特定的順序入棧S

2?topNum ← 0

3?while S≠ do

4?u ← pop（S）

5?Tu ← topNum

6?topNum ← topNum + 1

7?for each v ∈outG（u） do

8?degin（v） ← degin（v）-1

9?if degin（v） = 0 do

10?push（S，v）

算法1展示了在一個有向圖上求解互逆拓撲序號的過程。算法的輸入是G，輸出是G上所有頂點的互逆拓撲序號。第1行首先調用Tarjan算法將G中的強連通分量壓縮成超級頂點。第2～3行分別調用construct方法建立拓撲序號。

在算法2的construct方法中，第1行將入度為0的頂點按照特定的順序入棧S，第2行設置一個計數器topNum，用來記錄每個頂點的處理順序。第3行當棧S不為空時，執行第4～10行的操作。第4行先彈出棧首頂點v，并在第5行將頂點v的拓撲序號設置為topNum，同時第6行更新topNum。第7～10行按照特定的順序處理頂點v的所有出鄰居，將其入度均做減一處理，如果減后的入度為0，則將該出鄰居頂點入棧。

對于在同一個強連通分量中的每個頂點，各頂點的互逆拓撲序號都等于相應頂點所在的超級頂點的互逆拓撲序號。Tarjan算法和construct方法的時間復雜度都為O（m）， 其中m為有向圖G的邊數，因此整個genTopo方法的時間復雜度為O（m）。

2.2?基于等價頂點的圖壓縮方法

在1.1節中給出了等價頂點的相關定義。對于任意2個相互等價的頂點u、v，在回答可達性查詢時（除查詢頂點對為（u，v）這種特殊情況，稍后討論）可以相互替換。例如當回答從頂點u到頂點w（其中w≠v）的k步可達查詢時，可以替換成從頂點v到頂點w的k步可達查詢。

根據該特性，可以實現基于等價頂點的圖壓縮算法。具體的做法是對于互為等價頂點的一組頂點，只保留其中的一個頂點，同時刪除與該頂點等價的其他頂點。當需要回答涉及被刪除頂點的k步可達查詢信息時，可以通過與查詢頂點等價的那個保留頂點來判斷可達性。在對圖建立2-hop索引之前，通過先對圖進行基于等價頂點的圖壓縮，能有效減小圖的規模，從而降低構建索引的時間和索引大小。

本文采用文獻[14]中提出的基于分治思想的求解等價頂點方法。該方法的基本思路是首先將頂點集V中的所有頂點視為可能相互等價的，再將集合V分成2個集合，這2個集合中的頂點可能互相等價，但不同集合中的頂點不可能等價。接下來繼續對2個集合進行類似的分割，直到每個集合都無法再繼續分割下去。最后每個集合中存儲的頂點都是相互等價的，而集合之間的頂點是不可能等價的，該算法的時間復雜度是O（m），其中m是圖中邊的個數。

對于2個等價頂點u、v，當查詢頂點對為（u，v）時，根據頂點u和頂點v是否位于同一個強連通分量中，會存在2種不同的情況，具體如圖1所示。在圖1（a）中，即頂點u和頂點v不在同一個SCC并且頂點u和頂點v互為等價頂點，此時頂點u必然不可達頂點v、并且頂點v也不可達頂點u，因此查詢結果返回FALSE。在圖1（b）中，頂點u和頂點v位于同一個SCC、并且頂點u和頂點v互為等價頂點，則u和v可能是k步可達的（取決于k值是否大于或等于這2個頂點之間的最短路徑長度），此時可能就需要通過遍歷或者額外的索引來處理這種特殊情況。為了處理這種不常見但又確實存在的查詢，導致每一次回答查詢時都要進行額外的判斷，這顯然是十分繁瑣又低效的操作。

為了解決該問題，本文提出了一種新的策略，對于不在同一個SCC中的等價頂點，將對其進行壓縮操作。而對于處于同一個SCC中的等價頂點，則將其視為不等價的，因此無需進行壓縮，等價頂點之間的k步可達查詢可以直接通過建立的2-hop標簽回答。該策略能有效地避免在這種特殊條件下的冗長而低效的條件分支判斷以及遍歷圖的操作。

2.3?查詢方法

算法3給出了在2種優化方法下的PLL算法的查詢方法，設計代碼依次展開如下。

算法3?query（u，v，k）

輸入：源頂點u，目標頂點v，查詢距離k

輸出：TRUE/FALSE

1?if Xu > Xv or Yu > Yv

2?return FALSE

3?ue ← Eu， ve ← Ev

4?if ue = ve

5?return FALSE

6?ui ← 0， vi ← 0

7?while ui < Lout（ue）.size and vi < Lin（ve）.size

8?hu = Lout（ue）[ui].hop， hv = Lin（ve）[vi].hop

9?du = Lout（ue）[ui].dist， dv = Lin（ve）[vi].dist

10?if hu = hv do

11?if du +?dv <= k do

12?return TRUE

13?else

14?ui ← ui + 1， vi ← vi + 1

15?else if hu < hv do

16?ui ← ui + 1

17?else

18?vi ← vi + 1

19?return FLASE

算法3中，第1行先判斷頂點u的拓撲序號X是否大于頂點v的拓撲序號X以及頂點u的拓撲序號Y是否大于頂點v的拓撲序號Y。如果任意一個條件成立，表明頂點u不可達頂點v，因此第2行直接返回FALSE。第3行將頂點u和頂點v轉換成對應的等價頂點ue和ve。數組E保存了每個頂點與其對應的等價頂點的關系，該數組由2.2節中所描述的方法求出。第4行如果轉換后的等價頂點相等，則查詢結果返回FALSE。否則第6～19行通過PLL算法構建的2-hop標簽來回答查詢。

3?實驗分析

3.1?實驗環境

本文實驗中所使用的硬件平臺為Intel（R）Core（TM） i5-4200M @ 2.5GHz CPU，16G雙通道內存，操作系統為Ubuntu 18.04.3 LTS。本次實驗算法采用C++語言實現，并且查詢距離k均取值為10。實驗首先比較了PLL算法和PLL算法在分別使用2種優化算法的情況下的索引構造時間、索引大小以及查詢時間。隨后比較了PLL算法與同時使用2種優化算法的索引構造時間、索引大小以及查詢時間。

3.2?數據集

本次研究中所使用的10個數據集見表1。這10個數據集都來自斯坦福大型網絡數據集（snap.stanford.edu/data/）。這些圖數據集都是有向有環圖，表1中標注了每個數據集的頂點數V以及邊數E。本文將頂點數大于100000的數據集稱為大數據集，因此本次實驗中共有5個大數據集以及5個小數據集。本次實驗使用的查詢集大小為1000000，其中可達頂點對和不可達頂點對的比例為1：1。

3.3?性能比較分析

3.3.1?2種優化技術的比較

PLL算法和PLL算法在分別使用了2種優化方法之后的索引大小見表2。從表2中可以看到，互逆拓撲序號所需的存儲空間最多，因為需要額外的2個整型值來存儲拓撲序號（即PLL+Topo）。其次是PLL算法，最優的是使用了基于等價頂點壓縮的PLL算法（即PLL+GC），因為僅在部分點上建立2-hop索引，從而具有最小的索引大小。

PLL算法和PLL算法在分別使用了2種優化方法之后的索引構造時間見表3。從表3中可以得到與在索引大小中類似的結論，由于需要額外計算2個互逆拓撲序號，因此PLL+Topo的時間開銷最多，但由于求解拓撲序號是線性時間復雜度，因此差距并不明顯。其次，雖然PLL+GC方法花費了線性時間來計算等價頂點，但是由于進行了圖壓縮，因此整個索引構造時間相較于PLL算法減少了。

PLL算法和PLL算法在分別使用了2種優化方法之后的查詢時間見表4。其中，查詢距離k取10。從表4中可以看出在應用了互逆拓撲序號后的查詢效率有了明顯的提升，在一些數據集上有2～3倍左右的提升。PLL算法在回答不可達查詢時的時間消耗要大于回答可達的查詢頂點對所花費的時間，而互逆拓撲序號能在O（1）的時間內回答絕大部分的不可達查詢，因此提高了查詢的效率。對于PLL+GC方法來說，由于進行了圖壓縮，因此建立的索引大小更小，從而使得查詢時需要遍歷的hop頂點數更少，因此也在一定程度上提高了查詢效率。

3.3.2?PLL算法與PLL-O方法的比較

PLL算法和PLL算法同時應用了2種優化方法（即PLL-O）之后的索引大小見表5。從表5中可以看出在絕大多數的數據集上，PLL-O方法的索引大小要優于PLL算法。只有在極個別圖上（如HepTh），圖壓縮方法對索引大小帶來的收益沒能抵消2個拓撲號帶來的空間開銷，此時PLL-O方法的索引規模會略大于PLL算法。

PLL算法和PLL算法同時應用了2種優化方法之后的索引構造時間見表6。由于綜合了圖壓縮方法的優點，PLL-O算法在整體上的性能都優于PLL算法。

PLL算法和PLL算法同時應用了2種優化方法之后的查詢時間見表7，其中查詢距離k取10。從表7中可以看出PLL-O方法相比于只應用了圖壓縮的方法的查詢效率要高，然而相對于僅應用互逆拓撲序號的方法來說性能差距不大。但綜合考慮索引大小以及索引構造時間后，PLL-O方法較PLL算法以及僅使用一種優化方法的PLL方法仍具有較大的優勢。

4?結束語

本文針對已有k步可達查詢算法存在的不可達查詢效率低，索引構造時間長，索引規模大等問題提出了2種優化的方法，分別是基于等價頂點的圖壓縮方法以及基于互逆拓撲序號的不可達查詢優化方法。實驗結果表明，在同時應用了這2種算法之后，PLL算法的查詢效率、索引大小以及索引構造時間都有了明顯的提升。

參考文獻

[1]Van HELDEN J， NAIM A， MANCUSO R， et al. Representing and analysing molecular and cellular function using the computer[J]. Biological chemistry， 2000， 381（9-10）： 921-935.

[2]STANN F， HEIDEMANN J. RMST： Reliable data transport in sensor networks[C]//Proceedings of the First IEEE International Workshop on Sensor Network Protocols and Applications. Anchorage，AK， USA：IEEE， 2003： 102-112.

[3]KUMAR R， TUZHILIN A， FALOUTSOS C， et al. Social networks： Looking ahead[C]//Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Las Vegas， USA：ACM， 2008： 1060.

[4]CHEN Yangjun， CHEN Yibin. An efficient algorithm for answering graph reachability queries[C]//2008 IEEE 24th International Conference on Data Engineering. Cancun，Mexico：IEEE， 2008： 893-902.

[5]YU J X， CHENG Jiefeng. Graph reachability queries： A survey[M]//Managing and Mining Graph Data. Boston， MA：Springer， 2010： 181-215.

[6]CHENG J， HUANG Silu， WU Huanhuan， et al. TF-Label： A topological-folding labeling scheme for reachability querying in a large graph[C]//Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data. New York：ACM， 2013： 193-204.

[7]WANG H， HE H， YANG J， et al. Dual labeling： Answering graph reachability queries in constant time[C]//22nd International Conference on Data Engineering （ICDE'06）. Atlanta， Georgia：IEEE， 2006： 75.

[8]WEI Hao， YU J X， LU C，et al. Reachability querying： An independent permutation labeling approach[J]. The VLDB Journal， 2018，27：1-26.

[9]YANO Y， AKIBA T， IWATA Y， et al. Fast and scalable reachability queries on graphs by pruned labeling with landmarks and paths[C]//Proceedings of the 22nd ACM International Conference on Information & Knowledge Management. San Francisco， CA，USA：ACM， 2013： 1601-1606.

[10]CHENG J， SHANG Zechao， CHENG Hong， et al. K-reach： Who is in your small world[J]. Proceedings of the VLDB Endowment， 2012， 5（11）： 1292-1303.

[11]BUNDY A， WALLEN L. Breadth-first search [M]// Catalogue of Artificial Intelligence Tools.Symbolic Computation （Artificial Intelligence）. Berlin /Heidelberg： Springer ， 1984：13.

[12]STEIER D M， ANDERSON A P. Depth-first search [M]// Algorithm synthesis： A Comparative Study. US：Springer， 1989：47-62.

[13]YANO Y， AKIBA T， IWATA Y， et al. Fast and scalable reachability queries on graphs by pruned labeling with landmarks and paths[C]//Proceedings of the 22nd ACM international conference on Information & Knowledge Management. San Francisco， CA，USA：ACM， 2013： 1601-1606.

[13]TANG Xian， CHEN Ziyang， LI Kai， et al. Efficient computation of the transitive closure size[J]. Cluster Computing，2019，22： 6517-6527.

[14]ZHOU Junfeng， ZHOU Shijie， YU J X， et al. DAG reduction： Fast answering reachability queries[C]//Proceedings of the 2017 ACM International Conference on Management of Data. Raleigh：ACM， 2017： 375-390.