An experimental analysis of Link Prediction methods over Microservices Knowledge Graphs

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.

I grafi sono un approccio efficace per rappresentare i dati. Possono essere visti come una collezione di oggetti (nodi) e le relazioni tra di essi (archi o collegamenti). L'efficacia di questa struttura risiede nel valore intrinseco delle relazioni tra i punti dati, che possono fornire informazioni anche più significative delle proprietà dei dati stessi. Un tipo importante di grafo è il Knowledge Graph, in cui a ciascun nodo e arco è associato un tipo. Spesso i dati del grafo sono incompleti e, in questo caso, non è possibile recuperare informazioni utili. La predizione dei collegamenti, nota anche come completamento del knowledge graph, consiste nel compito di inferire se ci sono archi o nodi mancanti in un grafo. Sono stati sviluppati modelli di diversi tipi, tra cui modelli basati su apprendimento automatico, basati su regole e basati su reti neurali, per affrontare questo problema. L'obiettivo di questa ricerca è comprendere come i metodi di previsione dei collegamenti si comportano in uno scenario di utilizzo reale. Pertanto, sono stati confrontati più modelli su diverse metriche di accuratezza e requisiti relativi a production-level use-cases su un dataset di tracciamento di microservizi. I modelli sono stati allenati e testati su due diversi knowledge graph ottenuti dalla modellazione dei dati, uno che tiene conto delle informazioni temporali e l'altro che non le tiene in considerazione. Inoltre, le predizioni dei modelli sono state valutate sia come di consueto nella letteratura, sia simulando uno scenario di utilizzo reale. Il confronto ha mostrato che modelli troppo complessi non possono essere utilizzati quando il tempo durante la fase di allenamento e/o inferenza è critico. Il miglior modello per la predizione tradizionale è stato RotatE, che di solito ha raddoppiato il punteggio del secondo miglior modello. Considerando la predizione nello use-case, RotatE è stato pari a QuatE, che richiedeva molto più tempo per l'allenamento e la previsione. Hanno ottenuto punteggi migliori del 20\% al 40\% rispetto al terzo miglior modello, a seconda del caso. Inoltre, la maggior parte dei modelli ha richiesto meno di un millisecondo per prevedere una tripletta, con NodePiece che è stato il più veloce, superando ConvE di un margine del 4\%. Considernado il tempo di training, NodePiece batte AnyBURL del 40\%. Considerando l'utilizzo della memoria, ancora una volta NodePiece è il migliore, con un ordine di grandezza almeno 10 volte superiore rispetto alla maggior parte degli altri modelli. RotatE è stato considerato il miglior modello complessivo perché aveva la migliore accuratezza e una prestazione sopra la media sugli altri requisiti. Inoltre, è stata effettuata una simulazione dell'integrazione di RotatE con un tool di tracciamento di campionamento dinamico, mostrando risultati simili a quelli ottenuti in precedenza. Infine, vengono presentati un'analisi approfondita dei risultati e suggerimenti per i lavori futuri.