Optimization for Inference-Based Graph Databases

Abstract

Knowledge Graphs are commonly characterized by two challenges: massive scale and sparsity. The former leads to slow response times for complex queries with random data accesses, especially when they require deep graph traversals. The latter, which is caused by missing connections and characteristics in graphs modeling real information, implies that any analysis based solely on explicitly stored data is bound to yield incomplete results. This work aims to develop a novel graph database architecture that leverages the power of Graph Machine Learning to equip graph queries with prediction capabilities while ofering approximate but timely results to complex queries. We discuss challenges, design decisions, and research avenues required in materializing this prototype alongside the outline of the actively-pursued research plan.

Keywords

• of incomplete data
• where observations might enclose

1. Introduction

For years, the data management community has been investigating systems that can store, process, query, and anmaking or accelerate discoveries. One of the prevalent challenges refers to query complexity. Due to the requirement for random accesses, above-linear algorithms are dificult to execute, especially on natural graphs, which tions [ 1 ]. However, the need for fast complex computations is evident in the industry [ 2, 3 ]. Yet, answering complex queries requiring deep traversals of heterogeneous data or employing computationally expensive algorithms lacks support in common data management tools [ 4, 2 ].

As current systems attempt to address issues like distribution skew or evolution, most architectures neglect one of the major dificulties of KGs: data incompleteness.

Interconnected data modeling natural domains are often missing connections and properties [ 1 ]. Modern graph cessing systems, or graph streaming frameworks can only consult or compute properties of data that is explicitly stored but are usually unable to draw any conclusion that is not explicitly stated [ 5, 4 ]. Furthermore, systems that natively support reasoning capabilities, such as RDF stores, usually ofer deductive inference based on existing data and rely heavily on ontology definitions, which can grow complex and resource-intensive to maintain,

Such systems cannot be used to harness the potential

especially for massive, intricate dynamic graph datasets. in learned latent spaces. VLDB 2023 PhD Workshop, co-located with the 49th International

2. Research Goal

the system can decide to execute the first hop using an ML operator backed, for instance, by Query2Box, while The proposed architecture moves query computation choosing to traverse the explicitly stored data for the secfrom raw data accesses and expensive pointer-chasing for ond hop. Therefore, a novel query optimization process traversals to querying learned latent spaces. Specifically, is paramount to bringing this vision to fruition. we leverage the power of graph representation learn- Lastly, we highlight the potential prospect of the proing to approximate complex graph queries by using la- posed design for graph processing on GPUs. ML opertent representations (i.e., embeddings). In this attempted ators can naturally benefit from modern hardware acdesign, certain database operators have two operating celeration techniques since the computation is reduced modes, which we define as follows: (1) DB operators, to tensor operations. In contrast, conventional graph which refer to traditional database operations executed queries sufer from random data accesses, which are not on explicitly stored data, and (2) ML operators, where trivial to accelerate [ 9 ]. raw data accesses are replaced with Machine Learning inference calls. The latter does not require graph data accesses to finalize a computation, as it is carried out as 3. Challenges matrix multiplications using a given query input and a trained model. With this work, we argue that executing time-consuming

To exemplify this concept, we briefly describe queries on incomplete Knowledge Graphs is counterQuery2Box [ 8 ], a graph ML method that solves multi-hop productive since the processing will, nonetheless, yield queries of arbitrary length and type. The results are ap- incomplete results sets. Instead, we relax the requireproximated by traversing a learned latent space using pro- ment for exact answers and discuss potential research jections and intersections of hyper-rectangles. This sem- directions to equip the capabilities of current database inal work achieves noteworthy accuracy results, proving management systems with predictive powers. its capabilities for approximation and completing the results sets with meaningful inferred results. Furthermore, 3.1. Hybrid Query Optimizer attesting to its acceleration benefits, Query2Box’s theoretical response time grows linearly in the number of hops. When employing both DB and ML operators, convenIn contrast, multi-hop traversals of heterogeneous graphs tional cost-based query optimizers are insuficient since with raw data accesses are known to have exponential they are solely based on cardinality estimation and extime complexity [ 8 ]. Query2Box can serve as an ML oper- ecution time, whereas the envisioned architecture also ator in our envisioned database to approximate traversals. features uncertainty constraints. To materialize the pro

However, deep learning models’ decision-making pro- posed predictive graph database, where the predictions cess is opaque to the user, who can only observe the input are guided and controlled by uncertainty bounds, we will and output, thus causing a lack of credibility in the pre- explore a novel optimization process that complements dictions obtained. For this reason, despite the impressive traditional query optimizers in database management sysadvances and breakthroughs of ML methods, their adop- tems. The query optimization can potentially be framed tion remains limited. For a graph database, particularly, as a multi-objective cost function that minimizes IO while ofering predicted query results with no control over the ensuring the uncertainty threshold is met. We will redesired error or uncertainty bound is counter-productive. fer to the two cost models as performance-based and This research aims to tackle the trustworthiness chal- uncertainty-based, respectively. lenge by investigating methods to allow for statistically Performance-based Optimization. The performancesound uncertainty bounds per query. To illustrate, the based cost model estimates the IO costs on a given physfollowing two-hop Cypher query, which identifies the ical plan. It assigns a score for each valid physical query item bought by customers related to a customer named plan based on the expected processing cost and cardiAnna, restricts the tolerated error at 5%, thus allowing nality estimations. In the context of ML-enabled graph for ML predictions to be employed: databases, a performance-based cost function operates using conventional database methods for cost estimation M A T C H ( : C u s t o m e r { n a m e : ' A n n a ' } ) - [ : R E L A T E D _ T O ] - > for DB operators. Estimating the cost of ML operators ( : C u s t o m e r ) - [ : B O U G H T ] - > ( r : I t e m ) should follow a diferent approach: since the results of R E T U R N r one ML operator are obtained, regardless of query, using W I T H M A X I M U M U N C E R T A I N T Y 0 . 0 5 ; the same input type and model as a predefined number of matrix multiplications, the cost can always be accurately computed. The cardinality estimates are, however, noteworthy. Traditional databases consider cardinality estimation to decide on the order of operators in the re

The user-defined uncertainty bounds can potentially assist the database query optimizer in identifying the best physical plan. For example, to satisfy the error threshold, 2 1 3 4

5 Query 1: MATCH ( 2 )-[r]->(

RETURN p; Query 2: MATCH ( 5 )-[r]->(

RETURN p;

Ingestion time 7

6 )-[r]->(p: )-[r]->(p: 8 ) )

ML Operator

DB Operator

Node Type 1

Node Type 2

Node Type 3

Inference-Based

Queries

Mixed

Queries

Raw-Data

Queries iton yc h

g e n i

h lopCm tryLae taaD ueQ lw o oldest

Data freshness newest (a) Examples of queries for a heterogeneous, dynamic graph, where nodes 1 to 5 were used to train the model of an ML operator.

(b) Relation between inference capabilities and query latency with respect to the ingestion timestamp of the queried data.

Adapted from [ 4 ]. sulting physical plan. Predictive databases require an changes [ 4, 5 ]. Relying on ML models for querying caadditional layer of complexity: choosing between oper- pabilities cannot overlook the overhead introduced by ator execution modes (i.e., DB or ML) will potentially training and evaluating the deployed models. Whether result in diferent cardinalities for the result set since ML training happens as a background or periodic mechanism operators include plausible outcomes. triggered by concept drift monitors, querying a DBMS Bounding the Query Error. Similar to prior work [ 10 ], should always consult the freshest data with low latency. we extend graph query languages with support for user- Newly ingested data may not have been used to train the defined error threshold, as shown in Section 2. Hence, the current models backing the ML operators. However, due database user can choose if the system can maximize in- to the non-euclidean nature of graphs, our system could ferred results, obtain a mix of grounded and predicted an- continue to ofer predicted outcomes even for new data swers, or restrict the inference capabilities, depending on points up to a certain extent and with a caveat. application requirements. To the best of our knowledge, We exemplify this trade-of using the heterogeneous no general-purpose method currently exists to quantify graph depicted in Figure 1a. We assume a transductive the error of ML inference for embedding-based methods. link prediction model that assists the traversal ML opera1. Estimating Uncertainty. Promising directions for black- tor was trained using nodes 1 to 5. In contrast, nodes 6, box models, such as Conformal Prediction and Venn Pre- 7, and 8 were ingested after training. Query 1 traverses a dictors, rely on calibration sets to provide sound uncer- two-hop neighborhood (i.e., nodes 2, 1, 4) in the graph tainty bounds at the expense of producing multiple pre- that was covered during training; therefore, the link predictions or probabilities of a label, guaranteeing that the diction model can cater to this query. However, query 2 ground truth is among the outputs [ 11 ]. Such light in- reaches nodes and connections that the model has not strumentation is desirable for the query optimization pro- seen (e.g., node 7). Here, the system can ofer predictions cess; quantifying the uncertainty should not dominate the only for a sub-plan of the query while being forced to query latency time. This work investigates whether and follow explicit links for the rest. how such methods can be utilized for hybrid query plans. Figure 1b showcases the trade-of between complete2. Optimization Based on Uncertainty. Given that an ness and latency. Querying new data cannot use oracle exists to ensure accurate uncertainty estimate for inference-based methods, denoted as ML operators, unone ML operator or query sub-plan, we also explore how til the models are updated and, therefore, need to rely to obtain a precise estimate for a whole physical plan that on expensive traversals (i.e., DB operators) that result in uses a mix ML and traditional DB operators. Intuitively, incomplete results. Transductive graph ML models are the uncertainty estimation can be regarded as error especially afected by this compromise, as they need to probability. Assuming that the error of DB operators is build embeddings for all the entities at training time. On 0, estimating a physical plan’s uncertainty can perhaps the other hand, inductive approaches such as GraphSage be computed as a chain of prior probabilities. can mitigate the gap by building embeddings on-thelfy for new data but still sufer from concept drift that 3.2. Continuous Training and Inference requires re-training [ 12 ]. This work will review lowlatency training paradigms and investigate the trade-of Knowledge graphs are highly dynamic, both in terms introduced by combining DB and ML operators. of newly ingested data, but also in terms of schema

Closely related to this PhD project, a recent report

introduced the definition of Neural Graph Databases, which tackle the incompleteness assumption of large KGs through ML inference powered by Graph Representation Learning [ 13 ]. Our work builds on this concept by considering error-guided query optimization techniques. Furthermore, vector databases such as Milvus [ 14 ] are designed and optimized to maintain domain-agnostic vector representations of complex data. They ofer fast access to the embeddings and eficient similarity searches in learned latent space. Our design requires generating and maintaining embeddings, potentially benefiting from vector databases for fast retrieval and distance-based queries in latent spaces. Moreover, our work is closely intertwined with approximate query processing (AQP) [ 10 ] Recent research enabled by learned models shows potential in overcoming the performance of sample-based AQP and achieves fast, accurate approximations using a small memory footprint [ 15 ]. Similar to AQP methods, this work aims to approximate graph queries while providing mechanisms to estimate the approximation error. Finally, our goals are akin to systems that ofer logical reasoning capabilities over knowledge graphs, such as Vadalog [ 16 ]. However, this work features reasoning capabilities through ML models with bounded state size instead of computationally expensive rule-based approaches.

5. Conclusion

This paper described research directions and challenges of empowering graph databases with inference capabilities. We presented a potential query optimization strategy guided by user-defined error bounds and delved into the trade-ofs to achieve highly accurate and complete results while minimizing query latency. Lastly, we discussed the proposed PhD project in the context of existing literature. As a next step, we plan to develop a prototype of the hybrid query optimizer and integrate it into open-source graph database eforts.

Acknowledgments

This work is partially supported by the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation.

References

[1] M. Faloutsos , P. Faloutsos , C. Faloutsos , On powerlaw relationships of the internet topology , in: SIGCOMM, ACM, 1999 , pp. 251 - 262 .

[2] S. Sahu , A. Mhedhbi , S. Salihoglu , J. Lin , M. T. Özsu , The ubiquity of large graphs and surprising challenges of graph processing: extended survey , VLDB J . 29 ( 2020 ) 595 - 618 .

[3] R. Mavlyutov , C. Curino , B. Asipov , P. CudreMauroux, Dependency-driven analytics: A compass for uncharted data oceans ., in: CIDR , 2017 .

[4] S. Horchidan , P. Carbone, ORB: Empowering graph queries through inference , 2023. First International Workshop on Data Management for Knowledge Graphs.

[5] M. Lissandrini , D. Mottin , K. Hose , T. B. Pedersen , Knowledge graph exploration systems: are we lost?, in: CIDR, www .cidrdb.org, 2022 .

[6] A. Hogan , E. Blomqvist, M. Cochez , C. d'Amato, G. D. Melo , C. Gutierrez , S. Kirrane , J. E. L. Gayo , R. Navigli , S. Neumaier , et al., Knowledge graphs , ACM Computing Surveys (Csur) 54 ( 2021 ) 1 - 37 .

[7] A. J. Dudzik , P. Veličković , Graph neural networks are dynamic programmers , Advances in Neural Information Processing Systems 35 ( 2022 ) 20635 - 20647 .

[8] H. Ren , W. Hu , J. Leskovec, Query2box: Reasoning over knowledge graphs in vector space using box embeddings, in: ICLR, OpenReview .net, 2020 .

[9] X. Shi , Z. Zheng , Y. Zhou , H. Jin , L. He , B. Liu , Q. Hua , Graph processing on gpus: A survey , ACM Comput. Surv . 50 ( 2018 ) 81 : 1 - 81 : 35 .

[10] S. Agarwal , B. Mozafari , A. Panda , H. Milner , S. Madden , I. Stoica , Blinkdb: queries with bounded errors and bounded response times on very large data , in: EuroSys, ACM, 2013 , pp. 29 - 42 .

[11] V. Vovk , A. Gammerman , G. Shafer, Algorithmic learning in a random world, Springer Science & Business Media , 2005 .

[12] W. L. Hamilton , Z. Ying , J. Leskovec , Inductive representation learning on large graphs , in: NIPS , 2017 , pp. 1024 - 1034 .

[13] H. Ren , M. Galkin , M. Cochez , Z. Zhu , J. Leskovec , Neural graph reasoning: Complex logical query answering meets graph databases , arXiv preprint arXiv:2303.14617 ( 2023 ).

[14] J. Wang , X. Yi , R. Guo , H. Jin , P. Xu , S. Li , X. Wang , X. Guo , C. Li , X. Xu , K. Yu , Y. Yuan , Y. Zou , J. Long , Y. Cai , Z. Li , Z. Zhang , Y. Mo , J. Gu , R. Jiang , Y. Wei , C. Xie , Milvus: A purpose-built vector data management system , in: SIGMOD Conference , ACM, 2021 , pp. 2614 - 2627 .

[15] Q. Ma , A. M. Shanghooshabad , M. Almasi , M. Kurmanji , P. Triantafillou , Learned approximate query processing: Make it light, accurate and fast, in: CIDR, www .cidrdb.org, 2021 .

[16] L. Bellomarini , E. Sallinger, G. Gottlob, The Vadalog system: Datalog-based reasoning for knowledge graphs , Proc. VLDB Endow . 11 ( 2018 ) 975 - 987 .