CN117875374A - Graph representation learning method and device based on generation of countermeasure network - Google Patents

Abstract

An unsupervised graph representation learning method and device based on a generated countermeasure network, wherein the method comprises the following steps: in the pre-embedding generation stage, compressing the characteristics of the original data by using an LLE dimension reduction method, and recording the dimension reduced result as a pre-embedding; generating a countermeasure phase; generating an antagonism network model, in particular an embedded representation of the learning node; the generated countermeasure network consists of a generator and a discriminator, wherein each node embedding layer is arranged in the generator and the discriminator, and the embedding representation of the optimized node of the other party is pushed to each other based on the idea of countermeasure learning; executing the generation countermeasure phase for a plurality of times until the generation countermeasure model converges; at this time, node embedding layers Z≡G and Z≡D in the model are the embedding representation matrix of the finally learned graph nodes. The method and the device effectively remove redundant information and effectively optimize the GAN model.

Description

A graph representation learning method and device based on generative adversarial network

Technical Field

The present invention relates to a representation learning method and device for graph structure data.

Background technique

There are all kinds of intricate relationships in the real world, which constitute many huge relationship graphs. In order to better discover valuable information from these graph-structured data, graph representation learning methods are often used in the field of machine learning. This type of method converts the data that constitutes the node information in the graph into a low-dimensional vector form, called an embedding representation, which is then applied to downstream tasks such as node classification, link prediction, and recommendation. This type of method is also called graph embedding, network representation learning, and network embedding method.

Graph representation learning methods can be roughly divided into supervised graph representation learning and unsupervised graph representation learning according to the different learning processes. The most advanced graph representation learning methods usually adopt supervised models based on graph neural networks, or unsupervised models based on random walks or autoencoders. Supervised models require a large amount of reliable label information in the data; unsupervised models do not have strict requirements on the data set, but the accuracy of the information expressed by the learned embedded representation is lower than that of the supervised model.

In the real world, it is extremely difficult to obtain enough reliable labeled data for large-scale data sets, so using an unsupervised model to implement graph representation learning is a more ideal solution. Existing unsupervised methods have achieved some results, but they still lag behind supervised methods in terms of the accuracy of embedded representations, which limits their application in practical application scenarios that lack labels, such as life safety, risk prediction and other important fields. Therefore, it is of great practical significance to develop a new unsupervised graph representation learning method that can accurately express the embedded representation of information.

Summary of the invention

In order to overcome the problem that the accuracy of the expression information of the embedded representation obtained by the existing unsupervised graph representation learning method is low, the present invention provides an unsupervised graph representation learning method and device based on a generative adversarial network.

The present invention utilizes graph structure, converts original data into low-dimensional pre-embedding through LLE (local linear embedding) method, and uses generative adversarial model to learn and optimize embedded representation, thereby realizing graph representation learning.

The unsupervised graph representation learning method based on generative adversarial networks is divided into a pre-embedding generation phase and a generative adversarial phase. The specific steps are as follows:

Step 1: Pre-embedding generation stage: Use the LLE dimension reduction method to compress the features of the original data and record the result after dimension reduction as pre-embedding;

1.1 Original feature matrix of initial graph nodes Use the KNN algorithm to find the K nearest neighbors of each node sample, reconstruct the node through the K neighbor nodes of each node, calculate the weight A _ij , and the reconstruction error is shown in formula (1):

Where N represents the number of nodes, _d0 represents the dimension of the original feature vector, and the weight _Aij represents the contribution of the jth data point to the i-th reconstruction. In order to calculate the weight, it is necessary to minimize the cost function under two constraints: first, each node vector _xi can only be reconstructed through neighboring nodes, and if node j is not in the neighbor set, _Aij = 0; second, the sum of the rows of the weight matrix is one, that _{is, ∑jAij =} 1.

1.2 The optimal reconstruction weight matrix A obtained by formula (1) is used to calculate the embedding matrix after dimensionality reduction And satisfying d＜＜d ₀ , the embedding loss is shown in formula (2):

During the training process, the weight matrix A remains unchanged, and the embedding matrix result is obtained through formula (2).

Step 2: Generative adversarial phase: Through a generative adversarial network model, the embedded representation of the node is specifically learned; the generative adversarial network consists of two parts: the generator and the discriminator. Each of them has a node embedding layer. Based on the idea of adversarial learning, they push each other to optimize the embedded representation of the node;

2.1 Before training begins, initialize the generator and discriminator, and use the pre-embedding matrix obtained in the previous step as the initial value of their respective node embedding layers;

2.2 Node pair sampling: Starting from node i, based on the adjacency weight A random walk can get a path Path _i ; where the adjacency weight of node i/> is an N-dimensional vector, where N represents the number of nodes; /> Component in the jth dimension/> The calculation formula is shown in formula (3) (4):

in, represents the set of neighbor nodes of node i,/> represents the embedding representation of node i in the generator G, Z ^G represents the node embedding layer in the generator G;

Path _i is the set of all nodes that are passed through when randomly walking with node i as the starting node; for small-scale data sets, when the next node of the walk already exists in Path _i , the walk stops; for large-scale data sets, the walk stops when a certain number of steps are reached;

is a set of node pairs about node i used for generator training. Each pair of adjacent nodes in Path _i constitutes a node pair. is a node pair set about node i for discriminator training. The head and tail nodes in Path _i form a node pair and are added/> By performing multiple random walks starting from node i, /> and/> Get a sufficient number of node pairs for subsequent training steps;

2.3 Discriminator training: Use the Adam algorithm to minimize the discriminator loss function _LD and optimize the node embedding layer ^ZD of the discriminator D. The discriminator objective function calculation formula is shown in formula (5):

in, represents the embedding representation of node i in the discriminator D, <h, t> represents the node pair consisting of the head node h and the tail node t, and norm is the normalization function;

2.4 Generator training; Use the Adam algorithm to minimize the discriminator loss function L _G and optimize the node embedding layer Z ^G of the generator G; The generator objective function calculation formula is shown in formula (6):

Step 3: Execute the generative adversarial phase multiple times until the generative adversarial model converges; at this point, the node embedding layers Z ^G and Z ^D in the model are the embedding representation matrices of the final learned graph nodes.

The second aspect of the present invention relates to an unsupervised graph representation learning device based on a generative adversarial network, comprising a memory and one or more processors, wherein the memory stores executable code, and when the one or more processors execute the executable code, they are used to implement the unsupervised graph representation learning method based on a generative adversarial network of the present invention.

The third aspect of the present invention relates to a computer-readable storage medium having a program stored thereon, which, when executed by a processor, implements the unsupervised graph representation learning method based on a generative adversarial network of the present invention.

The present invention combines the above technologies to propose an unsupervised graph representation learning method based on a generative adversarial network; in order to solve the problem that the embedding representation obtained by the existing unsupervised graph representation learning method has low accuracy in expressing information, a generator for obtaining node positive and negative sample pairs based on neighbor weighted random walks and a discriminator structure responsible for distinguishing whether there is a real connection between node pairs are used to automatically learn and optimize node embedding in an adversarial manner; in addition, in order to solve the problem that pre-embedding has a large impact on the training of the generative adversarial model, the LLE dimensionality reduction technology is used to obtain high-quality pre-embedding.

The advantages of the present invention are: (1) LLE dimensionality reduction produces high-quality pre-embeddings, ensuring effective optimization of the GAN model. (2) The generative adversarial model selects the existence of a node pair connection as the adversarial point, and uses random walk sampling instead of the strategy of randomly generating node embeddings to effectively remove redundant information. (3) As an unsupervised graph representation learning method, there are no strict requirements for the data set, and the learned embedding representation is equal to or even exceeds the supervised learning method in terms of information expression accuracy.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is an overall flow chart of the method of the present invention.

FIG. 2 is a diagram specifically illustrating the method of the present invention.

Detailed ways

The specific implementation of the present invention is described below with reference to embodiments.

Example 1

This embodiment relates to a document classification and document recommendation method using the unsupervised graph representation learning method based on a generative adversarial network of the present invention.

Suppose we perform graph representation learning on the Citeseer citation dataset. This dataset has 3327 nodes and 4552 edges, and the feature dimension of each node is 3703 dimensions.

The graph representation learning method based on generative adversarial network is used to learn the graph representation of Citeseer dataset. The steps are as follows:

1Get pre-embedded;

1.1 For the original feature matrix X with the initial graph node dimension of 3327×3703, the KNN algorithm is used to find the 12 nearest neighbors of each node sample, and the node is reconstructed through the 12 neighbor nodes of each node. The weight matrix A for the optimal reconstruction is calculated, and the dimension of the weight matrix A is 3327×3327.

1.2 Fix the optimal reconstruction weight matrix A obtained in 1.1 and use formula (2) to calculate the embedding matrix Z with a dimension of 3327×64 after dimensionality reduction.

2. Adversarial training;

2.1 Initialize the Generative Adversarial Network.

(1) Initialize the generator embedding matrix Z ^G with a dimension of 3327 × 64 and an initial value equal to the value of the pre-embedding matrix in the previous step.

(2) Initialize the discriminator embedding matrix Z ^D with a dimension of 3327 × 64 and the initial value is the value of the pre-embedding matrix in the previous step.

2.2 Obtain training samples.

2.3 Calculate the discriminator loss function _LD from the node pair set Sample ^D and the embedding matrix ^ZD .

2.4 Use the Adam algorithm to minimize the discriminator loss function _LD and optimize the discriminator embedding matrix ^ZD .

2.5 Calculate the generator loss function _LG from the node pair set ^SampleG , the embedding matrix ^ZD and the embedding matrix ^ZG .

2.6 Use the Adam algorithm to minimize the generator loss function _LG and optimize the generator embedding matrix ^ZG .

3. Repeat the training to obtain the node embedding representation;

3.1 Take steps 2.2 to 2.6 as a complete iteration process, and repeat the iteration until 200 iterations or the values of the loss functions _LG and _LD are no longer significantly reduced. The changes in the internal embedding matrix of the model during the entire iteration process are shown in Figure 2.

3.2 The embedding representation matrices Z ^D and Z ^G of size 3327×64 are the 64-dimensional embedding representation results of the Citeseer dataset nodes.

4 Input the newly added document features into the model to achieve document subject classification and related document recommendation;

When a newly published document is added to the citation database, the newly constructed graph network is input into the trained model to obtain the embedding results of the document nodes. The subject classification of the documents is carried out using the node embedding similarity between the documents, and high-quality related document recommendations are provided to researchers to help them discover the latest research results in the target field.

This concludes the specific implementation steps of graph representation learning for the Citeseer dataset using the iterative aggregation graph representation learning method based on generative adversarial networks.

Example 2

This embodiment relates to an unsupervised graph representation learning device based on a generative adversarial network, including a memory and one or more processors, wherein the memory stores executable code, and when the one or more processors execute the executable code, they are used to implement the method of Example 1.

Example 3

This embodiment relates to a computer-readable storage medium on which a program is stored. When the program is executed by a processor, the method of Embodiment 1 is implemented.

The contents described in the embodiments of this specification are merely an enumeration of the implementation forms of the inventive concept. The protection scope of the present invention should not be regarded as limited to the specific forms described in the embodiments. The protection scope of the present invention also extends to equivalent technical means that can be conceived by those skilled in the art based on the inventive concept.

Claims (3)

1. An unsupervised graph representation learning method based on generation of an countermeasure network comprises the following steps:

step 1: a pre-embedding generation stage; compressing the characteristics of the original data by using an LLE dimension reduction method, and recording the dimension reduction result as pre-embedding;

1.1 original feature matrix for initial graph nodeK nearest neighbors of each node sample are found by using KNN algorithm, and the K nearest neighbors of each node are reconstructedThe node calculates the weight A _ij The reconstruction error is shown in formula (1):

where N represents the number of nodes, d ₀ Representing the dimension, weight A, of the original feature vector _ij Representing the contribution of the jth data point to the ith reconstruction; to calculate the weights, it is necessary to minimize the cost function under two constraints: first, each node vector x _i Can only be reconstructed by neighbor nodes, if node j is not in neighbor set A _ij =0; second, the sum of the rows of the weight matrix is one, Σ _j A _ij ＝1；

1.2 the optimal reconstruction weight matrix A obtained by the formula (1) is used for calculating the embedded matrix after dimension reductionAnd satisfy d < d ₀ The embedding loss is shown in formula (2):

the weight matrix A is fixed in the training process, and an embedded matrix result is obtained through a formula (2);

step 2: generating a countermeasure phase; generating an antagonism network model, in particular an embedded representation of the learning node; the generated countermeasure network consists of a generator and a discriminator, wherein each node embedding layer is arranged in the generator and the discriminator, and the embedding representation of the optimized node of the other party is pushed to each other based on the idea of countermeasure learning;

2.1, before training starts, initializing a generator and a discriminator, and taking the pre-embedded matrix obtained in the previous step as an initial value of each node embedded layer;

2.2 node pair sampling; starting from node i, by being based on adjacency weightsCan obtain a Path _i The method comprises the steps of carrying out a first treatment on the surface of the Wherein the adjacency weight of node i +.>Is an N-dimensional vector, N representing the number of nodes; />Component in the j-th dimension->The calculation formula of (2) is shown as formula (3) (4):

wherein,a set of neighbor nodes representing node i, +.>Representing the embedded representation of node i in generator G,Z ^G representing node embedded layers in generator G;

Path _i the method is a set of all nodes which pass by when the node i is used as a starting node to randomly walk; for small-scale data sets, path already exists when the next node to be walked _i Stopping wandering during the middle period; for large-scale data sets, at the walkStopping when a certain number of steps is reached;

is a set of node pairs for generator training with respect to node i, path _i Each pair of adjacent nodes in (a) constitutes a node pair add +.> Is a set of node pairs for discriminator training with respect to node i, path _i The head and tail nodes in the tree form a node pair to add +.>By taking multiple random walks from node i,and->Obtaining a sufficient number of node pairs for subsequent step training;

2.3 training the discriminator; minimizing discriminator loss function L using Adam algorithm _D Optimizing node embedding layer Z of discriminator D ^D The method comprises the steps of carrying out a first treatment on the surface of the The discriminator objective function calculation formula is shown as formula (5):

wherein,representing the embedded representation of node i in discriminator D,<h,t>a node pair consisting of a head node h and a tail node t is represented,norm is a normalization function;

2.4 generator training; minimizing discriminator loss function L using Adam algorithm _G Node embedding layer Z of optimization generator G ^G The method comprises the steps of carrying out a first treatment on the surface of the The generator objective function calculation formula is shown as formula (6):

step 3: executing the generation countermeasure phase for a plurality of times until the generation countermeasure model converges; at this time, the node in the model embeds layer Z ^G And Z ^D I.e. the embedded representation matrix of the final learned graph node.

2. An unsupervised graph representation learning apparatus based on a generated countermeasure network, comprising a memory and one or more processors, wherein the memory stores executable code, and the one or more processors are configured to implement the unsupervised graph representation learning method based on the generated countermeasure network of claim 1 when executing the executable code.

3. A computer-readable storage medium, having stored thereon a program which, when executed by a processor, implements the unsupervised graph representation learning method based on generating an countermeasure network of claim 1.