Temporally-aware node embeddings for evolving networks topologies

Issue title: Special section: Distilled insights from IBERAMIA 2022

Guest editors: Ana Cristina Bicharra Garcia and Mariza Ferro

Article type: Research Article

Authors: Enes, Karen B.^{; *} | Nunes, Matheus | Murai, Fabricio | Pappa, Gisele L.

Affiliations: Computer Science Department (DCC), Universidade Federal de Minas Gerais (UFMG), Belo Horizonte, Brazil

Correspondence: [*] Corresponding author. E-mail: karen@dcc.ufmg.br.

Abstract: Static node embedding algorithms applied to snapshots of real-world applications graphs are unable to capture their evolving process. As a result, the absence of information about the dynamics in these node representations can harm the accuracy and increase processing time of machine learning tasks related to these applications. Aiming at fill the gap regarding the inability of static methods to capture evolving processes on dynamic networks, we propose a biased random walk method named Evolving Node Embedding (EVNE). EVNE leverages the sequential relationship of graph snapshots by incorporating historic information when generating embeddings for the next snapshot. It learns node representations through a neural network, but differs from existing methods as it: (i) incorporates previously run walks at each step; (ii) starts the optimization of the current embedding from the parameters obtained in the previous iteration; and (iii) uses two time-varying parameters to regulate the behavior of the biased random walks over the process of graph exploration. Through a wide set of experiments we show that our approach generates better embeddings, outperforming baselines by up to 20% in a downstream node classification task. EVNE’s embeddings achieve better performance than others, based on experiments with four classifiers and five datasets. In addition, we present seven variations of our model to show the impact of each of EVNE’s mechanisms.

Keywords: Node embeddings, evolving graphs, representation learning

DOI: 10.3233/AIC-230028

Journal: AI Communications, vol. 37, no. 3, pp. 411-428, 2024