# CA-CGNet: Component-Aware Capsule Graph Neural Network for Non-Rigid Shape Correspondence
## 3 Proposed Method
### Component-Aware Graph Routing
#### 3.3.1 Multi-Layer Attention Graph Routing  
We extract features from different CA-GNN layers and fuse the capsule features through a multi-layer attention mechanism. The capsule is regarded as each node in the graph, and the adjacency matrix \(\mathbf{A}\) is used to represent the relationship between nodes in CA-GNN, which can be expressed as:  
\[\mathbf{\tilde{A}}=\mathbf{D}^{-\frac{1}{2}}\mathbf{A}\mathbf{D}^{-\frac{1}{2} }+\mathbf{E} \tag{5}\]  
where \(\mathbf{\tilde{A}}\) is the normalized \(N\times N\) adjacency matrix, \(N\) is the number of capsules, \(\mathbf{D}\) is the degree matrix, and \(\mathbf{E}\) is the identity matrix.  
The capsule vectors can be regarded as the probability of certain attributes, which is used to measure the semantic similarity of capsules. Since the capsule vector is an implicit expression, it is difficult to directly calculate the relationship between capsules. Thus, we used Wasserstein Distance to measure the distance between the distribution of capsule properties. The Component-aware Wasserstein Distance is defined as:  
\[W(V_{i},V_{j})=\left(\inf_{\Omega}\int\limits_{\mathbb{R}^{m}\times\mathbb{R} ^{m}}\Big{(}\|v_{i}-v_{j}\|_{2}+\lambda\Big{\|}X_{v_{i}}-X_{v_{j}}\Big{\|}_{2 }\Big{)}\Omega\big{(}dv_{i},dv_{j}\big{)}\right)^{\frac{1}{2}} \tag{6}\]  
where \(X_{v_{i}}\) and \(X_{v_{j}}\) are the component category to which the point belongs, \(\Omega\) is an element of set \(\Pi\big{(}V_{i},V_{j}\big{)}\), and \(\lambda\) is the coefficient and is set to be 0.005. Let \(a_{ij}=W_{\text{}}(V_{i},V_{j})\), we can convert component-aware Wasserstein Distance to adjacency between capsules inside. Inthis case, \(a_{ij}\) may be negative, so the adjacency matrix \(\mathbf{A}\) needs to be normalized, which is denoted as  
\[\mathbf{\bar{A}}=\frac{e^{\mathbf{A}_{i}}}{\sum\limits_{j}e^{\mathbf{A}_{i}}}+ \mathbf{E} \tag{7}\]  
Considering that the contribution of different levels of graph embedding is inconsistent, we introduce an attention mechanism to combine these different levels of graph embedding to get the final output result as shown in Figure 3. The procedure of the multi-layer attention module can be written as:  
\[w_{j}=\sigma\Big{\{}\Big{(}H_{1}^{GAP},H_{1}^{GMP}\Big{)}\oplus\Big{(}H_{2}^{ GAP},H_{2}^{GMP}\Big{)}\oplus\Big{(}H_{3}^{GAP},H_{3}^{GMP}\Big{)}\Big{\}} \tag{8}\]  
where \(\sigma(\cdot)\) represents the softmax function, and \(\oplus\) represents the feature concat.  
Each capsule is regarded as a center node, and the relationship between capsules is measured by distance with the performed normalization. Then, the multi-layer attention mechanism is introduced to transform the low-level capsule into the high-level capsule using component graph routing. Algorithm 1 gives the complete algorithm of Component-aware Graph Routing.  
Figure 3: The Multi-layer Attention Module. GAP means global average pooling, while GMP refers to global maximum pooling. FC is the fully connected layer. \(w_{j}\) means the weight for each layer.  
```
Input: The low-level capsules \(u_{i}\) and the weight matrix \(\mathbf{W}_{ij}\) Output: The high-level capsules \(v_{j}\)
1 initialize routing coefficients \(b_{ij}\gets 0\)
2 begin
3 // each low-level capsule \(i\)
4\(u_{j|i}=u_{i}\mathbf{W}_{ij}\)
5 Calculate the adjacency matrix \(\mathbf{A}\) for all low-level capsules
6 Normalize \(\mathbf{A}\) with Equation (7)
7 // each low-level capsule \(i\) and high-level capsule \(j\)
8\(g_{j}=u_{j|i}\tilde{\mathbf{A}}\mathbf{W}_{ij}\)
9 Calculate the attention score \(w_{j}\) with Equation (8)
10 for\(n\) in routing interationdo
11 // each low-level capsule \(i\)
12\(c_{ij}=\frac{1}{1+e^{-\frac{w_{j}}{w_{j}}}}\)
13 // each high-level capsule \(j\)
14\(s_{j}=\sum_{i}g_{j}w_{j}c_{ij}\)
15\(v_{j}=squash(s_{j})\)
16\(b_{j}=b_{j}+u_{j|i}v_{j}\)
17
18 end for
19 return\(v_{j}\)
```  
**Algorithm 1**The Algorithm of the Component-aware Graph Routing