# Neural Snowflakes: Universal Latent Graph Inference via Trainable Latent Geometries

arXiv: https://arxiv.org/abs/2310.15003 · HTML: https://mlsanity.com/paper/2310.15003/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 45 of its 84 references that are in the map.
- First posted on arXiv 23 Oct 2023.

## Builds on (most cited first, 30 of 45)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Dynamic Graph CNN for Learning on Point Clouds](https://mlsanity.com/paper/1801.07829/) (2018)
- [Geometric deep learning: going beyond Euclidean data](https://mlsanity.com/paper/1611.08097/) (2016)
- [Error bounds for approximations with deep ReLU networks](https://mlsanity.com/paper/1610.01145/) (2016)
- [Measuring and Relieving the Over-smoothing Problem for Graph Neural Networks from the Topological View](https://mlsanity.com/paper/1909.03211/) (2019)
- [Understanding over-squashing and bottlenecks on graphs via curvature](https://mlsanity.com/paper/2111.14522/) (2021)
- [Input Convex Neural Networks](https://mlsanity.com/paper/1609.07152/) (2016)
- [Hyperbolic Graph Convolutional Neural Networks](https://mlsanity.com/paper/1910.12933/) (2019)
- [Graph Structure Learning for Robust Graph Neural Networks](https://mlsanity.com/paper/2005.10203/) (2020)
- [Hyperbolic Graph Neural Networks](https://mlsanity.com/paper/1910.12892/) (2019)
- [Learning Discrete Structures for Graph Neural Networks](https://mlsanity.com/paper/1903.11960/) (2019)
- [Iterative Deep Graph Learning for Graph Neural Networks: Better and Robust Node Embeddings](https://mlsanity.com/paper/2006.13009/) (2020)
- [Stochastic Beams and Where to Find Them: The Gumbel-Top-k Trick for Sampling Sequences Without Replacement](https://mlsanity.com/paper/1903.06059/) (2019)
- [NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification](https://mlsanity.com/paper/2306.08385/) (2023)
- [Optimal approximation of piecewise smooth functions using deep ReLU neural networks](https://mlsanity.com/paper/1709.05289/) (2017)
- [Universality of Deep Convolutional Neural Networks](https://mlsanity.com/paper/1805.10769/) (2018)
- [Deep Network Approximation for Smooth Functions](https://mlsanity.com/paper/2001.03040/) (2020)
- [Kernel Operations on the GPU, with Autodiff, without Memory Overflows](https://mlsanity.com/paper/2004.11127/) (2020)
- [Optimal Approximation Rate of ReLU Networks in terms of Width and Depth](https://mlsanity.com/paper/2103.00502/) (2021)
- [Deep Neural Network Approximation Theory](https://mlsanity.com/paper/1901.02220/) (2019)
- [Optimal Approximation with Sparsely Connected Deep Neural Networks](https://mlsanity.com/paper/1705.01714/) (2017)
- [DiffWire: Inductive Graph Rewiring via the Lov'asz Bound](https://mlsanity.com/paper/2206.07369/) (2022)
- [Deep vs. shallow networks : An approximation theory perspective](https://mlsanity.com/paper/1608.03287/) (2016)
- [Neural Embeddings of Graphs in Hyperbolic Space](https://mlsanity.com/paper/1705.10359/) (2017)
- [VAIN: Attentional Multi-agent Predictive Modeling](https://mlsanity.com/paper/1706.06122/) (2017)
- [Universal Approximation Theorems for Differentiable Geometric Deep Learning](https://mlsanity.com/paper/2101.05390/) (2021)

## Built on by (most cited first, 6 of 6)

- [Neural Spacetimes for DAG Representation Learning](https://mlsanity.com/paper/2408.13885/) (2024)
- [Mixed-curvature decision trees and random forests](https://mlsanity.com/paper/2410.13879/) (2024)
- [Mixed-Curvature Decision Trees and Random Forests](https://mlsanity.com/paper/2406.05227/) (2024)
- [Metric Learning for Clifford Group Equivariant Neural Networks](https://mlsanity.com/paper/2407.09926/) (2024)
- [Alleviating Over-Smoothing via Aggregation over Compact Manifolds](https://mlsanity.com/paper/2407.19231/) (2024)
- [Classification Fields: Arbitrarily Fine Recursive Hierarchical Clustering From Few Examples](https://mlsanity.com/paper/2605.07119/) (2026)

## Abstract (arXiv)

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 neural snowflake, that can adaptively implement fractal-like metrics on ℝ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.