Boosting graph explainability using self-guided data augmentation

Patent metadata

Field	Value
Publication number	US-12548313-B2
Application number	US-202318177163-A
Country	US
Kind code	B2
Filing date	Mar 2, 2023
Priority date	Mar 2, 2023
Publication date	Feb 10, 2026
Grant date	Feb 10, 2026

Abstract

A method for training a model for determining graph similarity is disclosed. The method comprises receiving a first graph and a second graph as training inputs, the first graph and the second graph each including nodes connected by edges. The method further comprises applying a model to the first graph and the second graph to determine (i) pairs of aligned nodes between the first graph and the second graph and (ii) a first training loss. The method further comprises generating a first augmented graph by modifying the first graph depending on the pairs of aligned nodes. The method further comprises applying the model to the first graph and the first augmented graph to determine a second training loss. The method further comprises refining the model based on the first training loss and the second training loss.

First claim

What is claimed is:

1 . A method for training a model for determining graph similarity, the method comprising:
receiving a first graph and a second graph as training inputs, the first graph and the second graph each including nodes connected by edges; applying the model to the first graph and the second graph to determine (i) pairs of aligned nodes between the first graph and the second graph and (ii) a first training loss; generating a first augmented graph by modifying the first graph depending on the pairs of aligned nodes, the modifying the first graph including (i) identifying at least one node from the first graph to be deleted depending on attention scores of a cross-graph attention matrix that is determined by the model based on the first graph and the second graph and (ii) deleting the at least one node from the first graph; applying the model to the first graph and the first augmented graph to determine a second training loss; and refining the model based on the first training loss and the second training loss.

2 . The method according to claim 1 , wherein each pair of aligned nodes in the pairs of aligned nodes includes exactly one node from the first graph and one node from the second graph, and each node from the first graph and the second graph is included in no more than one pair of aligned nodes.

3 . The method according to claim 1 , the applying the model to the first graph and the second graph further comprising:
determining first node vector embeddings representing the nodes of the first graph; determining second node vector embeddings representing the nodes of the second graph; and determining the pairs of aligned nodes depending on the first node vector embeddings and the second node vector embeddings.

4 . The method according to claim 3 , the applying the model to the first graph and the second graph further comprising:
determining a first graph vector embedding representing the first graph based on the first node vector embeddings; determining a second graph vector embedding representing the second graph based on the second node vector embeddings; and determining the first training loss based on the first graph vector embedding and the second graph vector embedding using a first loss function.

5 . The method according to claim 4 , the applying the model to the first graph and the second graph further comprising:
determining first edge vector embeddings representing the edges of the first graph; determining second edge vector embeddings representing the edges of the second graph; determining the first graph vector embedding depending on the first node vector embeddings and the first edge vector embeddings; and determining the second graph vector embedding depending on the second node vector embeddings and the second edge vector embeddings.

6 . The method according to claim 4 , the applying the model to the first graph and the first augmented graph further comprising:
determining a third graph vector embedding based on the first graph; determining a fourth graph vector embedding based on the first augmented graph; and determining the second training loss based on the third graph vector embedding and the fourth graph vector embedding using the first loss function.

7 . The method according to claim 3 , the applying the model to the first graph and the second graph further comprising:
determining the cross-graph attention matrix based on the first node vector embeddings and the second node vector embeddings; and determining a third training loss based on the cross-graph attention matrix using a second loss function configured to enforce each node in the first graph attending to only one node in the second graph, wherein the model is refined based on the third training loss.

8 . The method according to claim 3 , the applying the model to the first graph and the second graph further comprising:
determining the cross-graph attention matrix based on the first node vector embeddings and the second node vector embeddings; and determining a fourth training loss based on the cross-graph attention matrix using a third loss function configured to enforce each node in the second graph attending to at most one node in the first graph, wherein the model is refined based on the fourth training loss.

9 . The method according to claim 3 , the applying the model to the first graph and the second graph further comprising:
determining the cross-graph attention matrix based on the first node vector embeddings and the second node vector embeddings; and determining the pairs of aligned nodes based on the cross-graph attention matrix.

10 . The method according to claim 1 , the identifying the at least one node from the first graph to be deleted further comprising:
identifying the at least one node from the first graph to be deleted as a node of the first graph that is associated with an attention score of the cross-graph attention matrix that does not exceed a predetermined threshold.

11 . The method according to claim 1 further comprising:
generating a second augmented graph by modifying the second graph depending on the pairs of aligned nodes; and
applying the model to the second graph and the second augmented graph to determine a fifth training loss,
wherein the model is refined based on the fifth training loss.

12 . The method according to claim 1 , the refining the model further comprising:
determining a weight summation of the first training loss and the second training loss.

13 . A method for determining graph similarity, the method comprising:
receiving a first graph and a second graph as inputs, the first graph and the second graph each including nodes connected by edges; applying a model to the first graph and the second graph to determine (i) pairs of aligned nodes between the first graph and the second graph and (ii) a similarity score indicating a similarity between the first graph and the second graph; and using the pairs of aligned nodes and the similarity score to perform a task, wherein each pair of aligned nodes in the pairs of aligned nodes includes exactly one node from the first graph and one node from the second graph, and each node from the first graph and the second graph is included in no more than one pair of aligned nodes.

14 . The method according to claim 13 , the receiving further comprising:
receiving a first image; determining the first graph based on the first image, the first graph representing keypoints in the first image; and retrieve the second graph from a database, the second graph being representing keypoints of a second image in the database.

15 . The method according to claim 13 , the receiving further comprising:
receiving first text data; determining the first graph based on the first text data, the first graph representing the first text data; and retrieve the second graph from a database, the second graph representing second text data in the database.

16 . The method according to claim 13 , the using the pairs of aligned nodes and the similarity score further comprising:
retrieving a database record associated with the second graph depending the on the similarity score.

17 . The method according to claim 16 , the using the pairs of aligned nodes and the similarity score further comprising:
displaying data from the database record; and displaying a graphical representation of at least some of the pairs of aligned nodes.

18 . The method according to claim 17 , wherein the graphical representation of the at le

Assignees

• Bosch Gmbh Robert

Inventors

• Chawla Piyush
• Gou liang
• Song Huan
• Doan Thang
• Ren Liu

Classifications

• G06V10/84

  using probabilistic graphical models from image or video features, e.g. Markov models or Bayesian networks · CPC title

• G06V10/761 Primary

  Proximity, similarity or dissimilarity measures · CPC title

• G06V10/82 Primary

  using neural networks · CPC title