# Using Graph Embedding Techniques in Process-Oriented Case-Based Reasoning
## 3 Neural Networks for Graph Embedding
### Propagation Layer  
With the initial embeddings of all nodes and edges, the propagation layer can be applied. This layer differs significantly for GEM and GMN. Therefore, the propagation concept of the GEM will be explained first, and the propagation concept of the GMN afterwards. The propagation layer of the GEM uses edges between nodes to iteratively update the representation of these nodes. In a single one of the \(K\) propagation steps, the representation of each node is updated. \[m_{w,v}=\text{NN}_{\text{message}}([h_{v}^{(k)},h_{w}^{(k)},h_{v,w}]),\quad \forall(v,w)\in E \tag{2}\]  
\(m_{w,v}\) is the representation of a single message between nodes. It is composed of the concatenated inputs of the node representation of \(v\), \(w\), and the representation of the edge \(e_{v,w}\), transformed by the neural network layer \(\text{NN}_{\text{message}}\). The type of this layer can be freely chosen but an MLP is recommended by [PERSON] et al. [23]. As follows, the message representation \(m_{w,v}\) is used to update all node representations from the current state \(h_{v}^{(k)}\) to the next state \(h_{v}^{(k+1)}\):  
\[h_{v}^{(k+1)}=\text{NN}_{\text{node}}\Bigg{(}\bigg{[}h_{v}^{(k)},\sum_{(w,v) \in E}m_{w,v}\bigg{]}\Bigg{)},\quad\forall v\in N \tag{3}\]  
The neural network layer \(\text{NN}_{\text{node}}\) from Equation (3) takes as inputs a concatenation of the current node state of node \(v\), i.e., \(h_{v}^{(k)}\), and an aggregation of the message representationsof all incoming edges of node \(v\) (see Equation (2)). This aggregation can be any commutative element-wise vector operator, e.g., sum, mean, maximum, or minimum. The layer \(\text{NN}_{\text{node}}\) can either be an MLP or a recurrent layer core such as a Gated Recurrent Unit (GRU) [45] and a Long Short-Term Memory (LSTM) [46]. The GMN approaches propagation from a different point of view to the GEM. Whereas the GEM only considers messages (in the form of edges) within a single graph, the GMN matches nodes from both graphs at an early stage of the similarity assessment. \[att(h_{v}^{(k)},h_{w}^{(k)})=\frac{e^{\text{r}sim(h_{v}^{(k)},h_{w}^{(k)})}}{ \sum_{w^{\prime}\in N:N\
i w}e^{\text{r}sim(h_{v}^{(k)},h_{w^{\prime}}^{(k)})}} \tag{4}\]  
Equation (4) shows the computation of the function \(att\) that computes attention weights using a softmax attention (see [47; 48] for a comprehensive explanation of attention in neural networks). In this case, the softmax function can be interpreted as the indication of relevance that the node representation \(h_{w}^{(k)}\) has for matching with the node representation \(h_{v}^{(k)}\). The function \(vsim\) can be any vector similarity measure, e.g., cosine similarity, that yields a scalar value. To indicate the attention weights of a node from one graph to all nodes of another graph, the descriptor \(attmat\) is used. For instance, \(attmat(v\in G_{1})\) represents a matrix where each row contains the pairwise attention weights (as computed by the function \(att\)) of the node \(v\) from graph \(G_{1}\) to other nodes from graph \(G_{2}\). \[h_{v}^{(k+1)}=\text{NN}_{\text{node}}\Bigg{(}\Big{[}h_{v}^{(k)},\sum_{(w,v)\in \mathbb{F}_{1}}(m_{w,v}),\;h_{v}^{(k)}\ominus\sum_{w^{\prime}\in\mathbb{N}_{2 }}attmat(v)\cdot h_{w^{\prime}}^{(k)}\Big{]}\Bigg{)} \tag{5}\]  
These attention weights are then used in the process of constructing node representations for the next transformation step, i.e., \(h_{v}^{(k+1)}\), by extending the update process of the GEM (see Equation (5)). The extended function \(\text{NN}_{\text{node}}\) of the GMN takes a third parameter that adds a _cross-graph matching component_. The cross-graph matching component is made up of the attention weights introduced by Equation (4). The matrix of attention weights of node \(v\), i.e., \(attmat(v)\) is multiplied with the representation vector of all nodes from \(G_{2}\), i.e., \(attmat(v)\cdot h_{w^{\prime}}^{(k)}\). The resulting vectors are finally aggregated and subtracted element-wise from the node representation of node \(v\).