A Hubness Information-Based k-Nearest Neighbor Approach for Multi-Label Learning

Zeyu Teng, Shanshan Tang, Min Huang, Xingwei WangMathematics 2025 · DOI

TL;DR

This paper introduces MLHiKNN, a novel k-Nearest Neighbor (kNN) approach for multi-label classification (MLC) that specifically addresses the "hubness" problem in high-dimensional data. By incorporating hubness information into label relevance and neighbor weighting, MLHiKNN achieves competitive performance on benchmark datasets, outperforming existing MLC algorithms.

What Problem Does This Paper Address?

Multi-label classification (MLC) is crucial for tasks where an instance can belong to multiple categories simultaneously (e.g., image tagging, document categorization). While kNN-based methods have shown promise in MLC, they are susceptible to the "hubness" phenomenon. Hubness occurs in high-dimensional spaces where a few data points (hubs) disproportionately appear in the k-nearest neighbor lists of many other points. This can lead to biased predictions, especially when hubs are not representative of the true class. Existing MLC algorithms and hubness reduction techniques have not adequately addressed this issue in the context of MLC.

Methods

The proposed method, MLHiKNN, is a kNN-based MLC algorithm that tackles hubness by:

  • Hubness-Aware Label Relevance: It introduces a fuzzy measure of label relevance for training examples. This measure considers not only the instance's own label but also its hubness information (k-occurrence) and the probability of it being irrelevant to a label based on its neighbors.
  • Weighted kNN Scheme: MLHiKNN employs a weighted kNN approach. The weights for nearest neighbors are adjusted based on both their distance to the query point (standard kNN practice) and their hubness information. This ensures that neighbors with high hubness (and potentially less informative or misleading) have their influence reduced.
  • High-Order Label Correlations: MLHiKNN exploits label correlations by training a logistic regression model for each label. This model uses the computed label relevance scores for all possible labels as input, effectively capturing higher-order relationships between labels.

Datasets

The proposed MLHiKNN algorithm was evaluated on 28 benchmark multi-label datasets. These datasets are from various domains (audio, music, biology, text, image, video) and vary in size, dimensionality, and number of labels. The paper does not introduce new datasets but utilizes publicly available ones from the MULAN and MEKA libraries.

Key Insights and Ideas

  • Hubness is a significant problem for MLC: The paper demonstrates that hubness, while studied in single-label settings, has a detrimental impact on MLC performance, particularly for kNN-based methods.
  • Hubness information can be leveraged: Instead of just trying to mitigate hubness, MLHiKNN shows that incorporating hubness information (specifically, k-occurrence) can actually improve classification by appropriately weighting neighbors and assessing label relevance.
  • Fuzzy logic and weighted kNN are effective: The combination of fuzzy membership for label relevance and weighted kNN based on distance and hubness proves to be a powerful approach for handling the complexities of MLC in high-dimensional, hubness-prone data.
  • High-order label correlations are crucial: The use of logistic regression on label relevance scores effectively captures complex label dependencies, leading to improved generalization.

Key Results

  • MLHiKNN achieved competitive performance across 28 benchmark datasets.
  • It was top-ranked on 26 out of 28 datasets in terms of AUC macro when compared to nine well-established MLC algorithms.
  • MLHiKNN consistently achieved better average ranks than other kNN-based MLC algorithms (BRkNNa, MLKNN, DMLKNN, IBLR) across various metrics and parameter settings.
  • The proposed method also outperformed hubness-reduced BRKNNa and MLKNN approaches, demonstrating the effectiveness of its integrated hubness handling.
  • Ablation studies confirmed the effectiveness of each component (fuzzy membership, hubness weighting, distance weighting) in MLHiKNN.

Limitations and Future Work

  • Computational Complexity: While MLHiKNN is effective, its complexity for training is noted as $O(n^2(d + q) + ng^2 + nqk)$, which can be high for very large datasets.
  • Parameter Sensitivity: The performance of MLHiKNN is influenced by parameters like $k$, $\lambda$, and $\beta$. While the paper provides recommendations based on experiments, optimal parameter tuning might still be dataset-dependent.
  • Future Work: The authors suggest combining their algorithm-level hubness reduction approach with data-level hubness reduction techniques to further improve performance on multi-label datasets with hubs.

Summary updated

Abstract

Multi-label classification (MLC) plays a crucial role in various real-world scenarios. Prediction with nearest neighbors has achieved competitive performance in MLC. Hubness, a phenomenon in which a few points appear in the k-nearest neighbor (kNN) lists of many points in high-dimensional spaces, may significantly impact machine learning applications and has recently attracted extensive attention. However, it has not been adequately addressed in developing MLC algorithms. To address this issue, we propose a hubness-aware kNN-based MLC algorithm in this paper, named multi-label hubness information-based k-nearest neighbor (MLHiKNN). Specifically, we introduce a fuzzy measure of label relevance and employ a weighted kNN scheme. The hubness information is used to compute each training example’s membership in relevance and irrelevance to each label and calculate weights for the nearest neighbors of a query point. Then, MLHiKNN exploits high-order label correlations by training a logistic regression model for each label using the kNN voting results with respect to all possible labels. Experimental results on 28 benchmark datasets demonstrate that MLHiKNN is competitive among the compared methods, including nine well-established MLC algorithms and three commonly used hubness reduction techniques, in dealing with MLC problems.
BibTeX
@inproceedings{teng2025hubness,
  author = {Zeyu Teng and Shanshan Tang and Min Huang and Xingwei Wang},
  title = {{A Hubness Information-Based k-Nearest Neighbor Approach for Multi-Label Learning}},
  booktitle = {Mathematics},
  year = {2025},
  doi = {10.3390/math13071202},
}
Figure