Comparative Analysis of Logic Reasoning and Graph Neural Networks for Ontology-Mediated Query Answering With a Covering Axiom
The problem of query answering over incomplete attributed graph data is a challenging field of database management systems and artificial intelligence. When there are rules on data structure expressed in the form of the ontology, the theoretical complexity of finding exact solution satisfying ontolo...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2023-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/10216983/ |
| _version_ | 1797736964941676544 |
|---|---|
| author | Olga Gerasimova Nikita Severin Ilya Makarov |
| author_facet | Olga Gerasimova Nikita Severin Ilya Makarov |
| author_sort | Olga Gerasimova |
| collection | DOAJ |
| description | The problem of query answering over incomplete attributed graph data is a challenging field of database management systems and artificial intelligence. When there are rules on data structure expressed in the form of the ontology, the theoretical complexity of finding exact solution satisfying ontology constraints increases. Logic-based methods use theoretical constructions to obtain efficient rewritings of the original queries with respect to ontology and find an answer to the rewriting query over incomplete data. However, there is an opportunity to use faster machine learning methods to label all the data and query over the “most probable” data model without taking into account the ontology. This research paper investigates the effectiveness and trustworthiness of both mentioned approaches for answering ontology-mediated queries on graph databases that integrate an ontology with a covering axiom, which states that every node belongs to either of two classes. The first approach involves finding precise answers through logical reasoning and rewriting the problem into a datalog program, while the second approach employs a trained graph neural network to label data in a binary classification problem and leverages SQL for query answering. We conduct an in-depth analysis of the time performance of these approaches and evaluate the impact of training set selection on their ability of correct query answering. By comparing these approaches across various experiments, we provide insights into their strengths and limitations for answering ontology-mediated queries containing a Boolean conjunctive query. In particular, we showed the importance of logic-based approaches for ontology with a covering axiom and the inability of machine learning methods to find answers for ontology-mediated queries in large networks. |
| first_indexed | 2024-03-12T13:21:32Z |
| format | Article |
| id | doaj.art-9354b35707f6454ea8c37c651a273b31 |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-03-12T13:21:32Z |
| publishDate | 2023-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-9354b35707f6454ea8c37c651a273b312023-08-25T23:00:57ZengIEEEIEEE Access2169-35362023-01-0111880748808610.1109/ACCESS.2023.330527210216983Comparative Analysis of Logic Reasoning and Graph Neural Networks for Ontology-Mediated Query Answering With a Covering AxiomOlga Gerasimova0https://orcid.org/0000-0002-3598-7701Nikita Severin1Ilya Makarov2https://orcid.org/0000-0002-3308-8825School of Data Analysis and Artificial Intelligence, HSE University, Moscow, RussiaSchool of Data Analysis and Artificial Intelligence, HSE University, Moscow, RussiaISP RAS Research Center for Trusted Artificial Intelligence, Moscow, RussiaThe problem of query answering over incomplete attributed graph data is a challenging field of database management systems and artificial intelligence. When there are rules on data structure expressed in the form of the ontology, the theoretical complexity of finding exact solution satisfying ontology constraints increases. Logic-based methods use theoretical constructions to obtain efficient rewritings of the original queries with respect to ontology and find an answer to the rewriting query over incomplete data. However, there is an opportunity to use faster machine learning methods to label all the data and query over the “most probable” data model without taking into account the ontology. This research paper investigates the effectiveness and trustworthiness of both mentioned approaches for answering ontology-mediated queries on graph databases that integrate an ontology with a covering axiom, which states that every node belongs to either of two classes. The first approach involves finding precise answers through logical reasoning and rewriting the problem into a datalog program, while the second approach employs a trained graph neural network to label data in a binary classification problem and leverages SQL for query answering. We conduct an in-depth analysis of the time performance of these approaches and evaluate the impact of training set selection on their ability of correct query answering. By comparing these approaches across various experiments, we provide insights into their strengths and limitations for answering ontology-mediated queries containing a Boolean conjunctive query. In particular, we showed the importance of logic-based approaches for ontology with a covering axiom and the inability of machine learning methods to find answers for ontology-mediated queries in large networks.https://ieeexplore.ieee.org/document/10216983/Computational complexitydatalog reasonerdisjunctive dataloggraph machine learninggraph neural networksnode classification |
| spellingShingle | Olga Gerasimova Nikita Severin Ilya Makarov Comparative Analysis of Logic Reasoning and Graph Neural Networks for Ontology-Mediated Query Answering With a Covering Axiom IEEE Access Computational complexity datalog reasoner disjunctive datalog graph machine learning graph neural networks node classification |
| title | Comparative Analysis of Logic Reasoning and Graph Neural Networks for Ontology-Mediated Query Answering With a Covering Axiom |
| title_full | Comparative Analysis of Logic Reasoning and Graph Neural Networks for Ontology-Mediated Query Answering With a Covering Axiom |
| title_fullStr | Comparative Analysis of Logic Reasoning and Graph Neural Networks for Ontology-Mediated Query Answering With a Covering Axiom |
| title_full_unstemmed | Comparative Analysis of Logic Reasoning and Graph Neural Networks for Ontology-Mediated Query Answering With a Covering Axiom |
| title_short | Comparative Analysis of Logic Reasoning and Graph Neural Networks for Ontology-Mediated Query Answering With a Covering Axiom |
| title_sort | comparative analysis of logic reasoning and graph neural networks for ontology mediated query answering with a covering axiom |
| topic | Computational complexity datalog reasoner disjunctive datalog graph machine learning graph neural networks node classification |
| url | https://ieeexplore.ieee.org/document/10216983/ |
| work_keys_str_mv | AT olgagerasimova comparativeanalysisoflogicreasoningandgraphneuralnetworksforontologymediatedqueryansweringwithacoveringaxiom AT nikitaseverin comparativeanalysisoflogicreasoningandgraphneuralnetworksforontologymediatedqueryansweringwithacoveringaxiom AT ilyamakarov comparativeanalysisoflogicreasoningandgraphneuralnetworksforontologymediatedqueryansweringwithacoveringaxiom |