Evolving network representation learning based on random walks
Open Access
- 18 March 2020
- journal article
- research article
- Published by Springer Nature in Applied Network Science
- Vol. 5 (1) , 1-38
Abstract
Large-scale network mining and analysis is key to revealing the underlying dynamics of networks, not easily observable before. Lately, there is a fast-growing interest in learning low-dimensional continuous representations of networks that can be utilized to perform highly accurate and scalable graph mining tasks. A family of these methods is based on performing random walks on a network to learn its structural features and providing the sequence of random walks as input to a deep learning architecture to learn a network embedding. While these methods perform well, they can only operate on static networks. However, in real-world, networks are evolving, as nodes and edges are continuously added or deleted. As a result, any previously obtained network representation will now be outdated having an adverse effect on the accuracy of the network mining task at stake. The naive approach to address this problem is to re-apply the embedding method of choice every time there is an update to the network. But this approach has serious drawbacks. First, it is inefficient, because the embedding method itself is computationally expensive. Then, the network mining task outcome obtained by the subsequent network representations are not directly comparable to each other, due to the randomness involved in the new set of random walks involved each time. In this paper, we propose EvoNRL, a random-walk based method for learning representations of evolving networks. The key idea of our approach is to first obtain a set of random walks on the current state of network. Then, while changes occur in the evolving network’s topology, to dynamically update the random walks in reserve, so they do not introduce any bias. That way we are in position of utilizing the updated set of random walks to continuously learn accurate mappings from the evolving network to a low-dimension network representation. Moreover, we present an analytical method for determining the right time to obtain a new representation of the evolving network that balances accuracy and time performance. A thorough experimental evaluation is performed that demonstrates the effectiveness of our method against sensible baselines and varying conditions.Keywords
Funding Information
- Canadian Network for Research and Innovation in Machining Technology, Natural Sciences and Engineering Research Council of Canada (2017- 05680)
This publication has 29 references indexed in Scilit:
- Temporal Analysis of Language through Neural Language Models2014
- Defining and evaluating network communities based on ground-truthKnowledge and Information Systems, 2013
- Representation Learning: A Review and New PerspectivesIEEE Transactions on Pattern Analysis and Machine Intelligence, 2013
- The BioGRID Interaction Database: 2008 updateNucleic Acids Research, 2007
- Random walks on the click graph2007
- The Structure and Function of Complex NetworksSIAM Review, 2003
- Relations Between Two Sets of Variates1992
- Matrix CorrelationPsychometrika, 1984
- Generalized master equations for continuous-time random walksJournal of Statistical Physics, 1973
- The Problem of the Random WalkNature, 1905