# SFCA: A Scalable Formal Concepts Driven Architecture for Multi-Field Knowledge Graph Completion
## 3 Methodology
### Formal Concept Sampling Module  
An obvious problem with dense formal concepts produced by the FCE module: Not all formal concepts are requisite. Similar semantic information and negative gain information consist of dense formal concepts (Not all formal concepts can have corresponding real concepts in the real world, so formal concepts need to be screened before using them). Thus, we proposed an FCS module to reduce complexity and improve the quality of formal concepts. An entity can be mapped into many formal concepts in a sizable KG. Formal concepts, including the same entity, can be considered a hierarchy. Among all formal concepts, we argue that those located in the top-most node formal concepts involve the most valuable information, and relation in factual triples is sufficient to filter out them (Here, the topmost formal concept refers to the formal concept that has a non-zero and minimum number of elements in the relationship set, and the number of elements in the entity set owned by this formal concept is closest to all entities). As shown in Figure 4, our FCS module is designed by a rough-to-fine sampling strategy in the usage of instance relations and partial order relations. Specifically, the formal concepts mapped by Entity 2 are marked by the blue dots in the concept lattice on the left top. The formal concepts mapped by Entity 2 and relation e after the first sampling are marked by the blue dots in the left middle concept lattice. The formal concept mapped by entity 2 and relation e after the second sampling is marked by the blue dots in the concept lattice on the lower left. The blue dots in the green parallelogram on top of the figure are the sampled formal concepts. (1) Sampling with instance relations: In the first stage, we only use the instance relations for sampling by inferring that formal concepts mapped by the same entity under different relations should differ. Given an instance triplet, if a formal concept in the set is mapped to the head entity of the instance triplet and the relation of the instance triplet belongs to the relation set of the formal concept, the formal concept will be mapped to the entity-relation pair composed of the head entity and the relation of the instance triple:  
For every \((e_{i},r_{j},e_{k})\in KG\), let \(\mathsf{C}_{e_{i}r_{j}}^{temp}=\left\{(A_{l},B_{l})\middle|(A_{l},B_{l}) \in\mathsf{C}_{e_{i}r_{j}}^{temp},r_{j}\in B_{l}\right\}\). Where \((A_{l},B_{l})\) is the concept in the concept lattice \(K\). We can get the following mapping:  
\[ \begin{split} g:&\mathsf{C}_{e_{i}r_{j}}^{temp} \rightarrow\left\{(e_{i},r_{j})\right\},\\ &\text{for every }(A_{l},B_{l})\in\mathsf{C}_{e_{i}r_{j}}^{temp},\mathcal{S}\big{(}(A_{l},B_{l})\big{)}=&(e_{i},r_{j}).\end{split}  \tag{5}\]  
(2) Sampling with partial order relations: After the first sampling stage, the selected formal concept set mapped to the head entity-relation pair still contains some formal concepts, and the formal concepts in this set can form a partial order relation between formal concepts. Thus, to simplify the mapping, we select the formal concept with the same link position for all formal concept links. Here, we select the most valuable formal concept in the formal concept set. Substitute formal concept set as a mapping formal concept of head entity-relation pair. Given an instance triplet, if a formal concept in the set mapped to the head entity-relation pair of the instance triplet and the relation set of the formal concept is included in the relation set of all formal concepts in the formal concept set, then the formal concept is selected to be mapped to the entity-relation pair composed of the instance triple head entity and relation, according to Definition 3, there exists a maximum concept in the \(\mathsf{C}_{e_{i}r_{j}}^{temp}\). For every \((e_{i},r_{j},e_{k})\in KG\), let \(\mathsf{C}_{e_{i}r_{j}}^{final}=\left\{(A_{l},B_{l})\middle|(A_{l},B_{l}) \in\mathsf{C}_{e_{i}r_{j}}^{temp},\forall(A_{m},B_{m})\in\mathsf{C}_{e_{i}r_{ j}}^{temp},\right.\)\((A_{m},B_{m})\leq(A_{l},B_{l})\right\}\).