# Metropolis-Hastings Data Augmentation for Graph Neural Networks

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

## Key facts

- Cited by 30 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 37 references that are in the map.
- First posted on arXiv 26 Mar 2022.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [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)
- [CutMix: Regularization Strategy to Train Strong Classifiers with Localizable Features](https://mlsanity.com/paper/1905.04899/) (2019)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [RandAugment: Practical automated data augmentation with a reduced search space](https://mlsanity.com/paper/1909.13719/) (2019)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [FixMatch: Simplifying Semi-Supervised Learning with Consistency and Confidence](https://mlsanity.com/paper/2001.07685/) (2020)
- [Modeling Relational Data with Graph Convolutional Networks](https://mlsanity.com/paper/1703.06103/) (2017)
- [Variational Graph Auto-Encoders](https://mlsanity.com/paper/1611.07308/) (2016)
- [Unsupervised Data Augmentation for Consistency Training](https://mlsanity.com/paper/1904.12848/) (2019)
- [MoleculeNet: A Benchmark for Molecular Machine Learning](https://mlsanity.com/paper/1703.00564/) (2017)
- [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)
- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [Hierarchical Graph Representation Learning with Differentiable Pooling](https://mlsanity.com/paper/1806.08804/) (2018)
- [Convolutional Networks on Graphs for Learning Molecular Fingerprints](https://mlsanity.com/paper/1509.09292/) (2015)
- [DropEdge: Towards Deep Graph Convolutional Networks on Node Classification](https://mlsanity.com/paper/1907.10903/) (2019)
- [Measuring and Relieving the Over-smoothing Problem for Graph Neural Networks from the Topological View](https://mlsanity.com/paper/1909.03211/) (2019)
- [Interaction Networks for Learning about Objects, Relations and Physics](https://mlsanity.com/paper/1612.00222/) (2016)
- [Representation Learning on Graphs: Methods and Applications](https://mlsanity.com/paper/1709.05584/) (2017)
- [CSI: Novelty Detection via Contrastive Learning on Distributionally Shifted Instances](https://mlsanity.com/paper/2007.08176/) (2020)
- [Graph Random Neural Network for Semi-Supervised Learning on Graphs](https://mlsanity.com/paper/2005.11079/) (2020)
- [Data Augmentation for Graph Neural Networks](https://mlsanity.com/paper/2006.06830/) (2020)
- [Transfer Learning of Graph Neural Networks with Ego-graph Information Maximization](https://mlsanity.com/paper/2009.05204/) (2020)
- [Batch Virtual Adversarial Training for Graph Convolutional Networks](https://mlsanity.com/paper/1902.09192/) (2019)
- [Self-supervised Training of Graph Convolutional Networks](https://mlsanity.com/paper/2006.02380/) (2020)

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

- [Graph Rationalization with Environment-based Augmentations](https://mlsanity.com/paper/2206.02886/) (2022)
- [Structural Re-weighting Improves Graph Domain Adaptation](https://mlsanity.com/paper/2306.03221/) (2023)
- [Prompt Learning via Meta-Regularization](https://mlsanity.com/paper/2404.00851/) (2024)
- [DAGAD: Data Augmentation for Graph Anomaly Detection](https://mlsanity.com/paper/2210.09766/) (2022)
- [GraphMETRO: Mitigating Complex Graph Distribution Shifts via Mixture of Aligned Experts](https://mlsanity.com/paper/2312.04693/) (2023)
- [Fused Gromov-Wasserstein Graph Mixup for Graph-level Classifications](https://mlsanity.com/paper/2306.15963/) (2023)
- [Data Augmentation on Graphs: A Technical Survey](https://mlsanity.com/paper/2212.09970/) (2022)
- [Matcha: Mitigating Graph Structure Shifts with Test-Time Adaptation](https://mlsanity.com/paper/2410.06976/) (2024)
- [Cross-Domain Graph Data Scaling: A Showcase with Diffusion Models](https://mlsanity.com/paper/2406.01899/) (2024)
- [FocusedCleaner: Sanitizing Poisoned Graphs for Robust GNN-based Node Classification](https://mlsanity.com/paper/2210.13815/) (2022)
- [Democratizing Large Language Model-Based Graph Data Augmentation via Latent Knowledge Graphs](https://mlsanity.com/paper/2502.13555/) (2025)
- [Towards Better Generalization with Flexible Representation of Multi-Module Graph Neural Networks](https://mlsanity.com/paper/2209.06589/) (2022)
- [Tokenized Graph Transformer with Neighborhood Augmentation for Node Classification in Large Graphs](https://mlsanity.com/paper/2305.12677/) (2023)
- [Node Duplication Improves Cold-start Link Prediction](https://mlsanity.com/paper/2402.09711/) (2024)
- [IntraMix: Intra-Class Mixup Generation for Accurate Labels and Neighbors](https://mlsanity.com/paper/2405.00957/) (2024)
- [MLDGG: Meta-Learning for Domain Generalization on Graphs](https://mlsanity.com/paper/2411.12913/) (2024)
- [Causally-guided Regularization of Graph Attention Improves Generalizability](https://mlsanity.com/paper/2210.10946/) (2022)
- [Graphs Generalization under Distribution Shifts](https://mlsanity.com/paper/2403.16334/) (2024)
- [DropEdge not Foolproof: Effective Augmentation Method for Signed Graph Neural Networks](https://mlsanity.com/paper/2409.19620/) (2024)
- [GLAD: Generalizable Tuning for Vision-Language Models](https://mlsanity.com/paper/2507.13089/) (2025)
- [Evolving Graph Learning for Out-of-Distribution Generalization in Non-stationary Environments](https://mlsanity.com/paper/2511.02354/) (2025)
- [GEANN: Scalable Graph Augmentations for Multi-Horizon Time Series Forecasting](https://mlsanity.com/paper/2307.03595/) (2023)
- [FRGNN: Mitigating the Impact of Distribution Shift on Graph Neural Networks via Test-Time Feature Reconstruction](https://mlsanity.com/paper/2308.09259/) (2023)
- [Robust Traffic Forecasting against Spatial Shift over Years](https://mlsanity.com/paper/2410.00373/) (2024)
- [Control the GNN: Utilizing Neural Controller with Lyapunov Stability for Test-Time Feature Reconstruction](https://mlsanity.com/paper/2410.09708/) (2024)
- [Graph Augmentation for Cross Graph Domain Generalization](https://mlsanity.com/paper/2502.18188/) (2025)
- [SGA: A Graph Augmentation Method for Signed Graph Neural Networks](https://mlsanity.com/paper/2310.09705/) (2023)
- [CoATA: Effective Co-Augmentation of Topology and Attribute for Graph Neural Networks](https://mlsanity.com/paper/2506.22299/) (2025)
- [Leakage-Free Evaluation and Distribution-Robust Spatio-Temporal Graph Learning for Inductive Kriging](https://mlsanity.com/paper/2509.23631/) (2025)
- [Rethinking Semi-Supervised Node Classification with Self-Supervised Graph Clustering](https://mlsanity.com/paper/2511.19976/) (2025)

## Abstract (arXiv)

Graph Neural Networks (GNNs) often suffer from weak-generalization due to sparsely labeled data despite their promising results on various graph-based tasks. Data augmentation is a prevalent remedy to improve the generalization ability of models in many domains. However, due to the non-Euclidean nature of data space and the dependencies between samples, designing effective augmentation on graphs is challenging. In this paper, we propose a novel framework Metropolis-Hastings Data Augmentation (MH-Aug) that draws augmented graphs from an explicit target distribution for semi-supervised learning. MH-Aug produces a sequence of augmented graphs from the target distribution enables flexible control of the strength and diversity of augmentation. Since the direct sampling from the complex target distribution is challenging, we adopt the Metropolis-Hastings algorithm to obtain the augmented samples. We also propose a simple and effective semi-supervised learning strategy with generated samples from MH-Aug. Our extensive experiments demonstrate that MH-Aug can generate a sequence of samples according to the target distribution to significantly improve the performance of GNNs.