The Influence of the Relational Schema on the Performance of Graph Neural Networks

Longar, Mark David (author), Šubelj, Lovro (mentor)

Relational deep learning applies graph neural networks to data stored in relational databases by constructing graphs directly from database schemas. This thesis investigates how relational database schemas influence graph neural network performance, focusing on the over-squashing phenomenon that limits information propagation. We demonstrate that graphs derived from relational schemas exhibit performance patterns consistent with over-squashing theory, where models perform well with shallow networks but degrade with increased depth due to topological bottlenecks. To address these limitations, we develop two graph rewiring approaches: a computationally efficient approximation of Stochastic Discrete Ricci Flow and a schema-aware heuristic method that leverages domain knowledge about relational structures. Experimental results on two datasets show that targeted rewiring strategies can provide substantial performance improvements, suggesting that graph topology should be considered a design choice rather than a fixed constraint in relational deep learning systems.

• Language: English
• Keywords: graph neural networks, relational deep learning, over-squashing, graph rewiring
• Work type: Bachelor thesis/paper
• Typology: 2.11 - Undergraduate Thesis
• Organization: FRI - Faculty of Computer and Information Science
• Year: 2025
• PID: 20.500.12556/RUL-171323
• COBISS.SI-ID: 247474435
• Publication date in RUL: 22.08.2025

Secondary language

• Language: Slovenian
• Title: Vpliv relacijske sheme na uspešnost grafovskih nevronskih mrež

Abstract

Relacijsko globoko učenje uporablja grafovske nevronske mreže na podatkih, shranjenih v relacijskih podatkovnih bazah, tako da grafe tvori neposredno iz shem podatkovnih baz. V diplomski nalogi raziskujemo, kako sheme relacijskih podatkovnih baz vplivajo na uspešnost grafovskih nevronskih mrež, pri čemer se osredotočimo na fenomen prekomernega stiskanja (angl. oversquashing), ki omejuje širjenje informacij. Pokažemo, da grafi, generirani iz relacijskih shem, kažejo vzorce, skladne s teorijo prekomernega stiskanja, kjer modeli delujejo dobro s plitvimi mrežami, njihova uspešnost pa upada z večanjem globine zaradi topoloških ozkih grl. Za odpravo teh omejitev razvijemo dva pristopa prevezave grafov: računsko učinkovito aproksimacijo Stohastičnega diskretnega Riccijevega toka (SDRF) in hevristično metodo, ki upošteva shemo in domensko znanje o relacijskih strukturah. Eksperimentalni rezultati na dveh naborih podatkov kažejo, da lahko ciljno usmerjene strategije prevezave grafa znatno izboljšajo uspešnost, kar nakazuje, da bi morali v relacijskem globokem učenju topologijo grafa obravnavati kot izbiro pri načrtovanju in ne kot fiksno omejitev.

• Keywords: grafovske nevronske mreže, relacijsko globoko učenje, prekomerno stiskanje, prevezava grafa