Many data representations are vectors of continuous values. In particular, deep learning embeddings are data-driven representations, typically either unconstrained in Euclidean space, or constrained to a hypersphere. These may also be translated into integer representations (quantised) for efficient large-scale use. However, the fundamental (and most efficient) numeric representation in the overwhelming majority of existing computers is integers with overflow -- and vectors of these integers do not correspond to either of these spaces, but instead to the topology of a (hyper)torus. This mismatch can lead to wasted representation capacity. Here we show that common deep learning frameworks can be adapted, quite simply, to create representations with inherent toroidal topology. We investigate two alternative strategies, demonstrating that a normalisation-based strategy leads to training with desirable stability and performance properties, comparable to a standard hyperspherical L2 normalisation. We also demonstrate that a torus embedding maintains desirable quantisation properties. The torus embedding does not outperform hypersphere embeddings in general, but is comparable, and opens the possibility to train deep embeddings which have an extremely simple pathway to efficient `TinyML' embedded implementation.
Figures & tables
Table 1: Normalisation projections for deep learning embeddings. Starting from a ‘raw’ unconstrained representation of dimension D , L2 normalisation is just one possible projection. We consider two approaches to normalisation that create hypertoroidal representations: each has two projections, one leading to the ‘flat square’ torus and one leading to the unit-norm ‘Clifford’ torus. See text for further explanation.
Figure 1: Extremely large gradient updates have different effects in the Clifford torus, depending on whether produced by L2 normalisation or Clifford projection. This illustration shows a single update in a figurative Clifford torus (upper, circle) and a ‘view’ of the same as a flat torus (lower, square). Under L2-normalisation (left), a gradient update is applied in the extrinsic space (solid arrow) before normalisation (dashed arrow), with the side-effect that gradient updates of unbounded size will have a stable impact—in fact, asymptotically limited to a 90 degree angle. In the Clifford-projected space (right), very large gradient updates simply ‘wrap around’, which means that very small deviations in large steps (e.g. floating point rounding errors) may lead to unstable updates.
Figure 2: The two methods for mapping data onto a hypertorus use very different mappings, as in these 2D illustrations. Left panel: L2p normalisation maps 2D points to their angle with respect to the origin. Centre and right panels: the Clifford projection transforms each dimension separately into a cyclical version of itself.
Quantisation method
Codebook size
Bits per vector
Num possible values
8-bit
2D
8D *
256D
1-bit
2D
D
2D
PQ(8,16)
256D
128
3.4×1038
PQ(8,4)
256D
32
4.2×109
PQ(8,2)
256D
16
65536
PQ(8,1)
256D
8
256
Table 3: Quantisation methods applied. PQ(m,n) represents product quantisation with m subspaces and n bits used for indexing within each subspace. D represents the extrinsic dimension of the input data. Codebook size is the number of full-precision scalar values needed in memory. *Note that for 8-bit quantisation in the case of method torusN, the bits-per-vector is half that implied here, because we convert data from Clifford into the flat torus representation before quantisation, which halves the extrinsic dimension D .
Figure 3: Classification performance (precision at 1) on the CIFAR10 and CIFAR100 data sets, using nearest-neighbour classification, comparing embedding spaces that are hyperspherical versus hypertoroidal. The x-axis shows variation in the embedding dimensionality, and (nested inside) variation in the strength of the KoLeo regularisation (the number is the log10 of the regularisation strength).
Figure 4: Classification performance as in Figure 3 (CIFAR100 data set), after quantisation by various methods. The 8-bit quantisation has only a mild impact on performance, but other methods degrade the classifier precision to varying extents.
Figure 5: Birdsong audio classification performance (accuracy) in a few-shot setting, comparing embedding spaces that are hyperspherical versus hypertoroidal. Scores shown are for each of six birdsong datasets provided by BIRB (left to right), with the overall average summarised in the rightmost panel. A dark gray line indicates chance performance for each dataset. The x-axis shows variation in the embedding dimensionality. Upper: 1-shot. Lower: 5-shot.
Appendix figures & tables4 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 6: Simulation to illustrate the effect of the curse of dimensionality in hyperspherical and hypertoroidal spaces. Distances are normalised against the largest possible in the space (the diameter of the space).
Figure 7: Contour plot illustrating the characteristics of distance measures in a 2-dimensional torus. We focus on the quadrant closest to the origin: in the full torus all distance measures ‘reflect’ at the boundaries shown here.
Figure 8: Effect of KoLeo regularisation. Here we visualise two arbitrary dimensions of the CIFAR100 validation set in a 128D trained hypertorus embedding (torusN), at various values of the KoLeo regularisation strength (cf. ( Sablayrolles et al., 2018 ) ). At the highest regularisation strength, data are spread more uniformly through the space, as is also reflected by the circular variance measurements below.
Figure 9: The circular variance of the representations evaluated in Figures 3 and 4 (CIFAR100 data set).
Hierarchical graphs embed in hyperbolic space with lower distortion than in Euclidean space owing to its negative curvature. However, their gradient-based learning is hampered at large radii, where the Poincaré ball and the Lorentz hyperboloid models fail numerically. Polar coordinates avoid this problem, but the hyperbolic metric scales the angular step by the hyperbolic sine of the radius, freezing angular motion. We observe that this factor is a choice, silently fixed by existing implementations: the Euclidean tangent parametrization, for instance, uses the radius itself. We show that other choices are not only possible but preferable. They are endpoints of a one-parameter family of optimization preconditioners with curvatures from −1 to 0, while the embedding remains at curvature −1. We show that since the Euclidean preconditioner rearranges a layout but refines it poorly, while an intermediate one refines far better once a layout is in place, combining them in two stages reduces the loss on real-world trees by 46-74% over the best single curvature.
Despite an ever-increasing interest in topological deep learning models that target higher-order datasets, there is no consensus on how to evaluate such models. This is exacerbated by the fact that topological objects permit operations, such as structural refinements, that are not appropriate for graph data. In this work, we extend MANTRA, a benchmark dataset containing manifold triangulations, to a larger class of manifolds with more diverse homeomorphism types. We show that, unlike prior claims, both graph neural networks (GNNs) and higher-order message passing (HOMP) methods can saturate the benchmark. However, we find that this is contingent on the right representation and feature assignment, emphasizing their importance in baseline models. We thus provide a novel evaluation protocol based on representational diversity and triangulation refinement. Surprisingly, we find no indication that existing models are capable of generalizing beyond the combinatorial structure of the data. This points towards a research gap in developing models that understand topological structure independent of scale. Our work thus provides the necessary scaffolding to evaluate future models and enable the development of topology-aware inductive biases.
Johannes S. Schmidt, Martin Carrasco, Ernst Röell +3
Dept. of Math. & Statistics University of Montréal Montréal, Canada · Dept. of Informatics University of Fribourg Fribourg, Switzerland
Topological structures such as simplicial complexes, hypergraphs, and cell complexes extend standard graph models by modeling higher-order relationships. These structures appear in many modern datasets and require specialized methods for generating meaningful embeddings. In this paper, we introduce TopoEmbedX, a unified framework for embedding a wide range of topological domains into Euclidean spaces. The package brings together several existing topological embedding algorithms---DeepCell, Cell2Vec, CellDiff2Vec, HOLE, and HOGLEE---and introduces five new algorithms: ComplexNetMF, ComplexRep, ComplexRandNE, ComplexWalklets, and ComplexHeat. These algorithms extend well-known graph embedding techniques to higher-order settings using the augmented Hasse graph of a topological domain. TopoEmbedX provides a clear, consistent, and easy-to-use framework for topological representation learning. Experiments show that the embeddings generated by TopoEmbedX support tasks such as classification and regression across multidimensional data.