Evolutionary rule learning in knowledge graphs with industry applications

Thesis

Artificial Intelligence harnessed from knowledge graphs and logical reasoning yields excellent interpretability as well as proficient reasoning and decision-making capabilities. Declarative rules, such as Prolog and Datalog, are prevalent formalisms for expressing expert knowledge and are employed in numerous systems due to their inherent explicability. This thesis introduces Evoda, a novel, evolutionary-based algorithm conceived for rule mining on large-scale knowledge graphs (KGs) and classification problems. While current methodologies examine the rule hypothesis space undertake exhaustive searches, subjected to heuristic and syntactic limitations on the rule language, thereby constraining the quality of the derived rules. In this research, the rule hypothesis space is broadened from conventional path rules to encompass general Datalog rules, with Evoda as a new metaheuristic genetic logic programming algorithm. Rule evaluation is extended from the restrictive closed world assumption (CWA) to a more practical open world assumption (OWA). Experimental results, assessed using various evaluation metrics on multiple real-world knowledge graphs, underscore Evoda's proficiency in mining superior quality rules, its enhanced precision in predictions within the enlarged rule space, and its significant strides in efficiency and scalability, handling up to 22 million facts within mere seconds. Additionally, we proposed and demonstrated that existential rules accelerate the learning rate through the inclusion of intermediate states. It surpasses several state-of-the-art rule mining and embedding models in KG completion tasks. From a machine learning standpoint, Evoda necessitates only a select few hyperparameters that display discernible patterns, thus obviating the need for hyperparameter tuning. Moreover, Evoda demonstrates exceptional performance on diverse classification datasets from academic to industry applications. In summary, this work accentuates the feasibility, effectiveness, and efficiency of the newly proposed evolutionary learning framework.

Authors: Wu, L

• Type of award: DPhil
• Level of award: Doctoral
• Awarding institution: University of Oxford
• Language: English
• Keywords: rule learning; knowledge graph; evolutionary algorithm
• Subjects: Algorithms; Evolutionary programming (Computer science); Knowledge and learning