N-STaRW: Normalized Spatiotemporal Random Walks on Dynamic Graphs

• L. F Steve Ataucuri Cruz USP
• Alneu de Andrade Lopes USP

DOI: https://doi.org/10.5753/eniac.2026.30547

Resumo

Graph representation learning for dynamic graphs has become an essential tool for modeling evolving interactions in real-world systems. Random walk-based methods are widely used to learn node embeddings, but many existing approaches focus primarily on either structural patterns or temporal dynamics without effectively balancing both. As a result, temporal walk strategies often prioritize recent interactions while failing to balance exploration between highand low-degree nodes. In this work, we propose N-STaRW, a spatiotemporal random walk strategy that combines temporal constraints with a degree-normalized structural component. The main idea is to guide the sampling process by preserving temporal ordering while reducing the dominance of high-degree nodes during exploration. We evaluate the method on several real-world datasets for temporal link prediction. The results show that the proposed strategy is competitive with strong baseline methods, particularly in transductive settings. Overall, our findings suggest that balancing temporal and structural information can improve representation quality in dynamic graphs.

Referências

Cao, S., Lu, W., and Xu, Q. (2016). Deep neural networks for learning graph representations. In Proceedings of the Conference on Artificial Intelligence (AAAI), pages 1145–1151.

Celikkanat, A. (2021). Graph Representation Learning with Random Walk Diffusions. PhD thesis. Thèse de doctorat dirigée par Paragios, Nikos et Malliaros, Fragkiskos Informatique université Paris-Saclay 2021.

Chen, F., Wang, Y.-C., Wang, B., and Kuo, C.-C. J. (2020). Graph representation learning: a survey. Transactions on Signal and Information Processing (APSIPA).

Defferrard, M., Bresson, X., and Vandergheynst, P. (2016). Convolutional neural networks on graphs with fast localized spectral filtering. In Advances in Neural Information Processing Systems (NeurIPS), pages 3844–3852.

Du, L., Wang, Y., Song, G., Lu, Z., and Wang, J. (2018). Dynamic network embedding : An extended approach for skip-gram based network embedding. In Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI).

Grover, A. and Leskovec, J. (2016). node2vec: Scalable feature learning for networks. KDD ’16, page 855–864. Association for Computing Machinery.

Hamilton, W. L., Ying, R., and Leskovec, J. (2017). Inductive representation learning on large graphs. In Proceedings of the 31st International Conference on Neural Information Processing Systems, NeurIPS.

Kim, Y., Park, S., and Yook, S.-H. (2016). Network exploration using true self-avoiding walks. Phys. Rev. E, 94:042309.

Kipf, T. N. and Welling, M. (2017). Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICLR).

Li, Q., Han, Z., and Wu, X.-M. (2018). Deeper insights into graph convolutional networks for semi-supervised learning. In Proceedings of the AAAI conference on artificial intelligence, volume 32.

Lü, L. and Zhou, T. (2011). Link prediction in complex networks: A survey. Physica A: Statistical Mechanics and its Applications, 390(6):1150–1170.

Mahdavi, S., Khoshraftar, S., and An, A. (2018). dynnode2vec: Scalable dynamic network embedding. In 2018 IEEE international conference on big data (Big Data), pages 3762–3765. IEEE.

Mikolov, T., Chen, K., Corrado, G., and Dean, J. (2013). Efficient estimation of word representations in vector space. In Proceedings of the International Conference on Learning Representations (ICLR).

Nguyen, G. H., Lee, J. B., Rossi, R. A., Ahmed, N. K., Koh, E., and Kim, S. (2018). Continuous-time dynamic network embeddings. International World Wide Web Conferences Steering Committee.

Noh, J. D. and Rieger, H. (2004). Random walks on complex networks. Physical Review Letters, 92(11):118701.

Oono, K. and Suzuki, T. (2019). Graph neural networks exponentially lose expressive power for node classification. In 8th International Conference on Learning Representations (ICLR).

Perozzi, B., Al-Rfou, R., and Skiena, S. (2014). Deepwalk: online learning of social representations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery & data mining, KDD ’14. ACM.

Rossi, E., Chamberlain, B., Frasca, F., Eynard, D., Monti, F., and Bronstein, M. (2020). Temporal graph networks for deep learning on dynamic graphs.

Rossi, R. and Ahmed, N. (2015). The network data repository with interactive graph analytics and visualization. Proceedings of the AAAI Conference on Artificial Intelligence, 29.

Sheng, J., Zhang, Y., and Wang, B. (2025). Continuous-time dynamic graph learning based on spatio-temporal random walks. The Journal of Supercomputing, 81(2):389.

Silva, T. and Zhao, L. (2016). Machine Learning in Complex Networks. Springer International Publishing.

Souza, A. H., Mesquita, D., Kaski, S., and Garg, V. (2022). Provably expressive temporal graph networks. In Proceedings of the 36th International Conference on Neural Information Processing Systems, NIPS ’22, Red Hook, NY, USA. Curran Associates Inc.

Tomčić, A., Savić, M., Simić, D., and Radovanović, M. (2025). Dynamic graph embedding through hub-aware random walks. In International Conference on Similarity Search and Applications, pages 315–329. Springer.

Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., and Bengio, Y. (2018). Graph attention networks. In International Conference on Learning Representations (ICLR).

Wang, D., Cui, P., and Zhu, W. (2016). Structural deep network embedding. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, page 1225–1234.

Xu, D., Ruan, C., Korpeoglu, E., Kumar, S., and Achan, K. (2020). Inductive representation learning on temporal graphs. In International Conference on Learning Representations (ICLR).