mlsanityData to 14 Oct 2026

Geometric instability of graph neural networks on large graphs

arXiv 2308.10099 ↗First posted 19 Aug 2023cs.LG cs.SIcited by 2

Not on the map. Why?

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.

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

27 of 35 references.

References · 27

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  2. 2017Graph Attention Networkscited by 8,923
  3. 2017Inductive Representation Learning on Large Graphscited by 6,320
  4. 2018How Powerful are Graph Neural Networks?cited by 4,393
  5. 2017Billion-scale similarity search with GPUscited by 2,497
  6. 2019Fast Graph Representation Learning with PyTorch Geometriccited by 2,434
  7. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,163
  8. 2016node2vec: Scalable Feature Learning for Networkscited by 1,918
  9. 2019Similarity of Neural Network Representations Revisitedcited by 1,755
  10. 2014DeepWalk: Online Learning of Social Representationscited by 1,547
  11. 2018Pitfalls of Graph Neural Network Evaluationcited by 1,007
  12. 2016Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphscited by 861
15 more
  1. 2019GraphSAINT: Graph Sampling Based Inductive Learning Methodcited by 618
  2. 2023A critical look at the evaluation of GNNs under heterophily: Are we really making progress?cited by 343
  3. 2020The Surprising Power of Graph Neural Networks with Random Node Initializationcited by 198
  4. 2020Random Features Strengthen Graph Neural Networkscited by 186
  5. 2019On the Universality of Invariant Networkscited by 152
  6. 2023Edge Directionality Improves Learning on Heterophilic Graphscited by 90
  7. 2022Reliability of CKA as a Similarity Measure in Deep Learningcited by 87
  8. 2021Torch.manual_seed(3407) is all you need: On the influence of random seeds in deep learning architectures for computer visioncited by 81
  9. 2016Cultural Shift or Linguistic Drift? Comparing Two Computational Measures of Semantic Changecited by 63
  10. 2022TwHIN: Embedding the Twitter Heterogeneous Information Network for Personalized Recommendationcited by 25
  11. 2020The Effects of Randomness on the Stability of Node Embeddingscited by 15
  12. 2022On the Prediction Instability of Graph Neural Networkscited by 6
  13. 2021Alignment and stability of embeddings: measurement and inference improvementcited by 4
  14. 2021Are Word Embedding Methods Stable and Should We Care About It?cited by 4
  15. 2022On the Surprising Behaviour of node2veccited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 1; 2026: 1.

2 papers.

  1. 2025PGOT: A Physics-Geometry Operator Transformer for Complex PDEscited by 0
  2. 2026The Impact of Dimensionality on the Stability of Node Embeddingscited by 0