Hyperbolic Convolution via Kernel Point Aggregation

Eric Qu, Dongmian ZouarXiv 2023 · DOI · arXiv

Introduction

Hyperbolic geometry has emerged as a powerful paradigm for representing hierarchical and tree-like data structures, such as social networks, taxonomies, and molecular graphs. Unlike Euclidean space, where volume grows polynomially with radius, hyperbolic space exhibits exponential growth. This property allows it to embed complex hierarchies with minimal distortion using fewer dimensions. However, extending deep learning primitives—specifically convolution—to hyperbolic manifolds remains a significant challenge due to the non-linear nature of these spaces.

The Challenge of Hyperbolic Convolution

Standard convolutional neural networks (CNNs) rely on a fixed grid and translation invariance, concepts that do not directly translate to curved manifolds. Existing hyperbolic neural networks often resort to simple fully-connected layers or graph message-passing schemes. While effective, these methods frequently overlook local geometric patterns or fail to maintain permutation equivariance—a crucial property ensuring that the model's output is independent of the ordering of a node's neighbors.

HKConv: Bridging Geometry and Convolution

To address these limitations, the authors propose HKConv (Hyperbolic Kernel Convolution). This novel layer draws inspiration from point cloud analysis, defining a geometrically-aware convolution that operates directly in hyperbolic space.

Visualization of kernel points distributed in hyperbolic space (left) and their projection onto the Poincaré disk (right).

The HKConv operation consists of three primary stages:

  1. Hyperbolic Translation: To focus on local relationships and ensure numerical stability, the model first translates a node and its local neighborhood to the hyperbolic origin. This creates a local coordinate system where relative positions are preserved, avoiding the extreme distortions typically found at the boundaries of hyperbolic models like the Poincaré disk or the Lorentz model.
  2. Kernel Point Correlation: The core innovation lies in the use of $K$ fixed "kernel points" distributed around the origin. For each neighbor in a neighborhood, the model computes its hyperbolic distance to these kernels. This distance profile serves as a "geometric signature," capturing how the neighbor is positioned relative to the fixed reference points.
  3. Aggregation via Centroid: Instead of a simple weighted sum, which is ill-defined in non-Euclidean spaces, HKConv employs a Lorentzian centroid. It aggregates the transformed features of neighbors, weighted by their proximity to the kernel points, ensuring the output remains on the manifold.
Detailed view of the kernel point correlation step, where neighbor positions are compared against fixed kernel points at the origin.

A key design choice is that kernel points are not learned during backpropagation. Instead, they are optimized as a preprocessing step to be maximally spread out near the origin. This approach prevents vanishing gradients and ensures stable training.

Experimental Results

The researchers evaluated HKConv across several domains, demonstrating its versatility and superior performance:

  • Graph Classification: On the ENZYMES dataset, HKConv achieved an accuracy of 82.46%, significantly outperforming both Euclidean GCNs (66.39%) and previous hyperbolic state-of-the-art models like WLHN (62.5%).
  • Node Classification: In tasks involving highly hyperbolic datasets (e.g., WebKB), HKConv established new benchmarks, often improving accuracy by 3-5% over existing methods.
  • Machine Translation: When applied to the IWSLT’14 and WMT’14 English-German datasets, HKConv improved BLEU scores over the standard Hyperbolic Transformer (HyboNet). This suggests that convolutional logic can effectively complement global attention mechanisms by capturing local linguistic hierarchies.

Conclusion

HKConv represents a significant step forward in hyperbolic deep learning. By introducing a geometrically-aware convolution that is both stable and permutation equivariant, the authors provide a robust tool for processing hierarchical data. While the method introduces some computational overhead due to multiple linear transformations per kernel, the substantial gains in accuracy across diverse tasks justify its use in complex, non-Euclidean domains.

Summary updated

Abstract

Learning representations according to the underlying geometry is of vital importance for non-Euclidean data. Studies have revealed that the hyperbolic space can effectively embed hierarchical or tree-like data. In particular, the few past years have witnessed a rapid development of hyperbolic neural networks. However, it is challenging to learn good hyperbolic representations since common Euclidean neural operations, such as convolution, do not extend to the hyperbolic space. Most hyperbolic neural networks do not embrace the convolution operation and ignore local patterns. Others either only use non-hyperbolic convolution, or miss essential properties such as equivariance to permutation. We propose HKConv, a novel trainable hyperbolic convolution which first correlates trainable local hyperbolic features with fixed kernel points placed in the hyperbolic space, then aggregates the output features within a local neighborhood. HKConv not only expressively learns local features according to the hyperbolic geometry, but also enjoys equivariance to permutation of hyperbolic points and invariance to parallel transport of a local neighborhood. We show that neural networks with HKConv layers advance state-of-the-art in various tasks.
BibTeX
@misc{qu2023hyperbolic,
  author = {Eric Qu and Dongmian Zou},
  title = {{Hyperbolic Convolution via Kernel Point Aggregation}},
  year = {2023},
  eprint = {2306.08862},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2306.08862},
}
Figure