# Incorporating External Knowledge Reasoning for Vision-and-Language Navigation with Assistant's Help
## 3 Method
### Attention-Based Knowledge-Enabled Cross-Modality Reasoning
#### 3.2.3 Attention-Based Internal-External Parallel Knowledge Graph Reasoning  
We design the AIEPKR module for room- and object-relation reasoning, where the object-relation reasoning is iteratively carried out by two parallel branches, i.e., external knowledge graph reasoning and internal task-specific knowledge graph reasoning using an attention mechanism to fuse, as shown in Figure 3.  
A. External knowledge graph reasoning. AIEPKR takes the top-K query to retrieve the most relevant \(K\) knowledge facts for each category of objects in the task from ConceptNet to construct an external knowledge graph \(KG^{E}=\left(X^{E},\mathcal{E}^{E}\right)\), where \(X^{E}=\{x_{i}\}_{i=1}^{N_{E}}\) is the node set and \(\mathcal{E}^{E}=\left\{\hat{e}_{i\hat{j}}\right\}_{i,j=1}^{N_{E}}\) is the edge set. Each node \(x_{i}\) corresponds to an object \(o_{i}\), and each edge \(\varepsilon_{ij}\) denotes the relationships between objects \(o_{i}\) and \(o_{j}\). Besides, \(H^{E}\in\mathbb{R}^{N_{E}\times D_{w}}\) denotes the node feature matrix, and \(\mathbb{R}^{N_{E}\times N_{E}}\) represents the weighted adjacency matrix, in which each element \(A_{i,j}^{E}\) is pre-trained. The multi-step reasoning process of external knowledge is as follows:  
\[\left\{ \begin{array}{l}H^{E(k)}=\delta\Big{(}A^{E}H^{E(k-1)}W^{E(k)}\Big{)}\\ H^{E(0)}=H^{E}\end{array} \right.\]  
where \(k\) represents the \(k\)th step of the graph convolution process using the Graph Convolutional Network (GCN), \(\delta(\cdot)\) is the activation function, and \(W^{E(k)}\) is a learnable parameter. B. Internal knowledge graph reasoning. The internal knowledge graph \(KG^{I}=\big{(}X^{I},\mathcal{E}^{I}\big{)}\) includes only 1600 categories that are able to be detected by the detector \(D\), dynamically learning domain-specific knowledge from the dataset. \(H^{I}\in\mathbb{R}^{1600\times D_{w}}\) and \(A^{I}\in\mathbb{R}^{1600\times 1600}\) represent the node feature matrix and weighted adjacency matrix of \(KG^{I}\), respectively, where \(A^{I}\) is learnable. At time step \(t\), the module samples from \(KG^{I}\) according to the detected object set \(X_{v_{t}}\) as an index to construct a fully connected subgraph \(KG^{I}_{v_{t}}=\big{(}X^{I}_{v_{t}},\mathcal{E}^{I}_{v_{t}}\big{)}\). \(H^{I}_{v_{t}}\in\mathbb{R}^{N_{v_{t}}\times D_{w}}\) denotes the node feature matrix, and \(A^{I}_{v_{t}}\in\mathbb{R}^{N_{v_{t}}\times N_{v_{t}}}\) denotes the learnable adjacency matrix. Similarly, \(H^{I}_{v_{t}}\) and \(A^{I}_{v_{t}}\) are sub-matrices of \(H^{I}\) and \(A^{I}\), respectively. \(KG^{I}_{v_{t}}\) dynamically extracts external knowledge from \(KG^{E}\) to enhance and correct internal knowledge reasoning. For the external knowledge extraction, also take \(X_{v_{t}}\) as the index to sample a sub-node feature matrix \(H^{E(k)}_{v_{t}}\) from \(H^{E(k)}\). Then, we use an attention mechanism to fuse \(H^{I(k)}_{v_{t}}\) with \(H^{E(k)}_{v_{t}}\), which is formulated as:  
\[\alpha^{E}_{k,i}=\frac{\exp\Big{(}H^{E(k)}_{v_{t}}[i,:]W_{h}h^{\top}_{t-1} \Big{)}}{\exp\Big{(}H^{I(k)}_{v_{t}}[i,:]W_{h}h^{\top}_{t-1}\Big{)}+\exp\Big{(} H^{E(k)}_{v_{t}}[i,:]W_{h}h^{\top}_{t-1}\Big{)}}\]  
\[\alpha^{I}_{k,i}=\frac{\exp\Big{(}H^{I(k)}_{v_{t}}[i,:]W_{h}h^{\top}_{t-1} \Big{)}}{\exp\Big{(}H^{I(k)}_{v_{t}}[i,:]W_{h}h^{\top}_{t-1}\Big{)}+\exp\Big{(} H^{E(k)}_{v_{t}}[i,:]W_{h}h^{\top}_{t-1}\Big{)}}\]  
\[\bar{H}^{I(k)}_{v_{t}}[i,:]=\alpha^{I}_{k,i}H^{I(k)}_{v_{t}}[i,:]+\alpha^{E}_{ k,i}H^{E(k)}_{v_{t}}[i,:]\]  
where \(M[i,:]\) represents the i-th row of the matrix and \(W_{h}\) is a learnable parameter. The multi-step reasoning process of internal knowledge is as follows:  
\[\left\{ \begin{array}{l}H^{I(k)}_{v_{t}}=\delta\Big{(}A^{I}_{v_{t}}H^{I(k-1) }_{v_{t}}W^{I(k)}\Big{)}\\ H^{I(0)}_{v_{t}}=H^{I}_{v_{t}}\end{array} \right.\]  
Figure 3: Illustration of the AEPKR module.