Node Copying: A Random Graph Model for Effective Graph Sampling

Abstract

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.

References in corpus (26)

• Statistical mechanics of complex networks
• Semi-Supervised Classification with Graph Convolutional Networks
• BPR: Bayesian Personalized Ranking from Implicit Feedback
• Adversarial Attacks on Neural Networks for Graph Data
• Variational Graph Auto-Encoders
• Pitfalls of Graph Neural Network Evaluation
• MolGAN: An implicit generative model for small molecular graphs
• Learning Deep Generative Models of Graphs
• Adversarial Attack and Defense on Graph Data: A Survey
• Hiding Individuals and Communities in a Social Network
• NetGAN: Generating Graphs via Random Walks
• GraphGAN: Graph Representation Learning with Generative Adversarial Nets
• Sparse graphs using exchangeable random measures
• Beyond Homophily in Graph Neural Networks: Current Limitations and Effective Designs
• Random graph models for dynamic networks
• Overlapping stochastic block models with application to the French political blogosphere
• Fast Gradient Attack on Network Embedding
• Anti-Money Laundering in Bitcoin: Experimenting with Graph Convolutional Networks for Financial Forensics
• The Class of Random Graphs Arising from Exchangeable Random Measures
• Adversarially Regularized Graph Autoencoder for Graph Embedding
• Random Graph Modeling: A survey of the concepts
• Large Scale Graph Learning from Smooth Signals
• Variational Inference for Graph Convolutional Networks in the Absence of Graph Data and Adversarial Settings
• Bayesian Graph Convolutional Neural Networks using Node Copying
• Fisher-Bures Adversary Graph Convolutional Networks
• Non-Parametric Graph Learning for Bayesian Graph Neural Networks

Cited by in corpus (2)

• Robust Node Classification on Graphs: Jointly from Bayesian Label Transition and Topology-based Label Propagation
• Sampling Theory of Jointly Bandlimited Time-vertex Graph Signals