Computing graph similarity via graph matching

1. A computer-implemented method for calculating a similarity between a pair of graph-structured objects by one or more learning-based techniques, the method comprising:

computing node embeddings of the pair of graph-structured objects of two computer graphs utilizing a hierarchical graph matching network (HGMN);

performing, by a first component of the HGMN, graph matching of global-level graph interactions of the two computer graphs;

performing, by a second component of the HGMN, graph matching of cross-level node-graph interactions of the two computer graphs, wherein the second component comprises a multi-perspective Node-Graph Matching Network (NGMN) configured for learning the cross-level node-graph interactions of the two computer graphs;

aggregating features learned from the graph matching of the global-level graph interactions and the cross-level node-graph interactions; and

performing at least one of a graph-graph classification or a graph-graph regression utilizing the learned features of the two computer graphs.

2. The computer-implemented method according to claim 1 , further comprising:

performing the graph matching of the global-level graph interactions by assessing graph-graph interactions; and

performing the graph matching of the cross-level node-graph interactions by assessing node-graph interactions, wherein the learning-based techniques comprise a deep-learning method.

3. The computer-implemented method according to claim 1 , wherein the first component of the HGMN performing the graph matching of the global-level graph interactions of the two computer graphs comprises a Siamese Graph Neural Network (SGNN) configured to learn the global-level interactions.

4. The computer-implemented method according to claim 3 , wherein the SGNN includes a multi-layer Graph Convolution Network (GCN), and the method further comprising:

computing the node embeddings of the two computer graphs by a node embedding layer of the GCN;

aggregating the computed node embeddings and formulating corresponding graph-level embeddings of each graph of the two computer graphs by a graph-level embedding aggregation layer of the GCN; and

computing a graph similarity score of the two graphs by a graph-graph matching and prediction layer of the GCN.

5. The computer-implemented method according to claim 1 , wherein the NGMN includes a plurality of node embedding layers and one or more node-graph matching layers, and the method further comprising:

computing node embeddings for each node of the node embedding layers;

calculating a graph-level embedding of a graph of the two graphs of the node-graph matching layers;

comparing the node embeddings of the graph with an associated graph-level embedding of a whole graph; and

producing a similarity feature vector.

6. The computer-implemented method according to claim 5 , wherein the NGMN includes a plurality of aggregation layers, and the method further comprising:

aggregating feature embeddings of the node-graph matching layers;

computing a similarity score based on a cosine or a sigmoid similarity of the aggregated features; and

outputting a predicted similarity score.

7. The computer-implemented method according to claim 6 , wherein the aggregating feature embeddings of the node-graph matching layers is performed by using a commutative aggregator.

8. A system for calculating a similarity between a pair of graph-structured objects by one or more learning-based techniques, the system comprising:

a processor configured to perform deep graph similarity learning;

a memory coupled to the processor, the memory storing instructions to cause the processor to perform acts comprising:

compute node embeddings of the pair of graph-structured objects of two computer graphs utilizing a hierarchical graph matching network (HGMN);

perform, by a first component of the HGMN, graph matching of global-level graph interactions of the two computer graphs; and

perform, by a second component of the HGMN, graph matching of cross-level node-graph interactions of the two computer graphs, wherein the second component of the HGMN comprises a multi-perspective Node-Graph Matching Network (NGMN) configured to perform graph matching of cross-level node-graph interactions of the two computer graphs;

aggregate features learned from the graph matching of the global-level graph interactions and the cross-level node-graph interactions; and

perform at least one of a graph-graph classification or a graph-graph regression utilizing the learned features of the two computer graphs or a graph-graph regression utilizing the learned features of the two computer graphs.

9. The system according to claim 8 , wherein the processor is further configured to:

perform the graph matching of global-level graph interactions by assessing graph-graph interactions; and

perform the graph matching of cross-level node-graph interactions by assessing node-graph interactions.

10. The system according to claim 8 , wherein the first component of the HGMN comprises a Siamese Graph Neural Network (SGNN) configured to perform graph matching of global-level graph interactions of the two computer graphs.

11. A non-transitory computer-readable storage medium tangibly embodying a computer-readable program code having computer-readable instructions that, when executed, causes a computer device to perform a method of calculating a similarity between a pair of graph-structured objects by one or more learning-based techniques, the method comprising:

computing node embeddings of the pair of graph-structured objects of two computer graphs utilizing a hierarchical graph matching network (HGMN);

performing, by a first component of the HGMN, graph matching of global-level graph interactions of the two computer graphs;

performing, by a second component of the HGMN, graph matching of cross-level node-graph interactions of the two computer graphs, wherein the second component of the HGMN comprises a multi-perspective Node-Graph Matching Network (NGMN) configured to learn the cross-level node-graph interactions of the two computer graphs;

aggregating features learned from the graph matching of the global-level graph interactions and the cross-level node-graph interactions; and

performing at least one of a graph-graph classification or a graph-graph regression utilizing the learned features of the two computer graphs.

12. The computer-readable storage medium according to claim 11 , wherein the method further comprises:

performing the graph matching of global-level graph interactions by assessing graph-graph interactions;

performing the graph matching of cross-level node-graph interactions by assessing node-graph interactions; and

the learning-based techniques comprise a deep-learning method.

13. The computer-readable storage medium according to claim 12 , wherein the method further comprises that the first component of the HGMN performing the graph matching of global-level graph interactions of the two computer graphs comprises a Siamese Graph Neural Network (SGNN) configured for learning the global-level interactions.

14. The computer-readable storage medium according to claim 13 , wherein the SGNN includes a multi-layer Graph Convolution Network (GCN), and the method further comprises:

computing the node embeddings of the two computer graphs by a node embedding layer of the GCN;

aggregating the computed node embeddings and formulating corresponding graph-level embeddings of each graph of the two computer graphs by a graph-level embedding aggregation layer of the GCN; and

computing a graph similarity score of the two computer graphs by a graph-graph matching and prediction layer of the GCN.

15. The computer-readable storage medium according to claim 11 , wherein the NGMN includes a plurality of node embedding layers and one or more node-graph matching layers, and the method further comprises:

computing the node embeddings for each node of the node embedding layers;

calculating a graph-level embedding of a graph of the two graphs of the node-graph matching layers; and

comparing the node embeddings of the graph with an associated graph-level embedding of a whole graph; and

producing a similarity feature vector.

16. The computer-readable storage medium according to claim 15 , wherein the NGMN includes a plurality of aggregation layers, and the method further comprises:

aggregating feature embeddings of the node-graph matching layers;

computing a similarity score based on cosine or sigmoid similarity of the aggregated features; and

determining a predicted similarity score.

17. The computer-readable storage medium according to claim 16 , wherein the method further comprises the aggregating feature embeddings of the node-graph matching layers is performed by using a commutative aggregator.