CN-122019536-A - Graph query method and device

CN122019536ACN 122019536 ACN122019536 ACN 122019536ACN-122019536-A

Abstract

The embodiment of the specification provides a graph query method and device, the method comprises the steps of obtaining a plurality of query requests of a user for target graphs, wherein the query requests comprise a plurality of query graphs, the target graphs and nodes in each query graph are configured with node attributes, executing a plurality of rounds of label generation by taking the node attributes as initial label values, and each round of label generation comprises the steps of obtaining a label structure combination formed by the current label value of the node and the current label value of a neighbor node of the node in each query graph, constructing a mapping relation between each label structure combination and a current round of label value, adding the current round of label value for each node in each query graph according to the mapping relation, and adding the corresponding current round of label value for the nodes conforming to the label structure combination according to the mapping relation for the target graphs.

Inventors

ZHOU QIANG
HONG CHUNTAO
ZHENG WEIGUO
ZHANG ZHIJIE

Assignees

支付宝(杭州)数字服务技术有限公司

Dates

Publication Date: 20260512
Application Date: 20260116

Claims (10)

1. A graph query method, comprising: acquiring a plurality of query requests of a user for a target graph, wherein the query requests comprise a plurality of query graphs, and node attributes are configured for each node in the target graph and each query graph; Executing a plurality of rounds of label generation by taking node attributes as initial label values, wherein each round of label generation comprises the steps of acquiring a label structure combination formed by the current label value of each node and the current label value of a neighbor node of each node in the plurality of query graphs, constructing a mapping relation between each label structure combination and the label value of the round, and adding the label value of the round for each node in each query graph according to the mapping relation; and matching query nodes based on the label values of all the nodes in the target graph to obtain a first query result, wherein the query nodes are from the query graph added with labels.
2. The method of claim 1, wherein each round of label generation further comprises culling nodes that do not fit any label structure combination therein for the target graph.
3. The method of claim 1, wherein the label structure combination indicates a current label value of the node, a current label value of a neighbor node of the node, and an adjacency relationship between the current label value of the node and the current label value of the neighbor node of the node.
4. The method of claim 1, further comprising, prior to performing the matching of the query nodes: Determining a first public subgraph of the plurality of query graphs based on label values of nodes in the plurality of query graphs; the query node is from the first public sub-graph.
5. The method of claim 4, further comprising: before determining a first common sub-graph of the plurality of query task graphs, determining a cost index in a target graph that matches the common sub-graph between the plurality of query task graphs from the plurality of query task graphs and the target graph; determining a first common subgraph of the plurality of query graphs based on label values of respective nodes in the plurality of query graphs, including: and if the cost index is not greater than a preset threshold value, determining a first public subgraph of the plurality of query graphs based on the label value of each node in the plurality of query graphs.
6. The method of claim 4, wherein the first common sub-graph comprises at least two portions that are not connected, the at least two portions being stored in a cache of a preset setting.
7. The method of claim 1, wherein the method is performed by a preset graph computation engine, the first portions of the target graph being pre-saved by a plurality of computing nodes of the graph computation engine; For the target graph, adding a corresponding local round of label value for the node conforming to the label structure combination according to the mapping relation, wherein the method comprises the following steps: Adding corresponding local turn label values to nodes conforming to the label structure combination in a first part of the target graph stored in the computing nodes according to the mapping relation in each computing node in the plurality of computing nodes; and matching query nodes based on the label values of all nodes in the target graph, wherein the matching of the query nodes comprises the step of adding corresponding local label values for nodes conforming to the label structure combination in a first part of the target graph stored in the computing nodes in each computing node in the plurality of computing nodes according to the mapping relation.
8. A graph query device, comprising: The acquisition unit is configured to acquire a plurality of query requests of a user for target graphs, wherein the query requests comprise a plurality of query graphs, and each node in the target graphs and each query graph is configured with a node attribute; The processing unit is configured to execute a plurality of rounds of label generation by taking node attributes as initial label values, wherein each round of label generation comprises the steps of acquiring a label structure combination formed by the current label value of each node and the current label value of a neighbor node of each node in the plurality of query graphs, constructing a mapping relation between each label structure combination and the label value of the round, and adding the label value of the round to each node in each query graph according to the mapping relation; and the query unit is configured to perform matching of query nodes based on the label values of all the nodes in the target graph to obtain a first query result, wherein the query nodes are from the query graph added with labels.
9. A computer readable storage medium having stored thereon a computer program which, when executed in a computer, causes the computer to perform the method of any of claims 1-7.
10. A computing device comprising a memory having executable code stored therein and a processor, which when executing the executable code, implements the method of any of claims 1-7.

Description

Graph query method and device Technical Field One or more embodiments of the present disclosure relate to the field of graph query technologies, and in particular, to a method and an apparatus for querying a graph. Background With the popularization and application of technologies such as big data and knowledge graph, the application scale of graph query based on big-scale graph data is increasing. Sub-graph query Subgraph Query refers to the process of looking up sub-graphs in a large graph that satisfy specific structural and attribute constraints. Subgraph queries have wide application in fields such as molecular structure retrieval, social network analysis, financial anti-fraud, and the like. In an actual production environment, users often perform a large number of sub-graph query tasks that are similar in structure or that exist partially overlapping on the same data graph. In the existing graph query scheme, a mode of independently processing each graph query task and carrying out simple sequential processing on a plurality of graph query tasks is adopted, so that a large amount of redundant calculation is generated in the steps of screening, traversing and the like of data nodes in the graph query process, the graph query efficiency is seriously restricted, and the consumption of calculation resources is improved. Disclosure of Invention Embodiments in the present specification aim to provide a graph query method and apparatus, which can generate, for a query task graph and a target graph, a node label containing not only node attribute information, but also structure information of a connection structure between a node and its neighboring node. Furthermore, a common sub-graph between query task graphs may be determined with fewer computational steps and computational resources from the node labels and query results may be determined from the target graph in accordance with the common sub-graph. Therefore, the calculation time and resources consumed by the whole of the plurality of graph query tasks are obviously reduced, the query efficiency of the plurality of graph query tasks is improved, and the defects in the prior art are overcome. According to a first aspect, there is provided a graph query method, including: acquiring a plurality of query requests of a user for a target graph, wherein the query requests comprise a plurality of query graphs, and node attributes are configured for each node in the target graph and each query graph; Executing a plurality of rounds of label generation by taking node attributes as initial label values, wherein each round of label generation comprises the steps of acquiring a label structure combination formed by the current label value of each node and the current label value of a neighbor node of each node in the plurality of query graphs, constructing a mapping relation between each label structure combination and the label value of the round, and adding the label value of the round for each node in each query graph according to the mapping relation; and matching query nodes based on the label values of all the nodes in the target graph to obtain a first query result, wherein the query nodes are from the query graph added with labels. In one possible implementation, each round of label generation further includes culling nodes that do not fit any label structure combination for the target graph. In one possible implementation, before the matching of the query node, the method further includes: Determining a first public subgraph of the plurality of query graphs based on label values of nodes in the plurality of query graphs; the query node is from the first public sub-graph. In one possible embodiment, the method further comprises: before determining a first common sub-graph of the plurality of query task graphs, determining a cost index in a target graph that matches the common sub-graph between the plurality of query task graphs from the plurality of query task graphs and the target graph; determining a first common subgraph of the plurality of query graphs based on label values of respective nodes in the plurality of query graphs, including: and if the cost index is not greater than a preset threshold value, determining a first public subgraph of the plurality of query graphs based on the label value of each node in the plurality of query graphs. In one possible embodiment, the first common sub-graph comprises at least two parts that are not connected. In one possible implementation, the label structure combination indicates a current label value of the node, a current label value of a neighbor node of the node, and an adjacency relationship between the current label value of the node and the current label value of the neighbor node of the node. In one possible implementation, the method is performed by a preset graph calculation engine, and the first parts of the target graph are pre-saved by a plurality of calculation nodes of the graph calculation engine