## 3 Proposed Method
### Negative Sampling  
In the knowledge-graph link-prediction task, how to construct the dynamic distribution of negative triplets and how to sample negative triplets efficiently have always been the biggest challenges faced by KGE models. To address these two challenges, we propose a negative sampling method CCS. First, we perform cluster analysis on the entity set, pay attention to the complex relationship between the head and tail entities. We calculate the probability score of each candidate negative triplet, using a small amount of cache to save high-quality entities as candidate negative triplets. Then, the negative triplets are extracted directly from the cache, and the cache is constantly updated during the training process. Figure 5 shows the negative sampling process. Figure 5: Negative triplet sampling process. Since the model generates negative samples by replacing head or tail entities, we set the head-cache H, indexed by \((r,t)\), to store \(h^{\prime}\in E\) as the candidate to replace the head entity. Similarly, we set the tail-cache T, indexed by \((h,r)\), to store \(t^{\prime}\in E\) as the candidate to replace the tail entity. When a positive triplet is received, it corresponds to caches that contain candidates for negative triplets, i.e., H and T. When selecting a candidate entity from the cache H or T which generates a negative triplet, we adopt the rule in [21]. It sets different probabilities for replacing the head entity or the tail entity when destroying the triplet, according to the relation mapping properties. If the relation is 1-to-N, the head entity is preferred to be replaced, referred to be replaced, and if the relation is N-to-1, the tail entity is preferred to be replaced, which greatly reduces the generation of false negative triplets. Under each relation \(r\), the average number of tail entities corresponding to per head entity is calculated, denoted as \(tph\), and the average number of head entities per tail entity is calculated, denoted as \(hpt\). Then, the head entity in the triplet is replaced with the probability of \(tph/(tph+hpt)\), and the tail entity in the triplet is replaced with the probability of \(hpt/(tph+hpt)\), which generates the negative triplet. We sample from the cache based on the score of the triplet, where the larger score indicates a higher probability of being sampled. We are more concerned with negative triplets with high scores during training than in previous work. Our method not only has fewer parameters but is also easier to train than a randomly initialized model. In addition, our method has good scalability and can be flexibly combined with other KGE models. The cache needs to be updated during the iteration; otherwise, it will still face a fixed distribution sampling method. Algorithm 2 shows the way to update the cache (updating the head-cache is the same as updating the tail-cache, and we show only the updating head-cache process here). First, we cluster the entity set using the simple and flexible K-Means algorithm [42; 43] which is more suitable for large entity sets and avoids introducing other biases with many parameters. This method divides the set of entities into \(k\) clusters, i.e., \(\{E_{1},E_{2},\ldots,E_{i},\ldots,E_{k}\}\), and obtains a subset \(E_{N}\in E_{i}\) of size \(N\) from the cluster \(E_{i}\) of the replaced head entity, and stores this subset \(E_{N}\) in the cache H. Then, the scores of all the triplets in H are calculated. Since we want to sample the negative samples with larger scores in the cache, we use the ratio of the scores of each triplet to the sum of all scores in the cache as the probability of each candidate entity in H being sampled. The probability is calculated as shown in Equation (4). \[p(h^{\prime}|(t,r))=\frac{\exp(f(h^{\prime},r,t))}{\sum_{h_{i}\in\text{H}}\exp (f(h^{\prime}_{i},r,t))} \tag{4}\]  
```
Input: head cache H of size \(N\).