Logical–Mathematical Foundations of a Graph Query Framework for Relational Learning

Pedro Almagro-Blanco, Fernando Sancho-Caparrini and Joaquín Borrego-Díaz ()
Additional contact information
Pedro Almagro-Blanco: Departamento Ciencias de la Computación e Inteligencia Artificial, E. T. S. Ingeniería Informática, Universidad de Sevilla, 41012 Sevilla, Spain
Fernando Sancho-Caparrini: Departamento Ciencias de la Computación e Inteligencia Artificial, E. T. S. Ingeniería Informática, Universidad de Sevilla, 41012 Sevilla, Spain
Joaquín Borrego-Díaz: Departamento Ciencias de la Computación e Inteligencia Artificial, E. T. S. Ingeniería Informática, Universidad de Sevilla, 41012 Sevilla, Spain

Mathematics, 2023, vol. 11, issue 22, 1-22

Abstract: Relational learning has attracted much attention from the machine learning community in recent years, and many real-world applications have been successfully formulated as relational learning problems. In recent years, several relational learning algorithms have been introduced that follow a pattern-based approach. However, this type of learning model suffers from two fundamental problems: the computational complexity arising from relational queries and the lack of a robust and general framework to serve as the basis for relational learning methods. In this paper, we propose an efficient graph query framework that allows for cyclic queries in polynomial time and is ready to be used in pattern-based learning methods. This solution uses logical predicates instead of graph isomorphisms for query evaluation, reducing complexity and allowing for query refinement through atomic operations. The main differences between our method and other previous pattern-based graph query approaches are the ability to evaluate arbitrary subgraphs instead of nodes or complete graphs, the fact that it is based on mathematical formalization that allows the study of refinements and their complementarity, and the ability to detect cyclic patterns in polynomial time. Application examples show that the proposed framework allows learning relational classifiers to be efficient in generating data with high expressiveness capacities. Specifically, relational decision trees are learned from sets of tagged subnetworks that provide both classifiers and characteristic patterns for the identified classes.

Keywords: graph pattern matching; graph query; node classification; relational machine learning; subgraph classification; symbolic artificial intelligence (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2023
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/11/22/4672/pdf (application/pdf)
https://www.mdpi.com/2227-7390/11/22/4672/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:11:y:2023:i:22:p:4672-:d:1281832

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().