Graph matching

Patent metadata

Field	Value
Publication number	US-9679247-B2
Application number	US-201314032105-A
Country	US
Kind code	B2
Filing date	Sep 19, 2013
Priority date	Sep 19, 2013
Publication date	Jun 13, 2017
Grant date	Jun 13, 2017

Abstract

A method of building a soft linkage between a plurality of graphs includes initializing a correspondence between type-1 and type-2 objects in the plurality of graphs, and reducing a cost function by alternately updating the type-1 correspondence and updating the type-2 correspondence.

First claim

The invention claimed is:

1. A non-transitory computer program product for building a soft linkage between a plurality of graphs, the computer program product comprising:
a computer readable storage medium having computer readable program code embodied therewith, the computer readable program code comprising:
computer readable program code configured to initialize a first-level correspondence between nodes of the plurality of graphs and a second-level correspondence between nodes of the plurality of graphs,
wherein the computer readable program code configured to initialize of the correspondences further comprises:
computer readable program code configured to sort, separately, the nodes of each of the plurality of graphs based on a degree distribution;
computer readable program code configured to determine a plurality of clusters, separately, the nodes of each of the plurality of graphs based on the sort; and
computer readable program code configured to initialize the first-level correspondence and the second-level correspondences uniformly between the plurality of graphs using the plurality of clusters;

computer readable program code configured to reduce a cost function by alternately updating the first level correspondence and updating the second-level correspondence,
wherein the computer readable program code configured to update the first-level correspondence comprises:
computer readable program code configured to fix the second-level correspondence;
computer readable program code configured to determine a gradient of the first-level correspondence; and
computer readable program code configured to update the first-level correspondence according to the gradient of the first-level correspondence; and

wherein the computer readable program code configured to update the second-level correspondence comprises:
computer readable program code configured to fix the updated value of the first-level correspondence;
computer readable program code configured to determine a gradient of the second-level correspondence using the updated value of the first-level correspondence; and
computer readable program code configured to update the second-level correspondence according to the gradient of the second-level correspondence; and

computer readable program code configured to build a matching graph between the plurality of graphs using the first-level and the second-level correspondences updated using the cost function.

2. The computer program product of claim 1 , wherein the first-level correspondence and the second-level correspondence are each represented as a non-negative matrix whose entries are between 0 and 1.

3. The computer program product of claim 1 , wherein the computer readable program code configured to update the second-level correspondence further comprises computer readable program code configured to match at least one community across multiple populations wherein the plurality of graphs corresponding to respective populations.

4. The computer program product of claim 1 , wherein the plurality of graphs are a plurality of heterogeneous graphs, respectively,
wherein the first-level correspondence is a correspondence between nodes of the plurality of graphs.

5. The computer program product of claim 1 , wherein the plurality of graphs are a plurality of multi-relational data sets, respectively.

6. The computer program product of claim 1 , wherein the plurality of graphs are a plurality of heterogeneous graphs, respectively, and further comprising computer readable program code configured to match entities and ontologies of the plurality of heterogeneous graphs based on structural representations thereof by finding a matching of the structural representations.

7. The computer program product of claim 6 , wherein the structural representations include one of heterogeneous networks and multi-relational data.

8. The computer program product of claim 1 , wherein the matching graph between the plurality of graphs is an integrated network and further comprising computer readable program code configured to perform a cross-network search comprising:
computer readable program code configured to perform the cross-network search on the integrated network.

9. The computer program product of claim 1 , wherein the matching graph between the plurality of graphs is an integrated network and further comprising computer readable program code configured to perform a cross-network visualization comprising:
computer readable program code configured to display visualizing of the matching graph.

10. The computer program product of claim 9 , wherein the computer readable program code configured to build the matching graph comprises:
computer readable program code configured to represent the first-level correspondence as nodes from a first network;
computer readable program code configured to represent the second-level correspondence as the nodes from a second network; and
computer readable program code configured to determine a plurality of links by a correspondence matrix between the plurality of graphs.

11. The computer program product of claim 1 , wherein the matching graph between the plurality of graphs is an integrated network and further comprising
computer readable program code configured to find a clustering on the integrated networks.

12. The computer program product of claim 1 , wherein the matching graph between the plurality of graphs is an integrated network and further comprising computer readable program code configured to detect communities across different populations represented by the plurality of graphs.

13. The computer program product of claim 1 , further comprising computer readable program code configured to perform a cross-network link prediction comprising:
computer readable program code configured to integrate the plurality of graphs including a target network and an auxiliary network;
computer readable program code configured to find at least one matched pair of nodes in the auxiliary network;
computer readable program code configured to extract a plurality of features for the at least one matched pair of nodes;
computer readable program code configured to transfer the plurality of features to at least one target pair of nodes in the target network; and
computer readable program code configured to predict a link between the target pair of nodes in the target network.

14. The computer program product of claim 1 , wherein the plurality of graphs including a target network and an auxiliary network and further comprising computer readable program code configured to perform a cross-network classification comprising:
computer readable program code configured to integrate the target network and the auxiliary network into an integrated network;
computer readable program code configured to build a classifier on the integrated network; and
computer readable program code configured to predict at least one label for a respective un-labeled node in the integrated network using the matching graph.

15. The computer program product of claim 1 , further comprising computer readable program code configured to predict a level of trust between a pair person in a target domain comprising:
computer readable program code configured to represent a trust/distrust relationship in a target domain as a first trust network of the plurality of graphs;
computer readable program code configured to represent a trust/distrust relationship in an auxiliary domain as a second trust network of the plurality of graphs;
computer readable program code configured to perform a cross-network link prediction usin

Assignees

• IBM

Inventors

• Koutra Danai
• Lubensky David M
• Tong Hanghang

Classifications

• G06N5/022 Primary

  Knowledge engineering; Knowledge acquisition · CPC title

• G06N5/048

  Fuzzy inferencing · CPC title