Neural Snowflakes: Universal Latent Graph Inference via Trainable Latent Geometries
Authors: Haitz Sáez de Ocáriz Borde
Anastasis Kratsios
Venue: ICLR 2024 poster (2024)
Keywords: Latent Graph Inference
Representation Learning
Metric Embedding
Geometric Deep Learning
Graph Neural Networks
Primary area: metric learning, kernel learning, and sparse coding
TL;DR: Trainable distance functions with universal graph embedding theorems.  These deep geometries allow for latent graph inference in GNNs, without combinatorial searches through representation spaces when learning the latent graph.

Abstract: The inductive bias of a graph neural network (GNN) is largely encoded in its specified graph. Latent graph inference relies on latent geometric representations to dynamically rewire or infer a GNN's graph to maximize the GNN's predictive downstream performance, but it lacks solid theoretical foundations in terms of embedding-based representation guarantees. This paper addresses this issue by introducing a trainable deep learning architecture, coined \textit{neural snowflake}, that can adaptively implement fractal-like metrics on $\mathbb{R}^d$. We prove that any given finite weights graph can be isometrically embedded by a standard MLP encoder. Furthermore, when the latent graph can be represented in the feature space of a sufficiently regular kernel, we show that the combined neural snowflake and MLP encoder do not succumb to the curse of dimensionality by using only a low-degree polynomial number of parameters in the number of nodes. This implementation enables a low-dimensional isometric embedding of the latent graph. We conduct synthetic experiments to demonstrate the superior metric learning capabilities of neural snowflakes when compared to more familiar spaces like Euclidean space.  Additionally, we carry out latent graph inference experiments on graph benchmarks. Consistently, the neural snowflake model achieves predictive performance that either matches or surpasses that of the state-of-the-art latent graph inference models. Importantly, this performance improvement is achieved without requiring random search for optimal latent geometry. Instead, the neural snowflake model achieves this enhancement in a differentiable manner.

Published as a conference paper at ICLR 2024
NEURAL SNOWFLAKES: UNIVERSAL LATENT GRAPH INFERENCE VIA TRAINABLE LATENT GEOMETRIES
Haitz Sáez de Ocáriz Borde* University of Oxford Oxford, UK chri 6704 4 ox ac uk
Anastasis Kratsios"
Department of Mathematics
McMaster University and the Vector Institute Ontario, Canada
kratsi oa @mema ster.
ABSTRACT
The inductive bias of graph neural network (GNN) largely encoded in its specified graph. Latent graph inference relies on latent geometric representations to dynamically rewire or infer a GNN's graph to maximize the GNN's predie- tive downstream performance, but it lacks solid theoretical foundations in terms embedding- representation guarantees. This paper addresses this issue by introducing trainable deep learning architecture, coined neural snowflake, that can adaptively implement fractal-like metrics on Rd. We prove that any given finite weighted graph be isometrically embedded by standard MLP encoder, together with the metric implemented by the neural snowflake. Further- more, when the latent graph can be represented in the feature space of suffi- ciently regular kernel, we show that the combined neural snowflake and MLP en- coder do not succumb to the curse of dimensionality by using only a low-degree polynomial number of parameters in the number of nodes. This implementation enables low-dimensional isometric embedding of the latent graph. We conduct synthetic experiments to demonstrate the superior metric learning capabilities of neural snowflakes when compared to more familiar spaces like Euclidean space.
Additionally, we carry out latent graph inference experiments on graph bench- marks. Consistently, the neural snowflake model achieves predictive performance that either matches or surpasses that of the state-of-the-arr latent graph inference models. Importantly, this performance improvement is achieved without requiring random search for optimal latent geometry. Instead, the neural snowflake model achieves this enhancement in a differentiable manner.
INTRODUCTION
Geometric deep learning (Bronstein et al., 2017; 2021) is a rapidly developing field that expands the capabilities of deep learning to encompass structured and geometric data, such as graphs, point- clouds, meshes, and manifolds. Graph neural networks (GNNs) derive their knowledge primarily from the specific graph they operate on, but many real-world problems lack an accessible ground truth graph for computation. Latent graph inference aims to address this by dynamically inferring graphs through geometric representations. Existing models lack a strong theoretical foundation and use arbitrary similarity measures for graph inference, lacking principled guidelines. A key challenge is the absence of a differentiable method to deduce geometric similarity for latent graph inference. Recently the concept of neural latent geometry search has been introduced (Sáez de Ocáriz Borde et al., 2023a), which can be formulated as follows: given a search space R denoting the set of all possible latent geometries, and the objective function LT,A(g) which evaluates the performance of given geometry g on downstream task T for machine learning model architecture A, the ob- jective is to optimize the latent geometry: gnf (g). In the context of latent graph inference R would denote the space of possible geometric similarity measures used to construct the latent graphs. Previous studies have utilized random search to find the optimal geometry in R (Kazi al., 2022; Sáez. de Ocáriz Borde et al., 2023c). However, these methods have their limitations as they "Equal Contribution.

---

Published as a conference paper at ICLR 2024
cannot infer geometry in differentiable manner, and the representation capabilities of Riemannian manifolds are constrained by certain assumptions inherent in their geometry.
Contributions. We introduce trainable deep learning architecture which we adaptively im- plement metrics on I' spaces with a fractal-like geometry, called neural snowflakes. We prove that together neural snowflake and a simple encoder enough to discover any latent graph ge- ometry. In particular, the neural snowflake implements a fractal geometry on IR in which any given finite latent weighted graph can be isometrically embedded and the elementary MLP implements that embedding. We show that in cases where the latent weighted graph has favourable geometry, the neural snowflake and MLP encoder break the curse of dimensionality by only requiring a poly- nomial number of parameters in the graph nodes to implement the isometric embedding. We note the contrast with universal approximation theorems, e.g. Yarotsky (2017); Lu et al. (2021); Shen et al. (2022); Kratsios & Papon (2022), where the number of parameters required to implement generic approximation depend exponentially on the dimension of the ambient space. Our embedding results exhibit no such exponential dependence on the dimension of the ambient space. We verify our theo- retical guarantees experimentally with synthetic metric learning experiments and graph embedding tasks. Additionally the state of the art across several latent graph inference benchmarks from the literature. This is achieved by learning the latent geometry in a differentiable manner, utilizing a single model. Thus, the neural snowflake eliminates the need to conduct costly combinatorial searches across numerous combinations of potential embedding spaces.
show that the neural snowflake and MLP encoder combination beat match
BACKGROUND
Related Work. In the field of Geometric Deep Learning, most research has relied on human anno- tators or simple preprocessing algorithms to generate the graph structure used in GNNs. However, even when the correct graph is provided, may not be optimal for the specific task, and the GNN could benefit from rewiring process (Topping et al., 2021). Latent graph inference allows models to dynamically learn the intrinsic graph structure of problems where the true graph is unknown (Wang et al., 2019; Kazi et al., 2022). This is particularly relevant in real-world applications where data might only be available in the form of pointeloud. There are several works in the literature ad- dressing latent graph inference. In particular,
can think of graph rewiring (Armaiz- Modaii-Rodriguez et al., 2022; Bi et al., 2022; Guo et al., 2023; Topping et al., 2021) as a subset of latent graph infer- ence in which an input graph is provided to the network, whereas latent graph inference in its most general form allows GNNs to infer a graph starting from only a pointcloud. When the underlying connectivity structure is unknown, traditional architectures like transformers (Vaswani et al., 2017) and attentional multi-agent predictive models (Hoshen, 2017) use a fully-connected graph. This as- sumption, however, leads challenges when training with large graphs. Generating sparse graphs can offer computationally tractable solutions (Fetaya et al., 201 8) and prevent over-smoothing (Chen et al., 2020a). Various models have been proposed tackle this problem, starting from Dynamic Graph Convolutional Neural Networks (DGCNNs) (Wang et al., 2019), to approaches that sepa- rate graph inference and information diffusion, such as the Differentiable Graph Modules (DGMs) in Cosmo et al. (2020) and Kazi et al. (2022). Recent approaches have focused on generalizing the DGM leveraging product manifolds (Sáez de Ocáriz Borde et al., 2023c;b). Latent graph inference is also referred to graph structure learning in the literature. A survey of similar methods can be found in Zhu et al. (2021), and some classical methods include LDS-GNN (Franceschi et al., 2019), IDGL (Chen et al., 2020b), and Pro-GNN (Jin et al., 2020). Moreover, recently generalizing latent graph inference to latent topology inference (Battiloro et al., 2023) has also been proposed.
Graphs. A weighted graph can be defined as an ordered pair G = (V, F, W), where V represents set of nodes (or vertices), E S {fu, v} : u, v E V} forms the collection edges (or links) within the graph, and W E + (0, oo) weights the importance of each edge. An (unweighted) graph & is weighted graph for which W ((u,v)) = for every edge {u, v} E E. The neighborhood A(u) of a node E is the set of nodes sharing an edge with w; i... (v) def. (ueV {u, v} E E].
Graph Neural Networks. To compute a message passing Graph Neural Network (GNN) layer over a grrpph 9 (excluding edge and graph level features for simplicity). the following equation typically implemented: x; (I+1)
4 x(x!")
jEN(C!") ((x!") (1) xx()). . In the given equation, & Rd Rd
2

---

Published as a conference paper at ICLR 2024
R represents a message passing function. The symbol Q denotes aggregation function, which must be permutation-invarian e.g. the sum or max operation. Additionally, & E R x IA + R represents readout function. We note that the update equation is local and relies solely on the neighborhood of the node. Both và and şo can be Multi-LLayer Perceptrons (MI.ss. In our manuscript all MLPs will use the RcLU(t) _ max(0, t} activation function, where t R. Several special cases have resulted in the development of a wide range of GNN layers: the most well-known being Graph Convolutional Networks (GCNs) (Kipf & Welling, 2017) and Graph Attention Networks (GATs) (Veličković et al., 2018).
While Riemannian manifolds have been employed for formalizing non- Euclidean distances between points, their additional structural properties, such as smoothness and infinitesimal angles, impose substantial limitations, rendering the demonstration of Riemannian manifolds with closed-form distance functions challenging. Quasimetric spaces, isolate the rele- vant properties of Riemannian distance functions without requiring any of their additional structure for graph embedding. A quasi-metric space is a set X with distance function d: X x X - [0, oo) satisfying for every x. y; E X: i) d(x, y) = O if and only if x = y. ii) d(s,, y) = d(y, x), iii) d(x, y) I =()(x,=) + y)), for some constant C' - When C 1, (X, is called a metric space, examples include Banach spaces and also, every (geodesic) distance on Rieman- nian manifold satisfies (i)-(iii) Conversely, several statistical divergences are weaker structures than quasi-metrics since they fail (ii). and typically fail (íii); see e.g. (Hawkins et al., 2017, Proposition > 1; otherwise (iii), is called the
Quasi-Metric Spaces.
A.2). Property (iii) is called the C-relaxed triangle inequality triangle inequality. Quasi-metric spaces typically share many of the familiar properties of metric umiform-continuity spaces, such as similar notions of convergence, uniform continuity of maps between quasimetric spaces, and compactness results for functions between quasimetric spaces such as Arzela-Ascoli theorems (Xia, 2009). The next example of quasimetric spaces are called metric snowflakes.
Example (Xia (2009)). Let p > 0 and (X, d) be a metric space. Then, (X,d)) is quasimetric space with C' = 2 if 1. When 0 < p S 1, then (X, is metric space; whence, C C= 1.
Snowflakes simple tool for constructing new (quasi) metric spaces from old ones with the following properties. Unlike products of Riemannian manifolds, a snowflake's geometry can be completely different than the original untransformed space's s geometry. Unlike classical methods for constructing new distances from old ones, e.g. as warped products in differential geometry (Chen, 1999: Alexander & Bishop, 1998), snowflakes admit simple fooee-ffrm distance functions.
Proposition 1 (Snowflakes are Metric Spaces- (Weaver, 2018, Proposition 2.50)). Let f: 10, x) - [0, oo) be continuous, concave, monotonically increasing function with /(0) O, and let (X, d)
be a metric space; then, dj X x X + R. is a metric on X dg(x,, 2) def. [(d(z, f)r any x, = X.
ADAPTIVE GEOMETRIES VIA NEURAL SNOWFLAKES
We overcome one of the main challenges in contemporary Geometric Deep Learning, namely the problem of discovering a latent graph which maximizes the performance of a downstream GNN by searching a catalogue of combinations of products of elementary geometries (Gu et al., 2019); in an attempt to identify which product geometry the latent graph can be best embedded in (Sáez de Ocáriz. Borde et al., 2023b;c). The major computational hurdle with these methods that they pose a non non-differentiable combinatorial optimization problem with a non-convex objective, making them computationally challenging to scale. Therefore, by designing a class of metrics which are differentiable in their parameters, we can instead discover which geometry best suits learning task using backpropagation. Core to this is a trainable metric on Rd, defined for any x. E Rd by
||x - y y/l.a....... def. (Ci (1 vll vlll- O2 || - yl1 + C3 log(1 + | - vll 1+|pl
Bounded
Fractal
Trregular Fractal
C1, C2, Cg,7 not all of which are O and C = (C.) The train- able metric in equation coined the snowflake activation, is the combination of three components, a bounded geometry, a fracial geometry, and an irregular fracial geometry part; as labeled therein. The first bounded geometry can adapt to latent geometries which are bounded akin to spheres, the second fractal geometry component can implement any classical snowflak as in Example I (where
where 0 <
3

---

Published as a conference paper at ICLR 2024
0 < p S 1) and the irregular fractal adapts to latent geometries much more irregular where the dis- tance between nearby points grows logarithmically at large scales and exponentially at small scales ! By Proposition 1, p O, the distance in equation is metric on R For p > 0 ( II..llo........)
a quasi-metric space with 20-1-relaxed triangle inequality, by Example 1.
3.1 NEURAL SNOWELAKES
We leverage the expressiveness of deep learning. by extending the trainable distance function equa- tion to a deep neural network generating distances on TR. called the neural snowflake.
We begin by rewriting equation I as a trainable activation function o, R + [0, oo) which sends on any vector R for J E N+, to the J x 3 matrix (a,b(u) whose jth row is
(2) (1 e 1 | log(1 + luy1)))
The parameters 0 < a and 0 f b 2 are trainable.
We introduce neural network architecture leveraging the "tensorized" snowflake activation func- tion in equation 2, which can adaptively perturb any metric. To ensure that the neural network model always preserves the metric structure of its input metric, typically the Euclidean metric on Rd we must constrain the weighs of the hidden layers to ensure that the model satisfies the con- ditions of Proposition 1. Building on the insights of monotone (Daniels & Velikova, 2010), "input convex" (Amos et al., 2017) neural network architectures, and monotone-value (Weissteiner et al., 2022) neural networks, we simply require that all hidden weights are non-negative and do not all vanish. Lastly, the final layer of our neural snowflake model raises the generated metric to the (p))) power as equation This allows the neural snowflake to leverage the flexibility of quasi-metrics, whenever suitable. They key point here is that by only doing so on the final layer, we can explicitly track the relaxation of the triangle inequality discovered while training. That is, as in Example 1, C' 2p if and C 1 otherwise. Putting it all together, neural snowflake is map f [0, 0o) - [0, 20), with iterative representation
f(t) - lpl
4 = B6x
Borbb (A (4))
for i = I,...,
to t
(0) is d; d;-1 matrix, B(i) is a d; x d,-mttxix and ((0) a x matrix all of which have non-negative weights and lt-least one non-zero weight, p E R; furthermore, for i = 1,.... T, < a, < 1, < b, S 1, di,..., d, E N₃, and do = = dj. We will always treat the neural snowflake as synonymous with the trainable distance function || alls
where for i = 1,..., 1,
del [([[ - yll),
where x, y E IRd for some contextually fixed and f is as in equation 3.
INFERABILITY GUARANTEES
This section contains the theoretical guarantees underpinning the neural snowflake graph inference model. We first show that it is universal, in the sense of graph representation learning, which we formalize. We then derive a series of qualitative guarantees showing that the neural snowflake graph inference model requires very few parameters infer any latent weighted graph. In particular, neural snowflakes require a computationally feasible number of parameters to be guaranteed to work.
4.1 UNIVERSAL GRAPH EMBEDDING
Many graph inference pipelines depend on preserving geometry representations or encodings within latent geometries when inferring the existence of an edge between any two points (nodes) in a point cloud. Therefore, the effectiveness of any algorithm this family of encoders hinges on its capacity to accurately approximately represent the geometry of the latent graph. In this work, we demonstrate that the neural foweeake can infer any latent graph in this way. Thus, we formalize what
Note that log(1 + || - vll) se 1 e [z-sil when ( Rs || - vl1-
4

---

Published as a conference paper at ICLR 2024
it means for graph inference model to be able to represent any latent (weighted) graph structure in R" based on a class of geometries R. For any D E N+, we call a pair (C, a graph inference model, on RP,, if R is family of quasi-metric spaces, and @ is family of maps with domain R' & and codomain in some member (R, dR) of R. Whenever RDD is clear from the context, we do not explicitly mention it.
4.1.1 UNIVERSAL RIEMANNIAN REPRESENTATION IS IMPOSSIBLE
Our primary qualitative guarantee asserts the universality of the graph inference model (e, R), where & represents the set MLPs into Rd with ReLU activation functions, and R comprises all (IR", I (t), where is neural snowflake; for integers d N+. We now formalized what is meant by a universal graph embedding model.
Definition 1 (Universal Graph Embedding). A graph inference model (E,R) R) is universal if: for every non-empty finite subset V C R and every connected weighted graph G = (V, E, W) there a (quasi-mettn metric) representation space (R, dR) E R and an encoder & R - R in E satisfying
dg(u u) dx (E
VuVEVV.
Our interest in universal graph inference models lies in their ability to infer graph edges. This is done by first learning an embedding & E & into some representation space (R, dæ) E R and subsequently sampling edges based on nearest neighbors within the aforementioned embedding.
One technical point worth noting is that, when forming sets of nearest neighbors, ties between equidistant points are broken arbitrarily. This is accomplished by indexing (possibly randomly) the graph's ss vertices and selecting the first few nearest points based on the ordering of that index, similar to the approach in Fakcharoenphol et al. (2004).
The formalization of this reconstruction procedure, in Theorem 1, uses the following notation. For every positive integer N, we denote the first N positive integers by [N] def. (1...., ; N). For every quasi-metric (representation) space (R. dR) each point x E R, and each radius r 2 0 the closed
unit ball about x of radius is B& (x, r) def. {u E R dx (x(22)) S r).
Theorem 1 (Generic Graph Reconstruction via Universal Graph Inference Models). Fix D E N. and a latent graph inference model (É, R) on PR For every non-empty finite subset V C RR,, every graph G EV,E), and each index V {vx J.N there exists: a quasi-metric (representation) space (R, dR) R and an encoder E : RR. > RR in E such that: for each i [N] there is (number of nearest neighbours) kū E [N] satisfying
U, E E E+ i and dx (E(u)) S r(ks)
where r(ks) del. inf (r 00 HUEV dx(E(()), <r) 2 ki} and where i del. [N): # (BBx(u, r(:)) (u.))_n) < k.).
Theorem shows that if latent graph inference model is universal, then can be used to reconstruct the edge set of any latent graph structure by first embedding the vertices/point-clous into a latent representation space and then joining nearest neighbours. The next natural question is: "How does one build a universal latent graph inference model which is differentiable?"
It known that the family of Euclidean spaces Ω. {(EE, || [Dae,,, are not flexible enough to isometrically accommodate all weighted graphs; even if è is the family of all functions from any E. into any Euclidean space (RR' || II). This is because, some weighted graphs do not admit isometric embeddings into any Euclidean space (Bourgain et al., 1986; Linial et al., 1995; Ma- toušek, 1997). Even infinite-dimensionn
need not be enough, since for every an n-point weighted graph which cannot be embedded in the Hilbert space ee with distortion less than (log(n)) log( (Bourgain, 1985, Proposition 2). In particular, it cannot be isometri- cally embedded therein. For example, any l-leaf tree embeds in d-dimensional Euclidean space with distortion at-least (((2/d). In contrast, any finite tree can embed with arbitrary low-distortion into the hyperbolic plane (Kratsios et al., 2023b), which is a particular two-dimensional non-flat Rie- mannian geometry. Several authors (Sarkar, 2012) have shown that cycle graphs can be embedded isometrically in spheres of appropriate dimension and radius (Schoenberg, 1942), or in the product
N+, there
5

---

Published as a conference paper at ICLR 2024
of spheres (Guella et al., 2016), but they cannot be embedded isometrically in Euclidean space (En- flo, 1976). These observations motivate geodesic deep learners (Liu et al., 2019; Chamberlain et al., 2017: Chami et al., 2019; Sáez de Ocáriz Borde et al., 2023c;b) and network scientists (Verbeek & Suri, 2014) to use families of Riemannian representation spaces R in which it is hoped that general graphs can faithfully be embedded, facilitating embedding-basee nately, 5 nodes and 5 edges are enough to construct a graph which cannot be isometrically embedded into any non-pathological Riemannian manifold.
latent graph inference. Unfortu-
Proposition 2 (Riemannian Representation Spaces are Too Rigid to be Universal). For any D E N+ and any 5-point subset V of RD, there exists set of edges E on such that:
(i) the graph G = EV connected
(ii) for every complete² and connected smooth Riemannian manifold (R,g) there does not exist isometric embedding vp (V, dg) + (R, dR)
where dg and dæ respectively denote the shortest path (geodesic) distances on G and on (R, g).
In other words, Proposition shows that if R is any set of non-pathological Riemannian manifolds and @ any set of functions from IR into any Riemannian manifold (R, g) in Ri the graph inference model (e, 9) is not universal. Furthermore, the graph "breaking its universality" is nothing obscure but a simple 5 node graph. Note that, no edge weights (not equal to 1) are needed in Proposition 2.
Figure I: Explanation of Proposition 2: The Graph of Proposition cannot be isometrically embedded into any complete and connected (smooth) Riemannian manifold. Briefly, the issue is that any isometric embedding into such Riemannian manifold must exhibit pair of geodesics one of which travels from the embeddings of node C' to node A. while passing through the embedding node D; and likewise, the other of which travels from the embedding of node C' to node B and again passes through the embedding of node D. However, this would violate the local uniqueness of geodesics in such Riemannian manifold. around the embedding of node D (implied by the Picard-I Ficard-Lindellf inndllöf theorem for ODEs); thus no such embedding can exist.
Proposition improves on (Kratsios et al., 2023a, Propositions 13 and 15) since the latter only show that no compact connected Riemannian manifolds (e.g. products of spheres) and no connected Riemannian manifold with bounded non-positive sectional curvatures (e.g. products of hyperbolic spaces) can accommodate certain sequences of expander graphs (see (Kratsios et al., 2023a, Remark 14)). However, those results do not rule out more complicated Riemannian representation spaces; e.g. the products of spheres, hyperbolic, and Euclidean spaces recently explored by Gu et al. (2019); Tabaghi et al. (2021); Di Giovanni et al. (2022); Sáez de Ocáriz Borde et al. (2023c),
4.1.2 UNIVERSAL REPRESENTATION Is POSSIBLE WITH NEURAL SNOWFLKKE
Juxtaposed against Proposition 2, our first main result shows that together, neural snowflake and MLPs, are universal graph embedding models.
Theorem (Universal Graph Embedding). Let D E N4 and G be a weighted graph with V C R with I N4 vertices. There exists an embedding dimension N4,, an MLP E RRD Rd with ReLU activation function, and a neural snowflake f such that
dg(u,v) = ||E(u) E
for each u, v E V. The (TR., (1.1111))) supports 200og(11 A ")) rrelaxed triangle inequality. IfG is a tree then (Rd. I1I )] instead supports an 8-triangle inequality.
Comparison: State-of-the-Art Deep Embedding Guarantees. Recently Kratsios et al. (2023a) built on Andoni et al. (2018) and proposed universal graph embedding model which uses the
Here, complete is meant in the sense of metric spaces; i.e. all Cauchy sequences in complete metric space have limit therein.

---

Published as a conference paper at ICLR 2024
transformer architecture of Kratsios (2021) to represent graphs in the order 2- W-ssserstein space on RR3 The drawbacks of this approach are that the metric is not available in closed-form, it is computationally infeasible to evaluate exactly for large graph embeddings, and it is still challenging to evaluate approximately (Cuturi, 2013). In contrast, Theorem 2 guarantees that a simple MI.P can isometrically emhedding any weighted graph into finiteddimensional representation space with closed-form distance function explicitly implemented by a neural snowflake.
Comparison: MLP without Neural Snowflake. We examine the necessity of the neural snowflake in Theorem 2, by showing that the MLP alone cannot isometrically represent any weighted graph into its natural output space; namely some Euclidean space.
Theorem 3 (Neural Snowflakes & MLPs Are More Powerful For Representation Learning Than MLPs). Let d, D E 14. The following hold:
(i) No Less Expressive Than MLP: For any weighted graph G = =V, EVE,W) with V S CRD, if there is MLP & RDD - RRd which isometrically embeds then there is a neural snowflake I and an MLP E TR. - Rd which isometrically embeds G into (TR., Ill (ls).
(ii) Strictly More Expressive Than MLP: There exists a complete weighted graph G = (V. E, W) with V C RDD by any MLP &. -RD + Rd but for which there exists a neu- ral snowflake f and an MLP & IR. Rd that isometrically embeds into (RP, || -ll))
4.2 ISOMETRIC REPRESENTATION GUARANTEES BY SMALL NEURAL SNOWFLAKES
Theorem 2 offers a qualitative assurance that the neural snowflake can represent any finite weighted graph. We now show that any weighted graph which can be isometrically represented in the latent geometry induced by kernel regressors, can be implemented by neural snowflake. We assume that the latent geometry of the weighted graph is encoded in a low-dimensional space and the distances in that oow-dimensional space given by a radially symmetric and positive-definite kernel.
Assumption 1 (Latent Eadially-Symmettry Kernel), There are d, D E N+, feature map 4 RDD + Rd, and a non-constant pessitive-definiie function' f: [0, 20) - [0, 0o) satisfying
dg(æ,, y) = f(11(x))(((1)))
for every x. E Rdd; where f(()
del f(0) - f(1).
Several satisfy Assumption 1, as we emphasize using two exotic examples (Appendix D). Example 2. The map f(t) (1 +
Ek= k= ) satisfies Assumption 1 for any K E N4 and
S Fi, ri,...,TK. 3 <
Example 3. The map [(() exp
-att- Tog(t)
satisfies Assumption 1, for all a >> 0.
We find that the neural snowflake implement isometric representation of the latent geometry, as in Theorem 2, using small number of parameters comparable to Theorem 5.
Theorem (Quantitative Embedding Guarantces for Bounded Metric Geometries). Let D, d E N G' be finite weighted graph with V IR and suppose that Assumption I (or equation 2) holds. Then, there is a neural snowflake (E, f) satisfying
[b((v) ((u)ll, ||E(w) - E(u)lfF
for every u, u E V. Furthermore, the depth and width of & and I are recorded in Table 1.
4.3 REPRESENTATION GUARANTEES LEVERAGING DISTORTION
Theorem shows the neural snowflake and an simple MLP are universal graph embedding models. By allowing the neural snowflake and MLP some possible slack to distort the latent graph's geom- etry, either by stretching or contracting pairwise distances ever so slightly, we are able to derive explicit bounds on the embedding dimension d and on the complexity of the neural snowflake and MLP.
positive-definite function, map f R - for which each (S(z) x1)) a positive-definite matrix, for every N e N4 and each #i.-... N.N E IR.
7

---

Published as a conference paper at ICLR 2024
Theorem 5 (Quantitative Approximately Isometric Embeddings for Weighted Graphs). Let G (V. W) be a weighted graph N E 44 nodes, a non-negative weighting function W, and V C Rd. For every < < 2, there exists an MLP with ReLU activation function E R2d + (O(log(dim()))) and snowflaking network f .R- - IR such that: for every x, u E V
da(ar u) S
S DP do(
where D E ( [ing (d)())))))))) and (TR", 11 (15)) is a quasi-metric space satisfying the 2p inequality. The depth and width of and f are recorded in Table I.
28-1-1riice -trianlee
Table I: Complexity of the Neural Snowflake and MLPs. Here, O suppresses a constant depending only on D
and Cg > 0 depends only on g (explicit constants are given in Appendix B).
Geometry
Net.
Hidden Layers (Depth -1)
Width
Theorem
General
f
((1)
5
Bounded
f
((1)
O(P)
4
All
3
log (P O(DI + d)
4 and 5
The complexity of the neural snowflake and MLP are reported in Table 1. Theorem shows that the neural snowflake can match the best known embedding guarantees by a deep learning model with values in a curved dimeniioddde space (Kratsios al., 2023a, Theorem 4), both in terms of distortion and the number of parameters. The neural snowflake's 's adaptive geometry allows for the representa- tions to be implemented in ([log(dim(G)) dimensions and the implemented representation space (R4, I]s) has an explicit closed-form distance function making it trivial to evaluate; unlike the distance function in the representation space of Kratsios et al. (2023a). Our guarantees show that neural snowflakes theoretically represent any weighted graph; either isometrically nearly isometrically with provable few parameters.
Discussion
Comparison with the Best Proven Deep Representation.
EXPERIMENTAL RESULTS
Next, we validate our embedding results through synthetic graph experiments, and we demonstrate how the combined representation capabilities of neural snowflakes and MLPs can enhance existing state-of-the--rt latent graph inference pipelines.
Synthetic Embedding Experiments: Neural Snowflakes vs Euclidean Graph Embedding Spaces. To assess the effectiveness of neural snowflakes as well as to compare their performance with that of MLPs in approximating metrics using Euclidean space, we conduct synthetic graph embedding experiments. Specifically, we focus on fully connected graphs, where the node coor- dinates randomly sampled from multivariate Gaussian distribution within a 100-dimensional hypercube in Euclidean space, denoted as 1000 The weights of the graphs are computed accord- ing to the metries in Table 2. In the leftmost column, the MLP model projects the node features in TR. 100 to R22 and aims at approximating the edge weights of the graph using the euclidean dis- MLP(y) between the projected features. In the central column, the neural snowflake f learns a quasi-metric based on the input Euclidean metric previously mentioned in IR?, [([MLP((x MLP( (l)) Finally, in the rightmost column the neural snowflake learns based on the Euclidean distance between features in I 100, f[|x l). In order to demonstrate the superior embedding capabilities of neural snowflakes compared Euclidean spaces, we intentionally equip the MLP in the first column with a significantly larger number of model parameters than the other models. This is done to highlight the fact that, despite having fewer learnable parameters, neural snowflakes outperform Euclidean spaces by orders of magnitude. Furthermore, the results of our experiments reveal that neural snowflakes exhibit remarkable flexibility in learning metrics even in lower-dimensional spaces such as IR... This is evident from the similarity of results obtained in the rightmost column (representing IR 100) compared to those achieved in the case of learning the metric in IR?. Additional information regarding these embedding experiments can be found in Appendix I.
tance ||MLP(x)
Graph Benchmarks. In this section, we present our findings on using Neural Snowflakes compared to other latent graph inference models. Our objective is evaluate the representation power offered
8

---

Published as a conference paper at ICLR 2024
Table 2: Results for synthetic graph embedding experiments for the test set. The Neural Snowflake models able to learn the metric better with substantially lesser number model parameters.
Neural Snow flake (+ ML.P)
Neural Snowflake
No. Parameters
5422
4169
847
Embedding space, R
Metric
Mcan Square Emheddding Error
xx vll log(1 + ||x v
1.3196
0.0034
0.0029
xx yll log(1 + ||x yll
1,2555
0.0032
0.0032
0.1738
0.00004
0.00004
1 exp >
-1lx-vi1-11
0,3249
0.00008
0.00008
0.0315
0.00005
0.00005
0.00002
0.00002
by various latent space metric spaces, and thus, we contrast our results with the original DGM (Kazi al., 2022) and its non-Euclidean variants (Sáez de Ocáriz Borde et al., 2023b;e). We also introduce a new variant of the DGM which uses a snowflake activation on top of the classical DGM, to equip the module with a snowflake quasi-metric space. We ensure fair evaluation, by conducting all experiments using the same GCN model and only modify the latent geometries used for latent graph inference. We take care to maintain consistency the number of model parameters, as well as other training specifications such as learning rates, training and testing splits, number of GNN layers, and so on. This approach guarantees that all comparisons are solely based on the metric (or quasi-metric) space utilized for representations. By eliminating the influence of other factors, can obtain reliable and trustworthy experimental results. A detailed and systematic analysis of the results is provided in Appendix I.
We first present results from latent graph inference on the well-known Cora and CiteSeer homophilic graph benchmarks. We use consistent latent space dimensionality of 8 and perform the Gumbel top-k trick for edge sampling with a k value 7. The models all share the same latent space dimen- sionality, differing solely in their geometric characteristics. In scenarios where product manifold is used, the overall manifold is constructed by amalgamating two 4-dimensional manifolds through Cartesian product. This yields total latent space dimensionality of 8. This methodology ensures an equitable comparison based exclusively on geometric factors. All other parameters, comprising network settings and training hyperparameters, remain unaltered. For all DGM modules, GCNs are employed as the underlying GNN diffusion layers. Table 3 displays the results for Cora and CiteSeer, leveraging the original dataset graphs as inductive biases.
Table 3: Results for Cora and CiteSeer leveraging the original input graph as an inductive bias.
Cora
CiteSeer
Model
Metic Space
Accuracy (%) = Standard Deviation
Neural Snowflake
Snowflake
87.07=5.45
74.76. 74
DGM
Snowflake
85.41+3.70
74.19:2.00 06
DGM
Euclidean
85.77=3.64
73.67=2.30
DGM
Hyperboloid
85.25
73.4662179
DGM
Poincure
86.07=a.63
71. 21.3333.
DGM
Spherical
76.14:22.8
T3.1322.0
DGM
Euclidean x Hyperboloid
84.33++2.56
73.20=2.16
DGM
Hyperboloid Hyperbolood
$1.59
74.42=1.s
GCN
Euclidean
83.50.2.00
70.03=2201
Next we perform experiments Cora and CiteSeer without considering their respective graphs, that is, the latent graph inference models only take pointclouds as inputs this case. We also in- clude results for the Tadpole and Aerothermodynamice datasets used in Sáez de Ocáriz Borde et al. (2023c). Note that in these experiments all models used GCNs and a fixed latent space dimension- ality of 8, unlike in the original paper which uses larger latent spaces and GAT layers. The effect of changing the latent space dimensionality is further explored in Appendix I. For both Tadpole and Aerothemodynamics, the Gumbel Top-k algorithm samples 3 edges per node. See Table 4.

---

Published as a conference paper at ICLR 2024
Table 4: Results for Cora and CiteSeer, and the real- world Tadpole and Aerothermodynamies datasets, without leveraging the original input graph as an inductive bias.
Cora
CiteSeer
Tadpole
Aerothernodynamies
Model
Metric Spuce
Accuracy (%) + Standard Deviation
Neural Snowtlake
Snowflake
71.22.24.2
67.80=2.44
90.02_...1
88 65.3 10
DGM
Snowflake
69.51
66.86
91.61=4.86
88,55
DGM
Euclidean
05.37
68. 2.800
59. 59.29
28.28::2.61
DGM
Hyperboloid
70.00:4.04
68.34:1.59
88.75st5.11
88,29::2.65
DGM
Poincare
65.74=4.02
61.63+2.95
56.96=5.30
89. 10.000222.
DGM
Spherical
37.03
20.00a4.13
82.32s11.74
88. 88.37133:00
DGM
Fuclidean x Hyperboloid
62.18:2.61
65.7222.06
90.71=3.17
88.20:13.05
DGM
Hyperboloid Euclidean
67.14:4.19
61.33+9.44
69.64
89. 53-.55+22.. 52
MLP
58.9243.28
59.48+2.14
87.70+3.45
80,9 80.9048.34
From the results, we can see that models using snowflake metric spaces are consistently amongst the top performers for both Cora and CiteSeer. On the other hand, employing non-learnable metric spaces necessitates conducting exploration of various latent space geometries to achieve optimal outcomes, since there is no metric space that consistently outperforms the rest regardless of the dataset. In our synthetic experiments, we have clearly demonstrated the remarkable advantage of neural snowflakes in learning metric spaces with enhanced flexibility, when compared to Euclidean space. In the context of latent graph inference, this distinction is not pronounced as observed in the synthetic experiments. This can be attributed to the suboptimal nature of the Gumbel Top-k edge sampling algorithm (Appendix E), a topic discussed in other research works (Kazi et al., 2022: Bat- tiloro et al., 2023), which essentially introduces form of "distortion" to the learned metric. Yet, it worth noting that the development of improved edge sampling algorithms to foster better synergy between metric space learning and graph construction is not the primary focus of this paper. Instead, our emphasis on introducing a more comprehensive and trainable metric space and integrating with existing edge sampling techniques.
6 CONCLUSION
Our theoretical analysis showed that small neural snowflake, denoted as S. can adaptively im- plement fractal-like geometries IIs on Rd, which are flexible enough to grant a small MLP the capacity isometrically embed any finite graph. We showed that the non-smooth geometry im- plemented by the neural snowflake is key by showing that there are simple graphs that cannot be isometrically embedded into any smooth Riemannian representation space. We then explored sev- eral cases in which the combination of neural snowflakes and MLPs requires a small number of total parameters, independent of ambient dimensions, to represent certain classes of regular weighted graphs. We complemented our theoretical analysis by extensively exploring the best approaches to implement neural snowflakes, ensuring stability during training, in both synthetic and graph bench- mark experiments. We also introduced snowflake activation that can easily be integrated into the DGM module using differentiable distance function, enabling the DGM to leverage a snowflake quasi-metric. We conducted tests on various graph benchmarks, systematically comparing the effec- tiveness of snowflake quasi-metric spaces for latent graph inference with other Riemannian metrics such as Euclidean, hyperbolic variants, spherical spaces, and product manifolds of model spaces. Our proposed model is consistently able to match or outperform the baselines while learning the latent geometry in differentiable manner and without having to perform random search to find the optimal embedding space.
Note that experiments were conducted in accordance with the differentiable graph module framework for discrete edge sampling as proposed by Kazi et al. (2022). Our primary objective was to compare the representation capabilities of various (metric) spaces, while keeping all other model architecture choices constant. Recently, the NodeFormer (Wu et al., 2023) architecture was introduced, enabling the scalability of latent graph inference to large graphs. However, this de- velopment is slightly tangential to the research presented in this work, which focuses on analyzing the geometric characteristics of different embedding spaces. We propose considering the incorpo- ration of the geometric notions discussed in this work into new scalable architectures, such as the Former, as part of future research.
10

---

Published as a conference paper at ICLR 2024
7 ACKNOWLEDGMENT AND FUNDING
AK acknowledges financial support from the NSERC Discovery Grant No. RGPIN-2023-04455 and their McMaster Startup Funds. The authors would also like thank Giulia Livieri for her helpful feedback.
REFERENCES
Ben Adcock, Simone Brugiapaglia, Nick Dexter, and Sebastian Moraga. Deep neural networks are effecttve at learning high-dimensional hilbert-valued functions from limited data. arXiv preprint arXiv:2012.0608) 2020.
Stephanie B Alexander and Richard I. Bishop. Warped products of hadamard spaces. manuscripta mathematica, 96:487-505, 1998.
Brandon Amos, Lei Xu, and Zico Kolter. Input convex neural networks. In International Confer- ence on Machine Learning, pp. 155. PMLR, 2017.
Alexandr Andoni, Assaf Naor, and Ofer Neiman. Snowflake universality of Wasserstein spaces. Ann. Sci. Éc. Norm. Supér. (4), 51(3))657-770, 2018. ISSN 24033/asems.2363. URL httpt::t////ttt.tt www.oorgg/oo.ooo htt///11.2223///// 24033/asens 2363.
doi: 10.
Adrián Rodriiuz Ahmed Begga, Francisco Escolano, and Nuria Oliver. Diffwire: Inductive graph rewiring via the lovász bound. In LOG IN, 2022.
Claudio Battiloro, Indro Spinelli, Lev Telyatnikov, Michael Bronstein, Simone Scardapane, and Paolo Di Lorenzo. From latent graph latent topology inference: Differentiable cell complex module, 2023.
Wendong Bi, Lun Du, Qiang Fu, Yanlin Wang, Shi Han, and Dongmei Zhang. Make heterophily graphs better gnn: graph rewiring approach. ArXiv, abs/2209.0822 082264, 2022.
Helmut Bolcskei, Philipp Grohs, Gitta Kutyniok, and Philipp Petersen. Optimal approximation with sparsely connected deep neural networks. SIAM Journal on Mathematics of Data Science, 1(1): 8-45, 2019.
Bourgain. On Lipschitz embedding of finite metric spaces in Hilbert space. Israel Math., 52 (1-2):46-52, 1985. ISSN 0021-2172. doi: 10. 10.1007//F002776078. URL htttps:/ /do.. org/ www-10000FF2276077
J. Bourgain, V. Milman, and H. Wolfson. On type of metric spaces. Trans. Amer. Math. Soc., 294(1):295-317, 1986. ISSN 0002-9947,1088-66 10586680. doi: 10.2307/2000132. URL https:
//doi. 100 230072200012..
Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge University Press, Cambridge, 2004. ISBN 0-521-83378-7. doi: 10.1077/CB097805118444 URL https: ///oii.org/1l 10. 1017111057700111104400
Michael M. Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geo- metric deep learning: Going beyond euclidean data. IEEE Signal Processing Magazine, 34(4): 18-42, 2017. doi: 1 10.1199//P.211.22999444
Michael M. Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković. Geometric deep learning: Grids, groups, graphs, geodesics, and gauges, 2021.
Benjamin P. Chamberlain, James Clough, and Mare Peter Deisenroth. Neural embeddings of graphs in hyperbolic space. ArXiv, 2017.
Ines Chami, Rex Ying, Christopher Ré, and Jure Leskovec. Hyperbolic graph convolutional neural networks, 2019.
Benjamin Charlier, Jean Feydy, Joan Alexis Glaunès, François-David David Collin, and Ghislain Durif. Kernel operations on the gpu, with autodiff, without memory overflows. Journal of Machine Learning Research, 22(74):1-6, 2021.
11

---

Published as a conference paper at ICLR 2024
Chien-Hsiung Chen. Warped products of metric spaces of curvature bounded from above. Transac- tions of the American Mathematical Sociery, (5111):477774444 1999.
Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, and Xu Sun. Measuring and relieving the over- smoothing problem for graph neural networks from the topological view. In AAAI, 2020a.
Yu Chen, Lingfei Wu, and Mohammed Zaki. Iterative deep graph learning for graph neural networks: Better and robust node embeddings. ArXiv, abs/2006. 1006..130,,, 2020b.
Luca Di Cosmo, Anees Kazi, Seyed-Ahmad Ahmadi, Nassir Navab, and Michael M. Bronstein. aatent-graph learning for disease prediction. MICCAI, 2020.
Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. Advances in neural information processing systems, 26, 2013.
Hennie Daniels and Marina Velikova. Monotone and partially monotone neural networks. IEEE Transactions on Neural Networks, (116)))06-91,, 2010.
Ingrid Daubechies, Ronald Vorere, Simon Foucart, Boris Hanin, and Guergana Petrova. Nonlinear approximation and (deep) relu networks. Constructive Approximation, 55(1):127-172, 2022.
M Deza and Hiroshi Maehara. Metric transforms and euclidean embeddings. Transactions of the American Mathematical Society, 317(2):661-671, 1990.
Francesco Di Giovanni, Giulia Luise, and Michael Bronstein. Heterogeneous manifolds for curvature-awarc graph embedding, 2022.
Dennis Elbrächter. Dmytro Perekrestenko, Philipp Grohs, and Helmut Böleskei. Deep neural net- work approximation theory. IEEE Transactions on Information Theory, 37(5):251122623 2021.
Enflo. Uniform homeomorphisms between Banach spaces. In Séminaire Maurey-Schwand ( (1975- 1976), Espaces L", applications radonifiantes et géométrie des espaces de Banach,, pp. Exp. No. 18, 7. 1976.
Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar. Approximating metrics by tree metrics. ACM SIGACT News, 35(2):60-70, 2004.
Fetaya, Elias Wang, K. C. Welling, Michelle Zemel, Thomas Kipf, Ethan Fetaya, Kuan- Chinhhhieh Wang, Max Welling, and Richard S. Zemel. Neural relational inference for interacting systems. arXiv: Machine Learning, 2018.
Luca Franceschi, Mathias Niepert, Massimiliano Pontil, and Xiao He. Learning discrete structures for graph neural networks. In 201M,,2019.
Luca Galimberti, Giulia Livieri, and Anastasis Kratsios. Designing universal causal deep learning models: The case of ddfinie-dimensionne dynamical systems from stochastic analysis. arXiv preprint arXiv:2210. 13300, 2022.
Albert Gu, Frederic Sala, Beliz Gunel, and Christopher Ré. Learning mixed-curvature representa- tions in product spaces. In ICLR, 2019.
J. C. Guella, A. Menegatto, and A. P. Peron. An extension of theorem of Schoenberg products of spheres. Banach J. Math. Anal., 10(4):671-685, 2016. ISSN 2662-2033 doi: 10.1215/ 17358787-3649261 URL https:ttpt...
Jiayan Guo, Lun Du, Wendong Bi, Qiang Fu, Xiaojun Ma, Xu Chen, Shi Han, Dongmei Zhang, and Yan Zhang. Homophily-oriente heterogeneous graph rewiring. Proceedings of the ACM Web Conference 2023, 2023.
Jeff Hawkins, Subutai Ahmad, and Yuwei Cui. A theory of how columns in the neocortex enable learning the structure of the world. Frontiers in Neural Circuits, 11, 2017.
Yedid Hoshen. Vain: Attentional multi-agent predictive modeling. In NIPS, 2017.
12

---

Published as a conference paper at ICLR 2024
Wei Jin, Yao Ma, Xiaorui Liu, Xianfeng Tang, Suhang Wang, and Jiliang Tang. Graph structure learning for robust graph neural networks. Proceedings of the 26th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, 2020.
Jürgen Jost. Riemannian geometry and geometric analysis. Universitext. Springer, Cham, seventh 978-3-319-61860-9, doi: 10. 00.1007/978--331--6166 1007/ 3 99119888---11-----------9----119
edition, 2017. ISBN wtt.:o/oo//............o/
URL httph:tt////mmm //oi/iiii// www.oooogooooeeee
Anees Kazi, Luca Cosmo, Seyed-Ahmad Ahmadi, Nassir Navab, and Michael Bronstein. Differ- entiable graph module (DGM) for graph convolutional networks. IEEE Transactions Pattern Analysis and Machine Intelligence, pp. 1-1, 2022.
Thomas Kipf and Max Welling, Semi-supervised classification with graph convolutional networks. ArXiv, 2017.
Wouter Kool, Herke van Hoof, and Max Welling. Stochastic beams and where find them: The gumbel-top-k trick for sampling sequences without replacement, 2019.
Anastasis Kratsios. Universal regular conditional distributions. arXiv preprint arXiv:2105.07743, 2021.
Anastasis Kratsios and Leonie Papon. Universal approximation theorems for differentiable geomet- ric deep learning. Journal of Machine Learning Research, 23(196):1-75 2022.
Anastasis Kratsios, Valentin Debarnot, and Ivan Dokmanić. Small transformers compute universal metric embeddings. Jourmal of Machine Learning Research, 24(170):1-48, 2023a. URL http: // //jmlr. otg/ pttpr//apprss//244
246 html.
Anastasis Kratsios, Ruiyang Hong, and Haitz Sáez de Ocáriz Borde. Capacity bounds for hyperbolic neural network representations of latent tree structures, 2023b.
Krauthgamer, JR Lee, M Mendel, and A Naor. Measured descent: embedding method for finite metrics. Geometric & Functional Analysis GAFA, 5(44)83998588 2005.
Enrico Le Donne and Tapio Rajala. Assouad dimension, Nagata dimension, and uniformly close metric tangents. Indiana Univ. Math. J., 64(1):21-54, 2015, ISSN 0022-2518. doi: 10. 10.1512/ 2015.64.5469, URL https: doi. /tt.g//...0... 1512/111222 htt::/mmj.2222 201.::/.....2221........... 64.5499.
Enrico Le Donne, Tapio Rajala, and Erik Walsberg. Isometric embeddings of snowflakes into finite- dimensional Banach spaces. Proc. Amer. Math. Soc., 146(())685-693, 2018. ISSN 0002-9939. doi: 10.1079/pro//13778 URL https:://////. /to.doo.oggooo 1ttp://...900////////3///
Nathan Linial, Eran London, and Yuri Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15(2):215-245, 1995. ISSN 0209-9683. doi: 10. N0.10077BFF11200757 htRp::/t: wtt.a/i.orrrroooooeeeeeeooo wwwg//.//.0....... 00100000//0000000
Qi Liu, Maximilian Nickel, and Douwe Kiela. Hyperbolic graph neural networks. NeurlPS, 2019.
Jianfeng Lu, Zuowei Shen, Haizhao Yang. and Shijun Zhang. Deep network approximation for smooth functions. SIAM J. Math. Anal., 5365):546 2021. ISSN 0036-1410, doi: 10.1137/ 20M134695X. URL https: /tt:///oiii/ org 010.001117//2//133333
Hiroshi Maehara. Metric transforms of finite spaces and connected graphs. Discrete mathematics, 61(2-3):235-244 1986.
Carlo Marcati, Joost AA Opschoor, Philipp C Petersen, and Christoph Schwab. Exponential relu neural network approximation rates for point and edge singularities. Foundations of Computa- tional Mathematics, pp. 1-85, 2022.
Jifí Matoušek. On embedding expanders into I, spaces. Israel J. Math, 102:189-197, 1997. ISSN 102552172.156--8111 doi: 10.1007/BF027773799. URL hitps: / /ci..rrg/10.1077 BF 77777937
13

---

Published as a conference paper at ICLR 2024
Robert J. McGlinn. Uniform approximation of completely monotone functions by exponential sums.
Math, Anal. Appl. 65(1):211-218, 1978. ISSN 0022-247X. doi: 10. 20016/0022-247X650
90210-X. URL https: www.doi...goolgoooo 1016000...1100101 001/000022222222 247X (78) 90210-X.
Hrushikesh N Mhaskar and Tomaso Poggio. Deep shallow networks: An approximation theory
perspective. Analysis and Applications, 14(06):829-848, 2016.
Assaf Naor and Ofer Neiman. Assouad's theorem with dimension independent of the snowflaking. Rev. Mat. Iberoam., 2834):1 2012. ISSN 0213-2230. doi: 10.4171/MM/706, URL
https: /ttp//ooiiio// org. wiwaccess....................... 1ib www.mmmmm..e.....mm.mm.mmm.em... ca /100 71/ /RMI/MMI
Philipp Petersen and Felix Voigtlaender. Optimal approximation of piecewise smooth functions using deep relu neural networks. Neural Networks, 108:296-330, 2018.
T. R. L. Phillips, K. M. Schmidt, and A. Zhigljavsky. Extension of the Schoenberg theorem to integrally conditionally positive definite functions. Math. Anal. Appl., 470(1):659 678, 2019. ISSN 0022-247X. doi:
j00..mm01..00000....... URL https: /ttp:///o...///1110//666
jma. 2018.10.032.
losif Pinelis. Representation of continuous, monotone, concave functions.
URL https://
mathoverflos. bathoverflow.net////a ntt.////////.......
Frank Rosenblatt. The perceptron: a probabilistic model for information storage and organization in the brain. Psychological review, 65(6):386, 1958.
Haitz Sáez de Ocáriz Borde, Alvaro Arroyo, Ismael Morales, Ingmar Posner, and Xiaowen Dong. Neural latent geometry search: Product manifold inference via gromov-hausdorf-iffomeed bayesian optimization, 2023a.
Haitz Sáez de Ocáriz Borde, Alvaro Arroyo, and Ingmar Posner. Projections of model spaces for latent graph inference. In ICLR 2023 Workshop on Physics for Machine Learning, 2023b.
Haitz Sáez de Ocáriz Borde, Ances Kazi, Federico Barbero, and Pietro Lio. Latent graph inference using product manifolds. The Eleventh International Conference Learning Representations, 2023c.
Rik Sarkar. Low distortion Delaunay embedding of trees in hyperbolic plane. In Gruph drawing, volume 7034 of Lecture Notes in Comput. Sci., pp. 355-366. Springer, Heidel- berg, 2012. doi: 0-00799788--642-28888--777 34. URL https:////// 110-6642258777 257722522777544
René L.
Schilling, Renming Song, and Zoran Vondraček. Bernstein functions, volume 37 of De Gruyter Studies in Mathematics. Walter Gruyter & Co., Berlin, second edition, 2012. ISBN doi: (0.151//97831102999 URL /tattss:/ddot 978-3-11-025229-3: 971 Theory and applications. 0tg/10.1511/9788110
J. Schoenberg. Metric spaces and completely monotone functions. Ann. of Math. (2), 39 841, 1938. ISSN 0003-486X. doi: 10.2307/1968466. URL htttps://cc..oo/o/
2307/
1968466.
Schoenberg. Positive definite functions on spheres. Duke Math. J., 9:96-108, 1942. ISSN 0012-7094. URL http::/ppoojeteecl///oooooo wttp://ww......./...e./e/e//aa.. httpe/i...mmm11711/1/ dmj//077493377.
Isaac Schoenberg, On certain metric spaces arising from euclidean spaces by a change of metric and their imbedding hilbert space. Annals of mathematics, pp. 787-793, 1937.
Zuowei Shen, Haizhao Yang, and Shijun Zhang. Optimal approximation rate of relu networks in terms of width and depth. Journal de Mathématiques Pures et Appliquées, 157:101-135, 2022.
Puoya Tabaghi, Eli Chien, Chao Pan, Jianhao Peng, and Olgica Milenković. Linear classifiers in product space forms, 2021.
Jake Topping. Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M. Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature. ArXiv, 1as/2111.115522 2021.
14

---

Published as a conference paper at ICLR 2024
Ashish Vaswani, Noam M. Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. ArXiv, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. ArXiv, 2018.
Kevin Verbeek and Subhash Suri. Metric embedding, hyperbolic space, and social networks. Pro- ceedings of the thirtieth annual symposium on Computational geometry, 2014.
Yue Wang, Yongbin Sun, Ziwei Liu, Sanjay E. Sarma, Michael M. Bronstein, and Justin M. Solomon. Dynamic graph enn for learning on point clouds. ACM Transactions on Graphics (TOG), 38:1 12, 2019.
Nik Weaver. Lipschitz algebras. World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, 2018. ISBN 978-981-4740-63-0, Second edition of [ MR MRI832645].
Jakob Weissteiner, Jakob Heiss, Julien Siems, and Sven Seuken. Monotone-value neural networks: Exploiting preference monotonicity combinatorial assignment. Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22), 2022.
David Vernon Widder. The Laplace Transform. Princeton Mathematical Series, vol. 6. Princeton University Press, Princeton, N. J., 1941.
Qitian Wu, Wentao Zhao, Zenan Li, David Wipf, and Junchi Yan. Nodeformer: A scalable graph structure learning transformer for node classification, 2023.
Qinglan Xia. The geodesic problem in quasimetric spaces. Geom. Anal, 19(2)452-479, URL attps://doi-ors
2009. ISSN 1050-6926. doi: 10.10077/12220-088899666 9065-44. libaccess.o 1ib. mwmaster.e.............m ca/10 1007 / w1200002222222222 008 9065-4.
Dmitry Yarotsky. Error bounds for approximations with deep relu networks. Neural Networks, 94: 103-114, 2017.
Ding-Xuan Zhou. Theory of deep convolutional neural networks: Downsampling. Neural Networks, 124:319-327, 2020a.
Ding- Xuan Zhou. Universality of deep convolutional neural networks. Applied and computational harmonic analywis, 48(2):787-794, 2020b.
Yanqiao Zhu, Weizhi Xu, Jinghao Zhang, Qiang Liu, Shu Wu, and Liang Wang. Deep graph struc- ture learning for robust representations: A survey. ArXiv, abs/2103..n 10100003300666 2021.
15


Reviews:
[{"review_id": "n2SVGsQAlg", "reviewer": "Reviewer_Sjjv", "summary": "The authors leverage the representation power of a snowflake metrics using learnable neural snowflake activation in a neural network-based model. In doing so, they prove that neural snowflake permits universal representation for learning latent graphs, which is not the case for simpler previous state-of-the-art geometric embeddings. This is demonstrated theoretically via Theorems 1-2, with particular examples provided to motivate a learnable, non-Riemannian metric. This is also demonstrated empirically with a comprehensive comparison to alternative latent graph inference methods which use more typical metrics, clearly outperforming these baselines in some cases, and performing competitively in others.", "questions": "While you note that this is mainly tangential to the primary focus of this paper, you mention that the suboptimality of the Gumbel Top-k edge sampling algorithm may be a reason why the improved performance of your method in the real data settings is not as pronounced. However, would this not affect all methods equally? That is, why do you suggest that an improvement in this regard might better differentiate the neural snowflake model from the baselines?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. The benefit of the extension to quasi-metric spaces and a learnable neural snowflake activation is clearly explained, as the authors provide both theoretical findings and concrete examples to demonstrate the utility.\n2. The experiments are thorough and well-controlled. The striking improvement in applying neural snowflake in the synthetic setting is convincing, and the marginal benefit in the \"input graph\" experiment of Table 3 demonstrates that this advantage is present in real data as well.\n3. The universal representation power in conjunction with the fact that the model provably needs not to use a large number of parameters is a very strong theoretical result.\n\nOverall, this is a very well-written and convincing work. While I am not entirely knowledgeable on the topic of latent graph inference, I think that the theoretical and empirical arguments of the authors provide a very clear explanation of the novelty of their approach and how it fits in the context of the current state of the field.", "weaknesses": "While the majority of the experimental results are convincing, the results of Table 4 are slightly underwhelming. It is certainly a good finding that neural snowflake is competitive in all cases, which cannot be said about any of the other approaches, but the fact that it is usually outperformed by some other method limits the applicability of this approach to real data.\n\nMaybe there is some experiment to evaluate the method in a way that provides more initial information than the experiment in Table 4, but not entirely the original input graph as used in Table 3? However, I don't believe this is entirely necessary to convey the utility of the approach.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "cBgOaqpLHi", "reviewer": "Reviewer_gXAo", "summary": "This work studies learning latent structures from pure point clouds (a set of points without graph structures) or graph-structured data (a set of points with observed structures). The authors present rogirous analysis into the property of latent structure learning models and how to conduct latent graph inference that satifies the metric properties. Experiments on several benchmark datasets verify the proposed approach.", "questions": "See some of the questions in the weakness section. Besides, there are some further questions:\n\n1. Can the model handle more difficult datasets, e.g., heterophilic graphs and graphs with incomplete edges?\n\n2. How does the model compare with recent graph structure learning models LDS [1] and NodeFormer [2]?\n\n3. What is the impact of the informativeness of node features on the model performance when not using the input graph?\n\n4. Can the theoretical results be applied to graph Transformers whose attention networks can be seen as latent graph inference?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The paper studies an important and interesting problem\n\n2. The theoretical analysis is rigorous and with technical depth\n\n3. The overall writing is good though some parts can be improved to increase the readability", "weaknesses": "1. One concern lies in the clarity of the proposed model. The paper title describes the model as a \"universal\" method, but the main paper does not justify this point very well. For example, how universal the model is and to what extent? What is the advantage of the proposed model compared with prior art? Also, the algorithm for the model is missing, which makes the reader hard to understand what is precisely done in the model implementation.\n\n2. The implication of the theoretical results needs to be made more clear. How can the theory apply to practical problems and what is the insight behind the analysis? \n\n3. The experiments are limited with four small datasets. For the Cora and Citeseer, it seems that the common benchmark settings are not used for evaluation. Can the authors provide more reasons on this and what precisely the data splits are used for the present experiments? The baselines for comparison are not sufficient, and some of the typical graph structure learning models are missing, e.g., LDS [1] and the state-of-the-art NodeFormer [2] (that also considers the Gumbel trick).\n\n[1] Luca Franceschi et al., Learning discrete structures for graph neural networks. In ICML, 2019.\n\n[2] Qitian Wu et al., NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification. In NeurIPS, 2022.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "dScKCpDyux", "reviewer": "Reviewer_pN6S", "summary": "The paper presents and analyzes a trainable metric termed \"neural snowflake\", which is a combination of a bounded gaussian kernel distance , a fractal component $\\vert a-b \\vert^\\alpha$ with $\\alpha \\in (0,1]$ and an *irregular* fractal component in log space $\\log\\left(1+\\Vert a-b\\Vert^\\beta\\right)^{1+\\vert p \\vert}$ with $\\beta \\in (0,1],p\\in \\mathbb{R}_0^+$. This distance function is used to learn *latent* graphs from data, wherein the graph structure of a dataset or sample is inferred from the features, instead of being constructed by a human annotater.\n\nThe paper proves that\n\n1. parametrized with an MLP as embedder and the neural snowflake and distance function, we can learn a $d$ dimensional embedding for any finite weighted graph\n2. There are finite weighted graphs which are *not* similarly representable if using a euclidean distance\n3. the depth and hidden width of the MLP depends favourably on the number of nodes and embedding dimensions (order $(n\\log n)^{1.5}$ and linearly, respectively)\n4. For specific graphs (e.g. trees) even more favourable guarantees are possible\n\nThe method is evaluated on Cora, CiteSeer (standard GNN benchmarks) and Tadpole and Aerothermodynamics (used in the paper which introduced the latent graph approach.)", "questions": "Aside from Q2 in weakness, no questions", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The paper is very accessible for such a technical topic and presents its story clearly and convincingly.\n\n\nNovelty/Originality: Moving from euclidean and Riemanian metrics to quasi-metric spaces is an idea which I haven't seen a lot in the literature ...and I checked because I was actually thinking about going into this direction myself but hadn't properly started working on this due to previous projects. Happy to be \"scooped\" in this manner!\n\nSignificance: Having provable representation power in this sense for arbitrary graphs will be an important ingredient as we move towards building less supervised relational ML models\n\nQuality: derivations, expositions and experiments are well presented and clean. Proofs look sane to me as well, although I did not step through them in detail", "weaknesses": "1.  There is relatively high variances in most of the tables, could you please perform suitable significance tests (e.g. with a bonferonni correction) and mark those that are significant to aid the viewer?\n2. I might have missed it, but what is the STD across? Evaluations or trainings? E.g. in table 7\n3. Nitpick, but explicitly discussing the memory constraints and other concerns in a limitations section in the appendix helps the readers judge potential pitfalls", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "IWF8tAQ76R", "reviewer": "Reviewer_cbgk", "summary": "The authors present Neural Snowflakes, a latent graph inference method. Neural Snowflakes are iterative representations that use a trainable activation function to refine input distance values $\\|x - y\\|$. The authors present theoretic justification for their model as well as compelling empirical results on latent graph inference tasks.", "questions": "Admittedly, I am not an expert on latent graph inference, so I'm doing my best to judge the quality of the work based on the description by the authors and the results produced.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The authors present compelling empirical results for their method\n* Theoretical analysis underpins these empirical results\n* The fact that Neural Snowflakes can break the curse of dimensionality and don't need exponentially many parameters is a very nice property", "weaknesses": "* The paper does not state the loss function the Neural Snowflake models are trained on\n* There is no mentioning of the computational complexity/ scalability of the approach: does it scale to hundreds of thousands/ millions of data points? Why (not)?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)