# Geometric instability of graph neural networks on large graphs

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 35 references that are in the map.
- First posted on arXiv 19 Aug 2023.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [Similarity of Neural Network Representations Revisited](https://mlsanity.com/paper/1905.00414/) (2019)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Pitfalls of Graph Neural Network Evaluation](https://mlsanity.com/paper/1811.05868/) (2018)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [GraphSAINT: Graph Sampling Based Inductive Learning Method](https://mlsanity.com/paper/1907.04931/) (2019)
- [A critical look at the evaluation of GNNs under heterophily: Are we really making progress?](https://mlsanity.com/paper/2302.11640/) (2023)
- [The Surprising Power of Graph Neural Networks with Random Node Initialization](https://mlsanity.com/paper/2010.01179/) (2020)
- [Random Features Strengthen Graph Neural Networks](https://mlsanity.com/paper/2002.03155/) (2020)
- [On the Universality of Invariant Networks](https://mlsanity.com/paper/1901.09342/) (2019)
- [Edge Directionality Improves Learning on Heterophilic Graphs](https://mlsanity.com/paper/2305.10498/) (2023)
- [Reliability of CKA as a Similarity Measure in Deep Learning](https://mlsanity.com/paper/2210.16156/) (2022)
- [Torch.manual_seed(3407) is all you need: On the influence of random seeds in deep learning architectures for computer vision](https://mlsanity.com/paper/2109.08203/) (2021)
- [Cultural Shift or Linguistic Drift? Comparing Two Computational Measures of Semantic Change](https://mlsanity.com/paper/1606.02821/) (2016)
- [TwHIN: Embedding the Twitter Heterogeneous Information Network for Personalized Recommendation](https://mlsanity.com/paper/2202.05387/) (2022)
- [The Effects of Randomness on the Stability of Node Embeddings](https://mlsanity.com/paper/2005.10039/) (2020)
- [On the Prediction Instability of Graph Neural Networks](https://mlsanity.com/paper/2205.10070/) (2022)
- [Alignment and stability of embeddings: measurement and inference improvement](https://mlsanity.com/paper/2101.07251/) (2021)
- [Are Word Embedding Methods Stable and Should We Care About It?](https://mlsanity.com/paper/2104.08433/) (2021)
- [On the Surprising Behaviour of node2vec](https://mlsanity.com/paper/2206.08252/) (2022)

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

- [PGOT: A Physics-Geometry Operator Transformer for Complex PDEs](https://mlsanity.com/paper/2512.23192/) (2025)
- [The Impact of Dimensionality on the Stability of Node Embeddings](https://mlsanity.com/paper/2604.08492/) (2026)

## Abstract (arXiv)

We analyse the geometric instability of embeddings produced by graph neural networks (GNNs). Existing methods are only applicable for small graphs and lack context in the graph domain. We propose a simple, efficient and graph-native Graph Gram Index (GGI) to measure such instability which is invariant to permutation, orthogonal transformation, translation and order of evaluation. This allows us to study the varying instability behaviour of GNN embeddings on large graphs for both node classification and link prediction.