Back to results
US 9,805,307 B2Granted
Determining soft graph correspondence between node sets based on feature representations
AssigneeInternational Business Machines Corporation
InventorsU Kang, Ravindranath Konuru, Jimeng Sun, Hanghang Tong
Life of this patent
Estimating the term…
Abstract
A method for determining a correspondence between a first node set of a first graph and a second node set of a second graph includes building a feature representation for each of the first graph and the second graph, and inferring the correspondence between the first node set and the second node set based on the feature representations.
Claims6
A method of operating a computer system to store in a memory an approximation of a random walk kernel given a first node set of a first graph and a second node set of a second graph, wherein a capability of said computer system to calculate said random walk kernel is constrained by said memory, the method comprising:
- building a feature representation for each of said first graph and said second graph, said feature representations each comprising a degree for each node of a respective one of said first graph and said second graph, a community-membership for said each node of said respective one of said first graph and said second graph, and a centrality for said each node of said respective one of said first graph and said second graph;
- calculating, from said feature representations, for each node of said first node set, a likelihood of matching each node of said second node set;
- and
- generating, and storing to said memory, a cross population matrix approximating said random walk kernel, wherein said cross population matrix comprises a plurality of columns and a plurality of rows, wherein each node of said first node set is represented in each cell of a respective one of said columns and each node of said second node set is represented in each cell of a respective one of said rows, wherein a value contained in each cell of said cross population matrix corresponds to a given node of said first node set and a given node of said second node set and gives a corresponding one of said likelihoods of matching;
- wherein building said feature representation for each of said first graph and said second graph further comprises:
- determining the degree for each node of said respective graph;
- inferring the community-membership for said each node of said respective graph, wherein the community-membership indicates a given node's inclusion in a cluster within said respective graph;
- and
- determining the centrality for said each node of said respective graph;
- and
- wherein calculating, from said feature representations, for each node of said first node set, said likelihood of matching each node of said second node set further comprises:
- initializing a correspondence between a first node of said first node set and any node of said second node set;
- adjusting said correspondence according to gradient information;
- and
- projecting an updated correspondence to a feasible region.
12 more elements
A computer program product for operating a computer system to store in a memory an approximation of a random walk kernel given a first node set of a first graph and a second node set of a second graph, wherein a capability of said computer system to calculate said random walk kernel is constrained by said memory, the computer program product comprising:
- a non-transitory computer readable storage medium having computer readable program code embodied therewith, the computer readable program code comprising:
- computer readable program code configured to build a feature representation for each of said first graph and said second graph, said feature representations each comprising a degree for each node of a respective one of said first graph and said second graph, a community-membership for said each node of said respective one of said first graph and said second graph, and a centrality for said each node of said respective one of said first graph and said second graph;
- computer readable program code configured to calculate, from said feature representations, for each node of said first node set, a likelihood of matching each node of said second node set;
- and
- computer readable program code configured to generate and store in said memory a cross population matrix approximating said random walk kernel, wherein said cross population matrix comprises a plurality of columns and a plurality of rows, wherein each node of said first node set is represented in each cell of a respective one of said columns and each node of said second node set is represented in each cell of a respective one of said rows, wherein a value contained in each cell of said cross population matrix corresponds to a given node of said first node set and a given node of said second node set and gives a corresponding one of said likelihoods of matching;
- wherein said computer readable program code configured to build said feature representation for each of said first graph and said second graph further comprises:
- computer readable program code configured to determine the degree for each node of said respective graph;
- computer readable program code configured to infer the community-membership for said each node of said respective graph, wherein the community-membership indicates a given node's inclusion in a cluster within said respective graph;
- and
- computer readable program code configured to determine the centrality for said each node of said respective graph;
- and
- wherein said computer readable program code configured to calculate, from said feature representations, for each node of said first node set, said likelihood of matching each node of said second node set further comprises:
- computer readable program code configured to initialize a correspondence between a first node of said first node set and any node of said second node set;
- computer readable program code configured to adjust said correspondence-according to gradient information;
- and
- computer readable program code configured to project an updated correspondence to a feasible region.
13 more elements
Dependencies are inferred from the claim text.