GPU Acceleration for Inductive Logic Rule Mining in Knowledge Graphs

Thesis title: GPU Acceleration for Inductive Logic Rule Mining in Knowledge Graphs
Author: Naar, Vojtěch
Thesis type: Diploma thesis
Supervisor: Zeman, Václav
Opponents: Sýkora, Lukáš
Thesis language: English
Abstract:
This master thesis focuses on accelerating support and confidence computation in inductive logic rule mining over large RDF knowledge graphs. The work builds on AMIE-style Horn rule mining and the RDFRules framework, where candidate rules are evaluated by repeatedly executing join-like graph pattern matching operations over large triple sets. The thesis investigates whether this counting phase can be accelerated using native C++ implementations and NVIDIA CUDA GPU execution while preserving the original rule semantics. The practical contribution consists of a faithful C++ rewrite of the RDFRules counting logic, a cache-oriented CPU implementation based on CSR indexes, and a CUDA implementation that stores graph indexes in GPU memory and evaluates rules using massively parallel DFS kernels. The implementations are integrated with the Scala RDFRules framework through a shared native library and Java Native Access. Experimental evaluation on synthetic, DBpedia, and biomedical datasets shows that GPU acceleration is strongest when rule evaluation produces large body-size search spaces, while CPU-side CSR optimization is highly dependent on graph topology and may regress on high-fanout predicates.
Keywords: Logic rule; graph mining; GPU; CUDA; Parallelism
Thesis title: GPU akcelerace pro indukční logické dolování pravidel v grafech
Author: Naar, Vojtěch
Thesis type: Diplomová práce
Supervisor: Zeman, Václav
Opponents: Sýkora, Lukáš
Thesis language: English
Abstract:
Tato diplomová práce se zaměřuje na akceleraci výpočtu podpory a spolehlivosti při indukčním logickém dolování pravidel v rozsáhlých znalostních grafech ve formátu RDF. Práce vychází z dolování Hornových pravidel ve stylu AMIE a frameworku RDFRules, kde jsou kandidátní pravidla vyhodnocována opakovaným prováděním operací podobných spojení nad rozsáhlými množinami trojic. Práce zkoumá, zda lze tuto fázi počítání akcelerovat pomocí nativních implementací v jazyce C++ a GPU vykonávání prostřednictvím NVIDIA CUDA při zachování původní sémantiky pravidel. Praktický přínos práce spočívá ve věrném přepisu logiky počítání RDFRules do jazyka C++, v CPU implementaci orientované na paměťovou lokalitu využívající indexy ve formátu CSR a v implementaci CUDA, která ukládá grafové indexy do paměti GPU a vyhodnocuje pravidla pomocí masivně paralelních DFS jader. Implementace jsou integrovány s frameworkem Scala RDFRules prostřednictvím sdílené nativní knihovny a Java Native Access. Experimentální vyhodnocení na syntetické, DBpedia a biomedicínské datové sadě ukazuje, že GPU akcelerace je nejsilnější tehdy, když vyhodnocování pravidel generuje velké prohledávací prostory těl pravidel, zatímco CPU optimalizace pomocí CSR je silně závislá na topologii grafu a může vykazovat regresi u predikátů s vysokým větvením.
Keywords: CUDA; dolování z grafů; grafová pravidla; Paralelismus; GPU

Information about study

Study programme: Znalostní a webové technologie
Type of study programme: Magisterský studijní program
Assigned degree: Ing.
Institutions assigning academic degree: Vysoká škola ekonomická v Praze
Faculty: Faculty of Informatics and Statistics
Department: Department of Information and Knowledge Engineering

Information on submission and defense

Date of assignment: 4. 12. 2025
Date of submission: 4. 5. 2026
Date of defense: 8. 6. 2026
Identifier in the InSIS system: https://insis.vse.cz/zp/94803/podrobnosti

Files for download

    Last update: