Dynamic graph embedding on event streams

Graphs are often considered an excellent way of modeling complex real-world problems since they allow to capture relationships between items. Because of their ubiquity, many research groups have focused their interest upon graph embedding techniques, seeking how vertices can be encoded into a low-dimensional latent space, useful to then perform machine learning. Recently Graph Neural Networks (GNN) have dominated the space of embeddings generation due to their inherent ability to encode latent node dependencies. Moreover, the newly introduced Inductive Graph Neural Networks gained much popularity for inductively learning and representing node embeddings through neighborhood aggregate measures. Even when an entirely new node, unseen during training, appears in the graph, it can still be properly represented by its neighboring nodes. Although this approach appears suitable for dynamic graphs, available systems and training methodologies are agnostic of dynamicity and solely rely on re-processing full graph snapshots in batches, an approach that has been criticized for its high computational costs. This work provides a solution to the problem of updating an Inductive Graph Neural Network while the graph evolves via a priority-based method for selecting rehearsed samples that guarantees low complexity and high accuracy. Finally, a data-parallel inference method has been evaluated at scale using Apache Flink, a data stream processor for real-time predictions on high volume graph data streams. This thesis is the result of a previous work done at KTH and at RISE SICS under the supervision of Prof. Seif Haridi, Paris Carbone, Vasiliki Kalavri and Giorgia Ramponi. It has then been extended adding experiments on new datasets and with a discussion on the integration of popular deep learning systems and widely used scalable data-processing frameworks. Results have been presented in the Research track of Flink Forward Europe 2019, a stream processing, real-time analytics and event-driven applications conference.

Molti problemi nel mondo reale possono essere rappresentati come grafi poichè queste strutture dati consentono di modellare relazioni tra elementi. A causa del loro vasto uso, molti gruppi di ricerca hanno tentato di rappresentare i vertici in uno spazio a bassa dimensione, utile per poi poter utilizzare tecniche di apprendimento automatico. Le reti neurali per grafi sono state ampiamente utilizzate per via della loro capacità di codificare dipendenze tra vertici. Le reti neurali induttive recentemente introdotte, inoltre, hanno guadagnato popolarità poichè consentono di generare rappresentazioni di vertici aggregando altri vertici. In questo modo anche un nodo completamente nuovo può comunque essere rappresentato utilizzando i suoi nodi vicini. Sebbene questo approccio sia adatto per grafici dinamici, i sistemi ad oggi disponibili e gli algoritmi di addestramento si basano esclusivamente sulla continua elaborazione di grafi statici, un approccio che è stato criticato per i suoi elevati costi di calcolo. Questa tesi fornisce una soluzione al problema di aggiornare una rete neurale induttiva mentre il grafo evolve tramite un metodo basato su un'euristica per la selezione dei vertici. Viene inoltre descritto un metodo per eseguire predizioni in modo scalabile in tempo reale utilizzando Apache Flink, un sistema per l'elaborazione di grandi quantità di flussi di dati in tempo reale. Questa tesi è il risultato di un lavoro svolto precedentemente a KTH, sotto la supervisione del Prof. Seif Haridi, Paris Carbone, Vasiliki Kalavri e Giorgia Ramponi. E' stata poi estesa con ulteriori esperimenti su nuovi dataset e con una discussione sull'integrazione tra sistemi di Deep Learning e sistemi per l'elaborazione scalabile. I risultati sono stati presentati nella Research track di Flink Forward Europe 2019, conferenza di stream processing e analitiche in tempo reale.