Research On The Application Of Locally Sensitive Hashing In Network Representation Learning

Network is an important form to express entities and their connections,such as social network,highway network and paper citation network.With the continuous deepening and development of the Internet,the complexity of the network is also increasing,which makes the amount of information it carries also have greater excavation value.In the domain of network data mining,there are many significant applications,such as recommendation system,community discovery,node classification and network link prediction.However,the natural representation of most networks is high-dimensional and sparse,which makes it difficult for machine learning algorithms to be applied to network mining tasks.Therefore,how to effectively and efficiently extract the feature information in the network is an important research direction.Network representation learning,also known as network embedding,embeds highdimensional and sparse original network information into a low-dimensional and dense real vector space,so that it can be used for machine learning tasks,such as classification,clustering,nearest neighbor search and so on.It is generally believed that nodes with similar topology structure should have similar representation.In other words,nodes with closer distance in the original network should still have closer distance in the representation space;on the contrary,nodes with farther distance in the original network should have farther distance after embedded in the representation space.The local sensitive hash has this characteristic.Therefore,this paper attempts to explore the application of local sensitive hash in various tasks of network representation learning.This paper first describes the basic ideas of network representation learning and local sensitive hash,and tries to define the nearest neighbor search problem between nodes in the network,so that the local sensitive hash is introduced into network representation learning,and then extended to the link prediction task in the network.Generally speaking,the main research contents and contributions of this paper are as follows:(1)The nearest neighbor search of network nodes based on local sensitive hash is studied.In this paper,the local sensitive hash algorithm is used to map the network nodes to several hash buckets;then the distance between the node representation vectors trained by skip gram model is used to measure the similarity between two nodes,so as to define the nearest neighbor search problem of network nodes.Our experiments on real data sets show that the nearest neighbor search algorithm combined with local sensitive hash can improve the time efficiency while sacrificing certain accuracy.(2)Based on the research of(1),the local sensitive hash algorithm is introduced to the network link prediction task,and the bucket results of the local sensitive hash are applied to the network link prediction task under several different similarity calculation standards.Finally,experiments on real data sets show that the proposed method can significantly improve the time efficiency of the algorithm at the expense of certain accuracy.