# Unveiling the Sampling Density in Non-Uniform Geometric Graphs

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 49 references that are in the map.
- First posted on arXiv 15 Oct 2022.

## Builds on (most cited first, 18 of 18)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Dynamic Graph CNN for Learning on Point Clouds](https://mlsanity.com/paper/1801.07829/) (2018)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Variational Graph Auto-Encoders](https://mlsanity.com/paper/1611.07308/) (2016)
- [Pitfalls of Graph Neural Network Evaluation](https://mlsanity.com/paper/1811.05868/) (2018)
- [Revisiting Semi-Supervised Learning with Graph Embeddings](https://mlsanity.com/paper/1603.08861/) (2016)
- [Multi-scale Attributed Node Embedding](https://mlsanity.com/paper/1909.13021/) (2019)
- [CayleyNets: Graph Convolutional Neural Networks with Complex Rational Spectral Filters](https://mlsanity.com/paper/1705.07664/) (2017)
- [Graphon Neural Networks and the Transferability of Graph Neural Networks](https://mlsanity.com/paper/2006.03548/) (2020)
- [Connecting the Dots: Identifying Network Structure via Graph Signal Processing](https://mlsanity.com/paper/1810.13066/) (2018)
- [Transferability of Spectral Graph Convolutional Neural Networks](https://mlsanity.com/paper/1907.12972/) (2019)
- [Transferability of Graph Neural Networks: an Extended Graphon Approach](https://mlsanity.com/paper/2109.10096/) (2021)
- [Transferability Properties of Graph Neural Networks](https://mlsanity.com/paper/2112.04629/) (2021)
- [Learning by Transference: Training Graph Neural Networks on Growing Graphs](https://mlsanity.com/paper/2106.03693/) (2021)
- [Learning Parametrised Graph Shift Operators](https://mlsanity.com/paper/2101.10050/) (2021)
- [Non-Uniform Distribution of Nodes in the Spatial Preferential Attachment Model](https://mlsanity.com/paper/1506.06053/) (2015)
- [Temporal connectivity in finite networks with non-uniform measures](https://mlsanity.com/paper/1807.10617/) (2018)

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

- [Learning on Large Graphs using Intersecting Communities](https://mlsanity.com/paper/2405.20724/) (2024)
- [Equivariant Machine Learning on Graphs with Nonlinear Spectral Filters](https://mlsanity.com/paper/2406.01249/) (2024)

## Abstract (arXiv)

A powerful framework for studying graphs is to consider them as geometric graphs: nodes are randomly sampled from an underlying metric space, and any pair of nodes is connected if their distance is less than a specified neighborhood radius. Currently, the literature mostly focuses on uniform sampling and constant neighborhood radius. However, real-world graphs are likely to be better represented by a model in which the sampling density and the neighborhood radius can both vary over the latent space. For instance, in a social network communities can be modeled as densely sampled areas, and hubs as nodes with larger neighborhood radius. In this work, we first perform a rigorous mathematical analysis of this (more general) class of models, including derivations of the resulting graph shift operators. The key insight is that graph shift operators should be corrected in order to avoid potential distortions introduced by the non-uniform sampling. Then, we develop methods to estimate the unknown sampling density in a self-supervised fashion. Finally, we present exemplary applications in which the learnt density is used to 1) correct the graph shift operator and improve performance on a variety of tasks, 2) improve pooling, and 3) extract knowledge from networks. Our experimental findings support our theory and provide strong evidence for our model.