Graphs are a powerful way to represent data. They can be seen as a collection of objects (nodes) and the relationships between them (edges or links). The power of this structure has its intrinsic value in the relationship between data points that can even provide more information than the data properties. An important type of graph is Knowledge Graphs in which each node and edge has a type associated. Often graph data is incomplete and in this case, it is not possible to retrieve useful information. Link prediction, also known as knowledge graph completion, is the task of inferring if there are missing edges or nodes in a graph. Models of different types, including Machine Learning-based, Rule-based, and Neural Network-based models have been developed to address this problem. The goal of this research is to understand how link prediction methods perform in a real use-case scenario. Therefore, multiple models have been compared on different accuracy metrics and production case requirements on a microservice tracing dataset. Models have been trained and tested on two different knowledge graphs obtained from the data, one that takes into account the temporal information, and the other that does not. Moreover, the prediction of the models has been evaluated with what is usually done in the literature, and also mimicking a real use-case scenario. The comparison showed that too complex models cannot be used when the time, at training, and/or inference phase, is critical. The best model for traditional prediction has been RotatE which usually doubled the score of the second- best model. Considering the use-case scenario, RotatE was tied with QuatE, which required a lot more time for training and predicting. They scored 20% to 40% better than the third-best performing model, depending on the case. Moreover, most of the models required less than a millisecond for predicting a triplet, with NodePiece that was the fastest, beating ConvE by a 4% margin. For the training time, NodePiece beats AnyBURL by 40%. Considering the memory usage, again NodePiece is the best, by an order of magnitude of at least 10 when compared to most of the other models. RotatE has been considered the best model overall because it had the best accuracy and an above-average performance on the other requirements. Additionally, a simulation of the integration of RotatE with a dynamic sampling tracing tool has been carried out, showing similar results to the ones previously obtained. Lastly, a thorough analysis of the results and suggestions for future work are presented. / Grafer är ett kraftfullt sätt att representera data. De kan ses som en samling objekt (noder) och förhållandet mellan dem (kanter eller länkar). Kraften i denna struktur har sitt inneboende värde i förhållandet mellan datapunkter som till och med kan ge mer information än dataegenskaperna. En viktig typ av graf är Knowledge Graphs där varje nod och kant har en typ associerad. Ofta är grafdata ofullständiga och i det här fallet är det inte möjligt att hämta användbar information. Länkprediktion, även känd som färdigställande av kunskapsdiagram, är uppgiften att förutsäga om det saknas kanter eller noder i en graf. Modeller av olika typer, inklusive Machine Learning-baserade, Regelbaserade och Neural Network-baserade modeller har utvecklats för att lösa detta problem. Målet med denna forskning är att förstå hur länkprediktionsmetoder fungerar i ett verkligt use-case scenario. Därför har flera modeller jämförts med olika noggrannhetsmått och produktionsfallskrav på en mikrotjänstspårningsdatauppsättning. Modeller har tränats och testats på två olika kunskapsgrafer som erhållits från data, en som tar hänsyn till tidsinformationen och den andra som inte gör det. Dessutom har förutsägelsen av modellerna utvärderats med vad som vanligtvis görs i litteraturen, och även efterlikna ett verkligt use-case scenario. Jämförelsen visade att alltför komplexa modeller inte kan användas när tiden, vid träning och/eller slutledningsfasen, är kritisk. Den bästa modellen för traditionell förutsägelse har varit RotatE som vanligtvis fördubblade poängen för den näst bästa modellen. Med tanke på användningsfallet var RotatE knuten till QuatE, vilket krävde mycket mer tid för träning och förutsägelse. De fick 20% till 40% bättre än den tredje bäst presterande modellen, beroende på fallet. Dessutom krävde de flesta av modellerna mindre än en millisekund för att förutsäga en triplett, med NodePiece som var snabbast och slog ConvE med 4% marginal. För träningstiden slår NodePiece AnyBURL med 40%. Med tanke på minnesanvändningen är återigen NodePiece bäst, med en storleksordning på minst 10 jämfört med de flesta andra modeller. RotatE har ansetts vara den bästa modellen överlag eftersom den hade den bästa noggrannheten och en prestanda över genomsnittet för övriga krav. Dessutom har en simulering av integrationen av RotatE med ett dynamiskt samplingsspårningsverktyg utförts, som visar liknande resultat som de tidigare erhållna. Slutligen presenteras en grundlig analys av resultaten och förslag till framtida arbete.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:kth-330659 |
| Date | January 2023 |
| Creators | Ruberto, Gianluca |
| Publisher | KTH, Skolan för elektroteknik och datavetenskap (EECS) |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | Swedish |
| Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | TRITA-EECS-EX ; 2023:370 |
Page generated in 0.0028 seconds