Context-Free Path Querying (CFPQ) is an important problem with applications in many areas, for example, graph databases, bioinformatics, static analysis, etc. Historically, regular languages are used as constraints for navigational path queries. However, in some important cases, regular languages are not expressive enough and context-free languages are used instead. Many algorithms for CFPQ were proposed but recently showed that the state-of-the-art CFPQ algorithms are still not performant enough for practical use. One promising way to achieve high-performance solutions for graph querying problems is to reduce them to linear algebra operations (such as matrix multiplication). The active utilization of these operations in the process of context-free path query evaluation makes it possible to eficiently apply a wide class of optimizations and computing techniques, such as GPGPU (General-Purpose computing on Graphics Processing Units), parallel computation, sparse matrix representation, distributed-memory computation, etc. In this Ph.D. work, we aim at: (i) studying the applicability of linear algebra methods to the CFPQ problem, (ii) at devising the algorithms for context-free path query evaluation formulated in terms of linear algebra operations, and (iii) at achieving high-performance implementations of the devised algorithms using parallel computations.
Formal language-constrained path querying [
CFPQ has been studied a lot since the problem was first stated by
Mihalis Yannakakis in 1990 [
A number of CFPQ algorithms based on parsing techniques were
proposed: (G)LL and (G)LR-based algorithms by Ciro M. Medeiros
et al. [
Inspired by Valiant’s [
In this Ph.D. work, we make the following contributions. (1) We provide an approach to solving the CFPQ problem using linear algebra operations. The provided approach allows us to use a wide class of optimizations of linear algebra operations for eficient analysis of large graphs. (2) Using provided approach, we devise the CFPQ algorithms based on linear algebra operations for relational, singlepath, and all-path query semantics. (3) We provide the implementations of the devised algorithms for context-free path query evaluation using diferent optimizations and computing techniques. Our preliminary results demonstrate that our best CPU and GPU-based implementations that utilize sparse matrix representation and parallel computation outperform the state-of-the-art context-free path querying solutions.
In this section, we describe our approach to solving the CFPQ
problem using linear algebra operations. The idea of using a sparse
adjacency matrix as a graph representation in graph analysis problems
is well-known. Recently, became very popular the GraphBLAS [
An overview of our proposed approach is shown in Figure 1. The purpose of this approach is to solving CFPQ problem using linear algebra operations. In order to do this, it is necessary to devise the CFPQ algorithms that have the input in the form of a directed edgelabeled graph as a data, a context-free grammar as a query, and the query semantics that determines the type of requested information about paths in the graph. Further, the approach can be divided into the following stages.
Reducing the CFPQ problem to the linear algebra operations. The query is formulated by a context-free grammar which is a tuple ( , Σ, , ), where is a finite set of nonterminals; Σ is a finite set of terminals, ∩ Σ = ∅; is a finite set of productions of the form → , where ∈ , ∈ ( ∪ Σ)∗; and is the start nonterminal. To formulate the obtained problem in terms of linear algebra, the input graphs are considered in the form of adjacency matrices, and the input context-free grammar (CF-grammar) is encoded in the form of a certain algebraic structure, namely, in the form of a semiring with non-associative multiplication. This approach takes advantage of the fact that in the production rules of the CF-grammars there are two operations — concatenation and union, which are transformed into the product and the sum of a semiring. The elements of the adjacency matrices must be sets of nonterminals since each of them describe the set of words corresponding to the paths of interest. Further, the resulting semiring is used to define matrix multiplication (or other linear algebra operation), which simulates the step of the input graph traversing. For a complete traversal of the input graph, a transitive closure of adjacency matrices can be defined, which allows us to obtain the information about all paths corresponding to the query. The type of information retrieved depends on the query semantics, which must be taken into account when constructing the adjacency matrices and semirings.
Analysis. To analyze the theoretical properties of the constructed algorithm, the existing theoretical results of linear algebra, graph theory and the theory of formal languages can be used. The properties of the entire CFPQ algorithm largely depend on the properties of linear algebra operations since it evaluates the context-free path queries by ofloading the most intensive computations into calls to procedures for these operations. Therefore, the most efective for the algorithm will be optimizations that use the existing results of linear algebra to eficiently compute such operations, for example, sparse matrix and vector operations.
Implementation. From a practical point of view, the algorithms
built in this approach are easy to implement, since the most time
consuming is the implementation of the necessary linear algebra
operations, which have already been implemented in many
eficient libraries that support linear algebra operations. For example,
can be used the SuiteSparse:GraphBLAS [
Result interpretation. The final step is to interpret the query result. Depending on the query semantics, it is possible to extract certain information about the paths between the vertices of interest from the resulting matrix. In addition, in the case when the query semantics involves the enumeration of paths between certain vertices in the graph, it also becomes necessary to implement an algorithm for constructing these paths from the resulting matrices. 3
In this section, we briefly describe our devised CFPQ algorithms based on the linear algebra operations. For all our algorithms we formally prove the correctness, termination, and time complexity bounds. Our algorithms can be divided into two groups.
Matrix-based algorithms. The algorithms in the first group utilize the Boolean matrix multiplication for relational query semantics and operate with more complex matrices for single-path and allpath query semantics. Also, these algorithms, like many existing ones, require the CF-grammar transformation to some normal form that allows us to encode one step of the input graph traversing into exactly one matrix multiplication since in this form we have only two nonterminals in the right-hand side of productions rules.
We define a binary operation ( · ) for arbitrary subsets 1, 2 of with respect to a CF-grammar = ( , Σ, ) as 1 · 2 = { | ∃ ∈ 1, ∃ ∈ 2 such that ( → ) ∈ }.
Using this binary operation as subset multiplication, and union as an addition, we can define a matrix multiplication, × = , where and are matrices of a suitable size, that have subsets of as elements, as , = Ð=1 , ·, . Also, we use the element-wise union operation on matrices and with the same size: ∪ = , where , = , ∪ , . Finally, we define the transitive closure of a square matrix as + = +(1) ∪ +(2) ∪ · · ·, where +(1) = and +() = Ð−=11 +() × +(−) , ≥ 2.
We can evaluate the context-free path queries with relational
semantics by computing this transitive closure of an adjacency
matrix of input labeled graph with sets of nonterminals as elements
where ∈ , only if there is ∈ Σ such that there is edge from
vertex to labeled by and ( → ) ∈ . However, described
operations can be computed using several Boolean matrix
multiplications and additions if we encode the matrix by the | | Boolean
matrices (one Boolean matrix for each nonterminal how it is done
in the work of Valiant [
For single-path and all-path query semantics, we store additional information in matrices to be able to restore found paths. For singlepath query semantics, we store the intermediate vertex in the element , only if there is a path from to corresponding to the nonterminal , there is a path from to corresponding to the nonterminal , and there is a rule ( → ) ∈ . For all-path query semantics, we store the sets of the intermediate vertices, since we must store the information about all paths between each vertex pair. In that case, we cannot reduce computations to operations on Boolean matrices and we use custom matrix multiplication for matrices with more complex elements (tuples or arrays of integers). There are still libraries that support linear algebra operations for our algorithms for single-path and all-path query semantics, for example, the GraphBLAS implementations that support the creation of custom semirings for the matrix operations.
Kronecker product-based algorithm. On the contrary, the algorithm in the second group is based on the Kronecker product operation and does not require the transformation of the input grammar. The transformation leads to at least a quadratic blow-up in grammar size, thus by avoiding the transformation, this algorithm achieves better time complexity in terms of the grammar size. While regular languages can be expressed as a Finite-State Machine (FSM), a CF-grammar can be expressed as a Recursive State Machine (RSM) in a similar fashion. In these algorithms, we use RSM to represent the context-free path query and evaluate this query using the Kronecker product of the corresponding adjacency matrices of the input graph and the RSM for the input CF-grammar. Although the Kronecker-based algorithm for constructing the matrices with information about required paths (or so-called index) is the same for all three query semantics, the paths extraction algorithm for each semantics is diferent. 4
We evaluate implementations of devised algorithms on real-world
RDFs. We provide results only for our CPU and GPU-based
implementations of matrix-based algorithms for relational and
singlepath query semantics because of the page limit. We use
RedisGraph [
Mem (MB) Time (s)
Mem (MB) Time (s)
Mem (MB) Time (s)
Mem (MB)
The results of the CFPQ evaluation are presented in Table 1.
As we can see, our matrix-based algorithm for relational query
semantics implemented for RedisGraph is more than 1000 times
faster than the one based on annotated grammar implemented for
Neo4j [
We can conclude, that the cost of computing matrices for singlepath query semantics is not high. On average, it is about 2 times slower than for the relational query semantics. The additional running time of the path extraction is presented in Figure 2 (boxplots are standard, outliers are omitted). As we can see, this time is small and linear in the length of the path.
Finally, we conclude that the matrix-based algorithm paired with a suitable database and employing appropriate libraries for linear algebra operations is a promising way to make CFPQ with diferent query semantics applicable for real-world data analysis. 5
In this Ph.D. work, we provide an approach to solving the CFPQ problem using linear algebra operations. Using provided approach we devise the CFPQ algorithms for all three query semantics and implement them using appropriate libraries for linear algebra operations. Preliminary results show that our CPU and GPU-based implementations that utilize sparse matrix representation and parallel computation outperform the state-of-the-art solutions.
As a next step, we plan to provide a full comparison of our linear
algebra-based implementations with all state-of-the-art solutions
for CFPQ on the same benchmark and experimental setup.
Moreover, our implementations are prototypes and we plan to provide
full integration of CFPQ to RedisGraph. Also, we plan to improve
the dataset by including more real-world cases with larger graphs,
for example, from the area of static code analysis [
This work was funded by RFBR, project number 19-37-90101, and grant from JetBrains Research.