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

Longar, Mark David (avtor), Š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.

• Jezik: Angleški jezik
• Ključne besede: graph neural networks, relational deep learning, over-squashing, graph rewiring
• Vrsta gradiva: Diplomsko delo/naloga
• Tipologija: 2.11 - Diplomsko delo
• Organizacija: FRI - Fakulteta za računalništvo in informatiko
• Leto izida: 2025
• PID: 20.500.12556/RUL-171323
• COBISS.SI-ID: 247474435
• Datum objave v RUL: 22.08.2025

Sekundarni jezik

• Jezik: Slovenski jezik
• Naslov: Vpliv relacijske sheme na uspešnost grafovskih nevronskih mrež

Izvleček

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.

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