Modular Decomposition-Based Graph Compression for Fast Reachability Detection

The index-based algorithms create labels for the vertices, and such labels contain the reachability information. These algorithms can be divided into Label-only and Label+G methods [19]. The label-only [1, 3, 4, 8, 10‐13, 20] methods use the labels of source and destination vertices only to answer reachability. Agrawal [1] proposed tree cover approach that creates an optimal spanning tree to create index. Here, an interval for each vertex is created. A reachability query is answered as true if the interval of target is contained in the interval of source vertex. The index construction time and index size both are high in this approach. A chain cover approach is first proposed in [8] where the entire graph is divided into a number of pairwise disjoint chains to create the index. The label of each vertex contains a minimal successor list containing their chain number and position in the chain. A vertex u will be reachable to v if label of u contains a pair (k, j) and v has an index pair (i, j) such that \(i \ge k\). This chain cover approach is later improved in [3]. Path tree [10] uses the similar concept of chain cover that uses paths to create index and has smaller index size than chain cover. The recent approaches DL [11], PLL [20] and TF [4] use the concept of two-hop labeling proposed in [6]. In two-hop labeling, a label is created for each vertex containing the subset of vertices that it can reach (\(L_\mathrm{out}\)) as well as the subset of vertices that can reach it (\(L_\mathrm{in}\)). Vertex u can reach vertex v if \(L_\mathrm{out}(u) \cap L_\mathrm{in}(v) \ne \emptyset \). [12] uses the concept of chain cover to improve two-hop and proposes a three-hop labeling that creates a transitive closure contour (Con(G)) of graph G using chain decomposition, and then applies two-hop techniques. Path-hop [2] improves three-hop by replacing the chain decomposition with a spanning tree. TF [4] proposes a topological folding approach for two-hop labeling that can significantly reduce the index size as well as the query time.

The Label+G approaches include [15‐19, 21] which require online searching of data graph G if the query cannot be answered from labels. Triβl and Leser [17] uses interval labeling over a spanning tree and performs DFS online if needed. Grail [21] and Ferrari [15] use multiple interval instead of single interval label for each vertex over the spanning tree. Feline [18] creates coordinates \(i(u) = (X_u, Y_u)\) for a vertex u and answers reachability from u to v as true if the area of i(v) is contained in that of i(u). Feline also uses interval labeling over spanning tree and compares topological levels of u and v as additional pruning strategy to reduce DFS search. \(\hbox {IP}\) [19] uses independent permutation numbering to label each vertex. Feline and \(\hbox {IP}\) show significant improvement on query time and require less index construction time and smaller index size. BFL [16] proposes a bloom-filter labeling to further improve the performance of \(\hbox {IP}\).

Graph compression-based works include scarab [9], equivalence reduction [7] and DAG reduction [22]. Scarab [9] compresses the original graph by creating a reachability backbone that carries the major reachability information. To find reachability from vertex u to vertex v, the algorithm needs access to a list of local outgoing backbone vertices of u and local incoming backbone vertices of v. The algorithm then performs a forward BFS for u and backward BFS for v on the original graph to answer reachability from u to v. If the answer is false, then it checks whether any outgoing backbone vertex of u can reach any incoming backbone vertex of v in the reachability backbone; if yes, then u can reach v. Scarab requires large index size with high time complexity. Equivalence reduction [7] reduces the graph by merging equivalent vertices into a single vertex. Two vertices are equivalent if they have the same ancestors and same descendants. The algorithm requires high equivalence class construction time. DAG reduction [22] improves the construction time of equivalence classes by doing a transitive reduction in graph first.

Our work is different from the previous works; in that, we not only consider equivalent classes, but also linear chains, when compressing the graph, and to the best of our knowledge, none of the previous works uses multilevel compression and modular decomposition tree in reachability queries.

Suppose (u, v) is an edge in G. If there is a path of length greater than 1 from u to v, then (u, v) is redundant for reachability queries, that is, removing (u, v) from G will not affect the answer to any reachability queries.

The redundant edges can be efficiently identified and removed by a transitive reduction algorithm proposed in [22]. The following lemma is shown in [22]:

Two vertices u and v are said to be equivalent if they have the same ancestors and the same descendants, that is, \(anc(u) = anc(v)\), \(des(u) = des(v)\) [7]. Because of Lemma 1, if G does not have redundant edges, then u and v are equivalent if and only if they have the same parents and same children. The equivalent vertices form an equivalence class. It is easy to see that all vertices in the same equivalence class have the same reachability properties, that is, if u is in an equivalence class, then for any other vertex \(u'\), u can reach \(u'\) (resp. u is reachable from \(u'\)) if and only if every vertex v in the same equivalence class can reach \(u'\) (resp. is reachable from \(u'\)).

Also as observed in [22], if G has no redundant edges, then all vertices in an equivalence class form an independent set, that is, there are no edges between the vertices in the same equivalence class.

The modular decomposition [14] of a directed graph G partitions the vertex set into a hierarchy of modules, where a module is conventionally defined as follows.

It is easy to see that a singleton set is a module and the set of all vertices in G is also a module. These modules are called trivial modules. Let G be a DAG that has no redundant edges. By Lemma 1, an equivalent class is also a module, and by Lemma 2, such a module is an independent set. In the literature, modules that are independent sets are referred to as parallel modules.

To utilize parallel and linear modules in reachability search, we perform a multilevel compression of the original graph G. First, we identify the maximal linear modules and parallel modules, and merge the vertices in each module into a single super vertex. We add an edge from super vertex \(s_1\) to super vertex \(s_2\) if and only if there exists \(u\in s_1\), and \(v\in s_2\) such that (u, v) is an edge in G. In this way, we obtain the first-level compressed graph \(G_1 = Compress(G)\). Clearly, \(G_1\) is also a DAG without redundant edges. Then, we apply the same compression process to \(G_1\) to obtain the next-level compressed graph \(G_2=Compress(G_1)\), and this process is repeated until we obtain a graph \(G_c\) which can no longer be compressed, i.e., \(G_c\) does not have singleton set parallel or linear modules.

We organize the modules in all levels of the compressed graphs into a tree structure, called the modular decomposition tree, or decomposition tree for brevity, as follows: The root of the tree is the final compressed graph \(G_c\). Each module in the previous-level compressed graph \(G_{c-1}\) is a child node of the root; Each child node of the root that corresponds to a non-trivial module of \(G_{c-1}\), in turn, has its own children, representing modules in the previous-level graph \(G_{c-2}\). This continues until we reach the nodes representing modules in the first-level compressed graph, where each non-trivial module points to their children, which are individual vertices in the original graph G. Note that the leaf nodes of the tree are individual vertices in the original graph G. Also, to help reachability detection, we keep a record of the vertex positions in the chain of each linear module in a compressed graph \(G_i\), where if the starting vertex has position 1, the next vertex will have position 2 and so on. We will use pos(v, LS) to denote the position of node v in the chain of LS. Obviously, for \(u,v\in LS\), \(u\rightsquigarrow _{G_i} v\) if and only if \(pos(u,LS) < pos(v, LS)\).

Figure 5 shows the modular decomposition tree, T, of graph \({\tilde{G}}\) in Fig. 3b. Let M be a non-leaf node in the decomposition tree of G. By definition, M is either a parallel or linear module in some compressed graph \(G_i\)\((i<c)\), or it is the final compressed graph \(G_c\). M can be regarded as a set of the original vertices of G in the obvious way. Put in another way, we say vertex \(v\in G\) belongs to (or is in) M if v is a descendant of M in the decomposition tree. For example, the vertices 2, 3, 4, 5, 6, 7, 8 belong to the module IS1 in Fig. 5.

We have the following observations about modules in the decomposition tree:

The above lemma can be easily proved by induction on the compression level i. Using Lemma 5, we can easily see:

Suppose we have the decomposition tree T of G. For ease of presentation, let us use \(G_0\) to denote the graph G. For any pair of vertices u, v in the original graph G, we use LCA(u, v) to denote the lowest common ancestor of u and v in T. Note that LCA(u, v) corresponds either to a module in some compressed graph \(G_i\)\((i\in [1, c-1])\), or to the final compressed graph \(G_c\) (i.e., the root of T). We have the following result.

With the above discussion, we are ready to present the method for answering reachability queries using the decomposition tree and the final compressed graph \(G_c\). Given two vertices \(u,v\in V_G\), to find whether \(u \rightsquigarrow _G v\), we can find the lowest common ancestor LCA(u, v) of u and v, and check the following:

Algorithm 1 shows the process of creating the modular decomposition tree along with the final compressed graph. The algorithm takes a DAG that has no redundant edges G as input and returns the modular decomposition tree and the final compressed graph. The algorithm first creates a tree with a root node r. Starting with a random vertex v, the algorithm first tries to find all other vertices that can form a linear module with v (Line 7). If no such module is found, then it will search for a maximal parallel module for v (Line 14). If such a module cannot be found, then v will be added as a child of r (Line 21), otherwise the found module M will be added as child of r, and each vertex in the module will be added as a child of M (Lines 8–12, 16–19). We record all such modules in S (Lines 9,16), and use them to compress the graph into a new graph (Line 24). Then, we recursively call the algorithm to compress the new graph (Line 27). If no non-single-vertex module is found in the current graph, the current tree T will be returned, and the current graph will be returned as \(G_c\).

The functions FindParallelModule() and FindLinearModule() used in Algorithm 1 are shown in Algorithm 2 and Algorithms 3, respectively. These algorithms try to find a relevant module based on Lemma 3.

Algorithm 2 takes a vertex v and DAG G as input, and it finds the set of vertices, M, that share the same parents and same children with v. To do that, it first finds the set of vertices, \(M_1\) that share the same parents with v, and then finds the set of vertices, \(M_2\) that share the same children with v. Then, M is the intersection of \(M_1\) and \(M_2\).

Algorithms 3 takes a vertex v and DAG G as input, and it first searches for a possible chain of ancestors of v (lines 2–12), and then searches for a chain of descendants of v (lines 13–26). Both parts are via an iterative process. Specifically, lines 2 and 4 check whether v has a sole parent \(v'\), and \(v'\) has a sole child v, if so \(v'\) is the parent of v in a linear module. After that, lines 7–12 try to find a parent of the first vertex in the chain, one by one. In the process, it also provides a position number for each vertex found (line 10). Note that the position does not have to be a positive number, as long as it can provide an appropriate order of the vertices in the chain, it will be fine. Lines 13–26 work similarly.

As discussed in the previous subsection, to answer reachability query \(? u\rightsquigarrow _G v\) using the decomposition tree, we only need to find LCA(u, v) and then take appropriate actions depending on the type of LCA(u, v). To save time for finding the LCA and storage space, we design a slightly modified algorithms as shown in Algorithm 4. Given vertices u and v, we first find the children of the root that u and v belong to, respectively; let us suppose \(u\in N_1\), \(v\in N_2\), if they are different (this is equivalent to say LCA(u, v) is the root), we will use some existing algorithm to check \(? N_1\rightsquigarrow _{G_c} N_2\). Otherwise we will find the lowest linear LCA of u, v (note that to do so we only need to record the linear module ancestors of the vertices), if no such LCA exists, then u cannot reach v. Otherwise, suppose the linear LCA is M, we will check the relative positions of u and v in M to determine whether u can reach v. Here, the position of u is defined to be same as the position of the child of M that contains u. If LCA(u, v) is a parallel module, then that module will be a child of M. So, u and v will have the same position in M thus u cannot reach v. It is easy to see that the algorithm is equivalent to the process described in Sect. 4; hence, its correctness is guaranteed.

We generated eight random graphs where the smallest graph have one thousand vertices with two thousands edges, and the largest graph have ten millions vertices with 15 millions edges. The other graphs have number of vertices and edges in between these two graphs.

Table 8 shows the graph profiles and their compression ratio for DAG reduction and multilevel compression. The table also shows the time required for compression of each of the graphs using multilevel compression. Multilevel compression can process the largest graph with ten millions vertices and 15 millions edges within few hours which ensures the scalability of this method.