Lab of Media and Network

Department of Computer Science & Technology

Tsinghua University

Non-transitive Hashing with Latent Similarity Components

M Ou, P Cui, F Wang, J Wang, W Zhu. SIGKDD 2015


This work embedds entities to a Hamming space based on their semantic similarity.

The semantic similarities between entities are often non-transitive since they could share different latent similarity components. For example, in social networks, we connect with people for various reasons, such as sharing common interests, working in the same company, being alumni and so on. These social connections are non-transitive if people are connected due to different reasons.

The figure below is another example.

We propose a non-transitive hashing method, namely Multi-Component Hashing (MuCH), to identify the latent similarity components to cope with the non-transitive similarity relationships. MuCH generates multiple hash tables with each hash table corresponding to a similarity component, and preserves the non-transitive similarities in different hash table respectively.


Ou, Mingdong and Cui, Peng and Wang, Fei and Wang, Jun and Zhu, Wenwu. Non-transitive Hashing with Latent Similarity Components. Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD '15).