Abstract
Non-Metric Label Propagation (NMLP) addresses the limitations of standard semi-supervised learning in domains where distance measures violate the triangle inequality. Such non-metricity is common in human perception and complex biological systems. NMLP decomposes a non-metric distance matrix into two metric components, enabling a joint label propagation process that preserves intrinsic data structure. Evaluated across 20 datasets, NMLP consistently outperforms traditional spectrum transformation methods, demonstrating that non-metric violations often contain valuable semantic information rather than mere noise.
The Challenge of Non-Metric Distances
In many real-world applications, the "distance" between objects does not adhere to Euclidean axioms, specifically the triangle inequality ($D_{ac} \leq D_{ab} + D_{bc}$). For instance, in visual pattern recognition, a digit '2' might resemble another '2' (b), which in turn resembles a '7' (d), yet the first '2' and the '7' remain distinct.
Standard label propagation fails in these scenarios. When applied to a non-metric graph, labels "bleed" across inconsistent paths, leading to classification errors and logical conflicts. Traditional solutions often involve spectrum transformations like Shift or Flip to force the data into a metric format, but these methods frequently discard useful semantic relationships.
The NMLP Framework
The authors propose a two-stage approach to handle non-metricity:
- Diagnosis: The algorithm analyzes the spectrum (eigenvalues) of the distance matrix to determine if non-metricity is negligible noise or an intrinsic property of the data.
- Decomposition & Joint Propagation: If intrinsic, the squared non-metric distance matrix $A$ is decomposed into two metric matrices: $A = A^+ - A^-$. The model then performs joint label propagation on a combined graph representing these positive and negative components.
This dual-graph approach allows the model to exploit the information hidden in non-metric violations without suffering from the inconsistency of a single, "broken" graph.
Experimental Evaluation
The NMLP method was evaluated across 20 datasets derived from 7 diverse databases, including evolutionary protein sequences, cat cerebral cortex connections, shape images (Kimia), and music similarity (EMD and PTD). These datasets represent a wide range of non-metric behaviors, from noise-driven to structurally intrinsic.
Comparative Performance
Experimental results demonstrate that NMLP consistently outperforms both direct propagation and various spectrum transformation techniques.
As shown in the results table, NMLP (rightmost column) achieves the lowest error rates across nearly all test cases. For instance, on the Cat-Cortex-1 dataset, NMLP achieves an error rate of 0.065, compared to 0.361 for direct propagation and 0.097 for the Flip baseline. These findings confirm that while the positive component ($A^+$) carries the primary signal, incorporating the negative component ($A^-$) via joint propagation provides a measurable boost in accuracy on intrinsically non-metric datasets.
Conclusion
NMLP provides a robust framework for semi-supervised learning in non-Euclidean spaces. By treating non-metricity as a source of information rather than noise, it preserves the semantic integrity of complex data. Future work will focus on optimizing the $\alpha$ parameter, which balances the influence of the positive and negative graph components.
Summary updated