# You Can Have Better Graph Neural Networks by Not Training Weights at All: Finding Untrained GNNs Tickets

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

## Key facts

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

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [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)
- [The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks](https://mlsanity.com/paper/1803.03635/) (2018)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Estimating or Propagating Gradients Through Stochastic Neurons for Conditional Computation](https://mlsanity.com/paper/1308.3432/) (2013)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Variational Graph Auto-Encoders](https://mlsanity.com/paper/1611.07308/) (2016)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [MoleculeNet: A Benchmark for Molecular Machine Learning](https://mlsanity.com/paper/1703.00564/) (2017)
- [Representation Learning on Graphs with Jumping Knowledge Networks](https://mlsanity.com/paper/1806.03536/) (2018)
- [Simple and Deep Graph Convolutional Networks](https://mlsanity.com/paper/2007.02133/) (2020)
- [Geom-GCN: Geometric Graph Convolutional Networks](https://mlsanity.com/paper/2002.05287/) (2020)
- [Gated Graph Sequence Neural Networks](https://mlsanity.com/paper/1511.05493/) (2015)
- [DropEdge: Towards Deep Graph Convolutional Networks on Node Classification](https://mlsanity.com/paper/1907.10903/) (2019)
- [To prune, or not to prune: exploring the efficacy of pruning for model compression](https://mlsanity.com/paper/1710.01878/) (2017)
- [Measuring and Relieving the Over-smoothing Problem for Graph Neural Networks from the Topological View](https://mlsanity.com/paper/1909.03211/) (2019)
- [DeepGCNs: Can GCNs Go as Deep as CNNs?](https://mlsanity.com/paper/1904.03751/) (2019)
- [Rigging the Lottery: Making All Tickets Winners](https://mlsanity.com/paper/1911.11134/) (2019)
- [The State of Sparsity in Deep Neural Networks](https://mlsanity.com/paper/1902.09574/) (2019)
- [Representation Learning on Graphs: Methods and Applications](https://mlsanity.com/paper/1709.05584/) (2017)
- [Scalable Training of Artificial Neural Networks with Adaptive Sparse Connectivity inspired by Network Science](https://mlsanity.com/paper/1707.04780/) (2017)
- [Do Transformers Really Perform Bad for Graph Representation?](https://mlsanity.com/paper/2106.05234/) (2021)
- [PairNorm: Tackling Oversmoothing in GNNs](https://mlsanity.com/paper/1909.12223/) (2019)
- [Towards Deeper Graph Neural Networks](https://mlsanity.com/paper/2007.09296/) (2020)
- [What's Hidden in a Randomly Weighted Neural Network?](https://mlsanity.com/paper/1911.13299/) (2019)
- [Supermasks in Superposition](https://mlsanity.com/paper/2006.14769/) (2020)

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

- [Dynamic Sparse No Training: Training-Free Fine-tuning for Sparse LLMs](https://mlsanity.com/paper/2310.08915/) (2023)
- [Correlation-aware Spatial-Temporal Graph Learning for Multivariate Time-series Anomaly Detection](https://mlsanity.com/paper/2307.08390/) (2023)
- [GOLD: Graph Out-of-Distribution Detection via Implicit Adversarial Latent Generation](https://mlsanity.com/paper/2502.05780/) (2025)
- [Graph Neural Networks Do Not Always Oversmooth](https://mlsanity.com/paper/2406.02269/) (2024)
- [Future Directions in the Theory of Graph Machine Learning](https://mlsanity.com/paper/2402.02287/) (2024)
- [Adversarial Erasing with Pruned Elements: Towards Better Graph Lottery Ticket](https://mlsanity.com/paper/2308.02916/) (2023)
- [Link Prediction with Untrained Message Passing Layers](https://mlsanity.com/paper/2406.16687/) (2024)
- [Multicoated and Folded Graph Neural Networks with Strong Lottery Tickets](https://mlsanity.com/paper/2312.03236/) (2023)
- [You do not have to train Graph Neural Networks at all on text-attributed graphs](https://mlsanity.com/paper/2404.11019/) (2024)
- [Optimal Eye Surgeon: Finding Image Priors through Sparse Generators at Initialization](https://mlsanity.com/paper/2406.05288/) (2024)
- [Position: Graph Condensation Needs a Reset -- Move Beyond Full-dataset Training and Model-Dependence](https://mlsanity.com/paper/2605.18893/) (2026)
- [(PASS) Visual Prompt Locates Good Structure Sparsity through a Recurrent HyperNetwork](https://mlsanity.com/paper/2407.17412/) (2024)
- [Exploring the impact of adaptive rewiring in Graph Neural Networks](https://mlsanity.com/paper/2602.10754/) (2026)
- [Refining Heuristic-Based Bitcoin Address Clustering with Graph Neural Networks](https://mlsanity.com/paper/2609.01942/) (2026)

## Abstract (arXiv)

Recent works have impressively demonstrated that there exists a subnetwork in randomly initialized convolutional neural networks (CNNs) that can match the performance of the fully trained dense networks at initialization, without any optimization of the weights of the network (i.e., untrained networks). However, the presence of such untrained subnetworks in graph neural networks (GNNs) still remains mysterious. In this paper we carry out the first-of-its-kind exploration of discovering matching untrained GNNs. With sparsity as the core tool, we can find textituntrained sparse subnetworks at the initialization, that can match the performance of textitfully trained dense GNNs. Besides this already encouraging finding of comparable performance, we show that the found untrained subnetworks can substantially mitigate the GNN over-smoothing problem, hence becoming a powerful tool to enable deeper GNNs without bells and whistles. We also observe that such sparse untrained subnetworks have appealing performance in out-of-distribution detection and robustness of input perturbations. We evaluate our method across widely-used GNN architectures on various popular datasets including the Open Graph Benchmark (OGB).