**SCCL**, or **Supporting Clustering with Contrastive Learning**, is a framework to leverage contrastive learning to promote better separation in unsupervised clustering. It combines the top-down clustering with the bottom-up instance-wise contrastive learning to achieve better inter-cluster distance and intra-cluster distance. During training, we jointly optimize a clustering loss over the original data instances and an instance-wise contrastive loss over the associated augmented pairs.

**Self-Adversarial Negative Sampling** is a negative sampling technique used for methods like [word embeddings](https://paperswithcode.com/methods/category/word-embeddings) and [knowledge graph embeddings](https://paperswithcode.com/methods/category/graph-embeddings). The traditional negative sampling loss from word2vec for optimizing distance-based models be written as:

$$ L = −\log\sigma\left(\gamma − d\_{r}\left(\mathbf{h}, \mathbf{t}\right)\right) − \sum^{n}\_{i=1}\frac{1}{k}\log\sigma\left(d\_{r}\left(\mathbf{h}^{'}\_{i}, \mathbf{t}^{'}\_{i}\right) - \gamma\right) $$

where $\gamma$ is a fixed margin, $\sigma$ is the sigmoid function, and $\left(\mathbf{h}^{'}\_{i}, r, \mathbf{t}^{'}\_{i}\right)$ is the $i$-th negative triplet. 

The negative sampling loss samples the negative triplets in a uniform way. Such a uniform negative sampling suffers the problem of inefficiency since many samples are obviously false as training goes on, which does not provide any meaningful information. Therefore, the authors propose an approach called self-adversarial negative sampling, which samples negative triples according to the current embedding model. Specifically, we sample negative triples from the following distribution:

$$ p\left(h^{'}\_{j}, r, t^{'}\_{j} | \text{set}\left(h\_{i}, r\_{i}, t\_{i} \right) \right) = \frac{\exp\alpha{f}\_{r}\left(\mathbf{h}^{'}\_{j}, \mathbf{t}^{'}\_{j}\right)}{\sum\_{i=1}\exp\alpha{f}\_{r}\left(\mathbf{h}^{'}\_{i}, \mathbf{t}^{'}\_{i}\right)} $$

where $\alpha$ is the temperature of sampling. Moreover, since the sampling procedure may be costly, the authors treat the above probability as the weight of the negative sample. Therefore, the final negative sampling loss with self-adversarial training takes the following form:

$$ L = −\log\sigma\left(\gamma − d\_{r}\left(\mathbf{h}, \mathbf{t}\right)\right) − \sum^{n}\_{i=1}p\left(h^{'}\_{i}, r, t^{'}\_{i}\right)\log\sigma\left(d\_{r}\left(\mathbf{h}^{'}\_{i}, \mathbf{t}^{'}\_{i}\right) - \gamma\right) $$

Self-Adversarial Negative Sampling

RotatE: Knowledge Graph Embedding by Relational Rotation in Complex Space

SCCL

Supporting Clustering with Contrastive Learning

**Global Sub-Sampled Attention**, or **GSA**, is a local [attention mechanism](https://paperswithcode.com/methods/category/attention-mechanisms-1) used in the [Twins-SVT](https://paperswithcode.com/method/twins-svt) architecture. 

A single representative is used to summarize the key information for each of $m \times n$ subwindows and the representative is used to communicate with other sub-windows (serving as the key in self-attention), which can reduce the cost to $\mathcal{O}(m n H W d)=\mathcal{O}\left(\frac{H^{2} W^{2} d}{k\_{1} k\_{2}}\right)$. This is essentially equivalent to using the sub-sampled feature maps as the key in attention operations, and thus it is termed global sub-sampled attention (GSA). 

If we alternatively use the [LSA](https://paperswithcode.com/method/locally-grouped-self-attention) and GSA like [separable convolutions](https://paperswithcode.com/method/depthwise-separable-convolution) (depth-wise + point-wise). The total computation cost is $\mathcal{O}\left(\frac{H^{2} W^{2} d}{k\_{1} k\_{2}}+k\_{1} k\_{2} H W d\right) .$ We have:

$$\frac{H^{2} W^{2} d}{k\_{1} k\_{2}}+k_{1} k_{2} H W d \geq 2 H W d \sqrt{H W} $$ 

The minimum is obtained when $k\_{1} \cdot k\_{2}=\sqrt{H W}$. Note that $H=W=224$ is popular in classification. Without loss of generality, square sub-windows are used, i.e., $k\_{1}=k\_{2}$. Therefore, $k\_{1}=k\_{2}=15$ is close to the global minimum for $H=W=224$. However, the network is designed to include several stages with variable resolutions. Stage 1 has feature maps of $56 \times 56$, the minimum is obtained when $k\_{1}=k\_{2}=\sqrt{56} \approx 7$. Theoretically, we can calibrate optimal $k\_{1}$ and $k\_{2}$ for each of the stages. For simplicity, $k\_{1}=k\_{2}=7$ is used everywhere. As for stages with lower resolutions, the summarizing window-size of GSA is controlled to avoid too small amount of generated keys. Specifically, the sizes of 4,2 and 1 are used for the last three stages respectively.

Source	Supporting Clustering with Contrastive Learning
Year	2000
Data Source	CC BY-SA - https://paperswithcode.com