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 |