Distance-Based Representation Learning with Nonlinear Feature Algebras

Abstract 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\pm 5.8\%$$ 77.8 ± 5.8 % mean accuracy separating grid from tree topology over ten runs, versus $$48.7\pm 5.9\%$$ 48.7 ± 5.9 % and $$45.5\pm 5.1\%$$ 45.5 ± 5.1 % for local and spectral baselines (paired t -test $$p<10^{-5}$$ p < 10 - 5 ); a non-saturating ReLU activation reaches $$99.9\pm 0.4\%$$ 99.9 ± 0.4 % on the same task, and $$96.2\pm 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 $$\sim \!20{,}000$$ ∼ 20 , 000 nodes), whose labels track content homophily rather than coarse geometry.