Research On Network Representation Learning Algorithm Based On Connectivity Perception And Deviation Feedback

With the advent of the era of big data,complex networks appear in various scenarios in the real world.High-quality network analysis allows users to have a deeper understanding of the content behind the massive data,which is beneficial for important network analysis tasks such as node classification,link prediction and visualization.However,most graph analysis tasks have the problem with high computational complexity and large space overhead.Network representation learning is a profound and efficient method to solve network analysis tasks.It maps network nodes to low-dimensional vector spaces while retaining the structural and attribute information of the original network to the greatest extent.Network representation learning algorithms based on random walks have received widespread attention in recent years due to their scalability.The random walk model is mainly divided into two stages.First,perform multiple random walks on each node in the network,and then use the Skip-Gram model to train the node vectors from the sampled node sequences.However,mainstream methods usually adopt a ‘one-size-fits-all'sampling strategy,resulting that random walks generate a large number of redundant samples at different stages of sampling,which introduces noise to the network representation learning and seriously affects efficiency.Therefore,an adaptive random walk algorithm based on connectivity perception and deviation feedback,ConDevRW is proposed.First,analyze the primary cause of sample redundancy introduced by transition probability and propose a new transfer strategy based on local connectivity perception to reduce repeated sampling caused by direct backtracking and indirect backtracking,which increase the proportion of effective information in the sample set.At the same time,based on the sampling deviation between the sample set and the original network,a single-path convergence monitor and a global convergence monitor are designed to adaptively determine the length of the node sequence and the number of walks.They can proactively stop sample when the sampling process converges to reduce the redundancy caused by the node sequences and number of walks.ConDevRW controls the random walk according to the network connectivity and sampling deviation.It can greatly reduce the redundant samples generated in the sampling stage while ensuring the sample quality of the original network topology as much as possible,thereby improve the scalability of the network representation learning algorithm.Experimental results on multiple datasets in different fields show that ConDevNE,a network representation learning system based on ConDevRW sampling,can significantly promote the efficiency and scalability of representation learning while ensuring the accuracy of multi-label classification and link prediction.Compared with representative network representation learning algorithms,ConDevNE's execution time speedup ratio can reach 1.3-46.2 times.Moreover,when applying node vectors from different datasets to downstream tasks,ConDevNE achieved an improvement of 2.7%-12.8% on the Micro-F1 of multi-label classification,and achieved an improvement of 0.7%-23.6% on the AUC of link prediction.