Unsupervised Hierarchy Matching with Optimal Transport over Hyperbolic Spaces

David Alvarez-Melis, Youssef Mroueh, Tommi S. Jaakkola

Abstract

This paper focuses on the problem of unsupervised alignment of hierarchical data such as ontologies or lexical databases. This is a problem that appears across areas, from natural language processing to bioinformatics, and is typically solved by appeal to outside knowledge bases and label-textual similarity. In contrast, we approach the problem from a purely geometric perspective: given only a vector-space representation of the items in the two hierarchies, we seek to infer correspondences across them. Our work derives from and interweaves hyperbolic-space representations for hierarchical data, on one hand, and unsupervised word-alignment methods, on the other. We first provide a set of negative results showing how and why Euclidean methods fail in this hyperbolic setting. We then propose a novel approach based on optimal transport over hyperbolic spaces, and show that it outperforms standard embedding alignment techniques in various experiments on cross-lingual WordNet alignment and ontology matching tasks.

Introduction: The Challenge of Hierarchy Alignment

Hierarchical structures—such as WordNet or biological ontologies—are essential for organizing knowledge. However, merging or matching these structures across different languages or domains is traditionally expensive, requiring expert knowledge or external resources like translation dictionaries.

While recent research has shown that hyperbolic spaces (like the Poincaré disk) are far better than Euclidean spaces for embedding trees and hierarchies, existing unsupervised alignment techniques fail in this setting. The authors identify a specific reason for this: branch permutation invariance. In hyperbolic embeddings, the relative positions of branches can flip or rotate between different training runs even if the underlying hierarchy is identical. Standard linear transformations cannot fix these "warped" branches, making unsupervised matching a major hurdle.

Visualization of hierarchy embeddings in the Poincaré disk illustrating branch permutation.

Methodology: Hyperbolic Optimal Transport

The authors propose a purely geometric approach that does not rely on text labels or external knowledge. Their method, Hyp-OT, consists of two main components:

  1. Hyperbolic Optimal Transport (OT): They adapt Optimal Transport to work over hyperbolic manifolds. Specifically, they use the Sinkhorn Divergence as a loss function, which provides a "soft" matching between entities and a smooth gradient for optimization.
  2. Non-linear Registration via Hyperbolic Neural Networks: To solve the branch permutation problem, they use a flexible, non-linear registration function f_theta implemented as a hyperbolic neural network. This network "warps" one hyperbolic space to align its branches with the other.
Overview of the proposed framework, showing the mapping f_theta and the alignment loss W(X, f_theta(Y)) based on hyperbolic optimal transport.

The training process is fully unsupervised: the model minimizes the transport cost between the source hierarchy and the transformed target hierarchy until the structures overlap.

Key Results and Insights

The proposed method showed dramatic improvements over Euclidean baselines across several challenging benchmarks, including a newly released multilingual WordNet dataset and OAEI 2018 Ontology Matching tasks.

  • WordNet Alignment: On English-to-Spanish matching, Hyp-OT achieved a Precision@10 of 56.8%, whereas standard Euclidean methods like MUSE and Invar-OT hovered between 0.25% and 1.2%.
  • Ablation Studies: The authors proved that the hyperbolic metric is essential. Replacing the hyperbolic distance with Euclidean distance in their own pipeline caused performance to plummet from 88.8% to 13.0% on a self-recovery task.
  • Ontology Matching: In the OAEI Anatomy task, Hyp-OT outperformed baselines by a wide margin (e.g., 7.89% P@10 vs. 0.12% for MUSE).

The most striking insight is that the alignment problem is fundamentally non-linear due to the geometry of trees. By treating the alignment as a manifold registration problem, the authors show that you can "un-distort" branch permutations using hyperbolic versions of standard neural network layers (like Möbius addition).

Conclusion

Hyp-OT represents a significant step forward in unsupervised hierarchy matching. While the method is sensitive to structural noise and requires careful initialization, its ability to leverage the natural geometry of hierarchical data allows it to succeed where traditional Euclidean methods fail. Future work may integrate lexical features to create even more robust semi-supervised tools.

Summary updated

Abstract

This paper focuses on the problem of unsupervised alignment of hierarchical data such as ontologies or lexical databases. This is a problem that appears across areas, from natural language processing to bioinformatics, and is typically solved by appeal to outside knowledge bases and label-textual similarity. In contrast, we approach the problem from a purely geometric perspective: given only a vector-space representation of the items in the two hierarchies, we seek to infer correspondences across them. Our work derives from and interweaves hyperbolic-space representations for hierarchical data, on one hand, and unsupervised word-alignment methods, on the other. We first provide a set of negative results showing how and why Euclidean methods fail in this hyperbolic setting. We then propose a novel approach based on optimal transport over hyperbolic spaces, and show that it outperforms standard embedding alignment techniques in various experiments on cross-lingual WordNet alignment and ontology matching tasks.
BibTeX
@inproceedings{alvarezmelis2020unsupervised,
  author = {David Alvarez-Melis and Youssef Mroueh and Tommi S. Jaakkola},
  title = {{Unsupervised Hierarchy Matching with Optimal Transport over Hyperbolic Spaces}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2020},
  url = {https://openreview.net/forum?id=Q1DaNRXl1pG},
}
Figure