# Valid Bootstraps for Network Embeddings with Applications to Network Visualisation

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 53 references that are in the map.
- First posted on arXiv 28 Oct 2024.

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

- [Efficient Estimation of Word Representations in Vector Space](https://mlsanity.com/paper/1301.3781/) (2013)
- [UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction](https://mlsanity.com/paper/1802.03426/) (2018)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [Graph Neural Networks in Recommender Systems: A Survey](https://mlsanity.com/paper/2011.02260/) (2020)
- [Graph-based Anomaly Detection and Description: A Survey](https://mlsanity.com/paper/1404.4679/) (2014)
- [A statistical interpretation of spectral embedding: the generalised random dot product graph](https://mlsanity.com/paper/1709.05506/) (2017)
- [Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel](https://mlsanity.com/paper/1309.4111/) (2013)
- [The impossibility of low rank representations for triangle-rich complex networks](https://mlsanity.com/paper/2003.12635/) (2020)
- [The multilayer random dot product graph](https://mlsanity.com/paper/2007.10455/) (2020)
- [DELTACON: A Principled Massive-Graph Similarity Function](https://mlsanity.com/paper/1304.4657/) (2013)
- [Illuminati: Towards Explaining Graph Neural Networks for Cybersecurity Analysis](https://mlsanity.com/paper/2303.14836/) (2023)
- [Spectral embedding for dynamic networks with stability guarantees](https://mlsanity.com/paper/2106.01282/) (2021)
- [Estimating Psychological Networks and their Accuracy: A Tutorial Paper](https://mlsanity.com/paper/1604.08462/) (2016)
- [Bootstrapping Networks with Latent Space Structure](https://mlsanity.com/paper/1907.10821/) (2019)
- [Subsampling bootstrap of count features of networks](https://mlsanity.com/paper/1312.2645/) (2013)
- [Bootstrapping Exchangeable Random Graphs](https://mlsanity.com/paper/1711.00813/) (2017)
- [Multiple Network Embedding for Anomaly Detection in Time Series of Graphs](https://mlsanity.com/paper/2008.10055/) (2020)
- [Valid Conformal Prediction for Dynamic GNNs](https://mlsanity.com/paper/2405.19230/) (2024)
- [A Simple and Powerful Framework for Stable Dynamic Network Embedding](https://mlsanity.com/paper/2311.09251/) (2023)

## Abstract (arXiv)

Quantifying uncertainty in networks is an important step in modelling relationships and interactions between entities. We consider the challenge of bootstrapping an inhomogeneous random graph when only a single observation of the network is made and the underlying data generating function is unknown. We address this problem by considering embeddings of the observed and bootstrapped network that are statistically indistinguishable. We utilise an exchangeable network test that can empirically validate bootstrap samples generated by any method. Existing methods fail this test, so we propose a principled, distribution-free network bootstrap using k-nearest neighbour smoothing, that can pass this exchangeable network test in many synthetic and real-data scenarios. We demonstrate the utility of this work in combination with the popular data visualisation method t-SNE, where uncertainty estimates from bootstrapping are used to explain whether visible structures represent real statistically sound structures.