Systems and methods of interactive visual graph query for program workflow analysis

Patent metadata

Field	Value
Publication number	US-12417622-B2
Application number	US-202117478478-A
Country	US
Kind code	B2
Filing date	Sep 17, 2021
Priority date	Sep 17, 2021
Publication date	Sep 16, 2025
Grant date	Sep 16, 2025

Abstract

Systems and methods are disclosed for identifying target graphs that have nodes or neighborhoods of nodes (sub-graphs) that correspond with an input query graph. A visual analytics system supports human-in-the-loop, example-based subgraph pattern search utilizing a database of target graphs. Users can interactively select a pattern of nodes of interest. Graph neural networks encode topological and node attributes in a graph as fixed length latent vector representations such that subgraph matching can be performed in the latent space. Once matching target graphs are identified as corresponding to the query graph, one-to-one node correspondence between the query graph and the matching target graphs.

First claim

What is claimed is:

1. A computer-implemented method for performing subgraph pattern searching with human-in-the-loop visual analytics, the computer-implemented method comprising:
storing, in memory, a graph database containing a plurality of target graphs, each target graph having a plurality of target nodes connected by edges;
receiving, via a user interface, a query graph having a plurality of query nodes;
via a graph neural network, retrieve one or more matching target graphs from the graph database that each contain the query graph as a subgraph thereof;
extracting embeddings of each of the query nodes and each of the target nodes of the one or more matching target graphs;
performing, via a second graph neural network, a comparison of the embeddings of each query node with the embeddings of each target node of the one or more matching target graphs by determining a similarity between the extracted embeddings of the query nodes and the target nodes of the one or more matching target graphs; and
generating, via the user interface, a graphical depiction of a one-to-one node correspondence between the query nodes and the target nodes of the one or more matching target graphs based on the comparison,
wherein the graphical depiction of the one-to-one node correspondence between the query nodes and the target nodes of the one or more matching target graphs includes, for each node pair in the correspondence, a graphical depiction of the extracted embeddings of the query node and the target node.

2. The computer-implemented method of claim 1 , wherein the embeddings for each of the query nodes and each of the target nodes of the one or more matching target graphs include attributes of that node, attributes of a neighboring node connected to that node, and attributes of a connection between that node and the neighboring node.

3. The computer-implemented method of claim 1 , wherein the step of performing utilizes an attention network.

4. The computer-implemented method of claim 1 , further comprising:
developing a probability matrix that compares each of the query nodes with each of the target nodes of the one or more matching target graphs, wherein the probability matrix includes a probability of a match between each of the query nodes and each of the target nodes of the one or more matching target graphs.

5. The computer-implemented method of claim 1 , wherein the step of performing the comparison is performed without segmenting the query graph and the one or more matching target graphs into neighborhoods of adjacent nodes.

6. The computer-implemented method of claim 1 , wherein the query nodes and the target nodes include labels identifying objects in an image, wherein the labels include at least one of a person, a vehicle, a road, a building, a tree, or a road sign.

7. A visual analytics system configured to support human-in-the-loop subgraph pattern searching, the visual analytics system comprising:
a user interface;
a memory storing a target graph database having a plurality of target graphs, each target graph having a plurality of target nodes connected by edges; and
a processor programmed to:
via the user interface, receive a query graph having a plurality of query nodes;
via a first graph neural network, retrieve one or more matching target graphs from the target graph database, wherein each of the one or more matching target graphs contains the query graph as a subgraph thereof;
extract embeddings of each of the query nodes and each of the target nodes of the one or more matching target graphs;
via a second graph neural network, compare the query nodes with the target nodes of the one or more matching target graphs by determining a similarity between the extracted embeddings of the query nodes and the target nodes of the one or more matching target graphs; and
generate, on the user interface, a graphical depiction of a one-to-one node correspondence between the query nodes and the target nodes of the one or more matching target graphs based on the comparing,
wherein the graphical depiction of the one-to-one node correspondence between the query nodes and the target nodes of the one or more matching target graphs includes, for each node pair in the correspondence, a graphical depiction of the extracted embeddings of the query node and the target node.

8. The visual analytics system of claim 7 , wherein the processor is further programmed to:
perform a comparison of the embeddings of each query node with the embeddings of each target node of the one or more matching target graphs.

9. The visual analytics system of claim 8 , wherein the processor is further programmed to utilize an attention network to perform the comparison.

10. The visual analytics system of claim 7 , wherein the processor is further configured to develop a probability matrix comparing each of the query nodes with each of the target nodes of the one or more matching target graphs, wherein the probability matrix includes a probability of a match between each of the query nodes and each of the target nodes of the one or more matching target graphs.

11. The visual analytics system of claim 7 , wherein the processor is further programmed to compare the query nodes with the target nodes on a one-to-one comparison.

12. The visual analytics system of claim 11 , wherein the processor is further programmed to compare the query nodes with the target nodes on the one-to-one comparison without segmenting the query graph and the one or more matching target graphs into neighborhoods.

13. The visual analytics system of claim 7 , wherein the query nodes and the target nodes include labels identifying objects in an image, wherein the labels include at least one of a person, a vehicle, a road, a building, a tree, or a road sign.

14. The visual analytics system of claim 7 , wherein the processor is further configured to generate, on the user interface, a graph query panel configured to allow a user to interactively construct the query graph by selecting the query nodes.

15. The visual analytics system of claim 7 , wherein the processor is further configured to generate, on the user interface, a query results window that displays all the one or more matching target graphs, with each of the target nodes that correspond to the query nodes being highlighted or colored.

16. A system comprising:
a memory storing a target graph database having a plurality of target graphs, each target graph having a plurality of target nodes connected by edges; and
a processor communicatively connected to the memory and programmed to:
receive a query graph having a plurality of query nodes;
retrieve, utilizing a first graph neural network, one or more matching target graphs from the target graph database, wherein each of the one or more matching target graphs contains the query graph as a subgraph thereof;
extract embeddings of each of the query nodes and each of the target nodes of the one or more matching target graphs;
determine, utilizing a second graph neural network, a similarity between the extracted embeddings of the query nodes and the target nodes of the one or more matching target graphs with a one-to-one node correspondence; and
generate a graphical depiction of the one-to-one node correspondence between the query nodes and the target nodes of the one or more matching target graphs,
wherein the graphical depiction of the one-to-one node correspondence between the query nodes and the target nodes of the one or more matching target graphs includes, for each node pair in the correspondence, a graphical depiction of the extracted embeddin

Assignees

• Bosch Gmbh Robert

Inventors

• Song Huan
• Dai Zeng
• Xu Panpan
• Ren Liu

Classifications

• G06V10/86

  using syntactic or structural representations of the image or video pattern, e.g. symbolic string recognition; using graph matching · CPC title

• G06F16/532

  Query formulation, e.g. graphical querying · CPC title

• G06F18/24143

  Distances to neighbourhood prototypes, e.g. restricted Coulomb energy networks [RCEN] · CPC title

• G06V20/64

  Three-dimensional [3D] objects · CPC title

• G06N3/08

  Learning methods · CPC title