CN119415744B

CN119415744B - Graph similarity searching method based on sub-graph matching

Info

Publication number: CN119415744B
Application number: CN202411558282.7A
Authority: CN
Inventors: 刘峥; 庄微风
Original assignee: Nanjing University of Posts and Telecommunications
Current assignee: Nanjing University of Posts and Telecommunications
Priority date: 2024-11-04
Filing date: 2024-11-04
Publication date: 2025-11-28
Anticipated expiration: 2044-11-04
Also published as: CN119415744A

Abstract

This invention discloses a graph similarity search method based on subgraph matching. The method divides the data graph into several mutually exclusive half-graphs. An inverted index is constructed using the subgraph embedding as the key and the data graph set containing the subgraph as the value. A coordinate index is constructed based on the size information of the data graph. Hierarchical filtering is achieved using the mapping relationship between the two indices. Self-loop or acyclic strategies are used to process the half-graphs. An ordered embedding model is designed so that the embeddings of two graphs with subgraph isomorphism have the same partial order position in the high-dimensional space. The input query graph is filtered through the coordinate index to obtain a preliminary candidate set, which is then further filtered through the inverted index. The graph edit distance between the query graph and the candidate graphs is accurately calculated to obtain the final result set. This method not only avoids traditional subgraph isomorphism testing but also generates subgraph embeddings offline, significantly shortening the model's inference time.

Description

Graph similarity searching method based on sub-graph matching

Technical Field

The invention belongs to the field of graph data application, and particularly relates to a graph similarity searching method based on neural subgraph matching.

Background

As a powerful data model, graphs have been successfully applied to many fields, which can describe not only the properties of a target object but also the structural relationships between respective components. As graph data is increasingly applied and databases become increasingly large in size, more and more research is trying to solve the similarity search problem in graph databases. The user only wants to acquire some graph data having a similar structure to a given query graph, and there may be some relatively small deviation, and a search that allows a difference between the query graph and the given graph is a similarity search. The similarity search problem for a graph may be defined as finding all graphs in the graph dataset that have similarities to query graph Q within a threshold given the graph database g= { G1, G2,... This approximate search mechanism greatly reduces the difficulty of searching by the user with little or no prior knowledge. Therefore, when exploratory research is performed in a large-scale graph database, a flexible and efficient graph similarity searching method is particularly important. In recent years, researchers have proposed a large number of graph similarity search algorithms, and among them, a similarity search method using graph edit distances as metrics has received a great deal of attention because of its good fault tolerance and versatility.

CN202410923861.0 calculates the structural similarity characteristics of the graph pairs based on the diffusion model and the attention mechanism, performs comparison learning through a multi-layer matching network to obtain a superside-superside matching vector and a superside-superside matching vector, generates semantic similarity characteristics based on the superside-superside matching vector and the superside-superside matching vector, splices the structural similarity characteristics and the semantic similarity characteristics to obtain global comparison feature vectors of the graph pairs, and inputs the global comparison feature vectors into a fully-connected neural network to obtain similarity scores for reflecting the similarity degree of the graph pairs. The heterogeneous graph similarity learning method provided by the invention combines the semantic and structural features, fuses the similar features of the graph structure and the node and subordinate community features to learn semantic information, is more comprehensive in consideration, and can effectively and accurately obtain the similarity score of the graph pair.

The invention discloses a similar network subgraph searching method and device based on semantic distance, a storage medium and a terminal, wherein the method comprises the steps of obtaining a reference network subgraph, obtaining set connection edges among all text units in the reference network subgraph based on preset screening conditions, connecting all text units in the reference network subgraph into a searching subgraph based on all set connection edges, obtaining a searching text unit set of target text units in an inference database in the searching subgraph, obtaining a searching text unit set of all text units in the searching subgraph in the inference database along a preset searching sequence in a preset searching set obtaining mode, and obtaining all similar network subgraphs of the reference network subgraph based on the searching text unit set of all text units in the reference network subgraph. However, when the graph similarity calculation method of the simple dependence neural network model is used for graph searching, all results cannot be found, and the graph searching speed is slower than that of the traditional indexing method.

Disclosure of Invention

Aiming at the defects of the prior art, the invention provides a graph node sequence embedding model based on the graph similarity searching method of nerve subgraph matching, which is used for judging whether subgraph isomorphism exists between a query graph and a partition by the phase position of the query graph and the sequence embedded in a high-dimensional space generated by the partition, thereby not only avoiding the traditional subgraph isomorphism test, but also generating partition embedding in an off-line stage, realizing quick judgment of isomorphism only by comparing the relative positions of the query graph and each partition embedded in the high-dimensional space during query, and greatly shortening the deducing time of the model.

The method for searching the graph similarity based on the neural subgraph matching comprises the following specific steps:

S1, dividing a data graph into a plurality of mutually exclusive half graphs, embedding a sub graph as a key, constructing an inverted index by taking a data graph set containing the sub graph as a value, constructing a coordinate index based on the size information of the data graph, and realizing hierarchical filtering by utilizing the mapping relation between the two layers of indexes.

S2, processing half by adopting a self-loop or loop-free strategy, and designing a sequential embedding model so that the embedding of two graphs with sub-graph isomorphic relations also has the same partial sequence position in a high-dimensional space.

And S3, inputting a query graph, screening a preliminary candidate set through a coordinate index, further screening the candidate set through an inverted index, accurately calculating the graph editing distance between the query graph and the candidate graph, and obtaining a final result set.

The specific steps of S1 include:

S11, mapping any data graph g into a two-dimensional coordinate system in a coordinate (|V _g|,|E_g |), namely a vertex-side based mode, wherein an x coordinate and a y coordinate respectively represent the number of the vertices and the number of the sides of the graph g.

For graph database G, a set of points (|v _g|,|E_g |) G e G can be obtained, and these points can form a rectangular area a= [ x _min,x_max]×[y_min,y_max ], where x _min/x_max and y _min/y_max are the minimum and maximum numbers of nodes and edges, respectively. Given a query graph q and a threshold T, a query rectangle Aq is defined as a rectangle composed of a set of points (x, y): x-V _q||+|y-|E_q |tau;

s13, giving a graph g which is divided into (tau+k) half graphs, wherein tau is a threshold value and k (k is equal to or larger than 1) is an integer parameter, and the set of the half graphs is P (g). For a given query graph q, if GED (g, q). Ltoreq.τ, there are at least k half graphs in the half graph set P (g): P _i1,p_i2,...,p_ik ε P (g), satisfy For any data graph G e G, its sub-graph set is P (G) = { P ₁,p₂,...,p_τ+k }. If it isThen p _i is referred to as the matching subgraph, otherwise it is referred to as the unmatched subgraph. If the number of matching subgraphs in the subgraph set P is less than k, then the graph edit distance GED (g, q) must be greater than τ.

And S14, dividing all the data graphs, and constructing an inverted index I (p) taking a division sub-graph as a key, and taking a data graph set containing the sub-graph as a value. For a given query graph q, ifAll data graphs containing partitions p can be quickly found in graph database G.

The specific steps of S2 include:

And S21, connecting the far ends and the near end nodes of all the halves in the half graph, reforming the halves into self-loops, and in the process of message transmission, not transmitting the message to the nodes connected by the self-loops reformed by the halves, and only embedding the degree information of the halves.

And S22, processing the node characteristics through linear transformation to obtain hidden layer representation. The model employs k layers of graph volumes to aggregate local neighborhood information and iteratively update node representations.

And S23, adding leachable jump connections between different convolution layers, wherein the connections are represented by a parameter matrix S epsilon R ^L×L, and L is the network layer number. During the training process, the parameter matrix is used to determine the optimal contribution of each layer of output to the final node representation.

S24, after the k-layer convolution, the node representations are aggregated by a global pooling operation to generate a fixed-size graph insert.

S25 given a target graph instance G _T＝(V_T,E_T) and a query graph instance G _Q＝(V_Q,E_Q), where V _T is the target graph node set, E _T is the target graph edge set, V _Q is the query graph node set, and E _Q is the query graph edge set. The level embedding Z _Q of level embedding Z _T,G_Q of G _T can be obtained by a sequential embedding model, and if G _Q is a isomorphic subgraph of G _T, then the position of Z _Q in the embedding space should be in the "lower left corner" of Z _T according to the sequential embedding theory.

S26, training and generating an embedded GNN model by using the maximum marginal loss.

The specific steps of S3 include:

s31, given a query graph q and a query threshold tau, calculating a query region, and taking the divided subgraphs corresponding to all graphs in the query region as the subgraphs to be searched of the inverted index through the mapping relation between the divided subgraphs and the data graph.

And S32, before the inverted index is queried, firstly creating a score array S for recording the number of matched partitions existing between the current query graph and each data graph. And inputting the query graph into a neural subgraph matching model to obtain query graph embedding, and for each to-be-searched partition, sequentially comparing the position relation of the query graph embedding and the partition embedding in an embedding space, wherein if Z (p) is less than or equal to Z (q), p is an isomorphic subgraph of the query graph q, the score S [ g ] +1 of all the data graphs comprising the partition is the candidate set when the score in the score group S is greater than or equal to k until all the to-be-searched partitions are completely compared.

And S33, verifying the candidate set by using an accurate GED verification algorithm to obtain a final query result.

Compared with the prior art, the method has the advantages that on all data sets, the similarity search is performed by using the method without losing any real result, and compared with other learning-based methods, the accuracy is greatly improved. Secondly, in order to improve the efficiency of searching the similar graphs, an index mapping strategy is designed, a quick index is generated by using the statistical information of the data graphs, and the hierarchical filtering of the similar graphs is realized by maintaining the mapping relation between the quick index and the partition index.

Drawings

FIG. 1 is a flow chart of the present invention.

Detailed Description

The present invention is further illustrated in the following drawings and detailed description, which are to be understood as being merely illustrative of the invention and not limiting the scope of the invention.

In the embodiment, as shown in fig. 1, in the real graph database, the information and the scale of the graphs often have large differences, and the graph pairs with small differences in similarity aiming at the graph similarity query problem exist, so that a large number of false positive samples which are easy to distinguish exist in the database. Therefore, a label index based on graph statistical information is established, and hierarchical filtering is realized by using the mapping relation between the two layers of indexes. For any data graph g, it is mapped in a two-dimensional coordinate system in coordinates (|vg|, |eg|), that is, in a vertex-side based manner, where x-and y-coordinates represent the number of vertices and the number of sides of the graph g, respectively. Thus, for graph database G, a set of points (|V _g|,|E_g |) G ε G can be obtained, and these points can make up a rectangular area A= [ x _min,x_max]×[y_min,y_max ], where x _min/x_max and y _min/y_max are the minimum and maximum numbers of nodes and edges, respectively. Given a query graph q and a threshold τ, a query rectangle A _q is defined as a rectangle consisting of a set of points (x, y): x- |V _q||+|y-|E_q ||τ.

The coordinate mapping is focused on the size of the graph, and a boundary condition is considered, so that the undesirable graphs are eliminated from the graph scale, and the method is a coarse-granularity filtering means to reduce the time cost of subsequent fine filtering. Therefore, after the coarse granularity filtering of the coordinate mapping layer, the number of data graphs which need to participate in the fine granularity filtering of the subsequent multiple graph division is obviously reduced, and the index construction time of the subsequent fine granularity filtering method can be obviously shortened.

S13. theorem 1 given a graph g, the graph is divided into (τ+k) half-graphs, the set of half-graphs is P (g), where T is a threshold value and k (k≥1) is an integer parameter. For a given query graph q, if GED (g, q). Ltoreq.τ, there are at least k half graphs in the half graph set P (g): P _i1,p_i2,...,p_ik ε P (g), satisfyFor any data graph G e G, its partition set is P (G) = { P ₁,p₂,...,p_τ+k }. If it isThen p _i is referred to as the matching partition, otherwise it is referred to as the unmatched partition.

S14, if the number of matched partitions in the partition set P is smaller than k according to theorem 1, the graph editing distance GED (g, q) is necessarily larger than tau, so that g can be judged to be a false positive graph, and the time cost is greatly saved by adopting the deducing mode. An inverted index I (p) is constructed from a partition p of graph g. For a given query graph qAll data graphs containing partitions p can be quickly found in graph database G. Thus, after the necessary half sub-graph isomorphism calculation of the partition p is performed, all the data graphs containing the partition p can be found through the inverted index, so that a large amount of calculation is reduced. A random partitioning strategy is adopted, namely, nodes of (tau+k) seeds are randomly selected as a starting partition in the graph g, and then the partition is expanded in a region growing mode until all the nodes in the graph g are incorporated into the partition.

The graph partitioning strategy partitions each data graph into several mutually exclusive half graphs, which are different from the normal graph in that the existence of half is not directly encoded by GNN. For the processing of the half-edge graphs, the traditional isomorphism testing method generally adopts a mode of adding virtual nodes, adds a virtual node for each half-edge graph, connects the far ends of all the half-edges with the virtual node, and can be matched with any node. Then, when the sub-graph isomorphism test is performed, the half sides can be effectively matched.

However, in GNN, if a policy of joining virtual nodes is still adopted, distortion of original graph data may be caused. This is because GNN cannot identify virtual nodes as in the conventional algorithm, and cannot match any virtual node with any node, and it only treats it as a normal node, so that the structure and node information of the original half graph are changed, and thus, deviation and even erroneous information are learned.

A self-loop strategy is provided to realize lossless embedding of the half graph, and the far ends and the near ends of all half in the half graph are connected, so that the half becomes a self-loop, and virtual nodes are not needed to be introduced, and half can be described. However, in the message passing process of GNN, since the self-loop is equivalent to passing the message to itself, the effect of the current node information in the current node embedded representation is enhanced, which is not consistent with the real result. Therefore, in the process of message passing, we do not pass messages to the node connected by the self-ring formed by half reconstruction, so that only half degree information is included in the GNN, and for the node with the self-ring, the message passing update formula is as follows:

where N (v) represents the set of neighbor nodes of node v, σ is the activation function, W is the weight matrix, and b is the bias.

A SkipConGNN model was trained to implement sequential embedding. The model integrates leap connection which can be learned, so that the convolution operation of each layer not only depends on the output of the last layer, but also can directly use the output of all the previous layers. This mechanism is very important in deep neural networks, helping to alleviate the gradient vanishing problem and improve the performance of the model.

Specifically, the SkipConGNN model realizes a more flexible and expressive feature propagation mechanism by introducing a leachable jump connection, and can integrate information across multiple network layers. SKIPLASTGNN architecture can be divided into the following key components:

S22, the input layer is responsible for processing the initial node characteristics. Let node feature matrix be X ε R ^N×F, where N represents the number of nodes and F represents the feature dimension. Firstly, processing node characteristics through linear transformation to obtain hidden layer representation:

H⁽⁰⁾＝XW₀

Where W ₀∈R^F×H is the linearly transformed weight matrix and H is the hidden layer dimension. If feature preprocessing is enabled, additional preprocessing steps are applied to enhance the original input features. The model employs k layers of graph volumes to aggregate local neighborhood information and iteratively update node representations. Aggregation of node neighborhood information is achieved herein using a GRAPHSAGE convolution, the propagation rules of which can be expressed as:

where H ⁽¹⁾ is the node representation of the first layer, W _l is the weight matrix of the first layer, N (v) is the set of neighbor nodes of node v, and σ is the activation function.

S23 a leachable jump connection is added between the different convolutional layers SkipConGNN, which is represented by a parameter matrix S e R ^L×L, where L is the number of network layers. During the training process, the parameter matrix is used to determine the optimal contribution of each layer of output to the final node representation.

Assuming that H ⁽⁰⁾,H⁽¹⁾,...,H^(l) is a node representation of the previous l layers, the output of the jump connection is represented as:

Wherein S _l,i is a leap connection weight that can be learned. The introduction of a jump connection effectively alleviates the gradient vanishing problem, enabling the model to capture information from different network depths. σ is an activation function for scaling the weight of the jump connection to limit it to the (0, 1) range. The weight of such a jump connection will control the extent to which each input feature is affected in the current layer.

Z=Pool(H^(L))

Wherein H (^L) is a node representation of the final layer L, Z is a global representation of the graph, pool is a global pooling function, and different pooling modes can be selected according to specific requirements.

S25 given a target graph instance G _T＝(V_T,E_T) and a query graph instance G _Q＝(V_Q,E_Q), where V _T is the target graph node set, E _T is the target graph edge set, V _Q is the query graph node set, and E _Q is the query graph edge set. The level embedding Z _Q of level embedding Z _T,G_Q of G _T can be obtained by a sequential embedding model, and if G _Q is a isomorphic subgraph of G _T, then the position of Z _Q in the embedding space should be in the "lower left corner" of Z _T, according to the sequential embedding theory:

Where D is the embedding dimension. We can measure how well ZQ and Z _T satisfy order embedding theory with E (ZQ, Z _T),

S26-thus, the maximum marginal loss is used to train the generation of embedded GNNs:

Where P is the positive sample set, N is the negative sample set, and α is the hyper-parameter. When Z _Q[i]>Z_T [ i ] is in any dimension i, the sub-graph constraint is violated. E (Z _Q,Z_T) represents the amplitude thereof. For positive example P, E (Z _Q,Z_T) is minimized when all elements of the query node embedded in the ZQ are smaller than the corresponding elements of the target node embedded in Z _T. For the negative pair (Z _Q,Z_T), the amount of violation E (Z _Q,Z_T) should be at least α to obtain zero loss.

And S3, after all preparation works of constructing the index, sequentially embedding and mapping the index are completed, searching the similar map, firstly constructing the coordinate index based on the size information of the data map, secondly dividing the data map, inputting divided partitions into a nerve subgraph embedded model to obtain partition embedded representation, and finally constructing the inverted index by taking the embedded representation of the partition as a key and taking the ids of all the data maps comprising the partition as values, and simultaneously maintaining the mapping relation between the data map and the partitions divided by the map. When inquiring, firstly, calculating an inquiry area through an inquiry diagram q and an inquiry threshold tau, and taking the partitions corresponding to all diagrams in the inquiry area as the partitions to be checked of the inverted index through the mapping relation between the partitions and the data diagram. Secondly, before the inverted index is queried, a score array S is firstly created and is used for recording the number of matching partitions existing between the current query graph and each data graph. And inputting the query graph into a neural subgraph matching model to obtain query graph embedding, and for each partition to be searched, comparing the position relations of the query graph embedding and the partition embedding in an embedding space in sequence, wherein if Z (p) is less than or equal to Z (q), p is an isomorphic subgraph of the query graph q, and then the score Sg+1 of all the data graphs of the partition is included until all the partitions to be searched are completely compared. And according to theorem 1, the score in the score array S is greater than or equal to k and is the candidate set. And finally, verifying the candidate set by using an accurate GED verification algorithm to obtain a final query result.

It should be noted that the foregoing merely illustrates the technical idea of the present invention and is not intended to limit the scope of the present invention, and that a person skilled in the art may make several improvements and modifications without departing from the principles of the present invention, which fall within the scope of the claims of the present invention.

Claims

1. A graph similarity searching method based on sub graph matching is characterized by comprising the following steps,

S1, dividing a data graph into a plurality of mutually exclusive half graphs, embedding a sub graph as a key, constructing an inverted index by taking a data graph set containing the sub graph as a value, constructing a coordinate index based on size information of the data graph, and realizing hierarchical filtering by utilizing a mapping relation between two layers of indexes;

s2, processing half by adopting a self-loop or loop-free strategy, and designing a sequential embedding model so that two graphs with sub-graph isomorphic relations are embedded in a high-dimensional space to have the same partial sequence position;

The step S2 comprises the following steps:

S21, connecting far ends and near end nodes of all halves in the half graph, reforming the halves into self-loops, and in the process of message transmission, not transmitting the message to the nodes connected by the self-loops reformed by the halves, and only embedding the degree information of the halves;

s22, processing node characteristics through linear transformation to obtain hidden layer representation, wherein a model adopts The graph volume layer is used for aggregating local neighborhood information and iteratively updating node representations;

s23, adding leachable jump connections between different convolution layers, wherein the connections are composed of a parameter matrix Representation of whereinFor the network layer number, in the training process, the parameter matrix is used for determining the optimal contribution of each layer of output to the final node representation;

s24, after passing through After the layer convolution, the node representations are aggregated by a global pooling operation to generate a fixed-size graph insert;

s25, giving a target graph example And query graph instanceWhereinIs a set of nodes of the target graph,Is the set of target graph edges,Is a set of nodes of a query graph,Is a query graph edge set, obtained by sequentially embedding modelsIs embedded at the level of the graph,Is embedded at the level of the graphAnd if (Is thatIsomorphic subgraphs of (c), according to the order embedding theory,In the embedding spaceLower left corner of (2);

s26, training and generating an embedded GNN model by using the maximum marginal loss;

S3, inputting a query graph, screening a preliminary candidate set through a coordinate index, further screening the candidate set through an inverted index, accurately calculating a graph editing distance between the query graph and the candidate graph, and obtaining a final result set;

the step S3 comprises the following steps:

S31, given query graph And query thresholdCalculating a query area, and taking the divided subgraphs corresponding to all the graphs in the query area as the subgraphs to be searched of the inverted index through the mapping relation between the divided subgraphs and the data graph;

S32, before inquiring the reverse index, firstly creating a score array For recording the number of matching sub-graphs existing between the current query graph and each data graph, inputting the query graph into the sub-graph matching model to obtain query graph embedding, and for each sub-graph to be queried, comparing the position relationship of the query graph embedding and the sub-graph embedding in the embedding space in turn, ifThenIs a query graphIs a isomorphic sub-graph containing scores for all data graphs of the sub-graphUntil all the sub-graphs to be checked are compared completely, the score groupThe medium fraction is greater than or equal toIs the candidate set;

2. The graph similarity search method based on sub-graph matching according to claim 1, wherein the step 1 comprises the steps of,

S11, for any data graph g, the data graph g is coordinated with the data graph gThat is, based on the vertex-side mode, mapping in a two-dimensional coordinate system, wherein x-coordinate and y-coordinate represent the number of vertices and the number of sides of the graph g respectively;

S12, for the graph database G, obtaining a point set While the points form a rectangular areaWhereinAndGiven a query graph q and a threshold τ, a query rectangle Aq is defined as defined by the set of pointsA rectangular shape;

S13, giving a graph g which is divided into Half graphs, the set of half graphs is P (g), whereinFor threshold value, k (k≥1) is an integer parameter, for a given query graph q, ifAt least k half graphs exist in the half graph set P (g): pil ⊆ q (1≤l≤k) is satisfied for any data graph Its subgraph set is P (g) = { P1, P2,..and P tau + k }, if pi ⊆ q, pi is called a matching subgraph, otherwise it is called a non-matching subgraph, if the subgraph setThe number of matching subgraphs in (c) is less than k, graph edit distanceNecessarily greater than;

S14, dividing all the data graphs, constructing an inverted index I (p) with the divided sub-graph as a key and the data graph set containing the sub-graph as a value, and for a given query graphIf (3)In a graph databaseMid-fast find containing partitionsIs a data map of the data set.

3. The graph similarity search method based on sub-graph matching according to claim 1, wherein, in step S21, for the node having the self-loop, the message passing update formula is as follows,

,

Wherein, the Representing nodesIs defined by a set of neighboring nodes of the network,Is the function of the activation and,Is a matrix of weights that are to be used,Is offset.

4. The graph similarity search method based on sub-graph matching of claim 1, wherein the architecture of the GNN model includes components,

The input layer is responsible for processing initial node characteristics and takes a node characteristic matrix asWhereinRepresenting the number of nodes to be connected,Representing feature dimensions, first, processing node features through linear transformation to obtain hidden layer representation:

,

Wherein, the The model adopts k graph convolution layers to aggregate local neighborhood information and iteratively update node representation, and uses GRAPHSAGE convolution to realize the aggregation of the node neighborhood information, wherein the propagation rule is expressed as follows:

,

Wherein, the Is the firstThe node representation of the layer is such that,Is the firstThe weight matrix of the layer is used to determine,Is a nodeIs defined by a set of neighboring nodes of the network,Is an activation function.

5. The graph similarity search method according to claim 1, wherein in step S23, leachable jump connections are added between the different convolution layers of SkipConGNN, and these connections are made by a parameter matrixRepresentation of whereinFor the number of network layers, the parameter matrix is used to determine the optimal contribution of each layer output to the final node representation during the training process,

Assume thatIs the front partThe nodes of the layer represent the output of the jump connection is represented as:

,

Wherein, the Is a leap connection weight that can be learned, allowing the model to capture information from different network depths,Is an activation function for scaling the weight of the jump connection in order to limit it to the (0, 1) range.

6. The graph similarity search method based on sub-graph matching according to claim 1, wherein in step S24, the graph similarity search method is performed afterAfter the layer convolution, the node representations are aggregated by a global pooling operation to generate a fixed-size graph insert,

,

Wherein, the Is the final layerZ is the global representation of the graph and Pool is the global pooling function.

7. The graph similarity search method based on sub-graph matching according to claim 1, wherein, in step S25, according to the order embedding theory,In the embedding spaceLower left corner of (2), i.e.:

,

Wherein D is the embedding dimension, using To measureAndThe degree of the order-embedding theory is satisfied,

。

8. The graph similarity search method based on sub-graph matching according to claim 1, characterized in that in step S26, the maximum margin loss is used to train the generation of embedded GNNs:

,

Wherein, the Is a set of positive samples that are,Is a set of negative examples of the type,Is a superparameter when in any dimensionIn the process, the When the sub-graph constraint is violated,Representing the amplitude thereof, for the positive exampleWhen the query node is embeddedAll elements in (a) are smaller than the target node embeddingIn the case of the corresponding element of the group,Is minimized for negative pairs ofAmount of violationShould be at leastTo obtain zero loss.