Vector-valued Distance and Gyrocalculus on the Space of Symmetric Positive Definite Matrices

Federico López, Beatrice Pozzetti, Steve Trettel, Michael Strube, Anna Wienhard

TL;DR

This paper introduces a framework for performing deep learning on the manifold of Symmetric Positive Definite (SPD) matrices by leveraging vector-valued distances and gyrocalculus. By treating the distance between points as a vector rather than a scalar, the authors capture richer geometric information, allowing SPD-based models to outperform Euclidean and hyperbolic equivalents in knowledge graph completion, recommendation, and question answering.

What Problem Does This Paper Address?

In geometric deep learning, researchers often choose between Euclidean space (good for flat features) and hyperbolic space (ideal for hierarchical data). However, many real-world datasets contain a mix of both. The space of Symmetric Positive Definite (SPD) matrices is a powerful alternative because its geometry naturally encompasses both Euclidean and hyperbolic subspaces.

Despite this potential, SPD manifolds are difficult to work with. Standard scalar distance metrics (like the Affine Invariant metric) discard significant geometric information. Furthermore, basic neural network operations—like adding a bias or scaling a feature—don't have straightforward "closed-form" equivalents in the curved SPD space. Previous attempts often "flattened" the manifold, which leads to structural distortion and poor performance in high dimensions.

Methods

The authors bridge the gap between Euclidean intuition and SPD geometry using two primary tools:

  1. Vector-valued Distance (VVD): In flat space, the distance between two points is a single number (a scalar). In SPD space, the relative position of two points is more complex. The authors use a vector of the logarithms of the eigenvalues of the matrices to define distance. This vector is a "complete invariant," meaning it captures the full geometric relationship between two points. This also allows them to use Finsler metrics (like $L_1$ or $L_\infty$ norms of the VVD) instead of just the standard Riemannian ($L_2$) distance.
  2. Gyrocalculus: To build neural layers, you need arithmetic. The authors develop "gyro-operations" for SPD matrices, providing explicit formulas for:
  3. Gyro-addition: Analogous to adding a bias.
  4. Gyro-scalar multiplication: Analogous to scaling a vector.
  5. Matrix scaling: A more flexible version of scaling using Hadamard products.
  6. Tangent Space Optimization: Instead of complex Riemannian optimization, they map points to the tangent space (which is flat), perform standard Euclidean optimization, and map back using exponential and logarithmic maps.

Datasets

The authors evaluated their approach across three distinct domains:

  • Knowledge Graph Completion: WN18RR (WordNet) and FB15k-237 (Freebase).
  • Recommender Systems: Amazon (Software, Luxury & Beauty, Prime Pantry) and MindReader (movie recommendations).
  • Question Answering: TrecQA and WikiQA.

Key Insights and Ideas

  • SPD as a "Super-Geometry": Because SPD manifolds contain both flat and curved subspaces, a single model can learn to represent hierarchical structures in the hyperbolic parts and flat features in the Euclidean parts simultaneously.
  • Information Richness: A scalar distance tells you how far two points are; the VVD tells you in which geometric way they are related. This extra information is crucial for disentangling complex relationships in knowledge graphs.
  • Explainability through VVD: The authors found that VVD isn't just for computation—it's a visualization tool. By plotting the VVD, they could visually demonstrate how the model learns to cluster "true" facts away from "false" ones as training progresses.
  • Metric Flexibility: The paper shows that the "best" distance metric is task-dependent. For example, the Finsler $L_1$ metric performed better on WordNet, while the standard Riemannian metric was superior for Freebase.

Key Results

  • State-of-the-Art Performance: SPD models consistently tied or outperformed Euclidean and hyperbolic baselines.
  • Knowledge Graphs: On WN18RR, the SPD scaling model achieved a Hits@10 of 59.0, significantly beating the hyperbolic MuRP model (56.6).
  • Recommendations: SPD rotation-based models were particularly effective, achieving the best performance in 3 out of 4 datasets, proving highly versatile for modeling user-item interactions.
  • Question Answering: The SPD models outperformed 105-dimensional Euclidean and hyperbolic baselines on both TrecQA and WikiQA, suggesting that SPD embeddings are excellent for capturing semantic word relationships.

Limitations and Future Work

The primary drawback is computational complexity. Calculating distances and gyro-operations involves matrix inversions and diagonalizations, resulting in an $O(n^3)$ cost relative to the matrix dimension $n$. While $n$ doesn't need to be very large (e.g., a $14 \times 14$ matrix provides 105 degrees of freedom), it is still more expensive than simple vector arithmetic.

Future work could involve exploring more sophisticated neural architectures (like Transformers) adapted to the SPD manifold and investigating more efficient ways to compute these geometric operations at scale.

Summary updated

Abstract

We propose the use of the vector-valued distance to compute distances and extract geometric information from the manifold of symmetric positive definite matrices (SPD), and develop gyrovector calculus, constructing analogs of vector space operations in this curved space. We implement these operations and showcase their versatility in the tasks of knowledge graph completion, item recommendation, and question answering. In experiments, the SPD models outperform their equivalents in Euclidean and hyperbolic space. The vector-valued distance allows us to visualize embeddings, showing that the models learn to disentangle representations of positive samples from negative ones.
BibTeX
@inproceedings{lopez2021vector,
  author = {Federico López and Beatrice Pozzetti and Steve Trettel and Michael Strube and Anna Wienhard},
  title = {{Vector-valued Distance and Gyrocalculus on the Space of Symmetric Positive Definite Matrices}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=9uXILaIam0},
}
Figure