Learning K-way D-dimensional Discrete Embedding for Hierarchical Data Visualization and Retrieval

Xiaoyuan Liang, Martin Renqiang Min, Hongyu Guo, Guiling Wang

Abstract

Standard machine learning models often represent data as high-dimensional "flat" real-valued vectors, which lack explicit structural organization and demand significant storage. This paper introduces Hierarchical K-way D-dimensional (HKD) discrete embeddings, a method to compress these vectors into compact, hierarchical codes. By utilizing a regularized autoencoder with an exponentially decaying weight function, HKD forces the model to capture broad categories in the initial dimensions and fine-grained details in subsequent ones. Evaluations on synthetic and real-world datasets demonstrate that HKD achieves massive search space reductions (up to 93.6%) and superior neighborhood preservation compared to existing discrete encoding techniques.

Introduction

While real-valued embeddings are powerful for capturing semantic relationships, they are computationally expensive to search and store. Furthermore, they do not inherently reflect the hierarchical nature of real-world data, such as biological taxonomies or product categories. Existing discrete hashing methods improve search speed but often treat all bits as equally important, failing to recover nested structures. HKD addresses these challenges by learning a structured discrete representation that naturally organizes data into a searchable hierarchy.

The HKD Framework

The core of the proposed method is a Regularized Autoencoder designed to map continuous embeddings into $D$ slots, each containing a $K$-way discrete value.

Architecture of the HKD regularized autoencoder, showing the transition from continuous embeddings to discrete K-way codes.

Hierarchical Encoding via Weight Decay

To induce a hierarchical structure, the authors introduce an exponentially decaying weight function, $w_d = w_0 \exp(-\lambda d)$, into the neighborhood preservation loss. By penalizing differences in the "front" slots of the code more heavily than the "back" slots, the model is incentivized to use the first few dimensions for high-level clustering.

Differentiable Discrete Codes

Since the "argmax" operation required for discrete selection is non-differentiable, the framework employs a "Softmax temperature" trick during training. This allows gradients to flow through the discrete code layer, enabling end-to-end optimization of the autoencoder.

Neighborhood Preservation (pt-SEE)

To maintain the local structure of the original space without the quadratic cost of all-pairs comparisons, the model uses parametric t-distributed stochastic exemplar-centered embedding (pt-SEE). This technique compares data points to a fixed set of representative "exemplars," significantly reducing computational overhead.

Experimental Results

The authors evaluated HKD against the state-of-the-art KD-encoding (Shu et al., 2018) across synthetic and real-world datasets, including WordNet and CIFAR-100.

Retrieval Efficiency and Accuracy

On a synthetic hierarchical dataset, HKD demonstrated a remarkable ability to prune search spaces. As shown in the table below, the method achieves a search complexity reduction of up to 93.6% while maintaining near-perfect neighborhood preservation (KNN accuracy) compared to the baseline.

Quantitative comparison of HKD and the baseline (Shu et al.) regarding neighborhood preservation and search complexity reduction.

Semantic Hierarchy Recovery

In experiments with the WordNet mammal subtree, HKD successfully recovered biological taxonomies. For instance, closely related species shared identical codes for the first several dimensions, only diverging at the final bits. In contrast, distantly related animals were separated at the very first dimension. Similar results were observed in CIFAR-100, where the model successfully partitioned "superclasses" (e.g., vehicles) into specific sub-classes (e.g., bicycles vs. motorcycles) as more code dimensions were considered.

Conclusion

HKD provides a robust framework for transforming flat embeddings into structured, searchable hierarchies. By combining discrete encoding with hierarchical regularization, the method offers a scalable solution for large-scale data retrieval and visualization. Future work may explore end-to-end training directly from raw data, potentially removing the dependency on pre-trained continuous embeddings.

Summary updated

Abstract

Traditional embedding approaches associate a real-valued embedding vector with each symbol or data point, which is equivalent to applying a linear transformation to ``one-hot" encoding of discrete symbols or data objects. Despite simplicity, these methods generate storage-inefficient representations and fail to effectively encode the internal semantic structure of data, especially when the number of symbols or data points and the dimensionality of the real-valued embedding vectors are large. In this paper, we propose a regularized autoencoder framework to learn compact Hierarchical K-way D-dimensional (HKD) discrete embedding of symbols or data points, aiming at capturing essential semantic structures of data. Experimental results on synthetic and real-world datasets show that our proposed HKD embedding can effectively reveal the semantic structure of data via hierarchical data visualization and greatly reduce the search space of nearest neighbor retrieval while preserving high accuracy.
BibTeX
@inproceedings{liang2019learning,
  author = {Xiaoyuan Liang and Martin Renqiang Min and Hongyu Guo and Guiling Wang},
  title = {{Learning K-way D-dimensional Discrete Embedding for Hierarchical Data Visualization and Retrieval}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/411},
}
Figure