# US 2021/0342352 A1 · Method for duplicate determination in a graph

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2021/0342352 A1
- Document ID: US20210342352A1
- Status: Published application
- Kind: A1
- Application number: 17/114,547
- Filed: 2020-12-08
- Published: 2021-11-04
- Earliest claimed: 2020-04-29
- Assignees: International Business Machines Corporation
- Applicants: International Business Machines Corporation
- Inventors: Thuany Karoline Stuart; Basem Elasioty; Claudio Andrea Fanconi; Mike W. Grasselt; Hemanth Kumar Babu; Yannick Saillet; Robert Kern; Martin Oberhofer; Lars Bremer; Jonathan Roesner; Jason Allen Woods
- Web page: https://patentgrep.com/patent/US20210342352A1

## CPC

- G06F 16/24556: {Aggregation; Duplicate elimination}
- G06F 16/2272: {Management thereof}
- G06F 16/9024: {Graphs; Linked lists (G06F16/9027 takes precedence)}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Embodiments of the present invention determines duplicates in a graph. The graph comprises nodes representing entities and edges representing relationships between the entities. The method comprises: identifying at least two nodes in the graph. A neighborhood subgraph may be determined for each of the two nodes. The neighborhood subgraph includes the respective node. The method further comprises determining whether the two nodes are duplicates with respect to each other, based on a result of a comparison between the two subgraphs.

## Claims

### Claim 1

A computer-implemented method comprising:
determining duplicates in a graph wherein the graph comprises nodes representing entities and edges that represent relationships between the entities by:
identifying at least two nodes in the graph;
determining a respective neighborhood subgraph for each of the two nodes, the neighborhood subgraph including a respective node;
comparing the respective neighborhood subgraphs; and
determining whether the two nodes are duplicates with respect to each other, based on a result of the comparison.

### Claim 2 (depends on 1)

The computer-implemented method of claim 1, wherein determining of the neighborhood subgraph of the node comprises:
selecting nodes of the graph using a selection criterion, the selection criterion being based on at least one of: a number of nodes, an entity represented by a node, a distance between the node and another node in the subgraph; the subgraph comprising the selected nodes.

### Claim 3 (depends on 2)

The computer-implemented method of claim 2, wherein the selection criterion requires at least one of:
the number of nodes of the subgraph being smaller than a maximum number;
the edge of the subgraph connected to at least one node that represents a same entity as the entity of the node; and
the distance between the node and another node in the subgraph is smaller than a threshold number of edges.

### Claim 4 (depends on 1)

The computer-implemented method of claim 1, wherein comparing the respective subgraphs comprises:
calculating a similarity metric;
comparing the calculated similarity metric with a predefined threshold; and
in response to determining that the similarity metric exceeds the predefined threshold determining whether the two nodes are duplicates.

### Claim 5 (depends on 1)

The computer-implemented method of claim 1, further comprising:
in response to determining that the two nodes are duplicates, performing a twin detection method, wherein the twin detection method comprises:
acquiring additional properties of the entities represented by the two nodes; and
cancelling a decision that the two nodes are duplicates with respect to each other based on the additional properties.

### Claim 6 (depends on 1)

The computer-implemented method of claim 1, wherein identifying the at least two nodes comprises:
calculating an index structure, the index structure comprising:
for each node of the graph, at least one index entry, the index entry including an identifier of the node and an edge descriptor describing an edge connected to that node, wherein the edge descriptor comprises direction information related to a direction of the edge and/or a neighbor node identifier;
sorting and grouping the index structure according to the edge descriptors of individual index entries, resulting in a set of one or more groups;
selecting a first node of the at least two nodes; and
finding further nodes that are in a same group, of the set of groups, as the first node.

### Claim 7 (depends on 6)

The computer-implemented method of claim 6, wherein the individual index entries are represented as text strings.

### Claim 8 (depends on 6)

The computer-implemented method of claim 6, wherein the grouping further comprises deleting groups based on their size.

### Claim 9 (depends on 1)

The computer-implemented method of claim 1, wherein determining of the neighborhood subgraphs comprises:
removing duplicate nodes of each subgraph the neighborhood subgraphs.

### Claim 10 (depends on 1)

The computer-implemented method of claim 1, further comprising:
using a received indication of the two identified nodes for the identifying.

### Claim 11

A computer program product comprising:
one or more computer readable storage media and program instructions stored on the one or more computer readable storage media, the program instructions comprising:
program instructions to determine duplicates in a graph wherein the graph comprises nodes representing entities and edges that represent relationships between the entities by:
program instructions to identify at least two nodes in the graph;
program instructions to determine a neighborhood subgraph for each of the two nodes, the neighborhood subgraph including a respective node;
program instructions to compare the respective neighborhood subgraphs; and
program instructions to determine whether the two nodes are duplicates with respect to each other, based on a result of the comparison.

### Claim 12 (depends on 11)

The computer program product of claim 11, wherein the program instructions to determine of the neighborhood subgraph of the node comprise:
program instructions to select nodes of the graph using a selection criterion, the selection criterion being based on at least one of: a number of nodes, an entity represented by a node, a distance between the node and another node in the subgraph; the subgraph comprising the selected nodes.

### Claim 13 (depends on 12)

The computer program product of claim 12, wherein the selection criterion requires at least one of:
the number of nodes of the subgraph being smaller than a maximum number;
the edge of the subgraph connected to at least one node that represents a same entity as the entity of the node; and
the distance between the node and another node in the subgraph is smaller than a threshold number of edges.

### Claim 14 (depends on 11)

The computer program product of claim 11, wherein the program instructions to compare the respective subgraphs comprise:
program instructions to calculate a similarity metric;
program instructions to compare the calculated similarity metric with a predefined threshold; and
program instructions to, in response to determining that the similarity metric exceeds the predefined threshold, determine whether the two nodes are duplicates.

### Claim 15 (depends on 11)

The computer program product of claim 11, wherein the program instructions stored on the one or more computer readable storage media further comprise:
program instructions to, in response to determining that the two nodes are duplicates, perform a twin detection method, wherein the twin detection method comprises:
program instructions to acquire additional properties of the entities represented by the two nodes; and
program instructions to cancel a decision that the two nodes are duplicates with respect to each other based on the additional properties.

### Claim 16

A computer system comprising:
one or more computer processors;
one or more computer readable storage media; and
program instructions stored on the one or more computer readable storage media for execution by at least one of the one or more computer processors, the program instructions comprising:
program instructions to determine duplicates in a graph wherein the graph comprises nodes representing entities and edges that represent relationships between the entities by:
program instructions to identify at least two nodes in the graph;
program instructions to determine a neighborhood subgraph for each of the two nodes, the neighborhood subgraph including a respective node;
program instructions to compare the respective neighborhood subgraphs; and
program instructions to determine whether the two nodes are duplicates with respect to each other, based on a result of the comparison.

### Claim 17 (depends on 16)

The computer system of claim 16, wherein the program instructions to determine of the neighborhood subgraph of the node comprise:
program instructions to select nodes of the graph using a selection criterion, the selection criterion being based on at least one of: a number of nodes, an entity represented by a node, a distance between the node and another node in the subgraph; the subgraph comprising the selected nodes.

### Claim 18 (depends on 17)

The computer system of claim 17, wherein the selection criterion requires at least one of:
the number of nodes of the subgraph being smaller than a maximum number;
the edge of the subgraph connected to at least one node that represents a same entity as the entity of the node; and
the distance between the node and another node in the subgraph is smaller than a threshold number of edges.

### Claim 19 (depends on 16)

The computer system of claim 16, wherein the program instructions to compare the respective subgraphs comprise:
program instructions to calculate a similarity metric;
program instructions to compare the calculated similarity metric with a predefined threshold; and
program instructions to, in response to determining that the similarity metric exceeds the predefined threshold, determine whether the two nodes are duplicates.

### Claim 20 (depends on 16)

The computer system of claim 16, wherein the program instructions stored on the one or more computer readable storage media further comprise:
program instructions to, in response to determining that the two nodes are duplicates, perform a twin detection method, wherein the twin detection method comprises:
program instructions to acquire additional properties of the entities represented by the two nodes; and
program instructions to cancel a decision that the two nodes are duplicates with respect to each other based on the additional properties.
