# US 2021/0173841 A1 · Answering complex queries in knowledge graphs with bidirectional sequence encoders

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

- Number: US 2021/0173841 A1
- Document ID: US20210173841A1
- Status: Published application
- Kind: A1
- Application number: 16/857,194
- Filed: 2020-04-24
- Published: 2021-06-10
- Earliest claimed: 2019-12-06
- Assignees: NEC Corporation
- Applicants: NEC Laboratories Europe GmbH
- Inventors: Bhushan Kotnis; Mathias Niepert; Carolin Lawrence
- Web page: https://patentgrep.com/patent/US20210173841A1

## CPC

- G06F 16/24553: {of query operations}
- G06F 16/2246: {Trees, e.g. B+trees}
- G06F 16/24522: {Translation of natural language queries to structured queries}
- G06F 16/322: {Trees}
- G06F 16/3334: {Selection or weighting of terms from queries, including natural language queries}
- G06F 16/9024: {Graphs; Linked lists (G06F16/9027 takes precedence)}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Method for encoding a query graph into a sequence representation includes receiving a set of m×n path queries representing a query graph, the query graph having a plurality of nodes including m root nodes and n leaf nodes, wherein m and n are integer values, each of the m×n path queries beginning with a root node and ending with a leaf node, and encoding positions of each node and each edge between nodes within each of the m×n path queries independently, wherein the encoded positions include a positional order within each path query. The positional encodings may include no positional ordering between different path queries. The query graph may include one or more missing entities and each token representing one of the one or more missing entities may be masked to produce a masked sequential query, which may be fed to a transformer encoder.

## Claims

### Claim 1

A processor-implemented method of encoding a query graph into a sequence representation, the query graph having a plurality of nodes including m root nodes and n leaf nodes, wherein m and n are integer values, the method comprising the steps, implemented in a processor, of:
receiving a set of m×n path queries representing a query graph, each of the m×n path queries beginning with a root node and ending with a leaf node; and
encoding positions of each node and each edge between nodes within each of the m×n path queries independently, wherein the encoded positions include a positional order within each path query.

### Claim 2 (depends on 1)

The method of claim 1, wherein the receiving the set of m×n path queries representing the query graph includes: receiving the query graph, and converting the query graph into a sequential format by decomposing the graph query into the set of m×n path queries.

### Claim 3 (depends on 1)

The method of claim 1, wherein the query graph is a connected directed acyclic graph (DAG).

### Claim 4 (depends on 1)

The method of claim 1, wherein each of the plurality of nodes represents one of an entity on the query graph, an existentially quantified entity variable or a free entity variable, and wherein each edge represents a relation type.

### Claim 5 (depends on 4)

The method of claim 4, further including masking each free variable entity.

### Claim 6 (depends on 4)

The method of claim 4, wherein the query graph includes at least two free variable entities.

### Claim 7 (depends on 1)

The method of claim 1, wherein the encoding positions of each node and each edge between nodes within each of the m×n path queries independently includes mapping each of the m×n path queries to a sequence of tokens, and encoding positions of each token within each sequence of tokens.

### Claim 8 (depends on 1)

The method of claim 1, wherein the query graph includes one or more missing entities and the method further includes masking each token representing one of the one or more missing entities to produce a masked sequential query.

### Claim 9 (depends on 8)

The method of claim 8, further including feeding the masked sequential query to a transformer encoder, wherein the transformer encoder is trained at the location of each of the masked tokens in the masked sequential query using a categorical cross-entropy loss.

### Claim 10 (depends on 8)

The method of claim 8, wherein two or more of the masked tokens represent the same entity, and wherein the method further includes averaging output probability distributions of the two or more masked tokens.

### Claim 11

A system for encoding a query graph, the query graph having a plurality of nodes including m root nodes and n leaf nodes, wherein m and n are integer values, the system comprising one or more processors which, alone or in combination, are configured to provide for execution of a method comprising:
receiving a set of m×n path queries representing a query graph, each of the m×n path queries beginning with a root node and ending with a leaf node; and
encoding positions of each node and each edge between nodes within each of the m×n path queries independently, wherein the encoded positions include a positional order within each path query.

### Claim 12 (depends on 11)

The system of claim 11, wherein the receiving the set of m×n path queries representing the query graph includes receiving the query graph, and converting the query graph into a sequential format by decomposing the graph query into the set of m×n path queries.

### Claim 13 (depends on 11)

The system of claim 11, wherein the query graph includes one or more missing entities and the method further includes masking each token representing the one or more missing entities to produce a masked sequential query.

### Claim 14 (depends on 13)

The system of claim 13, wherein the method further includes feeding the masked sequential query to a transformer encoder, wherein the transformer encoder is trained at the location of each of the masked tokens in the masked sequential query using a categorical cross-entropy loss.

### Claim 15

A tangible, non-transitory computer-readable medium having instructions thereon which, upon being executed by one or more processors, alone or in combination, provide for execution of a method of encoding a query graph into a sequence representation, the query graph having a plurality of nodes including m root nodes and n leaf nodes, wherein m and n are integer values, the method comprising the steps of:
receiving a set of m×n path queries representing a query graph, each of the m×n path queries beginning with a root node and ending with a leaf node; and
encoding positions of each node and each edge between nodes within each of the m×n path queries independently, wherein the encoded positions include a positional order within each path query.
