# Using Graph Embedding Techniques in Process-Oriented Case-Based Reasoning
## 2 Foundations and Related Work
### Similarity-Based Retrieval of Semantic Graphs  
While the similarity assessment that is shown in Section 2.2 can be used to determine a single similarity between two semantic graphs, it is more common to use it in the _retrieve_ phase of CBR. A retrieval aims to find the most similar cases from a case base \(CB\) for a given query \(QG\). The most similar cases are determined by computing the pairwise similarity between the query and each case from the case base, before ranking the cases in descending order according to the computed similarities. Many CBR applications only consider the \(k\)-most similar cases as result of the retrieval, which is similar to the well-known \(k\)_-nearest neighbors_ (kNN) algorithm. Although the retrieval algorithm itself has a computational complexity of \(O(|CB|)\), the retrieval time is usually dominated by the similarity measure that is used to compare the cases. For instance, measures that perform any kind of inexact subgraph matching (such as the similarity measure introduced in Section 2.2) belong to the class of NP-complete algorithms [7; 10; 11] and thus have a great impact on performance. To overcome possible performance issues in retrieval situations, the approach of _MAC/FAC_ (\"Many are called but few are chosen\"), introduced by [PERSON] et al. [31], can be used. MAC/FAC is a two-staged retrieval approach that aims to decrease the computation time by pre-filtering the case base in the MAC phase to reduce the number of cases that have to be evaluated by a (potentially) computationally complex similarity measure in the subsequent FAC phase. The MAC phase is parameterized by giving a specific similarity measure and a filter size. The approximating similarity measure of the MAC phase usually has low computational complexity and is knowledge-poor, thus introducing the trade-off between quality and performance of the similarity assessment. The filter size is a parameter of the MAC/FAC algorithm that can be used to control how many of the most similar cases according to the MAC similarity measure are transferred to the FAC phase. In general, the results from the MAC stage can be seen as _candidates_ that might be part of the most similar cases regarding the query. With the pre-filtered cases as an input, the FAC phase applies the computationally intensive similarity measure on these candidates. The result is a list of the same length as the filter size that is not guaranteed to contain the most similar cases of the case base according to the query graph. Further truncation to the \(k\)-most similar cases can be performed analogously to the standard retrieval. Eventually, MAC/FAC is  
Figure 2: Mapping procedure of nodes with illegal mappings.  
a trade-off between retrieval quality and retrieval time. The (possibly) decreased quality results from the pre-filtering that might not return the same graphs that a standard retrieval would have returned. The decreased retrieval time is due to a smaller amount of graph pairs that have to be evaluated by the computationally complex, knowledge-intensive similarity measure in the FAC phase. This points out the importance of a well-designed and well-integrated MAC phase as it significantly influences the results of using a MAC/FAC implementation [31; 32]. Related MAC/FAC approaches in the context of POCBR use similarity measures that are defined on clustered representations of the case base [20], manually modeled graph features [12], and embeddings of graph triplets [19].