# Node Copying: A Random Graph Model for Effective Graph Sampling

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 40 of its 61 references that are in the map.
- First posted on arXiv 4 Aug 2022.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Dropout as a Bayesian Approximation: Representing Model Uncertainty in Deep Learning](https://mlsanity.com/paper/1506.02142/) (2015)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [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)
- [Pitfalls of Graph Neural Network Evaluation](https://mlsanity.com/paper/1811.05868/) (2018)
- [Image-based Recommendations on Styles and Substitutes](https://mlsanity.com/paper/1506.04757/) (2015)
- [Neural Graph Collaborative Filtering](https://mlsanity.com/paper/1905.08108/) (2019)
- [GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models](https://mlsanity.com/paper/1802.08773/) (2018)
- [Adversarial Attacks on Neural Networks for Graph Data](https://mlsanity.com/paper/1805.07984/) (2018)
- [MolGAN: An implicit generative model for small molecular graphs](https://mlsanity.com/paper/1805.11973/) (2018)
- [GraphVAE: Towards Generation of Small Graphs Using Variational Autoencoders](https://mlsanity.com/paper/1802.03480/) (2018)
- [Efficient Graph Generation with Graph Recurrent Attention Networks](https://mlsanity.com/paper/1910.00760/) (2019)
- [Learning Deep Generative Models of Graphs](https://mlsanity.com/paper/1803.03324/) (2018)
- [Adversarial Attack and Defense on Graph Data: A Survey](https://mlsanity.com/paper/1812.10528/) (2018)
- [Anti-Money Laundering in Bitcoin: Experimenting with Graph Convolutional Networks for Financial Forensics](https://mlsanity.com/paper/1908.02591/) (2019)
- [NetGAN: Generating Graphs via Random Walks](https://mlsanity.com/paper/1803.00816/) (2018)
- [GraphGAN: Graph Representation Learning with Generative Adversarial Nets](https://mlsanity.com/paper/1711.08267/) (2017)
- [Graphite: Iterative Generative Modeling of Graphs](https://mlsanity.com/paper/1803.10459/) (2018)
- [Bayesian graph convolutional neural networks for semi-supervised classification](https://mlsanity.com/paper/1811.11103/) (2018)
- [Bayesian Graph Neural Networks with Adaptive Connection Sampling](https://mlsanity.com/paper/2006.04064/) (2020)
- [Hiding Individuals and Communities in a Social Network](https://mlsanity.com/paper/1608.00375/) (2016)
- [Constrained Generation of Semantically Valid Graphs via Regularizing Variational Autoencoders](https://mlsanity.com/paper/1809.02630/) (2018)
- [Fast Gradient Attack on Network Embedding](https://mlsanity.com/paper/1809.02797/) (2018)
- [Stochastic Blockmodels meet Graph Neural Networks](https://mlsanity.com/paper/1905.05738/) (2019)
- [Large Scale Graph Learning from Smooth Signals](https://mlsanity.com/paper/1710.05654/) (2017)
- [Multi-Graph Convolution Collaborative Filtering](https://mlsanity.com/paper/2001.00267/) (2020)
- [A Flexible Generative Framework for Graph-based Semi-supervised Learning](https://mlsanity.com/paper/1905.10769/) (2019)
- [Sparse graphs using exchangeable random measures](https://mlsanity.com/paper/1401.1137/) (2014)

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

- [Are Defenses for Graph Neural Networks Robust?](https://mlsanity.com/paper/2301.13694/) (2023)
- [Robust Node Classification on Graphs: Jointly from Bayesian Label Transition and Topology-based Label Propagation](https://mlsanity.com/paper/2208.09779/) (2022)
- [Individualised recovery trajectories of patients with impeded mobility, using distance between probability distributions of learnt graphs](https://mlsanity.com/paper/2410.21983/) (2024)
- [Preference and Concurrence Aware Bayesian Graph Neural Networks for Recommender Systems](https://mlsanity.com/paper/2312.11486/) (2023)

## Abstract (arXiv)

There has been an increased interest in applying machine learning techniques on relational structured-data based on an observed graph. Often, this graph is not fully representative of the true relationship amongst nodes. In these settings, building a generative model conditioned on the observed graph allows to take the graph uncertainty into account. Various existing techniques either rely on restrictive assumptions, fail to preserve topological properties within the samples or are prohibitively expensive for larger graphs. In this work, we introduce the node copying model for constructing a distribution over graphs. Sampling of a random graph is carried out by replacing each node's neighbors by those of a randomly sampled similar node. The sampled graphs preserve key characteristics of the graph structure without explicitly targeting them. Additionally, sampling from this model is extremely simple and scales linearly with the nodes. We show the usefulness of the copying model in three tasks. First, in node classification, a Bayesian formulation based on node copying achieves higher accuracy in sparse data settings. Second, we employ our proposed model to mitigate the effect of adversarial attacks on the graph topology. Last, incorporation of the model in a recommendation system setting improves recall over state-of-the-art methods.