Distance-Based Representation Learning with Nonlinear Feature Algebras

Abstract

<jats:p> 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 <jats:italic>(i)</jats:italic> stability under quasi-isometries, <jats:italic>(ii)</jats:italic> a universal approximation property for the distance-generated algebra on compact metric spaces, and <jats:italic>(iii)</jats:italic> 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 <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$77.8\pm 5.8\%$$</jats:tex-math> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>77.8</mml:mn> <mml:mo>±</mml:mo> <mml:mn>5.8</mml:mn> <mml:mo>%</mml:mo> </mml:mrow> </mml:math> </jats:alternatives> </jats:inline-formula> mean accuracy separating grid from tree topology over ten runs, versus <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$48.7\pm 5.9\%$$</jats:tex-math> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>48.7</mml:mn> <mml:mo>±</mml:mo> <mml:mn>5.9</mml:mn> <mml:mo>%</mml:mo> </mml:mrow> </mml:math> </jats:alternatives> </jats:inline-formula> and <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$45.5\pm 5.1\%$$</jats:tex-math> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>45.5</mml:mn> <mml:mo>±</mml:mo> <mml:mn>5.1</mml:mn> <mml:mo>%</mml:mo> </mml:mrow> </mml:math> </jats:alternatives> </jats:inline-formula> for local and spectral baselines (paired <jats:italic>t</jats:italic> -test <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$p<10^{-5}$$</jats:tex-math> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>p</mml:mi> <mml:mo><</mml:mo> <mml:msup> <mml:mn>10</mml:mn> <mml:mrow> <mml:mo>-</mml:mo> <mml:mn>5</mml:mn> </mml:mrow> </mml:msup> </mml:mrow> </mml:math> </jats:alternatives> </jats:inline-formula> ); a non-saturating ReLU activation reaches <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$99.9\pm 0.4\%$$</jats:tex-math> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>99.9</mml:mn> <mml:mo>±</mml:mo> <mml:mn>0.4</mml:mn> <mml:mo>%</mml:mo> </mml:mrow> </mml:math> </jats:alternatives> </jats:inline-formula> on the same task, and <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$96.2\pm 2.4\%$$</jats:tex-math> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>96.2</mml:mn> <mml:mo>±</mml:mo> <mml:mn>2.4</mml:mn> <mml:mo>%</mml:mo> </mml:mrow> </mml:math> </jats:alternatives> </jats:inline-formula> 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 <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$\sim \!20{,}000$$</jats:tex-math> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>∼</mml:mo> <mml:mspace/> <mml:mn>20</mml:mn> <mml:mo>,</mml:mo> <mml:mn>000</mml:mn> </mml:mrow> </mml:math> </jats:alternatives> </jats:inline-formula> nodes), whose labels track content homophily rather than coarse geometry. </jats:p>