Distance-Based Representation Learning with Nonlinear Feature Algebras

Graph neural networks and spectral embeddings aggregate local neighbourhoods and so miss the global metric properties—growth rate, hyperbolicity, boundary at infinity—that govern large-scale structure in hierarchical, networked, and negatively curved data. We propose a framework grounded in coarse geometry, the branch of mathematics studying metric spaces up to quasi-isometry: features are nonlinear functions of the distances from each point to a set of anchor points, so they read global geometry directly rather than through local aggregation. We formulate this as a parametric model with learnable anchors and scales and prove (i) stability under quasi-isometries, (ii) a universal approximation property for the distance-generated algebra on compact metric spaces, and (iii) a boundary-extension result in Gromov-hyperbolic spaces. On grid and tree graphs that share low-order local structure but differ in coarse geometry, a tanh-activated distance representation reaches 77.8± 5.8% 77.8 ± 5.8 % mean accuracy separating grid from tree topology over ten runs, versus 48.7± 5.9% 48.7 ± 5.9 % and 45.5± 5.1% 45.5 ± 5.1 % for local and spectral baselines (paired t -test p<10⁻⁵ p < 10 - 5 ); a non-saturating ReLU activation reaches 99.9± 0.4% 99.9 ± 0.4 % on the same task, and 96.2± 2.4% 96.2 ± 2.4 % separating grid from a Barabási–Albert scale-free graph. On real networks the result is scope-dependent: the representation outperforms spectral embedding on the Zachary karate club and Les Misérables networks, but is outperformed by it on the Cora and PubMed citation networks (up to ~ \!20,000 ∼ 20 , 000 nodes), whose labels track content homophily rather than coarse geometry.