Background
The well-blown development of the mobile internet in china has prompted the mobile social market in china to grow at an explosive rate. Ai Mei consultation (iMedia Research) data shows that the utilization rate of the Chinese instant messaging application reaches 96.9% in the last half year of 2019, the mobile social network represented by instant messaging is in a normal life state of networked people, and along with the development of domestic mobile social ecology, the user scale is expected to break through 9 hundred million in 2020. The huge mobile social user scale also means more market possibilities, and young new generations, which are dominant after 95 and 00, gradually become the dominant force of the Chinese mobile social market. This part of young users prefer a relaxed, interesting social form, favoring trendy, interesting, multi-element social scenes.
The mobile internet provides more information and services for users, and mass data also makes information processing and filtering more complex. On the one hand, users are easy to get lost in a large amount of information space and get rid of the way; on the other hand, the website loses contact with the user and cannot establish a long-term firm cooperative relationship with the user. In this context, recommendation systems have evolved. The recommendation system is a personalized system for analyzing interests and demands of users according to the existing historical data and recommending information, products, services or other users with high relevance to the users. Wherein friend recommendations are intended to recommend users with high relevance but not yet established friend relationships. This allows users (especially new users) to quickly build good circles of friends, integrate into the information services of the social network, and thereby increase user liveness and user viscosity.
In the process of evaluating the user relevance, people tend to complete the evaluation of the user relevance on the social network by training the deep neural network by utilizing the user information in order to obtain a better evaluation result. Among the many methods of deep learning, the graph neural network (Graph Neural Networks) has been widely studied and applied due to its unique design and accurate correlation evaluation results for graph structure data. After converting the social network into an abstract graph structure, the graph neural network can learn the implicit connection patterns between users. For a given user, the relevance of the remaining users to the user may be calculated based on the learned pattern.
The graph neural network is an important algorithm in the deep learning field, and the core calculation process can be summarized into the following two points:
1. and transmitting the node information to the neighborhood nodes.
2. The information is encoded using a deep neural network.
In the current graph neural network computing method, the time consumption is generally dependent on the consistency of the social network. For the social network with larger average association degree among users, the information propagation speed of the graph neural network is lower, so that the efficiency of the user relevance evaluation is limited to a certain extent, and the speed of friend recommendation is influenced.
At present, the correlation evaluation on a small-scale user group can be realized by the existing technical algorithm, but with the arrival of a big data age, the social network scale is larger and larger, such as WeChat, twitter (Twitter) and the like of billions of users, the recommendation result cannot be effectively calculated on a large graph by the existing technical algorithm due to huge time or space expenditure, and the quality and effect of the friend recommendation function are greatly influenced.
The information disclosed in this background section is only for enhancement of understanding of the general background of the invention and should not be taken as an acknowledgement or any form of suggestion that this information forms the prior art already known to a person of ordinary skill in the art.
Disclosure of Invention
The invention aims to provide a social network friend recommending method based on a graph neural network, which improves the efficiency of social user relevance evaluation, thereby improving the friend recommending speed.
In order to achieve the above purpose, the present invention provides a social network friend recommendation method based on a graph neural network, including: all users and the relation among the users are converted into a graph structure. Mapping all user attribute information into a numerical vector to obtain an attribute matrix. And executing L-layer attribute transition probability calculation, thereby obtaining attribute information of the target user and the user to be recommended after aggregating the domain information. And inputting the attribute information into a deep neural network for coding, so as to obtain information after the coding of the host node and other nodes to be recommended, calculating the relevance score of the host node relative to each other node to be recommended according to the coding information, and taking the relevance score as a recommended measurement standard for friend recommendation.
In one embodiment of the present invention, the graph structure includes nodes corresponding to users and edges corresponding to relationships between users, and the target user is a sink node of the graph structure.
In one embodiment of the present invention, performing the L-layer attribute transition probability calculation includes:
for the graph structure, the w sampling processes are repeatedly performed on the sink node and the node to be recommended. And performing an update procedure for each column of the attribute matrix, and combining the sampling procedure and the update procedure structure.
In one embodiment of the invention, repeatedly performing the w sampling process on the sink node and the node to be recommended includes estimating the probability of the random walk from node u to reach node v through 1 step using the samplesWhere v is any node in the graph structure.
In one embodiment of the present invention, the update process is performed for each column of the attribute matrix, and combining the sampling process and the update process structure includes: judging whether the numerical value of each item (u, f) in a certain column of the attribute matrix meets a first preset condition. If the first preset condition is met, using a first updating formula to transfer the probability value of the attribute of the current node uUpdate and clear attribute value +.>Attribute value +.>And updating. And after the updating is finished, combining the sampling process and the result obtained in the sampling process by using a third updating formula.
In one embodiment of the present invention, the first preset condition is:the first update formula is:the second updated formula is: />Wherein (1)>The attribute transition probability of the current node u at the current layer l is initially 0. Wherein (1)>The attribute value of the current node u at the current layer l is initially user information. Wherein (1)>The probability of attribute transition at layer 1+1 for the updated node v. And θ is an error parameter determined by the user according to the actual situation. Wherein d (u) is the number of neighbors of node u. If the value of each item (u, f) does not meet the first preset condition, ending the updating process.
Compared with the prior art, according to the social network friend recommendation method based on the graph neural network, the attribute transition probability of the user can be obtained under the sub-linear time complexity through the combination sampling process and the updating process, the dependence relationship between the transition probability calculation time and the social network consistency is eliminated, the social user relevance evaluation efficiency is improved, and therefore the friend recommendation speed is improved.
Detailed Description
The following detailed description of embodiments of the invention is, therefore, to be taken in conjunction with the accompanying drawings, and it is to be understood that the scope of the invention is not limited to the specific embodiments.
Throughout the specification and claims, unless explicitly stated otherwise, the term "comprise" or variations thereof such as "comprises" or "comprising", etc. will be understood to include the stated element or component without excluding other elements or components.
Fig. 1 is a flowchart of a social network friend recommendation method based on a graph neural network according to an embodiment of the invention. As shown in fig. 1, a social network friend recommendation method based on a graph neural network according to a preferred embodiment of the present invention includes:
s1, converting a relationship among users on a social network platform into a graph structure G, wherein the graph structure G comprises nodes corresponding to the users and edges corresponding to the relationship among the users, and a target user is a sink node of the graph structure;
firstly, the relationship among users is converted into a graph structure G, wherein the graph structure G comprises all social users, namely target users and other users, the social users correspond to nodes on the graph structure, the attention relationship among the social users corresponds to edges on the graph structure, the target users are sink nodes u of the graph structure, and the graph structure G comprises n nodes.
In the embodiment of the invention, the users refer to all registered users on the social platform, and the relationship among the users can be specifically the attention relationship among the users. For example, all registered friends on Facebook and a friend relationship network.
Specifically, for social networks such as microblogs and Facebook, instagram which have attention, users of the social networks are corresponding to nodes on the graph structure, and attention among the users is corresponding to edges on the graph structure. Specifically, if the A-user focuses on the B-user or the B-user focuses on the A-user, a bi-directional edge from the A-user node to the B-user node is established on the graph structure. The number of edges owned by one node is referred to as "degree".
For social networks with friend relations such as WeChat and QQ, users on the social networks are corresponding to graph nodes, and the friend relations are corresponding to edges on a graph structure. Specifically, if there is a buddy relationship between the A-user and the B-user (i.e., A, B is a buddy with respect to each other), a bi-directional edge is established from the A-user node to the B-user node on the graph structure.
In storing the graph structure, an adjacency list is built for each node on the graph to store all neighbors of the node. For any node v on the graph, the corresponding ingress adjacency table length d (v) represents the egress of node v.
S2, mapping the user attribute information into a numerical vector to obtain an attribute matrix R(0) ；
And transversely splicing various different types of information of the user into a vector with the length of F, wherein the user information comprises numerical information or literal information, the numerical information can be directly used, and the literal information uses a word embedding technology to map the literal into the numerical information. Two-dimensional matrix R using an n-row F-column(0) Information of all users is stored.
S3, performing L-layer attribute transition probability calculation to obtain attribute information P after aggregation of neighborhood information of a target user and a user to be recommended of a graph structure, wherein the user corresponds to a node on the graph structure;
and executing L-layer attribute transition probability calculation, and updating L according to the following formula until L is greater than a preset value L.
The update formula is: l=l+1.
Wherein the preset value of 1 is 0.
Before step S3 is performed, all nodes on the graph structure each maintain 3L vectors, corresponding to the sampling probability, residual value and attribute transition probability values of the node at each layer. For example, for any node v on the graph, it needs to maintain 3L vectors:the attribute transition probability values of the corresponding node v at layers 0, 1, … and L,the sampling probability values of the corresponding nodes v at layers 0, 1, … and L,the residual values of the corresponding node v at layers 0, 1, … and L. Remove->All other values are initialized to 0 except for the encoded information.
In the calculation process of the L-layer attribute transition probability, the sampling probability, the attribute transition probability and the residual value of each node in the 1 layer are correspondingly updated. 1 is an intermediate variable for marking the number of update layers of the current value and determining the stop time of the whole calculation process, and taking the weighted sum of the sampling probability, the attribute transition probability and the residual value of the previous L layers as the estimated value of the final attribute transition probability P after stoppingIt can be demonstrated that P and +.>The error between the two parameters does not exceed theta, wherein theta is an error parameter determined by a user according to actual conditions.
And S4, inputting the attribute transfer probability P obtained in the S3 into a deep neural network for coding to obtain information of the destination node and other nodes to be recommended after coding, and calculating the relevance score of the destination node relative to each other node to be recommended according to the coding information, wherein the relevance score is used as a recommendation measurement standard for friend recommendation.
Using the attribute transition probability P as input information to encode by using a deep neural network to obtain encoding vectors h of a host node u and other nodes v to be recommendedu And hv The correlation pi of u and v is calculated according to the following formula(u，v) 。
Correlation pi(u，v) The calculation formula of (2) is as follows: pi(u，v) ＝hu ·hv 。
From all the nodes, the first t nodes with the highest correlation value with the destination node u are found to conduct friend recommendation, t is a preset value and can be designated by a user, and the number of users recommending to a target user is indicated.
In addition, for calculation of attribute transition probability, when w is set toθ is set to +.>In this case, the embodiment of the invention may be +.>The calculation of the attribute transfer probability of the sink node and the node to be recommended under the constraint threshold of the absolute error epsilon is completed within the time complexity of the map structure, the C is the total number of the sink node and the node to be recommended in the corresponding map structure, and d is the node average degree on the map structure.
The existing attribute transition probability calculation method can only be used inThe result of the calculation under absolute error epsilon is obtained or the accurate result is obtained in the time of O (LndF).
Fig. 2 is a schematic flowchart of step S3 in fig. 1, and as shown in fig. 2, step S3 specifically includes:
s31, for the graph structure, repeatedly executing w sampling processes on the sink node and the node to be recommended;
specifically, the sampling process is: if the random walk from node u reaches node v through 1 step, the following formula is used forAnd updating.
The update formula is: />
Wherein v is any node in the graph structure, and the random walk is a neighbor node which randomly goes to the current node with equal probability.
S32, executing an updating process for each column of the attribute matrix, combining the sampling process and the updating process result, and obtaining attribute information of each user for subsequent calculation.
In one embodiment of the present invention, the step S32 specifically includes:
s321, attribute matrix R of the certain layer 1(l) Judging whether the numerical value of each item (u, f) in the column meets a first preset condition one by one, and if so, using a first updating formula to transfer the probability numerical value of the attribute of the current node uUpdate and clear->Is used to update the attribute value +.>And updating.
The first preset condition is:
the first update formula is:
the second updated formula is:
wherein,,for the attribute transition probability of the current node u at the current layer 1, the initial value is 0, ++>For the attribute value of the current node u at the current layer l, user information is initially taken as +.>Representing the attribute transfer probability of the updated node v in the 1+1 layer, wherein θ is an error parameter determined by a user according to actual conditions, d (u) is the number of neighbors of the node u, and if the numerical values of all the items (u, f) do not meet the first preset condition, ending the updating process;
s322, after the updating process is finished, combining the sampling process and the updating process by using a third updating formula;
the third updated formula is:
wherein gamma isl The weight parameters determined by the user according to the actual conditions are satisfiedAn estimate of the L-layer attribute transition probability P.
In a word, the social network friend recommendation method based on the graph neural network can obtain the attribute transfer probability of the user under the sub-linear time complexity through combining the sampling process and the updating process, gets rid of the dependence relationship between the transfer probability calculation time and the social network consistency, and improves the efficiency of social user relevance assessment, thereby improving the friend recommendation speed.
It will be appreciated by those skilled in the art that embodiments of the present application may be provided as a method, system, or computer program product. Accordingly, the present application may take the form of an entirely hardware embodiment, an entirely software embodiment, or an embodiment combining software and hardware aspects. Furthermore, the present application may take the form of a computer program product embodied on one or more computer-usable storage media (including, but not limited to, disk storage, CD-ROM, optical storage, and the like) having computer-usable program code embodied therein.
The present application is described with reference to flowchart illustrations and/or block diagrams of methods, apparatus (systems) and computer program products according to embodiments of the application. It will be understood that each flow and/or block of the flowchart illustrations and/or block diagrams, and combinations of flows and/or blocks in the flowchart illustrations and/or block diagrams, can be implemented by computer program instructions. These computer program instructions may be provided to a processor of a general purpose computer, special purpose computer, embedded processor, or other programmable data processing apparatus to produce a machine, such that the instructions, which execute via the processor of the computer or other programmable data processing apparatus, create means for implementing the functions specified in the flowchart flow or flows and/or block diagram block or blocks.
These computer program instructions may also be stored in a computer-readable memory that can direct a computer or other programmable data processing apparatus to function in a particular manner, such that the instructions stored in the computer-readable memory produce an article of manufacture including instruction means which implement the function specified in the flowchart flow or flows and/or block diagram block or blocks.
These computer program instructions may also be loaded onto a computer or other programmable data processing apparatus to cause a series of operational steps to be performed on the computer or other programmable apparatus to produce a computer implemented process such that the instructions which execute on the computer or other programmable apparatus provide steps for implementing the functions specified in the flowchart flow or flows and/or block diagram block or blocks.
The foregoing descriptions of specific exemplary embodiments of the present invention are presented for purposes of illustration and description. It is not intended to limit the invention to the precise form disclosed, and obviously many modifications and variations are possible in light of the above teaching. The exemplary embodiments were chosen and described in order to explain the specific principles of the invention and its practical application to thereby enable one skilled in the art to make and utilize the invention in various exemplary embodiments and with various modifications as are suited to the particular use contemplated. It is intended that the scope of the invention be defined by the claims and their equivalents.